面试官：MySQL 8.0版本引入的 hash join 有什么优势？-平芜编程栈

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

1.简介

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

CREATE TABLE t1 (c1 INT, c2 INT); CREATE TABLE t2 (c1 INT, c2 INT);

再给出一个连接查询 SQL：

SELECT * FROM t1 JOIN t2 ON t1.c1=t2.c1;

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

1.确定驱动表（MySQL 会选择结果集较小的表作为驱动表），将结果集加载到内存中；

2.以连接键为 hash key 构建 hash 表，使用链表法解决 hash 冲突。

3.对于非驱动表，依次扫描每一行数据，对 join 字段取 hash 值，然后在 2 构建的 hash 表中查找这个 hash 值；

4.如果找到，则对这个 hash 值所在的链表上每个值进行等值比较，如果比较结果一致，则结合两个表的相关字段生成结果集并输出；

5.如果找不到，则继续扫描下一行。整个过程如下图：

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 算法流程如下：

1.把 t1 表的数据读出放到 join_buffer；

2.扫描 t2 表中的每一行，用 c1 字段值跟 join_buffer 中 t1 表的 c1 字段值做比较；

3.如果 c1 值一样，则作为结果集返回，如果不一样，则继续扫描 t2 表下一行。

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 字段都没有索引：

SELECT * FROM t1 JOIN t2 ON t1.c1=t2.c1;

3.1 配置

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

3.2 连接条件优化

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

mysql> EXPLAIN FORMAT=TREE -> SELECT * FROM t1 -> JOIN t2 ON (t1.c1 = t2.c1) -> JOIN t3 ON (t2.c1 < t3.c1)\G *************************** 1.row *************************** EXPLAIN: -> Filter: (t1.c1 < t3.c1) (cost=1.05rows=1) -> Innerhashjoin (no condition) (cost=1.05rows=1) -> Tablescanon t3 (cost=0.35rows=1) -> Hash -> Innerhashjoin (t2.c1 = t1.c1) (cost=0.70rows=1) -> Tablescanon t2 (cost=0.35rows=1) -> Hash -> Tablescanon t1 (cost=0.35rows=1)

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

mysql> EXPLAIN FORMAT=TREE -> SELECT * -> FROM t1 -> JOIN t2 -> WHERE t1.c2 > 50\G *************************** 1.row *************************** EXPLAIN: -> Innerhashjoin (cost=0.70rows=1) -> Tablescanon t2 (cost=0.35rows=1) -> Hash -> Filter: (t1.c2 > 50) (cost=0.35rows=1) -> Tablescanon t1 (cost=0.35rows=1)

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

1.内连接无等值条件：

mysql> EXPLAIN FORMAT=TREE SELECT * FROM t1 JOIN t2 ON t1.c1 < t2.c1\G *************************** 1.row *************************** EXPLAIN: -> Filter: (t1.c1 < t2.c1) (cost=4.70rows=12) -> Innerhashjoin (no condition) (cost=4.70rows=12) -> Tablescanon t2 (cost=0.08rows=6) -> Hash -> Tablescanon t1 (cost=0.85rows=6)

2.半连接：

mysql> EXPLAIN FORMAT=TREE SELECT * FROM t1 -> WHERE t1.c1 IN (SELECT t2.c2 FROM t2)\G *************************** 1.row *************************** EXPLAIN: -> Hash semijoin (t2.c2 = t1.c1) (cost=0.70rows=1) -> Tablescanon t1 (cost=0.35rows=1) -> Hash -> Tablescanon t2 (cost=0.35rows=1)

3.反连接：

mysql> EXPLAIN FORMAT=TREE SELECT * FROM t2 -> WHERE NOT EXISTS (SELECT * FROM t1 WHERE t1.c1 = t2.c1)\G *************************** 1.row *************************** EXPLAIN: -> Hash antijoin (t1.c1 = t2.c1) (cost=0.70rows=1) -> Tablescanon t2 (cost=0.35rows=1) -> Hash -> Tablescanon t1 (cost=0.35rows=1) 1rowinset, 1warning (0.00 sec) mysql> SHOWWARNINGS\G *************************** 1.row *************************** Level: Note Code: 1276 Message: Fieldorreference't3.t2.c1'ofSELECT#2 was resolved in SELECT #1

4.左外连接：

mysql> EXPLAIN FORMAT=TREE SELECT * FROM t1 LEFTJOIN t2 ON t1.c1 = t2.c1\G *************************** 1.row *************************** EXPLAIN: -> Lefthashjoin (t2.c1 = t1.c1) (cost=0.70rows=1) -> Tablescanon t1 (cost=0.35rows=1) -> Hash -> Tablescanon t2 (cost=0.35rows=1)

5.右外连接：

mysql> EXPLAIN FORMAT=TREE SELECT * FROM t1 RIGHTJOIN t2 ON t1.c1 = t2.c1\G *************************** 1.row *************************** EXPLAIN: -> Lefthashjoin (t1.c1 = t2.c1) (cost=0.70rows=1) -> Tablescanon t2 (cost=0.35rows=1) -> Hash -> Tablescanon t1 (cost=0.35rows=1)