From: | Tatsuo Ishii <ishii(at)postgresql(dot)org> |
---|---|
To: | stark(at)enterprisedb(dot)com |
Cc: | mmoncure(at)gmail(dot)com, pgsql-hackers(at)postgresql(dot)org |
Subject: | Re: RFP: Recursive query in 8.4 |
Date: | 2008-03-04 14:32:53 |
Message-ID: | 20080304.233253.62356358.t-ishii@sraoss.co.jp |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
> 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.
>
From | Date | Subject | |
---|---|---|---|
Next Message | Bruce Momjian | 2008-03-04 14:39:19 | Re: pg_dump additional options for performance |
Previous Message | Gavin M. Roy | 2008-03-04 14:02:27 | 8.3.0 Core with concurrent vacuum fulls |