Best implementation of PATRICIA
Hello!
I'm working on a project requiring fast query like 'does ADDRESS belongs
to SET OF NETWORKS?'. Naturally, such a query is better implemented
using PATRICIA, but building PATRICIA tree is a relatively long task and
is better to be done once, for instance, at server startup.
I'm thinking of implementing such a tree using stored procedures, and
looking for advise from postgresql-hackers: how can I hook startup of
server?
Idea of having something like a blob to store and restore PATRICIA tree
may be better suited to standard SQL, but I'm looking for more elegant
solution. Or am I totally wrong?
Alex.
On Aug 25, 2007, at 11:37 AM, Alex Povolotsky wrote:
Hello!
I'm working on a project requiring fast query like 'does ADDRESS
belongs to SET OF NETWORKS?'. Naturally, such a query is better
implemented using PATRICIA, but building PATRICIA tree is a
relatively long task and is better to be done once, for instance,
at server startup.I'm thinking of implementing such a tree using stored procedures,
and looking for advise from postgresql-hackers: how can I hook
startup of server?Idea of having something like a blob to store and restore PATRICIA
tree may be better suited to standard SQL, but I'm looking for more
elegant solution. Or am I totally wrong?
Patricia is a nice algorithm, but I suspect you'd be much happier with
GIST and http://pgfoundry.org/projects/ip4r/
Cheers,
Steve
Patricia as well as other digital trees could be realized using GiST
once we'll have time and support to extend current GiST interface.
For the moment you can use SP-GiST which should have patricia implementation.
http://www.cs.purdue.edu/spgist/.
Oleg
On Sat, 25 Aug 2007, Alex Povolotsky wrote:
Hello!
I'm working on a project requiring fast query like 'does ADDRESS belongs to
SET OF NETWORKS?'. Naturally, such a query is better implemented using
PATRICIA, but building PATRICIA tree is a relatively long task and is better
to be done once, for instance, at server startup.I'm thinking of implementing such a tree using stored procedures, and looking
for advise from postgresql-hackers: how can I hook startup of server?Idea of having something like a blob to store and restore PATRICIA tree may
be better suited to standard SQL, but I'm looking for more elegant solution.
Or am I totally wrong?Alex.
---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster
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
Alex Povolotsky <tarkhil@over.ru> writes:
I'm working on a project requiring fast query like 'does ADDRESS belongs
to SET OF NETWORKS?'. Naturally, such a query is better implemented
using PATRICIA, but building PATRICIA tree is a relatively long task and
is better to be done once, for instance, at server startup.
I'm thinking of implementing such a tree using stored procedures, and
looking for advise from postgresql-hackers: how can I hook startup of
server?
Idea of having something like a blob to store and restore PATRICIA tree
may be better suited to standard SQL, but I'm looking for more elegant
solution. Or am I totally wrong?
If it's as expensive as all that, why would you want to redo it even at
server start? Maybe a new index type would be appropriate.
regards, tom lane