From: Hripchenko Sergey <hripchenko@linkey.ru>
To: pgsql-performance@postgresql.org
Subject: longest prefix match querries
Date: Fri, 7 Jul 2006 12:48:49 +0400
Message-ID: <848789310.20060707124849@linkey.ru> (raw)
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: hripchenko@linkey.ru
Subject: Re: longest prefix match querries
In-Reply-To: <848789310.20060707124849@linkey.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox