Re: Recursive Queries

Ü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