On Thu, 22 Feb 2007, Gregory Stark wrote: > "Gavin Sherry" <[EMAIL PROTECTED]> writes: > > > Can you elaborate on the 'two different sets of parameters' bit? I'm still > > without coffee. > > The spec allows for arbitrarily complex recursive query structures. Including > mutually recursive queries, and even non-linearly recursive queries. I found > grokking them requires far stronger brews than coffee :)
Hehe. > 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. > >> It is sufficient for the non-recursive case which might make it worthwhile > >> putting it in 8.3. But even there user's expectations are probably that the > >> reason they're writing it as a cte is precisely to avoid duplicate > >> execution. > > > > I wonder if the planner should decide that? > > That's one option. For the non-recursive case we could inline the cte subquery > everywhere it's referenced and then add smarts to the planner to find > identical subqueries and have a heuristic to determine when it would be > advantageous to calculate the result once. > > The alternative is to retain them as references to a single plan. Then have a > heuristic for when to inline them. > > In neither case is a heuristic going to be particularly good. The problem is > that for any reasonably complex plan it'll be cheaper to execute it only once > than multiple times. Unless there's an advantage to be gained by inlining it > such as being able to push conditions down into it. But the only way to find > out if that will be possible would be to try planning it and see. Pushing down predicates was the exact idea I had in mind. Thanks, Gavin ---------------------------(end of broadcast)--------------------------- TIP 4: Have you searched our list archives? http://archives.postgresql.org