Martijn van Oosterhout írta:
On Mon, May 19, 2008 at 11:56:17AM +0200, Zoltan Boszormenyi wrote:
>From an implementation point of view, the only difference between
breadth-first and depth-first is that your tuplestore needs to be LIFO
instead of FIFO.
Are you sure? I think a LIFO tuplestore would simply return reversed
breadth-first order. Depth-first means for every new record descend into
another recursion first then continue with the next record on the right.

Say your tree looks like: Root->A, D A->B,C

LIFO pushes A and D. It then pops A and pushes B and C. B and C have no
children and are returned. Then D is popped and E and F pushed. So the
returned order is: A,B,C,D,E,F. You could also do B,C,A,E,F,D if you

FIFO pushes A and D. It then pops A and puts B and C at *the end*. It
then pops D and pushes E and F at the end. So you get the order

Hope this helps,

Thanks, I didn't consider popping elements off while processing.
However, if the toplevel query returns tuples in A, D order, you need
a positioned insert into the tuplestore, because the LIFO would pop D first.

Say, a "treestore" would work this way:
1. setup: treestore is empty, storage_position := 0
2. treestore_puttupleslot() adds slot at current position, storage_position++ 3. treestore_gettupleslot() removes slot from the beginning, storage_position := 0 This works easily in memory lists but it's not obvious for me how it may work
with disk backed temporary storage inside PG.

Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH

Sent via pgsql-patches mailing list (
To make changes to your subscription:

Reply via email to