The fastest way to find the longest prefix in ORACLE

Question

I have a list of phone number prefixes defined for a large number of zones (the request defines gvcode and CGI). I need to effectively find the longest prefix matching the given number PHONE_NR.

I use an inverted LIKE clause on the digits box (which contains prefixes in the form + 48%, + 49%, + 1%, + 1232% and so on).

Therefore, I cannot use the normal index in this field.

I was able to significantly improve using IOT on gvcode and the CGI field (which are part (the first two passes) of the primary key). I also looked at some oracle text indexes, but cannot find one that matches a longer input with a shorter prefix in the table.

Is there any other way to perform such a search faster than this approach.

Here is a query that contains a list of all the relevant prefixes (sort it subsequently by length digits).

select t.gvcode, t.digits from NUMBERS t where t.gvcode=ZONE_SET_CODE and t.cgi=cgi_f and ( PHONE_NR like t.digits) order by length(digits) desc 

Answer 1

In addition to the index on “digits”, you can create an index on rpad(substr(digits,1,length(digits)-1), 10, '9') . "10" is the maximum length you want to support. You add an additional condition to the where clause: rpad(substr(digits,1,length(digits)-1), 10, '9') >= PHONE_NR

Your SQL will be:

 select t.gvcode, t.digits from NUMBERS t where t.gvcode=ZONE_SET_CODE and t.cgi=cgi_f and PHONE_NR like t.digits and substr(digits, 1, length(digits)-1) <= PHONE_NR and rpad(substr(digits,1,length(digits)-1), 10, '9') >= PHONE_NR order by length(digits) desc 

Here is an example in sqlfiddle

Answer 2

I might seem stupid, but when I came across such a problem, I took up most of the unsafe brute force methods:

Let's say:

 L=length of longest prefix to match (without obvious +, of course) 

Add L additional fields, naming them, for example, P1, P2,...,PL

Update these fields with

 UPDATE NUMBERS set P1=SUBSTR(PHONE_NR,1,1), P2=SUBSTR(PHONE_NR,1,2), ..., PL=SUBSTR(PHONE_NR,1,L) 

(you can do this later in the INSERT OR UPDATE trigger)

You now have L-fields for creating an index and comparing with whatever you like.

Answer 3

I'm not sure if this will really help, but I think it's worth a try.

Create function index on substr(digits, 1, length(digits)-1) (this is just to index digits without "%")

Then in your query you can add one more condition:

 AND substr(digits, 1, length(digits)-1) <= PHONE_NR 

Here is the sqlfiddle daemon

The idea is that with lexical comparison you can “cut out” all the numbers that are after PHONE_NR

Answer 4

Ok, just write because I had the same problem. If you know the range of prefix lengths that you have, you can do something similar to the following. The following example assumes a prefix length of 2-6

 select t.num, coalesce(p6.PREFIX, p5.PREFIX, p4.PREFIX, p3.PREFIX, p2.PREFIX) PREFIX from NUMBERS t LEFT OUTER JOIN PREFIXES p2 ON substr(t.num,1,2)=p2.PREFIX LEFT OUTER JOIN PREFIXES p3 ON substr(t.num,1,3)=p3.PREFIX LEFT OUTER JOIN PREFIXES p4 ON substr(t.num,1,4)=p4.PREFIX LEFT OUTER JOIN PREFIXES p5 ON substr(t.num,1,5)=p5.PREFIX LEFT OUTER JOIN PREFIXES p6 ON substr(t.num,1,6)=p6.PREFIX 

Equal joins are as good as you can get.

I believe it works much better than any other possible solution here, hope this helps anyone who stumbles on the same problem

Sqlfiddle link modified from sailaway answer, whose script still gives all matches, not just the longest

Answer 5

I ran into the same problem and found this solution useful (thanks to L. Schneider at https://community.oracle.com/thread/351988 ):

 create table a (a varchar2(100)); create index a_1 on a(a); begin delete a; insert into a values ('00431'); insert into a values ('004312'); insert into a values ('0043123'); insert into a values ('00431234'); insert into a values ('004312345'); end; / select max(a) from a where '004311' like a||'%' ; 

http://sqlfiddle.com/#!4/abc975/1