Re: [PATCH] Allow multiple recursive self-references

> I have been studying this a bit more. I don't understand your argument here.
> Why would this query have different semantics than, say
>
> WITH RECURSIVE t(n) AS (
> VALUES (1)
> UNION ALL
> VALUES (2)
> UNION ALL
> SELECT n+1 FROM t WHERE n < 100
> ) SELECT * FROM t LIMIT 100;
>
> The order of UNION branches shouldn't be semantically relevant.

WITH RECURSIVE (ab)uses the (typically associative and commutative) UNION [ALL] clause,
and fundamentally changes the semantics – associativity and commutativity no longer apply.
I think your confusion stems from this ambiguity.

Let me briefly reiterate WITH RECURSIVE. Basically, you always have a query like this:

> WITH RECURSIVE w(c1,...) AS (
> <non-recursive>
> UNION [ALL]
> <recursive>
> ) q;

There must be a non-recursive part that does not refer to w, and -- without
the patch -- exactly one recursive part that refers to w. The non-recursive part,
and the recursive part are combined using UNION [ALL].

However, let's assume a different, unambiguous syntax just to make my point:

> WITH RECURSIVE w(c1,...) AS (
> <non-recursive>
> RUNION [ALL]
> <recursive>
> ) q;

Everything remains the same except that the non-recursive part and the recursive
part are combined using RUNION [ALL] instead of UNION [ALL].

Now let me rephrase your examples using this syntax:

> WITH RECURSIVE t(n) AS (
> (VALUES (1) UNION ALL VALUES (2))
> RUNION ALL
> SELECT n+1 FROM t WHERE n < 100
> )
> SELECT sum(n) FROM t;

> WITH RECURSIVE t(n) AS (
> VALUES (1) RUNION ALL (VALUES (2)
> UNION ALL
> SELECT n+1 FROM t WHERE n < 100)
> )
> SELECT sum(n) FROM t;

I hope this shows that this is not the same. The first query has two non-recursive
cases and one recursive case. The second query has two recursive cases instead.

The rewrites of those examples:

> RUNION RUNION
> / \ good / \
> VALUES(1) UNION --> VALUES(1) UNION
> / \ / \
> SELECT n+1... VALUES(2) VALUES(2) SELECT n+1...

This rewrite would be valid. The patch would not do that, however.

> RUNION RUNION
> / \ bad / \
> VALUES(1) UNION --> UNION SELECT n+1...
> / \ / \
> SELECT n+1... VALUES(2) VALUES(1) VALUES(2)

This is the rewrite you would expect. But it is not valid, because it changes semantics.
Therefore the patch does not do that.

> I'm having difficulties understanding which subset of cases your patch wants to address.

With this patch an extended WITH RECURSIVE syntax is enabled:

> WITH RECURSIVE w(c1,...) AS (
> <non-recursive>
> UNION [ALL]
> <recursive 1>
> ...
> UNION [ALL]
> <recursive n>
> ) q;

But really, it is:

> WITH RECURSIVE w(c1,...) AS (
> <non-recursive 1>
> ...
> <non-recursive n>
> UNION [ALL]
> <recursive n+1>
> ...
> UNION [ALL]
> <recursive m>
> ) q;

We can have arbitrarily many non-recursive branches (that is possible without the patch),
as well as arbitrarily many recursive UNION [ALL] branches. Problem here: UNION [ALL]
associates to the left. This means that we end up with a left-deep parse tree, that looks
something like this:

> RUNION
> / \
> ... m
> /
> UNION
> / \
> n n+1
> /
> ...
> /
> UNION
> / \
> 1 2

That is not correct, because all non-recursive branches must be part of the left
RUNION branch, and all recursive branches must be part of the right one. Postgres
performs this check in parse_cte.c using the checkWellFormedRecursion() function.

Having said the above, let me once again define the rewrite case the patch implements:

> RUNION RUNION
> / \ rotate / \
> ... n+m ---> UNION UNION
> / / \ / \
> UNION ... n n+1 UNION
> / \ / / \
> n n+1 UNION ... m
> / / \
> ... 1 2
> /
> UNION
> / \
> 1 2

By using tree rotation, the patch transforms the parse tree on the left
into the one on the right. All non-recursive terms 1..n are found in the
left branch of RUNION, all recursive terms n+1..m in the right branch.
This tree now passes the checkWellFormedRecursion() check.
I hope this clarifies things.

> The order of UNION branches shouldn't be semantically relevant.

I agree. However, a strict distinction must be made between RUNION and UNION clauses.
These must not be interchanged.

> I wonder why in ExecWorkTableScan() and ExecReScanWorkTableScan() you call
> tuplestore_copy_read_pointer() instead of just tuplestore_select_read_pointer().

The WorkTableScan reads the working_table tuplestore of the parent RecursiveUnion
operator. But after each iteration of the RecursiveUnion operator, the following
operations are performed:

> 122 /* done with old working table ... */
> 123 tuplestore_end(node->working_table); -- (1)
> 124
> 125 /* intermediate table becomes working table */
> 126 node->working_table = node->intermediate_table; -- (2)
> 127
> 128 /* create new empty intermediate table */
> 129 node->intermediate_table = tuplestore_begin_heap(false, false,
> 130 work_mem); -- (3)

https://doxygen.postgresql.org/nodeRecursiveunion_8c_source.html#l00122

In step (1), the current working_table is released. Therefore, all read pointers
that we had additionally allocated are gone, too. The intermediate table becomes
the working table in step (2), and finally a new empty intermediate table is
created (3).

Because of step (1), we have to allocate new unique read pointers for each worktable
scan again. Just using tuplestore_select_read_pointer() would be incorrect.

> What is the special role of read pointer 0 that you are copying. Before your
> changes, it was just the implicit read pointer, but now that we have several,
> it would be good to explain their relationship.

To allocate a new read pointer, tuplestore_alloc_read_pointer() could also be used.
However, we would have to know about the eflags parameter – which the worktable
scan has no information about.

The important thing about read pointer 0 is that it always exists, and it is initialized correctly.
Therefore, it is save to copy read pointer 0 instead of creating a new one from scratch.

> Also, the comment you deleted says "Therefore, we don't need a private read pointer
> for the tuplestore, nor do we need to tell tuplestore_gettupleslot to copy."
> You addressed the first part with the read pointer handling, but what about the
> second part? The tuplestore_gettupleslot() call in WorkTableScanNext() still
> has copy=false. Is this an oversight, or did you determine that copying is
> still not necessary?

That's an oversight. Copying is still not necessary. Copying would only be required,
if additional writes to the tuplestore occur. But that can not happen here.

Best,
-- Denis