【分布式 OLAP 查询引擎】统计信息与代价模型

CBO（Cost-Based Optimizer）在 第 3 篇 的规则链之后做 数值决策：选哪种 join 算法、哪种 join 顺序、是否 broadcast 小表。决策输入是 基数估计（cardinality） 与 代价常量；输出是 estimated rows / cost 列在 EXPLAIN 里。

本文拆解 OLAP 引擎（Trino 476+ 主线）的统计来源与代价组成，并对照 postgresql-kernel 第 10 篇 的 pg_statistic。文末用 DuckDB 1.5.4 本机 plan 中的 Cardinality 说明估算如何进入计划；Trino 有/无 ANALYZE 的对比实验需 Docker 栈，本机未跑时不伪造 Trino 数字。

环境：WSL2、i9-12900K；DuckDB 1.5.4 实测；无 Trino JVM。Trino 机制引用官方 Cost-based optimizations（476+）。

一、CBO 在优化链中的位置

flowchart TB
  RULES["Logical / physical rules"]
  STATS["Statistics snapshot"]
  COST["CostCalculator"]
  WIN["Pick lowest cost plan"]
  RULES --> COST
  STATS --> COST
  COST --> WIN

第 5 篇 的 broadcast vs shuffle 阈值直接依赖 build 侧 estimated size。

二、统计对象：表与列

2.1 选择率合成

多谓词 AND 常假设 ** independence**（与 PG clauselist_selectivity 类似）：

\[ sel(p_1 \land p_2) \approx sel(p_1) \times sel(p_2) \]

相关列（city + zipcode）会 严重低估或高估；PG 用 CREATE STATISTICS；Trino/Iceberg 侧部分依赖 Puffin 扩展统计（Iceberg spec，A 级）。

2.2 Join 基数

等值 join 常用：

\[ |R \bowtie S| \approx \frac{|R| \cdot |S|}{\max(D_{R.k}, D_{S.k})} \]

NDV 估错时 中间结果数量级错误，导致 错误 join 顺序（先放大再过滤 vs 先过滤再 join）。

三、统计来源

3.1 Trino ANALYZE

Trino 对支持 analyze properties 的 connector 提供 ANALYZE（文档 ANALYZE，476+）。写入 column statistics 到 metastore 或 connector 元数据，供下次 planning 读取。

本机限制：reproduce/docker-compose.yml 未在本写作环境执行；不编造 「ANALYZE 前后 estimated rows 从 X 变 Y」的 Trino 片段。复现步骤见 reproduce/run_trino_experiments.sh 与 lakehouse reproduce。

3.2 Iceberg 与湖上统计

引擎 不扫描全表 即可从 manifest 汇总 分区级 row count；这是湖仓相对裸 Parquet 的关键优势（lakehouse/08）。

四、代价模型组成

Trino CostCalculator（概念，476+ 文档 Cost-based optimizations）将计划节点代价分解为：

\[ Cost(plan) = w_{cpu} \cdot CPU + w_{io} \cdot IO + w_{net} \cdot Network \]

权重 \(w_*\) 可通过 session property 或 config 调整（具体 property 名以 476+ 文档为准）。

4.1 与 PostgreSQL 对照

PG 第 10 篇 的 rows=1 灾难 在 Trino 体现为 estimated 1 row → nested loop + 实际百万行 shuffle。

五、DuckDB 1.5.4：计划中的 Cardinality

本机 run_duckdb_experiments.py（100k orders，5000 customer）：

DuckDB 在 优化阶段 用表统计（generate_series 合成数据亦有内置估计）写入 plan Cardinality 字段。这与 Trino EXPLAIN 的 Estimates: rows=... 角色相同；数值 不可跨引擎对比（算法与假设不同）。

实测 wall time（q_join，EXPLAIN ANALYZE 3 次中位数）：0.0028 s——说明 估计与执行在小数据上一致，不代表 Trino 在 TB 级 Iceberg 上的行为。

六、统计过期与估算误差

flowchart LR
  STALE["Stats stale"] --> BAD["Bad cardinality"]
  BAD --> WRONG["Wrong join order"]
  WRONG --> SCAN["Full table scan"]
  WRONG --> BOOM["Huge intermediate"]
  WRONG --> BC["Bad broadcast"]

Trino EXPLAIN ANALYZE 对比 estimated vs actual 是生产第一排查手段（第 17 篇）。

七、Histogram 与 NDV 精度

等深直方图（equi-depth）：每桶行数相近，桶边界记录值域；范围查询用 桶重叠比例 估选择率。

NDV：HyperLogLog 或采样估计；小样本下 distinct 低估 会导致 join 结果 高估（保守）或 低估（激进），取决于引擎公式。

Iceberg Puffin 可存储 sketches；connector 是否读取取决于 Trino Iceberg 版本实现（第 15 篇）。

八、代价 vs 真实延迟

优化器选「最低 cost plan」是在模型内最优，不是全局 SLA 最优；resource group、并发 spill 会改变实际表现（第 16 篇）。

九、诊断清单

1. SHOW STATS FOR / information_schema（connector 支持时）。
2. EXPLAIN 看 Estimates 是否全为默认值（如 -1 或固定常数）。
3. EXPLAIN ANALYZE 看 Input rows vs Planned rows 比率。
4. 湖表：对照 lakehouse/18 看 layout constraint 是否出现。
5. 必要时 ANALYZE 或重写 SQL（谓词写在 partition 列上）。

十、小结

统计信息把 「这张表有多大、这列有多散」 变成数字，代价模型把 算法与 shuffle 体积 变成可比较的 cost。湖格式把 file-level stats 推到 planning 入口，减少全表采样依赖；但 ** independence 假设与过期 stats** 仍是 join 计划崩溃的主因。

下一篇进入 Join 重排与物理算子选择：left-deep vs bushy、broadcast vs partitioned join、DPP。

参考资料

1. Trino Documentation, Cost-based optimizations / ANALYZE（476+）。
2. Apache Iceberg Specification, Metrics / Puffin。
3. postgresql-kernel 第 10 篇（pg_statistic）。
4. DuckDB 1.5.4，reproduce/run_duckdb_experiments.py（Cardinality 与 timing）。
5. 第 3 篇（CBO 位置）。
6. lakehouse 第 18 章（manifest stats 与 pruning）。

返回 系列目录 ｜ 上一篇：Calcite 与优化框架 ｜ 下一篇：Join 规划