Re: RFP: Recursive query in 8.4

> Tatsuo Ishii wrote:
> >> On Tue, Feb 19, 2008 at 3:36 AM, Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:
> >>
> > I hope so. But the first thing I would like to do is, to implement the
> > right thing (i.e. following the standard).
> >
> > I don't see any reason that the proposal gets less performance than
> > existing functions. Moreover the proposal could better cooperate with
> > the optimizer since it can feed more info to it. Any ideas to enhance
> > the performance are welcome.
> >
>
> I agree about following the standard but I think it's true that the
> standard creates some challenges for the optimizer.
>
> The standard recursive query syntax is quite general. It can represent
> arbitrary non-linear recursive queries including possibly mutually
> recursive queries, for example. The challenge is that there are no extra
> hints when you have the more usual case of a simple linear recursion.

I seems the standard does not allow non-linear recursive queries. In
the SQL:2008 draft pp.380:

7.13 <query expression>

Syntax Rules 2) g) iv)

"If WLE_i is recursive, then WLE_i shall be linearly recursive."

So now the problem is, how to detect the non-linear recursive queries
and reject them.

> You really do want to discover such linear recursive structures because
> you can use simpler algorithms and recover memory sooner if you know you
> have a linear recursive query. You can also support the SEARCH and CYCLE
> clauses to do depth-first searches which you can't do for arbitrary
> recursive queries. I also don't have much hope for good optimizer
> estimates for general recursive queries but for linear recursive queries
> we can probably do better.
>
> But I think it's actually easier to implement the general case than the
> special nodes to handle the linear case more efficiently. To handle the
> general case we need the memoize node to handle recursive loops in the
> plan and then we can use otherwise normal plan nodes.
>
> My plan was to implement the general case first, then look for ways to
> add intelligence in the planner to discover linearity and add new paths
> to take advantage of it.
>