通过延续传递数据库

# CPS 来源：https://remy.wang/blog/cps.html ## 将数据库通过续延传递 *本文献给米诺布鲁克分析推理研讨会 (https://events.syracuse.edu/event/minnowbrook-analytic-reasoning-seminar)，特别感谢 Kris Micinski (https://kmicinski.com/) 和 Michael Ballantyne (https://mballantyne.net/)* 假设你想编写一个数据库。你可能会从实现关系代数算子开始——投影、过滤、连接等等。简单的方法是将它们实现为接受表并返回表的函数，然后将它们组合成更大的表达式。这就是 Prela (https://prela-lang.org/) 最初版本的工作方式。代码很简洁，但速度慢得惊人！这并不奇怪，因为每个算子都会物化每一个中间结果。标准的解决方案是迭代器模型 (https://cs-people.bu.edu/mathan/reading-groups/papers-classics/volcano.pdf)，其中每个算子实现一个 *Iterator* 接口，逐行流式传输中间表，而不是物化它们。但天真地实现迭代器模型仍然会产生开销：每次调用 `Iterator.next()` 都会触发动态分发，导致虚表查找并破坏缓存局部性。有两种标准的补救措施：向量化和编译 (https://www.vldb.org/pvldb/vol11/p2209-kersten.pdf)。向量化数据库通过实现 `Iterator.next_batch()` 来分摊开销，该函数返回可以一起处理的整个批次数据；编译数据库则将传入的查询直接编译成快速机器码，无需任何动态分发。这两种方法都需要大量非常聪明的人投入整个职业生涯来构建，这就是 DuckDB 和 Umbra 等系统存在的原因。我算是中等聪明，但没有太多时间，所以我在寻找一条捷径。我偶然发现的捷径 (https://dl.acm.org/doi/10.1145/165180.165214) 如此美丽，以至于当我终于理解它时，我 literally cried1 (https://remy.wang/blog/cps.html#fn1)，我希望我下面的解释也能让你哭 :') 为了简单起见，我们假设只处理数字列表，并且只做两件非常简单的事情：`inc` 将每个数字加 1，`dbl` 将每个数字加倍。这写起来很容易：2 (https://remy.wang/blog/cps.html#fn2) ``` inc(xs) = [x + 1 for x in xs] dbl(xs) = [2 * x for x in xs] ``` 现在，我们可以通过 `dbl(inc(xs))` 将它们链式组合，这将按顺序执行两个步骤。问题是，因为每个函数接受一个列表并返回一个列表，我们的程序会产生一个 *中间结果*，即 `inc(xs)`。这会分配一个新列表，然后立即被 `dbl` 的调用丢弃。当我们将多个 `inc` 和 `dbl` 调用链式组合时，情况只会更糟。一种更高效的实现会将操作 *融合* 在一起： ``` inc_n_dbl(xs) = [2 * (x + 1) for x in xs] ``` 当然，我们不可能像这样写下每一种可能的算子组合。有没有一种方法可以模块化地定义每个算子，同时又让它们自动组合成紧密融合的操作呢？是的，如果我们使用一些函数式编译器的魔法——续延传递风格（CPS）。 CPS 的关键思想是定义 *执行* 某些事情的算子，而不是 *制造* 某些东西。上面定义的 `inc` 和 `dbl` 各自接受一个列表并 *制造* 一个列表。相反，每个算子的 CPS 版本接受一个列表和一个额外的输入 `k`：这个 `k` 是由调用者传入的函数，指定了在算子工作完成后，调用者希望如何处理每个元素。`k` 被称为 *续延*。让我们看一些代码： ``` function inc(xs, k) for x in xs k(x + 1) end end ``` 现在假设 `k` 是 `print` 函数，那么上面定义的 `inc` 会将每个数字加 1，然后打印结果。注意没有返回任何东西，`inc` 只完成它的工作（加 1），然后执行它被告知的操作（应用 `k`）。作为练习，你可以尝试用 CPS 风格写出 `dbl`。 但目前，`inc` 和 `dbl` 各自仍然接受一个列表，并且没有明显的方法来组合多个算子。为此，我们将 `xs` 替换为一个“子”算子 `op`： ``` inc(op, k) = op(x -> k(x + 1)) dbl(op, k) = op(x -> k(x * 2)) function scan(xs, k) for x in xs k(x) end end ``` 直观地说，`inc` 现在信任它的子算子 `op` 来完成其工作，即 `op` 会将收到的续延应用于每个元素。因此，`inc` 不再迭代 `xs`，而只是将 `+1` 步骤附加到续延上，然后将它传递给 `op`。我还定义了一个“源”算子 `scan`，用于连接输入列表和算子。让我们看看代码的实际运行。 1. 首先调用 `inc(scan(xs), print)`。3 (https://remy.wang/blog/cps.html#fn3) 2. 根据 `inc` 的定义，这将调用 `scan(xs, x -> print(x + 1))` 3. 代入 `scan` 的定义，得到 `for x in xs; print(x + 1); end` 所以将 `inc` 和 `scan` 链式组合确实满足我们的需求！现在让我们尝试一个更长的链 `dbl(inc(scan(xs)), print)`： 1. 展开 `dbl` 得到 `inc(scan(xs), x -> print(x * 2))` 2. 展开 `inc` 得到 `scan(xs, x -> print((x + 1) * 2))` 3. 最后，展开 `scan` 得到 `for x in xs; print((x + 1) * 2); end` 注意我使用了“展开”这个词——如果我们给每个算子定义加上 `@inline` 注解，编译器实际上会像上面那样展开代码，最终一个算子链会被编译成一个融合的循环！你可以尝试展开更长的链，比如 `dbl(inc(dbl(inc(scan(xs)))), print)`，以练习思考 CPS。Julia 也提供了方便的工具，比如 `@code_typed` 让你检查编译后的代码，或者名副其实的 Cthulhu.jl (https://github.com/JuliaDebug/Cthulhu.jl) 以交互方式进行。总之，这个例子说明，如果我们用 CPS 模块化地定义算子，内联这些定义将自动产生紧密融合的编译代码。 这些都不是全新的概念，函数式程序员几十年来已经知道它们，名为 deforestation (https://en.wikipedia.org/wiki/Deforestation_(computer_science))。但当在 Prela 中实现时，发生了一些不可思议的事情：*一个干净的 CPS 风格的 Prela 解释器，在编译时自动恢复了快速的列式执行！* Prela 背后的核心设计原则是“一切都是 *二元* 关系”。这意味着 Prela 能够干净地映射到逻辑上的实体/关系数据模型，以及列式物理存储。我不会在这里详述，但鼓励你尝试使用该语言来感受这一点。实际上，这意味着我们将所有具有 m 个属性的宽表完全归一化为 m 个二元关系。例如，一个包含列 `ID, year, title` 的表 `movie` 变成了： 1. 身份关系（我称之为 `movie`），关于 `ID`（你可以将其视为关于 `ID` 的一元表） 2. 将每个 `ID` 映射到 `year` 的表 3. 将每个 `ID` 映射到 `title` 的表 但现在的问题是，即使是简单的 `SELECT * FROM movie`，我们也需要连接 3 个不同的表！而列存储只需运行： ``` for i in 0:n print(id_col[i], year_col[i], title_col[i]) end ``` 换句话说，列存储在一趟中对列进行 *协同迭代* 以计算查询。 让我们首先看看 Prela 过去如何运行这个查询。Prela 中最重要的算子是 *关系组合* →，它像关系推广函数一样推广函数组合。在标准关系代数中：R → S = π_{x, z}(R ⋈_{R.y = S.y} S)，其中 R 的模式是 (x, y)，S 的模式是 (y, z)。Prela 中第二重要的算子是 *乘积* ×，它接受两个二元关系并连接它们：R × S = R ⋈_{R.x = S.x} S，其中 R 的模式是 (x, y)，S 的模式是 (x, z)。 因此 `SELECT * FROM movie` 在 Prela 中写成 \text{movie} → \text{year} × \text{title}。现在，这需要首先连接 `year` 和 `title`，然后将结果与 `movie` 连接。如果我们假设主键 `ID` 是密集且连续的，我们可以使其稍微便宜一些，在这种情况下，我们只需将 `year` 存储为整数数组，将 `title` 存储为字符串数组；对于 `ID`，我们只需要存储一个数字 `n`，表示有多少个 ID。但即使这样，我们仍然需要做连接表的工作。 相反，让我们用 CPS 定义 *compose* 和 *product*： ``` compose(lhs, rhs, k) = lhs((x, y) -> rhs(y, (z -> k(x, z)))) product(lhs, rhs, x, k) = lhs(x, (y -> rhs(x, (z -> k((y, z)))))) scan_id(n, k) = for i in 0:n; k(i, i); end probe(col, i, k) = k(col[i]) ``` 让我们仔细分析每一行。从语义上讲，`compose` 应该通过组合 `lhs` 和 `rhs` 关系来返回一个（二元）关系。在 CPS 中，它的工作是将 `k` 应用于组合中的每个对。它的第一个参数 `lhs` 表示一个二元关系，并将给定的续延应用于每个对。`rhs` 略有不同：它表示一个支持 *查找* 的关系，即 `rhs(key, k)` 将查找与 `key` 关联的值，然后将 `k` 应用于每个这样的值。现在回到 `compose`——我们在说，对于 LHS 中的每个 `(x, y)` 元组，我们将从 RHS 中查找 `y`，然后对于每个匹配的 `z`，应用 `k(x, z)`。在循环中，这将是： ``` for (x, y) in lhs for z in rhs[y] k(x, z) end end ``` 这恰好是一个哈希连接和投影丢弃 `y` 的操作。 接下来，`product` 本身是一个支持查找的关系，它的参数也是如此。要在乘积中查找 `x`，我们首先从 `lhs` 中查找它，得到一堆 `y`。然后对于每个 `y`，我们现在从 `rhs` 中查找 `x`，得到一堆 `z`。最后，对于每个 `(y, z)` 对，应用续延 `k((y, z))`。在循环中： ``` for y in lhs[x] for z in rhs[x] k((y, z)) end end ``` 这就是如果你在 R ⋈_{R.x = S.x} S 中查找 `x` 时会发生的事情。 最后，我们有“源”算子 `scan_id` 和 `probe`。`scan_id` 是 `scan` 的特化版本，适用于只存储了 `n` 的密集 ID 关系：它简单地将 `i` 从 0 递增到 `n`，并将 `k` 应用于 `(i, i)`。`probe` 表示一个支持查找主键 `i` 的输入关系，并且由一个密集向量支持，因此查找 ID `i` 只需索引 `col[i]`，并将 `k` 应用于该值。 我们现在准备将所有内容组合在一起并扣动扳机：Prela 查询 \text{movie} → \text{year} × \text{title} 脱糖为 `compose(scan_id(n), product(probe(year), probe(title)))`，其中 `n` 是电影数量。为了参考，这里再次给出定义： ``` compose(lhs, rhs, k) = lhs((x, y) -> rhs(y, (z -> k(x, z)))) product(lhs, rhs, x, k) = lhs(x, (y -> rhs(x, (z -> k((y, z)))))) scan_id(n, k) = for i in 0:n; k(i, i); end probe(col, i, k) = k(col[i]) ``` 1. 展开 `compose`：`` scan_id(n, (x, y) -> product(probe(year), probe(title), y, (z -> k(x, z)))) `` 2. 展开 `scan_id`：`` for i in 0:n product(probe(year), probe(title), i, (z -> k(i, z))) end `` 3. 展开 `product`：`` for i in 0:n probe(year, i, (y -> probe(title, i, (z -> k(i, (y, z)))))) end `` 4. 展开 `probe`：`` for i in 0:n k(i, (year[i], title[i])) end `` 取 `k = print`，我们最终得到： ``` for i in 0:n print(i, (year[i], title[i])) end ``` 太壮观了！！ 为了使示例保持简短，我做了一些简化。实际的 Prela 实现为每个算子定义了 `drive` 和 `probe` 两个方法，根据算子的访问方式（扫描或探查）而触发。但基本上就是这样，完整的源代码是大约 1000 行的单个 Julia 文件，支持 select、project、join、groupby、aggregation、CTE、UDF，并且在 TPCH 和 Join Order Benchmark 上的性能与 DuckDB 相当。我应该指出，性能数字建立在很多假设之上，最强的假设是： - 目前我不关心编译时间，Julia 需要一些时间来 JIT 编译查询 - 引擎积极利用 TPCH 和 JOB 中 PK 是密集的这一事实，这在现实世界中可能成立也可能不成立 尽管如此，CPS 方法清晰地分离了数据引擎的职责——即将查询映射到某种目标语言的高效代码——和编译器的职责——即快速生成快速代码，并且我们看到编译器有很大的改进空间。PK 密集的假设也可以借助 B 树、位图过滤和其他数据结构来放宽。 但 CPS 风格最大的优势或许是它使 Prela 具有 *可扩展性*，因为用户可以用几行代码以自然的方式编写自己的算子，并确保它会与查询的其余部分一起被编译和融合，从而实现高效执行。 --- 1. 远在 AI 精神病之前，有 FP 精神病，临床上定义为理解函数式编程概念（如递归、高阶函数、单子，或者本例中的续延传递风格）时产生的强烈心理反应。↩︎ (https://remy.wang/blog/cps.html#fnref1) 2. 本文中的所有代码都是 Julia 语言。↩︎ (https://remy.wang/blog/cps.html#fnref2) 3. `scan(xs)` 表示 `k -> scan(xs, k)`，即 `scan` 对 `xs` 的 curried (https://en.wikipedia.org/wiki/Currying) 应用。类似地，下面的 `inc(scan(xs))` 用 `scan(xs)` 对 `inc` 进行柯里化。↩︎ (https://remy.wang/blog/cps.html#fnref3)