数据库的查询执行计划中的基数估计与代价模型

1. 基数估计与代价模型的基本概念

基数估计（Cardinality Estimation）是查询优化器预测每个操作符（如过滤、连接、分组）输出行数的过程。代价模型（Cost Model）则基于基数估计，结合硬件特性（如I/O、CPU成本），计算不同执行计划的代价，从而选择最优计划。两者共同决定查询性能的优劣。

2. 基数估计的重要性与挑战

• 重要性：若基数估计错误（如实际行数100万，估计为100行），优化器可能选择低效计划（如误用嵌套循环连接代替哈希连接）。
• 挑战：
  • 数据分布不均（如age=25的行占90%）。
  • 多列关联（如城市=北京和职业=程序员存在强相关性）。
  • 查询条件复杂（如包含LIKE、BETWEEN或子查询）。

3. 基数估计的常用方法

（1）基础统计信息

数据库通过ANALYZE命令收集统计信息，包括：

• 直方图（Histogram）：将数据按值域分桶，记录每桶的频率分布。例如，对age列构建直方图后，可估算age BETWEEN 20 AND 30的比例。
• 不同值数量（NDV, Number of Distinct Values）：用于估算等值查询的选择性（如age=25的选择性约为 1/NDV）。
• 空值比例、数据密度等。

（2）假设与简化

• 独立性假设：默认多列条件相互独立，例如估算age=25 AND salary>5000时，直接计算两者选择性的乘积。但实际数据可能存在关联（如年轻人工资较低），导致估计偏差。
• 均匀分布假设：假设数据均匀分布，但现实数据常呈现倾斜（如少数城市人口密集）。

（3）应对关联性的技术

• 多列统计信息（Extended Statistics）：手动创建列组合的统计信息（如Oracle的DBMS_STATS.CREATE_EXTENDED_STATS）。
• 动态采样（Dynamic Sampling）：对复杂查询临时抽取少量数据，校准估计值。

4. 代价模型的计算要素

代价模型将执行计划分解为操作符（如扫描、连接、排序），并为每个操作符分配成本：

• I/O成本：数据页的读取/写入次数（受索引类型、缓存影响）。
• CPU成本：处理一行数据所需的计算量。
• 内存成本：哈希连接或排序等操作的内存占用。

示例代价公式（简化）：

总代价 = 顺序扫描成本 + 过滤成本 + 连接成本  
顺序扫描成本 = 表页数 × 单页I/O成本  
过滤成本 = 扫描行数 × 单行CPU成本  
嵌套循环连接成本 = 外表行数 × 内表单次扫描成本  

5. 实际优化器的工作流程

以估算SELECT * FROM users WHERE age>30 AND city='北京'为例：

1. 收集统计信息：直方图显示age>30的行占比40%，city='北京'的NDV为50（选择性1/50）。
2. 基数估计：
   • 若假设独立性，条件组合的选择性 = 40% × 1/50 = 0.8%。
   • 若表总行数100万，则估计输出行数 = 100万 × 0.8% = 8000行。
3. 代价计算：
   • 计划A：全表扫描（成本 = 100万行 × 0.1成本单位 = 10万单位）。
   • 计划B：在city索引上扫描，再回表过滤age>30（成本 = 索引遍历 + 回表I/O）。
   • 比较代价后选择更低成本的计划。

6. 常见问题与优化手段

• 估计偏差大的场景：
  • 多列关联查询：需创建扩展统计信息。
  • 复杂表达式（如UPPER(name)=‘ALICE’）：需函数索引或表达式统计信息。
• 数据库优化手段：
  • PostgreSQL：支持多列统计信息、自定义统计目标（ALTER TABLE ... SET STATISTICS）。
  • MySQL：通过INDEX MERGE应对多条件查询，但需警惕索引合并的代价误判。
  • Oracle：提供SQL计划管理（SPM）固定最优计划，避免因估计错误导致性能回退。

7. 总结

基数估计与代价模型是查询优化器的核心，其准确性直接依赖统计信息的质量。实践中需定期更新统计信息，对复杂查询验证执行计划，必要时使用优化器提示（如/*+ INDEX(...) */）或计划引导技术（如SQL Plan Baseline）纠正偏差。