Re: Status of Hierarchical Queries

"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.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com