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.