# 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.

# Test that correlated CTE are lowered properly

mode cockroach

statement ok
CREATE TABLE x (a int)

statement ok
INSERT INTO x VALUES (1), (2), (3)

statement ok
CREATE TABLE y (a int)

statement ok
INSERT INTO y VALUES (2), (3), (4)

# Check that CTEs aren't inlined during planning
query T multiline
EXPLAIN RAW PLAN FOR
WITH t AS (SELECT * FROM y WHERE a < 3)
  SELECT * FROM t NATURAL JOIN t a;
----
Project (#0)
  With
    cte [l0 as t] =
      Filter (#0{a} < 3)
        Get materialize.public.y
  Return
    InnerJoin (#0{a} = #1{a})
      Get l0
      Get l0

Target cluster: quickstart

EOF

# Check that CTE defined in outer context is explained properly
query T multiline
EXPLAIN RAW PLAN FOR
WITH t AS (SELECT * FROM y WHERE a < 3)
  SELECT * FROM y WHERE (select a from t) < a;
----
With
  cte [l0 as t] =
    Filter (#0{a} < 3)
      Get materialize.public.y
Return
  Filter (select(Get l0) < #0{a})
    Get materialize.public.y

Target cluster: quickstart

EOF

# Check the body of a CTE is only lowered once
query T multiline
EXPLAIN DECORRELATED PLAN WITH(arity) FOR
WITH t AS (SELECT * FROM y WHERE a < 3)
  SELECT * FROM t NATURAL JOIN t a;
----
With
  cte l0 =
    Filter (#0{a} < 3) // { arity: 1 }
      CrossJoin // { arity: 1 }
        Constant // { arity: 0 }
          - ()
        Get materialize.public.y // { arity: 1 }
Return // { arity: 1 }
  Project (#0) // { arity: 1 }
    Filter (#0{a} = #1{a}) // { arity: 2 }
      Project (#0, #1) // { arity: 2 }
        CrossJoin // { arity: 2 }
          Get l0 // { arity: 1 }
          Get l0 // { arity: 1 }

Target cluster: quickstart

EOF

# Correlated CTE inside a LATERAL join operand
query T multiline
EXPLAIN DECORRELATED PLAN WITH(arity) FOR
SELECT *
FROM x,
     LATERAL(WITH a(m) AS (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT * FROM a);
----
With
  cte l0 =
    CrossJoin // { arity: 1 }
      Constant // { arity: 0 }
        - ()
      Get materialize.public.x // { arity: 1 }
  cte l1 =
    Distinct project=[#0] // { arity: 1 }
      Get l0 // { arity: 1 }
  cte l2 =
    Reduce group_by=[#0] aggregates=[max(#1{a})] // { arity: 2 }
      Filter (#1{a} < #0{a}) // { arity: 2 }
        CrossJoin // { arity: 2 }
          Get l1 // { arity: 1 }
          Get materialize.public.y // { arity: 1 }
Return // { arity: 2 }
  Project (#0, #2) // { arity: 2 }
    Join on=(#0 = #1) // { arity: 3 }
      Get l0 // { arity: 1 }
      Union // { arity: 2 }
        Get l2 // { arity: 2 }
        CrossJoin // { arity: 2 }
          Project (#0) // { arity: 1 }
            Join on=(#0 = #1) // { arity: 2 }
              Union // { arity: 1 }
                Negate // { arity: 1 }
                  Distinct project=[#0] // { arity: 1 }
                    Get l2 // { arity: 2 }
                Distinct project=[#0] // { arity: 1 }
                  Get l1 // { arity: 1 }
              Get l1 // { arity: 1 }
          Constant // { arity: 1 }
            - (null)

Target cluster: quickstart

EOF

query II rowsort
SELECT *
FROM x,
     LATERAL(WITH a(m) AS (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT * FROM a);
----
1  NULL
2  NULL
3  2

# Reference of a correlated CTE applied to an outer relation that has the same cardinality as
# the one the CTE was applied to.
# When the CTE is lowered, the outer relation is `Get x`. But then, the reference of the CTE
# is applied to `Distinct(Join(Get x, Get y), x.*)` which has the same cardinality as `Get x`.
query T multiline
EXPLAIN DECORRELATED PLAN WITH(arity) FOR
SELECT *
FROM x,
     LATERAL(WITH a(m) as (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT (SELECT m FROM a) FROM y) b;
----
With
  cte l0 =
    CrossJoin // { arity: 1 }
      Constant // { arity: 0 }
        - ()
      Get materialize.public.x // { arity: 1 }
  cte l1 =
    Distinct project=[#0] // { arity: 1 }
      Get l0 // { arity: 1 }
  cte l2 =
    Reduce group_by=[#0] aggregates=[max(#1{a})] // { arity: 2 }
      Filter (#1{a} < #0{a}) // { arity: 2 }
        CrossJoin // { arity: 2 }
          Get l1 // { arity: 1 }
          Get materialize.public.y // { arity: 1 }
  cte l3 =
    CrossJoin // { arity: 2 }
      Get l1 // { arity: 1 }
      Get materialize.public.y // { arity: 1 }
  cte l4 =
    Distinct project=[#0, #1] // { arity: 2 }
      Get l3 // { arity: 2 }
  cte l5 =
    Distinct project=[#0] // { arity: 1 }
      Get l4 // { arity: 2 }
  cte l6 =
    Project (#0, #2) // { arity: 2 }
      Join on=(#0 = #1) // { arity: 3 }
        Get l5 // { arity: 1 }
        Union // { arity: 2 }
          Get l2 // { arity: 2 }
          CrossJoin // { arity: 2 }
            Project (#0) // { arity: 1 }
              Join on=(#0 = #1) // { arity: 2 }
                Union // { arity: 1 }
                  Negate // { arity: 1 }
                    Distinct project=[#0] // { arity: 1 }
                      Get l2 // { arity: 2 }
                  Distinct project=[#0] // { arity: 1 }
                    Get l1 // { arity: 1 }
                Get l1 // { arity: 1 }
            Constant // { arity: 1 }
              - (null)
  cte l7 =
    Union // { arity: 2 }
      Get l6 // { arity: 2 }
      Project (#0, #2) // { arity: 2 }
        FlatMap guard_subquery_size(#1) // { arity: 3 }
          Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
            Get l6 // { arity: 2 }
Return // { arity: 2 }
  Project (#0, #2) // { arity: 2 }
    Join on=(#0 = #1) // { arity: 3 }
      Get l0 // { arity: 1 }
      Project (#0, #2) // { arity: 2 }
        Project (#0, #1, #5) // { arity: 3 }
          Map (#4) // { arity: 6 }
            Join on=(#0 = #2 AND #1 = #3) // { arity: 5 }
              Get l3 // { arity: 2 }
              Project (#0, #1, #3) // { arity: 3 }
                Join on=(#0 = #2) // { arity: 4 }
                  Get l4 // { arity: 2 }
                  Union // { arity: 2 }
                    Get l7 // { arity: 2 }
                    CrossJoin // { arity: 2 }
                      Project (#0) // { arity: 1 }
                        Join on=(#0 = #1) // { arity: 2 }
                          Union // { arity: 1 }
                            Negate // { arity: 1 }
                              Distinct project=[#0] // { arity: 1 }
                                Get l7 // { arity: 2 }
                            Distinct project=[#0] // { arity: 1 }
                              Get l5 // { arity: 1 }
                          Get l5 // { arity: 1 }
                      Constant // { arity: 1 }
                        - (null)

Target cluster: quickstart

EOF

# Correlated CTE used at different scope level: offset 0 and offset 1 (RHS of the join)
# Note: the CTE is represented by %12 (l4)
query T multiline
EXPLAIN DECORRELATED PLAN WITH(arity) FOR
SELECT *
FROM x,
     LATERAL(WITH a(m) AS (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT * FROM a INNER JOIN a b ON a.m = b.m);
----
With
  cte l0 =
    CrossJoin // { arity: 1 }
      Constant // { arity: 0 }
        - ()
      Get materialize.public.x // { arity: 1 }
  cte l1 =
    Distinct project=[#0] // { arity: 1 }
      Get l0 // { arity: 1 }
  cte l2 =
    Reduce group_by=[#0] aggregates=[max(#1{a})] // { arity: 2 }
      Filter (#1{a} < #0{a}) // { arity: 2 }
        CrossJoin // { arity: 2 }
          Get l1 // { arity: 1 }
          Get materialize.public.y // { arity: 1 }
  cte l3 =
    Union // { arity: 2 }
      Get l2 // { arity: 2 }
      CrossJoin // { arity: 2 }
        Project (#0) // { arity: 1 }
          Join on=(#0 = #1) // { arity: 2 }
            Union // { arity: 1 }
              Negate // { arity: 1 }
                Distinct project=[#0] // { arity: 1 }
                  Get l2 // { arity: 2 }
              Distinct project=[#0] // { arity: 1 }
                Get l1 // { arity: 1 }
            Get l1 // { arity: 1 }
        Constant // { arity: 1 }
          - (null)
Return // { arity: 3 }
  Project (#0, #2, #3) // { arity: 3 }
    Join on=(#0 = #1) // { arity: 4 }
      Get l0 // { arity: 1 }
      Filter (#1{m} = #2{m}) // { arity: 3 }
        Project (#0, #1, #3) // { arity: 3 }
          Join on=(#0 = #2) // { arity: 4 }
            Get l3 // { arity: 2 }
            Get l3 // { arity: 2 }

Target cluster: quickstart

EOF

query III
SELECT *
FROM x,
     LATERAL(WITH a(m) AS (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT * FROM a INNER JOIN a b ON a.m = b.m);
----
3  2  2

query III rowsort
SELECT *
FROM x,
     LATERAL(WITH a(m) as (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT * FROM a INNER JOIN a b ON true);
----
1  NULL  NULL
2  NULL  NULL
3  2  2

# Correlated CTE used at different scope level: offset 0 and offset 3 (subquery in the
# selection list of a derived relation in the RHS of the join)
query T multiline
EXPLAIN DECORRELATED PLAN WITH(arity) FOR
SELECT *
FROM x,
     LATERAL(WITH a(m) as (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT * FROM a INNER JOIN (SELECT (SELECT m FROM a) FROM y) b ON true);
----
With
  cte l0 =
    CrossJoin // { arity: 1 }
      Constant // { arity: 0 }
        - ()
      Get materialize.public.x // { arity: 1 }
  cte l1 =
    Distinct project=[#0] // { arity: 1 }
      Get l0 // { arity: 1 }
  cte l2 =
    Reduce group_by=[#0] aggregates=[max(#1{a})] // { arity: 2 }
      Filter (#1{a} < #0{a}) // { arity: 2 }
        CrossJoin // { arity: 2 }
          Get l1 // { arity: 1 }
          Get materialize.public.y // { arity: 1 }
  cte l3 =
    Union // { arity: 2 }
      Get l2 // { arity: 2 }
      CrossJoin // { arity: 2 }
        Project (#0) // { arity: 1 }
          Join on=(#0 = #1) // { arity: 2 }
            Union // { arity: 1 }
              Negate // { arity: 1 }
                Distinct project=[#0] // { arity: 1 }
                  Get l2 // { arity: 2 }
              Distinct project=[#0] // { arity: 1 }
                Get l1 // { arity: 1 }
            Get l1 // { arity: 1 }
        Constant // { arity: 1 }
          - (null)
  cte l4 =
    CrossJoin // { arity: 2 }
      Get l1 // { arity: 1 }
      Get materialize.public.y // { arity: 1 }
  cte l5 =
    Distinct project=[#0, #1] // { arity: 2 }
      Get l4 // { arity: 2 }
  cte l6 =
    Distinct project=[#0] // { arity: 1 }
      Get l5 // { arity: 2 }
  cte l7 =
    Project (#0, #2) // { arity: 2 }
      Join on=(#0 = #1) // { arity: 3 }
        Get l6 // { arity: 1 }
        Get l3 // { arity: 2 }
  cte l8 =
    Union // { arity: 2 }
      Get l7 // { arity: 2 }
      Project (#0, #2) // { arity: 2 }
        FlatMap guard_subquery_size(#1) // { arity: 3 }
          Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
            Get l7 // { arity: 2 }
Return // { arity: 3 }
  Project (#0, #2, #3) // { arity: 3 }
    Join on=(#0 = #1) // { arity: 4 }
      Get l0 // { arity: 1 }
      Project (#0, #1, #3) // { arity: 3 }
        Join on=(#0 = #2) // { arity: 4 }
          Get l3 // { arity: 2 }
          Project (#0, #5) // { arity: 2 }
            Map (#4) // { arity: 6 }
              Join on=(#0 = #2 AND #1 = #3) // { arity: 5 }
                Get l4 // { arity: 2 }
                Project (#0, #1, #3) // { arity: 3 }
                  Join on=(#0 = #2) // { arity: 4 }
                    Get l5 // { arity: 2 }
                    Union // { arity: 2 }
                      Get l8 // { arity: 2 }
                      CrossJoin // { arity: 2 }
                        Project (#0) // { arity: 1 }
                          Join on=(#0 = #1) // { arity: 2 }
                            Union // { arity: 1 }
                              Negate // { arity: 1 }
                                Distinct project=[#0] // { arity: 1 }
                                  Get l8 // { arity: 2 }
                              Distinct project=[#0] // { arity: 1 }
                                Get l6 // { arity: 1 }
                            Get l6 // { arity: 1 }
                        Constant // { arity: 1 }
                          - (null)

Target cluster: quickstart

EOF

query III rowsort
SELECT *
FROM x,
     LATERAL(WITH a(m) AS (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT * FROM a INNER JOIN (SELECT (SELECT m FROM a) FROM y) b ON true);
----
1  NULL  NULL
1  NULL  NULL
1  NULL  NULL
2  NULL  NULL
2  NULL  NULL
2  NULL  NULL
3  2  2
3  2  2
3  2  2

# Correlated CTE used from a correlated scope
# Note: the CTE is represented by %12 (l4)
query T multiline
EXPLAIN DECORRELATED PLAN WITH(arity) FOR
SELECT *
FROM x,
     LATERAL(WITH a(m) AS (SELECT max(y.a) FROM y WHERE y.a < x.a)
             SELECT * FROM y INNER JOIN LATERAL(SELECT y.a FROM x WHERE (SELECT m FROM a) > 0) ON true);
----
With
  cte l0 =
    CrossJoin // { arity: 1 }
      Constant // { arity: 0 }
        - ()
      Get materialize.public.x // { arity: 1 }
  cte l1 =
    Distinct project=[#0] // { arity: 1 }
      Get l0 // { arity: 1 }
  cte l2 =
    Reduce group_by=[#0] aggregates=[max(#1{a})] // { arity: 2 }
      Filter (#1{a} < #0{a}) // { arity: 2 }
        CrossJoin // { arity: 2 }
          Get l1 // { arity: 1 }
          Get materialize.public.y // { arity: 1 }
  cte l3 =
    CrossJoin // { arity: 2 }
      Get l1 // { arity: 1 }
      Get materialize.public.y // { arity: 1 }
  cte l4 =
    CrossJoin // { arity: 2 }
      Distinct project=[#1] // { arity: 1 }
        Get l3 // { arity: 2 }
      Get materialize.public.x // { arity: 1 }
  cte l5 =
    Distinct project=[#0] // { arity: 1 }
      Get l4 // { arity: 2 }
  cte l6 =
    Project (#0, #2) // { arity: 2 }
      Join on=(#0 = #1) // { arity: 3 }
        Get l5 // { arity: 1 }
        Union // { arity: 2 }
          Get l2 // { arity: 2 }
          CrossJoin // { arity: 2 }
            Project (#0) // { arity: 1 }
              Join on=(#0 = #1) // { arity: 2 }
                Union // { arity: 1 }
                  Negate // { arity: 1 }
                    Distinct project=[#0] // { arity: 1 }
                      Get l2 // { arity: 2 }
                  Distinct project=[#0] // { arity: 1 }
                    Get l1 // { arity: 1 }
                Get l1 // { arity: 1 }
            Constant // { arity: 1 }
              - (null)
  cte l7 =
    Union // { arity: 2 }
      Get l6 // { arity: 2 }
      Project (#0, #2) // { arity: 2 }
        FlatMap guard_subquery_size(#1) // { arity: 3 }
          Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
            Get l6 // { arity: 2 }
Return // { arity: 3 }
  Project (#0, #2, #3) // { arity: 3 }
    Join on=(#0 = #1) // { arity: 4 }
      Get l0 // { arity: 1 }
      Project (#0, #1, #3) // { arity: 3 }
        Join on=(#1 = #2) // { arity: 4 }
          Get l3 // { arity: 2 }
          Project (#0, #2) // { arity: 2 }
            Map (#0{a}) // { arity: 3 }
              Project (#0, #1) // { arity: 2 }
                Filter (#2 > 0) // { arity: 3 }
                  Project (#0, #1, #3) // { arity: 3 }
                    Join on=(#0 = #2) // { arity: 4 }
                      Get l4 // { arity: 2 }
                      Union // { arity: 2 }
                        Get l7 // { arity: 2 }
                        CrossJoin // { arity: 2 }
                          Project (#0) // { arity: 1 }
                            Join on=(#0 = #1) // { arity: 2 }
                              Union // { arity: 1 }
                                Negate // { arity: 1 }
                                  Distinct project=[#0] // { arity: 1 }
                                    Get l7 // { arity: 2 }
                                Distinct project=[#0] // { arity: 1 }
                                  Get l5 // { arity: 1 }
                              Get l5 // { arity: 1 }
                          Constant // { arity: 1 }
                            - (null)

Target cluster: quickstart

EOF

# Check that CTEs are annotated with their names
query T multiline
EXPLAIN RAW PLAN FOR
WITH a(a) AS (SELECT a FROM y),
     b(b) AS (SELECT a FROM y),
     x(x) AS (SELECT b FROM b)
SELECT (WITH c(c) AS (SELECT a FROM y)
        SELECT c FROM c where (WITH d(d) AS (SELECT c FROM c)
                               SELECT max(d) FROM d) > 1)
FROM (WITH e(e) AS (SELECT b FROM b)
      SELECT e FROM e where (WITH f(f) AS (SELECT e FROM e)
                             SELECT min(f) FROM f)
                             < (SELECT max(x) FROM x))
----
Project (#1)
  With
    cte [l0 as a] =
      Get materialize.public.y
    cte [l1 as b] =
      Get materialize.public.y
    cte [l2 as x] =
      Get l1
    cte [l8 as subquery-8] =
      With
        cte [l3 as c] =
          Get materialize.public.y
        cte [l5 as subquery-5] =
          With
            cte [l4 as d] =
              Get l3
          Return
            Reduce aggregates=[max(#0{d})]
              Get l4
      Return
        Filter (select(Get l5) > 1)
          Get l3
  Return
    Map (select(Get l8))
      With
        cte [l3 as e] =
          Get l1
        cte [l7 as subquery-7] =
          Reduce aggregates=[max(#0{x})]
            Get l2
        cte [l6 as subquery-6] =
          With
            cte [l4 as f] =
              Get l3
          Return
            Reduce aggregates=[min(#0{f})]
              Get l4
      Return
        Filter (select(Get l6) < select(Get l7))
          Get l3

Target cluster: quickstart

EOF

# CTEs with the same name in nested context
query T multiline
EXPLAIN RAW PLAN FOR
WITH a(a) AS (SELECT a FROM y) SELECT * FROM (WITH a(a) AS (SELECT a FROM a) SELECT a FROM a);
----
With
  cte [l0 as a] =
    Get materialize.public.y
  cte [l1 as a] =
    Get l0
Return
  Get l1

Target cluster: quickstart

EOF