查询优化器：代价模型与统计信息

一句话定义

查询优化器把 SQL 改写为关系代数树后，用「统计信息估算基数 × 算子代价公式」枚举并比较可行计划，选出估算总代价最低的一个——它是数据库的「自动驾驶仪」，绝大多数性能问题最终都会撞上它的判断。

为什么重要

「SQL 写对但跑得慢」的根因几乎都在优化器的输入端：统计信息过期、参数嗅探、代价公式低估连接爆炸。
理解代价模型，才能解释 kp-012 里那些「反直觉」的计划（明明有索引却全表扫）。
这是 SQL 从「能跑」到「规模化可靠」的分水岭，也是数据库岗位进阶面试的高频深水区。

前置知识

kp-012（会读执行计划、见过估算行数）。

核心概念

逻辑优化（规则改写）：谓词下推、投影裁剪、子查询解关联、外连接消解、视图展开。
物理优化（代价搜索）：访问路径选择（全扫/索引扫）、连接算法（NL/Hash/merge）、连接顺序。
基数估计（Cardinality Estimation）：由统计信息推算每个算子输出行数。
统计信息：直方图（列值分布）、最常见值（MCV）、不同值数（NDV）、相关性（ correlated 列）。
代价公式：cost = w_io × 预计页读 + w_cpu × 预计元组/比较次数，权重由系统标定。
搜索算法：动态规划（少表穷举）→ 贪心/遗传（多表近似，PostgreSQL 默认 ≥ 12 表转遗传）。

原理与机制

Selinger 1979 年的 System R 论文奠基了主流代价模型：先算每个访问路径的代价，再用动态规划自底向上枚举连接顺序（(A⋈B)⋈C 与 A⋈(B⋈C) 分别计价），剪掉同结果集下更贵的子计划。基数估计是链条源头，经典假设两条：属性独立（sel(A∧B) = sel(A) × sel(B)）与均匀分布（除 MCV 外等概率）——现实数据的相关性与倾斜会让估算偏差指数级放大，上游估错 10 倍、三层连接后可差千倍，计划随之翻转。参数嗅探（Parameter Sniffing）：绑定变量首次执行时计划被缓存，后续参数选择性剧变时复用错误计划。补救体系包括：定期/触发式 ANALYZE、扩展统计（PG CREATE STATISTICS 捕获列相关性）、自适应计划（Oracle 12c+ 运行时修正）、计划基线（SQL Plan Baseline 锁定已知好计划）。

实例或案例

十亿行订单表，WHERE city = '杭州' 在直方图中占 30% 时优化器选全表扫（读 1 遍比走索引回表 3 亿次便宜），在占 0.1% 时选索引扫——同一条 SQL、两种「都正确」的计划。而 WHERE city = '杭州' AND age = 25 因「城市与年龄相关」（不同城市年龄结构不同），独立性假设把选择性估成乘积而严重低估，三层 JOIN 后计划崩坏；建扩展统计捕获相关性后估算回归，计划恢复。这就是「先修统计，再质疑优化器」的完整案例。

常见误区

认为「优化器会找到最优计划」：它只在已知统计内找「估算最优」，垃圾进垃圾出。
用 Hint 强行锁死计划而不解释原因：数据分布变化后旧 Hint 变枷锁，必须写清 Hint 的成立条件。
以为统计信息自动永远新鲜：大批量导入、分区交换、大删除后必须显式 ANALYZE。

自测题

为什么多表连接的连接顺序是优化器最重的决策？答：n 表连接顺序有 n! 量级组合，不同顺序的中间结果集大小差异可达数量级，直接决定后续每步扫描与内存代价；DP 保证小表场景全局最优，大表场景用贪心/遗传近似。
参数嗅探为什么会引发线上抖动？答：首参数生成的计划被缓存复用，当后续参数选择性差异极大（如 city 既有 30% 也有 0.1%）时，同一计划对某些参数严重次优。

公式或模型

System R 风格代价：Cost(scan) = pages × w_io；Cost(NL) = C_outer + N_outer × C_probe；Cost(Hash) = C_build + C_probe + output × w_cpu。选择性：等值 sel = 1/NDV（无 MCV 时），范围 sel = (v2 - v1)/(max - min)，合取 sel = Π sel_i。

图示

优化器流水线：统计信息 → 基数估计 → 代价搜索，估算质量决定计划质量

直观类比

优化器像导航 App：统计信息是实时路况，代价模型是「时间优先还是费用优先」的打分函数，动态规划是比选所有换乘方案。路况数据过期（统计过期），导航就带你走上已经封路的捷径。

与其他知识点的关系

kp-012 是它的观测窗口；kp-009/kp-010/kp-011 的索引是它菜单里的候选路径；kp-021 的 LSM 代价结构不同，优化器规则也随之不同。

前置知识点