Index Efficiency 3

My last posting about indexes was an introduction to a pl/sql script that estimated the sizes that your indexes would be if you rebuilt them at a given percentage of utilisation for leaf blocks. By comparing these estimates with the actual size of the indexes you can get a quick report of indexes that are probably significantly larger than they really need to be. If you find that you have some indexes that look suspect the next step is to work out why; and whether or not it matters.

I can think of four classes of reasons why an index is larger than the sum of its data:

There is a bug somewhere in Oracle’s code to handle leaf node splits that can appear even at fairly low levels of concurrency . This results in excess ITL entries being allocated in the new leaf nodes. Once the ITL entires have been allocated they are always propagated across future leaf block splits – so you can easily end up with an index where half the space in most leaf blocks is wasted on unnecessary ITL entries.

The table has been subject to a massive delete (e.g. purging a lot of history) and the index hasn’t yet had time to refill the resulting empty space.

The index is a “FIFO” or “queue” index (such as the Advanced Queueing index organized tables (IOTs)). Data is inserted with a constantly increasing (time-based or sequence-based) key and is subsequently deleted; but if the deletion can be delayed or is not 100% perfect, the index can end up with a long near-empty “tail”.

Indexes with a large number of rows per key (by which I mean enough to fill at least one or two leaf blocks per key) can regularly cause 50/50 block splits as new rows are inserted “out of sequence” into an existing key range. Because of the typical nature of extent allocation such indexes are likely to be slower refilling the empty space than a “high-precision” B-tree index where you can expect a fairly small number of rows for each keys and a random arrival pattern for the key values.

If you can get some idea of how the data is spread across an index, and combine this with your knowledge of the application, you should be able to understand why an index has become larger than it should be and have a better idea of how to address the situation sensibly (ideally with a one-fix and subsequent minimum ongoing maintenance).

To start with you can try to answer a few simple questions, and the first question is always – can I see that the space wastage is having an effect on performance. Assuming you think it probably is then you can go on to the following:

Has someone deleted a large fraction of the table in the recent past. If so then any apparent space wastage may be the natural side effect, and it may be a good idea to rebuild the index. (In fact it may be a good idea to rebuild the table using the dbms_redefinition package first. Rebuilding tables is easy to do – sometimes too easy – but can have undesirable side effects in certain circumstances – which I’ll have to describe in another posting some time.)

Does your knowledge of the application tell you that this is a FIFO/Queue index – if so you probably need to include a call to coalesce the index regularly somewhere in the application code. It’s probably a good idea to rebuild the index once before you implement the regular coalesce to release any excess space back to the tablespace.

If the index appears to be about twice the size you expect it might be the concurrency bug or the unlucky 50/50 split problem (are you likely to have hot spots in the index, or a few very popular values) . Dump a few blocks (see the end of this note) from one of the higher numbered extents in the index to see if they have a lot of ITL entries, or if they have roughly 50% free space. If they have a lot of ITL entries (significantly more than your expected level of real concurrent change) then rebuild the index and set maxtrans  (possibly getting approval from Oracle support first for using the workaround described in one of my earlier articles). If you see half-empty blocks, then you may have to work out what it is about your application that makes that happen. Having thought about it, you may decide that the index shouldn’t even exist, or should be changed to a small collection of function-based indexes, or turned into a partitioned index. There are many variations on a theme – but the symptoms suggest an opportunity for improving the design and efficiency of your database,

If the index appears to be about four times the size you expect it’s possible that you’ve run into a variant of the 50/50 split problem combined with the concurrency bug. This is most likely to happen with a time-based or sequence-based index where (a) all inserts are taking place at the right hand block of the index and (b) the new data doesn’t arrive in absolutely perfect sequence order (after all, concurrent processes can get randomly pre-empted by the operating system). In this case you probably need to think about your options for recreating the as a reverse-key index as this generally spreads the inserts randomly across the index so you end up a lower degree of concurrent activity on any one block, and a more typical 70% utilisation because of the random arrival effect. (This is likely to increase the amount of random I/O suffered by that index, though.)

The last two cases, in particular, need a little more thought than just the simple “it’s two / four times the size”- and this is what the script index_efficiency_3.sql is about. Given the schema, table, and index name, it produces a report which tells you about the distribution of rows across index leaf blocks.

The script is quite expensive to run – it reads every index leaf block, calls an undocumented function for every non-deleted entry it finds, and then performs a large aggregation. Make sure you read the notes before you use the script.  (For an example of use, showing some excel charts from the output, see the note at this URL.)

Update:

As an example of the output from the code, here’s an index that I was looking at quite recently. The index is a classic example of the FIFO problem. Before a call to coalesce it totalled about 33,000 used leaf blocks and the report – – which took just over two minutes to produce – looked like this (with a couple of hundred lines removed, of course):

ROWS_PER_BLOCK     BLOCKS TOTAL_ROWS RUNNING_TOTAL
-------------- ---------- ---------- -------------
             1       8706       8706          8706
             2       4830       9660         13536
             3       2953       8859         16489
             4       1648       6592         18137
             5        997       4985         19134
             6        628       3768         19762
             7        300       2100         20062
             8        162       1296         20224
             9         87        783         20311
            10         52        520         20363
...
           227        100      22700         31871
           228        111      25308         31982
           229         84      19236         32066
           230         97      22310         32163
           231         77      17787         32240
           232         61      14152         32301
           233         54      12582         32355
           234        529     123786         32884
               ---------- ----------
sum                 32884    1887595

Note, particularly, that about 20,000 of the blocks have seven entries or fewer, while the mostly heavily used blocks manage to hold 234 entries.

After the coalesce (which also took just over two minutes), the report took 34 seconds to run, and looked like this:

ROWS_PER_BLOCK     BLOCKS TOTAL_ROWS RUNNING_TOTAL
-------------- ---------- ---------- -------------
             2          1          2             1
             7          1          7             2
            10          1         10             3
            11          1         11             4
            13          1         13             5
            14          1         14             6
            23          1         23             7
            29          1         29             8
            33          1         33             9
            34          1         34            10
...
           418         47      19646           730
           419         96      40224           826
           420        154      64680           980
           421        193      81253          1173
           422       3731    1574482          4904
               ---------- ----------
sum                  4904    1910921

We’ve dropped to less than 5,000 blocks, and only a scattering of blocks with a small number of index entries, and these are probably a result of the fact that coalesce doesn’t work across branch block boundaries.

The result shows us something else, though. Each leaf block is capable of holding 422 index entries rather than the limit of 234 that we saw before, this tells us that the index was probably also suffering from the concurrency bug (a problem that isn’t a great surprise when a sequence is used for a key and the levels of concurrency are quite high).

After the coalesce we still have 28,000 blocks in the index segment on its freelist (or marked as free in its space management bitmap – I can’t remember whether or not this index was in an ASSM tablespace) so at some stage we should rebuild the index, then change the initrans and fake in a sensible maxtrans, and introduce a regular coalesce.

There’s one more thing we could do to understand the state of a problem index – but I’ll have to leave that for another blog post.