jump to navigation

Introduction To Reverse Key Indexes: Part I January 14, 2008

Posted by Richard Foote in Index Access Path, Oracle Cost Based Optimizer, Oracle Indexes, Reverse Key Indexes.
trackback

Following on from the “8 things You May Not Know About Indexes”, #7 regarding Reverse Key Indexes requires a number of posts to do the subject justice. However, Part I will focus of the specific issue related to point # 7, namely:

“A REVERSE index can quite happily be used by the CBO to perform index range scans within an execution plan”.

Reverse Key Indexes are designed to resolve a specific issue, that being index block contention. Many indexes in busy database environments with lots of concurrent inserts (and in some scenarios updates and deletes as well) can suffer from index block contention (as highlighted by high levels of “buffer busy waits” and “read by other session” wait events for the index segments). Monotonically increasing indexes, such as Primary Keys generated by a sequence, are especially prone to contention as all inserts need to access the maximum “right-most” leaf block.  This is of particular concern in RAC environments, where this “hot” index block needs to be accessed by all the instances and is being bounced around the various SGAs causing expensive block transfers between instances.

A solution is make the index a Reverse Key Index.

CREATE INDEX bowie_reverse_idx ON bowie(id) REVERSE;

A Reverse Key Index simply takes the index column values and reverses them before inserting into the index. “Conceptually”, say the next generated ID is 123456, Oracle will reverse it to 654321 before inserting into the index. It will then take the next generated ID 123457 and reverse it to 754321 and insert it into the index and so on. By doing this, inserts are spread across the whole index structure, ensuring the right most block is no longer the only index leaf block being hammered. Index contention is dramatically reduced or eliminated entirely.

Reverse Key Indexes address a specific problem but may in turn introduce a number of problems themselves.

One problem is the simple fact index entries are no longer sorted in their natural order. Value 123456 is no longer adjacent to value 123457 in the index structure, they’re likely to be found in completely different leaf blocks. Therefore a range predicate (such as BETWEEN 123450 and 123460) can no longer be found by a single index probe, Oracle would be forced to search for each specific index value separately as each value in the range is likely to be in differing leaf blocks.

This makes it all just too difficult and troublesome for the Cost Based Optimizer (CBO). As a result, the CBO totally ignores Reverse Key Indexes when processing Range Predicates (eg. BETWEEN, <, >, <=, >=, LIKE etc.). Even innocent looking range predicates such as “BETWEEN 123456 and 123457″, with just the 2 values of interest are ignored by the CBO. A 10053 trace shows how the CBO totally ignores Reverse Key Indexes and doesn’t even bother to cost such accesses when processing Range Predicate conditions.

In the above example and in scenarios where it’s possible and practical to convert range predicates, use an IN clause instead, e.g. “IN (123456, 123457)” as Oracle will convert this into an OR clause with each equality condition usable with the Reverse Key Index.

Oracle is also clever enough to identify equality conditions that may be written as a range scan (e.g. BETWEEN 123456 and 123456) and use a Reverse Key Index accordingly.

Hints won’t work either. You may be able to force Oracle into performing a Full Index Scan but it will not perform an Index Range Scan with a Range Predicate.

But doesn’t all this mean I’m wrong when I suggested a Reverse Key Index can be used by the CBO to use Index Range Scans.

No :)

I’ve only described how Oracle ignores the use of a Reverse Key Index for Range Predicates, however Index Range Scans are quite possible.

Remember, a Reverse Key Index will reverse all values and if two values happen to have the same value or two index entries happen to have the same leading column, then all such values are indeed stored together and are logically adjacent to one another.

For example, if the Reverse Key Index is Non-Unique, Oracle must perform an Index Range Scan, even for equality predicates. I discussed this in some detail when discussing the differences between a Unique and a Non-Unique Index. Even if the column or columns have a PK or a Unique Key Constraint, Oracle will still check the next index entry “just in case” there are indeed duplicate values. Also, although usually used for monotonically index columns, there’s nothing preventing you from creating a Reverse Key Index on a Non-Unique column and all duplicate values must reside together in the index structure. Therefore an equality search that uses any Non-Unique Reverse Key Index will generate an Index Range Scan access

But even Unique indexes can be used to perform an Index Range Scan.

If you have a multi-column Unique Index but not all columns are being searched (although the leading column must be known), then again, all index values with the same leading column (or columns) must be stored together in the Reverse Key Index and an Index range Scan can be performed for such equality conditions.

For some examples of what I’ve discussed see this Reverse Key Part I Demo.

So yes, a Reverse Key Index can indeed be used by the CBO to perform Index Range Scans.

There are also a number of other issues (and indeed myths) associated with Reverse Key Indexes that will be discussed in the fullness of time.

About these ads

Comments»

1. jarneil - January 14, 2008

HI Richard,

You have in the 8th paragraph:
“One problem is the simple fact index entries are no longer sorted in their natural order”

Did you mean stored, rather than sorted – same letters different ordering!

cheers,

jason.

2. Richard Foote - January 14, 2008

Hi Jason

Actually, to be perfectly honest I’m not entirely sure which word I meant to type !!

Either word kinda means what I trying to say as non-reverse indexes are both stored and sorted in their natural “binary” order within the index.

Whereas reverse indexes are neither stored or sorted in their natural binary order.

So you pick which word you prefer and makes the most sense and I’ll use it for you :)

3. Robert - January 14, 2008

Jason, funny coincidence. I would translate the sentence as “One problem is the simple fact index entries are no longer stored sorted according to their natural order.” But then again, I’m not a native speaker. :-)

Richard, it started to dawn on me when I read the highlighted “predicates” and two paragraphs above the smiley I slapped my hand on my forehead. It’s so obvious. Man…

Thanks for handing me the crutch, Richard!

4. Richard Foote - January 14, 2008

No worries Robert. After All, sometimes it’s those obvious things staring right in front of you that are hardest to spot … ;)

5. Lookup Now - July 2, 2008

Very Infomrative site, found it quite educational. I’ll definately bookmark this.

6. java4b2b - February 14, 2009

wonder can you have both an index and a reverse key index on the same column?

7. Richard Foote - February 17, 2009

Hi Java

The short answer is no.

The slightly longer answer is why would you want to do such a thing when the idea of using a reverse key index is to reduced index contention. If you have both a reverse and a noreverse index, the reverse index would be pointless as you’ll still have the contention issues with the noreverse index. Therefore, Oracle allowing you to do so would make no sense.

However, the best answer is to suggest you simply try it out and find out yourself. Rather than wait potentially days for the answer, typing 3 short commands in a sqlplus session would give you the answer:

SQL> create table a (col1 number);

Table created.

SQL> create index a_idx on a(col1);

Index created.

SQL> create index a_rev_idx on a(col1) reverse;
create index a_rev_idx on a(col1) reverse
*
ERROR at line 1:
ORA-01408: such column list already indexed

There’s no need to wonder when it’s so easy to find out …

8. Raja - August 10, 2009

Hi,

How can we identify there is an Index Contenstion is High. Is there any formula to calculate the Index Contention apart from looking at High Buffer Busy Waits.

Raja

Richard Foote - August 20, 2009

Hi Raja

There’s no formula as such. If you have high buffer busy waits and they’re a significant factor in causing response times or throughput times to be unacceptable, then you have a problem worth looking at. Looking a v$segment_statistics is also a good place to start for any general high contention issues.

9. Navodaya - October 7, 2009

Hi ,
This article is really gives good understanding of the reverse key indexes .
Thanks
Navodaya

10. Jan - May 7, 2010

If we have an index T_IDX (c1, c2) and we do rebuild with a REVERSE option:

ALTER INDEX T_IDX REBUILD REVERSE

It reverses values in both of the columns?

Thanks, Jan

Richard Foote - May 12, 2010

Hi Jan

Yes it does. Very simple demo to find out:

SQL> create table abc (a varchar2(10), b varchar2(10));

Table created.

SQL> insert into abc values ('ABC', 'EFG');

1 row created.

SQL> commit;

Commit complete.

SQL> create index abc_i on abc(a,b) reverse;

Index created.

SQL> select header_file, header_block from dba_segments where segment_name = 'ABC_I';

HEADER_FILE HEADER_BLOCK
----------- ------------
          5       289161

SQL> alter system dump datafile 5 block 289162;

System altered.


row#0[8019] flag: ------, lock: 0, len=17
col 0; len 3; (3):  43 42 41
col 1; len 3; (3):  47 46 45
col 2; len 6; (6):  01 44 69 02 00 00
11. Rohit Gupta - July 5, 2010

Hi Richard,

First of all, thanks a lot for this very very good note on reverse key indexes. I am big fan of your technical acumen.

Now to my question (rather doubt) – So this means for a purely unique column (like a sequence ever increasing), reverse key index is the most suitable because it speeds up the inserts. But then at the same time, you also stated that on such a column, CBO might not go for an index scan. Is that right? Then why to use reverse key index, or rather when to use reverse key index?

I understand that index scans are only possible with a reverse key index when the column values are either non-unique or if the index is a multi-column (concatenated index). With a uique valued single column reverse key index, index scans are not possible and hence a reverse key index is not suitable even though it might dramatically reduce index block contention for insert operations. Is that understanding correct?

Also, is the reverse key index helful for tables with heavy inserts only? I mean what other cases/examples in support of reverse key indexes?

Sorry, these might sound a bit naive, but i have not used reverse key indexes ever :(

Thanks
Rohit

12. Richard Foote - July 20, 2010

Hi Rohit

You use reverse key indexes when the benefit they provide, that mainly being faster insert times due to reduced contention, is greater or more important than the possible downsides, such as not being able to service range based predicates.

Perhaps you have a PK that is only ever accessed via equality predicates and by making the index a reverse key index, you enable insert performance that meets business requirements.

The only real benefit of a reverse key index is to reduce contention issues (especially in RAC based environments). If you have no such issues, you likely have no reason for using them.

13. Nigel Noble - July 21, 2010

Hi Richard,

Nice post.

One of the issues I have seen using reverse key indexes, is they can then introduce much more phyisical IO on both reads and writes. Your data can be spread over many more blocks. You might find you trade one kind of contention problem for a physical IO problem.

Then it’s a case of working out which problem costs you more (in elapsed time/CPU time) and choosing the cheaper one.

Regards

Nigel.

Richard Foote - July 22, 2010

Hi Nigel

Absolutely, if you effectively randomise the inserts into the index, you’re going to hit more disitnct leaf blocks and potentially generate more PIOs.

Everything comes at some cost. Determining whether the cost is worth it is what it’s all about.

14. Hans van Driel - August 2, 2012

Richard,

Could be explain why there is a hugh increase of db block gets and redo size when using the reverse key index ?

demo>drop table t1;

Table dropped.

demo>create table t1 (a number);

Table created.

demo>create index t1_idx on t1(a);

Index created.

demo>set autotrace on
demo>insert into t1 select level from dual connect by level <=500000;

500000 rows created.

Execution Plan
———————————————————-
Plan hash value: 230221486

—————————————————————————–
| Id | Operation | Name | Rows | Cost (%CPU)| Time |
—————————————————————————–
| 0 | INSERT STATEMENT | | 1 | 2 (0)| 00:00:01 |
|* 1 | CONNECT BY WITHOUT FILTERING| | | | |
| 2 | FAST DUAL | | 1 | 2 (0)| 00:00:01 |
—————————————————————————–

Predicate Information (identified by operation id):
—————————————————

1 – filter(LEVELdrop table t1;

Table dropped.

demo>create table t1 (a number);

Table created.

demo>create index t1_idx on t1(a) reverse;

Index created.

demo>set autotrace on
demo>insert into t1 select level from dual connect by level <=500000;

500000 rows created.

Execution Plan
———————————————————-
Plan hash value: 230221486

—————————————————————————–
| Id | Operation | Name | Rows | Cost (%CPU)| Time |
—————————————————————————–
| 0 | INSERT STATEMENT | | 1 | 2 (0)| 00:00:01 |
|* 1 | CONNECT BY WITHOUT FILTERING| | | | |
| 2 | FAST DUAL | | 1 | 2 (0)| 00:00:01 |
—————————————————————————–

Predicate Information (identified by operation id):
—————————————————

1 – filter(LEVEL<=500000)

Statistics
———————————————————-
5944 recursive calls
1259447 db block gets
10490 consistent gets
10477 physical reads
140978084 redo size
401 bytes sent via SQL*Net to client
342 bytes received via SQL*Net from client
3 SQL*Net roundtrips to/from client
263 sorts (memory)
0 sorts (disk)
500000 rows processed

15. Hans van Driel - August 2, 2012

These were the statistics from the first insert.

Statistics
———————————————————-
4351 recursive calls
43561 db block gets
6088 consistent gets
5144 physical reads
41750704 redo size
401 bytes sent via SQL*Net to client
342 bytes received via SQL*Net from client
3 SQL*Net roundtrips to/from client
190 sorts (memory)
0 sorts (disk)
500000 rows processed

David Penington - September 14, 2012

I would guess that it’s because with a normal index, each of the rows you inserted goes onto the end of the index (and Oracle has some optimisations to handle that). Once an index block is full, Oracle doesn’t have to do anything to it except for b-tree rebalancing operations. With the reverse key index, once the index has more than a few blocks, each consecutive row goes into a different place in the index, and you get extra costs maintaining all those different blocks, especially if the database didn’t have enough memory to cache them.
The redo size is three times as big as well.
This suggests that reverse key indexes have a significant cost if a single session is inserting many rows at once.

Hans van Driel - September 14, 2012

David, thanks for your answer. So there can be a hugh performance penalty when inserting many rows a once, as seen by the increase of the redo size and db block gets.

16. Richard Foote - September 19, 2012

Hi Hans

That’s correct. As David as stated, you have to visit many more leaf blocks when adding the data, increasing the number of db block gets. Additionally, you’re also performing 50-50 block splits rather than the really cheap and efficient 90-10 splits which further increases the costs and overheads, especially undo.

17. Anshuman bajaj - March 4, 2013

Thanks richard
completly awsome answer

Cheers dear


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,715 other followers

%d bloggers like this: