作者：David Rowley
譯者：閻書利
正文
近年來，PostgreSQL 進(jìn)行了一些優(yōu)化，使排序速度更快。在 PostgreSQL 15 開發(fā)周期（于 2022 年 4 月結(jié)束）中，我和 Ronan Dunklau、Thomas Munro、Heikki Linnakangas 對 PostgreSQL 做出了一些更改，以加快排序的速度。
當(dāng) PostgreSQL 15 于 2022 年底推出時(shí)，排序的每一項(xiàng)優(yōu)化都應(yīng)該是可用的狀態(tài)。
為什么要關(guān)心排序性能？當(dāng)您在 PostgreSQL 上運(yùn)行應(yīng)用程序時(shí)，有幾種情況 PostgreSQL 表示您需要對記錄（也稱為行）進(jìn)行排序。主要用于 ORDER BY 查詢。排序也可以用于：
- 使用 ORDER BY 子句聚合函數(shù)
- GROUP BY 查詢
- 具有包含合并聯(lián)接的計(jì)劃的查詢
- UNION 查詢
- DISTINCT 查詢
- 帶有 PARTITION BY 和/或 ORDER BY 子句的窗口函數(shù)的查詢
如果 PostgreSQL 能夠更快地對記錄進(jìn)行排序，那么使用 sort 的查詢將運(yùn)行得更快。
讓我們探索 PostgreSQL 15 中使排序性能更快的 4 項(xiàng)優(yōu)化：
變化1：對單個(gè)列的排序的優(yōu)化
變化2：使用生成內(nèi)存上下文來減少內(nèi)存消耗
變化3：為常見數(shù)據(jù)類型添加專門的排序例程
變化4：用多路歸并 (k-way merge)代替多階段合并 (Polyphase Merge)算法
變化 1：優(yōu)化對單個(gè)列的排序
PostgreSQL 14 的查詢執(zhí)行器總是會在排序操作期間存儲整個(gè)元組。此處的更改使得 PostgreSQL 15 僅在排序結(jié)果中有單個(gè)列時(shí)存儲 Datum。僅存儲 Datum 意味著不再需要將元組復(fù)制到排序的內(nèi)存中。
優(yōu)化適用于以下查詢：
SELECT col1 FROM tab ORDER BY col1;
而不是
SELECT col1, col2 FROM tab ORDER BY col1;
上述第一個(gè)查詢在實(shí)際中可能很少見。使用單列排序的其中一個(gè)更常見的原因是組合排序半連接 （merge join semi ）和 組合排序反連接 （merge join anti ）。這些很可能出現(xiàn)在包含 EXISTS 或 NOT EXISTS 子句的查詢中。
下圖顯示了通過測試對10,000個(gè)整數(shù)值進(jìn)行排序的性能，僅使用Datum可以幫助存儲多少數(shù)據(jù)。
圖 1：在 PostgreSQL 15 中對單個(gè)列進(jìn)行排序的速度比在 PostgreSQL 14 中快 26%。
有關(guān)詳細(xì)信息，請參閱 https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=91e9e89dc
變化2：使用生成內(nèi)存上下文來減少內(nèi)存消耗
當(dāng) PostgreSQL 存儲記錄以準(zhǔn)備排序時(shí)，它必須將記錄復(fù)制到準(zhǔn)備排序的內(nèi)存區(qū)域中。在 PostgreSQL 14 和更早的版本中，當(dāng)分配內(nèi)存來存儲要排序的記錄時(shí)，使用“aset”內(nèi)存分配器。這些內(nèi)存分配器用于管理 PostgreSQL 中的內(nèi)存。它們充當(dāng) PostgreSQL 和底層操作系統(tǒng)之間的緩沖區(qū)?！癮set”分配器（AllocSet）總是將內(nèi)存分配請求的大小向上取整為 2 的下一個(gè)冪。例如，24 字節(jié)的分配請求變?yōu)?32 字節(jié)，而 600 字節(jié)變?yōu)?1024 字節(jié)。舍入到 2 的下一個(gè)冪，因?yàn)楫?dāng)內(nèi)存被釋放時(shí)，PostgreSQL 希望能夠重用該內(nèi)存以滿足未來的需要。完成向上舍入以便可以根據(jù)分配的大小在空閑列表中跟蹤內(nèi)存。
向上取整到 2 的下一個(gè)冪會導(dǎo)致平均 25% 的內(nèi)存被浪費(fèi)。
通常，PostgreSQL 在排序時(shí)不需要為記錄釋放任何內(nèi)存。正常它只需要在排序完成后立即釋放所有內(nèi)存，并消耗記錄。當(dāng)要排序的數(shù)據(jù)不適合內(nèi)存并且必須溢出到磁盤時(shí)，PostgreSQL 也會立即釋放所有內(nèi)存。因此，對于一般情況，PostgreSQL 永遠(yuǎn)不必釋放單個(gè)記錄，并且內(nèi)存分配大小的四舍五入只會導(dǎo)致內(nèi)存浪費(fèi)。
PostgreSQL 有另一個(gè)名為“generation”的內(nèi)存分配器。這個(gè)generation分配器：
- 從不維護(hù)任何空閑列表
- 從不四舍五入分配大小
- 假設(shè)分配模式是先進(jìn)先出的。
- 當(dāng)不再需要每個(gè)塊上的所有塊時(shí)，依賴于釋放完整塊
因?yàn)?quot;generation" 不會對分配大小進(jìn)行四舍五入，所以 PostgreSQL 可以用更少的內(nèi)存存儲更多的記錄。從 CPU 緩存的角度來看，將 sort 的元組存儲切換為使用生成內(nèi)存上下文而不是 aset 上下文也可以改善這種情況。
這種變化能提高多少性能取決于存儲的元組的寬度。略高于 2 次方的元組大小提高最多。例如，PostgreSQL 14 會將一個(gè) 36 字節(jié)的元組四舍五入為 64 字節(jié)——接近所需內(nèi)存的兩倍。我們可以預(yù)見到，已經(jīng)是 2 次方大小的元組的性能提升最少。
為了顯示這種變化使排序的速度有多快，我們需要測試幾個(gè)不同大小的元組。我所做的是從 1 列開始并測試其性能，然后再添加另一列并重復(fù)。我停在 32 列。每列使用 BIGINT 數(shù)據(jù)類型，每次添加一列時(shí)會消耗額外的 8 個(gè)字節(jié)。
圖 2：圖表顯示 PostgreSQL 15 中內(nèi)存排序的性能提高了 3% 到 44%。
測試結(jié)果表明，PostgreSQL 15 的性能提升了 3% 到 44%，具體取決于元組的寬度。
- 仔細(xì)觀察 PostgreSQL 14 的時(shí)間，您可以看到條形圖呈階梯狀上升。當(dāng)元組大小超過另一個(gè) 2 的冪時(shí)，每一步都對齊。
- 而對于 PostgreSQL 15，您看不到與 Postgres 14 一樣（7 列、15 列和 31 列）查詢時(shí)間明顯更長的“步驟”。相反，在 PostgreSQL 15 中，查詢時(shí)間隨著列數(shù)的增加而逐漸增加。
PostgreSQL 15 不使用生成內(nèi)存上下文進(jìn)行有界排序。例如，帶有 ORDER BY 和 LIMIT N 子句的查詢。此處未使用優(yōu)化的原因是有界排序僅存儲前 N 個(gè)元組。一旦獲取了 N 條記錄，PostgreSQL 將開始丟棄超出范圍的元組。丟棄元組需要釋放內(nèi)存。PostgreSQL 無法提前確定釋放元組的順序。如果生成內(nèi)存上下文用于有界排序，它可能會浪費(fèi)大量內(nèi)存。
有關(guān)詳細(xì)信息，請參閱 https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=40af10b57
變化 3：為常見數(shù)據(jù)類型添加專門的排序例程
使用經(jīng)過調(diào)整的快速排序算法在 PostgreSQL 中完成排序。PostgreSQL 有大量不同的數(shù)據(jù)類型，用戶甚至可以自行擴(kuò)展。每種數(shù)據(jù)類型都有一個(gè)比較函數(shù)，該函數(shù)提供給快速排序算法以在比較 2 個(gè)值時(shí)使用。比較函數(shù)返回負(fù)數(shù)、0 或正數(shù)以說明哪個(gè)值更高或它們是否相等。
使用這個(gè)比較函數(shù)的問題是，要執(zhí)行排序，PostgreSQL 必須多次調(diào)用該函數(shù)。
- 在平均情況下，當(dāng)對 10,000 條記錄進(jìn)行排序時(shí)，PostgreSQL 需要調(diào)用比較函數(shù) O(n log2 n) 次。也就是大約 13.2 萬次。
- 對 100 萬條記錄進(jìn)行排序時(shí)，平均比較次數(shù)約為 2000 萬。
PostgreSQL 是用 C 編程語言編寫的——雖然 C 函數(shù)調(diào)用開銷很低，但 C 函數(shù)調(diào)用不是免費(fèi)的。多次調(diào)用函數(shù)會產(chǎn)生明顯的開銷，尤其是在和它自己原本開銷很低的情況比較更為明顯。
此處所做的更改添加了一組新的快速排序函數(shù)，這些函數(shù)適合一些常見的數(shù)據(jù)類型。這些快速排序函數(shù)具有內(nèi)聯(lián)編譯的比較函數(shù)，以消除函數(shù)調(diào)用開銷。
如果您想檢查您在 PostgreSQL 15 中排序的數(shù)據(jù)類型是否使用這些新的快速排序函數(shù)之一，您可以執(zhí)行以下操作：
set client_min_messages TO 'debug1';
并運(yùn)行您的 SQL 查詢：
explain analyze select x from test order by x;
如果您的調(diào)試消息顯示：
- qsort_tuple_unsigned
- qsort_tuple_signed
- qsort_tuple_int32
那么你很幸運(yùn)。如果調(diào)試消息顯示其他內(nèi)容，則排序使用原始（較慢）快速排序功能。
添加的 3 個(gè)專業(yè)化快速排序不僅僅涵蓋整數(shù)類型。這些新到 PostgreSQL 15 的函數(shù)還涵蓋了時(shí)間戳和所有使用縮寫鍵的數(shù)據(jù)類型，其中包括使用 C 排序規(guī)則的 TEXT 類型。
讓我們看一下排序?qū)I(yè)化函數(shù)帶來的性能提升。我們可以通過在查詢中添加 LIMIT 子句來欺騙 PostgreSQL 的執(zhí)行程序，使其不應(yīng)用變化 2 的優(yōu)化。
圖 3：圖表顯示 PostgreSQL 15 的內(nèi)存排序性能提高了 4% 到 6%。
在這里我們可以看到，在這種小規(guī)模排序中，性能確實(shí)會隨著排序的更多行而提高。這是符合預(yù)期的，因?yàn)榕判驅(qū)I(yè)化這個(gè)更改減少了排序期間比較元組的常數(shù)因子。平均而言，對更多記錄進(jìn)行排序需要對每條記錄進(jìn)行更多比較。因此，我們可以看到大量記錄帶來更大的節(jié)省。這些加速僅適用于 CPU 緩存效果由于更頻繁的 CPU 緩存未命中而導(dǎo)致性能再次下降之前。
有關(guān)詳細(xì)信息，請參閱 https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=697492434
變化4：用多路歸并 (k-way merge)代替多階段合并 (Polyphase Merge)算法
最后的變化是針對work_mem明顯超過大小的更大規(guī)模的排序。合并單個(gè)磁帶的算法已更改為使用多路歸并 (k-way merge)。當(dāng)磁帶數(shù)量很大時(shí)，所需的 I/O 比原來的多階段合并 (Polyphase Merge)要少。
讓我們做一些基準(zhǔn)測試，看看合并算法的變化如何影響 PostgreSQL 15 的性能。
圖 4：圖表顯示 PostgreSQL 15 對大型排序的執(zhí)行速度提高了 43%。
上面的圖 4 向我們展示了 PostgreSQL 15 在具有非常小的work_mem.?隨著work_mem設(shè)置的增加，性能差距縮小。使用最大值work_mem(16GB) 時(shí)，排序不再溢出到磁盤。我們還可以看到work_mem設(shè)置為 64MB 的測試導(dǎo)致查詢運(yùn)行更慢。這需要在 PostgreSQL 15 發(fā)布之前進(jìn)行一些進(jìn)一步的調(diào)查。
有關(guān)詳細(xì)信息，請參閱 https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=65014000b
Postgres 中sort未來的工作
我們很可能會在未來的 PostgreSQL 版本中看到排序函數(shù)專業(yè)化領(lǐng)域的進(jìn)一步改進(jìn)。例如，當(dāng) PostgreSQL 在排序期間比較兩個(gè)值時(shí)，它需要檢查 NULL。這對于幾個(gè)值來說花銷是很小的，但請記住，這種比較必須進(jìn)行多次。比較的成本迅速增加。如果 PostgreSQL 在存儲記錄時(shí)通過檢查它們已經(jīng)知道不存在 NULL，那么在比較兩條記錄以進(jìn)行排序時(shí)就不需要檢查 NULL。許多列都有 NOT NULL 約束，因此這種情況應(yīng)該很常見。PostgreSQL 也可以使用 NOT NULL 約束作為證明，這樣它就不必在運(yùn)行時(shí)檢查 NULL。
為什么不立即嘗試 PostgreSQL 15，看看這些變化如何影響您的負(fù)載？
我在減少排序的內(nèi)存消耗時(shí)運(yùn)行的第一個(gè)測試將性能提高了 371%。這是由于存儲要排序的記錄所需的內(nèi)存消耗減少，不再超出我的work_mem設(shè)置。以前排序溢出到磁盤，更改后整個(gè)排序在內(nèi)存中完成。
在 PostgreSQL 上運(yùn)行的許多 SQL 查詢都需要對記錄進(jìn)行排序。在 PostgreSQL 15 中使排序速度更快可能會使您的許多查詢比在 PG 14 上更快。
如果您想在 PostgreSQL 15 中提供排序性能，請嘗試：
- PostgreSQL 15的發(fā)行說明現(xiàn)已上線
- PostgreSQL 15 beta 1 于 2022 年 5 月 19日發(fā)布（隨后幾個(gè)月將發(fā)布“候選發(fā)布”版本）
- PostgreSQL 15 的最終版本將于 2022 年 10 月/11 月左右發(fā)布
- 您可以在此處下載 PostgreSQL 15 beta 1
