Sort 節(jié)點概覽

排序的樸素含義是將一個數(shù)據(jù)集按照某種特定的排序方式進行排列的算法，最常見的排列方式是數(shù)值順序和字典序。

排序算法的應用非常廣泛，主要分為了兩類：

• 內(nèi)排序：在內(nèi)存中完成的排序，常見的有插入排序、快速排序、堆排序、基數(shù)排序等
• 外排序：數(shù)據(jù)集過大，內(nèi)存中無法全部存放，需要借助外存的排序，常見的有歸并排序的各種變形

gpdb 的排序節(jié)點會根據(jù)查詢計劃中的排序鍵對指定的元組進行排序，根據(jù)排序的數(shù)據(jù)量和其他的一些性質(zhì)，gpdb 會選擇不同的排序算法：

• 如果排序節(jié)點的工作內(nèi)存可以容納所有的元組時，排序節(jié)點使用快速排序或者堆排序
• 堆排序主要用于 TopK 查詢，即只需要輸出排序后元組的前 K 個，例如 Sort 節(jié)點之上還存在 Limit 節(jié)點

如果工作內(nèi)存無法容納所有的元組，則使用基于歸并排序的外排序算法。

排序節(jié)點除了本身對元組排序的功能外，在 gpdb 中的應用也廣泛，查詢優(yōu)化器還會根據(jù)代價選擇基于排序的聚集節(jié)點 Group Agg 和連接節(jié)點 Merge Join。

此外，Group By，Distinct 等 sql 關鍵字也和排序息息相關。

TupleSort

TupleSort 是 gpdb 各種排序功能的底層實現(xiàn)，各種需要排序的模塊都會使用調(diào)用 TupleSort 對元組進行排序。
TupleSort 使用的排序算法如下所示：

其中快速排序和堆排序都是標準的內(nèi)存排序算法。

快速排序

快速排序（Quick Sort）是最常見的內(nèi)存排序算法，由 Tony Hoare 在 1959 年發(fā)明。

快速排序的三個步驟：

挑選基準值，從數(shù)據(jù)集中挑選出一個基準元素，一般稱為 Pivot

分割：將所有比 pivot 小的數(shù)據(jù)放到 pivot 之前，將所有比 pivot 大的數(shù)據(jù)放到 pivot 之后

遞歸子序列：遞歸的將小于 pivot 的子序列大于 pivot 的子序列分別進行排序

gpdb 中對于快速排序的實現(xiàn)如下：

代碼位置：https://github.com/greenplum-db/gpdb/blob/main/src/backend/utils/sort/gen_qsort_tuple.pl

堆排序

堆排序也是內(nèi)存中一種常用的排序算法，堆是一種完全二叉樹

最大堆：對于每個節(jié)點，其值大于左右子節(jié)點的值

最小堆：對于每個節(jié)點，其值小于左右子節(jié)點的值

堆排序算法：

建立最大堆，數(shù)組中的最大元素在堆頂

取出堆頂元素，插入到數(shù)組中，更新堆

重復第二步，直到堆大小為 0

原始的數(shù)組的排列：

開始建堆：

進行排序：

gpdb 中也有對堆排序的實現(xiàn)：

代碼位置：https://github.com/greenplum-db/gpdb/blob/main/src/backend/utils/sort/tuplesort.c#L3525

外部歸并排序

基于外存的歸并排序主要分為了兩個階段：

• 分割階段：將原始待排序數(shù)據(jù)分成若干個順串
• 合并階段：將所有的小順串合并為包含所有數(shù)據(jù)的大順串

順串的定義：由于要排序的數(shù)據(jù)集過大，無法全部在內(nèi)存中排序，因此只能選擇部分數(shù)據(jù)在內(nèi)存中排序，將排好序的部分數(shù)據(jù)稱為順串

替換選擇算法

分割階段可以線性掃描一遍數(shù)據(jù)，當達到內(nèi)存大小閾值的時候，在內(nèi)存中排序，生成一個順串。然后再重復的取出原始數(shù)據(jù)到內(nèi)存中排序，生成順串，直到原始數(shù)據(jù)被取完。

這樣生成的順串大小，實際上不會超過內(nèi)存的大小。如果順串越小，在合并的時候，讀取外存的次數(shù)就越多，我們的排序算法的效率就越低。

所以，如何在分割階段 ，盡量生成盡可能大于內(nèi)存容量的順串，減少合并階段讀取外存的數(shù)量？

可以使用替換選擇算法，替換選擇算法借鑒的是掃雪機模型。

想象有一個環(huán)形的跑道，跑道上有積雪，假設最開始時積雪的高度為 h，掃雪機不停地向前鏟雪，同時也有新的雪落在跑道上，新的雪一部分落在了掃雪機的前面，一部分落在了掃雪機的后面。假設雪下的速度和掃雪機鏟雪的速度一致，掃雪機掃了一圈之后，掃雪機前面的高度仍然為 h，后面的高度是 0，這樣就達到了一個動態(tài)的平衡。

掃雪機前方和后面的積雪就是一個從 0 - h 的斜坡，也就是說路面積雪量就是下圖中直角三角形的面積，并且可以計算出掃雪機鏟雪的量就是這個三角形的兩倍。

類比掃雪機模型，跑道上的積雪就是替換選擇算法使用的堆，積雪的量就是內(nèi)存的大小。

輸出當前最小值，生成順串的過程就是鏟雪的過程。順串的大小就是鏟雪量。

新落下的雪就是新的輸入數(shù)據(jù)，由于輸入隨機，如果輸入大于等于剛輸出的元素，則被加入到堆中，即被掃雪車清除。如果輸入小于剛輸出的元素，則相當于新雪下在了掃雪車的后方，本次鏟雪(順串)不包含該元素。

因此，順串的長度就是鏟雪量，也就是內(nèi)存大小(跑道上的積雪)的兩倍。

基于此，替換選擇算法的大致過程如下：

• 初始化階段，將元組讀取到內(nèi)存中，并根據(jù)排序鍵建立最小堆
• 取出堆頂元組，寫到順串文件的緩沖區(qū)，并記錄這個元組的排序鍵是 lastkey
• 讀取新的元組，如果排序鍵大于 lastkey，則插入到堆中，重新調(diào)整堆的順序
• 如果新元組的排序鍵小于 lastkey，則插入到堆的末尾，并將堆的大小減一
• 重復第二步，直至堆的大小變?yōu)?0
• 然后重新建堆，再取出新的元組，重復第二步，生成下一個順串

順串合并
假設順串分布在 K 個文件中，如何高效的比較 K 個文件中的最小值，并將其輸出到外部文件中？
敗者樹算法
輸入每個順串的第一個記錄作為敗者樹的葉子節(jié)點，建立初始化敗者樹。

兩兩相比較，父親節(jié)點存儲了兩個子節(jié)點比較的敗者（節(jié)點較大的值）；勝利者 （較小者）可以參與更高層的比賽。這樣樹的頂端就是當次比較的冠軍（最小者）

調(diào)整敗者樹，當我們把最小者輸入到輸出文件以后，需要從相應的順串取出 一個記錄補上去。補回來的時候，我們就需要調(diào)整敗者樹，我們只需要沿著當前 節(jié)點的父親節(jié)點一直比較到頂端。比較的規(guī)則是與父親節(jié)點比較，勝者可以參與更高層的比較，一直向上，直到根節(jié)點。失敗者留在當前節(jié)點。

第一次比較：

第二次比較：

合并階段如何減少磁盤讀取次數(shù)

多路歸并

兩路歸并，使用兩個輸入文件和兩個輸出文件，每次歸并，順串的長度翻倍，并存儲到輸出文件中。下次歸并，輸出緩沖區(qū)和輸出緩沖區(qū)的位置互換。

下面是一個兩路歸并的例子，每個輸入文件在初始狀態(tài)下有 32 個順串，每次歸并，順串的長度翻倍。

這樣歸并之后，IO 次數(shù)是 64 * 6 = 384 次，每個順串移動了 6 次，有沒有什么更好的辦法，可以使順串的移動次數(shù)更少？

多相歸并

Knuth 5.4.2 D 多相歸并排序算法。

初始化階段，N+1 個緩沖區(qū)，其中 N 個輸入緩沖區(qū)，1 個輸出緩沖區(qū)，每一個輸入緩沖區(qū)包含若干個順串。

從每個輸入緩沖區(qū)選取開頭的順串，組成 N 個順串，并對其進行歸并排序，排序結果寫入輸出緩沖區(qū)。此時每個輸入緩沖區(qū)順串數(shù)減 1，輸出緩沖區(qū)順串數(shù)加 1。

如果任何一個輸入緩沖區(qū)的順串數(shù)都大于 0，重復第二步

如果所有緩沖區(qū)的順串數(shù)和大于 1，選擇順串數(shù)為 0 的輸入緩沖區(qū)作為新的輸出緩沖區(qū)，重復第二步

如果所有緩沖區(qū)的順串數(shù)和為 1，那么這個順串就是排序好的數(shù)據(jù)集，算法結束

TupleSort 代碼邏輯

TupleSort 是排序節(jié)點的核心，算法主要分為了四個階段：
第一階段
初始化 TupleSort，調(diào)用函數(shù) tuplesort_begin_common，生成 Tuplesortstate，Tuplesortstate 用于描述排序的狀態(tài)等信息。
其中 status 字段表示當前狀態(tài)機的信息

狀態(tài)轉換圖：

TupleSortstate 中其他的一些重要字段：

第二階段
插入元組，每次調(diào)用函數(shù) puttuple_common，根據(jù)當前 TupleSortstate 的狀態(tài)，將元組插入到不同的位置

• 對于 TSS_INITIAL 狀態(tài)，會將元組存儲到內(nèi)存的 memtuples 中，如果滿足 TopK 的排序條件，會轉為堆排序算法，狀態(tài)切換為 TSS_BOUNDED
• TSS_BOUNDED 狀態(tài)：插入到堆中
• TSS_BUILDRUNS 狀態(tài)：外排序算法，基于替換選擇算法，如果元組大于等于堆頂元組，插入當前元組到堆，否則是其他的順串，將其放到 memtuples 末尾

第三階段
調(diào)用 tuplesort_performsort 執(zhí)行實際的排序操作，仍然根據(jù)狀態(tài)機，選擇不同的排序策略。

• TSS_INITIAL：所有數(shù)據(jù)都在內(nèi)存中，直接執(zhí)行快速排序，結束后將狀態(tài)設置為 TSS_SORTEDINMEM
• TSS_BOUNDED：所有數(shù)據(jù)仍然在內(nèi)存中，執(zhí)行堆排序，結束后將狀態(tài)設置為 TSS_SORTEDINMEM
• TSS_BUILDRUNS：執(zhí)行多相歸并排序，函數(shù) mergeruns 負責對順串進行歸并

第四階段
負責輸出排序后的元組，在排序完成后，每次調(diào)用 tuplesort_gettuple_common 獲取排序后的元組。
還是會根據(jù)不同的狀態(tài)選擇不同的策略。

• TSS_SORTEDINMEM：元組是在內(nèi)存中排序的，元組本身也在內(nèi)存中，直接從 memtuples 中獲取即可
• TSS_SORTEDONTAPE：元組通過歸并排序完成，存儲在外部文件中，因此元組需要從文件中讀取
• TSS_FINALMERGE：元組存儲在文件中，每個文件有且僅有一個順串，在輸出元組的時候需要進行合并

單鍵排序

gpdb 的排序支持單鍵和多鍵排序兩種，其中單鍵排序基于 TupleSort 接口，多鍵排序基于 TupleSort_mk 接口，排序節(jié)點也是標準的執(zhí)行器三部曲 ExecInitSort、ExecSort、ExecEndSort，但是由于 TupleSort 和 TupleSort_mk 已經(jīng)封裝了完善的排序邏輯，因此三部曲的邏輯就比較簡單了。

ExecInitSort

初始化的時候，調(diào)用 ExecInitSort 方法，主要負責初始化 SortState 結構體。

ExecSort

ExecSort 負責傳遞元組給下層節(jié)點排序，并將排好序的數(shù)據(jù)返回給上層節(jié)點。
ExecSort 的第一次調(diào)用會讀取所有的元組并傳遞給 TupleSort 排序。

/*
* Scan the subplan and feed all the tuples to tuplesort.
*/

for (;;)
        {
            slot = ExecProcNode(outerNode);

            if (TupIsNull(slot))
                break;

            tuplesort_puttupleslot(tuplesortstate, slot);
        }

SIMPLE_FAULT_INJECTOR("execsort_before_sorting");

/*
* Complete the sort.
*/
tuplesort_performsort(tuplesortstate);

后續(xù)每次調(diào)用 ExecSort，都會返回排序后的元組。

SO1_printf("ExecSort: %s\n",
      "retrieving tuple from tuplesort");

 /*
  * Get the first or next tuple from tuplesort. Returns NULL if no more
  * tuples.  Note that we only rely on slot tuple remaining valid until the
  * next fetch from the tuplesort.
  */
 slot = node->ss.ps.ps_ResultTupleSlot;
 (void) tuplesort_gettupleslot(tuplesortstate,
          ScanDirectionIsForward(dir),
          false, slot, NULL);

ExecEndSort

ExecEndSort 的邏輯比較簡單，主要就是清理掃描和排序結果，以及清理外排序的臨時文件。

/* clean out the tuple table */
 ExecClearTuple(node->ss.ss_ScanTupleSlot);

 /* must drop pointer to sort result tuple */
 ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);

 if (node->tuplesortstate != NULL)
 {
  /*
   * Save stats like in ExecSortExplainEnd, so that we can display
   * them later in EXPLAIN ANALYZE.
   */
  tuplesort_finalize_stats(node->tuplesortstate,
         &node->sortstats);
  if (node->ss.ps.instrument)
  {
   node->ss.ps.instrument->workfileCreated = (node->sortstats.spaceType == SORT_SPACE_TYPE_DISK);
   node->ss.ps.instrument->workmemused = node->sortstats.workmemused;
   node->ss.ps.instrument->execmemused = node->sortstats.execmemused;
  }

  tuplesort_end((Tuplesortstate *) node->tuplesortstate);
  node->tuplesortstate = NULL;
 }

多鍵排序

gpdb 中特有的排序方式，針對具有相同前綴的字符串排序的優(yōu)化。

多鍵排序算法又被稱為三路基數(shù)排序，融合了快速排序和基數(shù)排序的排序算法，主要的優(yōu)勢在于對具有相同前綴的字符串進行更高效的排序。

多鍵排序的流程和單鍵排序的三部曲類似，但底層基于 TupleSort_mk 接口。

標準快速排序在處理字符串的時候，平均時間復雜度是 N*logN，當字符串擁有相同的前綴時，快速排序仍然需要花費大量的時間去比較這些字符串的相同前綴，而多鍵排序避免了對前綴的重復比較，只使用必要的非前綴字符確定排序。

在現(xiàn)實世界中，具有相同前綴的字符串的場景還是很多的，例如很多的 URL 都以 http:// 開頭，每個具體的站點都有自己特定的前綴，例如 https://www.baidu.com。

下面是一個多鍵排序的示例：

注意：從 postgres12 開始，已經(jīng)自帶了多鍵排序，因此目前 gpdb 當中已經(jīng)刪除了對應的 tuplesort_mk 的邏輯。