with_mutually_recursive.slt

# Copyright Materialize, Inc. and contributors. All rights reserved.
#
# Use of this software is governed by the Business Source License
# included in the LICENSE file at the root of this repository.
#
# As of the Change Date specified in that file, in accordance with
# the Business Source License, use of this software will be governed
# by the Apache License, Version 2.0.

mode cockroach

## Test correct (intended) behavior:

## Test a plausibly correct recursive query.
query I
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT 1, 2 UNION SELECT a, 7 FROM bar),
    bar (a int) as (SELECT a FROM foo)
SELECT * FROM bar;
----
1
1

## Test a straightforward recursive query.
## This could not terminate if we fail to consolidate iterates.
query I
WITH MUTUALLY RECURSIVE
    t (n int) AS (
        VALUES (1)
        UNION ALL
        SELECT n+1 FROM t WHERE n < 100
    )
SELECT sum(n) FROM t;
----
5050

## Test a straightforward mutually recursive query.
query I
WITH MUTUALLY RECURSIVE
    evens(n int) AS (
        VALUES (1)
        UNION ALL
        SELECT n+1 FROM odds WHERE n < 100
    ),
    odds (n int) AS (
        VALUES (0)
        UNION ALL
        SELECT n+1 FROM evens
    ),
    both (n int) AS (
        SELECT * FROM evens
        UNION ALL
        SELECT * FROM odds
    )
SELECT sum(n) FROM both;
----
10100

## Test a potentially surprising recursive query.
## The analogue of this query in postgres produces only powers of two.
query I
WITH MUTUALLY RECURSIVE
    numbers (n int) as (
        VALUES (1)
        UNION ALL
        (
            WITH rebound AS (SELECT * FROM numbers)
            SELECT distinct t1.n + t2.n AS n
            FROM rebound AS t1, rebound AS t2
            WHERE t1.n <= 256 AND t2.n <= 256
        )
    )
SELECT count(*) FROM numbers;
----
512

## Test a correlated recursive subquery.
query II
SELECT bound, (
    WITH MUTUALLY RECURSIVE
        numbers (n int) as (
            VALUES (1)
            UNION ALL
            (
                WITH rebound AS (SELECT * FROM numbers)
                SELECT distinct t1.n + t2.n AS n
                FROM rebound AS t1, rebound AS t2
                WHERE t1.n <= bound AND t2.n <= bound
            )
        )
    SELECT count(*) FROM numbers
)
FROM (
    SELECT generate_series AS bound FROM generate_series(1, 10)
);
----
1  2
2  4
3  6
4  8
5  10
6  12
7  14
8  16
9  18
10  20

## Test recursive name resolution in SELECT subquery
query III
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT (
        SELECT MIN(c) FROM bar
    ), 2 UNION SELECT 5, 5 FROM bar),
    bar (c int) as (SELECT a FROM foo)
SELECT * FROM foo, bar;
----
5  2  5
5  2  5
5  5  5
5  5  5

## Test recursive name resolution in FROM clause
query III
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (
        SELECT 1, 2 UNION
        SELECT * FROM (
            SELECT MIN(c), 2 FROM bar
        )
    ),
    bar (c int) as (SELECT a FROM foo)
SELECT * FROM foo, bar;
----
1  2  1

## Test recursive name resolution in FROM clause
query I
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT 1, 2 UNION SELECT a, 7 FROM bar),
    bar (a int) as (SELECT a FROM foo)
SELECT (SELECT COUNT(*) FROM foo) FROM bar;
----
2
2

## Test error cases

## Test a recursive query with mismatched types.
statement error did not match inferred type
WITH MUTUALLY RECURSIVE
    foo (a text, b int) AS (SELECT 1, 2 UNION SELECT a, 7 FROM bar),
    bar (a int) as (SELECT a FROM foo)
SELECT * FROM bar;

## Test with fewer columns than declared
statement error did not match inferred type
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT 1 UNION SELECT a FROM bar),
    bar (a int) as (SELECT a FROM foo)
SELECT a FROM foo, bar;

## Test with more columns than declared
statement error did not match inferred type
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT 1, 2, 3 UNION SELECT a, 5, 6 FROM bar),
    bar (a int) as (SELECT a FROM foo)
SELECT a FROM foo, bar;

## Test ambiguity of resulting columns.
statement error column reference "a" is ambiguous
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT 1, 2 UNION SELECT a, 5 FROM bar),
    bar (a int) as (SELECT a FROM foo)
SELECT a FROM foo, bar;

## Test column resolution in planning.
statement error column "a" does not exist
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT 1, 2 UNION SELECT a, 5 FROM bar),
    bar (c int) as (SELECT c FROM foo)
SELECT * FROM foo, bar;

## Test column resolution in planning.
statement error column "c" does not exist
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT 1, 2 UNION SELECT 5, 5 FROM bar),
    bar (c int) as (SELECT c FROM foo)
SELECT * FROM foo, bar;

## Test nested mutual recursion.
statement error column reference "a" is ambiguous
WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (
        WITH MUTUALLY RECURSIVE
            foo (a int, b int) AS (SELECT 1, 2 UNION SELECT c, 5 FROM bar),
            bar (c int) as (SELECT a FROM foo)
        SELECT a, c FROM foo, bar
    ),
    bar (a int) as (SELECT a FROM foo)
SELECT a FROM foo, bar;

## Test Explain plans:

## Test a plausibly correct recursive query.
query T multiline
EXPLAIN WITH MUTUALLY RECURSIVE
    foo (a int, b int) AS (SELECT 1, 2 UNION SELECT a, 7 FROM bar),
    bar (a int) as (SELECT a FROM foo)
SELECT * FROM bar;
----
Explained Query:
  Return
    Get l0
  With Mutually Recursive
    cte l0 =
      Project (#0)
        Distinct group_by=[#0, #1]
          Union
            Map (1, 2)
              Constant
                - ()
            Map (7)
              Get l0

EOF

## Test a nested recursive query.
query T multiline
EXPLAIN WITH MUTUALLY RECURSIVE
    foo (a int8) AS (
        WITH MUTUALLY RECURSIVE
            bar (b int8) AS (
                SELECT * FROM (SELECT * FROM foo UNION ALL SELECT * FROM bar)
            )
        SELECT * FROM (SELECT * FROM foo EXCEPT ALL SELECT * FROM bar)
    )
SELECT * FROM foo;
----
Explained Query:
  Return
    Get l1
  With Mutually Recursive
    cte l1 =
      Return
        Threshold
          Union
            Get l1
            Negate
              Get l0
      With Mutually Recursive
        cte l0 =
          Union
            Get l1
            Get l0

EOF

## Test consolidation of not-really nested recursive query.
query T multiline
EXPLAIN WITH MUTUALLY RECURSIVE
    foo (a int8) AS (
        WITH MUTUALLY RECURSIVE
            bar (b int8) AS (
                SELECT * FROM foo
            )
        SELECT * FROM (SELECT * FROM foo UNION ALL SELECT * FROM bar)
    )
SELECT * FROM foo;
----
Explained Query:
  Return
    Get l0
  With Mutually Recursive
    cte l0 =
      Union
        Get l0
        Get l0

EOF

## Test consolidation of independent recursive query blocks.
query T multiline
EXPLAIN SELECT * FROM (
    WITH MUTUALLY RECURSIVE
        foo (a int8) AS (SELECT DISTINCT a FROM foo)
    SELECT * FROM foo
)
UNION ALL
SELECT * FROM (
    WITH MUTUALLY RECURSIVE
        bar (a int8) AS (SELECT DISTINCT a FROM bar)
    SELECT * FROM bar
);
----
Explained Query:
  Return
    Union
      Get l0
      Get l1
  With Mutually Recursive
    cte l1 =
      Distinct group_by=[#0]
        Get l1
    cte l0 =
      Distinct group_by=[#0]
        Get l0

EOF

## Tests for nested WITH MUTUALLY RECURSIVE

statement ok
CREATE TABLE edges (src int, dst int);

statement ok
INSERT INTO edges SELECT x, x + 1 FROM generate_series(0, 9) as x;

statement ok
INSERT INTO edges VALUES (4, 2), (8, 6);

statement ok
CREATE VIEW strongly_connected_components AS
WITH MUTUALLY RECURSIVE
    intra_edges (src int, dst int) as (
        SELECT * FROM edges
        EXCEPT ALL
        SELECT * FROM edges_delayed
        UNION ALL
        SELECT src, dst
        FROM
            edges,
            forward_labels f_src,
            forward_labels f_dst,
            reverse_labels r_src,
            reverse_labels r_dst
        WHERE src = f_src.node
            AND src = r_src.node
            AND dst = f_dst.node
            AND dst = r_dst.node
            AND f_src.label = f_dst.label
            AND r_src.label = r_dst.label
    ),
    forward_labels (node int, label int) AS (
        WITH MUTUALLY RECURSIVE
            label (node int, comp int) AS (
                SELECT dst, MIN(comp)
                FROM (
                    SELECT dst, dst AS comp FROM edges
                    UNION ALL
                    SELECT intra_edges.dst, label.comp
                    FROM intra_edges, label
                    WHERE intra_edges.src = label.node
                )
                GROUP BY dst
            )
        SELECT * FROM label
    ),
    reverse_labels (node int, label int) AS (
        WITH MUTUALLY RECURSIVE
            label (node int, comp int) AS (
                SELECT src, MIN(comp)
                FROM (
                    SELECT src, src AS comp FROM edges
                    UNION ALL
                    SELECT intra_edges.src, label.comp
                    FROM intra_edges, label
                    WHERE intra_edges.dst = label.node
                )
                GROUP BY src
            )
        SELECT * FROM label
    ),
    edges_delayed (src int, dst int) AS (SELECT * FROM edges)
SELECT * FROM forward_labels UNION SELECT * FROM reverse_labels;

query II
SELECT size, COUNT(*) FROM (
    SELECT label, COUNT(*) as size
    FROM strongly_connected_components
    GROUP BY label
)
GROUP BY size;
----
1  5
3  2

query II
SELECT label, COUNT(*) as size
FROM strongly_connected_components
GROUP BY label
----
0  1
1  1
2  3
5  1
6  3
9  1
10  1

## Tests for sequenced WITH MUTUALLY RECURSIVE

## We should not see any rounds greater than zero, because the fixed point
## should have been reached in the first WITH MUTUALLY RECURSIVE.
query II
WITH MUTUALLY RECURSIVE
    label (node int, comp int) AS (
        SELECT dst, MIN(comp)
        FROM (
            SELECT dst, dst AS comp FROM edges
            UNION ALL
            SELECT edges.dst, label.comp
            FROM edges, label
            WHERE edges.src = label.node
        )
        GROUP BY dst
    )
SELECT round, COUNT(*) FROM (
    WITH MUTUALLY RECURSIVE
        relabel (node int, comp int, round int) AS (
            SELECT DISTINCT ON(node) node, comp, round
            FROM (
                SELECT node, comp, 0 as round FROM label
                UNION ALL
                SELECT edges.dst, relabel.comp, relabel.round + 1
                FROM edges, relabel
                WHERE edges.src = relabel.node
            )
            ORDER BY node, comp
        )
    SELECT round FROM relabel
)
GROUP BY round;
----
0  10