Thread: 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