##
Store Indexes In A Larger Block Tablespace: Height Reduction 1/2 Myth (Five Foot One)
*March 26, 2008*

*Posted by Richard Foote in Index Block Size, Index Height, Index Internals, Oracle General, Oracle Indexes, Oracle Myths, Tablespace Management.*

14 comments

14 comments

A common misconception with using a larger block tablespace specifically for indexes is that this will result in a reduction in the height of indexes and hence “flatten” index structures.

However, this is only partly true.

A few little generalisations to begin with.

First, most databases out there have a default block size of 8K. I won’t go into a big discussion on what the database block size should be set to (maybe another time), however I will say most databases these days have a default block size of 8K and that it’s certainly questionable to have the database block size set to 2K.

Note also in many common platforms (e.g. Windows, Linux) the maximum block size limit is 16K. So in many environments, when we talk about moving indexes into a bigger sized block, it specifically involves moving from an 8K to a 16K block size.

Yes, in theory you could move an index from (say) a 2K block size up as high as a 32K block size but you would need to question why the default is so low to begin with and whether the upper value is actually supported in your environment.

I make this point because the difference between block sizes makes a huge difference in the probability of the index height actually being reduced.

So let’s start with an example of moving indexes between an 8K default block size to a 16K block tablespace, not least because the arithmetic is easier and extrapolate out as we go along.

So in our example, the new block size is double or 2 times that of the default one. By doubling the block size, we effectively 1/2 the number of necessary leaf blocks in the index structure. By having fewer leaf blocks we also therefore reduce the overall associated block level overheads so the actual reduction in leaf blocks could be a tad more, but we’ll say a 1/2 reduction to keep the numbers nice and simple.

Note the reduction in leaf blocks in therefore simply 1 / the ratio of block increase (1/2). Moving from a 2K block to a 32K block is 16 times larger so we’ll have approximately 1/16 the number of leaf blocks.

So how does (say) halving the number of leaf blocks impact the overall height of the index ?

We obviously can’t reduce the height of an index with a height of just 1. The index consists of just the one block so a larger block would simply mean the block having more free space.

To reduce the height of an index with a height of 2 (back to 1), we therefore must be able to store all index entries within a single block. Therefore, in the 8K to 16K example, the index can only have 2 full leaf blocks for this to be possible. If an index has 3 or more “filled” leaf blocks, the index must remain at a height of 2 as we can’t fit all the index entries into the single larger index block.

Importantly therefore, all indexes with a height of 2 with more than 2 full leaf blocks would not reduce in height by simply doubling the block size. This could very well be the vast majority of indexes at this level.

For an index with a height of 2, the index must have less full leaf blocks than the ratio of block increase for a height reduction to be possible. In our best case scenario, 2K block to 32K block, any index with more than 16 full leaf blocks would not reduce in height.

To reduce the height of an index with a height of 3 (back to 2), we must therefore be able to store all intermediate branch blocks into the one branch (root) block. When we double the block size, we therefore 1/2 the leaf blocks and 1/2 again the necessary branch blocks. Therefore the necessary branch blocks is 1/(2×2) = 1/4 that of the default block size. Therefore any index with a height of 3 that has more than 4 full intermediate branch blocks will again not reduce in height as again all the necessary branch information would not fit in one root block.

Importantly therefore, all indexes with a height of 3 with more than 4 full intermediate branch blocks would not reduce in height by simply doubling the block size. Again, this could very well be a significant proportion of all indexes at this level. Note also in many databases, the vast majority of indexes have a height of 3 or less so by simply doubling the index block size, most indexes would not reduce in height …

For an index with a height of 3, the index must have less full intermediate branch blocks than the ratio of block increase to the power of 2 for a height reduction to be possible. In our best case scenario, the 2K block to 32K block, only those indexes with more than 16×16=256 full intermediate branch blocks will reduce in height. This is therefore likely to be a far higher proportion of all such indexes.

You see the pattern …

To reduce the height of an index with a height of 4 (back to 3), we must therefore store all first level intermediate branch blocks into the one branch (root) block. When we double the block size, we therefore 1/2 the leaf blocks, 1/2 again the second level intermediate branch blocks and 1/2 again the first level intermediate branch blocks. Therefore the necessary first level intermediate branch blocks is 1/(2x2x2) = 1/8 that of the default block size. Therefore any index with a height of 4 that has more than 8 full intermediate first level branch blocks would again not reduce in height as again all the necessary first level branch information would not fit in the one root block.

Importantly therefore, all indexes with a height of 4 with more than 8 full intermediate branch blocks will not reduce in height by simply doubling the block size. However, as the index height increases, the ratio of indexes where this is likely to be the case decreases.

For our best case scenario, 2K to 32K, we now start hitting very large numbers 16x16x16=4096 so the likelihood of a index height reduction is very very high.

And so on …

The important point being that by simply doubling the index block size, in most databases, the vast majority of indexes are actually quite unlikely to reduce in height as the index needs to be within very limited size boundaries for the index height to reduce. The greater the index height however, the greater the index size boundaries whereby an index height reduction is possible.

Also, the greater the index block increase, proportionally the fewer the index blocks and so greater the likelihood of an index height reduction.

This demo on the Impact Of Block Size On Index Height illustrates that by simply doubling the index block size, the height of an index (in various sizes) rarely decreases.

One final point. With our height 4 index example, note the index can only have a maximum of 8 first level branch blocks for the height to reduce. Therefore, in effect, we’re replacing a maximum of 9 x 8K branch blocks with 1 x 16K block. If this index is frequently accessed, these 9 branch blocks are likely cached and we only need to read two of these blocks anyways for an index range scan (for a total of 16K). After the rebuild, we still need to read this block (16K again) anyways so from a purely performance perspective with regard to just simply reducing the index height, the so-called performance benefits are often very much exaggerated.

As we’ll see in the next epic episode of this series, performance can actually decrease :(

Next time someone claims moving indexes into a larger block size will decrease the height and flatten an index, remember it really does depend. In many databases, especially when the index block size is just doubled, it’s actually quite surprising just how unlikely it is for an index to actually decrease in height.