Sort 節(jié)點(diǎn)概覽

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

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

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

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

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

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

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

此外，Group By，Distinct 等 sql 關(guān)鍵字也和排序息息相關(guān)。

TupleSort

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

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

快速排序

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

快速排序的三個步驟：

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

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

遞歸子序列：遞歸的將小于 pivot 的子序列大于 pivot 的子序列分別進(jìn)行排序

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

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

堆排序

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

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

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

堆排序算法：

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

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

重復(fù)第二步，直到堆大小為 0

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

開始建堆：

進(jìn)行排序：

gpdb 中也有對堆排序的實(shí)現(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)存中排序，因此只能選擇部分?jǐn)?shù)據(jù)在內(nèi)存中排序，將排好序的部分?jǐn)?shù)據(jù)稱為順串

替換選擇算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第一次比較：

第二次比較：

合并階段如何減少磁盤讀取次數(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 個順串，并對其進(jìn)行歸并排序，排序結(jié)果寫入輸出緩沖區(qū)。此時每個輸入緩沖區(qū)順串?dāng)?shù)減 1，輸出緩沖區(qū)順串?dāng)?shù)加 1。

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

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

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

TupleSort 代碼邏輯

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

狀態(tài)轉(zhuǎn)換圖：

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

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

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

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

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

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

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

單鍵排序

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

ExecInitSort

初始化的時候，調(diào)用 ExecInitSort 方法，主要負(fù)責(zé)初始化 SortState 結(jié)構(gòu)體。

ExecSort

ExecSort 負(fù)責(zé)傳遞元組給下層節(jié)點(diǎn)排序，并將排好序的數(shù)據(jù)返回給上層節(jié)點(diǎn)。
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 的邏輯比較簡單，主要就是清理掃描和排序結(jié)果，以及清理外排序的臨時文件。

/* 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)勢在于對具有相同前綴的字符串進(jìn)行更高效的排序。

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

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

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

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

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