【分布式 OLAP 查询引擎】Calcite 与规则/代价优化框架

第 2 篇 的逻辑计划是 未优化或初建 的代数树。优化器通过 等价变换规则 缩小搜索空间、下推谓词与投影，再交给 代价模型 选物理实现（第 4–5 篇）。Apache Calcite 是工业界最常见的 独立优化器框架；Trino 使用 自研 planner，但在 Rel 代数、规则链思想上与 Calcite 同源借鉴，不能把 Trino 等同于「跑 Calcite 的 fork」。

本文钉住 Calcite 的核心抽象，并说明 Trino 476+ 与 Spark 3.5+ Catalyst 在优化阶段的对应关系。不展开 Calcite 全 API；源码与文档为 A 级依据。

环境：本机无 JVM 优化器调试环境；Trino/Spark 行为以官方文档与标注版本为准。不粘贴未实测的 EXPLAIN 输出。

一、为什么需要独立优化框架

flowchart TB
  FE["SQL Frontend<br/>many engines"]
  OPT["Optimizer<br/>rules + cost"]
  BE["Backends<br/>Trino / Spark / JDBC"]
  FE --> OPT --> BE

Flink Table、Hive、Dremio 等历史上均与 Calcite 有交集；Trino 选择 深度自研 以控制 MPP 分布式 trait 与 connector SPI（Trino Developer guide, Planner）。

二、RelNode：关系代数 IR

Calcite 中计划节点为 RelNode 子类，与 第 2 篇 LogicalPlan 一一对应：

表达式 在 RexNode（row expression）中表示：列引用 InputRef、常量、函数调用。Constant folding 在 Rex 层完成。

Trino 内部使用 PlanNode 层次（TableScanNode、FilterNode…），概念同构，命名不同（A 级：Trino 源码 io.trino.sql.planner）。

三、Convention 与 Trait

物理计划需绑定 执行约定：

Implementation Rule 把 LogicalJoin 转为带 Convention.TRINO（概念名）的 HashJoinNode，并声明 输出 trait（如 hash 分区 on join key）。

flowchart LR
  LJ["LogicalJoin<br/>Convention: NONE"]
  R["Rule: JoinToHashJoin"]
  PJ["Physical HashJoin<br/>+ DISTRIBUTION"]
  LJ --> R --> PJ

MPP 中 DISTRIBUTION trait 决定是否插入 Exchange（第 11 篇）：例如 probe 端需 HASH(custkey) 与 build 端一致。

四、Rule-based 优化：常见规则链

规则形式：Pattern → Transform，保持等价性。典型 logical rules（Calcite 与 Trino 均存在同类实现，名称各异）：

DuckDB 1.5.4 本机 实验 中 SEQ_SCAN 带 Filters: o_orderdate>=...，即 filter into scan 的结果。

4.1 下推边界

并非所有谓词都能进 connector：

lakehouse/18 的 四层漏斗 在引擎侧由 layout constraint + rule 共同触发（第 15 篇）。

五、VolcanoPlanner 与 Cascades

Memo：同一逻辑表达式对应 Group，多种物理实现并存，Winner 由代价选优。

flowchart TB
  G1["Group: Scan orders"]
  G2["Group: Scan customer"]
  G3["Group: Join"]
  G1 --> G3
  G2 --> G3
  G3 --> G4["Group: Agg"]

Implementation rules 在 group 内展开 HashJoin vs MergeJoin；Exploration rules 做 join reorder（第 5 篇）。

Trino JoinOrderOptimizer 与 dynamic programming / heuristic 边界见 Trino 文档 Join planning（476+）；实现细节在源码，不在此篇臆测默认算法版本差异。

六、Trino 与 Calcite 的关系

写作口径：说「Calcite 式 框架」或「与 Calcite 同类的 rule + cost 搜索」，不说「Trino 基于 Calcite 构建」。

Spark Catalyst 是另一套 Scala Tree + RuleExecutor（第 13 篇），阶段名 Optimizer / SparkPlanner，与 Calcite 无直接依赖，但 规则链思想平行。

七、优化阶段流水线（Trino 概念）

flowchart LR
  LP["Logical plan"]
  LR["Logical rules"]
  SP["Stats + CBO"]
  PP["Physical rules"]
  DP["Distributed planning"]
  LP --> LR --> SP --> PP --> DP

PostgreSQL 在 单进程 内完成类似链条（PG 第 10–11 篇），无 Distributed 层；parallel worker 是物理计划上的 partial path，不是 shuffle 网络。

八、Rule 调试与可观测

生产 Trino 调优常看 默认 EXPLAIN + EXPLAIN ANALYZE（第 12 篇），而非逐条 rule trace。

九、与 columnar-engine 的衔接

columnar-engine 讲 存储层向量化读；优化器决定 读哪些列、哪些 granule/file。规则 Project prune 直接减少 ColumnHandle 数量；Filter pushdown 减少 row group / page 解码（columnar-engine 第 4 篇）。

执行层 向量化 batch 由 physical rule 选型（BatchScan + VectorizedFilter），属 第 7 篇。

十、小结

Calcite 提供了 RelNode + RexNode + Rule + Trait/Convention + Volcano/Cascades 的完整叙事；Trino 在 自研 planner 中实现同类阶段，并扩展 分布式 trait 与 connector layout。理解规则链后，读 EXPLAIN 时能看到 Filter 是否在 Scan 下、Project 是否只剩必要列——这是下推与列裁剪是否生效的第一眼检查。

下一篇进入 统计信息与代价模型：NDV、histogram、connector stats 如何进入 CostCalculator。

参考资料

1. Apache Calcite Documentation, Algebra / Rules / Cost-based optimization。
2. Trino Documentation, Developer guide / Cost-based optimizations（476+）。
3. Graefe, The Volcano Optimizer Generator（经典，规则与 extensibility）。
4. 第 2 篇（LogicalPlan）。
5. postgresql-kernel 第 10 篇（PG 统计对照）。
6. Apache Spark Documentation, Catalyst Optimizer（3.5+）。

返回 系列目录 ｜ 上一篇：逻辑计划 ｜ 下一篇：统计与代价模型