虽千万里 日夜兼程

MySQL 8.0 执行计划学习

理解 MySQL 的执行计划是优化 SQL 查询的关键技能。MySQL 8.0 对优化器和执行器进行了大规模重构，引入了 Iterator 执行器、EXPLAIN ANALYZE、Hash Join、AccessPath、Hypergraph 优化器等重要改进。

整体架构变迁：5.7 vs 8.0

MySQL 5.7 的执行模型

在 MySQL 5.7 及更早版本中，查询的执行依赖于以下核心结构：

5.7 的执行器与优化器高度耦合，读取行的方式通过 C 函数指针（read_record 等抽象）在不同场景间切换，代码结构较为复杂且不易扩展。

MySQL 8.0 的架构跃迁

MySQL 8.0 从 8.0.16 开始引入全新的 Volcano Iterator 执行器，并在后续版本逐步完善。核心变化包括：

版本重要变更
8.0.16引入 Volcano Iterator 执行器基础框架（WL#11785, WL#12074）
8.0.18引入 Hash Join（Inner Join）和 EXPLAIN ANALYZE
8.0.20Hash Join 支持 Outer/Semi/Anti Join；不再要求等值条件
8.0.22引入 AccessPath 结构，解耦优化器与执行器
8.0.23引入 Hypergraph Join 优化器（实验性），支持 Bushy Tree
8.0.32引入 explain_format 系统变量，统一 EXPLAIN 输出控制

从宏观上看，8.0 的执行链路变为：

SQL → Parser → AST (Query_expression / Query_block)
    → Prepare/Rewrite (resolve, transform)
    → Optimize (Old Optimizer: JOIN::optimize → QEP_TAB
                 OR New Hypergraph Optimizer: FindBestQueryPlan)
    → AccessPath Tree（执行计划的中间表示）
    → CreateIteratorFromAccessPath → RowIterator Tree
    → 执行（Iterator 逐行拉取数据）

Volcano Iterator 执行器详解

设计理念

MySQL 8.0 的新执行器基于经典的 Volcano 模型（又称 Iterator 模型），由 Goetz Gräfe 在论文中提出。核心思想是：

RowIterator 基类

在源码中，基类定义位于 sql/iterators/row_iterator.h（早期版本在 sql/row_iterator.h）：

class RowIterator {
public:
    // 构造与析构
    RowIterator(THD *thd);
    virtual ~RowIterator();

    // 初始化/重置迭代器，可能执行实质工作（如排序）
    // 可多次调用以重新定位
    virtual bool Init() = 0;

    // 读取一行，放入 record buffer
    // 返回值：0=成功，-1=EOF，1=错误
    virtual int Read() = 0;

    // 用于 EXPLAIN 的描述信息
    virtual std::vector<std::string> DebugString() const;
};

核心 Iterator 实现

MySQL 8.0 实现了丰富的 Iterator 类型，每种对应一种物理操作。以下是关键的 Iterator 分类：

表访问类（Table Access）

Iterator功能说明
TableScanIterator全表顺序扫描
IndexScanIterator沿索引做全索引扫描
IndexRangeScanIterator索引范围扫描（封装 QUICK_SELECT_I）
RefIteratorREF 类型连接访问（索引查找）
RefOrNullIteratorREF_OR_NULL 类型访问
EQRefIteratorEQ_REF 类型访问（唯一索引查找）
ConstIterator读取常量表（0 或 1 行）
FullTextSearchIterator全文索引搜索
DynamicRangeIterator动态范围扫描（QS_DYNAMIC_RANGE）

连接类（Join）

Iterator功能说明
NestedLoopIterator嵌套循环连接（支持 Inner/Outer/Semi/Anti）
HashJoinIterator哈希连接（8.0.18+）
BKAIterator批量键访问连接（Batch Key Access）

辅助类（Auxiliary）

Iterator功能说明
FilterIterator条件过滤（WHERE/HAVING）
SortingIterator排序（封装 filesort）
LimitOffsetIteratorLIMIT/OFFSET 截断
AggregateIterator聚合/GROUP BY
WindowingIterator窗口函数计算
MaterializeIterator物化（临时表）操作
StreamingIterator流式聚合
RemoveDuplicatesIterator去重（DISTINCT）
TimingIterator计时 Iterator（用于 EXPLAIN ANALYZE）

Iterator Tree 示例

对于查询：

SELECT * FROM t1 JOIN t2 ON (t1.c1 = t2.c1) WHERE t1.c2 > 50;

8.0 可能生成如下 Iterator Tree：

→ Inner hash join (t2.c1 = t1.c1)
    → Table scan on t2
    → Hash
        → Filter: (t1.c2 > 50)
            → Table scan on t1

对应的 Iterator 结构为：

HashJoinIterator
├── (probe side) TableScanIterator(t2)
└── (build side) FilterIterator(t1.c2 > 50)
                    └── TableScanIterator(t1)

AccessPath：执行计划的统一中间表示

为何引入 AccessPath

MySQL 8.0.22 引入了 AccessPath 结构体（定义在 sql/join_optimizer/access_path.h），目的是将执行计划的描述与具体 Iterator 的创建解耦，同时兼容新旧两套优化器。

在此之前，旧优化器直接操作 QEP_TAB 和各种散落的数据结构来描述执行计划，新旧优化器很难共享执行路径的表示。

AccessPath 的结构设计

AccessPath 采用 变体（variant） 设计——单一结构体可以表示任意类型的操作（全表扫描、过滤、哈希连接、排序等），但同一时刻只持有一种类型：

struct AccessPath {
    enum Type {
        TABLE_SCAN,
        INDEX_SCAN,
        REF,
        REF_OR_NULL,
        EQ_REF,
        INDEX_RANGE_SCAN,
        FILTER,
        SORT,
        HASH_JOIN,
        NESTED_LOOP_JOIN,
        BKA_JOIN,
        MATERIALIZE,
        AGGREGATE,
        LIMIT_OFFSET,
        WINDOW,
        // ... 更多类型
    };

    Type type;

    // 通用字段（约 32 字节）
    double cost;             // 总代价
    double init_cost;        // 初始化代价
    double init_once_cost;   // 仅需执行一次的初始化代价
    double num_output_rows;  // 预估输出行数

    // 类型特定字段（约 40 字节的 union）
    // 例如 table_scan 包含 TABLE* 指针
    // hash_join 包含左右子 AccessPath* 等
};

这种固定大小的设计允许在搜索最优计划时原地替换，避免频繁内存分配——这在作为规划结构时尤为重要。

从 AccessPath 到 Iterator

优化阶段完成后，通过 CreateIteratorFromAccessPath() 函数遍历 AccessPath 树，为每个节点创建对应的 RowIterator：

unique_ptr_destroy_only<RowIterator> CreateIteratorFromAccessPath(
    THD *thd, AccessPath *path, JOIN *join,
    bool eligible_for_batch_mode)
{
    switch (path->type) {
        case AccessPath::TABLE_SCAN: {
            const auto &param = path->table_scan();
            iterator = NewIterator<TableScanIterator>(
                thd, param.table, path->num_output_rows, examined_rows);
            break;
        }
        case AccessPath::INDEX_SCAN: {
            const auto &param = path->index_scan();
            iterator = NewIterator<IndexScanIterator<...>>(
                thd, param.table, param.idx, ...);
            break;
        }
        case AccessPath::HASH_JOIN: {
            // 创建 HashJoinIterator，递归处理左右子路径
            ...
            break;
        }
        case AccessPath::FILTER: {
            // 创建 FilterIterator，递归处理子路径
            ...
            break;
        }
        // ... 其他类型
    }
}

核心关系：一个 AccessPath 对应一个 Iterator。

优化器流程详解

旧优化器（Old Optimizer）流程

旧优化器入口为 JOIN::optimize()，主要步骤：

逻辑变换阶段

  1. optimize_derived — 优化派生表/视图
  2. optimize_cond — 等值传播、常量传播
  3. prune_table_partitions — 分区裁剪
  4. optimize_aggregated_query — 隐式分组时的 COUNT/MIN/MAX 常量替换
  5. substitute_gc — 生成列替换优化

代价优化阶段 6. JOIN::make_join_plan() — 确定 Join 顺序和初始访问路径 7. substitute_for_best_equal_field — 基于等值条件选择最优字段 8. make_join_query_block — 注入外连接保护条件 9. optimize_distinct_group_order — 优化 ORDER BY/DISTINCT

代码生成阶段 10. alloc_qep(tables) — 创建 QEP_TAB 数组 11. make_join_readinfo — 细化执行计划的读取方式 12. make_tmp_tables_info — 设置临时表的使用策略 13. create_access_paths — 生成 AccessPath 树

新优化器（Hypergraph Optimizer）

Hypergraph 优化器是 8.0.23 引入的实验性特性（需手动开启 SET optimizer_switch='hypergraph_optimizer=on'），主要改进包括：

入口函数为 FindBestQueryPlan()，核心逻辑：

  1. CheckSupportedQuery — 检查查询是否被新优化器支持
  2. 将 top_join_list 转换为 JoinHypergraph 结构（节点 + 超边）
  3. EnumerateAllConnectedPartitions — 实现 DPhyp 枚举算法
  4. CostingReceiver — 对每个子计划进行代价估算，保留最优子计划
  5. 获得 root_path 后，处理 GROUP BY / 聚合 / HAVING / ORDER BY / LIMIT

Join Tree 类型对比

左深树 (Left-Deep Tree) — MySQL 5.7 及 8.0 旧优化器
                JOIN
               /    \
             JOIN    T4
            /    \
          JOIN    T3
         /    \
        T1    T2

灌木树 (Bushy Tree) — MySQL 8.0 新 Hypergraph 优化器
             JOIN
            /    \
         JOIN    JOIN
        /    \  /    \
       T1   T2 T3   T4

灌木树的搜索空间更大，但在某些查询模式下能找到更优的执行计划。

Hash Join 实现细节

引入历程

版本支持范围
8.0.18Inner Hash Join（仅等值连接，无索引时替代 BNL）
8.0.19移除独立的 hash_join optimizer_switch，统一使用 BNL/NO_BNL 控制
8.0.20支持 Outer/Semi/Anti Hash Join；不要求等值连接条件

工作原理

Hash Join 分为两个阶段：

Build 阶段（构建）：扫描较小的输入表，以连接属性为键构建内存哈希表。

Probe 阶段（探测）：扫描较大的输入表，对每一行在哈希表中进行常量时间查找。

关键特性：

EXPLAIN TREE 输出解读

EXPLAIN FORMAT=TREE
SELECT * FROM t1 JOIN t2 ON (t1.c1 = t2.c1)
                  JOIN t3 ON (t2.c1 = t3.c1);

输出：

→ Inner hash join (t3.c1 = t1.c1)
    → Table scan on t3
    → Hash
        → Inner hash join (t2.c1 = t1.c1)
            → Table scan on t2
            → Hash
                → Table scan on t1

注意：Hash Join 在 TRADITIONAL 和 JSON 格式中不可见（会显示为 BNL），只有 TREE 格式和 EXPLAIN ANALYZE 才能正确展示 Hash Join。

与 5.7 的关键差异

MySQL 5.7 没有 Hash Join。5.7 中无索引的等值连接只能使用 Block Nested Loop（BNL），性能差距显著——Hash Join 对每个输入只扫描一次，且使用常量时间查找匹配行。

EXPLAIN ANALYZE 深入解析

概述

EXPLAIN ANALYZE 在 MySQL 8.0.18 引入，是一个查询性能剖析工具：它会实际执行查询，并收集执行过程中每个 Iterator 的计时和计数信息。

语法限制：

输出信息解读

EXPLAIN ANALYZE SELECT * FROM t1 JOIN t2 ON (t1.c1 = t2.c2)\G

→ Inner hash join (t2.c2 = t1.c1)
    (cost=3.5 rows=5)
    (actual time=0.121..0.131 rows=1 loops=1)
    → Table scan on t2
        (cost=0.07 rows=5)
        (actual time=0.0126..0.0221 rows=5 loops=1)
    → Hash
        → Table scan on t1
            (cost=0.75 rows=5)
            (actual time=0.0372..0.0534 rows=5 loops=1)

每个 Iterator 节点展示：

信息含义
cost=X rows=Y优化器的代价估算和行数估算
actual time=A..BA=读第一行的时间（ms），B=读所有行的时间（ms）
rows=N实际返回的行数
loops=N该 Iterator 被调用的次数

当 loops > 1 时，actual time 和 rows 是所有循环的平均值。

性能诊断思路

与 5.7 的差异

MySQL 5.7 没有 EXPLAIN ANALYZE，也没有 TREE 格式输出。5.7 只有 TRADITIONAL 和 JSON 格式，且 JSON 格式从 5.7.2 才开始包含代价信息。

关键源码文件索引

以下是进行 8.0 执行计划代码迁移时需要重点关注的源码文件：

执行器核心

sql/iterators/row_iterator.h          — RowIterator 基类定义
sql/iterators/basic_row_iterators.h   — 基础 Iterator（TableScan, IndexScan 等）
sql/iterators/hash_join_iterator.h    — HashJoinIterator
sql/iterators/composite_iterators.h   — 复合 Iterator（Filter, Sort, Aggregate 等）
sql/iterators/timing_iterator.h       — 计时 Iterator（EXPLAIN ANALYZE 用）
sql/sql_executor.h / .cc              — 执行器入口，Iterator 构建逻辑

AccessPath 与计划生成

sql/join_optimizer/access_path.h      — AccessPath 结构定义与类型枚举
sql/join_optimizer/join_optimizer.h    — Hypergraph 优化器入口
sql/join_optimizer/make_join_hypergraph.h — Hypergraph 构建
sql/sql_optimizer.cc                  — JOIN::optimize() 旧优化器入口

EXPLAIN 相关

sql/opt_explain.cc                    — EXPLAIN 输出生成
sql/opt_explain_format.h              — EXPLAIN 格式化
sql/join_optimizer/explain_access_path.cc — AccessPath 的 EXPLAIN 描述

计划转换

sql/sql_executor.cc 中的 CreateIteratorFromAccessPath()
    — AccessPath → RowIterator 的核心转换函数
sql/sql_executor.cc 中的 create_access_paths()
    — 旧优化器 QEP_TAB → AccessPath 的转换

从 8.0 向 5.7 回迁的关键考量

架构差异总结

特性MySQL 5.7MySQL 8.0
执行器模型旧执行器（函数指针切换）Volcano Iterator 执行器
执行计划表示JOIN + QEP_TAB 数组AccessPath Tree → Iterator Tree
Join 算法Nested Loop + BNLNested Loop + Hash Join + BKA
Join 树形状仅左深树左深树 + Bushy Tree (Hypergraph)
EXPLAIN 格式TRADITIONAL + JSONTRADITIONAL + JSON + TREE
EXPLAIN ANALYZE不支持8.0.18+ 支持
优化器单一（Greedy/Cost-Based）旧优化器 + Hypergraph 优化器
GROUP BY 隐式排序默认排序不再隐式排序
Semijoin 优化First Match, Materialization, DuplicateWeedout, LooseScan同上 + 更好的 Iterator 集成
子查询转换基础更激进（scalar subquery → derived table 等）

迁移策略建议

不可直接迁移的部分：

可考虑迁移的部分：

迁移建议：

  1. 不要尝试移植 Iterator 框架到 5.7 —— 这需要重写整个执行器，工程量等同于从 5.7 升级到 8.0。
  2. 关注优化器阶段的改进 —— JOIN::optimize() 中的逻辑变换大多是增量修改，可以有选择地 cherry-pick。
  3. 谨慎处理 GROUP BY 行为差异 —— 8.0 移除了 GROUP BY 的隐式排序，迁移代码时需确认排序语义。
  4. 测试优化器开关的差异 —— 8.0 新增了多个 optimizer_switch 选项（如 subquery_to_derived、hypergraph_optimizer），回迁时需逐项评估。
  5. 使用 Optimizer Trace 对比 —— 在 8.0 和 5.7 上分别开启 optimizer_trace，对比关键查询的优化决策差异，以此指导迁移。

代码依赖关系图

                         ┌───────────────┐
                         │   SQL Parser   │
                         │ (Bison-based)  │
                         └───────┬───────┘
                                 │
                    ┌────────────▼────────────┐
                    │  Query_expression /      │
                    │  Query_block (AST)       │
                    └────────────┬────────────┘
                                 │
                    ┌────────────▼────────────┐
                    │  Prepare / Rewrite       │
                    │  (resolve, transform)    │
                    └────────────┬────────────┘
                                 │
               ┌─────────────────┼─────────────────┐
               │                                     │
    ┌──────────▼──────────┐           ┌──────────────▼──────────┐
    │  Old Optimizer       │           │  Hypergraph Optimizer    │
    │  JOIN::optimize()    │           │  FindBestQueryPlan()     │
    │  → QEP_TAB array     │           │  → DPhyp algorithm       │
    └──────────┬──────────┘           └──────────────┬──────────┘
               │                                     │
               │  create_access_paths()              │ (直接输出)
               │                                     │
               └─────────────────┬───────────────────┘
                                 │
                    ┌────────────▼────────────┐
                    │    AccessPath Tree       │ ← 8.0.22+ 新增
                    │    (中间计划表示)         │
                    └────────────┬────────────┘
                                 │
                    CreateIteratorFromAccessPath()
                                 │
                    ┌────────────▼────────────┐
                    │    RowIterator Tree      │ ← 8.0.16+ 新增
                    │    (Volcano 执行器)       │
                    └────────────┬────────────┘
                                 │
                           执行 (Init/Read)

5.7 中不存在虚线以下的部分（AccessPath 和 RowIterator），执行直接从 QEP_TAB 驱动。

实用 EXPLAIN 示例与分析

TRADITIONAL 格式（兼容 5.7）

EXPLAIN SELECT * FROM employees e
  JOIN departments d ON e.dept_id = d.id
  WHERE e.salary > 50000;

+----+-------------+-------+------+---------------+---------+---------+-------------+------+----------+-------------+
| id | select_type | table | type | possible_keys | key     | key_len | ref         | rows | filtered | Extra       |
+----+-------------+-------+------+---------------+---------+---------+-------------+------+----------+-------------+
|  1 | SIMPLE      | d     | ALL  | PRIMARY       | NULL    | NULL    | NULL        |   10 |   100.00 | NULL        |
|  1 | SIMPLE      | e     | ref  | idx_dept      | idx_dept| 4       | test.d.id   | 1000 |    33.33 | Using where |
+----+-------------+-------+------+---------------+---------+---------+-------------+------+----------+-------------+

TREE 格式（8.0 特有）

EXPLAIN FORMAT=TREE SELECT * FROM employees e
  JOIN departments d ON e.dept_id = d.id
  WHERE e.salary > 50000;

→ Nested loop inner join
    → Table scan on d
    → Filter: (e.salary > 50000)
        → Index lookup on e using idx_dept (dept_id=d.id)

EXPLAIN ANALYZE（8.0.18+ 特有）

EXPLAIN ANALYZE SELECT * FROM employees e
  JOIN departments d ON e.dept_id = d.id
  WHERE e.salary > 50000\G

→ Nested loop inner join (cost=1050.00 rows=3333)
   (actual time=0.285..45.122 rows=3250 loops=1)
    → Table scan on d (cost=1.50 rows=10)
       (actual time=0.035..0.052 rows=10 loops=1)
    → Filter: (e.salary > 50000) (cost=95.00 rows=333)
       (actual time=0.024..4.488 rows=325 loops=10)
        → Index lookup on e using idx_dept (dept_id=d.id) (cost=95.00 rows=1000)
           (actual time=0.020..3.105 rows=1000 loops=10)

分析要点：

← ClickHouse 索引机制学习
列式数据库为什么需要 Delta Store →