jump to navigation

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.

About these ads

Comments»

1. Σωκράτης - January 18, 2008

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 ?

2. Richard Foote - January 18, 2008

Fixed, thank-you.

Of course, it was a deliberate mistake just to make sure you were paying attention ;)

3. Robert - January 18, 2008

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…

4. Brian Tkatch - January 18, 2008

>*** 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?

5. Richard Foote - January 18, 2008

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 ;)

6. Richard Foote - January 18, 2008

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 !!

7. Don Seiler - January 18, 2008

hey that title is like a Dav– oh I see what you did there.

8. Martin W - January 18, 2008

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.

9. Richard Foote - January 19, 2008

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: http://richardfoote.files.wordpress.com/2007/12/index-internals-rebuilding-the-truth.pdf

10. coskan - March 10, 2008

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

11. Richard Foote - March 11, 2008

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 :)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,895 other followers

%d bloggers like this: