# 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_1209.md mode cockroach statement ok CREATE TABLE input (input TEXT); # no data query T multiline EXPLAIN OPTIMIZED PLAN WITH(humanized expressions, arity, join implementations) AS VERBOSE TEXT FOR WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 30) lines (line TEXT, line_no INT) AS ( SELECT regexp_split_to_array(input, '\n')[i], i FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i ), numbers(value INT, line_no INT, col_no INT) AS ( SELECT regexp_split_to_array(line, ' ')[j]::INT, line_no, j FROM lines, generate_series(1, array_length(regexp_split_to_array(line, ' '), 1)) j ), -- Contains non-zero values of differences after each round. derivatives(value INT, line_no INT, col_no INT, round INT) AS ( SELECT numbers.*, 1 FROM numbers UNION SELECT COALESCE(i2.value, 0) - COALESCE(i1.value, 0), COALESCE(i1.line_no, i2.line_no), COALESCE(i1.col_no + 1, i2.col_no), COALESCE(i1.round, i2.round) + 1 FROM derivatives i1 FULL OUTER JOIN derivatives i2 ON (i1.line_no = i2.line_no AND i1.round = i2.round AND i1.col_no + 1 = i2.col_no) WHERE COALESCE(i2.value, 0) - COALESCE(i1.value, 0) != 0 AND COALESCE(i1.col_no + 1, i2.col_no) > COALESCE(i1.round, i2.round) AND COALESCE(i1.col_no + 1, i2.col_no) <= 21 ), -- Accumulate the derivatives at the leading edge part1(part1 BIGINT) AS ( SELECT SUM(value) FROM derivatives WHERE col_no = 21 ), -- Accumulate the derivatives at the preceding edge part2(part2 BIGINT) AS ( SELECT SUM(pow(-1, round + 1) * value) FROM derivatives WHERE col_no = round ) -- SELECT * FROM derivatives WHERE line_no = 1 ORDER BY round, col_no; SELECT * FROM part1, part2; ---- Explained Query: With Mutually Recursive cte l0 = Map ((#2{col_no} + 1)) // { arity: 5 } Get l3 // { arity: 4 } cte l1 = Project (#0..=#4, #6) // { arity: 6 } Join on=(#1{line_no} = #5{line_no} AND #3{round} = #7{round} AND #6{col_no} = (#2{col_no} + 1)) type=differential // { arity: 8 } implementation %0:l0[#1{line_no}, (#2{col_no} + 1), #3{round}]KKKif » %1:l3[#1{line_no}..=#3{round}]KKKiif ArrangeBy keys=[[#1{line_no}, (#2{col_no} + 1), #3{round}]] // { arity: 4 } Project (#0..=#3) // { arity: 4 } Filter (#4 <= 21) AND (#1{line_no}) IS NOT NULL AND (#4 > #3{round}) // { arity: 5 } Get l0 // { arity: 5 } ArrangeBy keys=[[#1{line_no}..=#3{round}]] // { arity: 4 } Filter (#2{col_no} <= 21) AND (#1{line_no}) IS NOT NULL AND (#2{col_no} > #3{round}) // { arity: 4 } Get l3 // { arity: 4 } cte l2 = Distinct project=[#0..=#2] // { arity: 3 } Project (#1, #3, #5) // { arity: 3 } Get l1 // { arity: 6 } cte [recursion_limit=30, return_at_limit] l3 = Distinct project=[#0..=#3] // { arity: 4 } Union // { arity: 4 } Project (#3, #0, #2, #4) // { arity: 4 } Map (text_to_integer(array_index(regexp_split_to_array[" ", case_insensitive=false](#1{line}), integer_to_bigint(#2{j}))), 1) // { arity: 5 } FlatMap generate_series(1, (regexp_split_to_array[" ", case_insensitive=false](#1{line}) array_length 1), 1) // { arity: 3 } Project (#1, #2) // { arity: 2 } Map (array_index(regexp_split_to_array["\n", case_insensitive=false](#0{input}), integer_to_bigint(#1{i}))) // { 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 } Project (#8..=#11) // { arity: 4 } Map ((coalesce(#4{value}, 0) - coalesce(#0{value}, 0)), coalesce(#1{line_no}, #5{line_no}), coalesce((#2{col_no} + 1), #6{col_no}), (coalesce(#3{round}, #7{round}) + 1)) // { arity: 12 } Union // { arity: 8 } Project (#4..=#7, #0..=#3) // { arity: 8 } Map (null, null, null, null) // { arity: 8 } Union // { arity: 4 } Negate // { arity: 4 } Project (#0..=#3) // { arity: 4 } Join on=(#1{line_no} = #4 AND #2{col_no} = #6 AND #3{round} = #5) type=differential // { arity: 7 } implementation %1:l2[#0, #2, #1]UKKK » %0:l3[#1{line_no}..=#3{round}]KKKif ArrangeBy keys=[[#1{line_no}..=#3{round}]] // { arity: 4 } Filter (#2{col_no} <= 21) AND (#1{line_no}) IS NOT NULL AND (#2{col_no} > #3{round}) AND (0 != (coalesce(#0{value}, 0) - 0)) // { arity: 4 } Get l3 // { arity: 4 } ArrangeBy keys=[[#0, #2, #1]] // { arity: 3 } Get l2 // { arity: 3 } Filter (#2{col_no} <= 21) AND (#2{col_no} > #3{round}) AND (0 != (coalesce(#0{value}, 0) - 0)) // { arity: 4 } Get l3 // { arity: 4 } Map (null, null, null, null) // { arity: 8 } Union // { arity: 4 } Negate // { arity: 4 } Project (#0..=#3) // { arity: 4 } Join on=(#1{line_no} = #4 AND #3{round} = #5 AND #6 = (#2{col_no} + 1)) type=differential // { arity: 7 } implementation %1:l2[#0..=#2]UKKK » %0:l0[#1{line_no}, #3{round}, (#2{col_no} + 1)]KKKif ArrangeBy keys=[[#1{line_no}, #3{round}, (#2{col_no} + 1)]] // { arity: 4 } Project (#0..=#3) // { arity: 4 } Filter (#4 <= 21) AND (#1{line_no}) IS NOT NULL AND (#4 > #3{round}) AND (0 != (0 - coalesce(#0{value}, 0))) // { arity: 5 } Get l0 // { arity: 5 } ArrangeBy keys=[[#0..=#2]] // { arity: 3 } Get l2 // { arity: 3 } Project (#0..=#3) // { arity: 4 } Filter (#4 <= 21) AND (#4 > #3{round}) AND (0 != (0 - coalesce(#0{value}, 0))) // { arity: 5 } Get l0 // { arity: 5 } Project (#0..=#4, #1, #5, #3) // { arity: 8 } Filter (0 != (coalesce(#4{value}, 0) - coalesce(#0{value}, 0))) // { arity: 6 } Get l1 // { arity: 6 } Return // { arity: 2 } With cte l4 = Reduce aggregates=[sum(#0{value})] // { arity: 1 } Project (#0) // { arity: 1 } Filter (#2{col_no} = 21) // { arity: 4 } Get l3 // { arity: 4 } cte l5 = Reduce aggregates=[sum((power(-1, integer_to_double((#1{col_no} + 1))) * integer_to_double(#0{value})))] // { arity: 1 } Project (#0, #2) // { arity: 2 } Filter (#2{col_no} = #3{round}) // { arity: 4 } Get l3 // { arity: 4 } Return // { arity: 2 } CrossJoin type=differential // { arity: 2 } implementation %0[×]U » %1[×]U 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 } Project (#1) // { arity: 1 } Map (f64toi64(#0{sum})) // { arity: 2 } Union // { arity: 1 } Get l5 // { arity: 1 } Map (null) // { arity: 1 } Union // { arity: 0 } Negate // { arity: 0 } Project () // { arity: 0 } Get l5 // { arity: 1 } Constant // { arity: 0 } - () Source materialize.public.input Target cluster: quickstart EOF