mysql 8 新特性三 Hash Join / 联接查询算法之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绝对值得一试的，当然具体两者之间的选择还请自己实际测试下。

下面我就看看hash join 是怎么工作的。

创建user和book表

CREATE TABLE `test`.`user`  (
  `id` bigint(0) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 772360 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

CREATE TABLE `test`.`book`  (
  `id` int(0) NOT NULL AUTO_INCREMENT,
  `user_id` bigint(0) NULL DEFAULT NULL,
  `book_name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  INDEX `index_user_id`(`user_id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compressed;

可以看看下列语句的执行计划，Extra 出现了 Using join buffer (hash join) 说明该语句使用到了hash join。这里还使用了 IGNORE index(index_user_id)禁用索引，不然使用的是INLJ。

mysql>  EXPLAIN SELECT *  FROM `user` a LEFT JOIN book  b IGNORE index(index_user_id)  ON a.id=b.user_id;
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+--------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra                                      |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+--------------------------------------------+
|  1 | SIMPLE      | a     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 639820 |   100.00 | NULL                                       |
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 785214 |   100.00 | Using where; Using join buffer (hash join) |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+--------------------------------------------+
2 rows in set (0.03 sec)

那么，使用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 操作，每个表只扫描一次就可以了，扫描匹配时间也是恒定的，非常高效。

hash 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失败。

查看hash join的执行计划

必须使用format=tree（8.0.16的新特性）才能查看hash join的执行计划：

EXPLAIN format=tree  SELECT *  FROM `user` a LEFT JOIN book  b IGNORE index(index_user_id)  ON a.id=b.user_id

-> Left hash join (b.user_id = a.id) (cost=10005295.31 rows=100050000)
-> Table scan on a (cost=101.00 rows=1000)
-> Hash
-> Table scan on b (cost=10.29 rows=100050)

对比下INLJ的执行计划：

EXPLAIN format=tree  SELECT *  FROM `user` a LEFT JOIN book  b force index(index_user_id)  ON a.id=b.user_id

-> Nested loop left join (cost=34806.15 rows=99158)
-> Table scan on a (cost=101.00 rows=1000)
-> Index lookup on b using index_user_id (user_id=a.id) (cost=24.80 rows=99)

什么样的sql可以用到Hash Join

创建几张测试表

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

从MySQL 8.0.18开始，MySQL对每个连接都有一个等连接条件的任何查询都使用散列连接，并且没有可应用于任何连接条件的索引，例如:

mysql> EXPLAIN
SELECT *
    FROM t1
    JOIN t2
        ON t1.c1=t2.c1;
                
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | NULL                                       |
|  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where; Using join buffer (hash join) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
2 rows in set (0.02 sec)

在MySQL 8.0.20之前，如果任何一对连接的表没有至少一个等连接条件，就不能使用Hash Join，并且使用了较慢的BNLJ。而在MySQL 8.0.20和更高版本中，hash join可以用于未包含等值连接条件的查询

mysql> explain SELECT * FROM t1
    JOIN t2 ON (t1.c1 < t2.c1 AND t1.c2 < t2.c2)
    JOIN t3 ON (t2.c1 < t3.c1); 
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | NULL                                       |
|  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where; Using join buffer (hash join) |
|  1 | SIMPLE      | t3    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where; Using join buffer (hash join) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
3 rows in set (0.05 sec)

甚至是笛卡尔积的join

mysql> explain SELECT * FROM t1,t2,t3;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                         |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------------------------+
|  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | NULL                          |
|  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using join buffer (hash join) |
|  1 | SIMPLE      | t3    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using join buffer (hash join) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------------------------+
3 rows in set (0.05 sec)

Semijoin也行

mysql> EXPLAIN  SELECT * FROM t1 
       WHERE t1.c1 IN (SELECT t2.c2 FROM t2)
    -> ;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+------------------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                                      |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+------------------------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | NULL                                                       |
|  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where; FirstMatch(t1); Using join buffer (hash join) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+------------------------------------------------------------+
2 rows in set (0.06 sec)

还有 antijoin

mysql>  EXPLAIN  SELECT * FROM t2 
         WHERE NOT EXISTS (SELECT * FROM t1 WHERE t1.c1 = t2.c1);
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                                  |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------------------+
|  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | NULL                                                   |
|  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where; Not exists; Using join buffer (hash join) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------------------+
2 rows in set (0.07 sec)

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 213,186评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,858评论 3赞 387
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 158,620评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,888评论 1赞 285
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,009评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,149评论 1赞 291
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,204评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,956评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,385评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,698评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,863评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,544评论 4赞 335
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,185评论 3赞 317
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,899评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,141评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,684评论 2赞 362
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,750评论 2赞 351