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.

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.