Thread: Longest prefix matching CTE

Have an Oracle "connect by" SQL that looks something like :

select phone, pfx, len, (select info from codes where
pfx = x.pfx) infot
 from (
 select :x phone, to_number(substr( :x, 1, length(:x)-level+1 )) pfx,
length(:x)-level+1 len
   from dual
connect by level <= length(:x)
 order by level
    ) x
   where rownum = 1
   and (select info from codes where pfx = x.pfx) is not null
/



Where codes is essentially a two column table :

create table codes(pfx bigint,info text);

And its contents look like :

61882    Australia - Sydney
61883    Australia - Sydney
61884    Australia - Sydney
61892    Australia - Sydney
61893    Australia - Sydney
61894    Australia - Sydney
6113    Australia - Premium
6118    Australia - Premium
61    Australia - Proper



The goal being to match the longest prefix given a full phone number, e.g.


61234567890  would match "australia proper 61"
whilst
61134567890 would match "Australia premium 6113"
and
61894321010 would match "Australia - Sydney 61893"

I know the answer involves Postgres CTE, but I haven't used CTEs much
yet... let alone in complex queries such as this.

Thanking you all in advance for your kind help.

T

On Feb 24, 2015, at 3:50 PM, Tim Smith <randomdev4+postgres@gmail.com> wrote:

>
>
> The goal being to match the longest prefix given a full phone number, e.g.
>
>
> 61234567890  would match "australia proper 61"
> whilst
> 61134567890 would match "Australia premium 6113"
> and
> 61894321010 would match "Australia - Sydney 61893"
>
> I know the answer involves Postgres CTE, but I haven't used CTEs much
> yet... let alone in complex queries such as this.
>
> Thanking you all in advance for your kind help.

There's probably a CTE approach for it, but you might want to look
at https://github.com/dimitri/prefix too - it's an extension that's designed
specifically for longest prefix matching, and that uses gist indexes to
do it efficiently.

Cheers,
  Steve

Will take a look.  Thanks steve.

On 24 February 2015 at 23:57, Steve Atkins <steve@blighty.com> wrote:
>
> On Feb 24, 2015, at 3:50 PM, Tim Smith <randomdev4+postgres@gmail.com> wrote:
>
>>
>>
>> The goal being to match the longest prefix given a full phone number, e.g.
>>
>>
>> 61234567890  would match "australia proper 61"
>> whilst
>> 61134567890 would match "Australia premium 6113"
>> and
>> 61894321010 would match "Australia - Sydney 61893"
>>
>> I know the answer involves Postgres CTE, but I haven't used CTEs much
>> yet... let alone in complex queries such as this.
>>
>> Thanking you all in advance for your kind help.
>
> There's probably a CTE approach for it, but you might want to look
> at https://github.com/dimitri/prefix too - it's an extension that's designed
> specifically for longest prefix matching, and that uses gist indexes to
> do it efficiently.
>
> Cheers,
>   Steve
>
>
>
> --
> Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-general

> On 25 Feb 2015, at 24:50, Tim Smith <randomdev4+postgres@gmail.com> wrote:
>
> Have an Oracle "connect by" SQL that looks something like :
>
> select phone, pfx, len, (select info from codes where
> pfx = x.pfx) infot
> from (
> select :x phone, to_number(substr( :x, 1, length(:x)-level+1 )) pfx,
> length(:x)-level+1 len
>   from dual
> connect by level <= length(:x)
> order by level
>    ) x
>   where rownum = 1
>   and (select info from codes where pfx = x.pfx) is not null
> /

> The goal being to match the longest prefix given a full phone number, e.g.

> I know the answer involves Postgres CTE, but I haven't used CTEs much
> yet... let alone in complex queries such as this.

The CTE would look something like this, assuming that :x is some parameter from outside the query ($1 here):

with recursive x(level) as (
    select $1 as phone, to_number(substr($1, 1, length($1))) as pfx, length($1 ) as len, 1 as level
    union all
    select $1 as phone, to_number(substr($1, 1, length($1)-level+1 )) as pfx, length($1 ) -level+1 as len, level +1 as
level
    from x
    where level <= x.len
)
select * from x;

Or:
select $1 as phone, to_number(substr($1, 1, length($1) - pos as pfx, length($1) as len
from generate_series(0, length($1)-1)(x);

BTW, I didn't test any of these (I'm late already!).

Alban Hertroys
--
If you can't see the forest for the trees,
cut the trees and you'll find there is no forest.