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

Re: [HACKERS] WITH RECURSIVE patch V0.1

From: Zoltan Boszormenyi <zb(at)cybertec(dot)at>
To: Gregory Stark <stark(at)enterprisedb(dot)com>
Cc: Martijn van Oosterhout <kleptog(at)svana(dot)org>, 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 19:22:32
Message-ID: 4831D378.7050201@cybertec.at (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-patches
Gregory Stark írta:
> "Martijn van Oosterhout" <kleptog(at)svana(dot)org> writes:
>
>   
>> 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. 
>>     
>
> I think it's not so simple. How do you reconcile that concept with the join
> plans like merge join or hash join which expect you to be able to be able to
> process the records in a specific order?
>
> It sounds like you might have to keep around a stack of started executor nodes
> or something but hopefully we can avoid anything like that because, well, ick.
>   

If I understand the code right, the recursion from level N to level N+1 
goes like this:
collect all records from level N and JOIN it with the recursive query. 
This way
we get all level 1 records from the base query, then all records at the 
second level, etc.
This is how it gets breadth-first ordering.
Depth-first ordering could go like this: get only 1 from the current 
level then go
into recursion. Repeat until there are no records in the current level.
The only difference would be more recursion steps. Instead of one per level,
there would be N per level if there are N tuples in the current level. 
Definitely
slower then the current implementation but comparable with the tablefunc.c
connectby() code.

-- 
----------------------------------
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: Douglas McNaughtDate: 2008-05-19 21:57:00
Subject: Re: Installation of Postgres 32Bit on 64 bit machine
Previous:From: Andrew DunstanDate: 2008-05-19 16:17:02
Subject: Re: triggers on prepare, commit, rollback... ?

pgsql-patches by date

Next:From: Tom LaneDate: 2008-05-19 23:42:15
Subject: Re: Map forks (WIP)
Previous:From: Tom LaneDate: 2008-05-19 18:10:12
Subject: Re: lc_time and localized dates

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