数据库查询优化中的代价估算原理解析（高级篇）

代价估算是查询优化器的核心环节，它通过预测不同执行计划的成本来选择最优方案。在基础篇中，我们介绍了代价模型的组成（CPU、I/O、网络成本）和基数估算的基本方法。本节将深入探讨代价估算中的高级技术，包括多列统计信息、直方图融合、相关性建模等难点及其解决方案。

1. 问题背景：为什么需要高级代价估算？

• 简单估算的局限性：
  基础篇中提到的统计信息（如单列直方图、NULL值比例、不同值数量）在处理多列条件或复杂表达式时误差较大。例如：

  WHERE age > 30 AND salary < 50000
  

  若age和salary独立分布，可简单使用选择率公式：
  sel(age>30 AND salary<50000) = sel(age>30) * sel(salary<50000)
  但若两列存在相关性（如年龄越大薪资越高），这种假设会严重低估实际结果集大小，导致优化器选择低效计划（如全表扫描而非索引扫描）。

2. 高级代价估算的核心技术

2.1 多列统计信息（Multi-Column Statistics）

• 原理：
  直接捕获多列之间的数据分布关系，避免独立性假设误差。例如，数据库（如MySQL、PostgreSQL）支持创建联合统计信息：

  ANALYZE TABLE employees UPDATE STATISTICS FOR COLUMNS (age, salary);
  

• 实现方式：
  • 多维直方图：将多列组合为一个维度，划分数据桶（Bucket）。但维度升高会导致桶数量指数级增长（维度诅咒），实际中较少使用。
  • 依赖系数（Dependency Coefficient）：
    通过统计两列的函数依赖程度（如皮尔逊相关系数）调整选择率。公式修正为：
    sel(A AND B) = sel(A) * sel(B) * correlation_factor
    其中correlation_factor基于历史查询数据或列值分布计算。

2.2 直方图融合（Histogram Fusion）

• 应用场景：
  当查询条件涉及同一列的不同取值范围时（如age BETWEEN 20 AND 30 OR age BETWEEN 40 AND 50），需合并多个直方图桶的统计信息。
• 步骤：
  1. 定位各条件对应的直方图桶（如桶1覆盖20-25岁，桶2覆盖26-30岁）。
  2. 按桶内数据分布线性插值，计算每个条件的选择率。
  3. 对OR条件使用公式：
     sel(A OR B) = sel(A) + sel(B) - sel(A AND B)
     若A和B互斥（如年龄不重叠），则直接相加。

2.3 表达式选择率估算

• 复杂表达式处理：
  对于包含函数或算术运算的条件（如WHERE YEAR(create_time) = 2023），优化器需推导底层列（create_time）的选择率。
• 方法：
  • 函数映射：将表达式逆推至列上的范围条件。例如：
    YEAR(create_time) = 2023 → create_time BETWEEN '2023-01-01' AND '2023-12-31'
  • 动态统计：当无法映射时（如WHERE LOWER(name) = 'alice'），可能通过采样（如随机页采样）实时估算选择率。

3. 代价模型的高级调整

3.1 成本系数校准（Cost Calibration）

• 问题：
  默认的CPU/I/O成本系数可能不匹配实际硬件性能（如SSD的随机I/O成本远低于机械硬盘）。
• 解决方案：
  数据库提供校准接口（如PostgreSQL的pg_test_fsync），通过基准测试调整成本系数，使模型更贴合实际环境。

3.2 渐进式更新统计信息

• 挑战：
  频繁更新的表（如电商订单表）可能导致统计信息过期。
• 策略：
  • 自动统计信息收集：数据库监控数据变化幅度，当增删改超过阈值（如10%行数变动）时触发重新统计。
  • 增量统计信息：仅更新变化数据的分布，避免全表扫描（如MySQL的innodb_stats_persistent_sample_pages）。

4. 实际案例：优化器如何选择连接顺序？

假设查询：

SELECT * FROM orders JOIN customers ON orders.cid = customers.id 
WHERE customers.region = 'Asia' AND orders.amount > 1000;

• 步骤1：基数估算
  • 计算customers.region = 'Asia'的选择率（如0.3）。
  • 计算orders.amount > 1000的选择率（如0.1）。
  • 若cid与id为外键关联，假设关联成功率为1。
• 步骤2：代价比较
  • 方案A：先过滤customers（减少中间结果），再与orders连接。
  • 方案B：先过滤orders，再与customers连接。
  • 优化器通过代价模型比较两种方案的I/O（访问索引/表）和CPU（连接操作）成本，选择总代价更低的方案。

5. 总结

高级代价估算通过多列统计信息、直方图融合等技术减少假设误差，结合成本系数校准使模型更贴近真实环境。然而，完全精确的估算仍不可行（如超高维相关性），因此现代数据库常结合动态采样或机器学习（如Google的Learned Cardinality）进一步优化。