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
