Join算法原理#
一句话答案#
MySQL 的 join 主要有三种算法：被驱动表关联列有索引时用 Index Nested-Loop Join（驱动表每行去索引里查，最优）；无索引时旧版用 Block Nested-Loop Join（驱动表批量放进 join buffer 再扫被驱动表，减少扫描次数）；MySQL 8.0.18 引入 Hash Join，8.0.20 起彻底移除 BNL，原来用 BNL 的场景（含非等值连接、外连接）一律改用 Hash Join。优化关键是”小表驱动大表 + 被驱动表关联列建索引”。
核心要点
| 算法 | 触发条件 | 原理 | 复杂度 |
|---|---|---|---|
| Index Nested-Loop（INLJ） | 被驱动表关联列有索引 | 驱动表逐行，拿连接值去被驱动表走索引查 | 最优，接近 O(N·logM) |
| Block Nested-Loop（BNL） | 被驱动表关联列无索引（8.0.20 前；8.0.20 起已移除） | 驱动表批量读入 join buffer，被驱动表只全表扫一次按 buffer 匹配 | O(N·M)，但减少被驱动表扫描遍数 |
| Hash Join | 无索引连接（8.0.18 起用于等值连接；8.0.20 起也用于非等值/外连接/半连接，全面取代 BNL） | 小表在内存建哈希表（超出 join_buffer_size 时落盘分片），大表逐行探测 | O(N+M)，大表等值连接最快 |
关键概念：
- 驱动表（外表）vs 被驱动表（内表）：优化器通常让结果集小的表做驱动表（“小表驱动大表”），减少外层循环次数
- join buffer：BNL 用，由
join_buffer_size控制；放不下时分多批，被驱动表要多扫几遍（8.0.20 起join_buffer_size改为限制 Hash Join 的内存，超出就写临时文件） - INLJ 性能由被驱动表索引决定：所以 join 优化第一步永远是给关联字段加索引，让 BNL/Hash Join 退化为 INLJ
- 8.0.18/8.0.19 的 Hash Join 要求至少有一个等值连接条件，否则仍走 BNL；8.0.20 起 BNL 被移除，非等值（
<、>、between）、外连接、semi/anti join 也都走 Hash Join
面试回答（2分钟版）
MySQL 的 join 本质是嵌套循环，外层叫驱动表、内层叫被驱动表。具体分三种算法：第一种 Index Nested-Loop Join，前提是被驱动表的关联列有索引，这时驱动表每取一行，就拿连接值去被驱动表走索引精确查，效率最高，是我们追求的形态。第二种 Block Nested-Loop Join，用在被驱动表关联列没索引的老版本上：如果还是逐行去全表扫被驱动表，那扫描次数等于驱动表行数，非常慢；所以 MySQL 改成先把驱动表的数据批量装进 join buffer，被驱动表只全表扫一次，扫的时候和 buffer 里所有行做匹配，这样被驱动表的扫描遍数从”驱动表行数”降到”buffer 批数”。第三种是 MySQL 8.0.18 引入的 Hash Join，它把较小一侧在内存里建哈希表，另一侧逐行探测，复杂度接近线性，比 BNL 快很多；8.0.20 起 BNL 被彻底移除，凡是以前走 BNL 的无索引 join（包括非等值连接和外连接）都改走 Hash Join。
优化上记两条：一是小表驱动大表，让优化器拿结果集小的当外层减少循环；二是给被驱动表的关联列建索引，把 BNL 或 Hash Join 优化成 Index Nested-Loop Join。可以用 explain 看，Extra 里出现
Using join buffer (Block Nested Loop)（8.0.20 前）或Using join buffer (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（只会出现在 8.0.20 之前）；Using join buffer (hash join)是 Hash Join；8.0.18+ 用EXPLAIN FORMAT=TREE能直接看到Inner hash join/Nested loop inner join
易错点：
- ❌ 以为 join 慢只能拆成多次单表查——大多数情况补被驱动表索引即可解决
- ❌ 以为 Hash Join 万能——它仍要全量扫描两侧、内存不够会落盘，有索引时通常不如 INLJ；（另：8.0.18/8.0.19 只支持含等值条件的连接，8.0.20 起非等值连接也走 Hash Join）
- ❌ 盲目调大 join_buffer_size——它是按连接分配的会话级内存，过大浪费内存（8.0.20 起它控制 Hash Join 内存，能减少落盘但治标）；根本解法是给关联列加索引走 INLJ