Hash Join 算法
mysql8以前 的 join 算法只有 nested loop 這一種驯耻,在 MySQL8 中推出了一種新的算法 hash join亲族,比 nested loop 更加高效。mysql8中的部分NLJ算法已經(jīng)取消可缚,hash join 是它的的替代方案霎迫。像屬于NLJ的BNLJ、SNLJ都會(huì)被Hash join替代帘靡!不過基于索引的INLJ算法還是存在的知给,所以實(shí)際使用中可以對(duì)比下INLJ和Hash Join的查詢性能然后做出選擇。
個(gè)人覺得mysql8這個(gè)hash join也只能算是一個(gè)錦上添花的功能描姚,頂多是代替了沒有加索引時(shí)默認(rèn)走的BNLJ算法涩赢,提高了join的性能下限。說白了就是給不懂加索引的mysql新用戶提高下join性能轰胁。其實(shí)也不絕對(duì)谒主,不過我有做 INLJ和Hash Join 對(duì)比實(shí)驗(yàn),Hash Join 很有可能比需要在內(nèi)部表建立索引的INLJ算法性能要好赃阀!畢竟當(dāng)INLJ需要回表查的時(shí)候性能會(huì)大幅度下降霎肯,這時(shí)候Hash Join絕對(duì)值得一試的,當(dāng)然具體兩者之間的選擇還請(qǐng)自己實(shí)際測(cè)試下榛斯。
下面我就看看hash join 是怎么工作的观游。
創(chuàng)建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;
可以看看下列語(yǔ)句的執(zhí)行計(jì)劃,Extra 出現(xiàn)了 Using join buffer (hash join) 說明該語(yǔ)句使用到了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會(huì)分為下面2個(gè)階段:
1搪柑、build 構(gòu)建階段:從參與join的2個(gè)表中選一個(gè)聋丝,選擇占空間小的那個(gè)表,不是行數(shù)少的工碾,這里假設(shè)選擇了 user 表弱睦。對(duì) user表中每行的 join 字段值進(jìn)行 hash(a.id ) 計(jì)算后放入內(nèi)存中 hash table 的相應(yīng)位置。所有行都存放到 hash table 之后渊额,構(gòu)建階段完成况木。
溢出到磁盤在構(gòu)建階段過程中,如果內(nèi)存滿了旬迹,會(huì)把表中剩余數(shù)據(jù)寫到磁盤上火惊。不會(huì)只寫入一個(gè)文件,會(huì)分成多個(gè)塊文件奔垦。
2屹耐、probe 探測(cè)階段:對(duì) book 表中每行中的 join 字段的值進(jìn)行 hash 計(jì)算:hash(b.user_id) 拿著計(jì)算結(jié)果到內(nèi)存 hash table 中進(jìn)行查找匹配,找到一行就發(fā)給 client椿猎。這樣就完成了整個(gè) join 操作张症,每個(gè)表只掃描一次就可以了,掃描匹配時(shí)間也是恒定的鸵贬,非常高效俗他。
hash join 相關(guān)參數(shù)
散列連接的內(nèi)存使用可以使用join_buffer_size系統(tǒng)變量來控制;散列連接使用的內(nèi)存不能超過這個(gè)數(shù)量阔逼。當(dāng)散列連接所需的內(nèi)存超過可用的數(shù)量時(shí)兆衅,MySQL通過使用磁盤上的文件來處理這個(gè)問題(溢出到磁盤)。
如果發(fā)生這種情況嗜浮,您應(yīng)該知道羡亩,如果散列連接無(wú)法容納在內(nèi)存中,并且它創(chuàng)建的文件超過了為open_files_limit設(shè)置的數(shù)量危融,則連接可能不會(huì)成功畏铆。
為避免此類問題,請(qǐng)執(zhí)行以下任一更改:
1吉殃、增加join_buffer_size辞居,以便哈希連接不會(huì)溢出到磁盤。
在MySQL 8.0.19及更高版本中蛋勺, 設(shè)置 optimizer_switch 變量值 hash_join=on or hash_join=off 的方式已經(jīng)失效了
2瓦灶、增加open_files_limit。若數(shù)據(jù)量實(shí)在太大內(nèi)存無(wú)法申請(qǐng)更大的join_buffer抱完,就只能溢出到磁盤上了贼陶。我們可以增加open_files_limit,防止創(chuàng)建的文件超過了為open_files_limit設(shè)置的數(shù)量而join失敗。
查看hash join的執(zhí)行計(jì)劃
必須使用format=tree(8.0.16的新特性)才能查看hash join的執(zhí)行計(jì)劃:
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)
對(duì)比下INLJ的執(zhí)行計(jì)劃:
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
創(chuàng)建幾張測(cè)試表
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對(duì)每個(gè)連接都有一個(gè)等連接條件的任何查詢都使用散列連接烘贴,并且沒有可應(yīng)用于任何連接條件的索引,例如:
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之前撮胧,如果任何一對(duì)連接的表沒有至少一個(gè)等連接條件庙楚,就不能使用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)