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

Em Wednesday 20 February 2008 05:55:07 Dragan Zubac escreveu:

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 ?

Prefix or suffix?

For prefix you can use "SELECT number FROM table WHERE number LIKE '123%'".

For suffix you change the "%" to the beginning of the string, but then loose
the ability to use indices. (Unfortunately, using suffixes is really
interesting for caller IDs since you don't always receive area code, country
code, etc.)

--
Jorge Godoy <jgodoy@gmail.com>

On Wed, 20 Feb 2008, Jorge Godoy wrote:

Em Wednesday 20 February 2008 05:55:07 Dragan Zubac escreveu:

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 ?

Prefix or suffix?

For prefix you can use "SELECT number FROM table WHERE number LIKE '123%'".

For suffix you change the "%" to the beginning of the string, but then loose
the ability to use indices. (Unfortunately, using suffixes is really
interesting for caller IDs since you don't always receive area code, country
code, etc.)

you can maintain an additional index for terms backwards.

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83