Thread: Recursive Queries
Hm, having skimmed through the Evgen Potemkin's recursive queries patch I find it quite different from what I was expecting. My own thinking was headed off in a different direction. Basically the existing patch reimplements a new kind of join which implements a kind of nested loop join (with newer versions adding a kind of hash join) which feeds a new kind of tuplestore called a tupleconn. I was thinking to have a new node above a standard join. The new node would repeatedly feed back down to the join the results of the previous iteration and reexecute the join to get the next generation. I think my approach is more in line with the DB2/ANSI "WITH" style query which is expected to do a breadth-first search. The Oracle CONNECT BY syntax is expected to do a depth first search. I have two major issues with the repeated-join model though. a) Ideally we would want to switch between nested loop, merge join, and hash join depending on the size of the previous generation. That means the join node wouldn't be the same type of join for all the iterations. This is important since in most applications you're traversing either up or down a tree and are likely starting with very few nodes but often ending up with very broad levels with many nodes. No single type of join will be appropriate for the whole plan execution. b) I do want to be able to support depth-first searching too. I'm not sure how to reconcile that with the repeated-join conceptual model. We could always resort the entire result set after generating it but that seems like an unsatisfactory solution. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com
Ühel kenal päeval, N, 2007-01-25 kell 11:08, kirjutas Gregory Stark: > Hm, having skimmed through the Evgen Potemkin's recursive queries patch I find > it quite different from what I was expecting. My own thinking was headed off > in a different direction. > > Basically the existing patch reimplements a new kind of join which implements > a kind of nested loop join (with newer versions adding a kind of hash join) > which feeds a new kind of tuplestore called a tupleconn. > > I was thinking to have a new node above a standard join. The new node would > repeatedly feed back down to the join the results of the previous iteration > and reexecute the join to get the next generation. > > I think my approach is more in line with the DB2/ANSI "WITH" style query which > is expected to do a breadth-first search. IIRC the ISO/ANSI spec has a special clause for specifying both BREADTH FIRST and DEPTH FIRST searches > The Oracle CONNECT BY syntax is expected to do a depth first search. > > I have two major issues with the repeated-join model though. > > a) Ideally we would want to switch between nested loop, merge join, and hash > join depending on the size of the previous generation. That means the join > node wouldn't be the same type of join for all the iterations. This is > important since in most applications you're traversing either up or down a > tree and are likely starting with very few nodes but often ending up with very > broad levels with many nodes. No single type of join will be appropriate for > the whole plan execution. Then it's probably better to optimize for "very broad levels with many nodes" case, as bad plan fro few joins will probably affect you less in case of only a small number of nodes. > b) I do want to be able to support depth-first searching too. I'm not sure how > to reconcile that with the repeated-join conceptual model. We could always > resort the entire result set after generating it but that seems like an > unsatisfactory solution. I guess there may be difference in breadth-first and depth-first actual data, if you use some recursion control clauses or include level variables. -- ---------------- Hannu Krosing Database Architect Skype Technologies OÜ Akadeemia tee 21 F, Tallinn, 12618, Estonia Skype me: callto:hkrosing Get Skype for free: http://www.skype.com
On Thu, Jan 25, 2007 at 11:08:14AM +0000, Gregory Stark wrote: > b) I do want to be able to support depth-first searching too. I'm not sure how > to reconcile that with the repeated-join conceptual model. We could always > resort the entire result set after generating it but that seems like an > unsatisfactory solution. If you have a tuplestore storing the intermediate tuples for looping, then surely the only difference between depth and breadth searching is that for the former new tuples goes to the front of the tuplestore, and the latter to the end. Have a nice day, -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > From each according to his ability. To each according to his ability to litigate.
"Martijn van Oosterhout" <kleptog@svana.org> writes: > On Thu, Jan 25, 2007 at 11:08:14AM +0000, Gregory Stark wrote: >> b) I do want to be able to support depth-first searching too. I'm not sure how >> to reconcile that with the repeated-join conceptual model. We could always >> resort the entire result set after generating it but that seems like an >> unsatisfactory solution. > > If you have a tuplestore storing the intermediate tuples for looping, > then surely the only difference between depth and breadth searching is > that for the former new tuples goes to the front of the tuplestore, and > the latter to the end. That's basically how the existing patch approached the problem. It invents a new type of join and a new type of tuplestore that behaves this way. This has the advantage of working the way Oracle users expect and being relatively simple conceptually. It has the disadvantage of locking us into what's basically a nested loop join and not reusing existing join code so it's quite a large patch. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com
Gregory Stark wrote:
> "Martijn van Oosterhout" <kleptog@svana.org> writes:
>
>> On Thu, Jan 25, 2007 at 11:08:14AM +0000, Gregory Stark wrote:
>>> b) I do want to be able to support depth-first searching too. I'm not sure how
>>> to reconcile that with the repeated-join conceptual model. We could always
>>> resort the entire result set after generating it but that seems like an
>>> unsatisfactory solution.
>> If you have a tuplestore storing the intermediate tuples for looping,
>> then surely the only difference between depth and breadth searching is
>> that for the former new tuples goes to the front of the tuplestore, and
>> the latter to the end.
>
> That's basically how the existing patch approached the problem. It invents a
> new type of join and a new type of tuplestore that behaves this way. This has
> the advantage of working the way Oracle users expect and being relatively
> simple conceptually. It has the disadvantage of locking us into what's
> basically a nested loop join and not reusing existing join code so it's quite
> a large patch.
I believe our Syntax should be whatever the standard dictates,
regardless of Oracle.
Joshua D. Drake
--
=== The PostgreSQL Company: Command Prompt, Inc. ===
Sales/Support: +1.503.667.4564 || 24x7/Emergency: +1.800.492.2240
Providing the most comprehensive PostgreSQL solutions since 1997 http://www.commandprompt.com/
Donate to the PostgreSQL Project: http://www.postgresql.org/about/donate
PostgreSQL Replication: http://www.commandprompt.com/products/
"Joshua D. Drake" <jd@commandprompt.com> writes: > > That's basically how the existing patch approached the problem. It invents a > > new type of join and a new type of tuplestore that behaves this way. This has > > the advantage of working the way Oracle users expect and being relatively > > simple conceptually. It has the disadvantage of locking us into what's > > basically a nested loop join and not reusing existing join code so it's quite > > a large patch. > > I believe our Syntax should be whatever the standard dictates, > regardless of Oracle. Well the issue here isn't one of syntax. The syntax is really an orthogonal issue. The basic question is whether to treat this as a new type of plan node with its behaviour hard coded or whether to try to reuse existing join types executing them recursively on their output. I can see advantages either way. As far as the syntax goes, now that I've actually read up on both, I have to say: I'm not entirely sure I'm happy IBM won this battle. The Oracle syntax is simple easy to use. The IBM/ANSI syntax is, well, baroque. There's a certain logical beauty to it but I can't see users being happy trying to figure out how to use it. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com
Le jeudi 25 janvier 2007 à 12:12 -0500, Gregory Stark a écrit : <blockquote type="CITE"><pre> <font color="#000000">"Joshua D. Drake" <<a href="mailto:jd@commandprompt.com">jd@commandprompt.com</a>> writes:</font> <font color="#000000">> > That's basically how the existing patch approached the problem. It invents a</font> <font color="#000000">> > new type of join and a new type of tuplestore that behaves this way. This has</font> <font color="#000000">> > the advantage of working the way Oracle users expect and being relatively</font> <font color="#000000">> > simple conceptually. It has the disadvantage of locking us into what's</font> <font color="#000000">> > basically a nested loop join and not reusing existing join code so it's quite</font> <font color="#000000">> > a large patch.</font> <font color="#000000">> </font> <font color="#000000">> I believe our Syntax should be whatever the standard dictates,</font> <font color="#000000">> regardless of Oracle.</font> <font color="#000000">Well the issue here isn't one of syntax. The syntax is really an orthogonal</font> <font color="#000000">issue. The basic question is whether to treat this as a new type of plan node</font> <font color="#000000">with its behaviour hard coded or whether to try to reuse existing join types</font> <font color="#000000">executing them recursively on their output. I can see advantages either way.</font> <font color="#000000">As far as the syntax goes, now that I've actually read up on both, I have to</font> <font color="#000000">say: I'm not entirely sure I'm happy IBM won this battle. The Oracle syntax is</font> <font color="#000000">simple easy to use. The IBM/ANSI syntax is, well, baroque. There's a certain</font> <font color="#000000">logical beauty to it but I can't see users being happy trying to figure out</font> <font color="#000000">how to use it.</font> </pre></blockquote><br /> I agree with THAT, it's clear that WITH RECURSIVE is more standard... but for the SQL developperCONNECT BY is a paradise... the syntax is clear and powerful... That's why we've chosen to developp our querieswith that (using the connectby() function and the <font size="1">evgen potemkin.</font>'s patch (<a href="http://gppl.moonbone.ru/)">http://gppl.moonbone.ru/)</a><br/><br /> _______________________________________________<br/>Ce message et les �ventuels documents joints peuvent contenir des informationsconfidentielles.<br />Au cas o� il ne vous serait pas destin�, nous vous remercions de bien vouloir le supprimeret en aviser imm�diatement l'exp�diteur. Toute utilisation de ce message non conforme � sa destination, toute diffusionou publication, totale ou partielle et quel qu'en soit le moyen est formellement interdite.<br />Les communicationssur internet n'�tant pas s�curis�es, l'int�grit� de ce message n'est pas assur�e et la soci�t� �mettrice nepeut �tre tenue pour responsable de son contenu.
The CONNECT BY patch from <font size="1">evgen potemkin </font>has been ported to pg 8.2...<br /> and it's now in BSD License...<br/><br /> I will test it on our test environement<br /><br /> Le jeudi 25 janvier 2007 à 11:08 +0000, GregoryStark a écrit : <blockquote type="CITE"><pre> <font color="#000000">Hm, having skimmed through the Evgen Potemkin's recursive queries patch I find</font> <font color="#000000">it quite different from what I was expecting. My own thinking was headed off</font> <font color="#000000">in a different direction.</font> <font color="#000000">Basically the existing patch reimplements a new kind of join which implements</font> <font color="#000000">a kind of nested loop join (with newer versions adding a kind of hash join)</font> <font color="#000000">which feeds a new kind of tuplestore called a tupleconn.</font> <font color="#000000">I was thinking to have a new node above a standard join. The new node would</font> <font color="#000000">repeatedly feed back down to the join the results of the previous iteration</font> <font color="#000000">and reexecute the join to get the next generation.</font> <font color="#000000">I think my approach is more in line with the DB2/ANSI "WITH" style query which</font> <font color="#000000">is expected to do a breadth-first search. The Oracle CONNECT BY syntax is</font> <font color="#000000">expected to do a depth first search.</font> <font color="#000000">I have two major issues with the repeated-join model though. </font> <font color="#000000">a) Ideally we would want to switch between nested loop, merge join, and hash</font> <font color="#000000">join depending on the size of the previous generation. That means the join</font> <font color="#000000">node wouldn't be the same type of join for all the iterations. This is</font> <font color="#000000">important since in most applications you're traversing either up or down a</font> <font color="#000000">tree and are likely starting with very few nodes but often ending up with very</font> <font color="#000000">broad levels with many nodes. No single type of join will be appropriate for</font> <font color="#000000">the whole plan execution.</font> <font color="#000000">b) I do want to be able to support depth-first searching too. I'm not sure how</font> <font color="#000000">to reconcile that with the repeated-join conceptual model. We could always</font> <font color="#000000">resort the entire result set after generating it but that seems like an</font> <font color="#000000">unsatisfactory solution.</font> </pre></blockquote> _______________________________________________<br />Ce message et les �ventuels documents joints peuventcontenir des informations confidentielles.<br />Au cas o� il ne vous serait pas destin�, nous vous remercions de bienvouloir le supprimer et en aviser imm�diatement l'exp�diteur. Toute utilisation de ce message non conforme � sa destination,toute diffusion ou publication, totale ou partielle et quel qu'en soit le moyen est formellement interdite.<br/>Les communications sur internet n'�tant pas s�curis�es, l'int�grit� de ce message n'est pas assur�e et lasoci�t� �mettrice ne peut �tre tenue pour responsable de son contenu.