From: | "Jim C(dot) Nasby" <jim(at)nasby(dot)net> |
---|---|
To: | Gregory Stark <stark(at)enterprisedb(dot)com> |
Cc: | Gavin Sherry <swm(at)alcove(dot)com(dot)au>, "Jonah H(dot) Harris" <jonah(dot)harris(at)gmail(dot)com>, PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: Status of Hierarchical Queries |
Date: | 2007-02-23 16:31:37 |
Message-ID: | 20070223163137.GJ19527@nasby.net |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On Thu, Feb 22, 2007 at 07:59:35AM +0000, Gregory Stark wrote:
> "Gavin Sherry" <swm(at)alcove(dot)com(dot)au> writes:
>
> > On Thu, 22 Feb 2007, Gregory Stark wrote:
> >
> >> But in a simple recursive tree search you have a node which wants to do a join
> >> between the output of tree level n against some table to produce tree level
> >> n+1. It can't simply execute the plan to produce tree level n since that's the
> >> same tree it's executing itself. If it calls the Init method on itself it'll
> >> lose all its state.
> >>
> >> There's another reason it can't just execute the previous node. You really
> >> don't want to recompute all the results for level n when you go to produce
> >> level n+1. You want to keep them around from the previous iteration. Otherwise
> >> you have an n^2 algorithm.
> >
> > Right. When I've spent some idle cycles thinking through this in the past
> > I figured that in a non-trivial query, we'd end up with a bunch of
> > materialisations, one for each level of recursion. That sounds very ugly.
>
> Well as long as you have precisely one for each level of recursion I think
> you're doing ok. The problem is if you do it the naive way you calculate the
> first level, then for the second level you recalculate the first level again,
> then for the third level you recalculate both of the previous two, ... So you
> end up with n copies of the first level, n-1 copies of the second level, ...
>
> If you reuse the result sets for subsequent recursive calls then you actually
> only need to keep then nth level around until you're done generating the n+1
> level.
>
> The trick is being able to have two different call sites in the plan tree
> pulling records out of the Materialize node at different points in the result
> set. That currently isn't possible.
So it's sounding like the best we can get in 8.3 is WITH doing
single-level subquery replacement?
--
Jim Nasby jim(at)nasby(dot)net
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)
From | Date | Subject | |
---|---|---|---|
Next Message | Joshua D. Drake | 2007-02-23 16:32:34 | Re: SCMS question |
Previous Message | Andreas Pflug | 2007-02-23 16:24:57 | Re: [Monotone-devel] Re: SCMS question |