Re: RFP: Recursive query in 8.4

[This message is mostly for the benefit of the list -- he and I already talked
a bit about this here at FOSDEM. Ishii-san, if you have a chance we should sit
down and talk about this in more detail before we leave!]

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 (surprisingly) 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.

--
greg