jump to navigation

Introduction To Reverse Key Indexes: Part II (Another Myth Bites The Dust) January 16, 2008

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

In Part I, we saw how with Reverse Key Indexes, Oracle will basically take the indexed value, reverse it and then index the reversed value. As a result, data that would ordinarily be logically sorted within an index structure will now be randomly distributed. This therefore negates the use of Reverse Key Indexes with range predicates, with the CBO not even considering them in its costings.

This is all the information we need to dispel a rather bizarre suggestion that has been doing the rounds regarding using Reverse Key Indexes to deal with LIKE predicates that have a leading wildcard. For example, such a suggestion can be found here and within an OTN discussion here.

Basically the suggestion is to:

1) Create a Reverse Key Index on the column to be searched with a LIKE predicate having a leading wildcard (such %, _).

2) Instead of writing the query as usual, e.g.

SELECT * FROM bowie_table WHERE name LIKE ‘%BOWIE’

rewrite the query programmatically such as:

SELECT * FROM bowie_table WHERE name LIKE ‘EIWOB%';

by reversing the required text and now having the wildcard at the end.

The Reverse Key Index stores the data in a reversed format identical to say ‘EIWOB’, so Oracle should be able to use the Reverse Key Index to efficiently find all rows that start with ‘EIWOB’ as they’re all grouped together within the index structure, right ?

Ummm, wrong.

Ignoring the fact the example in the above link is somewhat meaningless as it uses a leading and a trailing wildcard in both queries and so assuming the first query only has a leading wildcard and the second query only has a trailing wildcard, this suggested use of a Reverse Key Index can not possibly work on any current version of Oracle.

There are a few fundamental problems with this suggestion but in summary not only will it not work but worse, it will actually return the wrong results.

The suggestion is correct as far as indeed, using a normal index to return data with a LIKE statement containing a leading wildcard will negate the use of an index range scan, the CBO doesn’t even consider it. An index hint may push Oracle to use a Full Index Scan, but not an Index Range Scan.

However using a Reverse Index Key to solve this is unfortunately doomed to failure for two very simple reasons.

One, as we have already seen, Oracle also ignores Index Range Scans for Reverse Key Indexes with range predicates and unfortunately, a query such as WHERE name LIKE ‘EIWOB%’ is a range scan. The CBO simply doesn’t consider the Reverse Key Index in it’s deliberations.

Two, is of course that Oracle has no possible way of knowing that when you say LIKE ‘EIWOB%’, what you really mean is search for all records ending with BOWIE, LIKE ‘%BOWIE’. How can Oracle possibly know this ? If it could use the index (which it can’t) Oracle would only reverse the search string around anyways and use the index to look for indexed entries beginning with ‘BOWIE’ within the index structure, remembering everything is of course stored in reverse within the index.

So Oracle is actually searching for all records starting with ‘EIWOB’, not ending with ‘BOWIE’ which are two entirely different things.

The net result of using this suggested strategy is not good.

1) Oracle ignores the Reverse Key Index anyways as a LIKE ‘EIWOB%’ is a range predicate
2) Oracle therefore performs a Full Table Scan anyways
3) As the query is effectively searching for all records that start with ‘EIWOB’, not as expected all records that end with ‘BOWIE’, the two queries in the example will actually return completely different results

The Reverse Key Indexes Part II Demo shows how this suggested use of a Reverse Key Index is a very very bad idea …

However, if you want to solve the issue of efficiently finding the results of a LIKE ‘%BOWIE’, there are some possible approaches one could take that will use an index and return correct results.

One possible solution (as mentioned in the OTN link listed at the beginning) is to create a Function-Based Index using the REVERSE Function, (Warning: this function is undocumented and unsupported):

CREATE INDEX bowie_reverse_func_i ON bowie(REVERSE(name));

A query such as WHERE REVERSE(name) LIKE ‘EIWOB%’ or better still WHERE REVERSE(name) LIKE REVERSE(‘%BOWIE’) can now both potentially use the index.

The reverse function will reverse the name column (from say ‘DAVID BOWIE’ to ‘EIWOB DIVAD’) and the LIKE range predicate can work with the index as it’s a Function-Based index rather than a Reverse Key Index and it’s not using a LIKE with a leading wildcard. A column containing ‘DAVID BOWIE’, but stored as ‘EIWOB DIVAD’ within the index, can be found efficiently via an index range scan using this Function-Based Index.

I’ve included an example on effectively using a Function-Based Index with the Reverse Function at the end of the above demo. There’s also a discussion and other alternatives at Gints Plivna’s Blog.

Another alternative is to use an Oracle Text Index, which also has the capability of dealing logically with queries such as %BOWIE% but as they say, that’s a topic for another day.

More on Reverse Key Indexes to come as well.

About these ads

Comments»

1. Nigel Thomas - January 16, 2008

Warning: this function is not undocumented and unsupported…

Did you mean, it IS undocumented?

2. Richard Foote - January 16, 2008

Hi Nigel,

Oooops, yes I did. Fixed !!

Thanks :)

3. Robert - January 16, 2008

Richard,

so now you’re also sneaking in references to Queen. :-) All artists from the UK – coincidence?

I believe there is a touch too much “not” in “Warning: this function is not undocumented and unsupported” otherwise I don’t understand the point of the warning.

I am also missing the case where you reverse the index but use the original query

SELECT * FROM reverse_stuff WHERE object_name LIKE ‘%BOWIE';

Theoretically, since the column is reversed in the index, Oracle could do a range scan with this because it can use the leading portion of the reversed column much the same as with LIKE ‘DAVID%’ when there is a non reversed index.

Maybe I’ll try that later if I find the time.

Cheers

4. Richard Foote - January 16, 2008

Hi Robert

I see I’m going to have to sneak in the odd Lou Reed or Midnight Oil reference to keep you on your toes ;)

Warning has been fixed, thanks.

Sounds like it should work doesn’t it (no pun intended of course) ?

However, the CBO looks at the LIKE and goes, “forget it” and ignores the Reverse Key index. Precious little that can be done about it.

Perhaps a 12g new feature ;)

5. Robert - January 16, 2008

The CBO is *so* stupid. Ts ts ts… ;-)

PS: I sneaked a music reference in as well.

6. Richard Foote - January 16, 2008

You didn’t sneak one in, you used a sledgehammer ;)

7. cristiancudizio - January 16, 2008

Wow! compliments Richard. I found your blog very interesting.

8. Don Seiler - January 16, 2008

Great series Richard, thanks.

As long as you’re taking requests for 70s musical artists, I’ll throw out CSN&Y.

Have you heard the Seu Jorge cover of Bowie songs as used in “The Life Aquatic”? It’s brilliant. Album is called “The Life Aquatic Studio Sessions”, up on amazon and itunes I think.

9. Richard Foote - January 17, 2008

Glad you guys find some things interesting.

Don, check out the new David Gilmour Live At The Royal Abert Hall DVD. Very very good, featuring a great version of Echoes and guest appearances by Crosby, Nash and one David Bowie.

I’ve heard of the Seu Jorge covers but haven’t actually got to hear them yet, will check it out.

10. Robert - January 17, 2008

Richard, you did it again – with a UK artist. :-)

But right you are. I still have to work on my subtlety…

*chuckle*

11. Jeffrey Kemp - January 17, 2008

Thanks Richard, you stole my thunder. Just this morning I was considering the plight of a customer whose ‘%MITH’ queries weren’t running fast enough for them. A quick search on google didn’t come up with anything useful, unfortunately. I hadn’t caught up on my blog reading either.

My first thought was that maybe, just maybe, the new REVERSE indexes might help, thinking that the optimiser might be smart enough to convert WHERE name LIKE ‘%MITH’ into something like WHERE internal_reverse_function(name) LIKE ‘HTIM%’ (assuming that name only contains single-byte strings, and internal_reverse_function returns the input byte-reversed exactly like the reverse index stores it, and the function is specially recognised by the optimiser).

So of course a reasonable answer is as you say, to create a function-based index on the reverse function; but unfortunately to use it I have to modify the application code, which in some cases is not a cost effective option.

Oracle’s new reverse indexes were never intended for this purpose anyway, I’ve always heard them explained in terms of reducing insert contention for monotonically increasing values like meaningless IDs.

Thanks anyway!

12. Richard Foote - January 17, 2008

Hi Jeff

What can I say, great minds think alike ;)

My big concern with the reverse function is that it’s not supported, probably because of the issues due to multi-byte characters. But yes, it also requires the application to be written to reference the function.

We successfully use Oracle Text indexes to perform complex text searches.

Agreed, reverse key indexes are intended to reduce contention and any suggested clever tricks with them need to be carefully tested.

13. Martin W - January 17, 2008

Wonder if Jeffrey could use a regexp function based index – regexp is supported.

14. Richard Foote - January 18, 2008

Hi Martin

The problem with implementing any possible function-based index solution is that Jeffrey would be required to change the application code.

I must admit that regular expressions is something I keep meaning to learn more about as they can potentially be really useful in so many ways.

15. Martin W - January 18, 2008

I found out why reverse is not supported:-
1* select reverse (123456) from dual
p01cfd> /
Segmentation fault (core dumped)
-bash-3.00$
If anyone asks, I was not logged into a production system when I did this.
I feel so Low.

16. Martin W - January 18, 2008

Segmentation fault occurs on 9.2.0.7 and 10.2.0.3 on AIX, but 11.1 on windows XP is fine, it just says expects char not numeric

17. Jeffrey Kemp - January 18, 2008

on Linux…
Oracle Database 10g Express Edition Release 10.2.0.1.0

REVERSE(1234567)
———————-
-0.0000000000557799

Looks like REVERSE might be returning the byte-reversed internal representation of the number.

18. Richard Foote - January 19, 2008

Hi Martin

Indeed, there a various problems with the reverse function. Things are much worse with multi-byte character sets as discussed in the link I referred to in the blog entry.

I’m beginning to wish I never mentioned it ;)

Life’s a funny thing, you can be low one day and one of the Heroes the next …

19. Richard Foote - January 19, 2008

Hi Jeffery

Indeed. It’s also why you run into issues multi-byte character sets. The reverse function is used by Oracle internally for specific operations and is not meant to be used by those with too imagination and time on their hands ;)

20. Nick - July 2, 2008

Martin,

You just need to put ” around the string passed into the function.

I tried

select reverse(‘1234567′) from dual;

and got back 7654321

21. Richard Foote - April 14, 2009

Oh dear, this crazy, dangerous and outright wrong suggestion gets a mention yet again:

LIKE and REVERSE index Burleson tip is not working

Hopefully, one day, it will finally disappear completely …

22. LIKE with wildcard (%) at start CAN use an index « Jeff Kemp on Oracle - April 5, 2010

[...] looks like Richard Foote beat me to it, in a discussion of reverse indexes (which unfortunately don’t contribute [...]

23. Santosh - December 23, 2012

Hi,
Someone recently asked if there is any index (other than reverse key) we can build on sequence filed in a table. Is reveres key index only an advisable option on a sequence filed?

Thanks and regards

Santosh.

24. Richard Foote - February 7, 2013

Hi Santosh

If insert performance is not problematic, then a good old non-reverse index will of course be fine as well.

Other options could be to use a hash cluster for the table (and so potentially avoid a problematic index), use hash partitioning on the table and/or index to spread inserts across different partitions.

25. Santosh - June 8, 2013

Thanks.

Will IOT be a good candidate?

Thansk and regards

Santosh

Richard Foote - June 8, 2013

Hi Santosh

Would an IOT be a good candidate to avoid index contention ?

Probably not.

However, this is a fantastic “Candidate”:

santosh Upadhyay - August 18, 2013

Hi, Thanks for the reply. It is fantastic :-) As you suggested in your earliar reply, you said: Other options could be to use a hash cluster for the table (and so potentially avoid a problematic index), use hash partitioning on the table and/or index to spread inserts across different partitions. If the table exists already, do I need to recreate it into a cluster table? Can a cluster index be created only a clustred table, or it can be created on a non-clustered table as well? I sort of know the answer but not sure. Thanks and reagdrs

Santosh Date: Sat, 8 Jun 2013 09:20:45 +0000 To: santosh_kr@hotmail.co.uk


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

%d bloggers like this: