面試官：MySQL 8.0版本引入的 hash join 有什么優(yōu)勢(shì)？
MySQL 在 8.0.18 中引入 hash join，這是一個(gè)為 join 查詢語(yǔ)句設(shè)計(jì)的高效算法。今天來(lái)介紹一下 hash join。
1.簡(jiǎn)介
首先我們建立兩張表，SQL 如下：
CREATE TABLE t1 (c1 INT, c2 INT);
CREATE TABLE t2 (c1 INT, c2 INT);再給出一個(gè)連接查詢 SQL：
SELECT * FROM t1 JOIN t2 ON t1.c1=t2.c1;那 hash join 的執(zhí)行過(guò)程是怎樣的呢？
- 確定驅(qū)動(dòng)表（MySQL 會(huì)選擇結(jié)果集較小的表作為驅(qū)動(dòng)表），將結(jié)果集加載到內(nèi)存中；
- 以連接鍵為 hash key 構(gòu)建 hash 表，使用鏈表法解決 hash 沖突。
- 對(duì)于非驅(qū)動(dòng)表，依次掃描每一行數(shù)據(jù)，對(duì) join 字段取 hash 值，然后在 2 構(gòu)建的 hash 表中查找這個(gè) hash 值；
- 如果找到，則對(duì)這個(gè) hash 值所在的鏈表上每個(gè)值進(jìn)行等值比較，如果比較結(jié)果一致，則結(jié)合兩個(gè)表的相關(guān)字段生成結(jié)果集并輸出；
- 如果找不到，則繼續(xù)掃描下一行。 整個(gè)過(guò)程如下圖：
圖片
hash join 的時(shí)間復(fù)雜度是多少呢？假如 t1 表的記錄數(shù)是 M，掃描 t1 表的時(shí)間復(fù)雜度是 o(M)，t2 表的記錄數(shù)是 N，掃描 t2 表的時(shí)間復(fù)雜度是 o(N)，hash 表查詢的復(fù)雜度是 o(1)，這樣使用 hash join 查找的總時(shí)間復(fù)雜度是 o(M + N)。
2.優(yōu)勢(shì)
在上面的例子中，t1 表和 t2 表都沒(méi)有加索引，如果做 join 查詢，在 MySQL 8.0 以前，會(huì)使用 BNL 算法。
圖片
BNL 算法流程如下：
- 把 t1 表的數(shù)據(jù)讀出放到 join_buffer；
- 掃描 t2 表中的每一行，用 c1 字段值跟 join_buffer 中 t1 表的 c1 字段值做比較；
- 如果 c1 值一樣，則作為結(jié)果集返回，如果不一樣，則繼續(xù)掃描 t2 表下一行。
圖片
join_buffer 是一個(gè)無(wú)序數(shù)組，t2 表中的每一行都需要跟 t1 表的所有記錄做比對(duì)。假如 t1 表的數(shù)據(jù)量是 M，t2 表的數(shù)據(jù)量是 N，則需要比對(duì)的次數(shù)是 M * N，也就是說(shuō)時(shí)間復(fù)雜度是 o(M*N)。
從時(shí)間復(fù)雜度可以明顯看出 hash join 的優(yōu)勢(shì)。
從 MySQL 8.0.20 開(kāi)始，不再支持 BNL 算法，server 在原先使用 BNL 算法的地方使用 hash join。
3.hash join 優(yōu)化
MySQL 8.0.18 引入 hash join，主要用于 join 語(yǔ)句中有等值條件并且 join 條件中不能使用索引的場(chǎng)景。比如前面例子中的 join 語(yǔ)句，t1 和 t2 的 c1 字段都沒(méi)有索引：
SELECT * FROM t1 JOIN t2 ON t1.c1=t2.c1;3.1 配置
MySQL 8.0.18 版本中，支持設(shè)置 hash_join=on 或 hash_join=off 供優(yōu)化器選擇，在 MySQL 8.0.19 及更高版本中，這個(gè)設(shè)置不再生效，server 會(huì)默認(rèn)使用 hash join。
3.2 連接條件優(yōu)化
優(yōu)化一：在 MySQL 8.0.20 以前，如果 join 條件中存在一個(gè)非等值匹配的條件，就會(huì)走 BNL 算法。MySQL 8.0.20 以后，即使有非等值條件，也會(huì)走 hash join。下面 SQL 來(lái)自官網(wǎng)：
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)優(yōu)化二：即使 join 沒(méi)有條件，也會(huì)走 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)優(yōu)化三：即使 join 條件中沒(méi)有等值條件，也會(huì)走 hash join。下面 5 個(gè)示例來(lái)自官網(wǎng)，都會(huì)走 hash join。
1.內(nèi)連接無(wú)等值條件：
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 #14.左外連接：
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.總結(jié)
hash join 算法的出現(xiàn)對(duì) join 語(yǔ)句的性能大幅提升，MySQL 8.0.20 后，對(duì) hash join 的使用又做了進(jìn)一步的優(yōu)化，使用更加便捷。
