Tag Archives: Partition

Divide and ponder

Partitioning is an essential component to achieving scalability in a database server and there are several reasons for adopting partitioning.

One reason is to overcome the performance shortcomings of index structures and the following two partitioning  methods can be used to mitigate them

  • An index can be partitioned on time to reduce the active insert area of an index, such that a greater proportion of the active area can be cached than would be possible without partitioning. This can be used to alleviate poor insert and update performance in large indexes.
  • An index can be partitioned in line with queried keys to reduce the search area of an index, such that a query can eliminate index partitions based on key search criteria. This can be used to reduce query time in large indexes.

Clearly, it is unlikely that the different partitioning requirements above will be in alignment and therefore attempting to partition indexes for both fast inserts and fast queries typically creates conflicting partitioning requirements and these schemes require careful design to achieve an optimal partitioning arrangement.

In addition, the following partitioning methods can be used to achieve general scalability by allowing parallel processing and by easing data life-cycle management.

  • A table or index can be abundantly and equitably partitioned to allow arbitrarily parallel and independent operations against it.
  • A table or index can be partitioned by time divisions to facilitate life cycle management such that old and obsolete partitions can be dropped.

In contrast to partitioning used to rescue index performance, these schemes are mutually accommodating and do not conflict with each other; nor do they not require design decisions – data can be implicitly divided into arbitrarily granular time divisions for lifecycle management and parallel query operations can exploit those partitions at will.

However, while it is beneficial to partition most structures by time division for general scalability and life-cycle management, tree indexes (B-Trees etc) do not behave well in this respect. This is because an index partitioned orthogonally to the keys used in a query requires all of the partitions to be scanned for that query. While adding more partitions may reduce the size of each individual partition, the cost of scanning multiple partitions rises linearly with the number of partitions, yet the search depth of each partition reduces logarithmically with partition size. Hence the more partitions we add, the costlier the query for a tree index.

This increase in retrieval cost for a tree index partitioned orthogonally to a query key over a non-partitioned index is given by P(1-logN(P)) where P is the number of partitions and N is the total number of keys. We can see that for any non-trivial value of N, the retrieval cost effectively increases linearly with the number of partitions.

Of course, we can scan those tree index partitions in parallel, but the linear increase in overall cost means we gain nothing – it will take about the same time as it would to scan an unpartitioned index and yet we have to perform a lot more work and consume many more resources to achieve much the same result.

So, while a tree index will offer logarithmic scaling for specific queries, when general scalability requirements impose query independent partitioning upon it, that benefit is lost.

(fr)Agile

The phrase “agile relational database” is commonly viewed as an oxymoron.

This is not surprising when you consider the decisions and actions required to create or alter a table or column; or simply to introduce a new query. Whereas the logical schema definition is straightforward in itself, the implications that can arise from a change in the logical model are another matter.

Consider the simple act of creating a new table with its associated columns. Easy enough from the standpoint of the data model – just define the column names, their data types and any constraints required. From the requirements definition standpoint, we are already done.

But then we are forced to consider the physical implementation of this table if it is going to contain anything other than a trivial amount of data and allow queries to deliver results in a reasonably timely manner. We now have to consider one or more of the following

  • How many rows will be stored in the table?
  • Are row deletes likely?
  • What queries are expected against the table?
  • Does the table need to be partitioned to support the number of rows?
  • What partitioning scheme would need to be used?
  • Should heap storage or clustered storage be used?
  • What storage parameters are best for the table?
  • What columns need to be indexed?
  • In what order should columns appear in each index key?
  • What type of index is required in each case?
  • What storage parameters are best for each index?
  • Do the indexes need to be partitioned and how?
  • Are materialised aggregations required?
  • Do one or more tables need to be de-normalized to support join performance?

Worse still, each of the above questions can arise each time we add a new column to a table or even just by using a new query.

Moreover, the inertia created by these decisions increases as the data volumes grow and it becomes ever more difficult to change them.

Yet none of the questions above have anything to do with our logical data model; they are all physical design considerations inflicted upon the data model by the underlying database engine.

There is nothing quite like agility – and this is nothing like it.