PG歸併排序演算法詳解
- 2020 年 3 月 15 日
- 筆記
前言
-
歸併排序演算法是連接演算法中比較複雜的演算法，相比嵌套循環與Hash匹配而言。本節會通過實例來說明該演算法在PG中的具體實現。
-
在PG中，通過狀態機來實現——歸併-連接。當然這裡的完整流程是排序——歸併——連接，由於排序通過Sort操作來完成，這裡就不贅述。
-
這裡的狀態機一共有11中狀態，在這11中狀態的轉換過程中，會根據外表(inner)或內表(inner)讀取到數據的狀態分為——
MJEVAL_MATCHABLE、MJEVAL_NONMATCHABLE、MJEVAL_ENDOFJOIN。可以簡單理解為讀取到非空數據，讀取到數據為空以及所有數據讀取完成。 - 前置條件，內外表均已排序完成且都是升序策略。
-----------初始狀態----------------- EXEC_MJ_INITIALIZE_OUTER EXEC_MJ_INITIALIZE_INNER -----------中間狀態----------------- EXEC_MJ_NEXTOUTER EXEC_MJ_TESTOUTER EXEC_MJ_NEXTINNER EXEC_MJ_SKIP_TEST EXEC_MJ_SKIPOUTER_ADVANCE EXEC_MJ_SKIPINNER_ADVANCE -------------結束狀態----------------- EXEC_MJ_JOINTUPLES EXEC_MJ_ENDOUTER EXEC_MJ_ENDINNER舉例
- 接下來，以一個實例來說明狀態機轉換的具體流程。這裡假設有兩張表進行全外連接——outer/inner。數據如下所示：
outer inner 5 5 5 5 6 8 6 8 7 12 8 14- 簡單提及一下後面說明過程中會涉及到的變數
- 1 (current) outer tuple掃描到的一條外表數據，eg: 5/6/7
- 2 (current) inner tuple掃描到的一條內表數據，eg: 8/12/14
- 3 marked tuple 上一次與outer tuple匹配到的inner tuple，記錄為marked tuple(描述的是inner tuple)
-
4 offset tuple 在方法ExecMarkPos執行時，會將當前inner tuple的位置做標記，以便後面inner tuple的重新掃描。通過方法ExecSortRestrPos實現標記。通過方法ExecRestrPos來實現將(current) inner tuple恢復為offset tuple。
-
1 第一輪，初始狀態為EXEC_MJ_INITIALIZE_OUTER，外表游標下移獲取到outer tuple——5(1)。通過MJEVAL_MATCHABLE切換到狀態EXEC_MJ_INITIALIZE_INNER。
在狀態EXEC_MJ_INITIALIZE_INNER下，內表游標下移獲取到——5(1)。通過MJEVAL_MATCHABLE切換到EXEC_MJ_SKIP_TEST。
來到狀態EXEC_MJ_SKIP_TEST，這裡執行方法MJCompare，也就是對outer tuple與inner tuple進行了比較，5(1) == 5(1)。標記offset為current，同時將marked tuple置為當前tuple。然後切換到狀態EXEC_MJ_JOINTUPLES。
在狀態EXEC_MJ_JOINTUPLES下，首先更改狀態為EXEC_MJ_NEXTINNER，然後將匹配到的數據返回。
到這裡為止，完成了外表/內表的數據匹配，一輪匹配就結束了。
- 匹配結果 5(1) == 5(1)
outer inner outer tuple - 5 5 - marked tuple - offset tuple - inner tuple 5 5 6 8 6 8 7 12 8 14-
2 第二輪，由於上一輪在退出時將狀態置為EXEC_MJ_NEXTINNER，因此，這一輪從狀態EXEC_MJ_NEXTINNER出發。該狀態下，內表游標下移獲取數據——5(2),然後調用方法MJCompare比較outer tuple與inner tuple，5(1) == 5(2)，切換到狀態EXEC_MJ_JOINTUPLES。同樣，切換狀態為EXEC_MJ_NEXTINNER，並且完成該輪掃描(後面不再贅述)。
- 匹配結果 5(1) == 5(2)
outer inner outer tuple - 5 5 - marked tuple - offset tuple 5 5 - inner tuple 6 8 6 8 7 12 8 14-
3 第三輪，繼續來到狀態EXEC_MJ_NEXTINNER，此時內表游標下移獲取數據——8(1)，與outer tuple相比——5(1) < 8(1)，切換到狀態EXEC_MJ_NEXTOUTER。
在狀態EXEC_MJ_NEXTOUTER下，外表游標下移獲取到outer tuple——5(2)，同時通過MJEVAL_MATCHABLE切換到EXEC_MJ_TESTOUTER。
在狀態EXEC_MJ_TESTOUTER下，這裡對於outer tuple與marked tuple進行了比較，也就是5(2) == 5(1)，這裡調用方法ExecRestrPos重置了內表的游標，將inner tuple置為offset tuple，也就是說，下一次內表游標的下移後獲取的數據是——5(2)。然後切換狀態為EXEC_MJ_JOINTUPLES，同時結束了本輪的匹配。
- 匹配結果 5(2) == 5(1)
outer inner 5 5 - marked tuple - offset tuple - inner tuple outer tuple - 5 5 6 8 6 8 7 12 8 14-
4 第四輪，其實與第二輪的描述基本一致，只是結果發生了變化
- 匹配結果 5(2) == 5(2)
outer inner 5 5 - marked tuple - offset tuple outer tuple - 5 5 - inner tuple 6 8 6 8 7 12 8 14-
5 第五輪，在狀態EXEC_MJ_NEXTINNER下，內表游標下移獲取數據——8(1)，需要注意的是，這裡將mj_MatchedInner標記為false。與outer tuple比較——5(2) < 8(1)，切換到狀態EXEC_MJ_NEXTOUTER。
在狀態EXEC_MJ_NEXTOUTER下，外表游標下移獲取到outer tuple——6(1)，同時通過MJEVAL_MATCHABLE切換到EXEC_MJ_TESTOUTER。
在狀態EXEC_MJ_TESTOUTER下，這裡對於outer tuple與marked tuple進行了比較——6(1) > 5(1)，重新載入current inner tuple——8(1)，然後切換到狀態EXEC_MJ_SKIP_TEST。
在狀態EXEC_MJ_SKIP_TEST下，調用方法MJCompare比較outer tuple與inner tuple——6(1) < 8(1)。切換到狀態EXEC_MJ_SKIPOUTER_ADVANCE。
來到狀態EXEC_MJ_SKIPOUTER_ADVANCE。由於在該輪開始，變數mj_MatchedOuter已經被置為false，因此，這裡並沒有繼續外表的游標下移，而是修改變數mj_MatchedOuter為true，然後調用MJFillOuter將其關聯的inner tuple置為空。這裡沒有進行狀態的切換。該輪循環結束。
- 關聯結果 6(1) null
outer inner 5 5 - marked tuple - offset tuple 5 5 outer tuple - 6 8 - inner tuple 6 8 7 12 8 14-
6 由於上面一輪並沒有發生狀態的切換，因此，該輪繼續從狀態EXEC_MJ_SKIPOUTER_ADVANCE出發，只是，上一輪結束時，將變數mj_MatchedOuter置為true，因此，外表游標下移獲取到outer tuple——6(2)，將mj_MatchedOuter置為false，然後切換到狀態EXEC_MJ_SKIP_TEST。
來到狀態EXEC_MJ_SKIP_TEST，調用方法MJCompare比較outer tuple與inner tuple——6(2) < 8(1)。切換到狀態EXEC_MJ_SKIPOUTER_ADVANCE。與上一輪相似，這裡同樣調用MJFillOuter將其關聯的inner tuple置為空。這裡沒有進行狀態的切換。該輪循環結束。
- 關聯結果 6(2) null
outer inner 5 5 - marked tuple - offset tuple 5 5 6 8 - inner tuple outer tuple - 6 8 7 12 8 14-
7 這一輪的流程基本與第六輪相似，只是外表游標下移獲取到outer tuple——7。
- 關聯結果 7 null
outer inner 5 5 - marked tuple - offset tuple 5 5 6 8 - inner tuple 6 8 outer tuple - 7 12 8 14-
8 該輪同樣從狀態EXEC_MJ_SKIPOUTER_ADVANCE出發，外表游標下移獲取到outer tuple——8，狀態切換到EXEC_MJ_SKIP_TEST。
來到狀態EXEC_MJ_SKIP_TEST，調用方法MJCompare比較outer tuple與inner tuple——8 == 8(1)。這裡標記offset為current，同時將marked tuple置為當前tuple。然後切換到狀態EXEC_MJ_JOINTUPLES。同時結束了本輪的匹配。（不要忘記，下一輪從狀態EXEC_MJ_NEXTINNER出發）
- 關聯結果 8 == 8(1)
outer inner 5 5 5 5 6 8 - marked tuple - offset tuple - inner tuple 6 8 7 12 outer tuple - 8 14-
9 該輪從狀態EXEC_MJ_NEXTINNER出發，內表游標下移獲取數據——8(2)，調用方法MJCompare與outer tuple相比較——8 == 8(2)，因此，切換到狀態EXEC_MJ_JOINTUPLES，同時結束本輪的匹配。
- 關聯結果 8 == 8(2)
outer inner 5 5 5 5 6 8 - marked tuple - offset tuple 6 8 - inner tuple 7 12 outer tuple - 8 14-
10 該輪同樣從狀態EXEC_MJ_NEXTINNER出發，內表游標下移獲取數據——8(2)，同時將變數mj_MatchedInner設置為false，調用方法MJCompare與outer tuple相比較——8 < 12，故切換到狀態EXEC_MJ_NEXTOUTER。
在狀態EXEC_MJ_NEXTOUTER下，外表游標下移，同時將變數mj_MatchedOuter置為false，由於此時外表已經沒有數據了，因此通過MJEVAL_ENDOFJOIN切換到狀態EXEC_MJ_ENDOUTER。
來到狀態EXEC_MJ_ENDOUTER，由於變數mj_MatchedInner為false，這裡重置mj_MatchedInner為true後，調用方法MJFillInner，將inner tuple——12關聯的outer tuple填充為null。這裡沒有狀態切換。該輪循環結束。
- 關聯結果 null 12
outer inner 5 5 5 5 6 8 - marked tuple - offset tuple 6 8 7 12 - inner tuple 8 14 outer tuple - eof eof -
11 該輪從上一輪結束的狀態EXEC_MJ_ENDOUTER出發。由於mj_MatchedInner為true，首先調用方法ExecMarkPos標記offset為current，然後內表游標下移，同時將變數變數mj_MatchedInner設置為false，狀態不變。
繼續來到狀態，這裡與繼續調用方法MJFillInner，將inner tuple——14關聯的outer tuple填充為null。這裡沒有狀態切換。該輪循環結束。
- 關聯結果 null 14
outer inner 5 5 5 5 6 8 - marked tuple 6 8 7 12 - offset tuple 8 14 - inner tuple outer tuple - eof eof -
12 仍然是狀態EXEC_MJ_ENDOUTER，這裡同樣首先調用方法ExecMarkPos標記offset為current，然後內表游標下移，同時將變數變數mj_MatchedInner設置為false。由於此時內表的掃描結束，返回為空，同時該輪循環結束。
- 關聯結果 null
outer inner 5 5 5 5 6 8 - marked tuple 6 8 7 12 8 14 - offset tuple outer tuple - eof eof - inner tuple - 至此，歸併排序的舉例就結束了。我推薦大家在閱讀本文的時候最好參照pg源碼——nodeMergejoin.c文件中的ExecMergeJoin方法，有事半功倍之效。
總結
- 狀態EXEC_MJ_NEXTINNER，該狀態的前置狀態只有EXEC_MJ_JOINTUPLES。在該狀態下內表游標下移獲取數據，因此，outer tuple與inner tuple比較只有兩種情況
- 1 outer tuple = inner tuple
- 2 outer tuple < inner tuple
- 狀態EXEC_MJ_TESTOUTER，該狀態的前置狀態只有EXEC_MJ_NEXTINNER與EXEC_MJ_NEXTOUTER。而在該狀態下外表游標下移獲取數據，因此，outer tuple與inner tuple比較只有兩種情況
- 1 outer tuple = inner tuple
- 2 outer tuple > inner tuple
-
狀態EXEC_MJ_NEXTOUTER與EXEC_MJ_SKIPOUTER_ADVANCE的區別：
前者會切換到狀態EXEC_MJ_TESTOUTER來比較。
而後者會切換到EXEC_MJ_SKIP_TEST來比較。
-
狀態EXEC_MJ_SKIP_TEST與EXEC_MJ_TESTOUTER區別：
前者outer tuple與inner tuple比較有三種可能的結果。這裡比較的是current outer tuple與current inner tuple。
而後者只有兩種可能的情況。而這裡比較的是current outer tuple與makred inner tuple。
如果current outer tuple > marked inner tuple，那麼inner tuple從current tuple與outer tuple切換到狀態EXEC_MJ_SKIP_TEST進行比較。
-
恢復標記
在狀態EXEC_MJ_TESTOUTER中遇到outer tuple == marked tuple時，這裡會置inner tuple為offset tuple，並且將inner tuple置為之前保存的offset tuple。
圖示
