MySQL Hash Join实测

MySQL 在千呼万唤之后，终于在 8.0.18 版本引入了 Hash Joins^[1] 的特性，在某些场景下能大大加快 join 查询的速度。

在介绍 hash join 之前，让我们先了解一下 MySQL 在一般情况下使用的算法：Nested Loop Join

Nested Loop Join

Nested Loop Join(以下简写 NLJ)是常规情况下使用的 join 算法，无论列上个有没有索引。它的工作原理是这样的：外层循环逐行读取主表，将读到的行传递给内层循环进行 join。我们用伪码演示一下这个过程

假设有表 t1, t2, t3，执行计划里的 join type 如下

Table   Join Type
t1      range
t2      ref
t3      ALL

复制

NLJ 算法的过程可以这么表示

for each row in t1 matching range {
  for each row in t2 matching reference key {
    for each row in t3 {
      if row satisfies join conditions, send to client
    }
  }
}

复制

显而易见的是，对于 t3 上的每一行，都要重新执行 t1 join t2 的外层循环

Block Nested Loop Join

简单 NLJ 算法的不足，MySQL 做了一些局部优化。以上面的例子为例，BNL 会执行部分 t1 join t2，将中间结果缓存到 join buffer 里，把这块 join buffer 传递给 t3 循环去做 join。这样在遍历 t3 的时候就会少做很多 join 操作，节省 cpu 资源，过程可以用如下伪码表示

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions, send to client
        }
      }
      empty join buffer
    }
  }
}

if buffer is not empty {
  for each row in t3 {
    for each t1, t2 combination in join buffer {
      if row satisfies join conditions, send to client
    }
  }
}

复制

Hash Join

Hash Join 会在内存中创建一个临时的 hash table，在两个表做 join 时，主表读入 hash table，从表逐行遍历，去 hash table 中查找对应记录，完成一次 join。相比于 O(m*n)的 NLJ, Hash Join O(m+n)的复杂度更低。

Hash Join 只能在从表的被 join 字段没有索引的情况下工作，一般来说，非常不建议在没有索引的字段上做 join，因为这会严重形象性能。那么，Hash Join 真的能实际提升查询性能吗？

实测

我们先来建个测试表

CREATE TABLE `t1` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`c1` int(11) NOT NULL DEFAULT '0',
`c2` int(11) NOT NULL DEFAULT '0',
PRIMARY KEY (`id`),
KEY `idx_c1` (`c1`)
) ENGINE=InnoDB;

CREATE TABLE `t2` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`c1` int(11) NOT NULL DEFAULT '0',
`c2` int(11) NOT NULL DEFAULT '0',
PRIMARY KEY (`id`),
KEY `idx_c1` (`c1`)
) ENGINE=InnoDB;

复制

然后插入一些随机数据

mysql> select count(*) from t1;
+----------+
| count(*) |
+----------+
| 131072   |
+----------+

复制

用 sql 做一下实际查询测试

select count(*) from t1 join t2 on t1.c2 = t2.c2

复制

Hash Join 查询

先看一下执行计划

mysql> explain format=tree select count(*) from t1 join t2 on t1.c2 = t2.c2\G
*************************** 1. row ***************************
EXPLAIN: -> Aggregate: count(0)
-> Inner hash join (t2.c2 = t1.c2) (cost=1728502115.04 rows=1728488704)
-> Table scan on t2 (cost=0.01 rows=131472)
-> Hash
-> Table scan on t1 (cost=13219.45 rows=131472)

1 row in set (0.00 sec)

复制

注意这里只能使用format=tree
才能看到是不是用了 hash join，常规 explain 仍然显示使用 NLJ。MySQL 官方对此的说法是，不建议继续使用传统 explain，链接在此^[2]

实际执行结果

mysql> select count(*) from t1 join t2 on t1.c2 = t2.c2;
+----------+
| count(*) |
+----------+
| 17172231 |
+----------+
1 row in set (0.73 sec)

复制

非 Hash Join（无索引）查询

我们可以给 sql 加一个 hint，手动禁用 hash join

mysql> select /*+ NO_HASH_JOIN (t1,t2) */ count(*) from t1 join t2 on t1.c2 = t2.c2;
+----------+
| count(*) |
+----------+
| 17172231 |
+----------+
1 row in set (13 min 36.36 sec)

复制

可以看到跟我们想象中的一样，耗时非常久，达到了 13 分钟

非 Hash Join（有索引）查询

这次我们给表上加上索引

create index idx_c2 on t1(c2);
create index idx_c2 on t2(c2);

mysql> select count(*) from t1 join t2 on t1.c2 = t2.c2;
+----------+
| count(*) |
+----------+
| 17172231 |
+----------+
1 row in set (2.63 sec)

复制

2.63s，hash join 依旧比较快

在有索引的情况下，我们可以通过ignore index
来让 MySQL 忽略索引，进而走 hash join

mysql> explain format=tree select count(*) from t1 ignore index (idx_c2) join t2 ignore index (idx_c2) on t1.c2 = t2.c2 where t1.c2=t2.c2\G
*************************** 1. row ***************************
EXPLAIN: -> Aggregate: count(0)
-> Inner hash join (t2.c2 = t1.c2) (cost=1728502115.04 rows=17336898)
-> Table scan on t2 (cost=0.00 rows=131472)
-> Hash
-> Table scan on t1 (cost=13219.45 rows=131472)

1 row in set (0.00 sec)

复制

可以看到，执行计划和没有索引时直接 hash join 是一样的。理论上 MySQL 应该提供一个 hint 在有索引的情况下显式开启 hash join 的功能，但是并没有。仔细看前面文章^[3]里开发者的回复

BNL (Block Nested-Loop) will also go away entirely at some point, at which point this hint will be ignored.

复制

在未来，MySQL 会完全抛弃掉传统的 Nested Loop Join，到时候可能都是 hash join 了

Hash Join 限制

hash join 虽然强大，但是有几个使用限制

• 被 join 的列上没有索引
• 只能在等值 join 下使用
• 只能用在 inner join，不能用在 left/right join

最后这个条件理论上不应该存在，可能是 MySQL 没来得及在 8.0.18 上推出，今后可能会有完善计划（赶工痕迹明显 0.0）

结论

在的适用条件下，hash join 能表现出强大的威力，加速查询。但是，仍然有不完善的地方。比如，怎么监控 MySQL 究竟用了多少内存在 hash table 上？如果发生磁盘交换，对性能的影响怎么样？相信随着版本的迭代，MySQL 能进化出更加丰富的功能

参考资料