Introduction To Reverse Key Indexes: Part III (A Space Oddity) January 18, 2008
Posted by Richard Foote in Index Block Splits, Index Internals, Oracle Indexes, Performance Tuning, Reverse Key Indexes.trackback
A possibly significant difference between a Reverse and a Non-Reverse index is the manner in which space is used in each index and the type of block splitting that takes place.
Most Reverse Key Indexes are created to resolve contention issues as a result of monotonically increasing values. As monotonically increasing values get inserted, each value is greater than all previous values (providing there are no outlier values present) and so fill the “right-most” leaf block. If the “right-most” block is filled by the maximum current value in the index, Oracle performs 90-10 block splits meaning that full index blocks are left behind in the index structure. Assuming no deletes or updates, the index should have virtually 100% used space.
However, it’s equivalent Reverse Key index will have the values reversed and dispersed evenly throughout the index structure. As index blocks fill, there will be a very remote chance of it being due to the maximum indexed value and 50-50 block splits will result. The PCT_USED is likely therefore to be significantly less, averaging approximately 70-75% over time.
Therefore, for indexes with no deletions, a Reverse Key index is likely to be less efficient from a space usage point of view.
However, if there are deletions, the story may differ.
Deleted space can be reused if an insert is subsequently made into an index block with deleted entries or if a leaf block is totally emptied. However, if a leaf block contains any non-deleted entries and if subsequent inserts don’t hit the leaf block, then the deleted space can not reused. As monotonically increasing values in a non-reverse index only ever insert into the “right-most” leaf block, it won’t be able to reuse deleted space if leaf blocks are not totally emptied. Overtime, the number of such “almost but not quite empty” index leaf blocks may in some scenarios increase to significant levels and the index may continue to grow at a greater proportional rate than the table (where the reuse of space is set and controlled by the PCTUSED physical property).
However, Reverse Key indexes will be able to reuse any deleted space as they evenly distribute inserts throughout the index structure. Overtime, the index is likely to grow at a similar proportional rate as the table.
For indexes that have deletions resulting in many sparsely (but not totally emptied) leaf blocks, a Reverse Key index could be more efficient from a space usage point of view.
See this demo Differences in Space Usage Between a Reverse and a Non-Reverse Index for further details.
Richard Foote's Oracle Blog 
Richard, I think there is a mistake in this demonstration:
the *second* occurrence of
SQL> ANALYZE INDEX normal_index VALIDATE STRUCTURE;
should be
SQL> ANALYZE INDEX reverse_index VALIDATE STRUCTURE;
I suppose ?
LikeLike
Fixed, thank-you.
Of course, it was a deliberate mistake just to make sure you were paying attention 😉
LikeLike
Once again, pretty interesting stuff (despite the hammer)! 🙂
You write: “Reverse Key indexes will be able to reuse any deleted space as they randomly distribute inserts throughout the index structure.”
Considering increasing key values (e.g. from a sequence) wouldn’t it be more accurate to write “… as they _evenly_ distribute inserts throughout the index structure”? I mean, since the byte order is reversed the leading byte(s) follow a modulo structure, i,e, values from 0x00 to 0xFF will repeat in position 0, position 1 etc. Of course, this is no longer (exactly) true if there are holes in the key sequence…
LikeLike
>*** At the end of this process, PCT_USED is only 53%. If this were to
>continue, this figure will only get worse …
Is that because more DELETEs are assumed? What if there were no more DELETEs? As soon as the new set of blocks matched the old set (in quantity), would it not then get better? Or am i completely missing the point?
LikeLike
Hi Robert
Yes, I prefer your wording and I’ve changed it, thanks.
The word “random” popped into my head because when a *specific* index entry is inserted in a non-reverse index, it always goes into the right-most leaf block but with a reverse index it goes into a random leaf block. But I agree, the word evenly describes things much better.
“It ain’t easy” sometimes expressing things right 😉
LikeLike
Hi Brian
Yes, assuming more deletes and assuming more and more leaf blocks get left behind with few remaining index entries. Overtime, the proportion of sparsely populated index blocks continues to grow to the point when possibly only a small fraction of an index is densely populated.
This however will not be a problem for the reverse key index.
You have the point perfectly !!
LikeLike
hey that title is like a Dav– oh I see what you did there.
LikeLike
Hi Richard,
That’s an interesting side effect of using reverse key indexes. I’m struggling with understanding something though.
If the normal index is carrying out 90:10 block splits why is pctused 100% rather than a smidge under 90%? Once the growing block hits 100% and is split, won’t the block “left behind” be 90% full and so the index will consists of 90% full leaf blocks except for one partially filled leaf block and, I am guessing, 75% full blocks for the branch nodes? Your demo clearly shows pct_used as 100 percent and it’s bugging me why.
LikeLike
Hi Martin
That’s a very good question. As I say in my seminar, the term 90-10 is very confusing and I’m not sure why Oracle calls the split by that name.
What Oracle actually does when performing the “so-called” 90-10 split, is that it leaves the original full block alone full of the existing index entries and simply adds a new block into the index structure and puts just the new index in there, all on its little lonesome. The only change to the existing full block is to change the kdxlenxt pointer which was previously empty to point to the new index block.
So really it performs a 100-1 split, 100% remains in the full block and the 1 new entry goes into the new block.
However, this activity is called a 90-10 split by Oracle in statspack reports and the such and why I too refer to it as such.
This is all explained in the Index Internals presentation: https://richardfoote.files.wordpress.com/2007/12/index-internals-rebuilding-the-truth.pdf
LikeLike
Hi Richard,
I did not get something.
What is the difference between
creating a reverse index on a table which is already populated and populate an emprty table which is indexed as reverse
because PCT_USED for first one is %90 but second one has %68
FYI; I forgot to truncate the reverse_details table before creating reverse index and face with %90 result
LikeLike
Hi Coskan
When you create a table that’s already populated (or when you rebuild an exisiting index), Oracle first sorts the indexed values and fills the index structure up to the value of pctfree. By default, the pctfree of an index is 10% so an index when first created has a pct_used of 90%.
If the table is empty when the index is created, the index is likewise empty and so the pctfree is meaningless. As we insert values into the table, the index leaf blocks in the reverse index fill and eventually perform 50-50 block splits as it grows. This results in 1/2 empty blocks which are then subsequently inserted into. At the end of your insert process, the index hence ended up at only 68% full following all the 50-50 block splits that resulted.
Hope this makes sense 🙂
LikeLike
Hi Richard, i am getting PCT_USED as 100% for normal index even after deleting majority of rows from the table.
SQL> SELECT blocks,del_lf_rows,used_space,lf_blks, pct_used FROM index_stats;
BLOCKS DEL_LF_ROWS USED_SPACE LF_BLKS PCT_USED
———- ———– ———- ———- ———-
2048 0 16003760 1999 100
SQL> DELETE reverse_details_del1 WHERE MOD(id,250) 0;
996000 rows deleted.
SQL> commit;
Commit complete.
SQL> INSERT INTO reverse_details_del1 SELECT rownum+1000000, ‘David Bowie’ FROM dual CONNECT BY LEVEL commit;
Commit complete.
SQL> ANALYZE INDEX del1_normal_index VALIDATE STRUCTURE;
Index analyzed.
SQL> SELECT blocks,del_lf_rows,btree_space,used_space,lf_blks,round((used_space/btree_space),0) * 100 “%”,pct_used FROM index_stats;
BLOCKS DEL_LF_ROWS BTREE_SPACE USED_SPACE LF_BLKS % PCT_USED
———- ———– ———– ———- ———- ———- ———-
4224 995628 33055720 33015361 4126 100 100
This is in Oracle 12.1.0.2.0
LikeLike
734 5872 leaf node splits 12375 DEBUG
736 5888 leaf node 90-10 splits 12375 DEBUG
— after inserting 1 million rows
734 5872 leaf node splits 14373 DEBUG
736 5888 leaf node 90-10 splits 14373 DEBUG
BLOCKS DEL_LF_ROWS BTREE_SPACE USED_SPACE LF_BLKS % PCT_USED
———- ———– ———– ———- ———- ———- ———-
2048 0 16016116 16003760 1999 100 100
— deleting all but every 250th row
734 5872 leaf node splits 14373 DEBUG
736 5888 leaf node 90-10 splits 14373 DEBUG
BLOCKS DEL_LF_ROWS BTREE_SPACE USED_SPACE LF_BLKS % PCT_USED
———- ———– ———– ———- ———- ———- ———-
2048 996000 16016116 16003760 1999 100 100
— insert million rows greater than last max value inserted
734 5872 leaf node splits 16500 DEBUG
736 5888 leaf node 90-10 splits 16500 DEBUG
BLOCKS DEL_LF_ROWS BTREE_SPACE USED_SPACE LF_BLKS % PCT_USED
———- ———– ———– ———- ———- ———- ———-
4224 995628 33055720 33015361 4126 100 100
2127 leaf blocks added with 90-10 split
LikeLike
I could understand 90-10 split for normal index when new rows are inserted with a value higher than max value inserted before. But PCT_USED from index stats showing 100% in my case and 53% in your demo. could u please explain?
LikeLike
The difference is that all your deleted entries are still listed as such, check out your del_lf_rows value. The problem with pct_used is that it considers index entries marked as deleted as still being “used”, when in actual fact, they’re really “free” space just waiting to be cleaned up by subsequent activities in the leaf block.
LikeLike
[…] While researching for this I came across another blog entry called “A space oddity”: https://richardfoote.wordpress.com/2008/01/18/introduction-to-reverse-key-indexes-part-iii-a-space-od… by Richard Foote, who seems to be really deep into Oracle index internals. So don’t leave his […]
LikeLike
Hi Richard,
I have a table with standard two column primary key index running on two node RAC cluster.
The application for whatever reason updates the table (and primary key) very frequently from multiple sessions.
I am seeing a lot of waits for “read by other session” which seems to stem from this index.
I was wondering if rebuilding this primary key index as a reverse key index would help alleviate this, or whether I should use an alternative strategy to create the index over more blocks instead?
Thank
Ian
LikeLike
Hi Ian
Possibly.
However, need to be careful you don’t introduce worse issues such as excessive IOs due to the fact that the whole, much bigger index now effectively is accessed and needs to be stored in the buffer cache rather than just the tiny index subset.
Additionally, issues due to range predicates no longer being supported once index is reversed.
If you have Partitioning option, a Hash Based Index might be a better solution.
Better still, perhaps assigning a different set of cached values to different instances to avoid so contention.
But yes, reversing the index could reduce contention with multiple sessions waiting for the same IO call to complete.
LikeLike