Re: longest prefix match

Hi,

Le mercredi 20 février 2008, Dragan Zubac a écrit :
> Anybody got any ideas/experiences/links for 'longest prefix match'
> solution in PostgreSQL ?
> Basically,put some telephone prefices in some kind of trie,and be able
> to perform fast lookups ?

Glad you ask!

I've been taught there are several ways to have a fast longest prefix match
queries working, the best of the possible solutions being to write a
dedicated GiST index support. This is what I've begun doing here:
http://pgsql.tapoueh.org/site/html/prefix/index.html
http://pgfoundry.org/projects/prefix
http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/prefix/prefix/

This should work ok with 8.2 or 8.3 (I don't intend to support older releases
atm). The current code will allow you to create an index and use it in your
queries, as stated on the README.txt:
CREATE INDEX idx_prefix ON prefixes USING GIST(prefix gist_prefix_ops);
SELECT * FROM prefixes WHERE prefix @> '0218751234';

But it seems (from some comments I've got on IRC) that current implementation
performances are much less than one would expect from indexing support, so
we're about to implement some prefix-range datatype in order to come up with
a better picksplit(). I hope to have some time again to share on this project
pretty soon.

Regards,
--
dim