面试官：MySQL 8.0版本引入的 hash join 有什么优势？

MySQL 在 8.0.18 中引入 hash join，这是一个为 join 查询语句设计的高效算法。今天来介绍一下 hash join。

1.简介

首先我们建立两张表，SQL 如下：

再给出一个连接查询 SQL：

那 hash join 的执行过程是怎样的呢？

图片

hash join 的时间复杂度是多少呢？假如 t1 表的记录数是 M，扫描 t1 表的时间复杂度是 o(M)，t2 表的记录数是 N，扫描 t2 表的时间复杂度是 o(N)，hash 表查询的复杂度是 o(1)，这样使用 hash join 查找的总时间复杂度是 o(M + N)。

2.优势

在上面的例子中，t1 表和 t2 表都没有加索引，如果做 join 查询，在 MySQL 8.0 以前，会使用 BNL 算法。

图片

BNL 算法流程如下：

图片

join_buffer 是一个无序数组，t2 表中的每一行都需要跟 t1 表的所有记录做比对。假如 t1 表的数据量是 M，t2 表的数据量是 N，则需要比对的次数是 M * N，也就是说时间复杂度是 o(M*N)。

从时间复杂度可以明显看出 hash join 的优势。

从 MySQL 8.0.20 开始，不再支持 BNL 算法，server 在原先使用 BNL 算法的地方使用 hash join。

3.hash join 优化

MySQL 8.0.18 引入 hash join，主要用于 join 语句中有等值条件并且 join 条件中不能使用索引的场景。比如前面例子中的 join 语句，t1 和 t2 的 c1 字段都没有索引：

MySQL 8.0.18 版本中，支持设置 hash_join=on 或 hash_join=off 供优化器选择，在 MySQL 8.0.19 及更高版本中，这个设置不再生效，server 会默认使用 hash join。

优化一：在 MySQL 8.0.20 以前，如果 join 条件中存在一个非等值匹配的条件，就会走 BNL 算法。MySQL 8.0.20 以后，即使有非等值条件，也会走 hash join。下面 SQL 来自官网：

优化二：即使 join 没有条件，也会走 hash join：

优化三：即使 join 条件中没有等值条件，也会走 hash join。下面 5 个示例来自官网，都会走 hash join。 

1.内连接无等值条件：

2.半连接：

3.反连接：

4.左外连接：

5.右外连接：

4.总结

hash join 算法的出现对 join 语句的性能大幅提升，MySQL 8.0.20 后，对 hash join 的使用又做了进一步的优化，使用更加便捷。