数据库

数据库内核

Posted by fjw on June 3, 2025

基础

查询优化器

数据库查询优化器生成执行计划主要使用两大类算法：基于规则的优化（RBO） 和基于代价的优化（CBO），现代数据库通常结合两者。以下是核心算法和技术：

1. 基于规则的优化（Rule-Based Optimization, RBO）

原理：依赖预定义的启发式规则重写查询，不关心数据分布。
常用规则：
- 选择下推：尽早执行过滤（WHERE 条件）。
- 投影下推：尽早减少列（SELECT 列）。
- 连接重排序：小表作为驱动表（如“小表左连大表”）。
- 消除笛卡尔积：避免不必要的连接。
缺点：无法根据实际数据量动态调整（例如，小表可能因过滤条件实际数据量很大）。

2. 基于代价的优化（Cost-Based Optimization, CBO）

通过估算执行计划的“代价”（CPU、I/O、内存等），选择代价最小的计划。关键步骤：

a. 搜索空间生成

枚举所有可能的连接顺序、连接算法（嵌套循环、哈希连接、排序合并）和访问路径（索引扫描、全表扫描）。
问题：可能的计划数量随表数量指数增长（如 n 个表有 n! 种连接顺序）。

b. 代价估算

依赖统计信息：表大小、列分布直方图、索引基数等。
估算公式：
- 选择基数：sel = 1 / DISTINCT_COUNT（等值条件）。
- 连接结果大小：|R ⨝ S| = |R| * |S| * sel。
- I/O 代价：页面读取数 × 权重。
- CPU 代价：比较操作数 × 权重。

c. 搜索算法

（1）动态规划（System R 算法）

用于连接顺序优化，通过递推计算子集最优解。
示例：4 个表 {A,B,C,D}：
- 步骤1：计算所有单表代价。
- 步骤2：计算所有 2 表连接最优代价（如 {A,B}、{A,C}…）。
- 步骤3：基于子集结果递推（如 {A,B,C} 可通过 {A,B}+C 或 {A,C}+B 等组合）。
局限性：表过多时仍会组合爆炸（通常限制在 10-15 张表）。

（2）贪心算法

逐步选择“局部最优”连接（如最小结果集）。
更快但可能错过全局最优解。

（3）随机优化（如遗传算法、模拟退火）

用于复杂查询（>15 张表），在有限时间内搜索近似最优解。

（4）基于变换的搜索（如 Volcano/Cascades 框架）

将规则与代价结合：
- 用“规则”生成候选计划（如逻辑等价变换）。
- 用“代价模型”选择最优。
支持代价驱动的规则触发（如仅当索引扫描代价更低时才应用索引规则）。

3. 现代优化器的实际应用

PostgreSQL：基于代价的动态规划 + 遗传算法（表多时）。
MySQL：代价模型 + 启发式规则（如优先使用索引）。
Oracle：CBO 为主，内置多种优化模式（如 FIRST_ROWS 或 ALL_ROWS）。
SQL Server：Cascades 框架的变体，支持多阶段优化。

4. 高级优化技术

自适应优化：根据运行时反馈调整计划（如执行中重新选择连接算法）。
参数化查询优化：对参数化查询（如 WHERE id = ?）生成多个候选计划缓存。
机器学习辅助：使用历史查询数据预测最优计划（如 PostgreSQL 的 pg_hint_plan）。