PG15加速排序性能
介紹
近年來，PG對排序進行了一些改進。PG15的開發周期中，我和Ronan、Dunklau、Thomas Munro、Heikki Linnakangas對PG做了一些更改以加快排序速度。當PG15于2022年底推出時，排序的每一項改進都應該可用。
排序主要用于ORDER BY查詢，也可用于：
1) 使用ORDER BY子句聚合函數
2) GROUP BY查詢
3) 具有包含merge join計劃的查詢
4) UNION查詢
5) Distinct查詢
6) 帶有PARITION BY和/或ORDER BY子句的窗口函數的查詢
如果PG能夠更快地對記錄進行排序，那么使用排序的查詢將運行的更快。讓我們探索PG15中排序性能改進的4項：改進對單列的排序；使用generation memory context減小內存消耗；對于常見數據類型添加專門的排序routine；用k-way merge替代polyphase合并算法。
1、改進單列排序性能
PG14的查詢執行器在Sort算子執行時，總會存儲整個tuple。Sort算子的結果僅一列時PG15僅存儲一個Datum，意味著tuple不必再拷貝到sort的內存。對應的場景是：
SELECT col1 FROM tab ORDER BY col1;
而不是：
SELECT col1, col2 FROM tab ORDER BY col1;
第一個查詢在生產環境中很少見。使用單列排序的更常見的是merge semi和anti join。這些很可能出現在包含EXISTS或NOT EXISTS子句的查詢中。下圖測試了10,000行整數值排序性能，僅存儲Datum性能提升很明顯：PG15比PG14快近26%。
詳細信息參考commit：
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=91e9e89dc
2、使用generation memory context減小內存消耗
當PG存儲記錄準備排序時，必須將記錄復制到準備排序的內存區域中。PG14及更早版本中，使用“aset”內存分配器分配內存來存儲排序的記錄。這些內存分配器用于管理 PG中的內存。他們充當PG和底層操作系統之間的緩沖區。“aset”分配器總是將內存分配請求的大小向上取整為2的下一個冪。例如24字節的分配請求變成32字節，而600字節的變成1024字節。舍入到2的下一個冪，因為當釋放內存時，PG希望能夠重用該內存以滿足未來的需要。完成向上舍入以便根據分配的大小在空閑列表中跟蹤內存。
向上取整到2的下一個冪會導致平均浪費25%的內存。
通常PG在排序時不需要為記錄釋放任何內存。只需要在排序完成后立即釋放所有內存、以及記錄消耗的內存。當排序數據量很大需要溢出到磁盤時，PG會立即釋放所有內存。因此對于一般情況，PG不必釋放單獨記錄，并且內存分配大小的四舍五入只會導致內存浪費。
PG有另一個“generation”的內存分配器，該分配器：不維護任何空閑鏈表；不四舍五入分配大小；假設分配模式是先進先出的；當每個block的所有chunk不再需要時，依賴于釋放完整的blocks。
因為“generation”不四舍五入的分配大小，PG可以使用更少的內存存儲更多記錄。從 CPU 緩存的角度來看，將 sort 的元組存儲切換為使用生成內存上下文而不是 aset 上下文也可以改善這種情況。
這種變化能提高多少性能取決于存儲的元組的寬度。略高于 2 次方的元組大小提高最多。例如，PG 14 會將一個 36 字節的元組四舍五入為 64 字節——接近所需內存的兩倍。我們可以預期，已經是 2 次方大小的元組的性能提升最少。
為了顯示性能提升情況，我們需要測試幾個不同大小的元組。我所做的是從 1 列開始并測試其性能，然后再添加另一列并重復。我停在 32 列。每列使用 BIGINT 數據類型，每次添加一列時會消耗額外的 8 個字節。
內存排序的性能提升了3%到44%。具體取決于元組的寬度。
1) 仔細觀察 PG 14 時間，您可以看到條形圖呈階梯狀上升。當元組大小超過另一個 2 的冪時，每一步都對齊。
2) 而對于 PG 15，您看不到與 Postgres 14 一樣（7 列、15 列和 31 列）查詢時間明顯更長的“步驟”。相反，在 PG 15 中，查詢時間隨著列數的增加而逐漸增加。
PG 15 不使用generation內存上下文進行有界排序。例如，帶有 ORDER BY 和 LIMIT N 子句的查詢。此處未使用優化的原因是有界排序僅存儲前 N 個元組。一旦獲取了 N 條記錄，PG 將開始丟棄超出范圍的元組。丟棄元組需要釋放內存。PG 無法提前確定釋放元組的順序。如果generation內存上下文用于有界排序，它可能會浪費大量內存。
詳細信息參考：
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=40af10b57
3、為常見的數據類型添加專門的排序routine
PG使用一種改進的快速排序算法進行排序。PG 有大量不同的數據類型，用戶甚至可以自行擴展。每種數據類型都有一個比較函數，該函數提供給快速排序算法以在比較 2 個值時使用。比較函數返回負數、0 或正數以說明哪個值更高或它們是否相等。
使用這個比較函數的問題是，要執行排序，PG 必須多次調用該函數。
1) 在平均情況下，當對 10,000 條記錄進行排序時，PG 需要調用比較函數 O(n log2 n) 次。也就是大約 13.2 萬次。
2) 對 100 萬條記錄進行排序時，平均比較次數約為 2000 萬。
PG 是用 C 編程語言編寫的——雖然 C 函數調用開銷很低，但 C 函數調用不是免費的。多次調用函數會產生明顯的開銷，尤其是在比較本身很便宜的情況下。
此處所做的更改添加了一組新的快速排序函數，這些函數適合一些常見的數據類型。這些快速排序函數具有內聯編譯的比較函數，以消除函數調用開銷。
如果您想檢查您在 PG 15 中排序的數據類型是否使用這些新的快速排序函數之一，您可以執行以下操作：
set client_min_messages TO 'debug1';
并執行SQL：
explain analyze select x from test order by x;
如果您的調試消息顯示：
1) qsort_tuple_unsigned
2) qsort_tuple_signed
3) qsort_tuple_int32
那么你很幸運。如果調試消息顯示其他內容，則排序使用原始（較慢）快速排序函數。
添加的 3 個快速排序特化不僅僅涵蓋整數類型。這些新到 PG 15 的函數還涵蓋了時間戳和所有使用縮寫鍵的數據類型，其中包括使用 C 排序規則的 TEXT 類型。
讓我們看一下排序專業化函數帶來的性能提升。我們可以通過在查詢中添加 LIMIT 子句來欺騙 PG 的執行程序，使其不應用該優化。
性能提升4%-6%。在這里我們可以看到，在這種小規模排序中，性能確實會隨著排序的更多行而提高。這是預期的，因為排序專業化更改減少了排序期間比較元組的常數因子。平均而言，對更多記錄進行排序需要對每條記錄進行更多比較。因此，我們看到更多記錄帶來更大的節省。這些加速僅適用于 CPU 緩存效果由于更頻繁的 CPU 緩存未命中而導致性能再次下降之前。
詳細請查詢commit：
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=697492434
4、用k-way merge替代polyphase合并算法
最后的變化是針對work_mem明顯超過大小的更大規模的排序。合并單個磁帶的算法已更改為使用k 路合并。當磁帶數量很大時，所需的 I/O 比原來的多相合并算法要少。
對大型排序的執行速度提升了近43%。上面的圖 4 向我們展示了 具有非常小的work_mem進行大量排序時，PG 15 比PG14具有更高性能。 隨著work_mem設置的增加，性能差距縮小。使用最大值work_mem(16GB) 時，排序不再溢出到磁盤。我們還可以看到work_mem設置為 64MB 的測試導致查詢運行更慢。這需要在 PG 15 發布之前進行一些進一步的調查。
詳細查看commit：
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=65014000b
PG中排序的未來工作
我們很可能會在未來的 PG 版本中看到排序函數專業化領域的進一步改進。例如，當 PG 在排序期間比較兩個值時，它需要檢查 NULL。這對于幾個值來說是相當便宜的，但請記住，這種比較必須進行多次。比較的成本迅速增加。如果 PG 在存儲記錄時通過檢查它們已經知道不存在 NULL，那么在比較兩條記錄以進行排序時就不需要檢查 NULL。許多列都有 NOT NULL 約束，因此這種情況應該很常見。PG 也可以使用 NOT NULL 約束作為證明，這樣它就不必在運行時檢查 NULL。
原文
https://techcommunity.microsoft.com/t5/azure-database-for-postgresql/speeding-up-sort-performance-in-postgres-15/ba-p/3396953
