Обсуждение: 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