sqlpostgresqllongest-prefix

What is the best way to run a longest matching prefix against a table column?


I need to run a longest matching prefix against a column in a table, not just a single value. For a single value I use something like SELECT value, prefix as lmp FROM aTable WHERE SUBSTRING(value,1, LENGTH(prefix)) = prefix ORDER BY prefix DESC limit 1.

The problem is if it is being done against many records it will entail doing a table scan and getting the values one by one, and will entail a lot of traffic between client and server.

Is there a way to do it in a single query which will involve subqueries but not stored procedures? I am using PostgreSQL 8.4.


Solution

  • You can put the values in a table using a CTE and do:

    with list as (
        select 'abc' as prefix union all
        . . .
    )
    select value, lmp
    from (SELECT value, prefix as lmp,
                 row_number() over (partition by value order by len(prefix) desc) as seqnum
          FROM aTable join
               list l
               on SUBSTRING(value,1, LENGTH(prefix)) = prefix
         ) t
    where seqnum = 1
    

    This will move the looping entirely onto the server, which should be a bit faster.