本系列第 3/4 篇 · 优化器 / Cascades · 上一篇 · 下一篇

与 StarRocks Optimizer 对照（3–6 行）
optd 是教学向 Cascades：Memo / 任务调度 / Winner 表写得完整，便于看清搜索骨架。StarRocks 则是生产 Enforcer：Required Property 级联、Exchange/Sort 插入与 Cost 一并计入。读本篇抓「候选如何进 Memo、如何剪枝」；读 StarRocks Optimizer 抓「属性不满足时如何付账」。重复的 Memo 术语见系列第 1–2 篇，本文只保留与 DataFusion 落地相关的差异。

查询优化器（Query Optimizer）的计划质量受三个条件共同限制：规则能生成哪些合法候选，代价模型（Cost Model）如何比较候选，以及搜索预算允许探索多大空间。只跟踪 Filter 下推或 Join 交换，无法解释一条计划为何没有被选中；它可能代价更高，也可能从未进入搜索空间。

Cascades 用 Memo 共享等价子问题，通过动态规划（Dynamic Programming）复用子计划，并用分支限界（Branch-and-Bound）控制搜索量。实现这些机制需要同时维护：

• 哪些表达式具有相同关系语义；
• 哪些规则还没有在某个表达式上触发；
• 某个物理要求下有哪些可执行实现；
• 子计划的最优解何时可以复用；
• 当前最优代价能否剪掉尚未展开的分支；
• 当统计信息变化时，哪些搜索结果可以保留，哪些必须重新计算。

本文选择 optd 作为解剖对象。它的代码量远小于生产数据库优化器，却已经把计划表示、Memo、Transformation/Implementation Rule、Cost Model、属性推导、部分搜索、自适应反馈和 DataFusion Bridge 串成了一条可运行链路。更重要的是，它仍保留着一些没有被复杂工程包装掩盖的边界，适合回答两个互相补充的问题：

1. 如果从零实现一个现代 Cascades Optimizer，最小正确内核应该是什么？
2. optd 当前源码已经走到哪里，从教学原型走向生产系统还缺什么？

优化目标与接入路径

阅读范围与源码基线

optd 已打通等价表达式搜索与执行计划生成，但 GroupInfo 仍只有一个 Winner，Required Properties 尚未接入 Cascades 搜索。以下先沿 SQL 到执行计划的路径解释已有机制，再讨论自研时需要补齐的状态。

源码分析基线

本文的实现结论限定于下列源码快照，不代表 optd 后续版本。阅读时应优先对照提交中的类型和调用路径，而不是用早期设计文档替代当前实现。

optd 的文档保留了早期实现的设计说明，但当前代码已经发生过重要演进。例如文档中的关系与标量表达式共用一棵 RelNode，当前源码则拆成 PlanNode 与 PredNode；文档描述经典显式 Task Stack，当前 tasks2.rs 使用相互递归的异步任务并通过扩栈运行。本文以源码快照为准，并在涉及设计意图时再参考文档。

先定义优化器真正要解的问题

优化目标不是任意改写出一棵更小的树，而是在语义等价且满足物理要求的候选中选择低成本实现。连接重排（Join Reordering）同时改变子问题与中间基数，因而需要共享搜索空间和明确的子目标。

从一棵树到一个搜索空间

连接顺序（Join Order）和物理实现会产生相互组合的候选，复用等价子问题比复制整棵树更适合搜索。以三个表的内连接（Inner Join）为例：

1SELECT *
2FROM a
3JOIN b ON a.k = b.k
4JOIN c ON b.k = c.k;

输入逻辑计划可能是一棵左深树：

1Join(Join(Scan(a), Scan(b)), Scan(c))

但逻辑等价结构至少还包括：

1Join(Scan(a), Join(Scan(b), Scan(c)))
2Join(Scan(c), Join(Scan(b), Scan(a)))
3...

每个逻辑 Join 又可能对应 Nested Loop Join、Hash Join，未来还可能有 Merge Join；每个子计划还可能要求不同的 Distribution、Ordering 或 Partitioning。直接复制 Plan Tree 会产生大量重复子树，并让“同一个子问题的最佳解”难以复用。

Cascades 的关键转变是：不再问如何把当前树改得更好，而是问同一语义等价类中有哪些表达式，以及在一个物理要求下哪个表达式最便宜。

理想化的搜索子目标可以写成：

1Optimize(group_id, required_properties, upper_bound) -> Winner

• group_id：要实现哪一个关系语义；
• required_properties：父算子要求输出具有什么物理性质；
• upper_bound：超过多少代价就不值得继续搜索；
• Winner：满足要求且成本最低的物理表达式及其子 Winner。

这三个输入分别对应 Cascades 的三根支柱：Memo 等价类、物理属性（Physical Property）、基于代价的剪枝。

四个最小核心对象

最小搜索内核需要分别表达语义等价类、结构候选、变换和最优解，否则规则结果与代价结果会混在同一棵计划树中。下面的教学接口用四个对象表示这些职责：

 1struct Group {
 2    expressions: Vec<ExprId>,
 3    logical_properties: LogicalProperties,
 4    winners: HashMap<RequiredProperties, Winner>,
 5}
 6
 7struct MExpr {
 8    operator: Operator,
 9    children: Vec<GroupId>,
10    predicates: Vec<PredId>,
11}
12
13trait Rule {
14    fn matches(&self, expr: ExprId, memo: &Memo) -> Vec<Binding>;
15    fn apply(&self, binding: Binding) -> Vec<Expression>;
16}
17
18struct Winner {
19    expr_id: ExprId,
20    child_winners: Vec<WinnerKey>,
21    cost: Cost,
22    statistics: Statistics,
23}

这不是 optd 类型定义的原样复制，而是生产级心智模型。对照当前 optd 源码可以看到：Group、MemoPlanNode、Rule、WinnerInfo 都已经存在，但 winners 目前仍简化成一个 winner，尚未以 RequiredProperties 为 Key。

optd 的整体架构：优化器内核与执行引擎解耦

optd 将通用搜索、关系算子语义和执行引擎适配分开，因此替换代价模型不必修改 Memo，接入 DataFusion 也不必让内核依赖其计划类型。模块依赖如下：

 1DataFusion SQL / LogicalPlan
 2          │
 3          ▼
 4optd-datafusion-bridge
 5  into_optd.rs       DataFusion LogicalPlan → optd PlanNode
 6          │
 7          ▼
 8optd-datafusion-repr
 9  plan_nodes.rs      DataFusion 领域的算子与谓词类型
10  rules/             逻辑变换与物理实现规则
11  properties/        Schema、ColumnRef 等逻辑属性
12  cost/              基础代价与运行时自适应代价
13          │
14          ▼
15optd-core
16  nodes.rs           通用 Plan/Predicate 表示
17  cascades/memo.rs   Group、MExpr、去重与 Group Merge
18  cascades/tasks2.rs 搜索任务、规则触发、剪枝、Winner
19  cost.rs            CostModel 抽象
20          │
21          ▼
22optd-datafusion-bridge
23  from_optd.rs       optd Physical Plan → DataFusion ExecutionPlan
24  physical_collector 运行时 Cardinality 采集
25          │
26          ▼
27DataFusion ExecutionPlan

这个分层很值得自研优化器借鉴：

• optd-core 不知道 Scan、Join 或 DataFusion 的具体枚举，只要求 NodeType 能区分逻辑与物理算子；
• optd-datafusion-repr 定义领域模型、规则、属性和代价；
• optd-datafusion-bridge 负责边界翻译，不把 DataFusion 类型泄漏进 Memo；
• Advanced Cost 作为独立 crate 接入，说明统计估算可以替换，而不必改搜索内核。

所以“通用优化器框架”并不等于自己实现 SQL Parser、Catalog 和执行器。一个更现实的学习路径是：复用 DataFusion 生成合法 LogicalPlan，自己实现从关系代数（Relational Algebra）到物理计划之间的完整搜索。

全链路入口：SQL 如何进入并离开 optd

optd 的研究边界位于 DataFusion 的逻辑计划与执行计划之间。接入层决定哪些语义由 optd 处理，也决定规则产生的物理节点能否被执行器兑现。

接管 DataFusion 的 QueryPlanner

物理规划必须由 optd 独占，才能把生成的计划归因于它的规则与代价选择。optd-datafusion-bridge/src/lib.rs 中的 create_df_context 通过以下配置接管入口：

1if !use_df_logical {
2    session_config.options_mut().optimizer.max_passes = 0;
3    builder = builder.with_optimizer_rules(vec![]);
4}
5
6builder = builder.with_physical_optimizer_rules(vec![]);
7builder = builder.with_query_planner(optimizer.clone());

当 use_df_logical=false 时，DataFusion 自带的逻辑规则被关闭；DataFusion Physical Optimizer Rule 无论如何都会被清空；最终由 OptdQueryPlanner 接管物理规划。这样才能保证 Explain 中看到的 Join Reorder、物理算子选择与 Cost 都来自 optd，而不是两套优化器混合后的结果。

OptdQueryPlanner::create_physical_plan_inner 的主流程可以压缩为：

 1let mut optd_rel = ctx.conv_into_optd(logical_plan)?;
 2
 3if optimizer.is_heuristic_enabled() {
 4    optd_rel = optimizer.heuristic_optimize(optd_rel);
 5}
 6
 7let (group_id, optimized_rel, meta) =
 8    optimizer.cascades_optimize(optd_rel)?;
 9
10let physical_plan =
11    ctx.conv_from_optd(optimized_rel, meta).await?;

一条查询实际经历：

1DataFusion LogicalPlan
2  → optd Logical Plan
3  → Heuristic 规范化/子查询解关联
4  → Cascades Memo 搜索
5  → 提取 optd Physical Plan
6  → DataFusion ExecutionPlan

DML、DDL 等 optd 尚未支持的顶层计划会回退到 DefaultPhysicalPlanner。这是接入新执行引擎时应保留的工程策略：先明确支持矩阵，让未覆盖语义走可靠的 Fallback，而不是在搜索深处以 unimplemented! 暴露给用户。

为什么先有一轮 Heuristic Optimizer

确定性规范化可以减少 Memo 需要处理的表达式形状，但不应提前删除需要比较代价的候选。DatafusionOptimizer::default_heuristic_rules 主要处理：

• 无效 Project、Filter、Join、Limit 消除；
• Predicate 简化与 Project/Filter Merge；
• 重复 Sort/Aggregate 表达式消除；
• Dependent Join 消除与下推。

这说明 RBO 与 CBO 并不是二选一。确定性规范化放在 Memo 之前有三个好处：

1. 消除不会带来有价值备选的语法噪声；
2. 把相关子查询先转换为普通关系算子，降低 Cascades Rule 的状态空间；
3. 避免等价但形状不同的表达式过早污染 Memo。

但这条原则不能无限外推。像 Filter Pushdown、Join Reorder 这种变换可能改变中间结果基数，并与物理算子组合产生不同总代价，应该保留在 Memo 中比较，而不是在 Heuristic 阶段不可逆地覆盖原计划。

DataFusion LogicalPlan 到 optd PlanNode

计划转换必须保持列引用与输出模式一致；Join 的左右输入交换后，位置索引也必须变化。optd-datafusion-bridge/src/into_optd.rs 的转换覆盖范围如下：

这一层最重要的设计不是类型转换，而是建立优化器内部稳定的列引用语义。optd 使用位置索引：Join 条件中 [0, left_width) 属于左孩子，右侧从 left_width 开始。Join Commute 与 Join Assoc 改变孩子顺序时，必须同步重写列索引，否则结构上“等价”，语义上已经错误。

这也解释了为什么规则代码不能只移动 PlanNode：关系代数结构、谓词引用范围与输出 Schema 必须一起保持不变量。

计划表示与 Memo：搜索期间保存什么

计划表示：为什么 Plan 与 Predicate 要分开

关系节点与标量谓词采用不同的引用体系，使 Memo 可以共享关系子问题而不把每个谓词都当成关系等价类。optd-core/src/nodes.rs 定义如下：

 1pub enum PlanNodeOrGroup<T> {
 2    PlanNode(ArcPlanNode<T>),
 3    Group(GroupId),
 4}
 5
 6pub struct PlanNode<T: NodeType> {
 7    pub typ: T,
 8    pub children: Vec<PlanNodeOrGroup<T>>,
 9    pub predicates: Vec<ArcPredNode<T>>,
10}
11
12pub struct PredNode<T: NodeType> {
13    pub typ: T::PredType,
14    pub children: Vec<ArcPredNode<T>>,
15    pub data: Option<Value>,
16}

它把两类边分开：

1PlanNode.children    关系输入，可以是完整子树，也可以是 Memo Group 占位符
2PlanNode.predicates  算子参数，始终是完整的标量表达式树

在 DataFusion 领域中，DfNodeType 包含 Logical/Physical Scan、Projection、Filter、Join、Sort、Agg、Limit 等关系算子；DfPredType 包含 ColumnRef、Constant、BinOp、LogOp、Func、Cast、Like、InList、SortOrder 等标量节点。

这种拆分比“所有内容都是 RelNode”更利于保持边界：

• Memo 的关系等价类只围绕 Plan Child 建立；
• Predicate 可以单独 Intern，多个 MExpr 共享同一条件；
• Rule Matcher 可以明确匹配算子形状，而不是误把表达式子树当关系输入；
• Schema 和 Cardinality 沿关系边传播，表达式类型与引用分析沿谓词树传播。

当前限制也同样明确：PredNode 会被 Intern，但不会像关系算子一样进入 Cascades 等价搜索。因此常量折叠、布尔规范化、表达式公共子表达式、不同函数实现选择，主要依赖 Heuristic Rule 或执行引擎，而不是统一的 Memo 搜索。

Memo：Cascades 的真正内核

Memo 通过结构去重和等价类合并共享子问题，减少重复搜索；代价是必须维护引用、属性和最优解之间的一致性。后续规则与任务都依赖这些不变量。

Group、MExpr 与 Pred

Memo 用子 Group 引用替代具体子树，因此多个父候选可以共享同一子问题。optd-core/src/cascades/memo.rs 中的关系表达式只保存这些引用：

1pub struct MemoPlanNode<T: NodeType> {
2    pub typ: T,
3    pub children: Vec<GroupId>,
4    pub predicates: Vec<PredId>,
5}

这就是 Cascades 论文中的 MExpr。三个标识符分别表示：

例如同一个 Group 可能包含：

1Group !31
2  expr 8  : Filter(!6, #0 = #2)
3  expr 15 : Join(Inner, !2, !2, #0 = #2)
4  expr 25 : PhysicalNestedLoopJoin(!2, !2, #0 = #2)
5  expr 28 : PhysicalHashJoin(!2, !2, left=[#0], right=[#0])

这里 Filter(CrossJoin) 与 InnerJoin 来自逻辑变换，NLJ 与 HashJoin 来自实现规则。它们共享同一输出 Schema 和关系语义，所以进入同一 Group；但只有物理表达式有资格成为最终 Winner。

插入：先递归 Memoize 孩子，再做结构去重

结构去重依赖孩子已经获得规范化的 GroupId，因而插入必须先处理孩子，再处理父表达式。NaiveMemo::add_new_group_expr_inner 按以下顺序执行：

1完整 PlanNode
2  → 递归把每个 Plan Child 插入 Memo，得到 children_group_ids
3  → 把 Predicate Intern 成 pred_ids
4  → 构造 MemoPlanNode(operator, child groups, pred ids)
5  → 查询 expr_node_to_expr_id 做结构去重
6  → 新表达式：创建 ExprId，并加入目标 Group 或新 Group
7  → 已存在表达式：复用 ExprId，必要时触发 Group Merge

结构去重的 Key 是整个 MemoPlanNode。因此只要 Operator、Child Group 和 Predicate 都相同，它就是同一个 MExpr，不会因为由不同规则生成而重复占用搜索空间。

规则结果为什么必须加入原 Group

Transformation Rule 声明的是语义等价关系。若规则把：

1(A Join B) Join C

转换为：

1A Join (B Join C)

新根表达式必须插回旧根的 Group。tasks2.rs 在应用规则后调用：

1self.optimizer.add_expr_to_group(expr, group_id)

这行代码是规则契约的落点：Rule 的返回值不是一棵用来覆盖旧树的新树，而是“同一语义的又一种表达方式”。 如果 Rule 实际上不等价，整个 Group 的逻辑属性（Logical Property）与 Winner 都会失去意义。

Group Merge：等价关系会向父节点传播

如果新表达式已经存在于另一个 Group，两个 Group 必须合并。当前 NaiveMemo::merge_group_inner 会：

1. 把被合并 Group 的全部 Expr 移到目标 Group；
2. 合并已有 Winner，保留代价更低者；
3. 更新旧 Group 到新 Group 的重定向映射；
4. 遍历所有父 MExpr，把 Child GroupId 改为合并后的 ID；
5. 如果父 MExpr 因此结构重复，继续合并父 Group。

这说明等价类不是局部容器，而是一张带父子引用的图。孩子等价会导致父表达式相同，父 Group 也可能发生级联合并。

当前实现故意命名为 NaiveMemo：Group 重定向仍使用映射并全量更新，源码也留下使用 Union-Find 等结构优化的注释。生产系统还需要 Parent Index、并发安全、稳定 ID、增量失效和更高效的 Duplicate Detection，但这些都是在相同语义模型上的工程增强。

逻辑属性属于 Group，而不是 MExpr

逻辑属性（Logical Property）必须描述整个等价类，而不能随候选结构变化。当前 Group 在创建时通过第一个 MExpr 推导属性：

1pub struct Group {
2    group_exprs: HashSet<ExprId>,
3    info: GroupInfo,
4    properties: Arc<[Box<dyn LogicalProperty>]>,
5}

当前 DataFusion Repr 注册两个 Logical Property Builder：

• SchemaPropertyBuilder：输出列名、类型、Nullable；
• ColumnRefPropertyBuilder：输出列追溯到哪个 Base Table Column，并维护等值列相关性。

逻辑属性只在 Group 初始化时计算一次，后续等价表达式共享。这其实提供了一个很强的 Rule 校验思路：如果一条新表达式加入 Group 后推导出的 Schema、Column Lineage 或其他逻辑属性与 Group 不一致，说明规则很可能破坏了语义等价。当前实现相信 Rule 的正确性，没有对每次插入重新验证；自研版本可以在 Debug 模式增加这一断言。

从规则到 Winner：走通一次搜索

规则系统：结构匹配只是开始，语义维护才是难点

规则只有同时保持输出列、谓词绑定和连接语义，才能向原 Group 添加候选。Memo 信任这种等价性声明，不会替规则证明结果正确。

Transformation Rule 与 Implementation Rule

逻辑变换负责扩展等价空间，物理实现负责产生可执行候选；两类规则的调度时机不同。optd 用 is_impl_rule 在统一接口中区分它们：

1pub trait Rule<T, O> {
2    fn matcher(&self) -> &RuleMatcher<T>;
3    fn apply(&self, optimizer: &O, binding: ArcPlanNode<T>)
4        -> Vec<PlanNodeOrGroup<T>>;
5    fn name(&self) -> &'static str;
6    fn is_impl_rule(&self) -> bool { false }
7}

两类规则的职责必须区分：

探索子 Group 时只触发 Transformation Rule，因为此时目标是补齐上层 Rule 可能匹配的逻辑 Binding；真正优化 Group 时才触发 Implementation Rule。这个差异避免了为了匹配一个逻辑规则，提前把整个子树的物理实现全部展开。

Matcher 如何从 Memo 中还原 Binding

Memo 中一个孩子引用可能对应多个候选，规则匹配因此需要枚举 Binding，而不是只检查一棵树。当前 RuleMatcher 提供以下形态：

1MatchNode / MatchDiscriminant
2Any
3AnyMany

以 Join Associativity 为例：

1define_rule!(
2    JoinAssocRule,
3    apply_join_assoc,
4    (Join(JoinType::Inner), (Join(JoinType::Inner), a, b), c)
5);

Matcher 先锁定根 MExpr，再进入左 Child Group，枚举该 Group 内所有能匹配 Inner Join 的 MExpr。对于嵌套孩子，它递归匹配；对于 Any，只保留 Group 占位符。多个孩子的匹配结果最后做笛卡尔积，形成完整 Binding。

这套实现直观，但也揭示了规则爆炸的来源：

1父规则 Binding 数
2  = Child Group 1 的匹配数
3  × Child Group 2 的匹配数
4  × ...

optd 在单次规则得到至少 200 个 Binding 时记录警告，但当前仍会先物化全部 Binding。生产实现通常需要 Lazy Iterator、Promise/Rule Priority、Binding 上限，以及更细粒度的 Pattern Index。

Join Commute：移动孩子只是最简单的一半

rules/joins.rs 中的交换规则不是简单返回 Join(right, left)。它还要：

1. 获取左右输入 Schema 宽度；
2. 重写 Join Condition 中的列索引；
3. 在交换后的 Join 上增加 Projection；
4. 用 Projection 恢复原始输出列顺序。

可以抽象为：

1A columns: [0, a_width)
2B columns: [a_width, a_width + b_width)
3
4交换后条件索引：
5  A.col(i) → b_width + i
6  B.col(j) → j - a_width
7
8交换后输出：[B..., A...]
9恢复输出：  Project[A..., B...]

Projection 不是多余节点，而是让新表达式继续满足原 Group 输出 Schema 的必要条件。后续 ProjectionPullUpJoin、ProjectMergeRule 等规则再负责消除或移动它。

Join Assoc：只有可安全迁移的谓词才能结合

连接结合律只能迁移引用范围仍合法的谓词；改变树形后留下越界列引用，会破坏关系语义。当前实现支持以下变换：

1(A Join B on cond1) Join C on cond2
2  →
3A Join (B Join C on rewrite(cond2)) on cond1

它尝试把 cond2 的列引用去掉 A 的宽度。如果 cond2 引用了 A，rewrite_column_refs 返回 None，规则直接放弃。也就是说，规则不是看到形状就生效，还要证明谓词只依赖 B、C，能够安全迁移到新内层 Join。

当前规则仅处理 Inner Join，恰好说明一个普遍原则：Outer Join、Semi/Anti Join 的交换结合受 Null-Generating Side、谓词来源与输出列语义限制，不能把 Inner Join 代数定律直接复用。

HashJoinRule：物理实现规则也需要能力检查

Hash Join 的实现规则必须检查执行器支持的连接类型和键表达式，不能把任意 Join 都物理化为 Hash Join。HashJoinRule 当前只接受：

• Inner Join；
• 一个等值条件，或连续 AND 连接的等值条件；
• 等值两侧最终都是 ColumnRef；
• 一侧列来自左 Schema，另一侧来自右 Schema。

它把全局 Join 列索引改写成左右孩子各自的局部索引，再生成：

1PhysicalHashJoin(
2  left_group,
3  right_group,
4  left_keys=[...],
5  right_keys=[...]
6)

不满足条件时返回空结果，逻辑 Join 仍可由通用 Physical Conversion Rule 转为 Nested Loop Join。这保证了“Hash Join 不适用”不会等于“查询无法执行”。

但当前能力边界也很清晰：非 Inner Hash Join、表达式 Join Key、Residual Join Filter、Build/Probe 方向选择、Broadcast/Shuffle 模式都没有进入该规则的候选空间。

搜索任务：Cascades 如何把规则与动态规划串起来

搜索任务将候选生成与候选评价交错执行，避免必须先生成完整规则闭包才能计价。已有 Winner 提供上界，规则继续补充可能更便宜的表达式。

当前实现不是文档中的显式 Task Stack

该快照通过递归异步函数执行搜索任务，并未采用显式任务队列；async 在这里也不意味着并行搜索。经典 Cascades 的任务依赖仍可表示为：

1OptimizeGroup
2  → OptimizeExpression
3    → ExploreGroup
4    → ApplyRule
5    → OptimizeInputs

当前源码 optd-core/src/cascades/tasks2.rs 保留了相同任务语义，但使用相互递归的 async fn。fire_optimize_tasks 通过 stacker::grow 提供 32 MB 栈，再用 pollster 同步运行 Future。

这对理解算法很友好，因为源码调用关系与伪代码接近；对生产实现则意味着后续应考虑显式 Worklist，以降低深递归的栈占用，并支持任务优先级、暂停恢复、并行搜索与更完整的 Trace。

OptimizeGroup：先评价已有物理表达式，再展开逻辑表达式

先评价已有物理候选可以尽早取得代价上界，再用该上界剪掉更贵的逻辑扩展。optimize_group_inner 的顺序是：

1if group already explored: return
2mark group explored
3
4for physical expr in group:
5    OptimizeInput(expr)
6
7for logical expr in group:
8    OptimizeExpr(expr, exploring=false)

先评价物理表达式可以尽早得到一个 Winner Upper Bound，后续新物理候选就能用它剪枝。随后处理逻辑表达式，规则产生的新物理 MExpr 会立刻进入 OptimizeInput，产生更好的 Winner 后又会收紧 Upper Bound。

OptimizeExpr：Rule Fired Set 是搜索状态的一部分

每个 (ExprId, RuleId) 只触发一次。优化器维护：

1fired_rules: HashMap<ExprId, HashSet<RuleId>>

OptimizeExpr 先检查根 Operator 是否可能匹配 Rule，再探索 Child Group，最后调用 ApplyRule。探索模式下跳过 Implementation Rule，预算耗尽后跳过 Transformation Rule。

Rule Fired Set 很重要：没有它，Join Commute 可能在 A Join B 与 B Join A 之间无限往复；仅依赖 Memo 去重仍会反复做匹配和 Apply。Fired Set 把“这个表达式上的这条推导已经尝试过”显式记录下来。

ApplyRule：新表达式被递归纳入同一次搜索

规则产物必须重新进入搜索，才能从新增逻辑结构继续生成物理实现。ApplyRule 的关键步骤是：

1检查 disabled / fired
2  → 标记 fired
3  → 从 Memo 枚举 Binding
4  → 执行 Rule.apply
5  → 把结果加入原 Group
6  → 新 Logical Expr：OptimizeExpr
7  → 新 Physical Expr：OptimizeInput

因此 Cascades 不是“先生成完全部逻辑计划，再统一物理化”。逻辑扩展与物理评价交错发生，新的低成本 Winner 可以尽早反过来剪掉后续搜索。

OptimizeInput：自底向上的 Cost 与自顶向下的 Upper Bound

父节点需要孩子的统计和代价才能计价，孩子又受到父节点剩余预算约束。OptimizeInput 将这两个方向的信息传递结合起来，依次优化物理 MExpr 的每个 Child Group：

1parent upper bound
2  ├── 已知 operator cost
3  ├── 已决定 child cost
4  └── 当前处理 child 的可用预算

源码中的子节点上界近似为：

1child_upper_bound
2  = parent_upper_bound
3  - cost_so_far
4  + current_child_cost

如果 cost_so_far > upper_bound，当前物理表达式直接被剪掉。所有孩子都有 Winner 后，再完整计算：

1operation_cost = Cost(operator, child_statistics)
2total_cost     = operation_cost + sum(child_total_cost)
3statistics     = DeriveStatistics(operator, child_statistics)

若 weighted(total_cost) 更低，就覆盖 Group Winner。

这里同时存在两种信息流：

1Upper Bound：父 → 子，用于限制搜索
2Cost/Statistics：子 → 父，用于动态规划

这正是 Cascades 与简单 Bottom-Up DP 的区别：它不仅复用子问题最优解，还通过父问题的当前最好解主动限制子问题探索。

当前剪枝仍是保守的简化版本。源码 TODO 明确指出，尚未把“未决定孩子的 Lower Bound”加入 cost_so_far；它们暂时按零计算。因此当前实现可能少剪枝，但不会仅因为这一点错误剪掉更优计划。

Cost、Statistics 与 Winner：最优计划如何被选出

代价最小只对已生成的合法候选和当前模型成立。统计向父节点传递规模信息，Cost 将工作量映射为排序依据，Winner 缓存两者以支持动态规划。

CostModel 的职责边界

统计估算与工作量计价必须分开，因为输出行数要供父节点使用，局部代价则参与候选排序。optd-core/src/cost.rs 将二者定义为不同接口：

 1fn compute_operation_cost(
 2    node,
 3    predicates,
 4    children: &[Option<&Statistics>],
 5    context,
 6    optimizer,
 7) -> Cost;
 8
 9fn derive_statistics(
10    node,
11    predicates,
12    children: &[&Statistics],
13    context,
14    optimizer,
15) -> Statistics;

此外还提供 zero、accumulate、sum、weighted_cost 和 Explain。这里刻意把两件事分开：

• Statistics 描述数据规模与分布，是父节点估算的输入；
• Cost 描述执行工作量，用于候选排序。

同样的 Cardinality 可以映射为不同硬件下的 CPU、I/O、Network、Memory 或 Latency Cost；同样的 Operator Cost 也可能因为并发度和资源约束产生不同最终排序。

基础 Cost Model 的公式

基础代价模型适合验证搜索流程，不足以预测真实执行时间：它采用固定选择率，且未表达网络、内存或并发争用。optd-datafusion-repr/src/cost/base_cost.rs 使用二维 Cost：

1Cost = [compute_cost, io_cost]
2weighted_cost = compute_cost + io_cost

主要公式可以整理为：

这套公式显然不是生产模型。例如 Filter Selectivity 固定为 1%，基础 Limit 的 Cardinality 没有使用 fetch，Hash Join 的输出行数取两侧最小值。但它已经足以验证搜索内核：当 Join Order 改变中间基数时，总代价会变化；Hash Join 与 NLJ 也会因为复杂度差异产生稳定排序。

一个好的学习顺序正是如此：先让 Cost Model 简单到可以手算，验证 Memo 与 Winner；再逐步增加统计精度，而不是从一开始就把 Histogram、NDV 和相关性全部塞进系统。

Winner 记录的不是一个 ExprId

Winner 必须同时保存累计代价和输出统计，父节点才能复用子问题结果，而不只是复用一个表达式编号。当前 WinnerInfo 保存：

1pub struct WinnerInfo {
2    pub expr_id: ExprId,
3    pub total_weighted_cost: f64,
4    pub operation_weighted_cost: f64,
5    pub total_cost: Cost,
6    pub operation_cost: Cost,
7    pub statistics: Arc<Statistics>,
8}

它同时保留局部代价、累计代价和输出统计，便于：

• 父节点复用子节点累计 Cost；
• Explain 区分某个算子自身贵，还是孩子贵；
• 父节点基于子 Statistics 估算自己；
• 自适应重优化时清空 Winner 后重新计算。

不过当前 GroupInfo 只有一个 winner: Winner。如果一个 Group 同时需要：

1Winner[Ordering = (a)]
2Winner[Distribution = Hash(a)]
3Winner[Distribution = Single]

单一 Winner 无法表达这些互不可替代的最优解。这也是后文生产化路线中第一优先级要修改的数据结构。

用一条真实 Memo Trace 手算 Winner

手算测试中的 Winner 可以验证局部代价如何沿计划累计，但不能充当真实性能测量。optd 自带的 optd-sqlplannertest/tests/utils/memo_dump.planner.sql 使用以下自连接：

1SELECT *
2FROM t1 AS a, t1 AS b
3WHERE a.t1v1 = b.t1v1
4ORDER BY a.t1v1;

最终 optd Physical Plan 是：

1PhysicalSort
2├── exprs: SortOrder(Asc, #0)
3└── PhysicalHashJoin(Inner)
4    ├── left_keys:  [#0]
5    ├── right_keys: [#0]
6    ├── PhysicalScan(t1)
7    └── PhysicalScan(t1)

Memo Trace 中，两个别名 Scan 共享相同表语义并复用 Group !2。连接语义最后收敛到 Group !31，其中同时包含 Filter + Cross Join、Logical Join、Physical NLJ、Physical Hash Join，以及 Join Commute 产生的 Projection 组合。

基础模型缺省认为每次 Scan 1000 行：

1Scan(t1) operation cost = {compute=0, io=1000}
2两个 Scan total         = {compute=0, io=2000}

Hash Join 的局部代价为：

12 × left_rows + right_rows
2= 2 × 1000 + 1000
3= 3000 compute

所以连接 Group 的 Hash Join Winner：

1total = children 2000 IO + operator 3000 compute
2      = weighted_cost 5000

NLJ 则需要约 1000 × 1000 级别计算，Trace 中总加权代价为 1,003,000，因此很快被 Hash Join 取代。

Hash Join 输出仍估为 1000 行，Sort 局部代价：

11000 × ln(1001) ≈ 6908.75

最终根 Group Winner：

15000 + 6908.75 = 11908.75

这个例子非常适合验证自己写的第一版优化器：Memo 中要同时看见逻辑与物理候选，Winner 替换过程必须可解释，手算总代价还要与 Trace 一致。如果这三个条件做不到，继续增加规则只会让错误更难定位。

搜索边界：预算、物理属性与反馈

两阶段优化与预算：计划质量必须服从规划延迟

连接重排扩大计划选择空间，也增加规划时间。optd 先取得基线物理计划，再按预算探索，因此预算耗尽应被解释为候选覆盖不足，而非全局最优证明。

为什么先禁用 Join Reorder

先生成可执行计划再扩大连接顺序搜索，可以同时获得回退结果和剪枝上界。DatafusionOptimizer::cascades_optimize 把一次优化拆成两阶段：

1Stage 1
2  disable JoinCommute / JoinAssoc
3  插入计划并完成第一次搜索
4  得到不改变 Join Order 的可执行 Winner
5
6Stage 2
7  enable JoinCommute / JoinAssoc
8  清空 explored 状态
9  在已有 Memo 与 Winner 上继续搜索

Stage 1 的价值不是产出最终最优计划，而是尽快得到一个合法物理计划和 Upper Bound。Stage 2 扩展最容易爆炸的 Join Order 空间时，已有 Winner 可以用于剪枝；即使预算耗尽，系统也不会因为只生成了逻辑表达式而没有可执行结果。

step_next_stage 只清空 explored_group 与 explored_expr，不会清空 Memo、Winner 或 Fired Rules。Stage 1 被禁用的 Join Rule 不会被标记为 fired，因此 Stage 2 可以正常触发；已经完成的其他推导则无需重复。

两类预算对应两种降级策略

空间预算限制 Memo 增长，任务预算限制搜索工作量；触发任一预算都可能牺牲候选覆盖率。该快照的默认参数是：

1partial_explore_iter  = Some(1 << 18)
2partial_explore_space = Some(1 << 14)
3disable_pruning       = false

当 Memo 表达式数量超过空间预算时：

1停止 Transformation Rule
2继续 Implementation Rule

当任务步数超过总预算时：

1停止继续扩展规则
2如果 Group 已有完整 Winner，尽快结束

这种降级比简单抛出 Timeout 更有工程意义：逻辑搜索空间可以不完整，但已有逻辑表达式仍应被物理化，最终尽量返回一个可执行计划。

不过预算也会改变“最优”的含义。严格说，结果只是已探索空间中的最低代价计划，而不是完整规则闭包中的全局最优。生产 Explain 和 Metrics 应记录是否触发预算、哪些规则被截断、最终 Memo Space 多大，否则用户会把“搜索提前停止”误判为 Cost Model 选择错误。

当前搜索状态还不是完整的 Subgoal Cache

访问过一个子问题，不等于已经在所有约束下完成它的搜索。当前去重键缺少物理要求和搜索完成条件：

1explored_group key = GroupId
2TaskDesc key       = (ExprId, GroupId)

它们都没有包含 UpperBound，更没有 Required Physical Property。这意味着“在一个较紧上界下已经访问过”和“这个 Group 已被完整优化”会共享同一个 explored 标记。若某个子问题第一次在严格 Upper Bound 下没有找到 Winner，之后从更宽松的上下文再次进入时，理论上不应直接复用“已探索”结论。

更稳健的实现有两种方向：

1. 把 Required Property 与搜索完成状态纳入 Subgoal Key，并区分 InProgress、Pruned(bound)、Complete(winner)；
2. 仅缓存与 Upper Bound 无关的完整搜索结果，因 Bound 提前返回的任务不标记为全局 Complete。

另外，当前 step_clear 会重建 Memo 并清理 Fired/Explored Set，但没有重置 OptimizerContext 中的预算耗尽标记，也没有清空累计 CascadesStats。如果一个长生命周期 Optimizer 实例处理多条互不相关查询，一次查询触发预算后，后续查询可能继承降级状态。教学与基准场景可以观察累计指标，生产接入则应该明确拆分 Query-local Search State 与跨查询 Runtime Feedback State。

Winner::Impossible 虽然已经定义，当前任务主链在找不到孩子 Winner 时主要以 Unknown 提前返回，并没有形成完整的“不可能子目标”缓存。这些细节不会改变 Cascades 的核心模型，却决定了搜索结果能否在不同上下文中被安全复用。

逻辑属性与物理属性：当前实现最重要的分界线

逻辑属性是同一 Group 必须共享的事实，物理属性则取决于具体实现。前者已支持规则与估算，后者未进入 Cascades 子目标，限制了排序和分布策略的联合选择。

Schema 与 Column Lineage 已进入 Group

逻辑属性必须在所有等价 MExpr 间保持一致。optd 当前的两个属性已经支持不少关键 Rule：

1Schema
2  → Join 后列索引边界
3  → Projection 输出宽度
4  → Empty Relation 的输出语义
5
6ColumnRef / SemanticCorrelation
7  → 输出列追溯到 base_table.column
8  → 等值列集合
9  → Advanced Cost 中 Filter/Join 的列统计选择

ColumnRefPropertyBuilder 还使用并查集维护等值列相关性。例如 a.k = b.k AND b.k = c.k 可以形成一个等价列集合，为 Join Cardinality 和谓词推导提供语义事实。

这揭示了 Logical Property 的本质：它不是为了美化 Explain，而是让 Rule 和 Cost Model 可以查询“这个 Group 代表什么”，同时不依赖某一棵具体 Plan Tree。

Physical Property 抽象存在，但尚未接入 Cascades 搜索

存在物理属性（Physical Property）接口，并不代表它已经参与最优计划选择。optd-core/src/physical_property.rs 定义了以下能力，但 Cascades 主链尚未接入：

• derive：从孩子物理属性推导当前输出属性；
• passthrough：把父节点要求传给孩子；
• satisfies：已有属性能否满足 Required Property；
• enforce：不满足时插入 Sort、Exchange 等 Enforcer；
• default：无特殊要求。

Heuristic Optimizer 已能调用这套抽象。但当前 Cascades 实现中的：

1fn optimize_with_required_props(...) {
2    unimplemented!()
3}

而 DataFusion Cascades Optimizer 的构造也没有注册 Physical Property Builder。因此当前主链中的搜索子目标实际是：

1Optimize(GroupId, UpperBound)

而不是完整的：

1Optimize(GroupId, RequiredProperties, UpperBound)

这会带来直接限制：

• 一个 Group 只能保留一个 Winner；
• Sort Order 不能作为父子 Contract 参与候选复用；
• Hash Distribution、Broadcast、Single Partition 无法区分；
• Enforcer 不能作为带代价的候选进入统一搜索；
• Hash Join 的 Build/Probe 与 Exchange 组合无法一起比较。

如果要把 optd 推向分布式生产系统，最优先的改造不是再增加几十条 Rule，而是让 Winner Key、Task Key、Fired/Explored State 与 Costing 全部带上 Required Property。

一个最小演进版本可以是：

 1#[derive(Hash, Eq, PartialEq)]
 2struct WinnerKey {
 3    group_id: GroupId,
 4    required: PhysicalPropertySet,
 5}
 6
 7struct GroupInfo {
 8    winners: HashMap<PhysicalPropertySet, Winner>,
 9}
10
11enum TaskDesc {
12    OptimizeGroup(WinnerKey, UpperBound),
13    OptimizeExpr(ExprId, WinnerKey),
14    OptimizeInputs(ExprId, WinnerKey),
15}

同时，OptimizeInput 需要先把父 Required Property 通过 Operator Passthrough 到每个孩子，优化孩子后推导实际输出属性，不满足时生成 Enforcer，并把 Enforcer Cost 计入候选。

自适应优化：复用搜索空间，只重算 Winner

optd 的自适应路径复用 Memo，并在下一轮规划时用运行时基数重算 Winner。它减少重复候选生成，但不能补回此前预算下未生成的结构。

执行期统计如何回到 Group

运行时行数只有关联回规划阶段的 Group，才能用于后续重估。当 Adaptive 开启时，from_optd.rs 会在每个选中的物理节点外包一层 CollectorExec。计划提取阶段通过 PlanNodeMetaMap 把 materialized PlanNode 指针映射回 GroupId，于是 Collector 能记录：

1GroupId → (actual_row_count, iteration)

CollectorReader 在消费 RecordBatch 时累计行数，在 Stream 完成时写入共享 RuntimeAdaptionStorage。下一次规划时，AdaptiveCostModel 在 PhysicalScan 的 RelNodeContext.group_id 上查询最近的运行时行数；超过 decay 窗口后回退到缺省 1000 行。

链路可以画成：

 1Memo Group !31
 2   │  提取 Winner，写入 PlanNodeMeta
 3   ▼
 4PhysicalHashJoin
 5   │  包装 CollectorExec(group=!31)
 6   ▼
 7实际执行行数
 8   │  RuntimeAdaptionStorage[!31] = rows
 9   ▼
10下一轮清空 Winner，重新 Cost

为什么清空 Winner，而不是清空 Memo

统计变化不必使等价表达式失效，但会使按旧统计选出的 Winner 失效。非自适应模式调用 step_clear 清空 Memo、Fired Rules、Explored State；自适应路径则保留结构搜索结果。

自适应模式调用 step_clear_winner：

• 保留 Memo 中已经生成的逻辑与物理候选；
• 保留 Fired Rules，避免重复扩展相同等价空间；
• 清空所有 Winner；
• 清空 Explored State；
• 用新 Cardinality 重新运行 Cost DP。

这种重优化（Re-optimization）将结构搜索结果与代价评价结果分离。 SQL 语义和规则没有变化时，等价表达式空间可以复用；运行时只改变 Cardinality，因此重算 Winner 即可。

当前 Adaptive 闭环的限制

该反馈只支持受限的后续规划重估，不适用于通用的查询中途换计划或多分区执行反馈：

1. AdaptiveCostModel 当前只在 PhysicalScan 直接读取 Group 运行时行数，其他算子仍按基础公式推导；
2. CollectorExec 只接受 partition == 0，不支持多分区结果汇总；
3. 反馈以 GroupId 为 Key，跨 SQL、跨 Memo 的稳定签名与持久化尚未解决；
4. 当前共享 Optimizer 通过 Mutex<Option<Box<_>>> 临时取出，面向并发查询需要更稳健的 Session/Query 生命周期；
5. Re-optimization 发生在下一次规划，不是单个长查询执行到中途后的 Plan Fragment 替换；
6. 旧 Memo 保留哪些候选受此前预算影响，若第一次搜索未生成某类 Join Order，重算 Winner 也无法凭空得到它。

因此更准确的定位是：optd 实现了一个基于 Memo 复用的 Runtime Cardinality Feedback 原型，而不是完整的 Mid-query Re-optimization。

从 optd Physical Plan 落到 DataFusion ExecutionPlan

优化器选出的物理节点还需要转换为执行器认可的表达式和参数，才能实际执行。optd-datafusion-bridge/src/from_optd.rs 递归完成以下映射：

这里可以看到“选中物理算子”与“构造可执行算子”仍是两层：Cascades 只输出领域物理计划，Bridge 再解析 PredNode，依据输入 Schema 生成 DataFusion PhysicalExpr。

Hash Join 当前只支持 Inner Join，Key 必须是 ColumnRef，Residual Filter 为 None，并固定使用：

1PartitionMode::CollectLeft

这与基础 Cost 中 2 × left + right 的方向假设相呼应，但也说明 Distribution 尚未成为真正候选。如果未来要比较 Broadcast Left、Broadcast Right、Partitioned Hash Join，就必须同时扩展：

1Physical Operator Variant
2  + Required/Derived Distribution
3  + Exchange Enforcer
4  + Network/Memory Cost
5  + DataFusion ExecutionPlan 参数

只在 Bridge 中切换 PartitionMode，而不让 Memo 和 Cost 看见这个选择，会让执行策略脱离 CBO。

自研与验证：从最小闭环到属性搜索

如果亲手实现：一条可以逐步验证的路线

自研原型应先验证等价性与子问题复用，再增加统计和搜索策略；否则模型误差与搜索错误难以区分。以下步骤是教学实现建议，不是当前 optd 已有能力清单。

第 1 步：只支持三种逻辑算子

第一版只覆盖 Scan、Filter 和 Join，便于穷举小输入并检查规则前后的结果一致性：

1Scan(table)
2Filter(input, predicate)
3Join(left, right, condition)

标量表达式只支持 ColumnRef、Constant、Eq、And。此时不要做 SQL Parser，可以直接构造 Plan，或者接入 DataFusion/Calcite 的 LogicalPlan。

验收标准：Plan 与 Predicate 可以稳定 Hash、Equal、Display；Join 交换后列索引有单元测试。

第 2 步：实现 Memo Intern 与 Group

先验证结构去重和等价类合并，再让规则扩张搜索空间，才能区分合法新增候选与重复插入：

1PlanNode → MemoPlanNode(operator, child_groups, pred_ids)

加入三个不变量测试：

1. 相同 Scan 只产生一个 MExpr；
2. 相同结构重复插入返回同一 ExprId；
3. 等价孩子 Group 合并后，重复父表达式也会合并。

验收标准：Memo Dump 能稳定输出 Group、Expr、Pred。

第 3 步：只写一条 Transformation Rule

第一条交换规则应同时保持谓词绑定与输出列顺序，单纯交换左右孩子不足以保证等价。实现 Inner Join Commute 时需要包含：

• Condition Column Ref Rewrite；
• 输出 Projection Restore；
• Schema Property 校验。

验收标准：新表达式进入原 Group，规则重复运行不会无限增长。

第 4 步：加入 Implementation Rule 与最小 Cost

最小代价模型应足够简单，使候选排序可以手算复核。为 Join 提供 NLJ 与 HashJoin，为 Scan 提供 PhysicalScan，暂时只按行数计价：

1Scan = rows
2NLJ  = left × right
3Hash = left + right

验收标准：在这组教学公式下，大输入等值 Join 应选择 HashJoin；当输入很小时，应按公式比较，而不是要求 HashJoin 永远胜出。非等值 Join 回退 NLJ，手算结果与 Explain 一致。

第 5 步：实现 OptimizeGroup / Expr / Inputs

剪枝必须以不剪枝的搜索结果为校验基线，否则难以证明候选被安全排除。先在小查询上完成完整动态规划，再加入：

• Fired Rule Set；
• Task Cycle Detection；
• Current Winner；
• Upper Bound；
• Branch-and-Bound。

每加入一种状态，都要在 Trace 中可见。否则当一条候选消失时，无法判断是没匹配、被去重、被预算截断，还是被 Cost 剪掉。

第 6 步：加入 Logical Property

Schema 与列血缘（Column Lineage）检查可以在规划时发现列引用错误，无需等到执行结果出错。让每条 Rule 在 Debug 模式验证：

1output_schema(new_expr) == group.schema
2output_lineage(new_expr) == group.lineage

验收标准：故意写错 Join Commute 列索引时，属性检查立即失败，而不是等执行结果错误才发现。

第 7 步：把 Required Physical Property 纳入搜索 Key

同一等价类在不同排序要求下可能需要不同 Winner，因此先用 Ordering 验证搜索键与结果缓存：

1RequiredOrdering = Any | Prefix(columns)

让 Sort 作为 Enforcer，MergeJoin/SortAgg 可以产生或消费 Ordering。此时同一 Group 应出现多个 Winner：无序最优与有序最优不一定相同。

验收标准：父节点要求排序时，优化器能够在“孩子保序实现”与“无序低成本实现 + Sort”之间比较总代价。

第 8 步：再加入 Distribution、统计与反馈

分布式属性会扩大子目标数量，并引入网络和统计误差，适合在单机 Ordering 的正确性已验证后加入。扩展项包括：

• Single、Hash(keys)、Broadcast Distribution；
• Exchange Enforcer 与网络 Cost；
• NDV、Null Count、Min/Max、Histogram；
• Join Key 相关性与多列统计；
• Actual Cardinality Collector；
• Winner 失效与 Memo 复用。

这个顺序可以避免最常见的自研陷阱：统计模型看起来很丰富，但搜索 Key 仍不正确，最终不同物理要求下的 Winner 被错误覆盖。

从教学原型到生产优化器：源码暴露的演进清单

生产化应先补齐状态语义，再优化搜索效率；否则更快的匹配与更精细的代价仍可能复用错误 Winner。以下建议来自前述实现边界，尚不是经过生产负载验证的改造效果。

Required Properties 必须成为一等搜索状态

单一 Winner 无法区分有序与无序等物理要求，扩展生产能力时应先修正搜索状态。需要同时修改：

• GroupInfo：单 Winner → PropertySet → Winner；
• SearchContext：加入 Required Property；
• TaskDesc：避免把不同物理要求错误去重；
• OptimizeInput：属性 Passthrough、Derive、Satisfy、Enforce；
• Cost：Exchange、Sort、Materialize 等 Enforcer 成本；
• Plan Extraction：按 Root Required Property 提取。

搜索调度需要 Promise，而不只是注册顺序

当前规则按 Vec 顺序扫描。生产优化器通常需要估计 Rule 的收益与扩张风险：

1高 Promise：实现规则、明显减少基数的 Filter Pushdown
2中 Promise：有选择性依据的 Join Reorder
3低 Promise：可能产生大量对称表达式的交换/结合

在预算有限时，Rule Ordering 本身就是计划质量的一部分。两阶段优化已经是粗粒度 Promise；下一步可以把优先级下沉到 Rule/Binding/Task。

Memo 需要高效 Parent Index 与增量失效

当前 Group Merge 会扫描并重写所有表达式，适合小规模教学。生产实现需要：

• Group/Expr Canonicalization；
• Parent MExpr Index；
• Union-Find 或等价的稳定重定向；
• Winner Dependency Graph；
• 统计或 Cost 变化后的精确失效；
• 内存预算与冷候选回收。

Binding 枚举需要 Lazy 与上限

当前嵌套 Matcher 对 Child Group 结果做笛卡尔积并一次性生成 Vec。可以演进为：

1Lazy Binding Iterator
2  → 每产生一个 Binding 就评估 Promise/预算
3  → 可暂停、可恢复
4  → 超过阈值时保留最有希望的子集

否则 Group 内候选一多，Matcher 自身就可能先耗尽内存，而不是 Costing 成为瓶颈。

Cost 不应只是一组固定公式

固定行数公式不能区分同样基数下不同的行宽、网络传输和内存占用，生产计价需要额外的资源维度：

• CPU：表达式复杂度、Hash、Compare、Serialize；
• I/O：远端/本地、压缩后字节、Cache Hit；
• Network：Shuffle/Broadcast 字节与节点数；
• Memory：Hash Table、Sort Spill、并发 Pipeline；
• Latency：Blocking Boundary、并行度（Degree of Parallelism）、Startup Cost；
• Risk：Cardinality 不确定性与资源超限概率。

weighted_cost 可以保留多维向量，再根据 Workload/SLA 选择权重。更进一步，Winner 不一定只有一个标量最优，可以保留 Pareto Frontier，延迟到资源环境明确时再决策。

Rule 正确性需要系统化验证

规则验证应覆盖关系语义而不只覆盖计划形状，否则空值和外连接（Outer Join）错误可能通过结构测试。建议至少加入：

1. Property Invariant：Schema、Nullable、Keys、Lineage 不变；
2. Differential Test：随机小表上执行原计划与改写计划，比较结果；
3. Three-valued Logic Test：Null、Outer Join、NOT IN、Mark Join；
4. Rule Pair Convergence：检测规则组合产生的循环与爆炸；
5. Memo Replay：保存 Rule Trace，能够重放某次计划生成过程。

优化器最危险的 Bug 不是选慢计划，而是产生错误结果。Cost 可以近似，等价性不能近似。

Adaptive 需要稳定签名与并发模型

GroupId 只在当前 Memo 生命周期内有效。若要做跨查询 HBO，需要把反馈绑定到稳定语义签名，例如：

1Normalized SQL / Plan Fingerprint
2  + Logical Group Digest
3  + Predicate Parameter Bucket
4  + Catalog/Schema Version
5  + Statistics Version

同时要处理多分区聚合、采样偏差、并发更新、反馈衰减、参数敏感计划和版本失效。optd 的 (GroupId → rows) 是理解闭环的最小实现，但生产 HBO 的主要难点恰好在 GroupId 之外。

如何阅读与调试 optd

按状态依赖阅读源码更容易定位计划差异：先确认表示和去重，再追规则产物，最后复核代价与执行参数。阅读顺序如下：

 11. optd-core/src/nodes.rs
 2   先理解 PlanNode、PredNode、PlanNodeOrGroup
 3
 42. optd-core/src/cascades/memo.rs
 5   跟 add_new_group_expr_inner、append_expr_to_group、merge_group_inner
 6
 73. optd-core/src/cascades/rule_match.rs
 8   看 Pattern 如何从 Group 枚举 Binding
 9
104. optd-datafusion-repr/src/rules/joins.rs
11   用 JoinCommute、JoinAssoc、HashJoin 验证规则契约
12
135. optd-core/src/cascades/tasks2.rs
14   按 OptimizeGroup → Expr → Rule → Input 追搜索状态
15
166. optd-datafusion-repr/src/cost/base_cost.rs
17   手算 Scan、Join、Sort 的 Winner
18
197. optd-datafusion-repr/src/lib.rs
20   看 Rule Set、预算、两阶段与 Adaptive Clear
21
228. optd-datafusion-bridge/src/{into_optd,from_optd,physical_collector}.rs
23   最后串起 DataFusion 与运行时反馈

optd 的 Planner Test 支持输出 Physical Plan、Logical Join Orders、Memo Table 和 Rule Trace。一个高价值调试循环是：

1写一条两表/三表 SQL
2  → 打开 dump_memo_table + enable_tracing
3  → 找 Root Group
4  → 列出该 Group 的 Logical/Physical MExpr
5  → 找每次 apply_rule 的来源与产物
6  → 手算 proposed Winner
7  → 打开/关闭 pruning 比较搜索空间
8  → 限制 logical_rules 验证某条规则的边际作用

不要只看最终 Explain。最终树隐藏了绝大多数被拒绝候选，而优化器的价值与问题通常都发生在“为什么某个候选没有成为最终树”这一层。

实现边界与验证顺序

optd 适合验证 Cascades 的最小闭环，不适合直接作为支持多种分布属性的生产优化器。当前快照已将规则、Memo、动态规划和 DataFusion 执行接通，但物理属性搜索、Binding 枚举和运行时反馈仍有明确限制。

自研时先用小表差分测试（Differential Testing）保证规则等价性，再用可手算的代价检查 Winner，最后对照无剪枝基线验证预算与剪枝。引入 Ordering 或 Distribution 前，先把 Required Properties 纳入 Winner 与任务状态；引入跨查询反馈前，先解决稳定身份、版本失效和并发更新。统计精度不能补偿漏掉的候选，成本最小也不能证明规则语义正确。

参考资料

• optd 源码快照 e31c8e5
• The Columbia Optimizer Thesis
• How Good Are Query Optimizers, Really?
• Adaptive Optimization of Very Large Join Queries