概述

很長一段時(shí)間，MySQL 執(zhí)行 連接 的唯一算法是 嵌套循環(huán)算法 ( nested loop algorithm) 的變體 ，但是 嵌套循環(huán)算法 在某些場景下非常低效，也是 MySQL 一直被詬病的一個(gè)問題。

隨著 MySQL 8.0.18 的發(fā)布，MySQL Server 可以使用哈希連接（hash join），這篇文章將會簡單介紹下哈希連接如何實(shí)現(xiàn)，看看在 MySQL 中它是如何工作的，何時(shí)使用它，有什么限制。

推薦學(xué)習(xí)：MySQL教程

哈希連接簡介

什么是哈希連接？

哈希連接是一種用于關(guān)系型數(shù)據(jù)庫中的連接算法，只能用于有等連接條件的連接中（on a.b = c.b）。它通常比 嵌套循環(huán) 算法 更高效（探測端非常非常小除外），尤其是在沒有命中索引的情況下。

簡單來說，哈希連接算法就是先把一張小表加載到內(nèi)存哈希表里，然后遍歷大表的數(shù)據(jù)，逐行去哈希表中匹配符合條件的數(shù)據(jù)，返回到客戶端。

（哈希表只是示例，方面理解，實(shí)際 hash 的 key 是連接的值，value 是數(shù)據(jù)行鏈表）

通常將 哈希連接 分為兩個(gè)階段，構(gòu)建階段（build phase）和探測階段（probe phase）。在構(gòu)建階段，先選擇合適的表作為「構(gòu)建輸入」，構(gòu)建哈希表，然后再依次遍歷另一個(gè)「探測輸入」表記錄去探測哈希表查找符合連接條件的記錄。

以上圖為例，查詢城市對應(yīng)的省份。我們假設(shè) city 為 構(gòu)建輸入，在構(gòu)建階段，服務(wù)器構(gòu)建一個(gè) city 哈希 表 ，遍歷 city 表，將行依次放進(jìn) 哈希表，鍵為 hash(province_id)，值為對應(yīng)的 城市行。`

在探測階段，服務(wù)器開始從 探測輸入（province） 讀取行。對于每一行都使用 hash(province.province_id) 值作為查找鍵探測哈希表以匹配行。

也就是，構(gòu)建輸入能全部被加載到內(nèi)存的情況下，僅掃每個(gè)探測行一次，使用常數(shù)時(shí)間查找就可以查找到兩個(gè)輸入之間匹配的行。

數(shù)據(jù)太多不能放入內(nèi)存怎么辦？

將 構(gòu)建輸入 全部加載到內(nèi)存中無疑是效率最高的，但在有些情況下，內(nèi)存不足以將整張表加載到內(nèi)存中，就需要分批來處理。

常見的做法有兩種：

分批加載到內(nèi)存處理

1.讀取最大內(nèi)存可以容納的記錄創(chuàng)建哈希表 構(gòu)建輸入 生成哈希表；

2.遍歷 探測輸入 對這部分哈希表進(jìn)行一次全量探測；

3.清理掉哈希表重新進(jìn)行這個(gè)流程，直至全部處理完成。

這種方式會導(dǎo)致探測輸入全表被掃描多次。

寫到文件處理

1.當(dāng)在構(gòu)建哈希表階段內(nèi)存用完時(shí)，服務(wù)器將會把剩余的構(gòu)建輸入寫到磁盤上的許多小文件中，小文件塊經(jīng)過計(jì)算可以全部被讀入內(nèi)存并創(chuàng)建哈希表（避免文件塊太大后續(xù)無法加載到內(nèi)存還需要再次分隔）；

2.在探測階段，由于探測行可能與寫入磁盤的構(gòu)建輸入的某行匹配，所以也需要將探測輸入寫入到磁盤中；

3.探測階段完成后，從磁盤讀取塊文件并加載到內(nèi)存散列表中，再從探測輸入讀取響應(yīng)的塊文件并探測匹配項(xiàng)；

4.處理完后，移動到下一對塊文件，直至全部處理完成。

MySQL 中的哈希連接實(shí)現(xiàn)

MySQL 會選擇兩個(gè)輸入中較小的一個(gè)作為構(gòu)建輸入(以字節(jié)計(jì)算)，在內(nèi)存足夠的情況下將構(gòu)建輸入加載到內(nèi)存處理，不夠的情況下使用寫入文件的方式處理。

可以使用 join_buffer_size 系統(tǒng)變量控制 哈希連接 的內(nèi)存使用，哈希連接 使用的內(nèi)存不能超過這個(gè)數(shù)量，當(dāng)超過這個(gè)數(shù)量時(shí)，MySQL 將使用文件來處理。

如果內(nèi)存超過 join_buffer_size，并且文件超過 open_files_limit ，執(zhí)行可能失敗。

可以使用如下兩個(gè)解決方案：

● 增大 join_buffer_size 來避免 哈希連接 溢出到磁盤

● 增大 open_files_limit

MySQL 什么情況下會使用哈希連接？

在 MySQL 8.0.18 版本中，如果使用一個(gè)或多個(gè)等連接條件將表連接在一起，并且沒有可用于連接條件的索引，將使用哈希連接。如果索引可用，MySQL 傾向于使用索引查找來支持嵌套循環(huán)。

默認(rèn)情況下，MySQL 會盡可能使用哈希連接 ，可以通過以下兩種方式啟用或關(guān)閉：

● 設(shè)置全局或 session 變量 (hash_join = on or hash_join = off)；

SET optimizer_switch="hash_join=off";

● 使用 hints (HASH_JOIN or NO_HASH_JOIN)。

我們將使用以下查詢作為示例：

EXPLAIN FORMAT = tree SELECT   city.name AS city_name,   province.name AS province_name FROM   city   JOIN province     ON city.province_id = province.province_id;

輸出為：

| -> Inner hash join (city.province_id = province.province_id)  (cost=1333.82 rows=1329)     -> Table scan on city  (cost=0.14 rows=391)     -> Hash         -> Table scan on province  (cost=3.65 rows=34)

哈希連接 也可以用到多個(gè) join 的查詢中，只要存在等值連接，就可以使用哈希連接。

例如以下查詢：

EXPLAIN FORMAT= TREE SELECT   city.name AS city_name,   province.name AS province_name,   country.name AS country_name FROM   city   JOIN province     ON city.province_id = province.province_id     AND city.id < 50   JOIN country     ON province.province_id = country.id

輸出為：

| -> Inner hash join (city.province_id = country.id)  (cost=23.27 rows=2)     -> Filter: (city.id < 50)  (cost=5.32 rows=5)         -> Index range scan on city using PRIMARY  (cost=5.32 rows=49)     -> Hash         -> Inner hash join (province.province_id = country.id)  (cost=4.00 rows=3)             -> Table scan on province  (cost=0.59 rows=34)             -> Hash                 -> Table scan on country  (cost=0.35 rows=1)

哈希連接也同樣適用于 「笛卡爾積」，即沒有指定查詢條件，如下：

EXPLAIN FORMAT= TREE SELECT   * FROM   city   JOIN province;

輸出為：

| -> Inner hash join  (cost=1333.82 rows=13294)     -> Table scan on city  (cost=1.17 rows=391)     -> Hash         -> Table scan on province  (cost=3.65 rows=34)

MySQL 什么情況下不會使用哈希連接？

1.目前 MySQL 哈希連接只支持內(nèi)連接，反連接、半連接和外連接仍然使用塊嵌套循環(huán)執(zhí)行。

2.如果索引可用，MySQL 會更傾向于使用索引查找來支持嵌套循環(huán)；

3.當(dāng)不存在等值查詢時(shí)，會使用嵌套循環(huán)。

如下：

EXPLAIN FORMAT=TREE SELECT   * FROM   city   JOIN province     ON city.province_id < province.province_id;

輸出為：

| <not executable by iterator executor>

如何查看語句執(zhí)行是否使用哈希連接？

EXPLAIN FORMAT= TREE 在 MySQL 8.0.16 及之后的版本可以使用，TREE 提供了類似于樹的輸出，對查詢處理的描述比傳統(tǒng)格式更加精確，它是唯一顯示 哈希連接 用法的格式。

除此之外，也可以使用 EXPLAIN ANALYZE 查看 哈希連接 信息。

<hr/> 以上基于 MySQL community Server 8.0.18。