摘要Presto 的 CBO 是一个“全局优化器”吗为什么它借鉴 Cascades却没有把所有等价计划放进 Memo本文从 PlanOptimizers 流水线出发拆解 IterativeOptimizer、Memo、Rule、Stats、Cost 与 HBO揭开 Presto 如何把复杂的全局搜索变成多个可控的局部决策。引言一条 SQL 在 Presto 中被优化的过程并不是交给优化器跑一遍这么简单。Presto 的优化体系是一条串行的PlanOptimizers流水线计划依次流过有序排列的若干优化阶段每一站各自改写一部分然后交还下一站。流水线上混编着两类决策——依据代数定律的 RBO 与依据统计估计的 CBO此外还有一层不占据流水线站次的输入侧校正HBO。第一章先给出这条流水线的全景确定坐标系。了解了这条流水线之后本文重点描述其中的 CBO 骨架即IterativeOptimizer这一族实现。要理解一个 CBO 框架需要回答几个具体的问题同一条 SQL 的等价计划是一个组合爆炸的空间——例如仅 Join 顺序一项10 张表的排列就是 10! 量级。优化器如何组织这个空间才能既不重复计算又不遗漏候选计划树的节点是不可变对象immutable任何一次改写都要重建整棵树的祖先链。优化器如何在几秒钟内完成成百上千次改写而不被对象拷贝拖垮代价本身从哪里来统计信息的计算代价不低计划又在不断被改写——旧计划上算出的统计与代价凭什么在新计划上还有效这三个问题分别对应 CBO 框架的三大支柱搜索空间的组织Memo、候选计划的生成Rule、候选之间的裁决Stats Cost。本文沿着这条主线从 Cascades 的经典设计出发落到IterativeOptimizer的具体实现并特别关注 Presto 在教科书设计与工程落地之间做出的一系列取舍——尤其是它如何用串行流水线与受限规则集把搜索空间从运行时的赌注变成设计时的承诺。需要强调的是Presto 的整个 CBO 体系并不以找到全局最优计划为首要目标它追求的是受控的空间与时间尺度内的相对较优路径。因此文中凡提到最优都指这一意义上的相对最优而非全部等价计划中的全局最优。一、Presto 优化器体系串行的 PlanOptimizers 流水线在讨论 CBO 之前需要先确定坐标系Presto 并不存在一个全局 CBO 阶段。核心优化器本质上是一条串行的PlanOptimizers流水线——一个有序的PlanOptimizer列表其中既有纯粹的规则式优化器实现也有多个IterativeOptimizer实例后者每个只封装有限的一组规则在自己的 Memo 空间上做一次局部 CBO 探索然后交还计划由流水线的下一站继续处理。PlanNode ─►[ RBO 站 ]─►[ CBO 站 ]─►[ CBO 站 ]─►[ RBO 站 ]─►[ CBO 站 ]─► ... ─► 最终计划 确定性改写 受限规则集 受限规则集 确定性改写 受限规则集 | | | ▼ ▼ ▼ 每个规则集持有独立的 IterativeOptimizer 实例 和 Memo 空间也就是说代价驱动的探索被切分为若干个受控的小段嵌入在确定性的串行流程之中。这个设计从两个层面约束了搜索空间外层的流水线顺序是硬边界——每个阶段能看什么、能改什么由它在列表中的位置预先决定内层的规则集是软边界——每个 Memo 上 fixpoint 迭代的发散程度由该实例携带的规则数量决定。两层边界合在一起把搜索空间会不会爆炸这个 Cascades 最常被提及的风险从运行时的问题转换为设计时可以界定的范畴。代价是明确且被接受的流水线某一站做出的改写可能使另一站本可发现的更优形态永久不可达——Presto 追求的不是全局最优计划而是在受控的空间与时间尺度上的相对较优路径。这是贯穿后面所有实现细节的前提。1.1 流水线上的两类决策RBO 与 CBO流水线上各站做出决策的依据并不相同整体是RBO 与 CBO 的混编类型决策依据在 Presto 中的典型代表RBO代数定律与执行语义的必然要求与数据无关AddExchanges/AddLocalExchanges依据算子对数据分布的物理属性要求规划 Remote / Local Exchange谓词下推、列裁剪等结构性改写CBO基于统计的代价估计IterativeOptimizer实例上的一组受限规则如DetermineJoinDistributionType、ReorderJoins例如AddExchanges 体现的是典型的 RBO 决策它并不比较“Broadcast 还是 Repartition 哪个代价更低”而是根据下游算子要求的物理属性判断当前数据分布是否满足要求如果不满足就插入相应的 Exchange。这一决策主要由算子的执行语义与物理属性要求决定而不是由当前表有多少行、网络代价是多少来决定。而ReorderJoins是 CBO 阶段如何在受限空间内进行代价取舍的典型样本它先通过确定性的约束划定候选边界——JoinNodeFlattener 只展平 INNER Join展平数量受 joinLimit 限制并跳过已经确定 distribution type 的子树然后在这个受限集合上由JoinEnumerator枚举划分组合枚举时强制左集合包含首节点以规避Join(A,B)与Join(B,A)的对称重复最后使用CostProvider比较候选 Join 树的代价一次完整的示例见第八章。RBO 与 CBO 的混编发生在 PlanOptimizers 流水线层面而 CBO 阶段内部则通过确定性的搜索约束控制候选空间再由代价模型完成候选之间的取舍。这种分层设计使得 CBO 不必面对整个等价计划空间而只需在当前阶段允许探索的有限空间内进行代价比较。1.2 输入侧的第三种依据HBO除流水线上的两类决策之外Presto 还有一层基于历史执行的统计信息校正。需要注意它与 RBO、CBO 不在同一个维度上RBO 与 CBO 回答的是由谁、依据什么在流水线上做改写决策是结构层面的划分HBO 回答的是CBO 所依据的那个估计值从哪里来是输入层面的修正。换言之流水线的站次序列不会因为启用 HBO 而增减变化的只是 CBO 那一站读到的数字更准了一些详见 6.3。1.3 本文的范围本文聚焦上述体系中的 CBO 骨架从 Cascades 的经典设计第三章出发落到IterativeOptimizer的实现第四、五章展开它赖以决策的统计与代价基础设施第六章讨论 fixpoint 迭代的收敛保障第七章并以一个四表 Join 的完整示例把各机制跑通一遍第八章。流水线上纯粹的 RBO 阶段如AddExchanges依据物理属性规划 Exchange各有独立主题本文只在需要交代它与 CBO 的分工时提及。二、CBO 要解决什么问题在等价计划空间中取舍2.1 启发式规则的失效边界RBO 用一组确定性规则改写计划谓词下推、列裁剪、常量折叠……这类改写的正确性主要由关系代数与执行语义保证通常不需要依赖数据分布的统计估计。但另一类决策没有这种性质。典型的例子包括Join 数据分发方式。Broadcast Join 把一侧数据复制到所有 Worker代价与“数据量 × Worker 数”成正比Repartitioned Join 对两侧重新哈希分区代价与“两侧数据量”成正比。哪种方式更便宜取决于两侧的数据规模以及具体的代价模型参数——这正是DetermineJoinDistributionType需要回答的问题。Join 顺序。多表 Join 的执行代价对连接顺序高度敏感而顺序的取舍依赖于中间结果基数的估计其中等值 Join 的 Join Key NDV 是影响基数估算的关键统计量。一旦决策依据从逻辑必然变成数据特征优化器就必须回答一个新问题在一个等价的计划空间里如何系统地选出代价更低的那个这便是 CBO 需要回答的问题。2.2 三个子问题三大组件把上述命题拆开可以看到三个相互配合的核心问题子问题含义对应组件组织等价计划如何存放才能共享子结构、避免重复计算Memo空间生成等价候选从哪里来Rule转换规则 实现规则裁决候选之间如何比较Stats Cost统计与代价模型三者缺一不可没有 Memo每条等价改写都要复制整棵树没有 Rule空间里只有一个计划没有代价模型再大的空间也只能随机挑选。Presto 的实现沿用了 Cascades 的这套分工——而 Cascades 又源自上世纪 90 年代的 Volcano 体系这条谱系在工业界延续为 SQL Server、Orca 与 Calcite 的优化器框架。三、Cascades 框架Memo、Rule 与代价搜索3.1 Memo用等价类组织搜索空间Memo 的关键洞察是不同候选计划之间往往共享大量子结构。例如多个 Join 顺序不同的候选可能反复使用相同的 A ⋈ B、B ⋈ C 等子计划。如果让每个子计划只计算一次搜索空间就可以从“计划森林”压缩为“共享子结构的 DAG”。Memo 用Group等价类来表达这一点一个 Group 表示一组语义等价的表达式每个具体表达式的子节点则通过对其他 Group 的引用连接计划: A ── B ── C ── D └── E ── F Memo: G0: { A → G1 } G1: { B → [G2, G3] } G2: { C → G4 } G3: { E → G5 } G4: { D } G5: { F }在经典的 Cascades 中一个 Group 内会保留搜索过程中发现的等价表达式候选如G1 {Join(A,B), Join(B,A), HashJoin(A,B), MergeJoin(A,B), ...}逻辑候选与物理实现共存于同一等价类。这带来 DP 式的收益一个 Group 的最优计划算出一次即可缓存引用它的上层表达式可以直接复用——这正是 memoization 的本义。不过复用二字需要精确理解缓存的键不是 Group 本身而是Group, Required Properties。OptimizeGroup(G, RP, UB) 的优化上下文包含 Group、Required Properties 和 Cost Upper Bound但 winner 的缓存主要按 (Group, RP) 组织UB 是当前搜索的代价约束用于判断已有 winner 是否可以复用以及在不满足时继续搜索。这个限定并非小题大做。考虑一个 Group 内的两个候选P1代价 100 但输出无序P2代价 120 但输出按 k 有序。若父节点是要求输入有序的 Merge Join那么取最便宜的P1 补一个 Sort(60)合计 160反而不如直接采用P2的 120——单独看更贵的子计划在特定的父节点语境下可能给出更低的总代价。属性需求之所以必须参与 winner 的区分原因正在于此。3.2 Rule模式匹配驱动的候选生成等价候选由规则生成。规则由三部分构成Pattern模式描述可匹配的计划树形状如filter(x: project(any))命名绑定named arguments / capture把匹配到的子结构绑定为变量供规则体直接使用——Join(left, right)中的left、right绑定的就是实际计划中符合条件的子 Group规则体消费绑定产出零到多个新表达式。规则通常不需要通过一个固定的类型标签来区分从优化作用看可以概括为三类类型例子作用逻辑转换Join 交换律 / 结合律、谓词下推扩充逻辑等价空间物理实现LogicalJoin → HashJoin / NestedLoopJoin生成可执行计划属性强制在 Merge Join 之前强制排序建立物理属性要求3.3 代价搜索自顶向下触发自底向上聚合Cascades 的搜索方向常被概括为自顶向下但这个说法只对了一半。准确地说体系中存在两个方向规则展开 / 计划搜索 自顶向下 决定先优化哪个 Group 代价计算 自底向上 聚合子计划代价以得到父计划代价优化入口是optimize(rootGroup, costBound, requiredProperties)。表面上它从 Root Group 出发挑选候选表达式看起来是自顶向下的但任何一个表达式的代价都满足cost(Join(A, B)) local_cost(Join) best_cost(A) best_cost(B)best_cost(A)必须先算出来——于是优化器递归优化子 Group代价沿递归返回的方向自底向上聚合。最终行为是递归向下展开代价向上返回。那为什么不干脆用纯自底向上的动态规划两个原因剪枝的时机。自顶向下携带 cost bound代价上界可以在展开之前就放弃注定超界的分支不必探索整个搜索空间。具体机制是动态收紧的边界先用costBound优化左子树得到cost(L)再用costBound - cost(L)优化右子树最后用剩余边界约束当前节点。这构成了 branch-and-bound 式的剪枝机制物理属性的传递方向。required properties如输出需按 k 分区天然由父算子对子算子提出只能自顶向下传播。Cascades 是一个自顶向下触发 自底向上聚合的深度优先 DP 搜索框架。方向的选择并非随意为之而是由两件事决定何时能够剪枝以及物理属性沿哪个方向传递。四、Presto 的落地IterativeOptimizer 的组织与控制流以上介绍的是经典 Cascades 的基本搜索框架。Presto 的实际实现——IterativeOptimizer——保留了 Memo、Rule 和 Cost/Stats 这几个核心组件但在搜索空间组织和控制流上进行了明显的工程化简化。4.1 双轨入口IterativeOptimizer同时持有两套规则legacyRules传统的顺序重写优化器PlanOptimizer列表逐个应用newRulesCascades 风格的规则集合通过RuleIndex组织——一个从模式顶层算子类 → 规则的 multimap 索引。匹配某条规则时只需先按根节点类型过滤候选集避免了对全部规则的线性扫描。当会话未启用新优化器isNewOptimizerEnabled且存在 legacy 规则时走传统顺序路径否则进入 Cascades 风格的探索路径。需要说明的是IterativeOptimizer始终是 PlanOptimizers 流水线上的一站——而且在整个流水线中出现多次每次携带不同的规则集。它的探索范围因此受双重约束内层是本实例携带的规则集决定探索的发散程度外层是它在流水线中的位置前序阶段已经确定的形态不再重新考虑。这两层约束正是第一章所述搜索空间在设计期即可界定的具体含义。4.2 optimize() 的组织流程进入新路径后optimize()是整个 CBO 探索过程的入口。它首先为本次优化建立 Memo、RuleIndex、统计与代价 Provider 以及 Context 等基础设施然后从 Root Group 进入 exploreGroup() 的递归探索最终从 Memo 提取优化后的计划。optimize(plan, ...) │ ┌─────────────────┼────────────────┐ ▼ ▼ ▼ Memo RuleIndex Calculator │ │ │ ┌────────┴────────┐ │ ▼ ▼ │ StatsCalculator CostCalculator │ │ │ │ ▼ ▼ │ CachingStatsProvider CachingCostProvider │ └────────┬────────┘ │ │ └──────────────┬───────────────────┘ ▼ Context │ ▼ exploreGroup() │ ▼ memo.extract() │ ▼ 最终 PlanNode其中有两个值得注意的生命周期设计statsCalculator/costCalculator是全局单例依赖注入所有查询共享只负责怎么算CachingStatsProvider/CachingCostProvider是单次优化生命周期的缓存层内部是按引用判等的IdentityHashMap缓存算出来的结果生命周期与 Memo 一致——Memo 销毁缓存随之废弃。计算逻辑与计算缓存的分离使得缓存策略失效传播见 6.2可以完全内聚在 Provider 一侧。4.3 控制流exploreGroup 的 fixpoint 循环实际探索由三个方法构成递归的三角控制流exploreGroup(G) ← 整体控制器驱动当前子树整体收敛 │ ├── exploreNode(G) ← 对当前 Group 反复试规则直至局部收敛 │ └── while (有进展): exploreChildren(G) ── 递归 ──► exploreGroup(child) │ └── 子树变化后回到 exploreNode(G) ← 变化反馈父节点重新尝试exploreGroup的循环逻辑精确刻画了 fixpoint 语义先exploreNode对当前 Group 反复应用所有可匹配规则直到不再有规则触发局部收敛再exploreChildren递归优化所有子 Group。只要任何一个子树发生变化就返回当前 Group 重新执行exploreNode——因为子树变了父节点可能又能匹配新的规则了若父节点重试无进展跳出循环。Presto 新优化器框架整体上是一个自顶向下驱动 子树变化反馈 当前节点重试的 fixpoint 框架。收敛的判据不是所有规则都试过一遍而是再来一轮也不会有任何变化。4.4 规则执行与统计等价性的保持单条规则的执行在transform()中matcher.match(rule.getPattern(), node)先做模式匹配命中后调用rule.apply(match.value(), match.captures(), ruleContext(context))产出新节点最终通过memo.replace(group, transformedNode, ...)写回 Memo。一个容易被忽略、但在设计上颇有讲究的细节是statsEquivalentPlanNode 的保持如果规则改写了节点却没有显式声明统计等价信息框架会自动把原节点的统计等价声明迁移到新节点上。这维护了一个不变式——凡是规则没有明确声明“统计特征变了”的改写都默认视为统计上等价。统计缓存因此得以在大量纯结构性改写如变量重命名中安全复用。这条不变式的价值远不止缓存复用它同时也是 HBO 能够工作的前提——只有存在一个不随纯结构性改写漂移的统计身份当前计划节点才能在经过多轮优化改写后仍与历史执行中对应的计划节点建立关联从而复用其历史实测统计详见 6.3。五、Presto 的 Memo 数据结构单成员 Group 与引用计数5.1 GroupReference计划节点与 Group 的桥接Memo 将计划树中的计划节点分别组织到 Group 中其子节点被替换为GroupReference——一个形式上仍是 PlanNode、实质上指向 Group ID 的引用节点。这个设计让规则本身无需直接感知 Memo 的内部数据结构规则的 Pattern 匹配在普通 PlanNode 世界进行Lookup负责在 Group 引用与实际节点之间透明解析。5.2 引用计数与垃圾回收Group 维护incomingReferences谁引用了我。当改写使某个 Group 从根节点不可达时其引用计数可能归零Group 随之被级联删除这一机制更接近引用计数式的垃圾回收。memo.replace(G, newNode) │ ├── incrementReferenceCounts(newNode, G) ← 建立 G 到新子 Group 的引用 ├── membership newNode ← 替换 Group 当前成员 └── decrementReferenceCounts(oldNode, G) ← 撤销旧引用 │ └── 子 Group 引用计数归零 → deleteGroup → 递归清理其子引用5.3 关键差异单成员 Group这里存在一个关键差异。经典 Cascades 的 Group 可以保留搜索过程中发现的等价表达式候选并在这一搜索空间上进行 cost-guided exploration 与 branch-and-bound 剪枝而 Presto 的Memo.Group只保留一个字段privatePlanNodemembership;// 该分组当前关联的实际计划节点唯一memo.replace()的语义不是“往等价类里追加一个候选”而是**“用新节点覆盖当前成员”**。Group 退化成了一个可原地修改的槽位。Presto 的 Memo 不是搜索空间而是改写工作台它不保存“所有等价计划”供代价比较只保存“当前选定的形态”供继续改写。等价空间的枚举被放弃了换来的是实现简单、内存可控、调试可追踪。这个取舍的深层含义在于裁决权的下放既然框架不负责全空间枚举和统一的 branch-and-bound 搜索代价比较就主要下沉到具体规则中——例如DetermineJoinDistributionType从Rule.Context获取StatsProvider/CostProvider比较 Broadcast 与 Repartitioned 两种形态的代价ReorderJoins则在规则内部实现自己的 Join 顺序 DP。框架提供的是决策基础设施统计、代价、缓存而具体规则负责决策逻辑。反过来看单成员 Group 也使 3.1 节讨论的多 winner 问题不再出现在 Memo 层一个 Group 只维护一个当前成员因此不需要在同一 Group 内同时维护针对不同 Required Properties 的多个 winner。经典 Cascades 通过这种属性感知的 winner 复用扩大搜索与复用能力Presto 则不在 Memo 层维护这套机制而是将具体的属性与代价权衡下沉到规则内部在规则自己构造出的较小候选集上完成。六、统计与代价生产、缓存与失效传播6.1 计算链统计信息的计算链是典型的规则化计算 透明缓存两层结构StatsCalculator全局单例负责实际的统计信息计算 ├── ComposableStatsCalculator基础实现按根节点类型分派统计规则 │ └── RuleT: getPattern() calculate(node, sourceStats, ...) └── HistoryBasedPlanStatisticsCalculator启用 HBO 时的可选外壳 └── delegate ComposableStatsCalculator 先由 delegate 估算再用历史实测覆盖可用分量 StatsProvider单次优化生命周期向调用方提供统计信息 └── CachingStatsProvider提供缓存机制已算过的统计信息不用再算一遍 ├── GroupReference → memo.getStats(group) 命中即返回 └── 未命中 → statsCalculator.calculateStats(node, this, ...) → memo.storeStats(group, stats) 写回 MemoComposableStatsCalculator的分派逻辑与优化器的RuleIndex在组织方式上具有相似性都是先按计划节点类型缩小候选范围再选择适用的规则。也就是说统计推导本身也被建模为一套规则系统——Aggregation 的基数估计、Filter 的选择率推导各自是一条独立的统计规则。代价一侧的结构完全对称CostCalculator负责计算CachingCostProvider负责缓存于 Group此处不再赘述。6.2 失效传播改写如何使缓存作废计划被不断改写而统计与代价是针对特定计划形态算出来的。memo.replace()换掉 Group 的成员后旧统计立刻作废——而且不止本 Group任何以本 Group 为子节点的上层 Group其统计同样依赖这个子树也一并作废。evictStatisticsAndCost()实现了这个向上递归的失效传播memo.replace(G5, newNode) │ ▼ evictStatisticsAndCost(G5) ← G5.stats null, G5.cost null │ ├── 遍历 incomingReferences: {G2, G7} ├── evictStatisticsAndCost(G2) ← 引用本 Group 的父 Group 也失效 └── evictStatisticsAndCost(G7) ── 递归向上直到根反向引用边incomingReferences在此处发挥了第二个作用它不仅是 GC 的引用计数也是缓存失效的传播路径。子树一旦被改写沿引用边向上污染的所有相关统计被整体清除下次询问时按需重算。统计与代价不依附于计划树的数据结构而以 Group 为粒度旁挂在 Memo 上计划是主体统计是影子影子随主体改写而作废作废沿引用边向上蔓延。需要注意的是类似的失效机制也作用于 Logical Properties当计划结构发生变化时依赖该结构推导出的逻辑属性同样需要重新计算。这里不再展开。6.3 HBO让上一次的真实执行修正这一次的估计CBO 的精度瓶颈通常不在搜索而在输入。估计建立在一系列假设之上列间独立、取值均匀多表 Join 的选择率误差会被逐层放大若输入本身偏差过大再细致的搜索也难以选出合适的计划。HBOHistory Based Optimization正是对这一薄弱环节的补偿而它的接入方式相当克制——它不是流水线上的一个新阶段而是作用在 CBO 的输入侧HBO 不在流水线上占据新的阶段而是作用在 CBO 的统计输入侧。HistoryBasedPlanStatisticsCalculator内部持有一个 delegateStatsCalculator通常是ComposableStatsCalculator先用规则估算出delegateStats再用历史实测值覆盖其中可用的分量返回合并结果。流水线上的任何规则都不知道自己拿到的输入是算出来的还是跑出来的。要把第 N 次执行的经验迁移给第 N1 次查询先要解决一个身份问题计划树经历多轮优化改写之后如何认定这就是上次那个 Join这正与前文那条不变式相呼应——节点上的statsEquivalentPlanNode见 4.4提供不随纯结构性改写漂移的统计身份HistoricalStatisticsEquivalentPlanMarkingOptimizer在优化早期为各节点赋予该属性registerPlan()随即对每个节点做规范化并计算哈希CanonicalPlanGenerator按指定的PlanCanonicalizationStrategy生成规范化计划后序列化取摘要得到一个跨查询稳定的 key。匹配并非哈希相同即可。同一个计划在不同数据规模下输出行数可以相差几个数量级因此 HBO 还要比对输入表的统计信息只有当历史上那次执行的输入表统计与本次的偏差落在historyMatchingThreshold之内这条历史记录才被认为是可参考。命中且置信度大于零时delegateStats.combineStats(predicatedPlanStatistics, ...)用历史值覆盖对应的估计分量未命中则原样回退——HBO 的设计是增强而非替代历史统计不可用时仍回退到常规统计估计。写回侧构成闭环查询创建时HistoryBasedPlanStatisticsTracker通过addFinalQueryInfoListener挂到QueryExecution上执行完毕后把各规范化节点的实际统计写回HistoryBasedPlanStatisticsProvider可用 Redis、内存或空实现。一条跨越多次查询的反馈回路就此成型第 N 次查询 ── 执行 ──► 实际行数 / 数据量 │ addFinalQueryInfoListener 写回 ▼ 历史统计仓库按规范化计划哈希索引 │ 第 N1 次优化时读取 ▼ StatsCalculator 的估计值被实测值修正由此可以看清三者的关系——但它们并不处在同一个层次上RBO 主要依据规则与执行语义CBO 依据统计信息与代价模型HBO 则利用历史真实执行反馈修正统计估计。前两者是流水线上的两类决策确定性最强的先做估计驱动的取舍紧随其后而 HBO 不改变流水线的站次与顺序它只决定 CBO 拿到的那个估计值有多准。三者不是替代关系而是谁来做决策与决策依据从哪来这两个问题的不同答案。值得强调的是HBO 提高的是输入质量而不是空间覆盖它让同等规模搜索下的比较更准却不扩大被搜索的范围——较优向真正的最优推近一圈但受控空间的边界并未移动。七、收敛性fixpoint 的保障与最后的刹车规则驱动的 fixpoint 迭代首先需要回答一个问题如何防止规则组合把优化过程拖入无限迭代设计文档中列出了几类必须防范的情况不收敛的规则如limit(union(x)) → limit(union(limit(x)))规则输出会再次满足自身触发条件无限自激恒等改写规则产出与输入完全相同的表达式引擎原地打转重复触发union(union(union(x, y), z), w) → union(x, y, z, w)这类展平规则若不加以抑制会对每个子表达式不必要地重复触发匹配过程中的重复访问模式匹配在遍历计划结构时需要记录已访问的 Group避免同一 Group 被重复遍历。这些约束意味着写一条新规则时规则作者必须考虑它与现有规则组合后的收敛性。框架只提供两类兜底模式匹配的访问去重以及——最后的刹车——Context.checkTimeoutNotExhausted()。每次节点探索前检查耗时超过optimizer_timeout默认 3 分钟设置得较长是因为规则可能需要从 Connector 元数据获取信息即抛出异常终止优化。超时兜底的意义在于把最坏情况从优化器长时间空转降级为本次查询放弃优化——及早放弃而不是无限等待。还需要区分一点fixpoint 的收敛并不等于全局最优。 它只意味着在当前规则集合、搜索范围和探索过程下继续应用规则已经无法产生新的变化它并不构成对整个等价计划空间的最优性证明。这也是 Presto 与经典 Cascades 全局代价搜索模型之间的重要差异。八、示例一个四表 Join 如何被重排框架至此已经完整但还没有动起来。本章不再抽象地讨论组件而是让一个具体的 ReorderJoins 跑完整条链路Stats 提供输入Rule 生成候选内部 Memo 复用子问题Cost 完成候选裁决。接下来用一个最小例子把ReorderJoins的完整链路走一遍四张表A ⋈ B ⋈ C ⋈ D谓词为A.k B.k ∧ B.k C.k ∧ C.k D.k经过谓词下推后的基数估计为A 一千行B 十万行C 一万行D 五百万行。第一步 · 展平。JoinNodeFlattener将满足条件的连续 INNER Join 子树拆成 sources predicates最终形成MultiJoinNode。只有 INNER、deterministic、尚未确定 distribution type 且未超过 joinLimit 的 Join 才会继续展开否则整个子树作为一个 source 保留。第二步 · 划定空间。如果把 4 张表的左右顺序和二叉树形都分别计入理论上的有序 Join tree 数量是 120考虑 Join 交换律后对无方向的二叉 Join tree 可归并为 15 类。generatePartitions 生成左右子集合的划分并通过固定一个元素进入左集合消除左右交换产生的对称重复。第三步 · 递归与 memo。枚举对每个划分递归求解两侧对 4 张表而言理论上存在 11 个大小至少为 2 的子集合子问题。这些子问题通过JoinEnumerator内部的MapSetPlanNode, JoinEnumerationResult进行复用。第四步 · 剪枝。某划分两侧不存在可用于连接的跨侧 Join 条件返回INFINITE_COST_RESULT直接丢弃任一子问题无法得到可用的代价结果UNKNOWN_COST_RESULT则整个重排放弃并保留原始顺序宁可不改也不在代价信息不可靠时强行做选择。第五步 · 定价与选择。下面为了直观展示 Join reorder 的决策过程使用“移动行数”作为简化代价模型这不是 Presto 实际 CostCalculator 的完整计算公式。在这个简化模型下三个代表性候选候选形态关键中间结果累计代价A ⋈ (B ⋈ (C ⋈ D))C⋈D 50 万5,671,000A ⋈ ((B ⋈ C) ⋈ D)B⋈C 4 万5,152,200((A ⋈ B) ⋈ C) ⋈ DA⋈B 2 千 → 1 千5,114,000以第一行为例最内层C⋈D移动 1 万 500 万中间层B⋈(C⋈D)移动 10 万 50 万最外层移动 1 千 6 万合计 5,671,000。其余两行同理可验算。差距几乎全部来自 D 的位置让它先参与就得先把五百万行重分区让它最后参与届时中间结果只剩一千行。第六步 · 物理形态的二次选择。上表仍是逻辑层面的比较。setJoinNodeProperties还会为每个 Join 在 PARTITIONED 与 REPLICATED 之间再取一次 min最后一层左侧仅一千行在这个简化模型下若低于 broadcast 阈值改为 REPLICATED 之后代价约为一千 × Worker 数D 那一侧无需进行这一步的 repartition shuffle——总代价随之降到十万量级与最贵的候选相差近五十倍。注意这个规模一个数量级以上的收益产生在一个理论上只有 15 类无方向二叉 Join 结构、11 个非平凡子问题的搜索空间里。边界由JoinNodeFlattener的 INNER-only、deterministic 条件、已定 distribution type 的提前退出以及 joinLimit 共同划出边界之内DP 按子集合逐步计算候选代价并保留当前最优结果。九、总结规则生成候选代价完成裁决Memo 组织搜索回头看CBO 框架的三大支柱在 Presto 中的最终形态支柱经典 CascadesPresto IterativeOptimizer搜索空间全局统一的 memo 搜索空间串行流水线切分为多个受限的局部空间Memo等价类保留全部候选是搜索空间按Group、属性需求、上界缓存多份胜者单成员 Group是改写工作台无候选缓存Rule框架统一调度含代价边界剪枝fixpoint 重写裁决权下放到规则内部Costbranch-and-bound 全局搜索的评分函数StatsProvider/CostProvider作为规则可查询的基础设施收敛保障Memo 去重与搜索控制约束搜索范围流水线分段 规则自证收敛 超时兜底对照表背后的取舍可以归结为三个层面的收紧外层用串行的PlanOptimizers流水线把代价驱动的探索切成有限的几段每段只携带有限的规则集中层放弃全空间枚举与代价剪枝把框架简化为Memo 上的 fixpoint 重写引擎底层把裁决权下放到具体规则让每条代价敏感的规则ReorderJoins、DetermineJoinDistributionType……自带决策逻辑。代价是无法保证探索到全局最优的计划换来的是搜索空间在设计期即可界定、优化时间在运行期可约束、优化行为在故障时可追溯。这条路径在 Cascades 的思想谱系中有清楚的位置SQL Server、Orca 等实现采用统一的 Memo 搜索空间而 Presto 则选择了轻量的 Memo 化重写将搜索边界更多交给 PlanOptimizers 与具体 Rule。Calcite 则提供了不同类型的 Planner 实现可采用不同的优化策略。Memo 解决状态怎么存Rule 解决候选从哪来Cost 决定最终选哪个。CBO 的本质不是把代价算得多么准——统计永远只是估计——也不是把最优计划找出来——搜索空间永远只是全空间的一个受控切片——而是把这个计划为什么更好从直觉变成一条可计算、可复现、可失效的推导链。作者王冬PrestoDB Committer | Presto Iceberg Code OwnerGitHub: https://github.com/hantangwangdEmail: mingwbdgmail.com本文章同步发表于https://hantangwangd.github.io/zh/posts/2026-09-24-cbo-framework.html Presto 查询引擎内核详解：优化器体系与 CBO 框架——从 PlanOptimizers 流水线到 Memo 上的代价取舍
摘要Presto 的 CBO 是一个“全局优化器”吗为什么它借鉴 Cascades却没有把所有等价计划放进 Memo本文从 PlanOptimizers 流水线出发拆解 IterativeOptimizer、Memo、Rule、Stats、Cost 与 HBO揭开 Presto 如何把复杂的全局搜索变成多个可控的局部决策。引言一条 SQL 在 Presto 中被优化的过程并不是交给优化器跑一遍这么简单。Presto 的优化体系是一条串行的PlanOptimizers流水线计划依次流过有序排列的若干优化阶段每一站各自改写一部分然后交还下一站。流水线上混编着两类决策——依据代数定律的 RBO 与依据统计估计的 CBO此外还有一层不占据流水线站次的输入侧校正HBO。第一章先给出这条流水线的全景确定坐标系。了解了这条流水线之后本文重点描述其中的 CBO 骨架即IterativeOptimizer这一族实现。要理解一个 CBO 框架需要回答几个具体的问题同一条 SQL 的等价计划是一个组合爆炸的空间——例如仅 Join 顺序一项10 张表的排列就是 10! 量级。优化器如何组织这个空间才能既不重复计算又不遗漏候选计划树的节点是不可变对象immutable任何一次改写都要重建整棵树的祖先链。优化器如何在几秒钟内完成成百上千次改写而不被对象拷贝拖垮代价本身从哪里来统计信息的计算代价不低计划又在不断被改写——旧计划上算出的统计与代价凭什么在新计划上还有效这三个问题分别对应 CBO 框架的三大支柱搜索空间的组织Memo、候选计划的生成Rule、候选之间的裁决Stats Cost。本文沿着这条主线从 Cascades 的经典设计出发落到IterativeOptimizer的具体实现并特别关注 Presto 在教科书设计与工程落地之间做出的一系列取舍——尤其是它如何用串行流水线与受限规则集把搜索空间从运行时的赌注变成设计时的承诺。需要强调的是Presto 的整个 CBO 体系并不以找到全局最优计划为首要目标它追求的是受控的空间与时间尺度内的相对较优路径。因此文中凡提到最优都指这一意义上的相对最优而非全部等价计划中的全局最优。一、Presto 优化器体系串行的 PlanOptimizers 流水线在讨论 CBO 之前需要先确定坐标系Presto 并不存在一个全局 CBO 阶段。核心优化器本质上是一条串行的PlanOptimizers流水线——一个有序的PlanOptimizer列表其中既有纯粹的规则式优化器实现也有多个IterativeOptimizer实例后者每个只封装有限的一组规则在自己的 Memo 空间上做一次局部 CBO 探索然后交还计划由流水线的下一站继续处理。PlanNode ─►[ RBO 站 ]─►[ CBO 站 ]─►[ CBO 站 ]─►[ RBO 站 ]─►[ CBO 站 ]─► ... ─► 最终计划 确定性改写 受限规则集 受限规则集 确定性改写 受限规则集 | | | ▼ ▼ ▼ 每个规则集持有独立的 IterativeOptimizer 实例 和 Memo 空间也就是说代价驱动的探索被切分为若干个受控的小段嵌入在确定性的串行流程之中。这个设计从两个层面约束了搜索空间外层的流水线顺序是硬边界——每个阶段能看什么、能改什么由它在列表中的位置预先决定内层的规则集是软边界——每个 Memo 上 fixpoint 迭代的发散程度由该实例携带的规则数量决定。两层边界合在一起把搜索空间会不会爆炸这个 Cascades 最常被提及的风险从运行时的问题转换为设计时可以界定的范畴。代价是明确且被接受的流水线某一站做出的改写可能使另一站本可发现的更优形态永久不可达——Presto 追求的不是全局最优计划而是在受控的空间与时间尺度上的相对较优路径。这是贯穿后面所有实现细节的前提。1.1 流水线上的两类决策RBO 与 CBO流水线上各站做出决策的依据并不相同整体是RBO 与 CBO 的混编类型决策依据在 Presto 中的典型代表RBO代数定律与执行语义的必然要求与数据无关AddExchanges/AddLocalExchanges依据算子对数据分布的物理属性要求规划 Remote / Local Exchange谓词下推、列裁剪等结构性改写CBO基于统计的代价估计IterativeOptimizer实例上的一组受限规则如DetermineJoinDistributionType、ReorderJoins例如AddExchanges 体现的是典型的 RBO 决策它并不比较“Broadcast 还是 Repartition 哪个代价更低”而是根据下游算子要求的物理属性判断当前数据分布是否满足要求如果不满足就插入相应的 Exchange。这一决策主要由算子的执行语义与物理属性要求决定而不是由当前表有多少行、网络代价是多少来决定。而ReorderJoins是 CBO 阶段如何在受限空间内进行代价取舍的典型样本它先通过确定性的约束划定候选边界——JoinNodeFlattener 只展平 INNER Join展平数量受 joinLimit 限制并跳过已经确定 distribution type 的子树然后在这个受限集合上由JoinEnumerator枚举划分组合枚举时强制左集合包含首节点以规避Join(A,B)与Join(B,A)的对称重复最后使用CostProvider比较候选 Join 树的代价一次完整的示例见第八章。RBO 与 CBO 的混编发生在 PlanOptimizers 流水线层面而 CBO 阶段内部则通过确定性的搜索约束控制候选空间再由代价模型完成候选之间的取舍。这种分层设计使得 CBO 不必面对整个等价计划空间而只需在当前阶段允许探索的有限空间内进行代价比较。1.2 输入侧的第三种依据HBO除流水线上的两类决策之外Presto 还有一层基于历史执行的统计信息校正。需要注意它与 RBO、CBO 不在同一个维度上RBO 与 CBO 回答的是由谁、依据什么在流水线上做改写决策是结构层面的划分HBO 回答的是CBO 所依据的那个估计值从哪里来是输入层面的修正。换言之流水线的站次序列不会因为启用 HBO 而增减变化的只是 CBO 那一站读到的数字更准了一些详见 6.3。1.3 本文的范围本文聚焦上述体系中的 CBO 骨架从 Cascades 的经典设计第三章出发落到IterativeOptimizer的实现第四、五章展开它赖以决策的统计与代价基础设施第六章讨论 fixpoint 迭代的收敛保障第七章并以一个四表 Join 的完整示例把各机制跑通一遍第八章。流水线上纯粹的 RBO 阶段如AddExchanges依据物理属性规划 Exchange各有独立主题本文只在需要交代它与 CBO 的分工时提及。二、CBO 要解决什么问题在等价计划空间中取舍2.1 启发式规则的失效边界RBO 用一组确定性规则改写计划谓词下推、列裁剪、常量折叠……这类改写的正确性主要由关系代数与执行语义保证通常不需要依赖数据分布的统计估计。但另一类决策没有这种性质。典型的例子包括Join 数据分发方式。Broadcast Join 把一侧数据复制到所有 Worker代价与“数据量 × Worker 数”成正比Repartitioned Join 对两侧重新哈希分区代价与“两侧数据量”成正比。哪种方式更便宜取决于两侧的数据规模以及具体的代价模型参数——这正是DetermineJoinDistributionType需要回答的问题。Join 顺序。多表 Join 的执行代价对连接顺序高度敏感而顺序的取舍依赖于中间结果基数的估计其中等值 Join 的 Join Key NDV 是影响基数估算的关键统计量。一旦决策依据从逻辑必然变成数据特征优化器就必须回答一个新问题在一个等价的计划空间里如何系统地选出代价更低的那个这便是 CBO 需要回答的问题。2.2 三个子问题三大组件把上述命题拆开可以看到三个相互配合的核心问题子问题含义对应组件组织等价计划如何存放才能共享子结构、避免重复计算Memo空间生成等价候选从哪里来Rule转换规则 实现规则裁决候选之间如何比较Stats Cost统计与代价模型三者缺一不可没有 Memo每条等价改写都要复制整棵树没有 Rule空间里只有一个计划没有代价模型再大的空间也只能随机挑选。Presto 的实现沿用了 Cascades 的这套分工——而 Cascades 又源自上世纪 90 年代的 Volcano 体系这条谱系在工业界延续为 SQL Server、Orca 与 Calcite 的优化器框架。三、Cascades 框架Memo、Rule 与代价搜索3.1 Memo用等价类组织搜索空间Memo 的关键洞察是不同候选计划之间往往共享大量子结构。例如多个 Join 顺序不同的候选可能反复使用相同的 A ⋈ B、B ⋈ C 等子计划。如果让每个子计划只计算一次搜索空间就可以从“计划森林”压缩为“共享子结构的 DAG”。Memo 用Group等价类来表达这一点一个 Group 表示一组语义等价的表达式每个具体表达式的子节点则通过对其他 Group 的引用连接计划: A ── B ── C ── D └── E ── F Memo: G0: { A → G1 } G1: { B → [G2, G3] } G2: { C → G4 } G3: { E → G5 } G4: { D } G5: { F }在经典的 Cascades 中一个 Group 内会保留搜索过程中发现的等价表达式候选如G1 {Join(A,B), Join(B,A), HashJoin(A,B), MergeJoin(A,B), ...}逻辑候选与物理实现共存于同一等价类。这带来 DP 式的收益一个 Group 的最优计划算出一次即可缓存引用它的上层表达式可以直接复用——这正是 memoization 的本义。不过复用二字需要精确理解缓存的键不是 Group 本身而是Group, Required Properties。OptimizeGroup(G, RP, UB) 的优化上下文包含 Group、Required Properties 和 Cost Upper Bound但 winner 的缓存主要按 (Group, RP) 组织UB 是当前搜索的代价约束用于判断已有 winner 是否可以复用以及在不满足时继续搜索。这个限定并非小题大做。考虑一个 Group 内的两个候选P1代价 100 但输出无序P2代价 120 但输出按 k 有序。若父节点是要求输入有序的 Merge Join那么取最便宜的P1 补一个 Sort(60)合计 160反而不如直接采用P2的 120——单独看更贵的子计划在特定的父节点语境下可能给出更低的总代价。属性需求之所以必须参与 winner 的区分原因正在于此。3.2 Rule模式匹配驱动的候选生成等价候选由规则生成。规则由三部分构成Pattern模式描述可匹配的计划树形状如filter(x: project(any))命名绑定named arguments / capture把匹配到的子结构绑定为变量供规则体直接使用——Join(left, right)中的left、right绑定的就是实际计划中符合条件的子 Group规则体消费绑定产出零到多个新表达式。规则通常不需要通过一个固定的类型标签来区分从优化作用看可以概括为三类类型例子作用逻辑转换Join 交换律 / 结合律、谓词下推扩充逻辑等价空间物理实现LogicalJoin → HashJoin / NestedLoopJoin生成可执行计划属性强制在 Merge Join 之前强制排序建立物理属性要求3.3 代价搜索自顶向下触发自底向上聚合Cascades 的搜索方向常被概括为自顶向下但这个说法只对了一半。准确地说体系中存在两个方向规则展开 / 计划搜索 自顶向下 决定先优化哪个 Group 代价计算 自底向上 聚合子计划代价以得到父计划代价优化入口是optimize(rootGroup, costBound, requiredProperties)。表面上它从 Root Group 出发挑选候选表达式看起来是自顶向下的但任何一个表达式的代价都满足cost(Join(A, B)) local_cost(Join) best_cost(A) best_cost(B)best_cost(A)必须先算出来——于是优化器递归优化子 Group代价沿递归返回的方向自底向上聚合。最终行为是递归向下展开代价向上返回。那为什么不干脆用纯自底向上的动态规划两个原因剪枝的时机。自顶向下携带 cost bound代价上界可以在展开之前就放弃注定超界的分支不必探索整个搜索空间。具体机制是动态收紧的边界先用costBound优化左子树得到cost(L)再用costBound - cost(L)优化右子树最后用剩余边界约束当前节点。这构成了 branch-and-bound 式的剪枝机制物理属性的传递方向。required properties如输出需按 k 分区天然由父算子对子算子提出只能自顶向下传播。Cascades 是一个自顶向下触发 自底向上聚合的深度优先 DP 搜索框架。方向的选择并非随意为之而是由两件事决定何时能够剪枝以及物理属性沿哪个方向传递。四、Presto 的落地IterativeOptimizer 的组织与控制流以上介绍的是经典 Cascades 的基本搜索框架。Presto 的实际实现——IterativeOptimizer——保留了 Memo、Rule 和 Cost/Stats 这几个核心组件但在搜索空间组织和控制流上进行了明显的工程化简化。4.1 双轨入口IterativeOptimizer同时持有两套规则legacyRules传统的顺序重写优化器PlanOptimizer列表逐个应用newRulesCascades 风格的规则集合通过RuleIndex组织——一个从模式顶层算子类 → 规则的 multimap 索引。匹配某条规则时只需先按根节点类型过滤候选集避免了对全部规则的线性扫描。当会话未启用新优化器isNewOptimizerEnabled且存在 legacy 规则时走传统顺序路径否则进入 Cascades 风格的探索路径。需要说明的是IterativeOptimizer始终是 PlanOptimizers 流水线上的一站——而且在整个流水线中出现多次每次携带不同的规则集。它的探索范围因此受双重约束内层是本实例携带的规则集决定探索的发散程度外层是它在流水线中的位置前序阶段已经确定的形态不再重新考虑。这两层约束正是第一章所述搜索空间在设计期即可界定的具体含义。4.2 optimize() 的组织流程进入新路径后optimize()是整个 CBO 探索过程的入口。它首先为本次优化建立 Memo、RuleIndex、统计与代价 Provider 以及 Context 等基础设施然后从 Root Group 进入 exploreGroup() 的递归探索最终从 Memo 提取优化后的计划。optimize(plan, ...) │ ┌─────────────────┼────────────────┐ ▼ ▼ ▼ Memo RuleIndex Calculator │ │ │ ┌────────┴────────┐ │ ▼ ▼ │ StatsCalculator CostCalculator │ │ │ │ ▼ ▼ │ CachingStatsProvider CachingCostProvider │ └────────┬────────┘ │ │ └──────────────┬───────────────────┘ ▼ Context │ ▼ exploreGroup() │ ▼ memo.extract() │ ▼ 最终 PlanNode其中有两个值得注意的生命周期设计statsCalculator/costCalculator是全局单例依赖注入所有查询共享只负责怎么算CachingStatsProvider/CachingCostProvider是单次优化生命周期的缓存层内部是按引用判等的IdentityHashMap缓存算出来的结果生命周期与 Memo 一致——Memo 销毁缓存随之废弃。计算逻辑与计算缓存的分离使得缓存策略失效传播见 6.2可以完全内聚在 Provider 一侧。4.3 控制流exploreGroup 的 fixpoint 循环实际探索由三个方法构成递归的三角控制流exploreGroup(G) ← 整体控制器驱动当前子树整体收敛 │ ├── exploreNode(G) ← 对当前 Group 反复试规则直至局部收敛 │ └── while (有进展): exploreChildren(G) ── 递归 ──► exploreGroup(child) │ └── 子树变化后回到 exploreNode(G) ← 变化反馈父节点重新尝试exploreGroup的循环逻辑精确刻画了 fixpoint 语义先exploreNode对当前 Group 反复应用所有可匹配规则直到不再有规则触发局部收敛再exploreChildren递归优化所有子 Group。只要任何一个子树发生变化就返回当前 Group 重新执行exploreNode——因为子树变了父节点可能又能匹配新的规则了若父节点重试无进展跳出循环。Presto 新优化器框架整体上是一个自顶向下驱动 子树变化反馈 当前节点重试的 fixpoint 框架。收敛的判据不是所有规则都试过一遍而是再来一轮也不会有任何变化。4.4 规则执行与统计等价性的保持单条规则的执行在transform()中matcher.match(rule.getPattern(), node)先做模式匹配命中后调用rule.apply(match.value(), match.captures(), ruleContext(context))产出新节点最终通过memo.replace(group, transformedNode, ...)写回 Memo。一个容易被忽略、但在设计上颇有讲究的细节是statsEquivalentPlanNode 的保持如果规则改写了节点却没有显式声明统计等价信息框架会自动把原节点的统计等价声明迁移到新节点上。这维护了一个不变式——凡是规则没有明确声明“统计特征变了”的改写都默认视为统计上等价。统计缓存因此得以在大量纯结构性改写如变量重命名中安全复用。这条不变式的价值远不止缓存复用它同时也是 HBO 能够工作的前提——只有存在一个不随纯结构性改写漂移的统计身份当前计划节点才能在经过多轮优化改写后仍与历史执行中对应的计划节点建立关联从而复用其历史实测统计详见 6.3。五、Presto 的 Memo 数据结构单成员 Group 与引用计数5.1 GroupReference计划节点与 Group 的桥接Memo 将计划树中的计划节点分别组织到 Group 中其子节点被替换为GroupReference——一个形式上仍是 PlanNode、实质上指向 Group ID 的引用节点。这个设计让规则本身无需直接感知 Memo 的内部数据结构规则的 Pattern 匹配在普通 PlanNode 世界进行Lookup负责在 Group 引用与实际节点之间透明解析。5.2 引用计数与垃圾回收Group 维护incomingReferences谁引用了我。当改写使某个 Group 从根节点不可达时其引用计数可能归零Group 随之被级联删除这一机制更接近引用计数式的垃圾回收。memo.replace(G, newNode) │ ├── incrementReferenceCounts(newNode, G) ← 建立 G 到新子 Group 的引用 ├── membership newNode ← 替换 Group 当前成员 └── decrementReferenceCounts(oldNode, G) ← 撤销旧引用 │ └── 子 Group 引用计数归零 → deleteGroup → 递归清理其子引用5.3 关键差异单成员 Group这里存在一个关键差异。经典 Cascades 的 Group 可以保留搜索过程中发现的等价表达式候选并在这一搜索空间上进行 cost-guided exploration 与 branch-and-bound 剪枝而 Presto 的Memo.Group只保留一个字段privatePlanNodemembership;// 该分组当前关联的实际计划节点唯一memo.replace()的语义不是“往等价类里追加一个候选”而是**“用新节点覆盖当前成员”**。Group 退化成了一个可原地修改的槽位。Presto 的 Memo 不是搜索空间而是改写工作台它不保存“所有等价计划”供代价比较只保存“当前选定的形态”供继续改写。等价空间的枚举被放弃了换来的是实现简单、内存可控、调试可追踪。这个取舍的深层含义在于裁决权的下放既然框架不负责全空间枚举和统一的 branch-and-bound 搜索代价比较就主要下沉到具体规则中——例如DetermineJoinDistributionType从Rule.Context获取StatsProvider/CostProvider比较 Broadcast 与 Repartitioned 两种形态的代价ReorderJoins则在规则内部实现自己的 Join 顺序 DP。框架提供的是决策基础设施统计、代价、缓存而具体规则负责决策逻辑。反过来看单成员 Group 也使 3.1 节讨论的多 winner 问题不再出现在 Memo 层一个 Group 只维护一个当前成员因此不需要在同一 Group 内同时维护针对不同 Required Properties 的多个 winner。经典 Cascades 通过这种属性感知的 winner 复用扩大搜索与复用能力Presto 则不在 Memo 层维护这套机制而是将具体的属性与代价权衡下沉到规则内部在规则自己构造出的较小候选集上完成。六、统计与代价生产、缓存与失效传播6.1 计算链统计信息的计算链是典型的规则化计算 透明缓存两层结构StatsCalculator全局单例负责实际的统计信息计算 ├── ComposableStatsCalculator基础实现按根节点类型分派统计规则 │ └── RuleT: getPattern() calculate(node, sourceStats, ...) └── HistoryBasedPlanStatisticsCalculator启用 HBO 时的可选外壳 └── delegate ComposableStatsCalculator 先由 delegate 估算再用历史实测覆盖可用分量 StatsProvider单次优化生命周期向调用方提供统计信息 └── CachingStatsProvider提供缓存机制已算过的统计信息不用再算一遍 ├── GroupReference → memo.getStats(group) 命中即返回 └── 未命中 → statsCalculator.calculateStats(node, this, ...) → memo.storeStats(group, stats) 写回 MemoComposableStatsCalculator的分派逻辑与优化器的RuleIndex在组织方式上具有相似性都是先按计划节点类型缩小候选范围再选择适用的规则。也就是说统计推导本身也被建模为一套规则系统——Aggregation 的基数估计、Filter 的选择率推导各自是一条独立的统计规则。代价一侧的结构完全对称CostCalculator负责计算CachingCostProvider负责缓存于 Group此处不再赘述。6.2 失效传播改写如何使缓存作废计划被不断改写而统计与代价是针对特定计划形态算出来的。memo.replace()换掉 Group 的成员后旧统计立刻作废——而且不止本 Group任何以本 Group 为子节点的上层 Group其统计同样依赖这个子树也一并作废。evictStatisticsAndCost()实现了这个向上递归的失效传播memo.replace(G5, newNode) │ ▼ evictStatisticsAndCost(G5) ← G5.stats null, G5.cost null │ ├── 遍历 incomingReferences: {G2, G7} ├── evictStatisticsAndCost(G2) ← 引用本 Group 的父 Group 也失效 └── evictStatisticsAndCost(G7) ── 递归向上直到根反向引用边incomingReferences在此处发挥了第二个作用它不仅是 GC 的引用计数也是缓存失效的传播路径。子树一旦被改写沿引用边向上污染的所有相关统计被整体清除下次询问时按需重算。统计与代价不依附于计划树的数据结构而以 Group 为粒度旁挂在 Memo 上计划是主体统计是影子影子随主体改写而作废作废沿引用边向上蔓延。需要注意的是类似的失效机制也作用于 Logical Properties当计划结构发生变化时依赖该结构推导出的逻辑属性同样需要重新计算。这里不再展开。6.3 HBO让上一次的真实执行修正这一次的估计CBO 的精度瓶颈通常不在搜索而在输入。估计建立在一系列假设之上列间独立、取值均匀多表 Join 的选择率误差会被逐层放大若输入本身偏差过大再细致的搜索也难以选出合适的计划。HBOHistory Based Optimization正是对这一薄弱环节的补偿而它的接入方式相当克制——它不是流水线上的一个新阶段而是作用在 CBO 的输入侧HBO 不在流水线上占据新的阶段而是作用在 CBO 的统计输入侧。HistoryBasedPlanStatisticsCalculator内部持有一个 delegateStatsCalculator通常是ComposableStatsCalculator先用规则估算出delegateStats再用历史实测值覆盖其中可用的分量返回合并结果。流水线上的任何规则都不知道自己拿到的输入是算出来的还是跑出来的。要把第 N 次执行的经验迁移给第 N1 次查询先要解决一个身份问题计划树经历多轮优化改写之后如何认定这就是上次那个 Join这正与前文那条不变式相呼应——节点上的statsEquivalentPlanNode见 4.4提供不随纯结构性改写漂移的统计身份HistoricalStatisticsEquivalentPlanMarkingOptimizer在优化早期为各节点赋予该属性registerPlan()随即对每个节点做规范化并计算哈希CanonicalPlanGenerator按指定的PlanCanonicalizationStrategy生成规范化计划后序列化取摘要得到一个跨查询稳定的 key。匹配并非哈希相同即可。同一个计划在不同数据规模下输出行数可以相差几个数量级因此 HBO 还要比对输入表的统计信息只有当历史上那次执行的输入表统计与本次的偏差落在historyMatchingThreshold之内这条历史记录才被认为是可参考。命中且置信度大于零时delegateStats.combineStats(predicatedPlanStatistics, ...)用历史值覆盖对应的估计分量未命中则原样回退——HBO 的设计是增强而非替代历史统计不可用时仍回退到常规统计估计。写回侧构成闭环查询创建时HistoryBasedPlanStatisticsTracker通过addFinalQueryInfoListener挂到QueryExecution上执行完毕后把各规范化节点的实际统计写回HistoryBasedPlanStatisticsProvider可用 Redis、内存或空实现。一条跨越多次查询的反馈回路就此成型第 N 次查询 ── 执行 ──► 实际行数 / 数据量 │ addFinalQueryInfoListener 写回 ▼ 历史统计仓库按规范化计划哈希索引 │ 第 N1 次优化时读取 ▼ StatsCalculator 的估计值被实测值修正由此可以看清三者的关系——但它们并不处在同一个层次上RBO 主要依据规则与执行语义CBO 依据统计信息与代价模型HBO 则利用历史真实执行反馈修正统计估计。前两者是流水线上的两类决策确定性最强的先做估计驱动的取舍紧随其后而 HBO 不改变流水线的站次与顺序它只决定 CBO 拿到的那个估计值有多准。三者不是替代关系而是谁来做决策与决策依据从哪来这两个问题的不同答案。值得强调的是HBO 提高的是输入质量而不是空间覆盖它让同等规模搜索下的比较更准却不扩大被搜索的范围——较优向真正的最优推近一圈但受控空间的边界并未移动。七、收敛性fixpoint 的保障与最后的刹车规则驱动的 fixpoint 迭代首先需要回答一个问题如何防止规则组合把优化过程拖入无限迭代设计文档中列出了几类必须防范的情况不收敛的规则如limit(union(x)) → limit(union(limit(x)))规则输出会再次满足自身触发条件无限自激恒等改写规则产出与输入完全相同的表达式引擎原地打转重复触发union(union(union(x, y), z), w) → union(x, y, z, w)这类展平规则若不加以抑制会对每个子表达式不必要地重复触发匹配过程中的重复访问模式匹配在遍历计划结构时需要记录已访问的 Group避免同一 Group 被重复遍历。这些约束意味着写一条新规则时规则作者必须考虑它与现有规则组合后的收敛性。框架只提供两类兜底模式匹配的访问去重以及——最后的刹车——Context.checkTimeoutNotExhausted()。每次节点探索前检查耗时超过optimizer_timeout默认 3 分钟设置得较长是因为规则可能需要从 Connector 元数据获取信息即抛出异常终止优化。超时兜底的意义在于把最坏情况从优化器长时间空转降级为本次查询放弃优化——及早放弃而不是无限等待。还需要区分一点fixpoint 的收敛并不等于全局最优。 它只意味着在当前规则集合、搜索范围和探索过程下继续应用规则已经无法产生新的变化它并不构成对整个等价计划空间的最优性证明。这也是 Presto 与经典 Cascades 全局代价搜索模型之间的重要差异。八、示例一个四表 Join 如何被重排框架至此已经完整但还没有动起来。本章不再抽象地讨论组件而是让一个具体的 ReorderJoins 跑完整条链路Stats 提供输入Rule 生成候选内部 Memo 复用子问题Cost 完成候选裁决。接下来用一个最小例子把ReorderJoins的完整链路走一遍四张表A ⋈ B ⋈ C ⋈ D谓词为A.k B.k ∧ B.k C.k ∧ C.k D.k经过谓词下推后的基数估计为A 一千行B 十万行C 一万行D 五百万行。第一步 · 展平。JoinNodeFlattener将满足条件的连续 INNER Join 子树拆成 sources predicates最终形成MultiJoinNode。只有 INNER、deterministic、尚未确定 distribution type 且未超过 joinLimit 的 Join 才会继续展开否则整个子树作为一个 source 保留。第二步 · 划定空间。如果把 4 张表的左右顺序和二叉树形都分别计入理论上的有序 Join tree 数量是 120考虑 Join 交换律后对无方向的二叉 Join tree 可归并为 15 类。generatePartitions 生成左右子集合的划分并通过固定一个元素进入左集合消除左右交换产生的对称重复。第三步 · 递归与 memo。枚举对每个划分递归求解两侧对 4 张表而言理论上存在 11 个大小至少为 2 的子集合子问题。这些子问题通过JoinEnumerator内部的MapSetPlanNode, JoinEnumerationResult进行复用。第四步 · 剪枝。某划分两侧不存在可用于连接的跨侧 Join 条件返回INFINITE_COST_RESULT直接丢弃任一子问题无法得到可用的代价结果UNKNOWN_COST_RESULT则整个重排放弃并保留原始顺序宁可不改也不在代价信息不可靠时强行做选择。第五步 · 定价与选择。下面为了直观展示 Join reorder 的决策过程使用“移动行数”作为简化代价模型这不是 Presto 实际 CostCalculator 的完整计算公式。在这个简化模型下三个代表性候选候选形态关键中间结果累计代价A ⋈ (B ⋈ (C ⋈ D))C⋈D 50 万5,671,000A ⋈ ((B ⋈ C) ⋈ D)B⋈C 4 万5,152,200((A ⋈ B) ⋈ C) ⋈ DA⋈B 2 千 → 1 千5,114,000以第一行为例最内层C⋈D移动 1 万 500 万中间层B⋈(C⋈D)移动 10 万 50 万最外层移动 1 千 6 万合计 5,671,000。其余两行同理可验算。差距几乎全部来自 D 的位置让它先参与就得先把五百万行重分区让它最后参与届时中间结果只剩一千行。第六步 · 物理形态的二次选择。上表仍是逻辑层面的比较。setJoinNodeProperties还会为每个 Join 在 PARTITIONED 与 REPLICATED 之间再取一次 min最后一层左侧仅一千行在这个简化模型下若低于 broadcast 阈值改为 REPLICATED 之后代价约为一千 × Worker 数D 那一侧无需进行这一步的 repartition shuffle——总代价随之降到十万量级与最贵的候选相差近五十倍。注意这个规模一个数量级以上的收益产生在一个理论上只有 15 类无方向二叉 Join 结构、11 个非平凡子问题的搜索空间里。边界由JoinNodeFlattener的 INNER-only、deterministic 条件、已定 distribution type 的提前退出以及 joinLimit 共同划出边界之内DP 按子集合逐步计算候选代价并保留当前最优结果。九、总结规则生成候选代价完成裁决Memo 组织搜索回头看CBO 框架的三大支柱在 Presto 中的最终形态支柱经典 CascadesPresto IterativeOptimizer搜索空间全局统一的 memo 搜索空间串行流水线切分为多个受限的局部空间Memo等价类保留全部候选是搜索空间按Group、属性需求、上界缓存多份胜者单成员 Group是改写工作台无候选缓存Rule框架统一调度含代价边界剪枝fixpoint 重写裁决权下放到规则内部Costbranch-and-bound 全局搜索的评分函数StatsProvider/CostProvider作为规则可查询的基础设施收敛保障Memo 去重与搜索控制约束搜索范围流水线分段 规则自证收敛 超时兜底对照表背后的取舍可以归结为三个层面的收紧外层用串行的PlanOptimizers流水线把代价驱动的探索切成有限的几段每段只携带有限的规则集中层放弃全空间枚举与代价剪枝把框架简化为Memo 上的 fixpoint 重写引擎底层把裁决权下放到具体规则让每条代价敏感的规则ReorderJoins、DetermineJoinDistributionType……自带决策逻辑。代价是无法保证探索到全局最优的计划换来的是搜索空间在设计期即可界定、优化时间在运行期可约束、优化行为在故障时可追溯。这条路径在 Cascades 的思想谱系中有清楚的位置SQL Server、Orca 等实现采用统一的 Memo 搜索空间而 Presto 则选择了轻量的 Memo 化重写将搜索边界更多交给 PlanOptimizers 与具体 Rule。Calcite 则提供了不同类型的 Planner 实现可采用不同的优化策略。Memo 解决状态怎么存Rule 解决候选从哪来Cost 决定最终选哪个。CBO 的本质不是把代价算得多么准——统计永远只是估计——也不是把最优计划找出来——搜索空间永远只是全空间的一个受控切片——而是把这个计划为什么更好从直觉变成一条可计算、可复现、可失效的推导链。作者王冬PrestoDB Committer | Presto Iceberg Code OwnerGitHub: https://github.com/hantangwangdEmail: mingwbdgmail.com本文章同步发表于https://hantangwangd.github.io/zh/posts/2026-09-24-cbo-framework.html