原文地址：
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：
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：
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：
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