From: | Martijn van Oosterhout <kleptog(at)svana(dot)org> |
---|---|
To: | Zoltan Boszormenyi <zb(at)cybertec(dot)at> |
Cc: | Gregory Stark <stark(at)enterprisedb(dot)com>, Tatsuo Ishii <ishii(at)postgresql(dot)org>, David Fetter <david(at)fetter(dot)org>, PG Hackers <pgsql-hackers(at)postgresql(dot)org>, pgsql-patches(at)postgresql(dot)org |
Subject: | Re: [HACKERS] WITH RECURSIVE patch V0.1 |
Date: | 2008-05-19 10:06:30 |
Message-ID: | 20080519100630.GB14142@svana.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers pgsql-patches |
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
D->E,F
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
wanted.
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
A,D,B,C,E,F
Hope this helps,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> Please line up in a tree and maintain the heap invariant while
> boarding. Thank you for flying nlogn airlines.
From | Date | Subject | |
---|---|---|---|
Next Message | Bjorn Munch | 2008-05-19 10:21:04 | Re: Link requirements creep |
Previous Message | Zoltan Boszormenyi | 2008-05-19 09:56:17 | Re: [HACKERS] WITH RECURSIVE patch V0.1 |
From | Date | Subject | |
---|---|---|---|
Next Message | Zoltan Boszormenyi | 2008-05-19 10:30:26 | Re: [HACKERS] WITH RECURSIVE patch V0.1 |
Previous Message | Zoltan Boszormenyi | 2008-05-19 09:56:17 | Re: [HACKERS] WITH RECURSIVE patch V0.1 |