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，我们来看下执行计划。

MySQLbtree索引hash索引区别

ash 索引结构特殊性其检索效率非高索引检索定位像B-Tree 索引需要根节点枝节点才能访问页节点IO访问所 Hash 索引查询效率要远高于 B-Tree 索引

能疑问既 Hash 索引效率要比 B-Tree 高家都用 Hash 索引要使用 B-Tree 索引呢任何事物都两面性Hash 索引虽 Hash 索引效率高 Hash 索引本身由于其特殊性带限制弊端主要些

（1）Hash 索引仅仅能满足"=","IN""<=>"查询能使用范围查询

由于 Hash 索引比较进行 Hash 运算 Hash 值所能用于等值滤能用于基于范围滤经相应 Hash 算处理 Hash 值关系并能保证Hash运算前完全

（2）Hash 索引用避免数据排序 *** 作

由于 Hash 索引存放经 Hash 计算 Hash 值且Hash值关系并定 Hash 运算前键值完全所数据库利用索引数据避免任何排序运算；

（3）Hash 索引能利用部索引键查询

于组合索引Hash 索引计算 Hash 值候组合索引键合并再起计算 Hash 值单独计算 Hash 值所通组合索引前面或几索引键进行查询候Hash 索引利用

（4）Hash 索引任何候都能避免表扫描

前面已经知道Hash 索引索引键通 Hash 运算 Hash运算结 Hash 值所应行指针信息存放于 Hash 表由于同索引键存相同 Hash 值所即使取满足某 Hash 键值数据记录条数 Hash 索引直接完查询要通访问表实际数据进行相应比较并相应结

（5）Hash 索引遇量Hash值相等情况性能并定比B-Tree索引高

于选择性比较低索引键创建 Hash 索引存量记录指针信息存于同 Hash 值相关联要定位某条记录非麻烦浪费表数据访问造整体性能低

---