前言
在关系型数据库的世界里，JOIN（连接）是我们每天都会打交道的老朋友。无论是简单的报表查询，还是复杂的业务逻辑处理，都离不开它。但你是否遇到过这样的场景：两张表 JOIN 飞快，三张表变慢，五张表直接让数据库 CPU 飙升？
在深入算法之前，我们必须明确一个核心概念：JOIN 的本质是基于两张表的笛卡尔积进行数据过滤。
假设有表 A（100 行）和表 B（1000 行）。如果在没有任何条件的情况下把它们连接起来，数据库会生成一个包含 100 * 1000 = 100,000 行的临时大表，这就是笛卡尔积。显然，这种无脑组合绝大多数都是无意义的数据。
因此，JOIN 的过程实际上就是：
- 确定驱动表（Driving Table）和被驱动表（Driven Table）。
- 从驱动表中取出一条记录。
- 根据连接条件（
ON子句）到被驱动表中寻找匹配的记录。 - 将匹配的记录合并后返回或放入结果集中。
- 重复上述步骤，直到驱动表遍历完毕。
为了让这个过程更高效，MySQL 的优化器和执行引擎在背后付出了巨大的努力，演进出了多种 JOIN 算法。
JOIN 算法
MySQL 处理 JOIN 的主要算法经历了从简单的嵌套循环到利用内存和哈希表的演进。理解它们，是进行 SQL 优化的前提。
Simple Nested-Loop Join (SNLJ) - 简单嵌套循环连接
这是最原始、最暴力的连表方式。它的逻辑就和我们在代码里写两个嵌套的 for 循环一模一样。
执行逻辑： 从驱动表 A 中取出每一行，然后去被驱动表 B 中进行全表扫描匹配。
性能痛点： 如果驱动表有 1,000 行，被驱动表有 10,000 行，那么被驱动表就要被全表扫描 1,000 次！在磁盘 I/O 层面，这是极其恐怖的开销。因此，MySQL 实际上绝对不会在生产环境中使用如此简陋的算法。
Index Nested-Loop Join (INLJ) - 索引嵌套循环连接
为了拯救 SNLJ 糟糕的性能，索引派上了用场。这是日常开发中最常见，也是我们最期望数据库走的一种 JOIN 算法。
执行逻辑： 依然是从驱动表 A 取出一条数据。但这次去被驱动表 B 寻找匹配行时，直接利用表 B 的索引进行查找，而不再是全表扫描。
性能飞跃： 通过 B+ 树索引，原本被驱动表 O(N) 的扫描复杂度瞬间降到了树的高度（通常为 O(logN)）。 优化核心： 永远保证被驱动表的 JOIN 字段上有合适的索引！
Block Nested-Loop Join (BNLJ) - 块嵌套循环连接 (Buffer)
如果被驱动表的连接字段没有索引怎么办？MySQL 也不傻，它不会退化去使用 SNLJ，而是引入了 Join Buffer（连接缓冲区）来优化，这就是 BNLJ。
执行逻辑： MySQL 会在内存中开辟一块名为
Join Buffer的空间。它会将驱动表 A 的数据批量读取到 Join Buffer 中。然后扫描一次被驱动表 B，将 B 中的每一行与 Join Buffer 中的所有 A 表记录进行批量匹配。
为什么这样能变快？ 对比 SNLJ 中驱动表每读取一行，被驱动表就要被扫描一次；BNLJ 是驱动表的一批数据读入内存后，被驱动表扫描一次，就可以和内存中的这一批数据全部对比完毕。这极大地减少了被驱动表的磁盘扫描次数。（注意：Join Buffer 大小由参数 join_buffer_size 控制，默认 256KB）。
