Re: contrib/tree

Hannu Krosing wrote:

> On Sun, 2002-01-27 at 00:25, Don Baccus wrote:
>
>>Peter Eisentraut wrote:
>>
>>>I was under the impression that the typical way to handle tree structures
>>>in relational databases was with recursive unions. It's probably
>>>infinitely slower than stuffing everything into one datum, but it gets you
>>>all the flexibility that the DBMS has to offer.
>>>
>
> I see no reason why WITH RECURSIVE should be inherently slower than other
> approaches except that checks for infinite recursion could be pricey.
>
> Other than that getting rows by index should be more or less equal in both
> cases.

We use Oracle's "CONNECT BY", not a key-oriented approach, in the Oracle
version of the toolkit. There are some awkwardnesses involved in their
implementation. You can't join with the table you're "connecting". If
you do it in a subselect then join against the result, you get the right
rows (of course) but Oracle's free to join in any order. So you can't
get a "tree walk" output order if you need to join against your tree,
meaning you have to fall back on a sort key anyway (a simpler one, though).

I haven't looked at "WITH RECURSIVE" to see if it's defined to be more
useful than Oracle's "CONNECT BY" since I don't use any RDBMS that
implements it.

>>My impression is that there's no single "best way" to handle trees or
>>graphs in an RDBMS that doesn't provide internal support (such as Oracle
>>with its "CONNECT BY" extension).
>>
>
> The full SQL3 syntax for it is much more powerful and complex (see
> attachment).
>
> I think that this is what should eventually go into postgresql.

Yes, indeed.

> I'll try if I can build the operators in PL/PGSL so one would not
> "really" need to build special operators ;)
>
> Tell me if this is something impossible.

There's the speed issue, of course ... and the extra space, which for
deep trees could be significant.

Our solution suits our needs very well, and we're happy with it. We do
get 2 billion plus immediate children per node and a one-byte per level
key for trees that aren't big and flat. The intarray approach is just a
different storage technique for the same method, I don't see that moving
nodes is any easier (you have to touch the same number of nodes if you
move a subtree around). It takes more storage and the necessary
comparisons (even if written in C) will be slower unless the tree's big
and flat (because you're using four bytes for every level, while our BIT
VARYING scheme, in practice, uses one byte for each level in a very
large majority of cases).

--
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org