On Thu, Feb 22, 2007 at 07:59:35AM +0000, Gregory Stark wrote:
> "Gavin Sherry" <[EMAIL PROTECTED]> 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                                            [EMAIL PROTECTED]
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
       choose an index scan if your joining column's datatypes do not

Reply via email to