如何在分散式資料庫中實現 Hash Join ?

05-12

作者｜ @劍鳴

Join 是關係資料庫中非常重要的一種操作。資料庫對於Join通常有三種主要的實現: Merge Join, Nested-loop Join, Hash Join。其中 Hash Join 適用於帶有等值條件情況，由於 Hash Join 的演算法複雜度在平均情況下是 O(n)，通常在大規模數據做Hash Join是最優的選擇。主流的關係資料庫 (Oracle, SQL Server, PostgreSQL) 等都有 Hash Join 的實現。MySQL 主要應用於 oltp 場景，沒有實現 Hash Join。

In-Memory Hash Join

對於兩張待 join 的表 t1, t2。選取其中的一張表按照 join 條件給的列建立hash 表。然後掃描另外一張表，一行一行去建好的 hash 表判斷是否有對應相等的行來完成 join 操作，這個操作我們稱之為 probe (探測)。前一張表我們叫做 build 表，後一張表我們的叫做 probe 表。

為了減少內存使用量，我們通常選擇小表作為 hash 表，大表做為 probe 表。另外我們發現如果 hash 衝突比較嚴重的話，最極端的例子 hash 表所有的值都一樣的話，那麼單個 hash bucket (hash桶)內部的 Hash Join 就會退化成 Nested-Loop Join。

Grace Hash Join

當 build 表數據量比較大，無法在內存中全部存下的時候，我們需要利用磁碟來完成 join 操作。最直觀的想法，就是分片載入 build 表。每載入一個 build 表的一個分片，然後從頭到尾掃描一遍probe表，進行一次 probe 操作，完成 join 操作。這樣做的問題是掃描磁碟的次數過多。總的掃描量是build表 + n * probe 表。n 是 build 表的分片個數。

Grace Hash Join 的方法是: 先對兩個即將做 Hash Join 的表按照同一個 hash 函數分配到不同的分片中。然後再分別對不同的分片做 In-Memory Hash Join。這是典型的分治的思想。如果單個分片還是不能全部放到內存中，可以迭代的使用 Grace Hash Join 方法。具體做法的偽代碼如下：

t1, t2 是待join兩個表PartCount是分片的個數def graceJoin(t1, t2): for row in t1: hashValue = hash_func(row) N = hashValue % PartCount; write row to file t1_N; for row in t2: hashValue = hash_func(row) N = hashValue % PartCount; write row to file t2_N; for i in range(0, PartSize): join(t1_i, t2_i)

這裡的 PartCount 選取很有講究。不能太小，如果太小起不到分治效果，最後的那個 join 可能還需要做 Grace Hash Join。增加了讀寫磁碟的次數。比如極端情況下選取 PartCount = 1，那麼就完全沒有任何的效果了。那麼是不是PartCount 選取越大越好呢？其實也不是這樣的，主要是因為是磁碟是一個塊設備，每次刷盤都需要刷一定大小的塊 (block)才高效。如果 PartCount 設置的太大，會導致某些分片中包含的行數太少，達不到 block 的大小，刷盤不經濟。所以籠統的說 PartCount 在保證刷盤經濟上的情況下越大越好。這個需要優化器根據表的統計信息來確定。

這個演算法有一個 Bad Case 。就是某個表的 row 經過 hash 以後都落入了同一個分片中，那麼就起不到分治的效果。這個時候可以更換 hash 函數，但是如果本來 row 的值都是一樣的，那麼可以退化到直觀的那種做法。其實如果發生這種情況的時候，應該在優化器選擇 join 方法的時候就可能就不應該選擇 Hash Join。例如可以選擇 Nested-loop Join 會更好。

Hybrid Hash Join

Hybrid Hash Join 結合了 In-memory Hash Join 和 Grace Hash Join 的優點。Hybrid Hash Join 是 Grace Hash Join 的一種改進，在 Grace Hash Join 第一張表分片的過程中，盡量把越多的完整的分片保留在內存中。這樣在第二張表做分片的過程中，就可以同時對留在內存中的分片做 probe 操作，這樣省去了留在內存中分片的刷盤操作，同時第二張表對應的分片也不需要刷盤，提高效率。如果第一張表所有的分片都能留在內存中，其實就是 In-memory Hash Join。我們把第一張表叫做 build table，第一張表分片的過程叫做 build phase。第二張表叫做 probe table，第二張表分片的過程叫做 probe phase。那麼我們詳細介紹兩個過程。

Build Phase 如下圖所示，hash table 被分成了4個分片，圖中每個分片用不同的顏色表示。build階段讀取build表中的數據，然後 hash 到各個 hash 桶裡面。桶的數據存儲在內存塊 (block) 中，block 在圖中使用正方形的小方塊表示。 block 是一個刷盤的最小單位。當放 block 的內存快滿的時候，就會把其中一些 block 刷到磁碟中，刷盤的時候會盡量保證某些分片完整的留在內存中，所以盡量把那些已經落到磁碟中的分片的 block 刷出去。在圖中，紅色和綠色的分片應該盡量保留在內存中，會優先刷藍色和黃色的 block。

Probe Phase 如下圖所示，在 probe 階段，掃描probe表，然後在 hash table中找到對應的 hash 桶。如果 hash 到磁碟上沒有數據的分片（紅色，綠色）所在的hash桶，那麼就可以直接做 join 返回結果。如果hash到在磁碟上有數據的分片（黃色，藍色），那麼就把 probe 表的行寫內存中的對應分片的 block 中，當一個 block 被寫滿以後就刷到磁碟中，圖中虛線小方塊表示。

等 build 和 probe 階段都做完，還有一部分數據在磁碟和內存中。那麼遞歸分別對這些剩餘的分片遞歸調用一遍 Hybrid Hash Join。Hybrid Hash Join 也會遇到 Grace Hash Join 的一些問題 Bad Case，處理的方法類似。這裡不再贅述。

OceanBase 完整高效的實現了 Hybrid Hash Join 演算法，歡迎使用。

參考文檔

https://en.wikipedia.org/wiki/Hash_join
https://technet.microsoft.com/en-us/library/ms189313(v=sql.105).aspx