Re: Status of Hierarchical Queries - Mailing list pgsql-hackers

On Thu, 22 Feb 2007, Gregory Stark wrote:

> "Gavin Sherry" <swm@alcove.com.au> 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