今年我们为 Advent of Code 做了一些奇怪的事情：我们在 javascript 和 PostgreSQL 中解决了一些挑战。我们学到了一些关于 SQL 的有趣的东西，我们想在这里分享。
免责声明：我们没有完成 25 天的 SQL -专家。如果你是专家，你可能在这里学不到任何东西。
窗口函数范围很棒
首先，快速复习一下窗口函数：您可能知道窗口函数在一组与当前行有某种关联的表行上执行计算。Postgres 文档中的示例是计算特定员工的部门特定平均工资。SQL 如下所示：
SELECT depname, empno, salary, avg(salary) OVER (PARTITION BY depname) FROM empsalary;
|
在上面的示例中，所考虑的行的“窗口”是其部门与当前行的部门匹配的所有行，但是在处理挑战时，我们了解到也可以使用范围定义窗口。
例如，在第 1 天，我们被要求计算三个元素的滑动窗口中值的总和增加的次数。您可以使用窗口函数Ranges范围表示三个元素的滑动窗口之和。SQL 如下所示：
SELECT row_number, sum(value) OVER (ORDER BY row_number RANGE BETWEEN CURRENT ROW AND 2 FOLLOWING) AS value
FROM input_with_rows
|
整体解决方案如下所示：
WITH input_with_rows AS (
SELECT row_number() over () AS row_number, value
FROM day1_input
),
windows AS (
SELECT row_number, sum(value) OVER (ORDER BY row_number RANGE BETWEEN CURRENT ROW AND 2 FOLLOWING) AS value
FROM input_with_rows
),
lagged AS (
SELECT row_number, lag(value) OVER () AS value
FROM windows
)
SELECT count(*)
FROM windows
JOIN lagged ON (windows.row_number = lagged.row_number AND lagged.value < windows.value);
|
范围Ranges只是冰山一角。还有许多其他定义窗口的方法。查看Postgres 文档的这个页面了解更多信息。
用于可读性和迭代的通用表表达式
公用表表达式或 CTE 是通过简单查询表达式创建的临时、范围和别名表。在大多数情况下，子查询可以达到相同的结果，尽管子查询在教科书和数据库文档中比 CTE 更常见，但我们发现使用 CTE 而不是子查询消除了大量的嵌套。
有很多资源可以解释为什么深度嵌套的代码是一种代码异味。嵌套很快就会变得难以推理。当读者必须跳来跳去以获取上下文时，遵循执行流程会增加额外的认知负担。CTE 是顺序的，我们人类更容易遵循顺序步骤。
RECURSIVE使用 CTE 的另一个优点是，如果您使用关键字，它们可以引用自己的输出。文档建议使用递归 CTE 来处理任意嵌套的分层数据，但它们也可以用于迭代。
我们在第 3 天的工作中学习了如何使用 CTE 进行迭代。在第二部分，我们被要求：
- 从二进制数列表开始，只考虑这些数字的第一位。
- 丢弃第一位与所有剩余数字的第一位位置中最常见位不匹配的数字
- 如果您只剩下一个号码，请停止；这是您正在寻找的价值
- 否则，重复该过程，考虑右边的下一位。
用于此的 SQL 如下。我们使用递归 CTE 的有趣部分是第 14 - 40 行：
\copy day3_input FROM 'day3.txt';
WITH bits_with_row_number AS (
SELECT row_number() over () AS row_number,
regexp_split_to_array(bits, '') AS bits
FROM day3_input
),
bits_with_column_number AS (
SELECT *, row_number() over (partition by row_number) AS col_number
FROM bits_with_row_number
),
recurse AS (
WITH RECURSIVE filter AS (
(WITH target_bit AS (SELECT bits,
CASE
WHEN (sum(bits[1]::integer) OVER ()) < ((count(*) OVER ())::float / 2) THEN 0
ELSE 1 END AS o2,
CASE
WHEN (sum(bits[1]::integer) OVER ()) < ((count(*) OVER ())::float / 2) THEN 1
ELSE 0 END AS co2
FROM bits_with_column_number)
SELECT *, 1 AS i
FROM target_bit
WHERE bits[1]::integer = co2
)
UNION ALL
(WITH target_bit AS (SELECT bits,
i,
CASE
WHEN sum(bits[i + 1]::integer) OVER () < ((count(*) OVER ())::float / 2) THEN 0
ELSE 1 END AS o2,
CASE
WHEN sum(bits[i + 1]::integer) OVER () < ((count(*) OVER ())::float / 2) THEN 1
ELSE 0 END AS co2
FROM filter)
SELECT bits, o2, co2, i + 1 AS i
FROM target_bit
WHERE bits[i + 1]::integer = target_bit.co2)
)
SELECT *
FROM filter
)
SELECT *
FROM recurse
WHERE i = (SELECT max(i) FROM recurse);
|
关于递归 CTE 的工作原理有很多 很好[url=https://www.citusdata.com/blog/2018/05/15/fun-with-sql-recursive-ctes/]的[/url] 解释，所以我们不会在这里重复这些解释。
如何进行关联而不是迭代思考
在第 4 天，我们得到了一个数字列表和一个bingo boards ，我们被要求找出哪个bingo boards首先获胜。当我们开始编写 SQL 部分时，我们假设我们需要使用递归 CTE 以便我们可以迭代boards ，但是在 SQL 中解决问题的练习帮助我们从新的角度看待问题。我们了解到，仅仅因为问题陈述中存在迭代方面并不意味着我们不能将其抽象掉。
将问题分解成更小的部分让我们看到了另一种方式。我们需要找到第一个获胜的boards ，但这意味着什么？好吧，首先，我们需要考虑winning board会如何获胜。当一列或一行中的所有数字都被调用时，一个board获胜。因此，我们需要找出每一列和每一行的获胜时间。
以这种方式分解它让我们看到这是一个排序问题。我们已经知道号码被调用的顺序。您可以使用号码顺序为每一列和每一行分配一个“时间”，代表该列或行获胜的时间。然后我们只需找到每个板的那个时间的最小值。一旦你有了它，你就知道winning board会什么时候赢了。然后你按照他们获胜的时间对boards 进行排序，你就有了答案！
WITH boards_ordered_with_call_order AS (
SELECT *
FROM boards_ordered
JOIN called_numbers_with_row
ON called_numbers_with_row.called_number = boards_ordered.value
),
col_win_orders AS (
SELECT board_no, col_number, max(call_order) AS max_col_call_order
FROM boards_ordered_with_call_order
GROUP BY board_no, col_number
),
row_win_orders AS (
SELECT board_no, row_number, max(call_order) AS max_row_call_order
FROM boards_ordered_with_call_order
GROUP BY board_no, row_number
),
row_and_col_win_orders AS (
SELECT *
FROM col_win_orders
JOIN row_win_orders
USING (board_no)
ORDER BY board_no, row_number, col_number
),
winning_boards AS (
SELECT board_no,
min(LEAST(max_col_call_order, max_row_call_order)) AS winning_call_number
FROM row_and_col_win_orders
GROUP BY board_no
ORDER BY 2
LIMIT 1
),
last_called_number AS (
SELECT min(called_numbers_with_row.called_number) AS number
FROM winning_boards
JOIN called_numbers_with_row ON (called_numbers_with_row.call_order = winning_call_number)
)
SELECT board_no, sum(value::integer * called_numbers_with_row.called_number::integer)
FROM boards_ordered_with_call_order
JOIN winning_boards USING (board_no)
JOIN called_numbers_with_row ON called_numbers_with_row.call_order = winning_call_number
WHERE boards_ordered_with_call_order.call_order > winning_call_number
GROUP BY 1
|
这个练习是向我们的算法工具箱添加其他工具的好方法。
SQL 出奇的紧凑
在用 SQL 重写我们的 javascript 解决方案时，我们对用 SQL 表达解决方案的紧凑性和安全性感到震惊。例如，一个挑战要求您在潜艇执行一系列上下前进命令后计算它的位置（如果您真的想知道问题的细节，这是第 2 天，第 1 部分）。这是javascript中的解决方案：
let depth = 0;
let horizontal = 0;
instructions.forEach(({ direction, distance})=> {
switch (direction) {
case "up":
depth -= distance;
break;
case "down":
depth += distance;
break;
case "forward":
horizontal += distance;
break;
}
})
console.log(depth * horizontal);
|
这是 SQL 中的相同解决方案：
SELECT sum(distance) FILTER ( WHERE direction = 'forward' ) *
(- sum(distance) FILTER ( WHERE direction = 'up' ) +
sum(distance) FILTER ( WHERE direction = 'down' )) AS position
FROM day2_input
|
SQL 实际上在这里看起来比 javascript 解决方案更具声明性和紧凑性。我们预计我的几乎所有 SQL 解决方案都会很笨拙，但惊喜地发现它在这个问题和其他情况下都非常优雅。