MySQL优化器特性（四）表关联之BNL（Block Nested Loop）和Hash Join
什么是BNL
MySQL表关联时，如果关联条件上没有合适的索引，则join时，对于驱动表的每一条记录，都需要全表扫描被驱动表。如果驱动表有多条数据，则需要多次全表扫描被驱动表，查询性能很差。对于这种情况，MySQL会采用块嵌套循环（Block Nested Loop, BNL)，将驱动表的数据先缓存在join buffer中，一次读取被驱动表的数据，可以和驱动表的多条记录进行join，这样就可以减少全表扫描的次数。
MySQL 8.0引入了Hash join，对于BNL Join，会基于驱动表的数据在join buffer中构建一个Hashmap。如果驱动表的数据可以一次性全部加载到join buffer中，则只需要对被驱动表进行一次全表扫描，就能完成Join。如果驱动表的数据无法一次性全部加载到join buffer中，MySQL会根据关联条件对驱动表和被驱动表进行分片，一次join一对分片，这种情况下，一般只需要扫描两次数据，就能完成join操作。
一个例子
表结构
mysql> show create table tb\G *************************** 1. row *************************** Table: tb Create Table: CREATE TABLE `tb` ( `a` int DEFAULT NULL, `b` int DEFAULT NULL, `c` int DEFAULT NULL, `id` int NOT NULL AUTO_INCREMENT, PRIMARY KEY (`id`), KEY `idx_c` (`c`), KEY `idx_ab` (`a`,`b`) ) ENGINE=InnoDB AUTO_INCREMENT=321 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci 1 row in set (0.01 sec) mysql> select a,b,c, count(*) from tb group by a,b,c; +------+------+------+----------+ | a | b | c | count(*) | +------+------+------+----------+ | 1 | 1 | 1 | 32 | | 2 | 2 | 2 | 32 | | 3 | 3 | 3 | 32 | | 4 | 4 | 4 | 32 | | 5 | 5 | 5 | 32 | | 6 | 6 | 6 | 32 | | 7 | 7 | 7 | 32 | | 8 | 8 | 8 | 32 | | 9 | 9 | 9 | 32 | | 10 | 10 | 10 | 32 | +------+------+------+----------+ 10 rows in set (0.00 sec)
执行计划
执行计划的Extra中显示“Using join buffer (hash join)”，说明进行了Hash join。
mysql> explain select t1.*, t2.a,t2.b,t2.c from tb t1, tb t2 where t1.b = t2.b \G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t2 partitions: NULL type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 320 filtered: 100.00 Extra: NULL *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t1 partitions: NULL type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 320 filtered: 10.00 Extra: Using where; Using join buffer (hash join) 2 rows in set, 1 warning (0.00 sec)
从树形格式显示的执行计划能更清楚地看到join的执行过程：
使用t2表的数据构建hashmap
扫描t1表的数据
使用t1.b = t2.b为条件，进行hash join
mysql> explain format=tree select t1.*, t2.a,t2.b,t2.c from tb t1, tb t2 where t1.b = t2.b ; +----------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ | EXPLAIN | +----------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ | -> Inner hash join (t1.b = t2.b) (cost=10272.50 rows=10240) -> Table scan on t1 (cost=0.01 rows=320) -> Hash -> Table scan on t2 (cost=32.25 rows=320)
Hash join步骤
Hash Join的大致流程如下：
1、读取build table的记录，将记录加入到HashMap
1.1、如果join buffer空间不足，则需要初始化chunk文件，将build表的记录写入到chunk文件。
build表的chunk文件和probe表的chunk文件成对，按join key取hash，存入到对应的chunk文件。
2、读取probe表的记录，按join key查找hashmap。
2.1、如果是磁盘hash join，则需要将probe表的记录写入到chunk文件
3、依次读取HashMap中匹配的记录，处理其他额外条件，将记录返回给客户端。
4、如果是磁盘Hash join，需要依次加载chunk file，处理join。
4.1 如果分片后的数据依然无法一次性全部加载到join buffer中，则会开启probe row saveing，这种情况下，执行hash join的时候，会将probe记录存到临时文件。需要多次读取数据进行hash join。
如何确定是否需要进行磁盘Hash Join，以及将表分成多少个分片
1、如果无法一次性将build table的所有数据加载到join buffer中，则需要开启磁盘Hash Join。
2、根据当前join buffer已经加载的记录数，和优化器预估的build表的记录数，来评估需要将表分成多少个分片。
3、分片数会向上取整到最近的2的n次方。
Hash map存储格式
Hash table中，key相同的记录，会组成一个单向链表。
多趟Join
如果分片后的数据依然无法一次性全部加载到join buffer中，则需要进行多趟Join
1、将分片中的部分数据加载到hashmap中
2、读取probe分片的记录。执行join。
3、同时将probe记录写入到另外一个单独的文件（probe saving file）
4、输出join数据
5、清空hashmap。将build chunk的下一批数据加载进hashmap。
6、从probe saving file读取记录，进行join。
为什么需要将数据写入到单独的probe saving file，而不是直接使用probe chunk呢？
因为会有semi join、anti join等情况，如果已经和前面的记录匹配上了，就不需要匹配后续的记录了。
优化器参数
MySQL 8默认开启hash join。优化器选项(optimizer_switch)中有两个选项和hash join相关：
1、hash_join
2、block_nested_loop
经过测试，hash_join选项应该已经废弃，不影响执行计划。我们可以通过block_nested_loop选项来控制是否启用hash join。
