DuckDB 如何让递归 CTE 运行得更快

DuckDB 的递归 CTE 引擎将递归视为一次持续存在的计算：保留满足条件的 epoch 不变状态，根据精确前沿基数和物理工作选择执行模式，直接探测按键状态，并为 USING KEY ... UNION 引入变化键语义。

2020 年，Denis Hirn 实现了 DuckDB 的第一个递归 CTE 算子。当时，正确性决定了设计：先计算一次非递归项，再反复计算递归项，直到下一张工作表为空。这建立了正确的语义约定，但可复用的运行时状态被放在了过小的作用域中。每次迭代，递归输入都会变化，而求值所需的大部分执行机制仍然可以复用。

然而，这一实现几乎把每次迭代都当成一个新查询，反复付出流水线调度、算子初始化、执行和清理的成本。作者从那时起就一直希望消除这种不匹配。

在即将发布的 DuckDB v2.0 中，这些作用域得到了明确划分。查询计划拥有物理算子树、预先计算的流水线调度方案，以及可复用的流水线执行器池。每次递归调用从该池中借用执行器，并拥有累积的递归状态，以及生命周期覆盖整个不动点计算的保留物化结果；每轮迭代只拥有依赖当前前沿的状态。

这种划分让引擎能够保留哈希表构建结果、在每轮迭代中选择内联执行或调度执行，并直接探测按键维护的状态。物理执行方式的变化还伴随一项语义变化：对于 USING KEY，UNION 现在会将新键，以及最终载荷值发生变化的键，暴露给下一轮迭代。

为了说明性能影响，原文对一个小型可达性查询比较了新旧引擎。表中有 100 万条边、10 万个节点。每个源节点都有 10 条相同的出边；从节点 0 沿着这些边遍历，会访问 2 万个节点：

CREATE TABLE edges AS
    SELECT (range % 100_000)::INTEGER AS src,
           ((range * 13 + 7) % 100_000)::INTEGER AS dst
    FROM range(1_000_000);

WITH RECURSIVE reachable(node) AS (
    SELECT 0
    UNION
    SELECT dst
    FROM edges, reachable
    WHERE src = node
)
SELECT count(*)
FROM reachable;

采用下文介绍的优化后，原文基准中的运行时间中位数从 DuckDB v1.5.5 的 4.051 秒降至 DuckDB v2.0 预览版的 0.095 秒。SQL 保持不变，速度提高了 42.6 倍。

可复用执行状态的生命周期长于前沿

递归 CTE 的执行发生在查询计划的生命周期内。物理算子树属于该计划；不可变的调度投影在物理流水线构建阶段生成。在查询计划内部，一次调用覆盖一次完整的不动点计算，而一个 epoch（迭代轮次） 对应递归项的一次求值。

原来的查询计划已经保留了递归物理算子，但运行时仍把每个 epoch 当成一次全新的执行：重新创建事件和执行器、重建算子状态，并重复调度工作。

在构建流水线时，DuckDB 会从流水线依赖调度中导出不可变视图，其中也包括这样的视图：首次执行后，省略那些构建结果已被调用保留的流水线。原文将这些视图称为 调度投影（schedule projections）。运行时因而可以直接选择所需的依赖调度，而无须在每个 epoch 中重新推导。

前沿限定递归输入

每个递归 epoch 都会替换工作表，这张表通常称为 前沿（frontier）；查询本身则保持不变。锚定项产生第一个前沿。递归项读取这个前沿，为下一轮产生候选行。对于普通的 UNION，DuckDB 会拒绝已经出现过的行；剩余行构成下一个前沿，同时也进入逻辑上的 联合表（union table）。当不再有行留下时，求值结束。

联合表是语义的一部分，但 DuckDB 不一定需要将它物化：结果数据块可以流向下游，同时引擎保留当前前沿，以及普通 UNION 去重所需的哈希状态。只有当递归项访问 recurring.⟨cte_name⟩ 时，引擎才会累积一份完整副本。

对于单调、线性的递归项，这种前沿机制就是 半朴素求值（semi-naive evaluation） 的运行核心：每个 epoch 只读取上一轮的增量，而不是用此前见过的所有行重新计算递归项。原来的算子已经保持了这一语义不变量；尚未解决的不匹配，涉及求值该前沿的物理执行机制的生命周期。

epoch 不变的状态属于整次调用

前沿扫描在 EXPLAIN 计划中显示为 REC_CTE_SCAN。跨过 epoch 边界后，它必须读取新的输入；所有依赖该输入的算子的运行时状态也必须重置。属于查询计划的调度投影仍然有效。为这次调用借出的执行器，以及调用拥有的缓冲区，可以重置后复用；如果某次构建只依赖与递归无关的基表，而且重复构建会产生相同的可观察结果，就可以保留已经物化的状态。

旧运行时没有区分调用范围内的物化状态与依赖前沿的状态：在整个递归调用期间都有效的物化状态，不能由某一个 epoch 拥有。

如果一个操作的输入不依赖当前前沿，且重新求值会产生相同的可观察结果，那么它就是 epoch 不变的。扫描一张稳定的基表，并以此构建哈希表，就是典型例子。递归运行时采用与 循环不变代码外提（loop-invariant code motion） 相同的归属划分：不变的构建放在 epoch 循环之外，用不断变化的前沿去探测它的工作则留在循环内。

状态归属这个不变量，最先在递归运行时中失效。DuckDB 将查询作为流水线图来执行。尽管旧物理算子保留了递归元流水线，每个 epoch 仍会重新创建事件和执行器、调度流水线，并重建它们的状态。因此，epoch 不变的流水线也会重新读取同一份静态输入，重建同一份状态。

当一个 epoch 足够大时，固定的调度和初始化成本可以分摊到许多前沿行上。但重建不变状态的工作量仍与静态输入的大小成正比，其成本可能远高于用变化中的前沿探测已有状态。

DuckDB v1.5.5 每轮都会根据前沿重建哈希表，再把 edges 作为探测输入重新扫描。新引擎把连接方向反过来，只构建一次边表的哈希表，再让每个前沿去探测它。

最终的状态归属边界如下：

开头查询中的哈希连接，既需要重新调整连接方向，也需要保留状态。DuckDB v1.5.5 根据当前 reachable 前沿构建哈希表，并在每个 epoch 扫描 edges 作为探测输入。新规划器会在语义允许时，将与递归无关的 edges 关系放在构建侧。第一个 epoch 扫描 edges 并构建哈希表；后续 epoch 将 reachable 重新绑定为探测输入，复用该表。

EXPLAIN (ANALYZE, FORMAT JSON) 可以具体展示被省去的输入工作。原文比较的两个版本都返回了预期的 2 万个节点。DuckDB v1.5.5 在 edges 扫描上报告 operator_rows_scanned: 19,718,328,320，按行数折算，相当于约 19,718 次完整扫描；DuckDB v2.0 预览版则只扫描一次该表中的 100 万行。动态过滤跳过了 v1.5.5 某些扫描中的部分数据，但无法阻止每个 epoch 再次访问基表。

保留状态需要证明可重复性

只有构建结果在可观察层面可重复，引擎才会保留它。与递归无关是一个条件，可重复性则是另一个条件：带固定随机种子的采样可以保留；不带随机种子的采样、nextval() 之类的易变表达式、DML、有副作用的算子，或者行为未知的扩展算子，都必须重新构建。可重复性分类器负责这一判断；无法证明安全时，它会拒绝保留状态。这种保守选择可能放弃部分复用机会，但会保持查询语义。

完全物化的 CTE 生产者遵循相同的归属规则：与递归无关的结果可以继续保留，每个消费者扫描则重置。流式或混合式生产者不会被保留，因为它们的消费状态没有相同的生命周期。源数据提前终止也是一个边界情况：保留的流水线不能仅仅为了填满一个向量而扣住部分输出，否则可能阻止下游 LIMIT 提前停止递归执行。

因此，复用也会保持这一终止约定。

精确基数让执行自适应

epoch 边界提供了普通查询规划时无法获得的信息。一个 epoch 结束时，DuckDB 已经完整生成下一个前沿，因此能精确知道其行数和数据块数。这些实际观察到的基数决定了递归运行时如何执行下一个 epoch；优化器估计不再需要代替它们。

每个 epoch 选择自己的执行模式

开头的查询一旦构建并保留了边表的哈希表，一个 epoch 中的工作就变成：将一个可达节点送入一次探测。把这点工作交给并行调度器，协调成本会超过有效工作。前沿扩展到许多数据块的遍历则正好相反：只用一个线程执行，会让相互独立的流水线工作闲置。为整个查询固定选择一种模式无法同时满足这两种情况；同一查询也可能随着前沿扩张和收缩，在两种形态之间切换。

当精确的前沿大小和物理工作形态不足以支撑任务调度时，一个 epoch 会采用 内联执行（inline）。单个线程遍历选中的不可变调度投影，直接驱动算子，不创建任务，也不进入通用调度器。当工作分类器发现有足够多的独立工作时，调度执行（scheduled execution） 会实例化对应的递归事件图，将工作分配给数量受限的工作线程。两种模式都使用查询计划拥有的同一套调度投影。

为调用借出的执行器，以及调用拥有的缓冲区，会重置后复用；变化的只有 epoch 级别的执行策略。

有用的并行度不能只由行数决定。策略还会考虑前沿的数据块、递归引用的数量、独立源任务、配置的线程数，以及实际会执行的流水线。同一个前沿可能为多条流水线提供输入，独立的数据源也可能暴露前沿行数未体现的工作。另一方面，工作线程私有输出和边界处的合并也有自身成本。

因此，引擎同时根据递归输入和物理工作单元来限制工作线程数量；只有在覆盖面较广的普通 UNION ALL epoch，以及执行去重的 UNION epoch 中，且合并成本能够得到分摊时，才使用私有输出。

冻结的按键状态支持直接探测

Torsten Grust 与 Björn Bamberg 在 《递归 CTE 中的 USING KEY》 中介绍了最初的 USING KEY 功能及其应用。从语义上说，USING KEY 把联合表作为按键维护的状态：声明的键列标识一行，其余载荷列由声明的聚合函数，或者默认的 last 聚合函数维护。DuckDB 在物理层面用聚合哈希表表示这一状态。

因此，递归项可以直接探测选定的键，而不必扫描完整的累积递归状态。

每个 epoch 都读取冻结的按键状态

直接访问必须保持一个语义不变量：在 epoch i 期间，每次通过 recurring.⟨cte_name⟩ 进行的访问，观察到的都必须是同一个按键状态 Sᵢ。一个 epoch 有三个依次进行的阶段：读取 Sᵢ，缓存候选多重集，然后提交这些候选行，得到 Sᵢ₊₁。如果在读取阶段就让候选行可见，同一 epoch 的其他候选行可能观察到它，结果就会依赖工作线程的到达顺序。

这三个阶段保持了一轮一轮的状态转移，同时允许探测并发执行。

原实现通过把按键状态物化到一个集合中，供累积状态读取，来保持这个不变量。这样的表示方式让每次访问都走覆盖面很广的物理路径：即使一个 epoch 只访问少数几个键，仍可能复制或扫描包含数百万个键的状态。

现在，按键状态的拥有者直接保证这些阶段的顺序。在递归流水线执行时，recurring.⟨cte_name⟩ 读取冻结的聚合哈希表，候选行则单独累积。拥有者只在 epoch 边界处提交候选行。一次探测无法观察到只应用了一半的更新，哈希表增长也不会使并发读者持有的地址失效。递归结束后，源算子只遍历一次最终的按键状态以输出结果。

能否使用探测路径取决于连接形态

冻结的表示方式支持专门的物理查找路径，同时保留相同的语义视图。如果一个内连接使用 = 或 IS NOT DISTINCT FROM 比较每个声明的键，就可以使用 递归键连接：它在 EXPLAIN 中显示为 RECURSIVE_KEY_JOIN，直接探测聚合哈希表。如果这类比较只覆盖复合键的真子集，则可以通过 RECURSIVE_PARTIAL_KEY_JOIN 使用在当前 epoch 内稳定的辅助哈希索引。

新的完整键只有在其地址稳定后才会扩展索引；只更新载荷，不需要维护索引。

完整键专用路径只适用于这样的内连接：连接对方是直接的累积状态扫描（REC_REC_CTE_SCAN），对每个声明的键，都使用直接且类型完全匹配的标量 = 或 IS NOT DISTINCT FROM 比较。残余谓词、被其他算子包裹的扫描、不匹配的类型、嵌套键，以及其他连接类型，都走通用路径。普通的递归引用也不符合条件，因为它表示前沿；累积的按键状态要通过 recurring 引用访问。

把这两个身份视为可以互换，会改变查询。

稀疏工作应避免扫描完整状态

下面的工作负载保留 100 万个键，并让其中 1,000 个键推进 20 个 epoch：

WITH RECURSIVE state(key, value) USING KEY (key) AS (
    SELECT key, CASE WHEN key < 1_000 THEN 0 ELSE 100 END
    FROM range(1_000_000) keys(key)
    UNION ALL
    SELECT frontier.key, recurring_state.value + 1
    FROM state AS frontier
    JOIN recurring.state AS recurring_state USING (key)
    WHERE frontier.value < 20
)
SELECT count(*) AS keys, sum(value)::BIGINT AS value_sum
FROM state;

引入直接探测之前，这个连接会反复扫描 recurring.state。原文运行时指标统计出约 2,000 万行完整状态扫描，却只得到 2 万次有效匹配。专用计划把这些扫描替换为 2 万次直接探测，将检查的累积状态行数降低了 1,000 倍。比较直接探测改动前后的构建版本时，原文测得的运行时间中位数从 0.401 秒降至 0.040 秒。

新路径也移除了此前每个 epoch 为物化完整按键状态而使用的集合。

候选行可能不会改变按键状态

即使按键状态没有变化，候选多重集仍然可能非空。如果候选行自动成为下一个前沿，查询可见状态已经收敛后，递归仍可能继续。保留执行状态、提高探测效率，都无法修复这一语义上的不匹配。

USING KEY ... UNION 现在在 SQL 层面表达了这一区别。

CIDR 论文《A Fix for the Fixation on Fixpoints》 与 SIGMOD 论文《How DuckDB is USING KEY to Unlock Recursive Query Performance》 都描述了最初的候选前沿设计：无论按键状态是否变化，候选多重集都会成为下一张工作表。

两篇论文都没有定义变化键增量。按作者团队在原文发表时的了解，DuckDB 是首个、也是当时唯一将 UNION 的变化键递归与 UNION ALL 的候选前沿递归加以区分的数据库系统。

最终状态由提交层负责

在这项改动之前，DuckDB 遵循最初设计，对 USING KEY ... UNION 与 USING KEY ... UNION ALL 采用相同处理。递归项产生的每个候选行都会成为下一个 epoch 的输入，即使应用该候选行后，累积递归表保持不变。由于普通 UNION 与 UNION ALL 都采用相同的候选前沿行为，DuckDB v1.5 曾弃用 USING KEY 中的 UNION。这里引入的变化键语义为两个关键字赋予了不同含义，因此即将发布的 v2.0 会保留两者。

只有应用了该 epoch 的所有候选行之后，才能确定一个键的可观察聚合结果。因此，判断一个键是否发生变化，由 epoch 提交层负责。

最短路径计算的一轮迭代可以说明，为什么候选行不能自行作出这一判断。多条路径可能到达同一个节点，每条路径都必须参与 min(distance) 计算。按键状态中可观察到的，只有最终确定的最小值。把每条较差路径都传给下一轮，会放大下一轮的工作；把没有变化的最小值传过去，则可能让状态已经收敛之后，候选行仍不断产生。

考虑按键状态 {A:8, B:7}，载荷聚合为 min，候选行为 [A:9, A:5, B:7]。应用完整候选多重集后，得到 {A:5, B:7}。候选 A:9 不影响最终最小值，B:7 则重复了现有值。然而，UNION ALL 仍然会传递全部三个候选行。UNION 只传递最终行 A:5，因为它是唯一可观察到的状态变化。

UNION 与 UNION ALL 暴露不同的前沿

设 Cᵢ 为 epoch i 产生的候选多重集，Sᵢ 为该 epoch 期间可见的按键状态，Wᵢ₊₁ 为下一张工作表。update(Sᵢ, Cᵢ) 表示应用多重集中的所有候选行，并确定所有受影响载荷聚合的最终结果；keys(Sᵢ) 表示更新前存在的键。两种形式定义如下：

USING KEY ... UNION ALL
Sᵢ₊₁ = update(Sᵢ, Cᵢ)
Wᵢ₊₁ = Cᵢ

USING KEY ... UNION
Sᵢ₊₁ = update(Sᵢ, Cᵢ)
Wᵢ₊₁ = { Sᵢ₊₁[k] | k ∉ keys(Sᵢ) OR Sᵢ₊₁[k] IS DISTINCT FROM Sᵢ[k] }

对同一份输入状态和候选多重集，两种形式计算出的下一份按键状态相同。它们的区别是哪些行对下一轮递归可见：UNION ALL 原样传递候选多重集；UNION 则对每个新键，或可观察值发生变化的键，传递一行最终确定的结果。因此，在 USING KEY ... UNION 下，按键状态不再变化时，递归便会停止。

epoch 提交层通过以下方式实现该规则：记录键此前是否存在，并在一个已有键首次被触及时，为其 epoch 开始前的最终载荷建立快照。随后应用全部候选行，再对每个被触及的键进行一次最终化和比较。重复候选行，以及在 min 或 max 中未胜出的输入，仍然参与聚合求值，但不会仅凭自身就变成递归工作。

对于同一份按键状态和候选多重集，两种形式计算出的状态更新相同；下一个前沿可以是该多重集，也可以是变化键增量。

最终值采用 SQL 语义比较，包括 NULL 和排序规则。键身份使用与 GROUP BY 相同的规范化方式；带排序规则的标量键仍然可以使用完整键与部分键探测。实现也覆盖多列载荷、嵌套载荷、NaN 和带符号的零。

两个前沿的类型也不同。UNION ALL 前沿包含原始候选行，因此其载荷列使用聚合输入类型。UNION 前沿包含最终确定的按键行，因此其载荷列使用聚合结果类型。这一区别可以通过 SQL 约定观察到，也限制了内部表示方式。关键字决定前沿的内容、类型和终止条件，所以引擎绝不会把一种形式推断成另一种形式来进行优化。

变化键增量仍要支付处理候选行的成本

只有全部候选行都应用之后，变化键增量才能缩小下一个前沿。因此，即使最终只有很少的键变化，数百万个重复候选行仍可能让累积哈希表的更新代价高昂。对于满足条件、重复很多的 epoch，引擎会先在临时按键哈希表中合并候选行，再把这些聚合状态合并进累积状态。

预聚合要求聚合状态可以合并

提前合并必须在可观察结果上，等价于直接应用候选行。只有每个载荷聚合函数都提供状态合并操作，且都不依赖顺序时，预聚合才会启用。因此，默认的 last 聚合函数，以及没有合并回调的扩展聚合函数，仍走直接更新路径。没有合并操作，预聚合就缺少有效的状态转移。

对于依赖顺序的聚合函数，预聚合可能改变可观察的输入顺序，从而改变结果。

基数证据决定是否预聚合

适用性条件建立正确性；观察到的基数决定这个正确的变换是否值得执行。小于一个标准向量的 epoch 不进行分类；不扩张的 epoch，即候选行数不超过前一前沿行数的 epoch，也跳过分类。更大的、满足条件的 epoch 会对候选键构建 HyperLogLog 摘要。

只有将误差余量计入后的基数估计，小于候选行数的四分之一，才进行预聚合。一旦不同键数量的证据足以否决额外哈希表，就提前停止生成摘要。因此，这一决策会随每个 epoch 实际观察到的重复程度而调整。

证明一个值未发生变化的成本，也限制了该策略。对于包含 102,400 个不同已有键更新的宽工作负载，在新的 UNION 语义下，原文测得运行时间中位数增加 0.913 毫秒，也就是 6%。执行器必须比较最终值；旧实现则不证明变化，直接传递候选行。为 min 和 max 添加专用捷径，会把聚合语义放进递归执行器，因此实现没有采用这种做法。

如果聚合函数具有报告变化的约定，就能把这项责任放进聚合接口。当前接口还没有这样的约定。

推动这一工作的较大工作负载，是一个 LDBC SF100 寻路查询。它生成约 2,100 万个聚合候选行，但 epoch 级聚合只产生了 370 万个可观察的按键结果。自适应路径预聚合了 1,700 万个候选行。在变化键改动前后、相互匹配的 Release 构建上，原文测得查询时间中位数从 19.319 秒降至 2.948 秒，速度提高 6.55 倍；峰值驻留内存则从 3.918 GB 降至 2.663 GB。

更广的回归测试套件也界定了这项结果的适用范围。在同一次构建比较中，63 项递归基准的几何平均值改善了 5.5%，其中 60 项的变化在 ±2% 以内。重复汇入，以及重复很多的预聚合工作负载，改善显著；前面提到的宽、唯一键工作负载是唯一稳定退步的情况。因此，引擎按 epoch 分类工作，而不会把在推动这一优化的查询上获胜的策略直接套到所有工作负载上。

递归 CTE 作为一次自适应计算来执行

新引擎解决了作者实现 DuckDB 原始递归算子后一直希望消除的生命周期不匹配。查询计划拥有物理算子树、调度投影和可复用的执行器池。在每次调用内部，运行时借出执行器，并在各个 epoch 之间保留已证明可重复、且与递归无关的状态；每个 epoch 则重新绑定并重置依赖前沿的状态。这种划分让保留不变工作与每轮执行策略能够配合使用。

按键递归利用 epoch 边界冻结累积状态，以便直接探测；随后提交候选行，并在 UNION 下只把可观察的变化作为下一轮前沿。相关实现分别落在 #22211、#24031、#24565 和 #24647 中。

这一点之所以重要，是因为递归会倍增放进 epoch 循环中的每一项物理成本。单独看并不大的扫描、哈希构建，或进入通用调度器的开销，都可能执行数万次。新引擎在每次调用中，只支付一次满足条件的不变成本；当观察到的工作无法分摊调度开销时，避开这一开销；当 epoch 暴露出足够多的独立工作时，将其分配执行。满足条件的按键连接可以直接访问所需状态，而 USING KEY ... UNION 递归在状态收敛时终止。这使递归 SQL 成为更实用的图遍历、寻路和状态机执行模型，尤其适用于前沿一直很小、静态输入却很大，或者许多候选行更新相同键的场景。

下一步，是把这一基础扩展到更多递归计划。未来可以把调用范围内的复用扩展到更多满足条件的算子状态，并利用 epoch 边界观察到的基数，作出进一步的执行决策。每项扩展都必须保持相同的前沿语义和状态转移语义。作者计划继续沿着这条边界推进：在保持递归 SQL 可预测的同时，降低迭代的物理成本。