Reverse Key indexes

Can't understand the point in a reverse key index at the end of the day. Yes i cna see some advantages in that the B-tree index will be more evenly balanced when indexing on a column with sequential values. But then to go and reverse the values surely this counters the whole point of indexes in that it scatters the sequential values so that 2 sequential values will end up in different branches when if they hadn't been reversed they would have been found more quickly since they would be on the same branch.

Has anyone used RKIs to their advantage?

Cheers
Gus
:confused: Again!

it wud be useful were in u have a column with values in ascending/descending order....& the values in index wud be spread accross..due vaules stored in reverese struct...

query with equality predicates wud be faster...
also if u wanted to update the table based on the column having ascending/descending vales...the updates on index spread rather than occuring at same place if otherwise.

Abhay.

I have never used RKIs but i am pretty sure i have a fairly good understanding or as much as anyone can have not having used them before. But I still fail to see their advantage and there must be, sorry if i'm a bit slow on this one!

Abhaysk you said...
"it wud be useful were in u have a column with values in ascending/descending order....& the values in index wud be spread accross..due vaules stored in reverese struct..."

As far as i know all indexed columns by nature have values that are either ascending or descending, big deal, if they weren't i use a bit-map index ideal for columns of low cardinality! If the values were spread as you say i would have used a B-tree not reversed, reference my last message. Not sure what you are trying to say here, perhaps you could clarify.


Abhaysk you said...
"query with equality predicates wud be faster...

Faster than range scans, true of any index I would think.


"also if u wanted to update the table based on the column having ascending/descending vales...the updates on index spread rather than occuring at same place if otherwise."

Huh, you got me there?

Cheers
Gus

consider an example...

U have emp id from 7001 to 7999.

now as reverse index store values in reverse order...

u will see..id values begning with 1,2,3,4,5...n so..

so now with equaility predicate search for particular id wud be faster than any other indx...
as the range of values with any number(1 or 2 or so) wud be much less than the range of values starting with 7...

okie now with updates goin on in real time systems...since indx values wud be spread ... i/o contention wud be minimal....

Quote:

---

Abhaysk you said...
"it wud be useful were in u have a column with values in ascending/descending order....& the values in index wud be spread accross..due vaules stored in reverese struct..."

As far as i know all indexed columns by nature have values that are either ascending or descending, big deal, if they weren't i use a bit-map index ideal for columns of low cardinality! If the values were spread as you say i would have used a B-tree not reversed, reference my last message. Not sure what you are trying to say here, perhaps you could clarify.

---

this was just to support above 2 statements.

however it has as well disadvantages over b tree normal.

i love Jmodic to throw more light on this.

Abhay.

The point of reverse key indexes is to avoid contention for index blocks.

If you have multiple sessions inserting rows into a table then the table inserts themselves can be spread out among multiple blocks, according to which blocks are on the freelist(s) etc.

If the table has a synthetic PK derived from a sequence, then multiple sessions are trying to modify the same index block at the end of the index structure. A reverse key index avoids this contention by storing sequential values in a non-sequential manner.

The only disadvantage is that you lose the ability to range-scan, but that's generally not an issue with synthetic PK's, and you can still do a fast full index scan if need be.

Quote:

---

Originally posted by abhaysk
i love Jmodic to throw more light on this.

---

ALthough there is not much to be added to slimdave's explanation, you have chalanged me directly, so I will throw just one small comment....

Quote:

---

so now with equaility predicate search for particular id wud be faster than any other indx...

---

No, the index serach in this case will actually be a bit slower compared to normal btree index (the difference will be minimal though). The actual index tree traversing is identical in both cases, but there is a tiny overhead of CPU time with RK indexes as Oracle has first to reverse the order of bytes of the searched values to make it the same as it is stored in the index.

And as slimdave said, you (generaly) can't use RK indexes for range searches, they can only be used for equality based predicates.

Their main (and only?) purpose is to avoid "hot index blocks" when inserting rows with sequence-generated key values. So they were not invented to speed-up queries but to speed-up inserts....

Fantastic, much appreciated guys. RKIs was an area that i never really questioned before but having to look a bit closer now that the PT exam is coming up, i decided it was time to clear the doubts.

I assume (hope i don't become as ass for doing so) that reversing the key also means that the index will be less deeply nested (fewer levels) than if it were an ordinary B-tree index (when using sequence generated keys).

Jmodic....
"No, the index serach in this case will actually be a bit slower compared to normal btree index (the difference will be minimal though). The actual index tree traversing is identical in both cases, but there is a tiny overhead of CPU time with RK indexes as Oracle has first to reverse the order of bytes of the searched values to make it the same as it is stored in the index."

Believe it or not was not aware of this!

Jmodic & Slimdave....
Their main (and only?) purpose is to avoid "hot index blocks" when inserting rows with sequence-generated key values. So they were not invented to speed-up queries but to speed-up inserts....

This makes complete sense!


Slimdave...
The only disadvantage is that you lose the ability to range-scan, but that's generally not an issue with synthetic PK's, and you can still do a fast full index scan if need be.

Do you mean that range scans can be done with RKIs but will be very inefficent.

Beats me as to why the certification books (i am using Sybex) dont give these reasons as to why one would use RKIs. It would make things alot easier to understand on first meeting!


Much Appreciated
Gus

range scan does not wor with RK

in a b-tree index if you say

where empno between 25 and 35 then it reads the index sequentially (hence range scan)

if it was RK then there is no possibility to do so, it would has to read

52
62
72
82
92
03
13
23
33
43
53

I dont think I can read that as range and I dont think Oracle can neither :o

RK indexes also require the use of the cost-based optimizer -- another reason not to use RBO.

Sorry instead of...

Do you mean that range scans can be done with RKIs but will be very inefficent.

I meant to say...

Do you mean that range scans will end up becoming a FTS and therefore will be very inefficent.

:D
Gus

range scans are just not possible, because within the index structure physically adjacent key values are not sort-order adjacent.

The optimizer may choose an FFI or table scan, which would not be as efficient.

Not usually a problem because there is not much logical meaning in a range-scan of a synthetic key value, so an application is not likely to generate a query that would be helped by one.

I suppose that RK indexes cannot be used in an access path to provide a sort-order either.

Quote:

---

Originally posted by slimdave
range scans are just not possible, because within the index structure physically adjacent key values are not sort-order adjacent.

---

Well, to be absolutely precise, range scans on RK indexes actauly *are possible*, however only under very specific circumstances. There are two conditions to be met for index range scan to occur on RK indexes:

1. Index must be composite one (with two or more columns indexed)
2. There query must contain the equality predicate on leftmost column(s) of the index

Consider this example:

You have a reveresed key index consisting of two columns - col1 and col2. You have something like the following values stored in those indexed columns:

Code:

---

col1, col2
----  ----
  1,    1
  1,    3
  1,    4
...    ...
  17,    1
  17,    7
  17,  34
  17,  188
  18,    0
  19,    6
  21,  -1
...    ...

---

Now the optimizer will be able tu use range scan on this reversed key index for the query like the following:

Code:

---

SELECT * FROM my_table
  WHERE col1 = 17;

---

or for the ones like those:

Code:

---

SELECT * FROM my_table
  WHERE col1 = 17 AND col2 > 50;
SELECT * FROM my_table
  WHERE col1 = 17 AND col2 BETWEEN 50 AND 60;
SELECT * FROM my_table
  WHERE col1 = 17 AND col2 != 12;

---

That is because of the fact that despide the values for COL2 are reversed before they are stored in the RK index, they will still be stored addjacent to each other for the same COL1 value. So all the index entries for the same COL1 will be stored in the same (or at least adjacent ) leaf block(s) and thus range scan will be possible if you are looking for only one COL1 value.

"range scans are just not possible, because within the index structure physically adjacent key values are not sort-order adjacent."

did I say they were, i did correct myself?



"Not usually a problem because there is not much logical meaning in a range-scan of a synthetic key value, so an application is not likely to generate a query that would be helped by one. "

What do you mean? I would have thought that a range-scan of a synthetic key value was most logical or are we still talking in relation to RKIs here?



I suppose that RK indexes cannot be used in an access path to provide a sort-order either.

Not sure what you mean by this.


Gus

Quote:

---

"range scans are just not possible, because within the index structure physically adjacent key values are not sort-order adjacent."

did I say they were, i did correct myself?

---

no, you just asked whether they were not possible or just inefficient. That was an explanation of why they weren't possible. (OK, for non-composite indexes)

Quote:

---

"Not usually a problem because there is not much logical meaning in a range-scan of a synthetic key value, so an application is not likely to generate a query that would be helped by one. "

What do you mean? I would have thought that a range-scan of a synthetic key value was most logical or are we still talking in relation to RKIs here?

---

If you have a synthetic, numeric PK there is generally not a lot of call for query predicates like ...

MY_PK_COLUMN between 1000 and 1024

The range is not generally meaningful in terms of business logic.

Quote:

---

I suppose that RK indexes cannot be used in an access path to provide a sort-order either.

Not sure what you mean by this.

---

An index can be used as a means of satisfying an ORDER BY clause (with some restrictions).

So if you have an index of EMPLOYEE_START_DATE and you execute ...

SELECT * FROM EMPS
ORDER BY EMPLOYEE_START_DATE

... the optimizer might choose to scan the index in ascending order to retrieve the table rows, rather than FTS then sort. A RK index would not provide the sort order, so couldn't be used for this purpose.

Quote:

---

Originally posted by jmodic
you have chalanged me directly, so I will throw just one small comment....

---

Jurij:
Hey i didnt challange u........well i thought u have better knowledge in oracle than any 1, so i said it wud be intersting to c u comment u this thread...and u did..

Quote:

---

Originally posted by jmodic

No, the index serach in this case will actually be a bit slower compared to normal btree index (the difference will be minimal though). The actual index tree traversing is identical in both cases, but there is a tiny overhead of CPU time with RK indexes as Oracle has first to reverse the order of bytes of the searched values to make it the same as it is stored in the index.

---

it infact wud be as i said. PS below demo...(the table defination for both tables being same and data as well....analyzed on same day and so)

Code:

---

US18>select count(*) from TEMP_REPORTING_PRODUCT_Hier ;

  COUNT(*)
----------
    421047

Elapsed: 00:00:00.50


US18>select count(*) from TEMP1_REPORTING_PRODUCT_Hier ;

  COUNT(*)
----------
    421047

Elapsed: 00:00:00.34


US18>select index_type from dba_indexes where index_name='PK_TEMP_REPORTING_PRODUCT_HIER';

INDEX_TYPE
---------------------------
NORMAL


US18>select index_type from dba_indexes where index_name='PK_TEMP1_REPORTING_PROD_HIER';

INDEX_TYPE
---------------------------
NORMAL/REV



US18>select * from TEMP_REPORTING_PRODUCT_Hier where pin=512320;

      PIN PARENT_PIN        FORDATE  PH_ITEM_NAME      PH_ITEM_DESC                       
---------- ------------------ --------- ------------------ ------------------------------------
    512320 M5IJJ              28-MAR-01 QT-MU7A9-I9        DEC C V/A Install                   

Elapsed: 00:00:00.63


US18>select * from TEMP1_REPORTING_PRODUCT_Hier where pin=512320;

      PIN PARENT_PIN        FORDATE  PH_ITEM_NAME      PH_ITEM_DESC                       
---------- ------------------ --------- ------------------ ------------------------------------
    512320 M5IJJ              28-MAR-01 QT-MU7A9-I9        DEC C V/A Install                   

Elapsed: 00:00:00.47


US18>select * from TEMP_REPORTING_PRODUCT_Hier where pin=232478;

      PIN PARENT_PIN        FORDATE  PH_ITEM_NAME      PH_ITEM_DESC                       
---------- ------------------ --------- ------------------ -------------------------------
    232478 M3369              28-MAR-01 247318-375        SuperHeroes NT CKit A/P             

Elapsed: 00:00:00.62


US18>select * from TEMP1_REPORTING_PRODUCT_Hier where pin=232478;

      PIN PARENT_PIN        FORDATE  PH_ITEM_NAME      PH_ITEM_DESC                       
---------- ------------------ --------- ------------------ -------------------------------
    232478 M3369              28-MAR-01 247318-375        SuperHeroes NT CKit A/P             

Elapsed: 00:00:00.47

---

Abhay.