Join算法原理#
一句话答案#
MySQL 的 join 主要有三种算法：被驱动表关联列有索引时用 Index Nested-Loop Join（驱动表每行去索引里查，最优）；无索引时旧版用 Block Nested-Loop Join（驱动表批量放进 join buffer 再扫被驱动表，减少扫描次数）；MySQL 8.0.18+ 引入 Hash Join 替代无索引场景的 BNL，对大表等值连接更快。优化关键是”小表驱动大表 + 被驱动表关联列建索引”。
核心要点
| 算法 | 触发条件 | 原理 | 复杂度 |
|---|---|---|---|
| Index Nested-Loop（INLJ） | 被驱动表关联列有索引 | 驱动表逐行，拿连接值去被驱动表走索引查 | 最优，接近 O(N·logM) |
| Block Nested-Loop（BNL） | 被驱动表关联列无索引（8.0.18 前） | 驱动表批量读入 join buffer，被驱动表只全表扫一次按 buffer 匹配 | O(N·M)，但减少被驱动表扫描遍数 |
| Hash Join | 无索引等值连接（8.0.18+ 默认） | 小表在内存建哈希表，大表逐行探测 | O(N+M)，大表等值连接最快 |
关键概念：
- 驱动表（外表）vs 被驱动表（内表）：优化器通常让结果集小的表做驱动表（“小表驱动大表”），减少外层循环次数
- join buffer：BNL 用，由
join_buffer_size控制；放不下时分多批，被驱动表要多扫几遍 - INLJ 性能由被驱动表索引决定：所以 join 优化第一步永远是给关联字段加索引，让 BNL/Hash Join 退化为 INLJ
- Hash Join 仅支持等值连接（
=），非等值（<、>、between）仍走 BNL
面试回答（2分钟版）
MySQL 的 join 本质是嵌套循环，外层叫驱动表、内层叫被驱动表。具体分三种算法：第一种 Index Nested-Loop Join，前提是被驱动表的关联列有索引，这时驱动表每取一行，就拿连接值去被驱动表走索引精确查，效率最高，是我们追求的形态。第二种 Block Nested-Loop Join，用在被驱动表关联列没索引的老版本上：如果还是逐行去全表扫被驱动表，那扫描次数等于驱动表行数，非常慢；所以 MySQL 改成先把驱动表的数据批量装进 join buffer，被驱动表只全表扫一次，扫的时候和 buffer 里所有行做匹配，这样被驱动表的扫描遍数从”驱动表行数”降到”buffer 批数”。第三种是 MySQL 8.0.18 之后引入的 Hash Join，针对无索引的等值连接，它把较小一侧在内存里建哈希表，另一侧逐行探测，复杂度接近线性，比 BNL 快很多，现在是无索引等值 join 的默认算法。
优化上记两条：一是小表驱动大表，让优化器拿结果集小的当外层减少循环；二是给被驱动表的关联列建索引，把 BNL 或 Hash Join 优化成 Index Nested-Loop Join。可以用 explain 看，Extra 里出现
Using join buffer (Block Nested Loop)或(hash join)就说明没走索引，需要补索引。
追问与易错
追问方向：
- “什么叫小表驱动大表？谁是小表？”→ 不是看总行数，而是看经过 where 过滤后参与 join 的结果集大小；优化器会基于成本自动选驱动表，但写 SQL 时让过滤性强的表先过滤有助于它选对
- “BNL 为什么比朴素嵌套循环快？”→ 朴素做法被驱动表要被全表扫”驱动表行数”遍；BNL 把驱动表攒一批放 join buffer，被驱动表只扫”批数”遍，buffer 越大批数越少，扫得越少
- “Hash Join 和 INLJ 哪个快？”→ 被驱动表有合适索引时 INLJ 通常更快（直接索引定位）；无索引的大表等值连接 Hash Join 完胜 BNL。所以有索引优先 INLJ，没索引才靠 Hash Join 兜底
- “怎么判断走了哪种算法？”→ 看 explain 的 Extra：空着且被驱动表 type 为 ref/eq_ref 是 INLJ；
Using join buffer (Block Nested Loop)是 BNL；Using join buffer (hash join)是 Hash Join
易错点：
- ❌ 以为 join 慢只能拆成多次单表查——大多数情况补被驱动表索引即可解决
- ❌ 以为 Hash Join 万能——它只支持等值连接，范围/非等值连接仍走 BNL
- ❌ 盲目调大 join_buffer_size——只对 BNL 有效，且过大浪费内存；根本解法是加索引消灭 BNL