Re: [PATCH] Allow multiple recursive self-references

On Tue, Mar 23, 2021 at 1:03 PM Denis Hirn <denis(dot)hirn(at)uni-tuebingen(dot)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&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