DuckDB v2.0 如何让递归 CTE 跑得更快

TL;DR：DuckDB 的递归 CTE 引擎现在将递归视为一次长期存续的计算：它保留符合条件的、在 epoch 间不变的状态，根据精确的 frontier 基数和物理工作量选择执行模式，直接探测键控状态，并赋予 USING KEY ... UNION 变更键语义。

当我在 2020 年实现 DuckDB 的第一个递归 CTE 算子 时，正确性决定了设计：先对非递归项求值一次，然后反复对递归项求值，直到下一个工作表为空。这确立了正确的语义契约，但可复用的运行时状态作用域过于狭窄。在多次迭代之间，递归输入会发生变化，而对其求值的大部分机制仍然可复用。然而该实现几乎把每次迭代都当作一个新查询，反复为流水线调度、算子设置、执行和拆除付出代价。从那以后我一直想消除这种不匹配。

在即将发布的 DuckDB v2.0 中，我们显式地划分这些作用域。查询计划拥有物理算子树、预计算的流水线调度以及一个可复用流水线执行器池。每次递归调用从该池中借用执行器，并拥有累积的递归状态和保留的物化结果，其生命周期跨越整个不动点计算；而每次迭代只拥有依赖 frontier 的状态。这种分离使得保留哈希构建、在每次迭代中在内联执行与调度执行之间选择，以及直接探测键控状态成为可能。物理执行的变更伴随着一个语义变更：对于 USING KEY，UNION 现在使新键以及最终载荷发生变化的键对下一次迭代可见。

为了说明性能影响，我们在一个小型可达性查询上比较原始引擎和新引擎。该表包含 100,000 个节点上的一百万条边。每个源节点发出十条相同的边，从节点 0 出发沿着这些边会访问 20,000 个节点：

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 倍的加速。

可复用的执行状态比 frontier 存续更久

递归 CTE 执行位于查询计划的生命周期内。物理算子树属于该计划，不可变的调度投影在物理流水线构建期间生成。在计划内，一次调用跨越一个完整的不动点计算，而一个 epoch 跨越递归项的一次求值。原始查询计划已经保留了递归物理算子，但其运行时将每个 epoch 视为一次全新执行：它重新创建事件和执行器，重建算子状态，并重复调度工作。

在流水线构建期间，DuckDB 会派生流水线依赖调度的不可变视图，包括在首次执行后省略调用保留的构建流水线的形式。我们将这些视图称为 调度投影。因此，运行时可以选择所需的依赖调度，而无需为每个 epoch 重新派生。

Frontier 界定递归输入

每个递归 epoch 都会替换工作表（通常称为 frontier），而查询保持不变。锚点项生成第一个 frontier。递归项读取它并生成下一个 frontier 的候选行。使用常规 UNION 时，DuckDB 会拒绝已见过的行；幸存的行构成下一个 frontier，同时也贡献到逻辑 union table。当没有行幸存时，求值停止。

union table 属于语义的一部分。DuckDB 无需将其物化：结果块可以向下游流式传输，同时引擎保留当前 frontier，并且对于常规 UNION，保留去重所需的哈希状态。只有当递归项访问 recurring.cte_name 时，它才会累积完整副本。

对于单调、线性的递归项，这种 frontier 规则是 半朴素求值 的操作核心：一个 epoch 只读取前一个 delta，而不是从迄今见过的每一行重新求值递归项。原始算子已经保留了这一语义不变量；剩下的不匹配在于求值该 frontier 的物理机制的生存期。

Epoch 不变状态属于调用

frontier 扫描（在 EXPLAIN 计划中显示为 REC_CTE_SCAN）必须在 epoch 边界之后读取新输入，并且每个依赖该输入的算子的运行时状态都必须重置。查询计划拥有的调度投影仍然有效。为调用而检出的执行器和调用拥有的缓冲区可以重置以供重用，而完全基于与递归无关的基础表构建的 build 如果重复构建会产生相同的可观察结果，则可以保留其物化状态。旧的运行时未能区分调用作用域的物化状态与依赖 frontier 的状态：其有效性跨越递归调用的物化状态不能由一个 epoch 拥有。

当一个操作的输入不依赖于当前 frontier，并且重新求值它会产生相同的可观察结果时，该操作是 epoch 不变 的。扫描稳定的基础表并从中构建哈希表是典型示例。递归运行时遵循与 循环不变代码外提 相同的所有权区分：不变的 build 属于 epoch 循环之外，而用变化的 frontier 探测它则留在循环之内。

所有权不变量首先在递归运行时中失效。DuckDB 将查询作为管道图执行。尽管旧的物理算子保留了其递归元管道，但每个 epoch 都会重新创建事件和执行器、调度管道并重建其状态。因此，epoch 不变的管道会重新读取相同的静态输入并重建相同的状态。

一个大的 epoch 可以将固定的调度和设置成本分摊到许多 frontier 行上。重建不变状态仍然与静态输入大小成正比，并且其成本可能远高于用变化的 frontier 探测它。

DuckDB v1.5.5 从每个 frontier 重建哈希表，并重新将 edges 作为探测输入。新引擎反转了连接，只构建一次边哈希表，并用每个 frontier 探测它。

由此产生的所有权边界是：

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

EXPLAIN (ANALYZE, FORMAT JSON) 使所避免的输入工作量变得具体。两个版本都返回预期的 20,000 个节点。DuckDB v1.5.5 在 edges 扫描上报告 operator_rows_scanned: 19,718,328,320，其行量相当于约 19,718 次完整扫描，而 DuckDB v2.0 预览版仅报告该表的一百万行一次。动态过滤会跳过 v1.5.5 某些边扫描的部分内容，但无法阻止基础关系在每个 epoch 中被重新访问。

保留需要可重复性证明

只有当构建的可观察结果可重复时，我们才保留它。递归无关性确立了一个必要条件。可重复性又增加了一个条件：带种子的采样可以保留；无种子的采样、诸如 nextval() 这样的易变表达式、DML、有副作用的算子或未知的扩展算子必须重建。可重复性分类器负责该决策，并在无法证明安全时拒绝保留。这种保守选择可能放弃复用，但保留了查询语义。

完全物化的 CTE 生产者遵循相同的所有权规则：递归无关的结果可以保留，而每个消费者扫描会被重置。我们不保留流式或混合生产者，因为它们的消费状态不具有相同的生命周期。提前终止源是另一个边界情况。保留的流水线不得仅为填充向量而扣留部分输出，因为这样做可能会阻止下游的 LIMIT 提前停止递归执行。因此，复用保留了该终止契约。

精确基数使执行具有自适应性

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

每个 Epoch 选择自己的模式

一旦开头查询构建并保留了其边哈希表，一个 epoch 就将一个可达节点带入一次探测。将这项工作交给并行调度器会产生比有用工作更多的协调开销。前沿扩展到许多块的遍历则具有相反的形状：在单线程上执行它会使独立的流水线工作闲置。为整个查询选择的静态模式无法同时服务这两种情况，而单个查询可能随着其前沿的扩展和收缩在两者之间切换。

当确切的前沿和物理工作形态不足以证明任务调度的合理性时，一个 epoch 会内联运行。一个线程遍历选定的不可变调度投影并直接驱动其算子，而不创建任务或进入通用调度器。当工作分类器发现足够多的独立工作时，调度执行会实例化相应的递归事件图，并将工作分配给有限数量的 worker。两种模式都使用相同的查询计划所拥有的调度投影。为本次调用检出的执行器和调用所拥有的缓冲区会被重置以供复用；只有 epoch 级别的执行策略发生变化。

仅凭行数并不能决定有用的并行度。该策略还会考虑前沿块、递归引用的数量、独立的源任务、配置的线程数以及实际会执行的流水线。同一个前沿可以供给多个流水线，而一个独立的源可以暴露前沿行未表示的工作。反过来，worker 本地输出和边界合并也会引入自身的成本。因此，我们同时根据递归输入和物理工作单元来限制 worker 数量，仅在合并成本可以摊销的宽泛规则 UNION ALL 和消除重复的 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 中的另一个候选观察到它，从而使结果依赖于 worker 的到达顺序。这三个阶段在探测并发执行的同时，保持了逐 epoch 的状态转换。

最初的实现通过将键控状态物化到一个集合中以供循环状态读取，从而保持了该不变量。这种表示给每次访问都提供了一条宽泛的物理路径：一个只触及少数几个键的 epoch 仍然可能复制或扫描包含数百万个键的状态。

键控状态的所有者现在强制执行这些阶段。在递归流水线执行时，recurring.cte_name 读取冻结的聚合哈希表，候选则单独累积。所有者仅在 epoch 边界处提交它们。探测无法观察到半应用的更新，哈希表的增长也无法使并发读取器持有的地址失效。递归结束后，源会一次性排空最终的键控状态。

探测资格遵循连接形态

冻结表示支持专门的物理查找，同时保留语义视图。将每个声明的键与 = 或 IS NOT DISTINCT FROM 进行比较的内连接可以使用递归键连接，如 EXPLAIN 中的 RECURSIVE_KEY_JOIN 所示，并直接探测聚合哈希表。对复合键的适当子集进行此类比较时，可以通过 RECURSIVE_PARTIAL_KEY_JOIN 使用纪元稳定的二级哈希索引。新的完整键仅在其地址稳定后才扩展索引；仅负载更新不需要索引维护。

我们仅对针对直接循环状态扫描（REC_REC_CTE_SCAN）的内连接选择完整键特化，且对每个声明的键使用直接、类型完全匹配的标量 = 或 IS NOT DISTINCT FROM 比较。剩余谓词、包装扫描、类型不匹配、嵌套键和其他连接类型使用通用路径。普通的递归引用也不符合条件，因为它表示前沿；累积的键控状态可通过循环引用获得。将这两个身份视为可互换会改变查询。

稀疏工作负载应避免全状态扫描

下面的工作负载保留一百万个键，并推进其中 1,000 个键经过 20 个纪元：

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。运行时指标统计了约 2000 万行全状态扫描，才获得 20,000 个有用匹配。特化计划用 20,000 次直接探测取而代之，检查的循环状态行数减少了 1,000 倍。在直接探测工作前后立即进行的构建比较中，中位运行时间从 0.401 秒降至 0.040 秒。新路径还移除了此前用于物化完整键控状态的每纪元收集。

候选者可以保持键控状态不变

即使键控状态不变，候选袋也可以非空。如果候选者自动成为下一个前沿，那么递归可能在查询可见的状态已收敛后继续。保留执行状态并高效探测它无法修复这种语义不匹配。

USING KEY ... UNION 现在为这一区别赋予了 SQL 级语义。我们的 “A Fix for the Fixation on Fixpoints” CIDR 论文 和 “How DuckDB is USING KEY to Unlock Recursive Query Performance” SIGMOD 论文 都描述了最初的候选前沿设计，其中候选袋无论键控状态是否变化都会成为下一个工作表。两者都没有定义变更键增量。据我们所知，DuckDB 是第一个也是目前唯一一个区分 UNION 下的变更键递归与 UNION ALL 下的候选前沿递归的数据库系统。

最终状态属于提交层

在此更改之前，DuckDB 遵循原始设计，将 USING KEY ... UNION 和 USING KEY ... UNION ALL 同等对待。递归项产生的每个候选者都会成为下一个纪元的输入，即使应用它后循环表保持不变。由于普通 UNION 与 UNION ALL 具有相同的候选前沿行为，DuckDB v1.5 已弃用它而改用 USING KEY。此处引入的变更键语义赋予这两个关键字不同的含义，因此即将发布的 v2.0 将保留两者。一个键的可观察聚合结果只有在应用该纪元的所有候选者之后才能确定。因此，纪元提交层拥有决定某个键是否发生变更的权力。

最短路径的一个 epoch 说明了为什么候选者无法自行决定这一点。多条路径可能到达同一个节点，而每条路径都必须参与 min(distance)。只有最终确定的最小值在键控状态中可观察。转发每一条劣质路径会使下一个 epoch 的工作量成倍增加；转发未变化的最小值则可能在状态收敛后仍让候选生成继续存活。

考虑带有 min 载荷和候选 [A:9, A:5, B:7] 的键控状态 {A:8, 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，我们首先在临时键控哈希表中合并候选，然后将这些聚合状态合并到反复出现的状态中。

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

早期合并必须在观察上等价于直接应用候选。只有当每个 payload 聚合都提供状态合并操作且没有一个是顺序相关时，我们才启用预聚合。因此，默认的 last 聚合以及没有 combine 回调的扩展聚合仍留在直接更新路径上。没有合并操作，预聚合就缺少有效的状态转换。对于顺序相关的聚合，它可能改变观察到的输入顺序，从而改变结果。

基数证据决定预聚合

资格确立正确性；观察到的基数决定这一有效转换是否值得。小于一个标准向量的 epoch 会跳过分类，非扩展 epoch 若其候选数量不超过前一个前沿，也会跳过分类。更大的合格 epoch 会在候选键上构建 HyperLogLog 草图。只有当草图的误差膨胀基数估计低于候选数量的四分之一时，我们才进行预聚合，并且一旦不同键证据足以拒绝额外的哈希表，就提前停止草图构建。因此，该决策会适应每个 epoch 中观察到的重复情况。

证明值未改变的成本约束了这一策略。对于包含 102,400 个唯一现有键更新的宽工作负载，在新的 UNION 语义下，中位运行时间增加了 0.913 毫秒，即 6%。执行器必须比较最终值，而之前的实现只是转发候选，并未证明发生了变化。针对 min 和 max 的聚合特定捷径会将聚合语义放入递归执行器中，因此我们不使用它们。聚合级别的变更报告契约可以将该责任放入聚合接口中。当前接口没有提供这样的契约。

大型的动机工作负载是一个 LDBC SF100 寻路查询。它生成了约 2100 万个聚合候选，但 epoch 级聚合只产生了 370 万个可观察的键控结果。自适应路径预聚合了 1700 万个候选。在变更键工作前后紧邻的匹配 Release 构建上，查询时间从中位数 19.319 秒降至 2.948 秒，加速 6.55 倍，而峰值常驻内存从 3.918 GB 降至 2.663 GB。

更广泛的回归测试套件限定了这一结果。在同一构建比较中，63 个递归基准的几何平均值提高了 5.5%，其中 60 个在 ±2% 以内。重复扇入和重复密集的预聚合有显著改善；上述宽唯一键案例是唯一稳定的损失。因此，我们按 epoch 对工作进行分类，而不是将赢得动机查询的策略应用于每个工作负载。

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

新的引擎解决了我在实现 DuckDB 最初的递归算子后想要消除的生命周期不匹配问题。查询计划拥有物理算子树、调度投影和可复用的执行器池。在每次调用中，运行时检出执行器，并在各个 epoch 之间保留经过验证的、可重复且与递归无关的状态，而每个 epoch 则重新绑定并重置依赖 frontier 的状态。这种分离使得保留的不变量工作与按 epoch 的执行策略得以兼容。键控递归利用 epoch 边界冻结重复出现的状态以进行直接探测，然后提交候选，并仅将可观察到的变化作为下一个 frontier 暴露在 UNION 下。该实现已合入 #22211、#24031、#24565 和 #24647。

这很重要，因为递归会将放入 epoch 循环内的每一项物理成本成倍放大。一次扫描、哈希构建或经过通用调度器的一趟操作，孤立来看似乎微不足道，却可能运行数万次。新引擎每次调用只支付一次符合条件的不变量成本，当观察到的工作无法摊销调度器开销时避免使用调度器，并分配那些能暴露足够独立工作的 epoch。符合条件的键控连接可以直接访问所需状态，而 USING KEY ... UNION 递归在该状态收敛时终止。这使得递归 SQL 成为图遍历、寻路和状态机更实用的执行模型，尤其是当 frontier 保持较小而静态输入很大，或者当许多候选更新相同键时。

下一步是将这一基础扩展到更多递归计划。未来的工作可以将调用作用域内的复用扩展到更多符合条件的算子状态，并利用在 epoch 边界观察到的基数来做出进一步的执行决策。每个扩展都必须保持相同的 frontier 和状态转换语义。我打算继续沿着这一边界推进：降低迭代的物理成本，同时保持递归 SQL 的可预测性。

DuckDB CLI 中的 Agent 模式

DuckDB 团队

一个不含任何数据的 DuckDB 数据库

DuckDB 团队

使用 Java 表函数导入数据

客座作者，Geertjan Wielenga、Alex Kasko