Materialize/test/sqllogictest/advent-of-code/2023/aoc_1225.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.

# https://github.com/MaterializeInc/advent-of-code-2023/blob/main/week1/aoc_1225.md

mode cockroach

statement ok
CREATE TABLE input (input TEXT);

statement ok
INSERT INTO input VALUES (
'tls: ssh
ssh: ftp ssr sso
ftp: rgb mkd sso
ssr: dos htd
sso: lll pxp
rgb: zbz vmz htd
htd: jln
mkd: mmx');

query I
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 50)

    lines(r INT, line TEXT) AS (
        SELECT r, regexp_split_to_array(input, '\n')[r] as line
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) r
    ),

    edges(src TEXT, dst TEXT) AS (
        SELECT
            trim(':' FROM regexp_split_to_array(line, ' ')[1]),
            trim(',' FROM regexp_split_to_array(line, ' ')[x])
        FROM
            lines, generate_series(2, array_length(regexp_split_to_array(line, ' '), 1)) x
    ),

    symm(src TEXT, dst TEXT) AS (
        SELECT src, dst FROM edges
        UNION ALL
        SELECT dst, src FROM edges
    ),

    init(src TEXT, val NUMERIC) AS (
        SELECT src, CASE WHEN src < 'n' THEN 1.0 ELSE -1.0 END
        FROM (SELECT src FROM edges UNION ALL SELECT dst FROM edges)
    ),
    -- determine the second eigenvector of the adjacency matrix
    weight(src TEXT, val NUMERIC) AS (
        SELECT * FROM init
        EXCEPT ALL
        SELECT * FROM init_delayed
        UNION ALL
        SELECT symm.src, SUM((val - (SELECT AVG(val) FROM weight))/(SELECT STDDEV(val) FROM weight))
        FROM symm, weight
        WHERE symm.dst = weight.src
        GROUP BY symm.src
    ),

    init_delayed(src TEXT, val NUMERIC) AS ( SELECT * FROM init ),

    part1(part1 BIGINT) AS (
        SELECT
            (SELECT COUNT(*) FROM weight WHERE val < 0.0) *
            (SELECT COUNT(*) FROM weight WHERE val > 0.0)
    ),

    potato(x INT) AS ( SELECT 1 )

SELECT * FROM part1;
----
54

query T multiline
EXPLAIN OPTIMIZED PLAN WITH(humanized expressions, arity, join implementations) AS VERBOSE TEXT FOR
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 50)

    lines(r INT, line TEXT) AS (
        SELECT r, regexp_split_to_array(input, '\n')[r] as line
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) r
    ),

    edges(src TEXT, dst TEXT) AS (
        SELECT
            trim(':' FROM regexp_split_to_array(line, ' ')[1]),
            trim(',' FROM regexp_split_to_array(line, ' ')[x])
        FROM
            lines, generate_series(2, array_length(regexp_split_to_array(line, ' '), 1)) x
    ),

    symm(src TEXT, dst TEXT) AS (
        SELECT src, dst FROM edges
        UNION ALL
        SELECT dst, src FROM edges
    ),

    init(src TEXT, val NUMERIC) AS (
        SELECT src, CASE WHEN src < 'n' THEN 1.0 ELSE -1.0 END
        FROM (SELECT src FROM edges UNION ALL SELECT dst FROM edges)
    ),
    -- determine the second eigenvector of the adjacency matrix
    weight(src TEXT, val NUMERIC) AS (
        SELECT * FROM init
        EXCEPT ALL
        SELECT * FROM init_delayed
        UNION ALL
        SELECT symm.src, SUM((val - (SELECT AVG(val) FROM weight))/(SELECT STDDEV(val) FROM weight))
        FROM symm, weight
        WHERE symm.dst = weight.src
        GROUP BY symm.src
    ),

    init_delayed(src TEXT, val NUMERIC) AS ( SELECT * FROM init ),

    part1(part1 BIGINT) AS (
        SELECT
            (SELECT COUNT(*) FROM weight WHERE val < 0.0) *
            (SELECT COUNT(*) FROM weight WHERE val > 0.0)
    ),

    potato(x INT) AS ( SELECT 1 )

SELECT * FROM part1;
----
Explained Query:
  With
    cte l0 =
      Project (#3, #4) // { arity: 2 }
        Map (regexp_split_to_array[" ", case_insensitive=false](#0{line}), btrim(array_index(#2, 1), ":"), btrim(array_index(#2, integer_to_bigint(#1{x})), ",")) // { arity: 5 }
          FlatMap generate_series(2, (regexp_split_to_array[" ", case_insensitive=false](#0{line}) array_length 1), 1) // { arity: 2 }
            Project (#2) // { arity: 1 }
              Map (array_index(regexp_split_to_array["\n", case_insensitive=false](#0{input}), integer_to_bigint(#1{r}))) // { arity: 3 }
                FlatMap generate_series(1, (regexp_split_to_array["\n", case_insensitive=false](#0{input}) array_length 1), 1) // { arity: 2 }
                  ReadStorage materialize.public.input // { arity: 1 }
    cte l1 =
      Map (case when (#0{src} < "n") then 1 else -1 end) // { arity: 2 }
        Union // { arity: 1 }
          Project (#0) // { arity: 1 }
            Get l0 // { arity: 2 }
          Project (#1) // { arity: 1 }
            Get l0 // { arity: 2 }
  Return // { arity: 1 }
    With Mutually Recursive
      cte l2 =
        Project (#1{sum}) // { arity: 1 }
          Get l7 // { arity: 2 }
      cte l3 =
        Reduce aggregates=[sum(#0{val}), count(#0{val})] // { arity: 2 }
          Get l2 // { arity: 1 }
      cte l4 =
        Project (#2) // { arity: 1 }
          Map ((#0{sum} / bigint_to_numeric(case when (#1{count} = 0) then null else #1{count} end))) // { arity: 3 }
            Union // { arity: 2 }
              Get l3 // { arity: 2 }
              Map (null, 0) // { arity: 2 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l3 // { arity: 2 }
                  Constant // { arity: 0 }
                    - ()
      cte l5 =
        Reduce aggregates=[sum((#0{val} * #0{val})), sum(#0{val}), count(#0{val})] // { arity: 3 }
          Get l2 // { arity: 1 }
      cte l6 =
        Project (#3) // { arity: 1 }
          Map (sqrtnumeric(case when ((#0{sum}) IS NULL OR (#1{sum}) IS NULL OR (case when (#2{count} = 0) then null else #2{count} end) IS NULL OR (case when (0 = (#2{count} - 1)) then null else (#2{count} - 1) end) IS NULL) then null else greatest(((#0{sum} - ((#1{sum} * #1{sum}) / bigint_to_numeric(case when (#2{count} = 0) then null else #2{count} end))) / bigint_to_numeric(case when (0 = (#2{count} - 1)) then null else (#2{count} - 1) end)), 0) end)) // { arity: 4 }
            Union // { arity: 3 }
              Get l5 // { arity: 3 }
              Map (null, null, 0) // { arity: 3 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l5 // { arity: 3 }
                  Constant // { arity: 0 }
                    - ()
      cte [recursion_limit=50, return_at_limit] l7 =
        Union // { arity: 2 }
          Threshold // { arity: 2 }
            Union // { arity: 2 }
              Get l1 // { arity: 2 }
              Negate // { arity: 2 }
                Get l8 // { arity: 2 }
          Reduce group_by=[#0] aggregates=[sum(((#1{val} - #2) / #3))] // { arity: 2 }
            Project (#0, #3..=#5) // { arity: 4 }
              Join on=(#1{dst} = #2{src}) type=delta // { arity: 6 }
                implementation
                  %0 » %2[×]U » %3[×]U » %1:l7[#0{src}]K
                  %1:l7 » %2[×]U » %3[×]U » %0[#1{dst}]K
                  %2 » %3[×]U » %0[×] » %1:l7[#0{src}]K
                  %3 » %2[×]U » %0[×] » %1:l7[#0{src}]K
                ArrangeBy keys=[[], [#1{dst}]] // { arity: 2 }
                  Union // { arity: 2 }
                    Filter (#1{dst}) IS NOT NULL // { arity: 2 }
                      Get l0 // { arity: 2 }
                    Project (#1, #0) // { arity: 2 }
                      Filter (#0{dst}) IS NOT NULL // { arity: 2 }
                        Get l0 // { arity: 2 }
                ArrangeBy keys=[[#0{src}]] // { arity: 2 }
                  Filter (#0{src}) IS NOT NULL // { arity: 2 }
                    Get l7 // { arity: 2 }
                ArrangeBy keys=[[]] // { arity: 1 }
                  Union // { arity: 1 }
                    Get l4 // { arity: 1 }
                    Map (null) // { arity: 1 }
                      Union // { arity: 0 }
                        Negate // { arity: 0 }
                          Project () // { arity: 0 }
                            Get l4 // { arity: 1 }
                        Constant // { arity: 0 }
                          - ()
                ArrangeBy keys=[[]] // { arity: 1 }
                  Union // { arity: 1 }
                    Get l6 // { arity: 1 }
                    Map (null) // { arity: 1 }
                      Union // { arity: 0 }
                        Negate // { arity: 0 }
                          Project () // { arity: 0 }
                            Get l6 // { arity: 1 }
                        Constant // { arity: 0 }
                          - ()
      cte [recursion_limit=50, return_at_limit] l8 =
        Get l1 // { arity: 2 }
    Return // { arity: 1 }
      With
        cte l9 =
          Reduce aggregates=[count(*)] // { arity: 1 }
            Project () // { arity: 0 }
              Filter (#1{sum} < 0) // { arity: 2 }
                Get l7 // { arity: 2 }
        cte l10 =
          Union // { arity: 1 }
            Get l9 // { arity: 1 }
            Map (0) // { arity: 1 }
              Union // { arity: 0 }
                Negate // { arity: 0 }
                  Project () // { arity: 0 }
                    Get l9 // { arity: 1 }
                Constant // { arity: 0 }
                  - ()
        cte l11 =
          Reduce aggregates=[count(*)] // { arity: 1 }
            Project () // { arity: 0 }
              Filter (#1{sum} > 0) // { arity: 2 }
                Get l7 // { arity: 2 }
        cte l12 =
          Union // { arity: 1 }
            Get l11 // { arity: 1 }
            Map (0) // { arity: 1 }
              Union // { arity: 0 }
                Negate // { arity: 0 }
                  Project () // { arity: 0 }
                    Get l11 // { arity: 1 }
                Constant // { arity: 0 }
                  - ()
      Return // { arity: 1 }
        Project (#2) // { arity: 1 }
          Map ((#0{count} * #1{count})) // { arity: 3 }
            CrossJoin type=differential // { arity: 2 }
              implementation
                %0[×]U » %1[×]U
              ArrangeBy keys=[[]] // { arity: 1 }
                Union // { arity: 1 }
                  Get l10 // { arity: 1 }
                  Map (null) // { arity: 1 }
                    Union // { arity: 0 }
                      Negate // { arity: 0 }
                        Project () // { arity: 0 }
                          Get l10 // { arity: 1 }
                      Constant // { arity: 0 }
                        - ()
              ArrangeBy keys=[[]] // { arity: 1 }
                Union // { arity: 1 }
                  Get l12 // { arity: 1 }
                  Map (null) // { arity: 1 }
                    Union // { arity: 0 }
                      Negate // { arity: 0 }
                        Project () // { arity: 0 }
                          Get l12 // { arity: 1 }
                      Constant // { arity: 0 }
                        - ()

Source materialize.public.input

Target cluster: quickstart

EOF