資料庫哈希連接詳解（MySQL新特性）

概述

#很長一段時間，MySQL 執行連接的唯一演算法是嵌套循環演算法( nested loop algorithm) 的變體，但是嵌套循環演算法在某些場景下非常低效，也是MySQL 一直被批評的問題。

隨著MySQL 8.0.18 的發布，MySQL Server 可以使用雜湊連線（hash join），這篇文章將會簡單介紹下雜湊連線如何實現，看看在MySQL 中它是如何運作的，何時使用它，有什麼限制。

推薦學習：MySQL教學

雜湊連接簡介

什麼是雜湊連接？

雜湊連接是一種用於關係型資料庫中的連接演算法，只能用於有等連接條件的連接中（on a.b = c.b）。它通常比 嵌套循環 演算法 更有效率（探測端非常非常小除外），尤其是在沒有命中索引的情況下。

簡單來說，哈希連接演算法就是先把一張小表加載到內存哈希表裡，然後遍歷大表的數據，逐行去哈希表中匹配符合條件的數據，返回到客戶端。

（哈希表只是範例，方面理解，實際hash 的key 是連接的值，value 是資料行鍊錶）

#通常將哈希連接分為兩個階段，建構階段（build phase）和探測階段（probe phase）。在建置階段，先選擇適當的表作為「建構輸入」，建構哈希表，然後再依序遍歷另一個「探測輸入」表記錄去探測雜湊表尋找符合連接條件的記錄。

以上圖為例，查詢城市對應的省份。我們假設 city 為 建置輸入，在建置階段，伺服器建立一個 city 雜湊 表 ，遍歷 city 表，將行依序放進 雜湊表，鍵為 hash(province_id)，值為對應的 城市行。 `

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

也就是，建構輸入能全部被載入到記憶體的情況下，僅掃每個探測行一次，使用常數時間查找就可以查找到兩個輸入之間匹配的行。

資料太多不能放入記憶體怎麼辦？

將 建置輸入 全部載入到記憶體中無疑是效率最高的，但在有些情況下，記憶體不足以將整張表載入到記憶體中，就需要分批來處理。

常見的做法有兩種：

分批載入到記憶體處理

1.讀取最大記憶體可以容納的記錄創建哈希表構建輸入生成哈希表；

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

3.清理掉哈希表重新進行這個流程，直到全部處理完成。

這種方式會導致探測輸入全表掃描多次。

寫到檔案處理

1.當在建立雜湊表階段記憶體用完時，伺服器將會把剩餘的建置輸入寫到磁碟上的許多小檔案中，小檔案區塊經過計算可以全部被讀入記憶體並創建哈希表（避免檔案區塊太大後續無法載入到記憶體還需要再次分隔）；

2.在探測階段，由於探測行可能與寫入磁碟的建置輸入的某行匹配，所以也需要將探測輸入寫入到磁碟中；

3.探測階段完成後，從磁碟讀取區塊檔案並載入到內存在散列表中，再從探測輸入讀取回應的區塊檔案並探測匹配項；

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

MySQL 中的雜湊連接實作

MySQL 會選擇兩個輸入中較小的一個作為建構輸入(以位元組計算)，在記憶體足夠的情況下將建置輸入載入到記憶體處理，不夠的情況下使用寫入檔案的方式處理。

可以使用 join_buffer_size 系統變數控制 哈希連接 的記憶體使用，哈希連接 使用的記憶體不能超過這個數量，當超過這個數量時，MySQL 會使用檔案來處理。

如果記憶體超過 join_buffer_size，且檔案超過 open_files_limit ，執行可能會失敗。

可以使用以下兩個解決方案：

● 增大join_buffer_size 來避免雜湊連線溢出到磁碟

##● 增大open_files_limit

MySQL 什麼情況下會使用哈希連線？

在 MySQL 8.0.18 版本中，如果使用一個或多個等連接條件將資料表連接在一起，且沒有可用於連接條件的索引，則會使用雜湊連接。如果索引可用，MySQL 傾向於使用索引查找來支援巢狀循環。

預設情況下，MySQL 會盡可能使用哈希連接，可以透過以下兩種方式啟用或關閉：

● 設定全域或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)

雜湊連接也可以用到多個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 雜湊連接只支援內連接，反連接、半連接和外連接仍然使用區塊嵌套循環執行。

2.如果索引可用，MySQL 會更傾向於使用索引查找來支援巢狀循環；

#3.當不存在等值查詢時，會使用巢狀循環。

如下：

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

輸出為：

| <not executable by iterator executor>

#如何查看語句執行是否使用雜湊連接？

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

除此之外，也可以使用 EXPLAIN ANALYZE 查看 雜湊連接 資訊。

---

以上是基於 MySQL community Server 8.0.18。

以上是資料庫哈希連接詳解（MySQL新特性）的詳細內容。更多資訊請關注PHP中文網其他相關文章！