[PATCH] Allow multiple recursive self-references

On Tue, Mar 23, 2021 at 1:03 PM Denis Hirn <denis.hirn@uni-tuebingen.de>
wrote:

Hey everyone,

As you know, Postgres currently supports SQL:1999 recursive common table
expressions, using WITH RECURSIVE. However, Postgres does not allow more
than
one recursive self-reference in the recursive term. This restriction seems
to be
unnecessary.

In this mail, I'd like to propose a patch that removes this restriction,
and
therefore allows the use of multiple self-references in the recursive term.
After the patch:

WITH RECURSIVE t(n) AS (
VALUES(1)
UNION ALL
SELECT t.n+f.n
FROM t, t AS f
WHERE t.n < 100
) SELECT * FROM t;

n
-----
1
2
4
8
16
32
64
128
(8 rows)

This feature deviates only slightly from the current WITH RECURSIVE, and
requires very little changes (~10 loc). Any thoughts on this?

--
Denis Hirn

I am not at all sure what the standard says about such recursion but it
looks like the two t's are treated in your patch as the same incarnation of
the table, not as a cross join of two incarnations. The natural result I
would expect from a this query would be all numbers from 1 to 198 (assuming
that the query is modified to restrict f.n and that UNION ALL is converted
to UNION to avoid infinite recursion).

I don't think any other DBMS has implemented this, except MariaDB. Tested
here:
https://dbfiddle.uk/?rdbms=mariadb_10.5&amp;fiddle=565c22771fdfc746e05808a7da7a205f

SET @@standard_compliant_cte=0;
WITH RECURSIVE t(n) AS (
SELECT 1
UNION -- ALL
SELECT t.n + f.n
FROM t, t AS f
WHERE t.n < 4 AND f.n < 4
) SELECT * FROM t;

Result:

| n |
| -: |
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
| 6 |

Best regards
Pantelis Theodosiou

Hey Pantelis,

I am not at all sure what the standard says about such recursion [...]

as far as I know, the standard does not constraint the number of self-references
of recursive common table expressions. However, I could be wrong here.

[...] but it looks like the two t's are treated in your patch as the same incarnation of the table, not as a cross join of two incarnations.

That's right and – as far as I'm concerned – it's expected behaviour. The patch only allows the recursive
union operator's working table to be read more than once. All self-references read exactly the same rows
in each iteration. You could basically accomplish the same thing with another CTE like this:

WITH RECURSIVE t(n) AS (
VALUES(1)
UNION ALL
(WITH wt AS (SELECT * FROM t)
SELECT wt.n+f.n
FROM wt, wt AS f
WHERE wt.n < 100)
) SELECT * FROM t;

But honestly, this feels more like a hack than a solution to me. The entire working table is
materialized by the (non recursive) common table expression wt, effectively doubling the
memory consumption of the query. This patch eliminates this intermediate materialization.

I don't think any other DBMS has implemented this, except MariaDB. Tested here:

There are a few recent DBMSs that I know of that support this: HyPer, Umbra, DuckDB, and NoisePage.
I'm sure there are some more examples. Still, you are right, many other DBMSs do not support this – yet.

--
Denis Hirn

Denis Hirn <denis.hirn@uni-tuebingen.de> writes:

I am not at all sure what the standard says about such recursion [...]

as far as I know, the standard does not constraint the number of self-references
of recursive common table expressions. However, I could be wrong here.

As far as I can see, the spec flat-out forbids this. In SQL:2021,
it's discussed in 7.17 <query expression> syntax rule 3) j) ix), which
defines

ix) If WLEi is recursive, then:
1) Let S be the stratum that contains WQNi.
2) If WQEi does not contain a <query specification> that contains
more than one <query name> referencing members of S, then WLEi is
linearly recursive.

("stratum" means a set of mutually-recursive WITH items), and they
helpfully explain

NOTE 308 — For example, if WLEi contains the <query specification>
SELECT * FROM A AS A1, A AS A2
where A is a <query name> in S, then WLEi is not linearly recursive. The
point is that this <query specification> contains two references to
members of S. It is irrelevant that they reference the same member of S.

and then the next rule says

x) If WLEi is recursive, then WLEi shall be linearly recursive.

So the problem with extending the spec here is that someday they might
extend it with some other semantics, and then we're between a rock and
a hard place.

If there were really compelling reasons why (a) we have to have this
feature and (b) there's only one reasonable way for it to act, hence
no likelihood that the SQL committee will choose something else, then
I'd be willing to think about getting out front of the committee.
But you haven't made either case.

I don't think any other DBMS has implemented this, except MariaDB. Tested here:

There are a few recent DBMSs that I know of that support this: HyPer, Umbra, DuckDB, and NoisePage.

Do they all act the same? Has anybody that sits on the SQL committee
done it? (If you could point to DB2, in particular, I'd have some
confidence that the committee might standardize on their approach.)

A totally independent question is whether you've even defined a
well-defined behavior. There's an interesting comment in the spec:

NOTE 310 — The restrictions insure that each WLEi, viewed as a
transformation of the query names of the stratum, is monotonically
increasing. According to Tarski’s fixed point theorem, this insures that
there is a fixed point. The General Rules use Kleene’s fixed point
theorem to define a sequence that converges to the minimal fixed
point.

I don't know any of the underlying math here, but if you've got a
join of multiple recursion references then the number of output
rows could certainly be nonlinear, which very possibly breaks the
argument that there's a well-defined interpretation.

regards, tom lane

Thanks for the feedback, Tom.

Tom Lane <tgl@sss.pgh.pa.us> writes:
[...]
As far as I can see, the spec flat-out forbids this. In SQL:2021,
it's discussed in 7.17 <query expression> syntax rule 3) j) ix), which
defines [linear recursion]

(Aside: We don't have a copy of the SQL:2021 specification here (all
we've got here is the SQL:2016 variant). We've browsed the ISO site
and didn't find find SQL:2021 there. Is that a generally available
draft document?)

So the problem with extending the spec here is that someday they might
extend it with some other semantics, and then we're between a rock and
a hard place.

There are two issues, say [LIN] and [NON-LIN], here. Re [LIN]:

[LIN] PostgreSQL does not allow multiple references to the recursive
common table, even if the recursion is LINEAR. Plenty of examples
of such queries are found in the documentation of established RDBMSs,
among these IBM Db2 and MS SQL Server:

- https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/sqlp/rbafyrecursivequeries.htm#d60691e2455
(example "Two tables used for recursion using recursive common
table expressions")

- https://docs.microsoft.com/en-us/sql/t-sql/queries/with-common-table-expression-transact-sql?view=sql-server-ver15#h-using-multiple-anchor-and-recursive-members
(example "Using multiple anchor and recursive members")

Db2 and SQL Server process such linear queries with multiple recursive
CTE references just fine. As does SQLite3. With the proposed patch,
PostgreSQL would be able to process these, too (and deliver the same
expected result).

If there were really compelling reasons why (a) we have to have this
feature and (b) there's only one reasonable way for it to act, hence
no likelihood that the SQL committee will choose something else, then
I'd be willing to think about getting out front of the committee.
But you haven't made either case.
[...]
Do they all act the same? Has anybody that sits on the SQL committee
done it? (If you could point to DB2, in particular, I'd have some
confidence that the committee might standardize on their approach.)

We'd classify the ability of established RDBMSs to cope with the just
mentioned class of queries (and PostgreSQL's inability to do the same)
as one compelling reason. Also, the existing functionality in Db2 and
SQL Server would be a yardstick for the expected behavior.

A totally independent question is whether you've even defined a
well-defined behavior. There's an interesting comment in the spec:

NOTE 310 — The restrictions insure that each WLEi, viewed as a
transformation of the query names of the stratum, is monotonically
increasing. According to Tarski’s fixed point theorem, this insures that
there is a fixed point. The General Rules use Kleene’s fixed point
theorem to define a sequence that converges to the minimal fixed
point.

I don't know any of the underlying math here, but if you've got a
join of multiple recursion references then the number of output
rows could certainly be nonlinear, which very possibly breaks the
argument that there's a well-defined interpretation.

This brings us to [NON-LIN]:

[NON-LIN] NOTE 310 refers to Tarski's fixed point theorem and the
prerequisite that the recursive CTE defines a MONOTONIC query (this
guarantees the existence of a least fixed point which defines
the meaning of a recursive CTE in the first place). MONOTONICITY
and NON-LINEAR recursion, however, are two separate/orthogonal issues.

A linear recursive query can be monotonic or non-monotonic (and PostgreSQL
currently has a system of safeguards that aim to identify the latter
kind of problematic queries, ruling out the use of EXCEPT, aggregation,
and so forth), just like a non-linear query can. A mononotic non-linear
recursive query approaches a least fixed point which makes the
behavior of a non-linear recursive CTE as well-defined as a linear
CTE.

In fact, the document that led to the inclusion of WITH RECURSIVE into
the SQL standard (see reference [1]S.J. Finkelstein, N. Mattos, I.S. Mumick, H. Pirahesh, "Expressing Recursive Queries in SQL,"" ANSI Document X3H2-96-075r1, 1996, https://www.kirusa.com/mumick/pspapers/ansiRevisedRecProp96-075r1.ps.Z below) mentions that "Linear
recursion is a special case of non-linear recursion" (Section 3.9) in
the fixpoint-based semantics. (It appears that the authors aimed to
introduce non-linear WITH RECURSIVE from the start but the existing
RECURSIVE UNION proposal at the time was restricted to linear recursion;
so they paddled back and suggested to include non-linear recursion in a
future SQL standard update, coined SQL4 back then).

We do agree, though, that the absence of non-linear recursion in the SQL
standard has openened the field for varied interpretations of the
semantics. MariaDB, for example, admits non-linear recursion once you
set the configuration option standard_compliant_cte to 0. However, a
recursive table reference then returns *all* rows collected so far (not
just those rows produced by the last iteration). This implicit change of
behavior makes sense for use cases of non-linear recursion, yet may come
as a surprise for query authors. Since this implicit change could
alternatively be made explicit (and thus, arguably, clearer) in terms of
a UNION with the recursive table reference, we'd argue to keep the
semantics of recursive table references as is. But before you know, you
end up with diverging semantics for a single SQL construct, just as you said
above.

Given this, we would propose the patch as a means to allow multiple
recursive references for linear queries (see [LIN] above). This allows
PostgreSQL to catch up with Db2, SQL Server, or SQLite3. The semantics
in the [LIN] case are clear.

Best wishes,
--Denis and Torsten

[1]: S.J. Finkelstein, N. Mattos, I.S. Mumick, H. Pirahesh, "Expressing Recursive Queries in SQL,"" ANSI Document X3H2-96-075r1, 1996, https://www.kirusa.com/mumick/pspapers/ansiRevisedRecProp96-075r1.ps.Z
"Expressing Recursive Queries in SQL,"" ANSI Document X3H2-96-075r1, 1996,
https://www.kirusa.com/mumick/pspapers/ansiRevisedRecProp96-075r1.ps.Z

Based on Toms feedback, and due to the fact that SQL:2021 forbids
non-linear recursion, version 2 of the patch allows only linear
recursion. Therefore, later SQL committee decisions on non-linear
recursion should not be problematic.

[LIN] PostgreSQL does not allow multiple references to the recursive
common table, even if the recursion is LINEAR. Plenty of examples
of such queries are found in the documentation of established RDBMSs,
among these IBM Db2 and MS SQL Server:

- https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/sqlp/rbafyrecursivequeries.htm#d60691e2455 <https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/sqlp/rbafyrecursivequeries.htm#d60691e2455&gt;
(example "Two tables used for recursion using recursive common
table expressions")

See the gist at [1]https://gist.github.com/kryonix/73d77d3eaa5a15b3a4bdb7d590fa1253 <https://gist.github.com/kryonix/73d77d3eaa5a15b3a4bdb7d590fa1253&gt; below for SQL code that features multiple (yet linear)
recursive references. A patched PostgreSQL runs this query as expected.

Best wishes,
--Denis and Torsten

[1]: https://gist.github.com/kryonix/73d77d3eaa5a15b3a4bdb7d590fa1253 <https://gist.github.com/kryonix/73d77d3eaa5a15b3a4bdb7d590fa1253&gt;

Sorry, I didn't append the patch properly.

Best wishes,
--Denis

On Wed, Mar 31, 2021 at 7:28 PM Denis Hirn <denis.hirn@uni-tuebingen.de> wrote:

Sorry, I didn't append the patch properly.

The patch does not apply on Head anymore, could you rebase and post a
patch. I'm changing the status to "Waiting for Author".

Regards,
Vignesh

The patch does not apply on Head anymore, could you rebase and post a patch.

Sure thing. Here's the new patch.

Best wishes,
-- Denis

On Thu, Jul 15, 2021 at 09:18:00AM +0200, Denis Hirn wrote:

The patch does not apply on Head anymore, could you rebase and post a patch.

Sure thing. Here's the new patch.

Best wishes,

Thanks for updating this.

In the next version of the patch, would you be so kind as to include
updated documentation of the feature and at least one regression test
of same?

Best,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

In the next version of the patch, would you be so kind as to include
updated documentation of the feature and at least one regression test
of same?

As requested, this new version of the patch contains regression tests and documentation.

Best wishes,
-- Denis

On 20.07.21 13:15, Denis Hirn wrote:

In the next version of the patch, would you be so kind as to include
updated documentation of the feature and at least one regression test
of same?

As requested, this new version of the patch contains regression tests and documentation.

The tests fail when you build with assertions enabled (configure
--enable-cassert).

Some quick style comments:

DocBook content should use 1-space indentation (not 2 spaces).

Typo?: /* we'll see this later */ -> "set"

Opening brace after "if" should be on new line. (See existing code.)

Also, there should be a space after "if".

These casts appear to be unnecessary:

if((Node *) stmt->larg != NULL && (Node *) stmt->rarg != NULL)

The tests fail when you build with assertions enabled (configure --enable-cassert).

Thank you for pointing that out. The new version of this patch fixes that.
The tests are working properly now. All style related issues are fixed as well.

Best wishes,
-- Denis

On Tue, Aug 17, 2021 at 5:58 AM Denis Hirn <denis.hirn@uni-tuebingen.de>
wrote:

The tests fail when you build with assertions enabled (configure

--enable-cassert).

Thank you for pointing that out. The new version of this patch fixes that.
The tests are working properly now. All style related issues are fixed as
well.

Best wishes,
-- Denis

Hi,

+                   selfrefcountL = cstate->selfrefcount;
+                   cstate->selfrefcount = selfrefcount;

Maybe the variable selfrefcountL can be renamed slightly (e.g.
curr_selfrefcount) so that the code is easier to read.

Cheers

Maybe the variable selfrefcountL can be renamed slightly (e.g. curr_selfrefcount) so that the code is easier to read.

Yes, you are absolutely right. Thanks for the suggestion.
The new version renames this variable.

Best wishes,
-- Denis

I tested the following query (from SQLite documentation):

CREATE TABLE edge(aa INT, bb INT);

WITH RECURSIVE nodes(x) AS (
SELECT 59
UNION
SELECT aa FROM edge JOIN nodes ON bb=x
UNION
SELECT bb FROM edge JOIN nodes ON aa=x
)
SELECT x FROM nodes;

ERROR: 42P19: recursive reference to query "nodes" must not appear
within its non-recursive term
LINE 4: SELECT aa FROM edge JOIN nodes ON bb=x
^
LOCATION: checkWellFormedRecursionWalker, parse_cte.c:960

This well-formedness check apparently needs to be enhanced to allow for
more than two branches in the union.

This well-formedness check apparently needs to be enhanced to allow for more than two branches in the union.

The UNION operators' left associativity causes this problem. Currently, the recursive term
must be enclosed in parentheses to make this example work:

WITH RECURSIVE nodes(x) AS (
SELECT 59
UNION
(SELECT aa FROM edge JOIN nodes ON bb=x
UNION
SELECT bb FROM edge JOIN nodes ON aa=x)
)
SELECT x FROM nodes;

The current well-formedness check assumes the left argument of the top most UNION [ALL]
to be the non-recursive term. This allows for arbitrarily many non-recursive terms, and
exactly one recursive term. This should not be changed because later stages expect this
structure. But this left-deep UNION [ALL] tree does not suffice anymore. Therefore, the
ctequery field of the CommonTableExpr must be rewritten –– I think.

Let's take a look at another example:

WITH RECURSIVE nodes(x) AS (
SELECT 59
UNION
SELECT 42
UNION
SELECT aa FROM edge JOIN nodes ON bb=x
UNION -- Top most UNION operator
SELECT bb FROM edge JOIN nodes ON aa=x
)
SELECT x FROM nodes;

This would be parsed left-deep as:
((SELECT 59 UNION SELECT 42) UNION SELECT aa ...) UNION SELECT bb ...

The proposed rewriting should be able to detect that (SELECT 59 UNION SELECT 42) does
not contain any recursive references and therefore pull the term upwards in the tree,
leaving us with:

(SELECT 59 UNION SELECT 42) UNION (SELECT aa ... UNION SELECT bb ...)

Which would be the equivalent of:

WITH RECURSIVE nodes(x) AS (
(SELECT 59
UNION
SELECT 42)
UNION -- Top most UNION operator
(SELECT aa FROM edge JOIN nodes ON bb=x
UNION
SELECT bb FROM edge JOIN nodes ON aa=x)
)
SELECT x FROM nodes;

I am not sure if this patch should introduce such a rewriting.
Any thoughts on this?

Best,
–– Denis

I am not sure if this patch should introduce such a rewriting.

I have thought about this again. I think it is reasonable that this patch introduces
such a rewriting.

This well-formedness check apparently needs to be enhanced to allow for more than two branches in the union.

The new version of this patch contains the necessary rewriting. The example from the SQLite documentation
can now be executed without explicit parentheses.

Best,
–– Denis

The documentation was not up to date anymore with the most recent changes.
This version of the patch fixes that.

Best,
–– Denis

On 31.08.21 16:48, Denis Hirn wrote:

The documentation was not up to date anymore with the most recent changes.
This version of the patch fixes that.

I studied up on the theory and terminology being discussed here. I
conclude that what the latest version of this patch is doing (allowing
multiple recursive references, but only in a linear-recursion way) is
sound and useful.

I haven't looked closely at the implementation changes yet. I'm not
very familiar with that part of the code, so it will take a bit longer.
Perhaps you could explain what you are doing there, either in email or
(even better) in the commit message.

What I think this patch needs is a lot more test cases. I would like to
see more variants of different nestings of the UNION branches, some
mixtures of UNION ALL and UNION DISTINCT, joins of the recursive CTE
with regular tables (like in the flights-and-trains examples), as well
as various cases of what is not allowed, namely showing that it can
carefully prohibit non-linear recursion. Also, in one instance you
modify an existing test case. I'm not sure why. Perhaps it would be
better to leave the existing test case alone and write a new one.

You also introduce this concept of reshuffling the UNION branches to
collect all the recursive terms under one subtree. That could use more
testing, like combinations like nonrec UNION rec UNION nonrec UNION rec
etc. Also, currently a query like this works

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

but this doesn't:

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

With your patch, the second should also work, so let's show some tests
for that as well.