MySQL之Join的原理

一、概念

先了解下笛卡尔积，inner join、left join、right join之间的区别以及驱动表的概念。

笛卡尔积：两个集合相乘的结果。在数学的集合论中表示为X × Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。假设集合A={a, b}，集合B={0, 1, 2}，则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。

INNER JOIN：查询两个表之间的交集。MySQL 中 JOIN、INNER JOIN语法完全等价，可互相替换；用集合解析下：假设t1={3，4，5}，t2={4，5，6，7，8}；那么INNER JOIN 取值时，双层遍历查询，然后取交集j={4，5}。

什么是驱动表：最外层的for循环的表，把集合对应成MySQL表，t1是小表，t2是大表。在INNER JOIN过程中会遍历两个表，优化器会取小表作为驱动表，大表为被驱动表，然后进行双层遍历取值。伪代码表示如下：

for each row r in t1(驱动表):
    for each row s in t2(被驱动表) where s.key = r.val:
        output (r, s)

LEFT JOIN：取左表(驱动表)的全部数据，右表(被驱动表)如果有对应数据就显示，没有就为NULL。

RIGHT JOIN：取右表(驱动表)的全部数据，左表(被驱动表)如果有对应数据就显示，没有就显示为NULL。

二、MySQL Join 四种算法

三、执行前优化器怎么决定用哪种 Join？

MySQL 的查询优化器在执行 Join 前会做以下决策：

1. 选驱动表：优化器会估算每张表的行数、过滤后的结果集大小，选择结果集更小的那张表作为驱动表（outer table）。被驱动表是 inner table。

2. 选算法：

被驱动表的 Join 列有索引 → 用 Index Nested-Loop Join (NLJ)
没有索引，MySQL 5.7 及以下 → 用 Block Nested-Loop Join (BNL)
没有索引，MySQL 8.0+ → 优先用 Hash Join

四、四种算法讲解

简单嵌套循环 / Index NLJ：

总比较次数 = M × N。驱动表 1000 行、被驱动表 100 万行，就要做 10 亿次比较。这基本是没有优化，MYSQL不会选择它。真实的无索引场景会用 BNL，有索引会用 INLJ。

伪代码：

for each row r in 驱动表（共 M 行）:
    for each row s in 被驱动表（共 N 行）:
        if r.join_col == s.join_col:
            output(r, s)

Index Nested-Loop Join（INLJ）：

这是实际生产中最常用、性能最好的 Join 算法。它的核心改进是：当被驱动表的 Join 列存在索引时，内层循环不再全表扫，而是走 B+ 树点查，把内层的 O(N) 降为 O(log N)。

伪代码：

for each row r in 驱动表（共 M 行）:
    走被驱动表 Join 列上的索引，定位到 r.join_col 对应的行
    输出匹配行

内层每次查询代价从扫 N 行变成走 log N 层 B+ 树。这也是”被驱动表 Join 列必须加索引“的原因。

但是：若索引是非聚簇索引（二级索引），查到叶节点拿到的是主键值，还需要再回表（回聚簇索引）取完整数据行，这就是”回表”操作。若 SELECT 的列恰好都在二级索引里，则可以”覆盖索引”，免去回表。

Block Nested-Loop Join（BNL）：

当被驱动表没有索引时，MySQL 引入 join_buffer（默认 256KB，可调）来批量处理。BNL 的改进思路是：把驱动表的数据批量装入内存（Join Buffer），然后一次性和被驱动表的每一行做比较，把被驱动表的扫描次数从 M 次减少为 ceil(M / buffer_size) 次。

BNL 的本质优化是减少”被驱动表全表扫的轮数”，而不是减少”每轮扫的行数”。若驱动表 1000 行、buffer 一次能装 100 行，被驱动表就只需要扫 10 次而不是 1000 次。注意 join_buffer_size 是每个 join 操作独占的，多表 join 时每个 join 都有一个独立的 buffer，不要设得过大。

伪代码：

while 驱动表还有行:
    将驱动表的尽可能多的行装入 join_buffer（按 join_buffer_size 限制）
    全扫被驱动表，把每行和 join_buffer 里所有行做比较
    输出匹配行，清空 join_buffer，继续装下一批

Hash Join（MySQL 8.0.18+）：

Hash Join 彻底摆脱了”嵌套循环”的思路，分为两个阶段：

Build 阶段：扫描小表（驱动表），对每行的 Join 列计算哈希值，构建一张内存哈希表。
Probe 阶段：扫描大表（被驱动表），对每行的 Join 列同样计算哈希值，到哈希表里查找匹配行。

每张表只扫一次，总代价是 O(M + N)，远优于 BNL 的 O(M × N)。

当哈希表放不进 join_buffer_size 限制的内存时，MySQL 会自动将数据 spill 到磁盘做 Grace Hash Join，代价升高但仍能保证正确性。Hash Join 只能用于等值条件（ON a.id = b.id），范围条件仍须回退到 BNL。

四种算法对比：

五、实战调优

用EXPLAIN 看Join 算法：

EXPLAIN SELECT * FROM orders o JOIN users u ON o.user_id = u.id;

Extra 列的值	说明
`Using index`	Index NLJ，最优
`Using join buffer (Block Nested Loop)`	BNL，无索引 5.7 场景
`Using join buffer (Batched Key Access)`	BKA，批量 key 访问索引
`Using hash join`	Hash Join，8.0+ 无索引场景