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 |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers pgsql-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/
From | Date | Subject | |
---|---|---|---|
Next Message | Douglas McNaught | 2008-05-19 21:57:00 | Re: Installation of Postgres 32Bit on 64 bit machine |
Previous Message | Andrew Dunstan | 2008-05-19 16:17:02 | Re: triggers on prepare, commit, rollback... ? |
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2008-05-19 23:42:15 | Re: Map forks (WIP) |
Previous Message | Tom Lane | 2008-05-19 18:10:12 | Re: lc_time and localized dates |