longest prefix match querries - Mailing list pgsql-performance

From Hripchenko Sergey
Subject longest prefix match querries
Date
Msg-id 848789310.20060707124849@linkey.ru
Whole thread Raw
List pgsql-performance
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



pgsql-performance by date:

Previous
From: Markus Schaber
Date:
Subject: Re: Update INSERT RULE while running for Partitioning
Next
From: "Merlin Moncure"
Date:
Subject: Re: Calling a SP from Curosor loop