数据库查询优化中的代价模型（Cost Model）与基数估算（Cardinality Estimation）

1. 问题描述

在数据库查询优化中，代价模型（Cost Model） 和 基数估算（Cardinality Estimation） 是优化器选择最优执行计划的核心依据。优化器需要预测不同执行计划的代价（如CPU、I/O、内存开销），而代价计算依赖于对中间结果集大小的估算（即基数估算）。如果基数估算不准确，可能导致优化器选择低效计划，例如本应使用索引扫描却误选全表扫描。

2. 基数估算（Cardinality Estimation）

2.1 什么是基数估算？

基数估算是预测查询中每个操作（如过滤、连接、分组）产生的结果集行数。例如：

SELECT * FROM users WHERE age > 30;  

优化器需要估算满足 age > 30 的行数，以决定是否使用索引。

2.2 基数估算的方法

1. 统计信息（Statistics）：

   • 直方图（Histogram）：将数据分布划分为多个桶（buckets），记录每个桶的数值范围、频率和不同值数量。
     • 例如：age 字段的直方图可能显示 [0,20]: 100行, [21,40]: 150行，从而估算 age > 30 的行数。
   • 不同值数量（NDV, Number of Distinct Values）：用于估算等值条件的基数（如 age = 30）。
   • 空值比例、数据密度等。

2. 假设与简化：

   • 均匀分布假设：若缺乏详细统计信息，优化器可能假设数据均匀分布（实际数据往往倾斜，导致估算误差）。
   • 独立性假设：假设多个条件之间独立，例如 WHERE age > 30 AND city = 'Beijing' 的基数估算为：

\[ \text{基数} = \text{表总行数} \times \frac{\text{满足age>30的行比例}}{\text{满足city='Beijing'的行比例}} \]

 但实际中 `age` 和 `city` 可能相关（如年轻人更多聚集于大城市），导致估算偏离。  

3. 复杂条件的基数估算：
   • 多列统计信息：现代数据库（如Oracle、SQL Server）支持收集多列组合的统计信息，缓解独立性假设问题。
   • 动态采样：对少量数据实际执行查询，推断整体基数。

3. 代价模型（Cost Model）

3.1 代价模型的组成

代价模型将基数估算转换为具体代价值，通常包括：

• I/O代价：数据从磁盘读取到内存的开销（与页数相关）。
• CPU代价：处理数据（比较、计算、排序）的消耗。
• 网络代价（分布式数据库）：节点间数据传输成本。
• 内存代价：临时存储中间结果的资源占用。

3.2 代价计算示例

以简单的索引扫描 vs. 全表扫描为例：

• 全表扫描代价：

\[ \text{Cost} = \text{数据页数} \times \text{单页I/O代价} \]

• 索引扫描代价：

\[ \text{Cost} = \text{索引页数} \times \text{单页I/O代价} + \text{回表代价} \times \text{预估行数} \]

其中回表代价是通过索引定位到数据页的随机I/O开销。

3.3 代价模型的校准

数据库会根据硬件环境（如磁盘速度、内存大小）校准代价参数，例如：

• 调整随机I/O与顺序I/O的代价比例；
• 设置内存排序与磁盘排序的代价阈值。

4. 优化器的工作流程

1. 解析查询：生成逻辑计划（如关系代数表达式）。
2. 生成候选计划：利用等价变换规则（如改变连接顺序、选择下推）生成多个物理计划。
3. 基数估算与代价计算：对每个计划估算中间结果基数，计算总代价。
4. 选择最优计划：选取代价最小的计划执行。

5. 常见问题与优化

• 基数估算误差：数据倾斜、多列相关性、复杂表达式（如 LIKE '%abc'）易导致估算不准。
  • 解决方案：更新统计信息、使用提示（Hint）强制计划、升级数据库版本（如AI增强的基数估算）。
• 代价模型偏差：硬件变化或负载特征未反映在模型中。
  • 解决方案：手动调整代价参数（如 PostgreSQL 的 random_page_cost）。

6. 总结

基数估算和代价模型是查询优化器的“大脑”，其准确性直接决定查询性能。理解其原理有助于DBA通过统计信息管理、查询重写等手段规避优化器误判，提升数据库效率。