join 语句用于实现多表查询。

Index Nested-Loop Join

select * from a join b on a.id=b.id。对于两张表 a 和 b，Mysql 优化器会选择其中一张表执行全表扫描，称为驱动表。对于驱动表每一数据行，在被驱动表查询数据，将结果组合返回数据集。
假设驱动表行数是M，则时间复杂度为 M。
对于每一行，在 N 行被驱动表的非聚簇索引和局促索引各搜索一次。则时间复杂度为 M * 2 * log2(N)。
两者相加 M + M * 2 * log2(N)。可以看出应选择小表执行全表扫描，即作驱动表。这种使用索引的 join 语句称为 Index Nested-Loop Join(NLJ) ，性能不错。

Block Nested-Loop Join

如果被驱动表用不上索引，那么时间复杂度就是 M * N。mysql 对于这种 join 语句也有优化，称为 Block Nested-Loop Join。具体操作是：两张表都是全表扫描，用一块内存区域 join_buffer 存储其中一张表(驱动表)所有行的所选字段。扫描另一张表(被驱动表)，与 Join_buffer 数据对比，满足则存入结果集。在内存执行 M * N 次操作比在磁盘执行 M * N 次操作快。

如果 join_buffer 不够大，放不下驱动表所有数据。则分段存放(这就是 Block Nested-Loop Join 中 Block 的含义)。多次将驱动表的不同数据存入 join_buffer，再全表扫描被驱动表。为了降低 join_buffer 替换次数，选择结果集更小的表作为驱动表。比如：表 a 有 30 行，查询 3 个 int 字段，表b 有 10 行，查询 10 个 int 字段。此时就应该选择 a 表。
优化方案可以是：增加 join_buffer 空间。

Batched Key Access

Multi-Range Read

之前我们提及回表：在非聚簇索引查到主键 id，再到聚簇索引查询数据行。如果在非聚簇索引查询大量 id，Mysql 提供 Multi-Range Read 机制优化回表。它将非聚簇索引查询到到的 id 集合在内存区域 read_rnd_buffer 排序并且按顺序在聚簇索引查询数据行。这样可以将随机访问变为顺序访问，提升读性能。

Index Nested-Loop Join 的优化

Index Nested-Loop Join 的被驱动表也有回表，Batched Key Access = Index Nested-Loop Join + Multi-Range Read。
具体来说：用 join_buffer 批量缓存驱动表的数据，在被驱动表回表查询时利用 MRR 提升读性能。

Block Nested-Loop Join 的优化

如果某些 join 查询使用频率很低，或者 where 条件过滤后表的数据行非常少，那么不适合建立索引。

但是不建立索引，时间复杂度 M * N。此时可以用临时表，在临时表为字段建立索引，将 Block Nested-Loop Join 变为 Index Nested-Loop Join