Date: Fri, 7 Jul 2006 12:48:49 +0400
From: Hripchenko Sergey <hripchenko@linkey.ru>
Reply-To: Hripchenko Sergey <hripchenko@linkey.ru>
Organization: ITSP "Linkey"
Message-ID: <848789310.20060707124849@linkey.ru>
To: pgsql-performance@postgresql.org
Subject: longest prefix match querries
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Hi, all.

i'm trying to tune application which makes alots of queries
with semantics(find LONGEST PREFIX MATCH in a string) like:

SELECT cost
FROM tarif
WHERE $1 LIKE prefix
ORDER BY length(prefix) DESC
LIMIT 1

from table like:

CREATE TABLE tarif (
    id bigint NOT NULL,
    prefix varchar(55) NOT NULL,
    cost numeric(x, x) not null
) WITHOUT OIDS;

where $1 is the phone numbers.. for example.
it's common task for voice billing applications.


so, generally i can do it that ways:

WHERE $1 LIKE prefix
WHERE $1 SIMILAR TO prefix
WHERE $1 ~ prefix
WHERE position(prefix in $1) = 0

(
surely i must adopt prefix for matching rules,
e.g. LIKE prefix || '%'
and the best is to create trigger which modifies prefix on
insert/update time
)

BUT! this methods doesn't use indexes!!
this is the main disadvantage.

voip3a=# EXPLAIN ANALYZE SELECT cost FROM tarif WHERE '78123319060' like prefix ORDER BY length(prefix) LIMIT 1;
                                                            QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=3028.90..3028.90 rows=1 width=22) (actual time=162.189..162.192 rows=1 loops=1)
   ->  Sort  (cost=3028.90..3030.43 rows=612 width=22) (actual time=162.181..162.181 rows=1 loops=1)
         Sort Key: length((prefix)::text)
         ->  Seq Scan on tarif  (cost=0.00..3000.57 rows=612 width=22) (actual time=4.132..161.715 rows=39 loops=1)
               Filter: ('78123319060'::text ~~ (prefix)::text)
 Total runtime: 162.340 ms
(6 rows)

voip3a=# SELECT count(*) from tarif;
 count
--------
 122323
(1 row)


AND there are many more effective algorithms for searching LONGEST PREFIX
MATCH in a string.. like
http://search.cpan.org/~avif/Tree-Trie-1.1/Trie.pm
for example


Is there any ways to improve perfomance?
May be implement indexes using Tire algoritm ?
(if so can you please show me some url's to start...)


Thanks, Sergey