Re: Recursive Queries - Mailing list pgsql-hackers

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.