Re: Status of Hierarchical Queries

On Thu, Feb 22, 2007 at 07:59:35AM +0000, Gregory Stark wrote:
> "Gavin Sherry" <swm(at)alcove(dot)com(dot)au> writes:
>
> > On Thu, 22 Feb 2007, Gregory Stark wrote:
> >
> >> But in a simple recursive tree search you have a node which wants to do a join
> >> between the output of tree level n against some table to produce tree level
> >> n+1. It can't simply execute the plan to produce tree level n since that's the
> >> same tree it's executing itself. If it calls the Init method on itself it'll
> >> lose all its state.
> >>
> >> There's another reason it can't just execute the previous node. You really
> >> don't want to recompute all the results for level n when you go to produce
> >> level n+1. You want to keep them around from the previous iteration. Otherwise
> >> you have an n^2 algorithm.
> >
> > Right. When I've spent some idle cycles thinking through this in the past
> > I figured that in a non-trivial query, we'd end up with a bunch of
> > materialisations, one for each level of recursion. That sounds very ugly.
>
> Well as long as you have precisely one for each level of recursion I think
> you're doing ok. The problem is if you do it the naive way you calculate the
> first level, then for the second level you recalculate the first level again,
> then for the third level you recalculate both of the previous two, ... So you
> end up with n copies of the first level, n-1 copies of the second level, ...
>
> If you reuse the result sets for subsequent recursive calls then you actually
> only need to keep then nth level around until you're done generating the n+1
> level.
>
> The trick is being able to have two different call sites in the plan tree
> pulling records out of the Materialize node at different points in the result
> set. That currently isn't possible.

So it's sounding like the best we can get in 8.3 is WITH doing
single-level subquery replacement?
--
Jim Nasby jim(at)nasby(dot)net
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)