解析 Greenplum 數據庫的排序算法

本文是直播的文字稿，錄播地址：https://www.bilibili.com/video/BV11Y4y1U799

Sort 節點概覽

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

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

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

如果工作內存無法容納所有的元組，則使用基於歸併排序的外排序算法。

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

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

TupleSort

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

r0fwKG

其中快速排序和堆排序都是標準的內存排序算法。

快速排序

快速排序（Quick Sort）是最常見的內存排序算法，由 Tony Hoare 在 1959 年發明。

快速排序的三個步驟：
挑選基準值，從數據集中挑選出一個基準元素，一般稱爲 Pivot
分割：將所有比 pivot 小的數據放到 pivot 之前，將所有比 pivot 大的數據放到 pivot 之後
遞歸子序列：遞歸的將小於 pivot 的子序列大於 pivot 的子序列分別進行排序


gpdb 中對於快速排序的實現如下：

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

堆排序

堆排序也是內存中一種常用的排序算法，堆是一種完全二叉樹
最大堆：對於每個節點，其值大於左右子節點的值
最小堆：對於每個節點，其值小於左右子節點的值

堆排序算法：
建立最大堆，數組中的最大元素在堆頂
取出堆頂元素，插入到數組中，更新堆
重複第二步，直到堆大小爲 0
原始的數組的排列：

開始建堆：

進行排序：

gpdb 中也有對堆排序的實現：

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

外部歸併排序

基於外存的歸併排序主要分爲了兩個階段：

順串的定義：由於要排序的數據集過大，無法全部在內存中排序，因此只能選擇部分數據在內存中排序，將排好序的部分數據稱爲順串

替換選擇算法
分割階段可以線性掃描一遍數據，當達到內存大小閾值的時候，在內存中排序，生成一個順串。然後再重複的取出原始數據到內存中排序，生成順串，直到原始數據被取完。

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

所以，如何在分割階段 ，儘量生成儘可能大於內存容量的順串，減少合併階段讀取外存的數量？

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

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

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

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

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

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

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

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

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

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

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

第一次比較：

第二次比較：

合併階段如何減少磁盤讀取次數
多路歸併
兩路歸併，使用兩個輸入文件和兩個輸出文件，每次歸併，順串的長度翻倍，並存儲到輸出文件中。下次歸併，輸出緩衝區和輸出緩衝區的位置互換。
下面是一個兩路歸併的例子，每個輸入文件在初始狀態下有 32 個順串，每次歸併，順串的長度翻倍。

這樣歸併之後，IO 次數是 64 * 6 = 384 次，每個順串移動了 6 次，有沒有什麼更好的辦法，可以使順串的移動次數更少？
多相歸併
Knuth 5.4.2 D 多相歸併排序算法。
初始化階段，N+1 個緩衝區，其中 N 個輸入緩衝區，1 個輸出緩衝區，每一個輸入緩衝區包含若干個順串。

從每個輸入緩衝區選取開頭的順串，組成 N 個順串，並對其進行歸併排序，排序結果寫入輸出緩衝區。此時每個輸入緩衝區順串數減 1，輸出緩衝區順串數加 1。

如果任何一個輸入緩衝區的順串數都大於 0，重複第二步

如果所有緩衝區的順串數和大於 1，選擇順串數爲 0 的輸入緩衝區作爲新的輸出緩衝區，重複第二步
如果所有緩衝區的順串數和爲 1，那麼這個順串就是排序好的數據集，算法結束

TupleSort 代碼邏輯

TupleSort 是排序節點的核心，算法主要分爲了四個階段：
第一階段
初始化 TupleSort，調用函數 tuplesort_begin_common，生成 Tuplesortstate，Tuplesortstate 用於描述排序的狀態等信息。
其中 status 字段表示當前狀態機的信息

v4SkdO

狀態轉換圖：

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

HNIKKQ

第二階段
插入元組，每次調用函數 puttuple_common，根據當前 TupleSortstate 的狀態，將元組插入到不同的位置

第三階段
調用 tuplesort_performsort 執行實際的排序操作，仍然根據狀態機，選擇不同的排序策略。

第四階段
負責輸出排序後的元組，在排序完成後，每次調用 tuplesort_gettuple_common 獲取排序後的元組。
還是會根據不同的狀態選擇不同的策略。

單鍵排序

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

ExecInitSort

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

hYqtiU

ExecSort

ExecSort 負責傳遞元組給下層節點排序，並將排好序的數據返回給上層節點。
ExecSort 的第一次調用會讀取所有的元組並傳遞給 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);

後續每次調用 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 中特有的排序方式，針對具有相同前綴的字符串排序的優化。

多鍵排序算法又被稱爲三路基數排序，融合了快速排序和基數排序的排序算法，主要的優勢在於對具有相同前綴的字符串進行更高效的排序。

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

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

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

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

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/J76V5fjXhBYnV2B75IiYpQ

猜你喜歡