Reverse Key indexes
DBAsupport.com Forums - Powered by vBulletin
Page 1 of 2 12 LastLast
Results 1 to 10 of 15

Thread: Reverse Key indexes

  1. #1
    Join Date
    Aug 2002
    Location
    Brighton, England
    Posts
    93

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

  2. #2
    Join Date
    Dec 2002
    Location
    Bangalore ( India )
    Posts
    2,434
    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.
    funky...

    "I Dont Want To Follow A Path, I would Rather Go Where There Is No Path And Leave A Trail."

    "Ego is the worst thing many have, try to overcome it & you will be the best, if not good, person on this earth"

  3. #3
    Join Date
    Aug 2002
    Location
    Brighton, England
    Posts
    93
    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

  4. #4
    Join Date
    Dec 2002
    Location
    Bangalore ( India )
    Posts
    2,434
    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....

    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.
    funky...

    "I Dont Want To Follow A Path, I would Rather Go Where There Is No Path And Leave A Trail."

    "Ego is the worst thing many have, try to overcome it & you will be the best, if not good, person on this earth"

  5. #5
    Join Date
    Aug 2002
    Location
    Colorado Springs
    Posts
    5,253
    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.
    David Aldridge,
    "The Oracle Sponge"

    Senior Manager, Business Intelligence Development
    XM Satellite Radio
    Washington, DC

    Oracle ACE

  6. #6
    Join Date
    Dec 2000
    Location
    Ljubljana, Slovenia
    Posts
    4,439
    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....
    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....
    Jurij Modic
    ASCII a stupid question, get a stupid ANSI
    24 hours in a day .... 24 beer in a case .... coincidence?

  7. #7
    Join Date
    Aug 2002
    Location
    Brighton, England
    Posts
    93
    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

  8. #8
    Join Date
    Jun 2000
    Location
    Madrid, Spain
    Posts
    7,448
    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

  9. #9
    Join Date
    Aug 2002
    Location
    Colorado Springs
    Posts
    5,253
    RK indexes also require the use of the cost-based optimizer -- another reason not to use RBO.
    David Aldridge,
    "The Oracle Sponge"

    Senior Manager, Business Intelligence Development
    XM Satellite Radio
    Washington, DC

    Oracle ACE

  10. #10
    Join Date
    Aug 2002
    Location
    Brighton, England
    Posts
    93
    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.


    Gus

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width