[小技巧49]深入 MySQL JOIN 算法：从执行计划到性能优化

一、MySQL 支持的 JOIN 算法概览

MySQL 并不直接让用户指定使用哪种 JOIN 算法，而是由优化器（Optimizer） 根据表结构、索引、数据量、统计信息等自动选择最高效的执行策略。目前主要支持以下几种算法：

1. Simple Nested-Loop Join（SNLJ）

• 原理：对驱动表（外层表）的每一行，遍历被驱动表（内层表）的所有行进行匹配。
• 缺点：I/O 成本极高，尤其当内层表无索引时，复杂度为 O(N×M)。
• 实际使用：MySQL 几乎不会在生产环境中使用纯 SNLJ，通常会升级为 Block 或 Index 变体。

2. Block Nested-Loop Join（BNLJ）

• 原理：引入 Join Buffer，一次性读取驱动表的多行到内存缓冲区，再用整个缓冲区去扫描内层表，减少内层表的重复扫描次数。
• 触发条件：被驱动表没有可用索引用于连接条件。
• 配置参数：join_buffer_size 控制缓冲区大小（默认 256KB）。
• 注意：BNLJ 仍需全表扫描内层表，大数据量下性能较差。

3. Index Nested-Loop Join（INLJ）

• 原理：利用被驱动表上的索引，对驱动表的每一行，通过索引快速查找匹配行。
• 触发条件：被驱动表的连接字段上有有效索引（如 B+Tree 索引）。
• 优势：避免全表扫描，I/O 大幅降低，是 OLTP 场景中最常见的高效 JOIN 方式。
• 最佳实践：确保小表作驱动表，大表作被驱动表且有索引。

4. Hash Join（MySQL 8.0 新增）

• 引入版本：MySQL 8.0.18正式支持。
• 原理：
• 选择较小的表（或结果集）构建 Hash 表（内存中）；
• 遍历另一张表，对每行计算哈希值并在 Hash 表中查找匹配。
• 优势：无需索引即可高效处理等值连接（Equi-Join），特别适合大表 JOIN 且无索引的场景。
• 限制：
  • 仅支持 等值连接（如 a.id = b.id），不支持 <, > 等非等值条件；
  • 若内存不足，会退化为磁盘 Hash（性能下降）；
  • 在 EXPLAIN 中显示为 HashJoin。

版本差异说明：
MySQL 5.7 及更早版本不支持 Hash Join，所有无索引的 JOIN 都只能使用 BNLJ，这也是 8.0 在复杂分析查询上性能显著提升的原因之一。

二、算法选择流程图

以下为 MySQL 优化器选择 JOIN 算法的逻辑流程（可用于绘制流程图）：

开始
│
├─ 是否为等值连接（Equi-Join）？
│ ├─ 否 → 尝试 INLJ（若有索引）或 BNLJ（若无索引）
│ └─ 是 →
│ ├─ 被驱动表是否有可用索引？
│ │ ├─ 是 → 使用 Index Nested-Loop Join (INLJ)
│ │ └─ 否 →
│ │ ├─ MySQL ≥ 8.0.18？
│ │ │ ├─ 是 → 使用 Hash Join（若内存足够）
│ │ │ └─ 否 → 使用 Block Nested-Loop Join (BNLJ)
│ │ └─ （注：即使有 Hash Join，优化器仍可能因成本估算选择 BNLJ）
│
结束

三、JOIN 算法对比表

注：N、M 分别为驱动表和被驱动表的行数。

四、性能调优建议

示例：

EXPLAIN FORMAT=tree
SELECT * FROM orders o JOIN customers c ON o.cust_id = c.id;

输出中若含 -> Hash Join …，即表示使用了 Hash Join。

五、驱动表和被驱动表

1. 基本定义

💡 简单记忆：
驱动表 = 主动出击的一方
被驱动表 = 被查询的一方

2. 如何确定哪张是驱动表？

方法 1：看 EXPLAIN 输出（最可靠！）

在 MySQL 中，EXPLAIN 结果中靠前的表通常是驱动表（但要注意嵌套循环的方向）。

更准确的方法是看 Extra 列 或使用 EXPLAIN FORMAT=tree（MySQL 8.0+）。

示例 1：普通 JOIN

EXPLAIN
SELECT * FROM orders o JOIN customers c ON o.cust_id = c.id;

假设输出：

+—-+————-+——-+————+——+—————+———+———+——————+——+———-+——-+
| id | select_type | table | type | key | key_len | ref | rows | Extra |
+—-+————-+——-+————+——+—————+———+———+——————+——+———-+——-+
| 1 | SIMPLE | c | ALL | NULL | NULL | NULL | 10000 | |
| 1 | SIMPLE | o | ref | idx_cust_id | 4 | test.c.id | 5 | Using index |
+—-+————-+——-+————+——+—————+———+———+——————+——+———-+——-+

🔍 分析：

• customers (c) 先出现，且 type=ALL（全表扫描）→ 它是驱动表
• orders (o) 后出现，用 ref 索引查找 → 它是被驱动表

所以：小表 customers 驱动大表 orders 的索引查找，这是高效做法！

方法 2：使用 EXPLAIN FORMAT=tree（MySQL 8.0 推荐）

EXPLAIN FORMAT=tree
SELECT * FROM orders o JOIN customers c ON o.cust_id = c.id;

输出可能类似：

-> Nested loop inner join
-> Table scan on c — 驱动表
-> Index lookup on o using idx_cust_id (cust_id = c.id) — 被驱动表

这里明确显示：c 是驱动表，o 是被驱动表

方法 3：经验法则

• 小表通常作驱动表：优化器倾向于让结果集小的表驱动大的。
• 有 WHERE 条件过滤的表更可能成为驱动表：因为中间结果集更小。
• LEFT JOIN 中，左表一定是驱动表（因为语义要求保留左表所有行）。

示例 2：LEFT JOIN

SELECT * FROM customers c LEFT JOIN orders o ON c.id = o.cust_id;

• customers 一定是驱动表（即使它很大），因为 LEFT JOIN 语义要求遍历 customers 所有行。

3. 经典例子对比

场景设定：

• customers 表：1 万行（小表）
• orders 表：100 万行（大表）
• orders.cust_id 上有索引

好情况：小表驱动大表（高效 INLJ）

— 优化器自动选择 customers 作驱动表
SELECT * FROM customers c JOIN orders o ON c.id = o.cust_id;

• 驱动表：customers（1 万行）
• 被驱动表：orders（用索引查找，每次 O(log N)）
• 总成本 ≈ 1 万 × log(100 万) ≈ 1 万 × 20 = 20 万次操作

坏情况：大表驱动小表（低效）

— 假设因统计信息错误，优化器选 orders 作驱动表
SELECT * FROM orders o JOIN customers c ON o.cust_id = c.id;

• 驱动表：orders（100 万行）
• 被驱动表：customers（即使有主键索引，也要查 100 万次）
• 总成本 ≈ 100 万 × log(1 万) ≈ 100 万 × 13 = 1300 万次操作（慢 65 倍！）

🔧 解决方案：用 STRAIGHT_JOIN 强制顺序（谨慎使用）：

SELECT * FROM customers c STRAIGHT_JOIN orders o ON c.id = o.cust_id;

STRAIGHT_JOIN 是 MySQL 中一个强制控制表连接顺序的语法关键字，它会覆盖优化器的自动决策。
严格按照 FROM子句中表的书写顺序来执行，JOIN左边的表作为驱动表，右边的表作为被驱动表。

4. 常见误区澄清

5. 总结：

驱动表 = 先扫描的表 = EXPLAIN 中靠前的表（在 Nested Loop 中）
被驱动表 = 被查找的表 = 是否有索引决定性能的关键
优化核心：让小表/过滤后小的结果集作驱动表，大表作被驱动表且有索引

六、实际应用

1. 第一步：创建表结构

— 创建 customers 表（小表，主键为 id）
CREATE TABLE customers (
id INT PRIMARY KEY,
name VARCHAR(100) NOT NULL,
email VARCHAR(150)
);

— 创建 orders 表（大表，cust_id 为外键，有索引）
CREATE TABLE orders (
order_id INT PRIMARY KEY,
cust_id INT NOT NULL,
amount DECIMAL(10,2),
order_date DATE,
— 建议：为 JOIN 字段添加索引（用于触发 INLJ）
INDEX idx_cust_id (cust_id)
);

💡 说明：

• customers 模拟 小表（比如 100 行）
• orders 模拟 大表（比如 10,000 行）
• orders.cust_id 上有索引 → 可触发 Index Nested-Loop Join (INLJ)

2. 第二步：插入模拟数据

1. 插入 100 个客户

— 插入 100 个客户（id 从 1 到 100）
INSERT INTO customers (id, name, email)
WITH RECURSIVE nums AS (
SELECT 1 AS n
UNION ALL
SELECT n + 1 FROM nums WHERE n < 100
)
SELECT
n AS id,
CONCAT('Customer_', LPAD(n, 3, '0')) AS name,
CONCAT('customer', n, '@example.com') AS email
FROM nums;

2. 插入 10,000 条订单（随机分配给 100 个客户）

— 插入 10,000 条订单，cust_id 随机在 1~100 之间
INSERT INTO orders (order_id, cust_id, amount, order_date)
WITH RECURSIVE nums AS (
SELECT 1 AS n
UNION ALL
SELECT n + 1 FROM nums WHERE n < 10000
)
SELECT
n AS order_id,
FLOOR(1 + RAND() * 100) AS cust_id, — 随机客户 ID
ROUND(10 + RAND() * 990, 2) AS amount, — 金额 10~1000
DATE_SUB(CURDATE(), INTERVAL FLOOR(RAND() * 365) DAY) AS order_date
FROM nums;

3. 第三步：验证数据

— 查看表行数
SELECT COUNT(*) FROM customers; — 应为 100
SELECT COUNT(*) FROM orders; — 应为 10000

— 查看索引
SHOW INDEX FROM orders;
— 应看到 idx_cust_id 在 cust_id 上

4. 第四步：体验不同 JOIN 行为

1. 正常 JOIN（应使用 INLJ）

mysql> EXPLAIN FORMAT=tree SELECT c.name, o.amount FROM customers c JOIN orders o ON c.id = o.cust_id WHERE c.id <= 10\\G
*************************** 1. row ***************************
EXPLAIN: –> Nested loop inner join (cost=289.67 rows=999)
–> Filter: (c.id <= 10) (cost=2.26 rows=10)
–> Index range scan on c using PRIMARY over (id <= 10) (cost=2.26 rows=10)
–> Index lookup on o using idx_cust_id (cust_id=c.id) (cost=19.75 rows=100)

1 row in set (0.00 sec)

符合预期：Index lookup on o using idx_cust_id

2. 强制无索引 JOIN（先删索引，体验 BNLJ / Hash Join）

— 删除索引（谨慎操作！仅用于测试）
DROP INDEX idx_cust_id ON orders;

— 再次执行 EXPLAIN
mysql> EXPLAIN FORMAT=tree SELECT c.name, o.amount FROM customers c JOIN orders o ON c.id = o.cust_id WHERE c.id <= 10\\G
*************************** 1. row ***************************
EXPLAIN: –> Nested loop inner join (cost=4502.20 rows=9991)
–> Filter: (o.cust_id <= 10) (cost=1005.35 rows=9991) — 先扫描 orders 表（驱动表）
–> Table scan on o (cost=1005.35 rows=9991) — 全表扫描 orders（10,000 行）
–> Single–row index lookup on c using PRIMARY (id=o.cust_id) (cost=0.25 rows=1) — 用主键查 customers

1 row in set (0.01 sec)

虽然JOIN 条件中写的是FROM customers c JOIN orders o ON c.id = o.cust_id 但MySQL
并没有用 customers 作驱动表，而是反过来用 orders 作驱动表，customers 反而成了被驱动表！
驱动表：orders（全表扫描）
被驱动表：customers（通过主键 PRIMARY 索引查找）

为什么会这样？为什么不用 customers 驱动？

因为优化器做了成本估算：

“与其先读 10 行 customers（满足 c.id <= 10），再去 orders 里找匹配（但 orders.cust_id 没索引，每次都要全表扫 10,000 行）……

不如直接全表扫 orders（10,000 行），对每行用 cust_id 去 customers 主键索引里查一下（每次 O(1)），总成本更低。”

成本对比（估算）：

所以优化器选了 方案B —— 虽然看起来“反直觉”，但在 orders.cust_id 无索引 的前提下，这是更优解！

这说明了什么？

⚠️ 注意：这不是 Hash Join，因为虽然等值连接，但优化器认为 Nested Loop + 主键查找更便宜。

总结 & 行动建议

3. 测试 STRAIGHT_JOIN

mysql> EXPLAIN FORMAT=tree SELECT c.name, o.amount FROM customers c STRAIGHT_JOIN orders o ON c.id =
o.cust_id\\G
*************************** 1. row ***************************
EXPLAIN: –> Inner hash join (o.cust_id = c.id) (cost=99927.47 rows=99910)
–> Table scan on o (cost=1.07 rows=9991)
–> Hash
–> Table scan on c (cost=10.25 rows=100)

1 row in set (0.00 sec)

正确理解：Hash Join 的执行顺序 ≠ 驱动/被驱动关系

** 在 Nested-Loop Join（NLJ） 中：**

• 先扫描的表 = 驱动表（外层表）
• 后查找的表 = 被驱动表（内层表）
• 顺序 = 执行逻辑

这时，“先扫谁”确实代表驱动关系。

在 Hash Join 中：

执行分为两个独立阶段：

阶段 1️⃣：Build（构建哈希表）

• 选择较小的表（或优化器认为更合适的表）加载到内存，建立哈希表；

• 在你的输出中：
  → customers 被用来构建哈希表

  -> Hash
  -> Table scan on c ← 这是 Build 阶段！

阶段 2️⃣：Probe（探测匹配）

• 全表扫描另一张表，对每行去哈希表中查找匹配；

• 在输出中：

  -> Table scan on o ← 这是 Probe 阶段！

关键点：

EXPLAIN FORMAT=tree 中，Probe 表写在前面，Build 表写在 Hash 子节点里 —— 这是 MySQL 的显示习惯，不代表执行先后或驱动关系！

实际上，Build 阶段必须先完成，才能开始 Probe。

所以真实执行顺序是：

谁是“驱动表”？

在 传统术语中，“驱动表”源于 Nested-Loop 模型。
但在 Hash Join 语境下，我们更准确的说法是：

而 STRAIGHT_JOIN 的语义是：

“保持 FROM 中的连接顺序不变”，即逻辑上是 customers JOIN orders，不能被重排为 orders JOIN customers。

MySQL 在实现 Hash Join 时，尊重了这个逻辑顺序，并据此决定：

• 连接条件是 c.id = o.cust_id
• 优化器自由选择哪边做 Build（通常选小的）

所以：

• 从 SQL 语义和 STRAIGHT_JOIN 约束看：customers 是左表，逻辑上的“驱动方”；
• 从 Hash Join 物理执行看：customers 是 Build 表，orders 是 Probe 表；
• 绝不是 orders 驱动了 customers！

总结

在 Hash Join 的 EXPLAIN FORMAT=tree 中，Hash 子节点里的表才是 Build 表（相当于传统驱动表），外面的表是 Probe 表。

七、面试题

面试题 1：

“MySQL 中 JOIN 为什么有时候很慢？可能有哪些原因？”

参考答案：

• 被驱动表缺少索引，导致使用 BNLJ（5.7）或低效 Hash Join（8.0）；
• 驱动表过大，导致 Join Buffer 溢出或 Hash 表过大；
• 数据分布倾斜，导致 Hash 冲突严重；
• 统计信息过期，优化器误判成本，选择了次优算法；
• 使用了非等值连接，无法使用 Hash Join。

面试题 2：

“MySQL 8.0 的 Hash Join 和传统 BNLJ 有什么区别？什么情况下 Hash Join 更优？”

参考答案：

• 区别：Hash Join 基于哈希表实现，时间复杂度接近线性 O(N+M)，而 BNLJ 是 O(N×M / buffer)；Hash Join 不依赖索引，但仅支持等值连接。
• 更优场景：两表都较大、无可用索引、且为等值连接时，Hash Join 显著优于 BNLJ。例如数据仓库中的事实表与维度表关联。

面试题 3：

“在 MySQL 中，当执行一个等值连接（比如 a.id = b.id），并且连接字段上存在索引时，MySQL 通常会使用哪种 JOIN 算法？为什么？在什么情况下即使有索引也可能不使用该算法？”

参考答案

第一层：直接回答核心算法

在大多数情况下，MySQL 会使用 Index Nested-Loop Join（INLJ）。
因为被驱动表（inner table）的连接字段上有索引，优化器可以对驱动表的每一行，通过索引快速查找匹配行，避免全表扫描，从而大幅降低 I/O 和 CPU 开销。

第二层：解释执行逻辑

具体来说：

• 优化器会选择结果集更小的表作为驱动表；
• 对驱动表的每一行，取出连接键的值；
• 利用被驱动表上的索引进行点查（point lookup），获取匹配行；
• 整个过程的时间复杂度约为 O(N × log M)，远优于无索引时的 O(N×M)。

第三层：说明为何不用 Hash Join（即使 MySQL 8.0+）

虽然 MySQL 8.0 引入了 Hash Join，但在被驱动表有高效索引的场景下，优化器通常仍优先选择 INLJ，因为：

• INLJ 内存开销极小；
• 若驱动表很小（如 OLTP 场景），INLJ 的总成本更低；
• Hash Join 需要将驱动表加载到内存构建哈希表，可能带来不必要的内存压力。

第四层：指出例外情况

即使连接字段有索引，以下情况也可能导致不使用 INLJ：

第五层：如何验证？

可通过 EXPLAIN FORMAT=tree 查看执行计划：

• 若出现 Index lookup on … using <index_name>，说明使用了 INLJ；
• 若出现 Inner hash join，说明使用了 Hash Join；
• 传统 EXPLAIN 中，被驱动表的 type 为 ref 或 eq_ref，也暗示 INLJ。