Re: WITH RECURSIVE doesn't work properly for me

Jing Fan wrote:
> On Wed, Nov 6, 2013 at 8:10 AM, Albe Laurenz <laurenz(dot)albe(at)wien(dot)gv(dot)at> wrote:
>> Let's assume that we have three nodes A, B and C.
>> Also, A points to B, B points to C and C points to B.
>>
>> Let's assume that we already generated (A, B, 1) and (A, C, 2)
>> in previous iterations.
>>
>> Then the "recursive statement" will generate the new
>> rows (A, C, 2) and (A, B, 3).
>> The SELECT ... GROUP BY only surrounds the recursive statement,
>> So the result will still be (A, C, 2) and (A, B, 3).
>>
>> Then the UNION will take care of the first triple, but the second
>> one will be added in this iteration.
>>
>> And so on ad infinitum.

> But after this iteration, the paths will be:
> A B 1
> B C 1
> C B 1
> A C 2
> A B 3
>
> in next iteration, the recursive statement will generate (A,C,2), (A,B,3), and (A,C,4), after the
> group by, it will still be (A,C,2) and (A,B,3)
> so I think it should stop after this iteration.

I see, I didn't notice that.

Actually there is a mistake in my explanation above, see
http://www.postgresql.org/docs/9.3/static/queries-with.html#QUERIES-WITH-SELECT
"Recursive Query Evaluation" for a detailed explanation:

In step 2b, the "working table" is replaced with the "intermediate table",
so the next iteration does not see all previously generated rows,
but only the ones that were generated in the previous iteration.

So in our case, the working table will look like this:

Initially:
A B 1
B C 1
C B 1

After the first iteration:
A C 2

After the third iteration:
A B 3

After the fourth iteration:
A C 4

... and so on.

Your GROUP BY assumes that the working table contains
all previously generated rows.

Yours,
Laurenz Albe