DuckDB递归为何突然变快

你要沿着一张关系网找出所有能到达的人。旧版 DuckDB 像是每找到一批新线索，就把工作台拆掉重装：重新安排流程、准备工具，还反复翻同一本通讯录。即将发布的 DuckDB v2.0 改了这套做法。它保留跨轮次仍然有效的执行状态，只重置真正随新线索变化的部分，并根据这一轮线索多少选择执行方式。

值得注意的是，递归 CTE——一种让查询反复引用上一轮结果、直到没有新结果为止的 SQL 写法——本身并没有改变。变快的是数据库执行每一轮递归的方式。本文数字和机制均来自 DuckDB 官方博客这一家机构信源；其中 42.6× 来自特定合成测试，不能外推到所有递归查询。

旧引擎慢在“每轮重新开工”

我们此前在《递归CTE不只会查组织树》中介绍过，递归 CTE 可以找路径、计算关系距离和识别环。它通常包含两部分：先用一个查询产生起点，再让递归查询读取上一轮结果，持续扩展。

上一轮刚找到、下一轮还要继续处理的记录叫作“前沿”（frontier）。例如从节点 0 出发，第一轮找到它的邻居；这些邻居就是下一轮的前沿。前沿不断更换，但查询结构和基础数据通常没有变。

Denis Hirn 在 DuckDB 官方博客中回顾，DuckDB 首个递归 CTE 算子在 2020 年实现。当时设计首先保证语义正确，却把可复用运行状态的生命周期划得太短。旧运行时几乎把每轮迭代当成一次新查询，重复进行执行管线调度、算子状态构建、执行和清理。

执行管线可以理解为数据库拆出的扫描、连接、聚合等工序。每轮前沿可能只有少量记录，但整套工序仍要重新安排。固定成本由此不断累积。

关键不是少算一轮，而是留下能复用的东西

v2.0 重写后的引擎明确区分三种生命周期。

查询计划长期持有物理算子树、预先计算的管线调度方案，以及一组可复用的执行器。一次完整的递归调用持有累计状态和需要跨轮保留的中间结果。单轮迭代则只持有依赖当前前沿的状态。

这像是每天处理一批新订单：仓库布局和货品索引不必每天重建，只有当天订单需要更换。对应到数据库，如果一张基础表不依赖递归输入，而且重复计算会得到相同结果，引擎就能保留基于它建立的 hash table——一种把连接键整理成可快速查找结构的中间状态。下一轮只需拿新前沿去查询它。

引擎还会依据前沿大小，在 inline execution 和 scheduled execution 之间选择。前者可以理解为直接在当前执行路径里完成工作；后者则交给完整的管线调度系统。材料没有给出具体切换阈值，但思路很直白：小批任务不必启动一整套调度 machinery，大批任务则能摊薄调度成本。

一次扫描，替代近两万次扫描

官方展示的是一个可达性查询。测试表有 100 万条边、10 万个节点；从节点 0 出发，可以访问 2 万个节点。数据是特意构造的：每个源节点都有十条相同的边，因此包含大量重复边。

在这个例子中，DuckDB v1.5.5 的中位运行时间是 4.051 秒，v2.0 preview 为 0.095 秒，SQL 无需修改，官方计算为 42.6× 加速。

真正解释差距的是扫描量。旧版对 edges 表记录的 operator_rows_scanned 达到 19,718,328,320，约等于把整张表扫描了 19,718 次。新版只扫描 1,000,000 行，也就是一次。

原因在连接方向。旧版每轮根据前沿建立 hash table，再重新扫描 edges。新规划器在合法时会调换方向：先为 edges 建立一次可保留的 hash table，之后让每轮的可达前沿反复去探测它。递归逻辑没少走一步，但不再反复搬动那张更大的基础表。

`USING KEY` 也开始直接读状态

DuckDB v2.0 还优化了 USING KEY——一种按键保存递归状态的机制。新引擎可以直接探测聚合 hash table。每轮读取的是冻结状态，候选结果到轮次结束时再统一提交，避免同一轮中的更新改变其他记录看到的输入。

官方材料还称，USING KEY 配合 UNION 时，只有新 key，或最终 payload（键对应的值）发生变化的 key，才会进入下一轮前沿。不过这项语义与当前官方文档所述弃用安排存在版本间出入，因此长期行为仍不确定。

为什么值得关注

这次优化最有意思的地方，不只是某个测试快了几十倍，而是它展示了一条朴素的工程原则：递归每轮改变的是数据前沿，不代表整套执行机器都应推倒重来。

新引擎一面保留经过可重复性证明、又不依赖递归输入的状态，一面用精确的前沿规模选择执行模式。它把“什么会变”和“什么不会变”分开管理。相关实现已进入 DuckDB PR #22211、#24031、#24565 和 #24647。

局限与未知