来源 | 君哥聊技术(ID:gh_1f109b82d301)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)
4.总结
hash join 算法的出现对 join 语句的性能大幅提升,MySQL 8.0.20 后,对 hash join 的使用又做了进一步的优化,使用更加便捷。