在Mysql的实现中，Nested-Loop Join有3种实现的算法：

• Simple Nested-Loop Join：SNLJ，简单嵌套循环连接
• Index Nested-Loop Join：INLJ，索引嵌套循环连接
• Block Nested-Loop Join：BNLJ，缓存块嵌套循环连接

在选择Join算法时，会有优先级，理论上会优先判断能否使用INLJ、BNLJ（mysql内部优化后，基本上不会出现Simple Nested-Loop Join）：
Index Nested-LoopJoin > Block Nested-Loop Join > Simple Nested-Loop Join

1、Simple Nested-Loop（笛卡尔积）

1. 简单嵌套循环连接实际上就是简单粗暴的嵌套循环，如果table1有1万条数据，table2有1万条数据，那么数据比较的次数=1万 * 1万 =1亿次，这种查询效率会非常慢。table 1中的每条记录在比较匹配时，都会去扫描一次table 2 。

2、Index Nested-LoopJoin（减少内表的匹配次数）

1）前提条件，内表的关联字段上有索引

2）外表符合条件的记录，通过内表关联字段，通过索引查找进行匹配，减少比较次数：

• 原来的匹配次数 = 外层表行数 * 内层表行数
• 优化后的匹配次数= 外层表的行数 * 内层表索引的高度

3）如果关联字段的索引是二级索引，而且返回的数据中还包含内表其他列数据，则内表还需要进行回表查询，会额外多了一些IO操作。

3、Block Nested-Loop Join（减少内表扫描次数）

1）查询table 1符合条件的记录，一次性缓存到join buffer中，然后拿join buffer里的数据批量与内层表的数据进行匹配，从而减少了内表的扫描次数（内表扫描一次就可以批量匹配Join Buffer里面的外层表数据，即把join buffer当成一条记录看待）。

2）mysql将join优化后，在不使用Index Nested-Loop Join的时候，默认使用Block Nested-Loop Join。

3）什么是Join Buffer？

• Join Buffer会缓存所有参与查询的列而不是只有Join的列。
• 可以通过调整join_buffer_size缓存大小
• join_buffer_size的默认值是256K，join_buffer_size的最大值在MySQL 5.1.22版本前是4G-1，而之后的版本才能在64位操作系统下申请大于4G的Join Buffer空间。
• 使用Block Nested-Loop Join算法需要开启优化器管理配置的optimizer_switch的设置block_nested_loop为on，默认为开启。

4、三种算法比较

假设table 1和table 2的记录如下：

table 1             table 2

1                     1

2                     2

3                     3

                       4

select * from table1 join table2 on table1.id=table2.id