Re: INDEX possible for reverse wildcards?

From: <ctcgag_at_hotmail.com>
Date: 05 Jun 2004 17:24:37 GMT
Message-ID: <20040605132437.065$ZO@newsreader.com>

Christopher Browne <cbbrowne_at_acm.org> wrote:
> After takin a swig o' Arrakan spice grog, ctcgag_at_hotmail.com belched out:
> > "Mikito Harakiri" <mikharakiri_at_iahu.com> wrote:
> >> <ctcgag_at_hotmail.com> wrote in message
> >> news:20040604183510.277$gk_at_newsreader.com...
> >> > Well, you would only need to look at index entries that start with
> >> > 'w', '%', or '_'. And if the first character is a 'w' or a '_', you
> >> > only need to look at ones where the second is 'w', '%', or '_'.
> >>
> >> And if the first character happens to be '%', then?
> >
> > Then you check the rest of it to see if it matches. (What did you
> > expect?)

>

> I think you're missing the point of the question.

>

> The question is whether or not one can construct an index that makes
> it useful to search parts of the interior of a string.

Actually, the original question was rather Oracle *does* do it, not whether it could do it. When someone suggested that Oracle could not do it with their current index structure, I suggested they could at least get *some* benefit from it without changing the physical index structure, only changing some of the code that accesses it.

>

> Supposing we have the search criteria:
>
> select * from some_table where name like 'Bro%'; -- 1.

But that is what the original poster specifically excluded. He wanted it the other way around:

select * from some_table where 'Brown' like name;

Where the wildcards reside in the column, not in the bind value.

>

> That could be (character set dependent) transformed into the query:

>

> select * from some_table where name >= 'Bro' and name <= 'Brp'; -- 2.

>

> which wouldmake good use of a btree index on NAME to cut down the
> number of entries searched to a dull roar.

Yes, and in the case under discussion, my example could be transformed to something like:

select * from some_table where 'Brown' like name and substr(name,1,1) in ('B','_','%').

Where the "substr... in ..." part could (at least theoretically) be supported by the index. Of course for maximum benefit you would have to have to code the access method itself, not just some query re-write, because you could apply it recursively to each successive letter, up until a % is found, at which point you would have to return to the brute force method (or some even more clever method)

>

> In contrast that sort of transformation cannot be done with

>

> select * from some_table where name like '%owne'; -- 3.

>

> Unless there's some Rather Clever sort of index involved, the best you
> can usually do with that is to do a sequential scan across the table,
> looking for matches.

Meanwhile, in the situation we were actually talking about, with the pattern in the column, not in the bind variable---Sure, you still have to scan the patterns that do start with %, but there may be an aweful lot of patterns that don't start with % (or with _, or with the first letter of the query), and hence can be ruled out using the index, without ever scanning them.

Xho

-- 
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service                        $9.95/Month 30GB

Received on Sat Jun 05 2004 - 12:24:37 CDT