pg hashjoin 節點大致步驟:
1、分塊與分桶。對一個表hash時,確定塊數和桶數量。(一塊被劃分為10個元組的桶)確定分塊號與分桶號是由hashvalue決定的。
2、執行:
- 1、順序獲取S表中所有元組,對每一條元組Hash,獲取塊號和桶號,塊號為0,放入內存桶中。
否則放入S表建立的臨時文件中。
標記內存中塊號curbatch = 0 - 2、從表R中獲取元組,進行Hash,獲取元組塊號和桶號。
當塊號 = 當前內存塊號,直接掃描對應桶,尋找滿足條件的元組并進行連接。
否則放入為表R建立的臨時文件中(每個塊都有一個)
一直執行,直到R掃描完畢。 - 3、從S表中,塊號為curbatch+1對應的臨時文件中讀取所有存儲的元組,將其hash到對應桶內,curbatch++。
- 4、從R表塊中,塊號為curbatch對應臨時文件讀取所有存儲元組,并計算桶號,并掃描桶中S,尋找滿足連接條件的tuple。
build hash table
pg11,buildhashtable階段:
1、每個worker并行掃描部分inner_table。
2、在共享內存中并行build一個hash表
3、每個worker并行地掃描outer_table,并行執行join probe操作
需要注意的是,在join之前,需要通過barrier機制,先完成自己build操作的線程需要等待hashtable被完整build后才能進入下一步的probe狀態。
multipleBatch的probe與hash
1、并行掃描inner_table,屬于batch0的tuple在內存中構建一個shared hash table;不屬于這個batch的寫入對應batch的inner tuple文件中
2、并行掃描outer_table,寫入對應batch的outer_tuple文件。
3、并行地對batch0執行join
4、某些workers先完成batch0地join后,分別領取后續batch的join任務。
狀態機
對于正在處理某個batch的worker來說
1、若沒有build完成,且有其他worker加入進來,則一起并行build hash table,在join之前必須barrier同步
2、若build完成,無需barrier
3、在barrier相關的module中,每個worker加入執行attach時,barrier中維護計數,在需要等待的地方判斷計數是否歸零。
參考
https://zhuanlan.zhihu.com/p/112003245