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 match
