# 排序与分组
> 了解 PostgreSQL 18 中的内存排序、外部排序和增量排序、哈希聚合、有序数据分组以及窗口帧。
---
LLMS 索引： [llms.txt](/llms.txt)
---
## 1. 排序 {#qpt-section-4-1}
B-树索引可以按索引顺序产生行。当这个顺序与查询的 `ORDER BY` 相匹配时，PostgreSQL 有时可以避免显式排序：
```sql
EXPLAIN (costs off)
SELECT * FROM flights
ORDER BY flight_id;
QUERY PLAN
------------------------------------------
Index Scan using flights_pkey on flights
(1 row)
```
如果访问路径无法提供所需的排序，PostgreSQL 就需要两个独立的步骤：获取行，再对行排序。
```sql
EXPLAIN (costs off)
SELECT * FROM flights
ORDER BY status;
QUERY PLAN
--------------------------
Sort
Sort Key: status
-> Seq Scan on flights
(3 rows)
```
### 内存排序 {#qpt-p71-in-memory-sort}
最简单的情况是，要排序的数据能够放进 `work_mem` 为排序操作提供的内存中。此时 PostgreSQL 可以在内存中完成排序。`EXPLAIN ANALYZE` 会显示排序方法和使用的内存量：
```sql
EXPLAIN (analyze, timing off, summary off, buffers off)
SELECT *
FROM seats
ORDER BY seat_no;
QUERY PLAN
------------------------------------------------------------
Sort (cost=121.13..125.48 rows=1741 width=15) (actual ...
Sort Key: seat_no
Sort Method: quicksort Memory: 103kB
-> Seq Scan on seats (cost=0.00..27.41 rows=1741 wid...
(4 rows)
```
普通的 `Sort` 节点必须读取并排序完输入后才能返回第一行。因此，它的启动代价包括读取完整输入的代价。对于比较排序，典型的工作量按 \\(O(M \log M)\\) 的量级增长，其中 M 是输入行数。
如果查询只需要排序结果中的前 N 行，例如因为使用了 `LIMIT`，PostgreSQL 可以使用有界的前 N 排序，而不必完整排序每一行：
```sql
EXPLAIN (analyze, timing off, summary off, buffers off)
SELECT *
FROM seats
ORDER BY seat_no
LIMIT 100;
```
```text
QUERY PLAN
------------------------------------------------------------
Limit (cost=93.95..94.20 rows=100 width=15) (actual ro...
-> Sort (cost=93.95..98.30 rows=1741 width=15) (actu...
Sort Key: seat_no
Sort Method: top-N heapsort Memory: 30kB
-> Seq Scan on seats (cost=0.00..27.41 rows=1741...
(5 rows)
```
估计的查询代价更低，排序使用的内存也更少。前 N 堆排序的工作量按 \\(O(M \log N)\\) 的量级增长，而不是完整排序全部 M 行。
### 外部排序 {#qpt-p72-external-sort}
如果数据集过大，无法在可用内存中完成排序，PostgreSQL 就会使用外部排序。
排序器会在内存所能处理的范围内读取尽可能多的输入，将这部分数据排序，然后把排好序的**有序段**（run）写入临时文件。
{#qpt-fig-4-1 num="4.1" caption="外部排序：写入有序段" .book-original-figure .d-flex .flex-column .align-items-center width=413 height=268}
这个过程会重复进行，直到所有输入都被转换为各自有序的有序段。
`temp_file_limit` 限制 PostgreSQL 进程所属临时文件在任一时刻使用的总空间。显式临时表不计入这个限制。
然后合并这些有序段。从概念上看，归并过程会跟踪每个输入有序段的下一个候选值，选择其中最小或最大的一个，将它返回，然后推进对应的有序段。实际实现会以带缓冲的块读取数据，而不是逐行读取，这样可以保持 I/O 效率。
{#qpt-fig-4-2 num="4.2" caption="外部排序：合并有序段" .book-original-figure .d-flex .flex-column .align-items-center width=280 height=268}
如果内存不足以在一趟中合并所有有序段，PostgreSQL 会执行多趟归并：先把多个有序段分组并合并成更大的有序段，再继续合并，直到能够产生最终的有序流。大型排序会在 `EXPLAIN ANALYZE` 中显示临时存储的使用情况：
```sql
EXPLAIN (analyze, timing off, summary off)
SELECT *
FROM bookings
ORDER BY total_amount;
QUERY PLAN
------------------------------------------------------------
Sort (cost=406880.90..413097.68 rows=2486710 width=21)...
Sort Key: total_amount
Sort Method: external merge Disk: 78176kB
Buffers: shared read=15856, temp read=19539
written=19578
-> Seq Scan on bookings (cost=0.00..40723.10 rows=24...
Buffers: shared read=15856
Planning:
Buffers: shared hit=34 read=2 dirtied=1
(9 rows)
```
`Sort Method: external merge` 告诉我们排序溢出到了磁盘。`Disk` 值报告排序使用的临时磁盘空间，而临时缓冲区计数器显示临时 I/O。
### 增量排序 {#qpt-p74-incremental-sort}
假设查询要求按 \\(K_1,\ldots,K_m,\ldots,K_n\\) 这些键排序，但输入已经按前 m 个键排好序。此时无需再次对整个数据集排序。PostgreSQL 可以把输入划分为连续的组，这些组在预排序前缀 \\(K_1,\ldots,K_m\\) 上具有相同值，然后只按剩余键 \\(K_{m+1},\ldots,K_n\\) 对这些组排序。这就是**增量排序**。
增量排序可以减少内存需求和溢出到磁盘的可能性，因为每次排序只处理输入中较小的一部分。它还具有延迟优势：第一个组完成排序后，PostgreSQL 就可以开始返回行，不必等待整个输入排序完成。
{#qpt-fig-4-3 num="4.3" caption="增量排序" .book-original-figure .d-flex .flex-column .align-items-center width=422 height=244}
代价是识别和处理大量组会带来额外开销。
PostgreSQL 在内部使用两种策略。共享相同预排序前缀的较大组可以分别排序。较小的组可以先累积起来，再一起进行完整排序，以避免每个组都产生过高的处理开销。
可以使用 `enable_incremental_sort` 禁用增量排序。
在 `bookings.total_amount` 上创建一个索引：
```sql
CREATE INDEX ON bookings(total_amount);
```
现在增大 `work_mem`，并按 `total_amount` 和 `book_date` 排序：
```sql
SET work_mem = '8 MB';
EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT *
FROM bookings
ORDER BY total_amount, book_date;
```
```text
QUERY PLAN
------------------------------------------------------------
Incremental Sort (actual rows=2486710.00 loops=1)
Sort Key: total_amount, book_date
Presorted Key: total_amount
Full-sort Groups: 3132 Sort Method: quicksort
Average Memory: 27kB Peak Memory: 27kB
Pre-sorted Groups: 2449 Sort Method: quicksort
Average Memory: 6442kB Peak Memory: 6464kB
-> Index Scan using bookings_total_amount_idx on book...
Index Searches: 1
Planning Time: 0.128 ms
Execution Time: 934.215 ms
(11 rows)
```
索引扫描已经提供了按 `total_amount` 排序的行，这一点由 `Presorted Key` 表示。`Incremental Sort` 只需要建立按 `book_date` 排序的剩余顺序。
`Pre-sorted Groups` 描述使用已有 `total_amount` 顺序处理、再按 `book_date` 进一步排序的较大组。`Full-sort Groups` 描述合并后作为完整组排序的较小组。
在这个例子中，两类组都完全放入内存，并使用快速排序。
现在减少 `work_mem`：
```sql
SET work_mem = '128 kB';
```
再次运行查询：
```sql
EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT *
FROM bookings
ORDER BY total_amount, book_date;
```
```text
QUERY PLAN
------------------------------------------------------------
Incremental Sort (actual rows=2486710.00 loops=1)
Sort Key: total_amount, book_date
Presorted Key: total_amount
Full-sort Groups: 3132 Sort Method: quicksort
Average Memory: 27kB Peak Memory: 27kB
Pre-sorted Groups: 2449 Sort Method: external merge
Average Disk: 2662kB Peak Disk: 2672kB
-> Index Scan using bookings_total_amount_idx on book...
Index Searches: 1
Planning Time: 0.044 ms
Execution Time: 912.199 ms
(11 rows)
```
内存减少后，较大的预排序组现在使用外部归并处理，`EXPLAIN` 也明确报告了它们使用的临时磁盘空间。
恢复设置并移除演示索引：
```text
RESET work_mem;
DROP INDEX bookings_total_amount_idx;
```
### 构建 B-树 {#qpt-p77-building-a-b-tree}
原则上，PostgreSQL 可以从一棵空树开始，在扫描表时逐个插入索引项，以此构建 B-树索引。对于批量索引构建，这种方式效率很低。
相反，PostgreSQL 会先生成索引项，按索引键对它们排序，再依次填充叶级，随后逐层构建上层，直到只剩下根节点。这里使用的排序机制与上面讨论的排序密切相关，但创建索引使用的是 `maintenance_work_mem`，而不是普通的 `work_mem`。维护操作相对不频繁，因此通常可以为它们提供更大的内存预算。
B-树索引构建也可以并行运行。工作进程数量的选择方式与并行查询相同，会根据表的大小决定，但受 `max_parallel_maintenance_workers` 限制。
对于并行索引构建，`maintenance_work_mem` 适用于整个构建过程，而不是分别适用于每个工作进程。
## 2. 分组 {#qpt-section-4-2}
### 分组出现在哪里 {#qpt-p78-where-grouping-appears}
SQL 可以使用 `GROUP BY` 把行划分为多个组。聚合函数通常与这些组一起使用，为每个组计算一个结果。窗口函数通过 `PARTITION BY` 也有相关概念，但与普通分组不同，窗口函数不会把分区中的行压缩成一行结果。
当必须删除重复项时，也会隐式出现分组，例如使用：`DISTINCT`；不带 `ALL` 的 `UNION`；不带 `ALL` 的 `INTERSECT`；不带 `ALL` 的 `EXCEPT`。PostgreSQL 可以使用不同的物理策略执行分组和重复消除。
其中两个重要策略是哈希，以及按分组键顺序处理数据。规划器会根据估计代价、内存、下层计划节点已经提供的排序以及查询的其他属性，在可用方案中进行选择。
### 哈希聚合 {#qpt-p79-hash-aggregation}
哈希表使用哈希函数把值映射到有限数量的桶中。查找时：
1. 计算哈希值。
2. 使用哈希值的一部分选择一个桶。
3. 检查桶中的条目，并使用相等比较来区分哈希值或桶分配发生冲突的值。
在负载因子合理且分布良好的情况下，查找预计只需要近似常数时间。分布不佳或哈希表过载会增加处理冲突的工作量。
{#qpt-fig-4-4 num="4.4" caption="哈希聚合" .book-original-figure .d-flex .flex-column .align-items-center width=394 height=244}
基于哈希的聚合使用的计划节点是 `HashAggregate`：
```sql
EXPLAIN
SELECT airplane_code, count(*)
FROM seats
GROUP BY airplane_code;
QUERY PLAN
------------------------------------------------------------
HashAggregate (cost=36.12..36.20 rows=8 width=12)
Group Key: airplane_code
-> Seq Scan on seats (cost=0.00..27.41 rows=1741 wid...
(3 rows)
```
启动代价很高，因为 `HashAggregate` 必须读取输入并构建聚合状态，然后才能产生最终的分组。
`EXPLAIN ANALYZE` 会显示内存使用情况：
```sql
EXPLAIN (analyze, timing off, costs off, buffers off)
SELECT airplane_code, count(*)
FROM seats
GROUP BY airplane_code;
QUERY PLAN
------------------------------------------------------
HashAggregate (actual rows=8.00 loops=1)
Group Key: airplane_code
Batches: 1 Memory Usage: 32kB
-> Seq Scan on seats (actual rows=1741.00 loops=1)
Planning Time: 0.021 ms
Execution Time: 0.424 ms
(6 rows)
```
### 对有序数据分组 {#qpt-p80-grouping-sorted-data}
重复消除和分组也可以利用按分组键顺序到达的行。
{#qpt-fig-4-5 num="4.5" caption="对有序数据分组" .book-original-figure .d-flex .flex-column .align-items-center width=403 height=241}
`Unique` 会删除相邻的重复项。由于相等的键彼此相邻，它只需把当前值与前一个值比较。
`GroupAggregate` 节点返回聚合数据。在图中的例子里，该节点建立 `year` 字段的非重复值列表，并计算数据集中每个值出现的次数。
当输入已经具有所需的顺序时，`Unique` 或 `GroupAggregate` 可能很有吸引力，因为它们只需要相对少量的工作内存，并且可以增量处理数据流。当输入必须先完整排序时，哈希聚合往往代价更低，不过规划器会根据实际估计值做决定，而不是遵循固定规则。
这些节点会保留分组键的顺序，因此有时可以在后续 `ORDER BY` 中避免再次排序。
下面是一个输入顺序直接来自索引的 `GroupAggregate`：
```sql
EXPLAIN (costs off)
SELECT ticket_no, count(ticket_no)
FROM segments
GROUP BY ticket_no;
QUERY PLAN
------------------------------------------------------
GroupAggregate
Group Key: ticket_no
-> Index Only Scan using segments_pkey on segments
(3 rows)
```
`DISTINCT` 查询可以使用 `Unique`：
```sql
EXPLAIN (costs off)
SELECT DISTINCT ticket_no
FROM segments
ORDER BY ticket_no;
QUERY PLAN
------------------------------------------------------
Unique
-> Index Only Scan using segments_pkey on segments
(2 rows)
```
索引已经按 `ORDER BY` 所需的顺序产生 `ticket_no`，而 `Unique` 会保留这个顺序，因此不需要额外的 `Sort` 节点。
### 窗口函数 {#qpt-p82-window-functions}
与普通聚合函数不同，窗口函数为每个输出行计算一个值，而不是把一个组缩减为一行。在函数名之后，`OVER` 子句指定一个**窗口**：一条规则，用来确定对于每个结果行，窗口函数应处理哪一组行。这样的行集称为**窗口帧**（frame）。
{#qpt-fig-4-6 num="4.6" caption="有序与无序时的窗口帧" .book-original-figure .d-flex .flex-column .align-items-center width=338 height=215}
使用 `OVER ()` 时，没有 `PARTITION BY`，也没有 `ORDER BY`。因此这里只有一个包含所有行的分区，默认帧就是整个分区。
如果窗口定义包含用于排列行的 `ORDER BY` 子句，默认窗口帧会覆盖从第一行到当前行的行。
考虑一个预订金额的累计和：
```sql
EXPLAIN
SELECT *, sum(total_amount) OVER (ORDER BY book_date)
FROM bookings;
QUERY PLAN
------------------------------------------------------------
WindowAgg (cost=406880.92..450398.33 rows=2486710 widt...
Window: w1 AS (ORDER BY book_date)
-> Sort (cost=406880.90..413097.68 rows=2486710 widt...
Sort Key: book_date
-> Seq Scan on bookings (cost=0.00..40723.10 row...
(5 rows)
```
窗口函数由 `WindowAgg` 计算。在这里，它的子节点 `Sort` 建立窗口所需的顺序。排序可以使用任何合适的排序策略。较小的输入可以留在内存中：
```sql
EXPLAIN (analyze, timing off, summary off, buffers off)
SELECT *, count(*) OVER (ORDER BY seat_no)
FROM seats;
QUERY PLAN
------------------------------------------------------------
WindowAgg (cost=121.18..151.59 rows=1741 width=23) (ac...
Window: w1 AS (ORDER BY seat_no)
Storage: Memory Maximum Storage: 17kB
-> Sort (cost=121.13..125.48 rows=1741 width=15) (ac...
Sort Key: seat_no
Sort Method: quicksort Memory: 103kB
-> Seq Scan on seats (cost=0.00..27.41 rows=1741...
(7 rows)
```
较大的输入可能需要外部排序：
```sql
EXPLAIN (analyze, timing off, summary off, buffers off)
SELECT *, sum(total_amount) OVER (ORDER BY book_date)
FROM bookings;
QUERY PLAN
------------------------------------------------------------
WindowAgg (cost=406880.92..450398.33 rows=2486710 widt...
Window: w1 AS (ORDER BY book_date)
Storage: Memory Maximum Storage: 17kB
-> Sort (cost=406880.90..413097.68 rows=2486710 widt...
Sort Key: book_date
Sort Method: external merge Disk: 75760kB
-> Seq Scan on bookings (cost=0.00..40723.10 row...
(7 rows)
```
对于使用内部行存储的节点，例如 `WindowAgg`、`CTE Scan` 或 `Recursive Union`，`Storage` 行显示使用的最大存储量及其类型：当数据能放入内存时为 `Memory`，使用临时文件时为 `Disk`。
{#qpt-fig-4-7 num="4.7" caption="分区中的窗口帧" .book-original-figure .d-flex .flex-column .align-items-center width=418 height=214}
`PARTITION BY` 把输入划分为相互独立的行组。对于每个组，窗口帧的边界都会在该组内部变化。如果没有另行指定，窗口帧覆盖整个组。
如果窗口定义还包含 `ORDER BY`，行会按相应顺序处理。此时，窗口帧覆盖从第一行到当前行的行。
与普通的 `GROUP BY` 不同，`PARTITION BY` 总是使用排序：计划会保证 `WindowAgg` 节点接收到的行，先按 `PARTITION BY` 键排序，再按 `ORDER BY` 键排序。即使没有 `ORDER BY` 子句，也不会使用哈希。