两张表一 join 就变慢，加索引也没救——因为慢的不是"访问哪一行"，是"访问多少行"。EXPLAIN 里那行 type=ALL 后面跟着的 Using join buffer，说明优化器放弃了索引驱动，改走块嵌套循环：被驱动表整段读进来，在内存里跟驱动表逐行比对。
连接算法的选择直接决定复杂度是 O(N log M) 还是 O(N × M)。下面把 MySQL 实际会用的四种算法拆开：各自的前提、EXPLAIN 里长什么样、什么条件下会切换。
1. 四种算法一览
MySQL 8.0 的 join 实现收敛到一张不大的清单：
| 算法 | 全称 | 复杂度量级 | 关键前提 |
|---|---|---|---|
| NLJ | Nested-Loop Join | 被驱动表每次按索引查，O(N × log M) |
被驱动表连接列有索引 |
| BNL | Block Nested-Loop | O(N × M / buffer批量) |
无索引，且有 join_buffer |
| Hash Join | 哈希连接 | O(N + M) |
等值连接 + 无索引（8.0.18 起） |
| BKA | Batched Key Access | 批量回表，O(N × log M) 但 IO 更少 |
有索引 + MRR 开启 |
选择由优化器做，但它受三个外部条件约束：有没有可用索引、join_buffer_size 多大、optimizer_switch 开了什么。理解这三点，就能预测优化器会选哪个。
-- 先看优化器开关的真实值，不同版本默认值不同
SELECT @@optimizer_switch\G
-- 关注这几项：
-- block_nested_loop=on
-- batched_key_access=off ← 默认关闭
-- hash_join=on ← 8.0.18+ 才有
-- mrr=on
2. NLJ：最理想但最挑索引
嵌套循环连接就是两层 for 循环，外层是驱动表，内层是被驱动表。内层每一轮都用索引定位——所以它要求被驱动表的连接列上有可用的索引前缀。
EXPLAIN SELECT o.id, u.name
FROM orders o
JOIN users u ON u.id = o.user_id
WHERE o.created_at >= '2026-01-01';
| id | table | type | key | rows | Extra |
|---|---|---|---|---|---|
| 1 | o | range | idx_created | 1200 | Using index condition |
| 1 | u | eq_ref | PRIMARY | 1 | NULL |
eq_ref 是 NLJ 最健康的样子：被驱动表每轮只回一行，rows=1。判断口诀——驱动表 rows 是估计扫描量，被驱动表 rows=1 说明是精确索引命中。
rows 相乘就是这次 join 的大致工作量。上面是 1200 × 1。如果被驱动表显示 rows=800 且 type=ALL，那就是 1200 × 800 ≈ 96 万次比对，必然走 BNL。
3. BNL：没有索引时的兜底
当被驱动表在连接列上没有索引，优化器会把被驱动表的一段数据读进 join_buffer，然后拿驱动表的每一行去内存里比对。EXPLAIN 里会明确写出来：
EXPLAIN SELECT o.id, t.tag_name
FROM orders o
JOIN order_tags t ON t.order_id = o.id;
+----+-------+------+------+------+--------------------------------------------------+
| id | table | type | key | rows | Extra |
+----+-------+------+------+------+--------------------------------------------------+
| 1 | o | ALL | NULL | 5000 | NULL |
| 1 | t | ALL | NULL | 8000 | Using where; Using join buffer (hash join) |
+----+-------+------+------+------+--------------------------------------------------+
注意 8.0.18 之后同样是无索引场景，Extra 可能已经写成 (hash join) 而不是 (block nested loop)——版本差异会直接改变你读到的结论，必须按实际版本核对。
join_buffer_size 决定一次能装多少行。装不下就分块：被驱动表扫多遍，每遍装一块。
join_buffer_size |
被驱动表扫描次数 | 代价 |
|---|---|---|
| 小于单块 | 多趟扫描 | 磁盘 IO 放大 |
| 覆盖全表 | 一趟 | 内存占用高 |
| 过大（数百 MB） | 一趟但按连接分 | 并发高时内存爆 |
-- 会话级临时调大，用于验证"是否 buffer 太小导致多趟扫描"
SET SESSION join_buffer_size = 64 * 1024 * 1024;
这里的陷阱是：join_buffer_size 是每个连接、每个 join 分配的，不是全局共享。100 个并发连接各开 64MB，就是 6.4GB。
4. Hash Join：8.0.18 之后的主力
等值连接 + 被驱动表无索引，优化器会改走哈希连接：把小表建成哈希表，大表扫一遍探查。复杂度从 N × M 降到 N + M。
触发条件的完整清单（按 8.0.18+ 的规则）：
| 条件 | 要求 | 不满足时 |
|---|---|---|
| 连接类型 | 必须是等值（=） |
退回 BNL |
| 索引 | 被驱动表无可用索引 | 有索引时仍优先 NLJ |
| 内存 | 能在 join_buffer_size 内建表 |
分批，可能落盘 |
| 类型 | 两侧比较类型可哈希 | 类型不一致可能失效 |
-- 强制验证 hash join 的收益：临时关掉再对比
SET SESSION optimizer_switch = 'block_nested_loop=off';
-- 8.0.20+ 可以用 hint 逐语句指定
EXPLAIN /*+ HASH_JOIN(o, t) */ SELECT ... ;
一个反直觉的点：给被驱动表加上索引，可能让查询变快或变慢。加了索引优化器走 NLJ，如果驱动表行数很大而每次回表都是随机 IO，NLJ 反而比一次性哈希建表更慢。所以"加索引"不是无条件正确，要看驱动表的行数级。
5. BKA 与 MRR：批量回表
BKA（Batched Key Access）本质是 NLJ 的 IO 优化：先从驱动表攒一批 key，排序后一次性提交给存储引擎，让随机回表变成近似顺序读。它依赖 MRR（Multi-Range Read）。
SET SESSION optimizer_switch = 'mrr=on,mrr_cost_based=off,batched_key_access=on';
| 开关 | 默认 | 作用 |
|---|---|---|
mrr |
on | 允许范围扫描批量回表 |
mrr_cost_based |
on | 由代价决定是否用 MRR；关掉则强制 |
batched_key_access |
off | BKA 的总开关，默认关 |
batched_key_access 默认关闭不是遗漏：BKA 的代价模型在某些数据分布下会高估收益，导致选了更差的路。开启前必须在真实数据量下对比，不能只看单条 SQL 的 EXPLAIN。
BKA 生效时 EXPLAIN 的 Extra 会出现 Using join buffer (Batched Key Access)，且 rows 列会显示批量倍数。
6. 驱动表的选择：谁当外层
优化器选驱动表看的是"过滤后行数"，不是表的总行数。但它的估计依赖统计信息，统计信息不准就会选错。
-- 看统计信息新鲜度
SELECT table_name, last_update, n_rows
FROM mysql.innodb_table_stats
WHERE table_name IN ('orders','order_tags');
| 判断依据 | 含义 | 选错的表现 |
|---|---|---|
rows 估计 |
过滤后预期行数 | 小表被当外层才正常 |
filtered |
剩余比例 | 联合估计误差放大 |
| 直方图 | 列值分布 | 无直方图时等值条件估计极粗 |
-- 给倾斜列建直方图，能显著改善 join 顺序选择
ANALYZE TABLE orders UPDATE HISTOGRAM ON status, user_id WITH 64 BUCKETS;
STRAIGHT_JOIN 是强制指定驱动顺序的逃生口，但它只应在确认优化器选错时使用——一旦数据分布变化，写死的顺序可能变成新的瓶颈。
7. 排错：五种 join 变慢的真实原因
| 现象 | 真实原因 | 处理 |
|---|---|---|
Extra 显示 Using join buffer 且查询慢 |
被驱动表连接列无索引 | 建索引；索引建不上再评估 hash join |
rows 乘积巨大但实际返回很少 |
统计信息过期，估计偏差 | ANALYZE TABLE，必要时加直方图 |
| 内存持续上涨伴随 join | join_buffer_size 按连接 × 按 join 分配 |
降单值，或拆查询 |
| 加了索引反而更慢 | NLJ 随机回表次数超过哈希建表成本 | 对比两种计划的真实耗时，别只看 type |
hash join 用了但没提速 |
建表侧超过 join_buffer_size，分批落盘 |
调大 buffer 或先收窄子查询 |
还有一类不属于算法的慢：ON 条件里写了函数（ON DATE(t.created)=o.date），索引直接失效，任何算法都救不回来。
8. 边界：什么时候该在应用层拆
| 场景 | 建议 | 理由 |
|---|---|---|
| 两张超大表等值 join，结果集很小 | 先各自过滤再 join | 减少参与哈希的行数 |
| 需要跨库 / 跨实例 join | 应用层分两次查再内存拼装 | MySQL 不支持跨实例 join |
| join 后要做复杂聚合 | 先落临时表再聚合 | 避免优化器在 join 与聚合间反复权衡 |
| 只取被驱动表少量列 | 覆盖索引或子查询预聚合 | 减少回表 |
| 分页 + join | 先对驱动表分页再 join | 否则 LIMIT 在 join 之后才生效 |
最后一条最常被忽略：ORDER BY ... LIMIT 20 配 join 时，如果排序键在被驱动表上，MySQL 必须把 join 结果全物化再排序。先分页取驱动表的 20 个 id，再按 id 批量取明细，通常快一个量级。
9. 自测
EXPLAIN中被驱动表type=eq_ref且rows=1，说明走的是哪种算法？Using join buffer (block nested loop)出现的直接前提是什么？- 8.0.18 之后同样无索引的等值连接，
Extra可能变成什么？ join_buffer_size是全局共享还是按连接分配？batched_key_access为什么默认关闭？- 给被驱动表加索引一定更快吗？什么情况下不是？