Skip site navigation (1) Skip section navigation (2)

Re: [HACKERS] WITH RECURSIVE patch V0.1

From: Zoltan Boszormenyi <zb(at)cybertec(dot)at>
To: Martijn van Oosterhout <kleptog(at)svana(dot)org>
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:30:26
Message-ID: 483156C2.50204@cybertec.at (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-patches
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
> 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,
>   

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
http://www.postgresql.at/



In response to

pgsql-hackers by date

Next:From: David FetterDate: 2008-05-19 11:36:30
Subject: Re: WITH RECURSIVE patch V0.1
Previous:From: Bjorn MunchDate: 2008-05-19 10:21:04
Subject: Re: Link requirements creep

pgsql-patches by date

Next:From: David FetterDate: 2008-05-19 11:36:30
Subject: Re: WITH RECURSIVE patch V0.1
Previous:From: Martijn van OosterhoutDate: 2008-05-19 10:06:30
Subject: Re: [HACKERS] WITH RECURSIVE patch V0.1

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group