本章目录

第 4 章：排序与分组

4.1 排序

B 树索引可以按索引顺序返回行。当这一顺序与查询的 ORDER BY 要求一致时，PostgreSQL 有时可以省去显式排序：

EXPLAIN (costs off)
SELECT * FROM flights
ORDER BY flight_id;

                QUERY PLAN
------------------------------------------
 Index Scan using flights_pkey on flights
(1 row)

如果访问路径无法提供所需的顺序，PostgreSQL 就需要分两步完成：先获取行，再对它们排序。

EXPLAIN (costs off)
SELECT * FROM flights
ORDER BY status;

        QUERY PLAN
--------------------------
 Sort
   Sort Key: status
   -> Seq Scan on flights
(3 rows)

4.1.1 内存排序

最简单的情况是，待排序数据能够放入 work_mem 为排序操作限定的可用内存中。此时，PostgreSQL 可以在内存中完成排序。EXPLAIN ANALYZE 会显示所使用的排序方法和内存用量：

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 行的 Top-N 排序，而不必对所有行进行完整排序：

EXPLAIN (analyze, timing off, summary off, buffers off)
SELECT *
FROM seats
ORDER BY seat_no
LIMIT 100;

                         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)

查询的估算成本降低了，排序使用的内存也更少。Top-N 堆排序的工作量为 $O(M \log N)$ ，无须对全部 M 行进行完整排序。

4.1.2 外排

如果数据集过大，无法在可用内存中完成排序，PostgreSQL 就会使用外排。

排序器先读取内存能够容纳的一部分输入，对其排序，然后将得到的有序数据段 (run) 写入临时文件。

外排生成有序 run：内存中的数据经快排后写入临时文件；work_mem 与 temp_file_limit 分别约束内存和临时文件空间。

这一过程不断重复，直到全部输入都转换成各自有序的 run。

temp_file_limit 限制的是单个 PostgreSQL 进程在任一时刻使用的临时文件总空间。显式创建的临时表不计入这一限制。

接下来，对这些有序的 run 进行归并。从概念上看，归并过程会跟踪每个输入 run 的下一个候选行，从中选择最小或最大的一行并返回，再将该 run 向前推进一行。实际实现会以带缓冲的块为单位读取数据，而不是逐行读取，以保持较高的 I/O 效率。

外排的归并阶段：从各个有序 run 读取候选行并归并输出，内存缓冲受 work_mem 约束。

如果内存不足以在一轮中归并所有 run，PostgreSQL 就会执行多轮归并：先将若干 run 归并成更大的 run，再继续归并，直到能够生成最终的有序数据流。对于较大的排序操作，EXPLAIN ANALYZE 会显示临时存储的使用情况：

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 给出该排序使用的临时磁盘空间，temp 缓冲区计数则反映临时 I/O。

4.1.3 增量排序

假设查询需要按 $K_1 \ldots K_m \ldots K_n$ 排序，而输入已经按前 m 个键排好序，就没有必要重新对整个数据集排序。PostgreSQL 可以按照预排序前缀 $K_1 \ldots K_m$ 的值，将输入划分成一组组连续的行；每组内这些键的值都相同，只需再按剩余的键 $K_{m+1} \ldots K_n$ 排序。这就是增量排序。

由于每次只对较小的一部分输入排序，增量排序可以降低内存需求，减少溢出到磁盘的可能性。它还可以缩短返回首批结果的等待时间：第一组排好序后，PostgreSQL 就能开始返回行，无须等待全部输入排序完成。代价是识别和处理大量分组会带来额外开销。

增量排序：输入已按 album_id 排序，较大分组只按 name 进一步排序；较小分组合并后按全部字段排序。

PostgreSQL 内部采用两种策略。对于预排序前缀相同的较大分组，可以逐组单独排序；对于较小的分组，则可以先累积起来，再一起进行完整排序，以免逐组处理带来过多开销。

可以通过 enable_incremental_sort 禁用增量排序。

在 bookings.total_amount 上创建索引：

CREATE INDEX ON bookings(total_amount);

然后增大 work_mem，并按 total_amount 和 book_date 排序：

SET work_mem = '8 MB';
EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT *
FROM bookings
ORDER BY total_amount, book_date;

                         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：

SET work_mem = '128 kB';

再次运行查询：

EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT *
FROM bookings
ORDER BY total_amount, book_date;

                         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 也明确显示了它们使用的临时磁盘空间。

恢复参数设置，并删除演示用的索引：

RESET work_mem;
DROP INDEX bookings_total_amount_idx;

4.1.4 构建 B 树

原则上，PostgreSQL 可以从一棵空的 B 树开始，在扫描表的过程中逐条插入索引项，以此构建索引。但对于批量构建索引来说，这种方式效率很低。

实际采用的方式是：先生成索引项，按索引键排序，然后依次填充叶子层，再逐层构建上层节点，直到只剩下根节点。这里使用的排序机制与前面讨论的排序密切相关，但创建索引使用的是 maintenance_work_mem，而不是常规的 work_mem。维护操作相对不频繁，因此为它们分配更大的内存额度通常是合理的。

B 树索引也可以并行构建。工作进程数量的选择方式与并行查询相同，取决于表的大小，但受 max_parallel_maintenance_workers 限制。

并行构建索引时，maintenance_work_mem 适用于整个构建过程，而不是每个工作进程各自拥有一份。

4.2 分组

4.2.1 分组的应用场景

SQL 可以通过 GROUP BY 将行划分为多个组。通常会结合聚合函数，为每个组计算一个结果。窗口函数中的 PARTITION BY 与此有相近之处，但与普通分组不同，窗口函数不会将一个分区中的多行合并成一行结果。

需要消除重复项时，也会隐式涉及分组，例如：DISTINCT、不带 ALL 的 UNION、不带 ALL 的 INTERSECT，以及不带 ALL 的 EXCEPT。PostgreSQL 可以使用不同的物理执行策略来完成分组和去重。

其中两种重要的策略是哈希，以及按分组键的顺序处理数据。规划器会根据估算成本、内存、下层计划节点已经提供的顺序，以及查询的其他特征，在可用方案中进行选择。

4.2.2 哈希聚合

哈希表通过哈希函数，将值映射到数量有限的桶中。查找时需要：

计算哈希值。
使用哈希值的一部分选择一个桶。
检查桶中的条目，通过相等性比较，区分哈希值相同或映射到同一桶的不同值。

如果 load factor 合理，且数据分布均匀，查找的预期耗时近似为常数。分布不均匀或哈希表负载过高，都会增加处理冲突的工作量。

哈希聚合：按 year 的哈希值选择桶，通过相等性比较定位分组，并累加各组的计数。

基于哈希的聚合在执行计划中对应 HashAggregate 节点：

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 会显示内存用量：

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)

4.2.3 对有序数据分组

如果输入行已按分组键排序，去重和分组也可以利用这一顺序。

对有序数据去重和分组：Unique 返回 year 的非重复值，GroupAggregate 返回各个 year 及其出现次数。

Unique 去除相邻的重复项。由于相同的键彼此相邻，它只需将当前值与前一个值比较。

GroupAggregate 节点返回聚合后的数据。图中的例子里，该节点列出 year 字段的非重复值，并统计每个值在数据集中出现的次数。

如果输入已经具有所需的顺序，Unique 或 GroupAggregate 就可能是合适的选择：它们需要的工作内存相对较少，而且可以逐步处理数据流。如果必须先对全部输入排序，哈希聚合的成本往往更低。不过，规划器依据的是实际估算，而不是固定规则。

这些节点会保留分组键的顺序，有时可以直接满足后续 ORDER BY 的要求，无须再次排序。

下面这个 GroupAggregate 的输入顺序直接来自索引：

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：

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 节点。

4.2.4 窗口函数

与普通聚合函数不同，窗口函数为每一行输出计算一个值，而不是将整个组缩减为一行。函数名后面的 OVER 子句定义了一个窗口：它规定对于每一行结果，窗口函数应处理哪一组行。这样的一组行称为 frame。

窗口与 frame：OVER () 的默认 frame 包含整个分区；带 ORDER BY 时，图中 frame 随当前行向后扩展。

OVER () 既没有 PARTITION BY，也没有 ORDER BY。因此，所有行构成一个分区，默认 frame 就是整个分区。

如果窗口定义包含用于指定行顺序的 ORDER BY 子句，默认 frame 会覆盖从第一行到当前行的所有行。

来看一个计算预订金额累计和的例子：

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 提供窗口所需的顺序。该排序可以使用任何适用的排序策略。输入较小时，可以在内存中完成：

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)

输入较大时，可能需要外排：

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。

PARTITION BY 将输入划分为独立分区；左侧各 frame 包含整个分区，右侧带 ORDER BY 的 frame 只在所属分区内扩展。

PARTITION BY 将输入划分成相互独立的行组。对每个组来说，frame 的边界只在该组内部变化。没有另外指定时，frame 占据整个组。

如果窗口定义还包含 ORDER BY，就会按相应的顺序处理行。此时，frame 覆盖从组内第一行到当前行的所有行。

与常规的 GROUP BY 不同，PARTITION BY 始终采用排序方式：所选择的执行计划会让 WindowAgg 接收先按 PARTITION BY 键、再按 ORDER BY 键排好序的行集。即使没有 ORDER BY 子句，也不会使用哈希。