Materialize/test/sqllogictest/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

## Same as above, but with a non-erroring RECURSION LIMIT
query I
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 100)
    t (n int) AS (
        VALUES (1)
        UNION ALL
        SELECT n+1 FROM t
    )
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 db error: ERROR: WITH MUTUALLY RECURSIVE query "bar" declared types \(integer\), but query returns types \(text\)
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 db error: ERROR: WITH MUTUALLY RECURSIVE query "foo" declared types \(integer, integer\), but query returns types \(integer\)
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 db error: ERROR: WITH MUTUALLY RECURSIVE query "foo" declared types \(integer, integer\), but query returns types \(integer, integer, integer\)
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;

# 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

## Regression test for https://github.com/MaterializeInc/database-issues/issues/5550
## Test a WMR query with a delta join.
query III
WITH MUTUALLY RECURSIVE
    c1 (f1 INTEGER, f2 INTEGER, f3 INTEGER) AS (
        SELECT * FROM (VALUES (0, 0, 0))
        UNION ALL (
            SELECT
                a1.f1 + 1 AS f1,
                a1.f2 + 1 AS f2,
                a1.f3 + 1 AS f3
            FROM
                c1 AS a1,
                (
                    SELECT *
                    FROM c1 AS a1
                    LEFT JOIN c1 AS a2 USING (f2)
                    WHERE a1.f1 < 100 AND a2.f2 IS NULL
                ) AS a2
            WHERE a1 . f1 < 100
        )
    )
SELECT * FROM c1;
----
0  0  0

## Regression test for https://github.com/MaterializeInc/database-issues/issues/5606
## Test the situation when a WMR cte has an inner WMR whose body ends with an arrangement.
query I
WITH MUTUALLY RECURSIVE
  cnt (i int) AS (
    (WITH MUTUALLY RECURSIVE
       cnt (i int) AS (
         SELECT 1 AS i
         UNION
         SELECT i+1 FROM cnt WHERE i < 3)
       SELECT i FROM cnt
    )
    UNION
    SELECT i+100 FROM cnt WHERE i < 500)
SELECT i FROM cnt
ORDER BY i;
----
1
2
3
101
102
103
201
202
203
301
302
303
401
402
403
501
502
503

## Tests for RECURSION LIMIT
## (See plans in `normalize_lets.slt`)

query I rowsort
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 3)
  cnt (i int) AS (
    SELECT 1 AS i
    UNION
    SELECT i+1 FROM cnt)
SELECT * FROM cnt;
----
1
2
3

query I rowsort
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT = 3)
  cnt (i int) AS (
    SELECT 1 AS i
    UNION
    SELECT i+1 FROM cnt)
SELECT * FROM cnt;
----
1
2
3

query error db error: ERROR: Evaluation error: Recursive query exceeded the recursion limit 3\. \(Use RETURN AT RECURSION LIMIT to not error, but return the current state as the final result when reaching the limit\.\)
WITH MUTUALLY RECURSIVE (ERROR AT RECURSION LIMIT 3)
  cnt (i int) AS (
    SELECT 1 AS i
    UNION
    SELECT i+1 FROM cnt)
SELECT * FROM cnt;

query II
(WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 3)
  cnt (i int) AS (
    SELECT 1 AS i
    UNION
    SELECT i+1 FROM cnt)
SELECT -10, i FROM cnt)
UNION
(WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 5)
  cnt (i int) AS (
    SELECT 1 AS i
    UNION
    SELECT i+1 FROM cnt)
SELECT -20, i FROM cnt)
----
-20  1
-20  2
-20  3
-20  4
-20  5
-10  1
-10  2
-10  3

query I
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 100)
    t0 (n int) AS (
        VALUES (1)
        UNION ALL
        SELECT n+1 FROM t0
    ),
    t1 (n int) AS (
        VALUES (-1)
        UNION ALL
        SELECT n+1 FROM t1
    )
SELECT (SELECT sum(n) FROM t0) - (SELECT sum(n) FROM t1);
----
200

query I
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 6)
  cnt (i int) AS (
    (WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 3)
       cnt (i int) AS (
         SELECT 1 AS i
         UNION
         SELECT i+1 FROM cnt)
       SELECT i FROM cnt
    )
    UNION
    SELECT i+100 FROM cnt)
SELECT i FROM cnt
ORDER BY i;
----
1
2
3
101
102
103
201
202
203
301
302
303
401
402
403
501
502
503

query error db error: ERROR: Evaluation error: Recursive query exceeded the recursion limit 100\. \(Use RETURN AT RECURSION LIMIT to not error, but return the current state as the final result when reaching the limit\.\)
(WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 10)
    t (n int) AS (
        VALUES (1)
        UNION ALL
        SELECT n+1 FROM t
    )
SELECT sum(n) FROM t)
UNION ALL
(WITH MUTUALLY RECURSIVE (ERROR AT RECURSION LIMIT 100)
    t (n int) AS (
        VALUES (1)
        UNION ALL
        SELECT n+1 FROM t
    )
SELECT sum(n) FROM t);

statement ok
CREATE TABLE t1 (f1 INTEGER);

statement ok
CREATE MATERIALIZED VIEW v1 AS
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 2)
  cnt (f1 INTEGER) AS (
    SELECT f1 FROM t1 UNION ALL SELECT f1+1 AS f1 FROM cnt
  )
SELECT * FROM cnt;

statement ok
INSERT INTO t1 VALUES (1);

query I
SELECT * FROM v1;
----
1
2

statement ok
UPDATE t1 SET f1 = 2;

query I
SELECT * FROM v1;
----
2
3

statement error db error: ERROR: invalid RECURSION LIMIT: must provide an unsigned integer value
WITH MUTUALLY RECURSIVE (RECURSION LIMIT)
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

statement error db error: ERROR: Expected one of RECURSION or RETURN or ERROR, found right parenthesis
WITH MUTUALLY RECURSIVE ()
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

statement error db error: ERROR: invalid RECURSION LIMIT: cannot use value as number
WITH MUTUALLY RECURSIVE (RECURSION LIMIT aaaaaaa)
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

statement error db error: ERROR: invalid RECURSION LIMIT: invalid unsigned numeric value: invalid digit found in string
WITH MUTUALLY RECURSIVE (RECURSION LIMIT -3)
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

statement error db error: ERROR: RECURSION LIMIT specified more than once
WITH MUTUALLY RECURSIVE (RECURSION LIMIT 3, RECURSION LIMIT 5)
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

statement error db error: ERROR: Invalid WITH MUTUALLY RECURSIVE recursion limit\. More than one recursion limit given\. Please give at most one of RECURSION LIMIT, ERROR AT RECURSION LIMIT, RETURN AT RECURSION LIMIT\.
WITH MUTUALLY RECURSIVE (RECURSION LIMIT 3, ERROR AT RECURSION LIMIT 5)
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

statement error db error: ERROR: Invalid WITH MUTUALLY RECURSIVE recursion limit\. More than one recursion limit given\. Please give at most one of RECURSION LIMIT, ERROR AT RECURSION LIMIT, RETURN AT RECURSION LIMIT\.
WITH MUTUALLY RECURSIVE (RECURSION LIMIT 3, RETURN AT RECURSION LIMIT 5)
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

statement error db error: ERROR: Invalid WITH MUTUALLY RECURSIVE recursion limit\. More than one recursion limit given\. Please give at most one of RECURSION LIMIT, ERROR AT RECURSION LIMIT, RETURN AT RECURSION LIMIT\.
WITH MUTUALLY RECURSIVE (ERROR AT RECURSION LIMIT 3, RETURN AT RECURSION LIMIT 5)
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

# It's important that we error out for RECURSION LIMIT 0, because we are NOT handling this case in some optimizer transforms.
statement error db error: ERROR: Invalid WITH MUTUALLY RECURSIVE recursion limit\. Recursion limit has to be greater than 0\.
WITH MUTUALLY RECURSIVE (RECURSION LIMIT 0)
  cnt (i int) AS (SELECT 1 AS i UNION SELECT i+1 FROM cnt)
SELECT * FROM cnt;

## Check casting from derived to proposed types, see
## https://github.com/MaterializeInc/materialize/pull/23658

statement ok
CREATE TABLE y (a BIGINT);

statement ok
INSERT INTO y VALUES (1);

query T
WITH MUTUALLY RECURSIVE
    bar(x NUMERIC) as (SELECT sum(a) FROM y)
SELECT x FROM bar
----
1

query T
WITH MUTUALLY RECURSIVE
    bar(x NUMERIC) as (SELECT sum(a) FROM y)
SELECT pg_typeof(x) FROM bar
----
numeric

query T
WITH MUTUALLY RECURSIVE
    bar(x NUMERIC) as (SELECT sum(a) + 1.23456 FROM y)
SELECT x FROM bar
----
2.23456

query T
WITH MUTUALLY RECURSIVE
    bar(x NUMERIC(38,2)) as (SELECT sum(a) + 1.23456 FROM y)
SELECT x FROM bar
----
2.23

query T
WITH MUTUALLY RECURSIVE
    bar(x UINT2) as (SELECT 1::INT8)
SELECT x FROM bar
----
1

query error "-1" uint2 out of range
WITH MUTUALLY RECURSIVE
    bar(x UINT2) as (SELECT -1::INT8)
SELECT x FROM bar

# TODO: '1' should be coercible to an integer.
query error db error: ERROR: WITH MUTUALLY RECURSIVE query "bar" declared types \(bigint\), but query returns types \(text\)
WITH MUTUALLY RECURSIVE
    bar(x INT8) as (SELECT '1')
SELECT x FROM bar

statement ok
CREATE TYPE list_numeric_scale_2 AS LIST (ELEMENT TYPE = NUMERIC(38,2));

query T
WITH MUTUALLY RECURSIVE
    bar(x list_numeric_scale_2) as (SELECT LIST[sum(a) + 1.2345] FROM y)
SELECT x::TEXT FROM bar
----
{2.23}

query error db error: ERROR: WITH MUTUALLY RECURSIVE query "bar" declared types \(list_numeric_scale_2\), but query returns types \(text list\)
WITH MUTUALLY RECURSIVE
    bar(x list_numeric_scale_2) as (SELECT LIST['1'::TEXT])
SELECT x FROM bar

## Adapted from https://www.sqlite.org/lang_with.html#outlandish_recursive_query_examples
query T multiline
WITH MUTUALLY RECURSIVE
  xaxis(x double) AS (VALUES(-2.0) UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2),
  yaxis(y double) AS (VALUES(-1.0) UNION ALL SELECT y+0.1 FROM yaxis WHERE y<1.0),
  m(iter int, cx double, cy double, x double, y double) AS (
    SELECT 0, x, y, 0.0, 0.0 FROM xaxis, yaxis
    UNION ALL
    SELECT iter+1, cx, cy, x*x-y*y + cx, 2.0*x*y + cy FROM m
     WHERE (x*x + y*y) < 4.0 AND iter<28
  ),
  m2(iter int, cx double, cy double) AS (
    SELECT max(iter), cx, cy FROM m GROUP BY cx, cy
  ),
  a(t text, cy double) AS (
    SELECT string_agg( substr(' .+*#', 1+least(iter/7,4), 1), '' ORDER BY cx), cy
    FROM m2 GROUP BY cy
  )
SELECT string_agg(rtrim(t), chr(10) ORDER BY cy) FROM a;
----
                                    ....#
                                   ..#*..
                                 ..+####+.
                            .......+####....   +
                           ..##+*##########+.++++
                          .+.##################+.
              .............+###################+.+
              ..++..#.....*#####################+.
             ...+#######++#######################.
          ....+*################################.
 #############################################...
          ....+*################################.
             ...+#######++#######################.
              ..++..#.....*#####################+.
              .............+###################+.+
                          .+.##################+.
                           ..##+*##########+.++++
                            .......+####....   +
                                 ..+####+.
                                   ..#*..
                                    ....#
                                    +.
EOF