Progressive search for longest prefix

Question

I have a table with phone number prefix columns like:

prefix
------
9379
355422
35566
...

Given a phone number I want to drop its digits starting from the right until It finds the first match on the prefix column. ie:

937973418459
93797341845
9379734184
937973418
93797341
9379734
937973
93797
9379   <-- match found

Note that I need to do this for a list of phone numbers so bulk operation is important as opposed to individual query which is slow. I tried using postgres' full-text search using:

tsquery('937973418459|93797341845|9379734184|937973418|93797341|9379734|937973|93797|9379')

and it works but its slow when running against say 10k phone numbers. It there a more efficient way to solve this?

Answer 1

To find the longest prefix:

For a single given number:

SELECT *
FROM   prefix_tbl
WHERE  937973418459 LIKE prefix || '%'
ORDER  BY prefix DESC
LIMIT  1

For a whole table of given numbers:

SELECT DISTINCT ON (t.nr )
       p.*
FROM   prefix_tbl p
JOIN   tel_nr t ON t.nr LIKE p.prefix || '%'
ORDER  BY t.nr, prefix DESC;

Related:

• ? LIKE (column || '%')

For performance optimization consider this closely related, extensive answer on dba.SE:

• Algorithm for finding the longest prefix

And this:

• Optimize GROUP BY query to retrieve latest row per user