hybrid hash join

hybrid hash join是基于grace hash join 的優(yōu)化。
在postgresql中的grace hash join 是這樣做的：inner table太大不能一次性全部放到內(nèi)存中，pg會把inner table 和outer table按照join的key分成多個分區(qū)，每個分區(qū)(有一個inner table子部分也有一個outer table的子部分)保存在disk上。再對每個分區(qū)用普通的hash join。每個分區(qū)稱為一個batch，通過join key計算出hash value，然后計算出對應的batchNo與BucketNo：計算公式如下：

bucketNo = hash value % nbuckets; batchNo = (hash value / nbuckets) % nbatch; //nbuckets為buckets的個數(shù)，nbacth為batch的個數(shù)。

大致上和mysql差不多，不過mysql并沒有分buckets。
判斷是否需要多個batch的邏輯如下：
若 inner table的size + buckets的開銷 < work_mem，使用單個batch。否則使用多個batch：

plan_rows:預估的inner table的行數(shù) plan_width:預估的inner table的列數(shù) NTUP_PER_BUCKET：單個buckets的tuple數(shù)據(jù) Work_mem:為hashjoin分配的內(nèi)存配額

hybrid hash join的優(yōu)化在于：對于第一個batch不必寫入disk，從而避免第一個batch的磁盤IO

具體過程如下：
1、首先對inner table進行分區(qū)/分batch，計算batchNo：
如果該tuple屬于batch0，則加入內(nèi)存中的hashtable中；
否則寫入batchNo對應的disk file中。
總結(jié)就是batch0不用寫如磁盤（當然也有例外，在下文會提到）
2、對outer table進行分區(qū)/分batch，計算batchNo：
如果tuple屬于batch0，那么用key去內(nèi)存hashtable尋找(equal_range or find)，匹配則輸出，否則繼續(xù)讀下一行probe tuple。
否則寫入batchNo對應的disk file中。
3、outer table掃描完畢，batch0也處理完了。
開始按照No處理下一個batchx：
加載batchx的inner table到內(nèi)存，build hash table
掃描batchx的outer table，進行probe。
batchx處理完，處理batchx+1，直到所有batch都處理完畢。

現(xiàn)在還有一個問題：如果分割后的batch0仍然太大，不能一次性放到內(nèi)存中，怎么辦？
postgresql的做法是將batch個數(shù)翻倍，從原本的n變?yōu)?n。重新掃描batch0的tuples，根據(jù)nbatch = 2n，重新計算所屬的batch。如果重新計算后的batcth仍然屬于batch0，就保留在內(nèi)存中，否則從內(nèi)存中拿出，寫入到tuple對應的新batch中。
（此時batch0的后半部分數(shù)據(jù)被分配到batchn上）

注意，此時不會移動磁盤中batch file中已有的tuple，當處理到該batch的時候會處理。
還記得上文提到的hybrid hash join的取模操作嗎？這個操作保證了，batch數(shù)目翻倍后，tuple所屬的batch只會向后擴展。
剛剛說的只是batch0，當我們繼續(xù)處理batch_i的時候，可能還是會遇到這個問題。那么就繼續(xù)將nbatch數(shù)目翻倍吧！
當然tuple所屬的batchNo也會變化。

總結(jié)

以上是生活随笔為你收集整理的Postgresql中的hybrid hash join（无状态机讲解）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。