hybrid hash join
hybrid hash join是基于grace hash join 的優化。
在postgresql中的grace hash join 是這樣做的:inner table太大不能一次性全部放到內存中,pg會把inner table 和outer table按照join的key分成多個分區,每個分區(有一個inner table子部分也有一個outer table的子部分)保存在disk上。再對每個分區用普通的hash join。每個分區稱為一個batch,通過join key計算出hash value,然后計算出對應的batchNo與BucketNo:計算公式如下:
bucketNo = hash value % nbuckets;
batchNo = (hash value / nbuckets) % nbatch;
//nbuckets為buckets的個數,nbacth為batch的個數。
大致上和mysql差不多,不過mysql并沒有分buckets。
判斷是否需要多個batch的邏輯如下:
若 inner table的size + buckets的開銷 < work_mem,使用單個batch。否則使用多個batch:
plan_rows:預估的inner table的行數
plan_width:預估的inner table的列數
NTUP_PER_BUCKET:單個buckets的tuple數據
Work_mem:為hashjoin分配的內存配額
hybrid hash join的優化在于:對于第一個batch不必寫入disk,從而避免第一個batch的磁盤IO
具體過程如下:
1、首先對inner table進行分區/分batch,計算batchNo:
如果該tuple屬于batch0,則加入內存中的hashtable中;
否則寫入batchNo對應的disk file中。
總結就是batch0不用寫如磁盤(當然也有例外,在下文會提到)
2、對outer table進行分區/分batch,計算batchNo:
如果tuple屬于batch0,那么用key去內存hashtable尋找(equal_range or find),匹配則輸出,否則繼續讀下一行probe tuple。
否則寫入batchNo對應的disk file中。
3、outer table掃描完畢,batch0也處理完了。
開始按照No處理下一個batchx:
加載batchx的inner table到內存,build hash table
掃描batchx的outer table,進行probe。
batchx處理完,處理batchx+1,直到所有batch都處理完畢。
現在還有一個問題:如果分割后的batch0仍然太大,不能一次性放到內存中,怎么辦?
postgresql的做法是將batch個數翻倍,從原本的n變為2n。重新掃描batch0的tuples,根據nbatch = 2n,重新計算所屬的batch。如果重新計算后的batcth仍然屬于batch0,就保留在內存中,否則從內存中拿出,寫入到tuple對應的新batch中。
(此時batch0的后半部分數據被分配到batchn上)
注意,此時不會移動磁盤中batch file中已有的tuple,當處理到該batch的時候會處理。
還記得上文提到的hybrid hash join的取模操作嗎?這個操作保證了,batch數目翻倍后,tuple所屬的batch只會向后擴展。
剛剛說的只是batch0,當我們繼續處理batch_i的時候,可能還是會遇到這個問題。那么就繼續將nbatch數目翻倍吧!
當然tuple所屬的batchNo也會變化。