mysql 8 新特性三 Hash Join联接查询算法之Hash Join (五)

mysql8以前 的 join 算法只有 nested loop 这一种，在 MySQL8 中推出了一种新的算法 hash join，比 nested loop 更加高效。mysql8中的部分NLJ算法已经取消，hash join 是它的的替代方案。像属于NLJ的BNLJ、SNLJ都会被Hash join替代！不过基于索引的INLJ算法还是存在的，所以实际使用中可以对比下INLJ和Hash Join的查询性能然后做出选择。

个人觉得mysql8这个hash join也只能算是一个锦上添花的功能，顶多是代替了没有加索引时默认走的BNLJ算法，提高了join的性能下限。说白了就是给不懂加索引的mysql新用户提高下join性能。其实也不绝对，不过我有做 INLJ和Hash Join 对比实验，Hash Join 很有可能比需要在内部表建立索引的INLJ算法性能要好！毕竟当INLJ需要回表查的时候性能会大幅度下降，这时候Hash Join绝对值得一试的，当然具体两者之间的选择还请自己实际测试下。

创建user和book表

可以看看下列语句的执行计划，Extra 出现了 Using join buffer (hash join) 说明该语句使用到了hash join。这里还使用了 IGNORE index(index_user_id)禁用索引，不然使用的是INLJ。

那么，使用Hash Join会分为下面2个阶段：

1、build 构建阶段：从参与join的2个表中选一个，选择占空间小的那个表，不是行数少的，这里假设选择了 user 表。对 user表中每行的 join 字段值进行 hash(a.id ) 计算后放入内存中 hash table 的相应位置。所有行都存放到 hash table 之后，构建阶段完成。

溢出到磁盘在构建阶段过程中，如果内存满了，会把表中剩余数据写到磁盘上。不会只写入一个文件，会分成多个块文件。

2、probe 探测阶段：对 book 表中每行中的 join 字段的值进行 hash 计算：hash(b.user_id) 拿着计算结果到内存 hash table 中进行查找匹配，找到一行就发给 client。这样就完成了整个 join *** 作，每个表只扫描一次就可以了，扫描匹配时间也是恒定的，非常高效。

散列连接的内存使用可以使用join_buffer_size系统变量来控制；散列连接使用的内存不能超过这个数量。当散列连接所需的内存超过可用的数量时，MySQL通过使用磁盘上的文件来处理这个问题(溢出到磁盘)。

如果发生这种情况，您应该知道，如果散列连接无法容纳在内存中，并且它创建的文件超过了为open_files_limit设置的数量，则连接可能不会成功。

为避免此类问题，请执行以下任一更改:

1、增加join_buffer_size，以便哈希连接不会溢出到磁盘。

在MySQL 8.0.19及更高版本中， 设置 optimizer_switch 变量值 hash_join=on or hash_join=off 的方式已经失效了

2、增加open_files_limit。若数据量实在太大内存无法申请更大的join_buffer，就只能溢出到磁盘上了。我们可以增加open_files_limit，防止创建的文件超过了为open_files_limit设置的数量而join失败。

必须使用format=tree（8.0.16的新特性）才能查看hash join的执行计划：

创建几张测试表

从MySQL 8.0.18开始，MySQL对每个连接都有一个等连接条件的任何查询都使用散列连接，并且没有可应用于任何连接条件的索引，例如:

在MySQL 8.0.20之前，如果任何一对连接的表没有至少一个等连接条件，就不能使用Hash Join，并且使用了较慢的BNLJ。而 在MySQL 8.0.20和更高版本中，hash join可以用于未包含等值连接条件的查询

甚至是笛卡尔积的join

Semijoin也行

还有 antijoin

1. Nested-Loop Join 翻译过来就是嵌套循环连接，简称 NLJ。

这种是 MySQL 里最简单、最容易理解的表关联算法。

比如，拿语句 select * from p1 join p2 using(r1) 来说，

先从表 p1 里拿出来一条记录 ROW1，完了再用 ROW1 遍历表 p2 里的每一条记录，并且字段 r1 来做匹配是否相同，以便输出；再次循环刚才的过程，直到两表的记录数对比完成为止。

2. Block Nested-Loop Join ，块嵌套循环，简称 BNLJ

那 BNLJ 比 NLJ 来说，中间多了一块 BUFFER 来缓存外表的对应记录从而减少了外表的循环次数，也就减少了内表的匹配次数。还是那上面的例子来说，假设 join_buffer_size 刚好能容纳外表的对应 JOIN KEY 记录，那对表 p2 匹配次数就由 1000 次减少到 1 次，性能直接提升了 1000 倍。

3. 最近 MySQL 8.0.18 发布，终于推出了新的 JOIN 算法 — HASH JOIN。

MySQL 的 HASH JOIN 也是用了 JOIN BUFFER 来做缓存，但是和 BNLJ 不同的是，它在 JOIN BUFFER 中以外表为基础建立一张哈希表，内表通过哈希算法来跟哈希表进行匹配，hash join 也就是进一步减少内表的匹配次数。当然官方并没有说明详细的算法描述，以上仅代表个人臆想。那还是针对以上的 SQL，我们来看下执行计划。

---