DuckDB 优化器详解

逻辑计划是"做什么"的规范描述，但同一个查询有成千上万种等价写法。优化器的任务，是在这几千种可能里找出那个执行起来最快的——而且要在毫秒级完成。本篇拆开 DuckDB 的优化器：约四十七步重写的顺序编排、唯一的重型代价组件（连接排序），以及为什么"每步可关、每步可观测"是这个组件最被低估的设计。

数据库内核里，优化器是最接近"下棋"的部件：它面对一棵逻辑计划树，手里有一本等价变换的规则手册，每一步落子都会改变整盘棋的胜负。DuckDB 的规则手册有约四十七步，全部按固定顺序执行——src/optimizer/optimizer.cpp 里的 RunBuiltInOptimizers() 就是这本手册的目录。作者在实测中确认，这个顺序不是历史沉淀，而是被精心编排的契约：过滤下推必须发生在统计传播之前，连接排序必须发生在投影上拉之后，未用列裁剪在统计证明某些表达式冗余之后会二次执行。

这一篇会把这本手册读薄：先建立总图，再深挖唯一基于完整代价模型的组件，最后说说这套顺序艺术的代价。

总图：六个阶段，一条单向流水线

四十七步可以按"动什么"分成六组。它们共享一个前提：每一步都接收上一步认为"已经干净"的计划，产出更干净的计划。

第一组动表达式。 表达式重写器是规则最密集的一族，三十多条规则在表达式树上原地化简：常量折叠、NOT (a AND b) 的德摩根展开、x IN (1,2,3) 重写为 OR 链或半连接、LIKE 'abc%' 提取出范围条件。IN 子句重写和正则范围提取单独成步，因为它们影响的不仅是表达式形态，还会改变连接形态——比如 IN 子查询会被改造成半连接，这正是 Neumann《Unnesting Arbitrary Queries》论文在 DuckDB 的落地痕迹。

第二组动过滤条件和 CTE。 过滤上拉把埋在表达式里的条件变成独立的过滤算子，过滤下推再把它尽量推向数据源；CTE 内联决定一个 WITH 子句是物化还是展开——注意它在流程里出现了两次，早一次是为了让后续步骤看到更简单的形态，晚一次是因为前面的重写可能创造了新的内联机会。过滤统计步（FilterStatistics）用基表和分区的统计信息给过滤条件标注基数，供后续代价决策使用。

第三组动聚合。AVG(x) 被重写为 SUM(x)/COUNT(x)（因为后两者可以直接走快速路径）；ROLLUP/CUBE/GROUPING SETS 被展开成显式的多聚合计划；多阶段聚合重写器（MultiStageAggregateRewriter）是这一组里唯二带"代价决策"字样的——它决定一个分组聚合要不要拆成"预聚合 + 归并"两段，以及拆几段。DISTINCT 类聚合有自己的专门设置控制。

第四组动连接。 DelimJoin 化简清理子查询提升留下的中间结构；外连接简化在 NULL 值反正会被上层过滤掉时把外连接降级为内连接；然后是整本手册里唯一的重型角色——基于代价的连接排序，我们下一节专门讲。连接之后还有构建/探测侧选择（决定哈希连接哪边建表）和连接过滤下推（把哈希连接期间学到的过滤条件下推到扫描）。

第五组动投影与物化。 投影上拉让投影算子尽量靠近数据源，未用列裁剪把没人引用的列提前扔掉；列生命周期分析把"哪一列在哪个算子之后不再被需要"算清楚，同样的分析执行两次（统计传播前后各一次）；延迟物化（LateMaterialization）决定宽表扫描时是否只先读过滤需要的列、通过后再回表取其余列；公共子表达式和公共子计划把重复计算、重复扫描合并。

第六组收尾。 重排序消除删掉被上游算子丢弃的 ORDER BY；LIMIT 下推；ORDER BY + LIMIT 转成 TopN 算子；窗口函数转聚合（ROW_NUMBER() OVER () + 过滤 模式）；统计传播（严格说它贯穿全程，在计划定型时再跑一轮完整传播）；最后是分区执行（把流水线切成分片并行）和把类型转换、标量函数尽量下推给文件读取器。

入口是 EXPRESSION_REWRITER，出口是 SCALAR_FN_PUSHDOWN，中间还夹着两轮扩展钩子——优化器扩展可以在内置流程前后插入自己的重写。每一步都有名字、有开关（disabled_optimizers 设置可以传步骤名单独关闭）、有耗时记录。这个"每步可关、每步可观测"的属性，在排查"升级后某条查询变慢"时价值连城：你可以二分定位到是哪一步改变了计划形态。

深挖：连接排序，全手册唯一的重型武器

多表连接时，真正决定性能的是连接顺序。两张表连接只有一种顺序，六张表就有 720 种，而实际执行代价可能差几个数量级——先连接两张百万行大表产生的中间结果，可能比先连接两张千行维度表大一百万倍。DuckDB 的解法是教科书级的：把问题建模为查询图，然后用动态规划求最优。

查询图由关系（节点）和连接谓词（边）构成，由 QueryGraphManager::Build 从计划树提取；连接条件里的过滤条件也会进图。如果计划里混着无法重排的算子（比如聚合在连接之上），优化器只对可重排的子树递归处理，这就是代码里 CreateChildOptimizer 加一Depth 的来历——递归深度上限 128，超过就把当前计划原样返回，"返回当前计划永远是合法选择"。

枚举由 PlanEnumerator 完成，代码注释开门见山：这是《Dynamic Programming Strikes Back》（Moerkotte & Neumann）论文的直译实现。算法按子集大小逐层推进：从单表计划出发，逐层合并相连的关系子集，每个子集只保留代价最小的那个连接计划。组合总数 2^n，DP 把它压到 O(n·2^n)，并且借助"相连子图"剪枝——不相连的子集（会产生笛卡尔积的）默认不枚举，除非实在连不起来才强制激活（ActivateRequiredCrossProducts）。

成本模型简单得令人愉快（cost_model.cpp 全文核心就几行）：

cost(连接) = 连接结果基数 + 左子树成本 + 右子树成本

也就是说，一个计划的总成本等于它执行过程中产生的所有中间结果基数之和。没有 I/O 模型，没有 CPU 模型，没有内存带宽——只有一个信念：中间结果越少，总工作量越少。对于分析型负载，这个信念在绝大多数情况下成立，而它带来的估计速度让"每个子集都估一遍"成为可能。

基数估计从目录系统拿表统计（行数、列的 distinct count），distinct count 优先用 HyperLogLog 或精确统计，退化时用 min/max 区间推断，再不行用兜底值（cardinality_estimator.cpp 一千余行的核心工作）。连接键上的 distinct count 直接决定连接结果基数估计，这也是为什么 DuckDB 1.3 专门改进了 HLL 的统计质量。

降级路径是这套设计里最务实的部分。SolveJoinOrder 的逻辑是：如果表数达到 approximate_join_order_threshold（默认 12）——直接跳过 DP，用贪心算法（GOO，Greedy Operator Ordering）每次选当前代价最小的一对连接；表数没超阈值就先跑精确 DP，如果 DP 撞上枚举预算上限或图连不起来，也退回贪心。作者实测：6 表连接的 TPC-H Q5，join_order 一步耗时 0.82 ms，是优化器里最贵的一步；单表查询里它也要花 0.77 ms——因为完整性检查是少不了的。

统计传播：让条件自己消失

四十七步里还有个低调的角色值得单独一提：统计传播（StatisticsPropagation）。它把基表和已算出的区间统计沿计划树向下传播，在每个算子上重新推导输出统计。当推导结果证明某个过滤条件恒真或恒假时，这个条件会被直接删除——不是"执行时跳过"，而是从计划里消失。它还会顺带证明某些连接条件、某些聚合子表达式是冗余的。作者在 Q1 的 profile 里见过直接证据：过滤条件下推后扫描算子上的估算基数（120,114 行）与实际（591,856 行）差距不小，但计划形态依然正确——估算会错，删除不会错，因为证明是逻辑的而非采样的。

统计传播跑完之后，如果它删掉了表达式，未用列裁剪会二次执行——这就是四十七步里几个步骤出现两次的原因。顺序编排在这里显出它的细腻：每一步都为下一步创造前提。

实测：优化器的账本与开关

回到第 02 篇那张阶段耗时图。SF1 聚合查询总耗时 33.9 ms，其中优化器 7.5 ms，内部最贵的四步是表达式重写（0.77 ms）、连接排序（0.77 ms）、统计传播（0.76 ms）、过滤下推（0.53 ms）。几个可操作的结论：

短查询别怕优化器。 毫秒级的优化开销换来的是避免灾难性的计划，这笔账永远划得来。真正需要留心的是预备语句：同一条查询重复执行时，绑定与优化结果可以复用，省掉这 12.7 ms 的规划开销——交互式场景里"改个 LIMIT 再跑"几乎免费，因为 LIMIT 下推是轻量重写，而"改个 JOIN 条件"要重走全管线。

每一步都能单独关。SET disabled_optimizers = ['join_order']; 之类的设置让你能 A/B 测试某一步的贡献。作者没有系统 benchmark 每一步的收益，但排查计划异常时，这是最快的二分工具。

代价组件的边界要知道。 成本模型只看基数，不看数据分布偏斜、不看内存、不看 I/O。表数超过 12 直接贪心。这些边界决定了什么时候应该人工介入（改写 SQL、加统计提示、或调整连接顺序）。

冷静的部分

这套顺序艺术有三个真实的代价。

顺序即语义，改顺序即改行为。 四十七步是一条单向流水线，每一步的输入依赖前序步骤的不变量。往中间插一步新优化，可能 silently 改变下游所有步骤看到的世界。这也是为什么 DuckDB 对优化器改动格外谨慎——测试套件里成千上万个查询是这条流水线的回归防线。

启发式的胜利不等于全局最优。 六组步骤里五组是启发式，它们各自局部最优，组合起来不保证全局最优。代价组件只管连接顺序、多阶段聚合和投影放置三处。剩下的大量决策靠的是三十年积累的工程直觉——这些直觉在 TPC-H 类负载上表现极好，在你的负载上未必。

估算错误会级联。 基数估计错一步，代价比较就可能选错连接顺序，而计划一旦定型，执行层没有纠错机制（连接过滤下推算一点补偿，但那是执行期的）。好在其成本模型只用基数，估计错误的爆炸半径有限；换成带 I/O 权重的复杂成本模型，一次错误估计的后果会严重得多。

把优化器看到这里，下一篇进入它下游的物理世界：物理算子怎么把 2048 个值一批地搬来搬去，以及流水线怎么把一份数据切给八个线程。