2015年，慕尼黑工业大学的研究团队做了一个实验：他们把PostgreSQL查询优化器的基数估计值全部替换成真实值，然后观察113个复杂查询的执行时间变化。
结果令人震惊——超过30%的查询性能提升了2倍以上，其中一些甚至快了100倍。这个实验后来发表在VLDB会议上，标题是"How Good Are Query Optimizers, Really?"。
这个问题的核心在于：查询优化器是数据库性能的决策中枢，但它的决策依据——成本估算——存在根本性的缺陷。这不是某个特定数据库的bug，而是困扰了整个数据库领域四十多年的结构性难题。
成本估算的三支柱
要理解优化器为什么会犯错，首先要理解它是如何工作的。
1979年，IBM的Pat Selinger在System R项目中提出了成本基数优化的框架。这个框架沿用至今，由三个核心组件构成：基数估计（预测每个操作返回多少行）、成本模型（计算每个操作的资源消耗）、计划枚举（在可能的执行计划中搜索最优解）。
其中，基数估计是最关键的一环。它是成本模型的主要输入，直接决定了优化器对不同执行计划的评价。如果基数估计错了，后续的一切计算都建立在错误的基础之上。
那么，基数估计是如何进行的？
直方图与MCV：统计信息的骨架
现代数据库普遍采用采样统计来收集基表信息。以PostgreSQL为例，ANALYZE命令会对每个表进行随机采样，构建三类统计信息：
| 统计类型 | 描述 | 用途 |
|---|---|---|
| 直方图（Histogram） | 将列值分布划分为等频区间 | 范围查询的选择性估计 |
| MCV列表（Most Common Values） | 最常见值及其频率 | 等值查询的精确估计 |
| Distinct Count | 不同值的数量 | 连接操作的大小估计 |
对于简单的单表查询，这套机制工作得相当不错。微软SQL Server团队在2023年的研究中发现，基表选择谓词的估计中位数q-error（估计值与真实值的比值）接近1.0，意味着大多数单表估计是准确的。
但问题出现在更复杂的场景。
连接操作：错误的指数级传播
当查询涉及多个表的连接时，基数估计的准确性急剧下降。
PostgreSQL（以及大多数数据库）采用一个简单的公式来估计两个表连接后的行数：
|T1 ⋈ T2| = |T1| × |T2| / max(Distinct(T1.key), Distinct(T2.key))
这个公式基于一个关键假设：连接键的值是均匀分布的，且两个表的值域存在包含关系。
现实数据很少满足这些假设。当数据存在倾斜（skew）或相关性时，误差会快速放大。Leis等人的研究发现：
- 对于1个连接，PostgreSQL有16%的估计误差超过10倍
- 对于2个连接，这个比例上升到32%
- 对于3个连接，超过一半的估计误差超过10倍
更糟糕的是，错误会沿着查询树向上传播。如果一个中间结果的基数被低估，优化器可能会选择索引嵌套循环连接，而实际上哈希连接会快得多。如果被高估，可能会选择全表扫描而非索引访问。
独立性假设：最危险的简化
为什么基数估计如此困难？根本原因在于数据库被迫做出大量简化假设，而这些假设在现实世界中经常失效。
属性独立性假设
当查询包含多个谓词时，例如：
SELECT * FROM orders
WHERE status = 'SHIPPED' AND region = 'NORTH';
优化器需要估计同时满足两个条件的行数。在没有跨列统计信息的情况下，它只能假设两个谓词独立：
Selectivity(P1 AND P2) = Selectivity(P1) × Selectivity(P2)
如果status和region存在相关性（比如北方地区的发货率特别高），这个假设会导致严重误差。研究发现，对于存在相关性的谓词组合，估计误差可以达到100倍甚至更高。
PostgreSQL从版本10开始引入了扩展统计信息（CREATE STATISTICS），允许用户显式声明列间的函数依赖关系。但这是一个手动过程，需要DBA识别并创建。
连接独立性假设
更棘手的是"跨连接相关性"（join-crossing correlation）。考虑这样一个查询：找出所有出生于巴黎的演员参演的法国电影。
这个查询涉及演员、城市、电影三个表，且存在隐含的相关性：出生于巴黎的演员更可能参演法国电影。但优化器对这种跨越多个表的关联一无所知，只能按独立假设进行估计。
CockroachDB的技术博客指出，这是当前基数估计研究的前沿难题——如何在合理的计算开销内捕获这种跨连接的相关性。
包含假设
连接公式中的"包含假设"（principle of inclusion）假设较小表的连接键值都能在较大表中找到匹配。当这个假设失效时（比如大量外键值在主表中不存在），连接结果会被严重高估。
NP难问题：搜索空间的困境
即使我们有完美的基数估计，优化器仍然面临另一个根本挑战：计划枚举本身是一个NP难问题。
指数级爆炸的可能计划
对于一个涉及n个表的连接查询，可能的连接顺序数量随n呈指数增长。具体来说：
- 仅考虑左深树（left-deep trees）：n! 种顺序
- 考虑所有树形（包括bushy trees）：(2n-2)!/(n-1)! 种可能
一个10表连接的查询，可能的计划数量就已经是天文数字。
为了在可接受的时间内找到执行计划，数据库被迫使用动态规划（对小查询）或启发式算法（对大查询）来裁剪搜索空间。
动态规划的代价与局限
PostgreSQL对连接数小于12（可配置）的查询使用动态规划算法DPccp。该算法的时间复杂度是O(3^n)，空间复杂度是O(2^n)。
当表数增加时，优化时间会急剧增长。对于超过阈值的查询，PostgreSQL会切换到遗传算法GEQO——这本质上是随机搜索，不保证找到最优解。
微软SQL Server采用Cascades框架进行自顶向下的枚举，同样面临搜索空间爆炸的问题。
成本模型：不可忽视的误差源
即使基数准确、计划完美，成本模型本身也会犯错。
磁盘与内存的鸿沟
PostgreSQL的成本模型诞生于磁盘为主的时代。其默认参数假设随机I/O比顺序I/O贵400倍，这在机械硬盘上是合理的估计。
但在内存数据库或SSD环境下，这个假设严重高估了随机访问的成本。结果？优化器可能错误地偏爱全表扫描而非索引查找。
执行引擎的隐藏开销
成本模型需要量化各种操作的开销：CPU周期、内存访问、I/O操作。但现代CPU的缓存层次、分支预测、SIMD指令使得精确建模几乎不可能。
微软SQL Server团队的实验发现，即使用真实基数进行计划选择，仍有约1%的查询出现了性能倒退——原因正是成本模型的不准确。
各数据库的差异与应对
不同数据库在处理这些问题上各有策略：
PostgreSQL
- 扩展统计信息：支持声明函数依赖（DEPENDENCIES）和MCV组合
- 遗传算法GEQO：处理大查询的计划枚举
- 并行查询：部分缓解糟糕计划的影响
SQL Server
- 新旧基数估计器：2014年重写了CE，但允许切换回旧版本
- 自适应连接：运行时动态选择Hash Join或Nested Loops
- Parameter Sensitive Plan优化：针对参数嗅探问题
Oracle
- 动态采样：在优化时执行小规模查询获取实际数据分布
- SQL Profile：存储查询的历史执行统计
- 自适应游标共享：根据实际参数值选择不同计划
MySQL
- 索引统计：InnoDB维护的索引基数估计
- 索引下推：在存储引擎层提前过滤，减少回表
- 成本模型常量：可通过系统表调整成本权重
缓解策略：当优化器不可靠时
既然优化器存在根本性局限，实践中如何应对？
统计信息的精细化管理
-- PostgreSQL: 创建扩展统计信息
CREATE STATISTICS s1 (dependencies, mcv)
ON region, status FROM orders;
-- 手动触发统计更新
ANALYZE orders;
-- 调整采样精度
ALTER TABLE orders ALTER COLUMN status
SET STATISTICS 500;
强制计划选择
当优化器坚持错误选择时，可以强制指定计划：
-- PostgreSQL: 强制使用特定索引
SET enable_seqscan = off;
-- SQL Server: 使用提示
SELECT * FROM orders WITH (INDEX(idx_status)) ...
-- Oracle: 使用提示
SELECT /*+ INDEX(orders idx_status) */ * FROM orders ...
计划稳定性控制
对于关键查询，固定执行计划比让优化器"自由发挥"更安全：
-- SQL Server: 使用Query Store固定计划
EXEC sp_query_store_force_plan @query_id, @plan_id;
-- Oracle: 使用SQL Plan Baseline
DECLARE
v_plans NUMBER;
BEGIN
v_plans := DBMS_SPM.LOAD_PLANS_FROM_CURSOR_CACHE(
sql_id => 'abc123...'
);
END;
学习型基数估计：未来的希望？
近年来，机器学习被引入基数估计领域。2018年，Kipf等人提出了MSCN（Multi-Set Convolutional Network），使用深度学习来估计查询基数。
这些方法的核心思路是：不再依赖简化的假设，而是从历史查询中学习数据分布的实际特征。
2022年SIGMOD上的一项系统性研究比较了各类学习方法，发现它们在某些场景下确实能显著提升估计精度。但挑战仍然存在：
- 训练开销：需要大量历史查询数据
- 泛化能力：对未见过的查询模式表现不稳定
- 推理延迟：必须在毫秒级完成估计，否则影响优化时间
截至2025年，学习型基数估计仍主要处于研究阶段，尚未被主流数据库广泛采用。
结语：不完美的艺术
查询优化是数据库系统中最复杂的组件之一。四十多年来，研究人员和工程师构建了精密的框架，但始终无法摆脱核心假设与现实数据之间的张力。
理解优化器的局限性，不是为了否定它的价值——在绝大多数情况下，它确实能找到足够好的计划。而是为了在它失手时，能够诊断问题、施加干预。
下次当你发现一个本该秒级的查询跑了几分钟，不要急着质疑索引设计或硬件配置。先看看执行计划中的估计行数与实际行数——差异可能就是问题的根源。
参考资料
- Leis V, Gubichev A, Mirchev A, et al. How Good Are Query Optimizers, Really?. PVLDB, 9(3):204-215, 2015.
- Lee K, Dutt A, Narasayya V, Chaudhuri S. Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server. PVLDB, 16(11):2871-2883, 2023.
- Selinger P G, Astrahan M M, Chamberlin D D, et al. Access path selection in a relational database management system. SIGMOD, 1979.
- Kipf A, Kipf T, Radke B, et al. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. arXiv:1809.00677, 2018.
- Moerkotte G, Neumann T, Steidl G. Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors. PVLDB, 2(1):982-993, 2009.
- PostgreSQL Documentation: Chapter 14.2 Statistics Used by the Planner
- Microsoft Learn: Cardinality Estimation (SQL Server)
- Oracle Documentation: Understanding Optimizer Statistics
- CockroachDB Blog: An Introduction to Join Ordering
- Han Y, Wu Z, Wu P, et al. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. PVLDB, 15(4):752-765, 2021.