Re: RFP: Recursive query in 8.4

> Tatsuo Ishii wrote:
> >> On Tue, Feb 19, 2008 at 3:36 AM, Tatsuo Ishii <ishii@postgresql.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.
>