Mysql JOIN 的物理执行流程

一、关联字段在两个表中都没有索引

当两个参与join的表在关联字段上都没有索引时，MySQL 无法使用高效的索引树搜索，而是被迫采用Block Nested-Loop Join (BNL)算法。

为了清晰讲解物理流程，我们设定如下 SQL 示例 ：

• 表t1t1t1（驱动表）：100 行数据，字段bbb无索引 。
• 表t2t2t2（被驱动表）：1000 行数据，字段bbb无索引 。
• SQL 语句：select * from t1 straight_join t2 on (t1.b=t2.b);

1. 物理执行流程详解

在物理层面，该操作不再是“点对点”的查找，而是一次大规模的“内存对撞”过程 ：

1. 扫描并装载驱动表：
   MySQL 首先全表扫描驱动表t1t1t1，将这 100 行数据全部读入线程内存join_buffer中 。
   • 注意：由于是select *，整行数据都会被存入内存 。
2. 顺序扫描被驱动表：
   随后，MySQL 开始全表扫描被驱动表t2t2t2。它每从磁盘读入t2t2t2的一行数据，并不会立即写回结果集 。
3. 内存高速比对：
   对于t2t2t2读入内存的每一行，MySQL 都会将其与join_buffer中缓存的 100 行t1t1t1数据逐一进行等值判断 。
   • 如果匹配成功，则作为结果集的一行返回。
4. 循环直至结束：
   重复上述过程，直到t2t2t2的 1000 行数据全部扫描并比对完毕。

2. 核心物理指标

在这个示例中，虽然 SQL 看似简单，但底层的物理开销非常巨大 ：

• 磁盘扫描行数：100+1000=1100100 + 1000 = 1100100+1000=1100行 。
  • 驱动表t1t1t1扫一遍，被驱动表t2t2t2扫一遍。
• 内存判断次数：100×1000=10100 \times 1000 = \mathbf{10}100×1000=10万次。
  • 这是最消耗 CPU 资源的地方。因为没有索引辅助，每一行都必须和内存中所有的行“对撞”一次。

3. 极端情况：如果join_buffer不够大怎么办？

如果驱动表t1t1t1很大（例如 10 万行），而join_buffer只能放得下 1 万行，物理流程会演变为分段处理（Block）：

1. 从t1t1t1取出前 1 万行放入join_buffer。
2. 扫描t2t2t2全表（100 万行），在内存中进行1万×100万1\text{万} \times 100\text{万}1万×100万次比对 。
3. 清空join_buffer。
4. 从t1t1t1取出接下来的 1 万行，再次全表扫描t2t2t2进行比对 。

物理后果：
此时，被驱动表t2t2t2会被重复扫描多次。如果t1t1t1被分成KKK段，总扫描行数将变成N+K×MN + K \times MN+K×M。这会产生剧烈的磁盘 IO 波动，并严重污染 Buffer Pool，导致整个数据库实例响应变慢。

---

二、关联字段在其中一个表中有索引

当join关联字段在两个表中呈现“一有一无”的索引状态时，MySQL 的物理执行过程取决于优化器对驱动表（Driver Table）的选择。

核心结论是：MySQL 优化器会为了利用索引而极力避免BNL 算法，通常会选择将带索引的表作为被驱动表。

1. 物理流程的两种可能性

假设表t1t1t1无索引（100 行），表t2t2t2有索引（1000 行）。

情况一：带索引的表t2t2t2作为“被驱动表”（这是最优选）

此时物理上执行的是Index Nested-Loop Join (NLJ)算法 ：

1. 扫描驱动表：全表扫描不带索引的t1t1t1（100 行）。
2. 点对点查找：每读出t1t1t1的一行，就拿着关联字段的值去t2t2t2的索引树上搜索。
3. 物理开销：
   • 扫描行数：100+100100 + 100100+100（假设 1:1 匹配）。
   • 计算复杂度：100×log⁡21000100 \times \log_2 1000100×log2​1000。
4. 结果：这是最快的方式，因为利用了索引的对数级搜索能力。

情况二：不带索引的表t1t1t1作为“被驱动表”（这是最差选）

如果因为某些极端原因（如t2t2t2过滤后的结果集极小），优化器选了t1t1t1倒过来驱动，则物理上执行的是Block Nested-Loop Join (BNL)算法 ：

1. 扫描驱动表：扫描带索引的t2t2t2，将数据放入join_buffer。

2. 暴力对撞：由于被驱动表t1t1t1没有索引，系统必须对t1t1t1执行全表扫描。

3. 内存比对：将t1t1t1的每一行与内存中的数据进行暴力比对。

4. 物理开销：

   • 内存判断次数：1000×100=101000 \times 100 = \mathbf{10}1000×100=10万次。

5. 结果：性能极差，且会大量消耗 CPU 资源 。

2. 优化器的“智取”：索引权重高于表大小

在之前的讲解中，我们提到过“小表驱动大表”的原则 。但在“一有一无”的情况下，是否有索引对算法效率的影响（NLJ vs BNL）通常远超表的大小。

具体示例：

• 表AAA：100 行，没有索引。
• 表BBB：100 万行，有索引。

虽然表AAA很小，但如果选AAA驱动BBB，可以走索引（NLJ）；如果选BBB驱动AAA，则必须走暴力内存比对（BNL）。

• A 驱动 B (NLJ)：扫描 100 行 + 100 次索引树搜索→\rightarrow→毫秒级完成。
• B 驱动 A (BNL)：扫描 100 万行 + 1 亿次内存比对→\rightarrow→秒级甚至分钟级。

因此，物理交互的真相是：优化器会优先选择那个不带索引的表作为驱动表，从而强行让那个带索引的表成为被驱动表，以触发 NLJ 或 BKA 算法来提升性能 。

---

三、BKA优化NLJ算法

BKA（Batched Key Access）算法是 MySQL 对 Index Nested-Loop Join（NLJ）的进一步优化。它的核心逻辑是利用join_buffer批量缓存驱动表的数据，并配合MRR（Multi-Range Read）技术，将原本随机的磁盘访问转化为顺序访问。

以下是关于 BKA 算法的详细拆解：

1. 适用场景

BKA 算法主要适用于以下场景：

• 使用了索引关联：即被驱动表的关联字段上有索引（这是 NLJ 算法的前提）。
• 磁盘 IO 瓶颈：当被驱动表数据量较大且无法全部加载进内存时，随机回表的代价很高，此时 BKA 的提速效果最显著。
• 配置开启：由于 BKA 依赖于 MRR，而 MRR 的开启策略通常较为保守，因此需要手动设置参数以确保 BKA 能够生效：

  setoptimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

2. 物理执行流程

传统的 NLJ 算法是“拿一行驱动表数据，去被驱动表查一次索引”。而 BKA 算法改成了“批量处理”：

1. 批量读入驱动表：从驱动表t1中读取满足条件的行，并存入join_buffer内存中。
2. 构造批量键值：当join_buffer存满或者数据读完后，将这批记录的关联字段（Key）一次性发送给被驱动表t2的引擎层。
3. 触发 MRR 排序：被驱动表t2接收到这批 Key 后，利用 MRR 机制进行如下物理操作：
   • 在普通索引树上找到所有匹配记录的主键 ID。
   • 将这些 ID 放入read_rnd_buffer中进行递增排序。
   • 按照排序后的主键顺序，顺序访问主键索引（聚簇索引）拉取整行数据。
4. 返回结果：将取出的t2数据与join_buffer中的t1原始数据进行匹配，返回给 Server 层。

3. 算法开销分析

BKA 虽然极大地提升了查询速度，但也带来了一定的资源开销：

• 内存开销：
  • join_buffer：用于缓存驱动表的数据，其大小由join_buffer_size决定 。
  • read_rnd_buffer：用于 MRR 阶段的主键 ID 排序，大小由read_rnd_buffer_size决定。
• CPU 开销：
  • 在 MRR 阶段，系统需要对主键 ID 序列进行排序操作。如果一次性处理的 ID 数量极其庞大，会产生一定的 CPU 计算负担。
• IO 模式改变（正向开销）：
  • 扫描行数不变：物理上扫描的行数与传统的 NLJ 并没有区别 。
  • 性能提升根源：开销的减少主要源于减少了磁头寻道时间。将随机的磁盘跳转改成了连续的块读取，这在机械硬盘上是量级的提升，在 SSD 上也能减少内部控制器的随机寻址压力。

---

四、HashJoin优化BNL算法

由于 MySQL 5.6 和 5.7 版本在内核中并未内置原生的 Hash Join 执行引擎，文档主要通过“应用层 Hash Join”来展示其逻辑，以解决被驱动表无索引时 Block Nested-Loop Join (BNL) 算法性能低下的问题。

Hash Join 的核心物理逻辑是将原本需要“暴力比对”的N×MN \times MN×M次判断，通过在内存中构建哈希表，降级为近似O(1)O(1)O(1)的定位操作。

1. 适用场景

• 无索引关联：Join 关联字段在两张表中都没有索引，导致无法使用 NLJ 或 BKA 算法。
• 等值连接：仅适用于等值 Join（如t1.b = t2.b），因为哈希表无法处理范围查询（如>或<）。
• 内存充足：内存（或应用端内存）必须能够容纳较小表（Build Table）过滤后的全部数据集。

2. 物理执行流程

以select * from t1 join t2 on t1.b = t2.b为例，假设t1t1t1为 1000 行，t2t2t2为 100 万行。

1. 构建阶段 (Build Phase)

1. 扫描小表：全表扫描驱动表t1t1t1。
2. 内存建模：在内存中创建一个哈希表（Hash Table）。
3. 哈希计算：将t1t1t1的每一行根据关联字段bbb的值计算哈希值，然后以bbb为 Key，整行数据为 Value 存入哈希表。

2. 探测阶段 (Probe Phase)

1. 扫描大表：全表扫描被驱动表t2t2t2。
2. 命中检索：对于t2t2t2读入内存的每一行，取其字段bbb的值进行同样的哈希计算。
3. 定位匹配：直接去哈希表中检索对应的 Key。
   • 匹配成功：直接取出t1t1t1的数据进行拼装，返回结果。
   • 匹配失败：继续处理t2t2t2的下一行。

3. 算法开销分析

1. 扫描行数 (IO 开销)

• 磁盘扫描：N+MN + MN+M。
• 优势：每个表都只做一次物理全表扫描，彻底规避了 BNL 算法中被驱动表可能被重复扫描多次的问题 。

2. CPU 计算开销

• 复杂度：由 BNL 的O(N×M)O(N \times M)O(N×M)暴力比对降级为O(N+M)O(N + M)O(N+M)。
• 物理意义：内存中进行的不再是数亿次的字符串或数值比较，而是极快且次数极少的哈希计算与指针定位。

3. 内存开销

• 空间占用：必须在内存中开辟足以存储整个驱动表（Build表）结果集的空间。
• 风险：如果结果集超过内存上限，会导致严重的内存溢出（OOM）或必须借用磁盘临时文件进行分块处理（Graceful Hash Join），这会引入额外的磁盘 IO 损耗 。

4. 具体示例对比

背景：t1t1t1（1000行），t2t2t2（100万行），字段bbb均无索引。

指标	Block Nested-Loop (BNL)	Hash Join (应用层)
物理逻辑	扫描t2t2t2时，每一行都要跟内存里的 1000 行t1比对	扫描t2t2t2时，每一行只算一次哈希，直接定位t1t1t1
内存判断次数	10 亿次(1000×100万1000 \times 100万1000×100万)	100 万次哈希查找
执行耗时	约71.95 秒	< 1 秒

总结：Hash Join 的物理精髓是“空间换时间”。它通过在内存中提前构建高效的索引结构（哈希表），消除了 Join 过程中最昂贵的笛卡尔积式暴力比对。