# 排序与合并
LLMS 索引： [llms.txt](/zh18/llms.txt)
---
## 23.1. 归并连接 {#internal-ru-section-23-1}
合并连接适用于按连接键排序的数据集，并返回同样已排序的结果。输入数据集可能由于索引扫描而已经排序，或者可以显式排序[^internal-ru-484-1]。
### 归并排序数据集 {#internal-ru-subsection-star-329}
以下是合并连接的示例；它在执行计划中由 Merge Join 节点表示[^internal-ru-484-2]：
```text {label="psql"}
=> EXPLAIN (costs off) SELECT *
FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
ORDER BY t.ticket_no;
QUERY PLAN
----------------------------------------------------------------
Merge Join
Merge Cond: (t.ticket_no = tf.ticket_no)
-> Index Scan using tickets_pkey on tickets t
-> Index Scan using ticket_flights_pkey on ticket_flights tf
(4 rows)
```
优化器选择此连接方式，因为它恰好返回了 `ORDER BY` 子句中指定的顺序。在处理计划时，优化器会考虑数据集的排序顺序，如果不需要则不会执行显式排序。特别是，通过合并连接获得的行集可以用于下一个合并连接，只要其排序顺序合适：
```text {label="psql"}
=> EXPLAIN (costs off) SELECT *
FROM tickets t
JOIN ticket_flights tf ON t.ticket_no = tf.ticket_no
JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no
AND bp.flight_id = tf.flight_id
ORDER BY t.ticket_no;
QUERY PLAN
---------------------------------------------------------------------
Merge Join
Merge Cond: ((t.ticket_no = tf.ticket_no) AND (bp.flight_id = ...
-> Merge Join
Merge Cond: (bp.ticket_no = t.ticket_no)
-> Index Scan using boarding_passes_pkey on boarding_passe...
-> Index Scan using tickets_pkey on tickets t
-> Index Scan using ticket_flights_pkey on ticket_flights tf
(7 rows)
```
首先，按 `ticket_no` 顺序通过索引访问读取 `boarding_passes` 表和 `tickets` 表的行，结果也按 `ticket_no` 列排序。该结果集再与通过索引扫描以相同顺序返回的 `ticket_flights` 表的行进行连接。
合并连接仅需对两个数据集各扫描一次，且不需要额外内存。它使用两个指针分别指向内部和外部数据集的当前行（初始时为第一行）。
如果两个当前行的键不匹配，则指向较小键值行的指针向前移动，直到找到匹配项。对应的行返回给上层节点，同时向前移动内部数据集的指针。连接持续进行，直到其中一个数据集被耗尽。
该算法能够处理内部数据集中键的重复值，但由于外部数据集中也可能存在重复键，算法需要稍作调整：如果在移动外部指针后键值未变，则将内部指针回退到具有相同键值的第一行。这样，外部数据集的每一行都会与内部数据集中所有相同键值的行匹配[^internal-ru-486-1]。
对于外连接，算法略有不同，但基本思想保持不变。
合并连接仅支持等值连接，即仅支持等值连接（尽管其他条件的支持工作也在进行中[^internal-ru-486-2]）。
**成本估算。** 考虑上述示例：
```text {label="psql" hl_lines="7"}
=> EXPLAIN SELECT *
FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
ORDER BY t.ticket_no;
QUERY PLAN
----------------------------------------------------------------
Merge Join (cost=0.99..822507.74 rows=8391852 width=136)
Merge Cond: (t.ticket_no = tf.ticket_no)
-> Index Scan using tickets_pkey on tickets t
(cost=0.43..139136.22 rows=2949857 width=104)
-> Index Scan using ticket_flights_pkey on ticket_flights tf
(cost=0.56..571098.73 rows=8391852 width=32)
(6 rows)
```
合并连接的初始成本至少包括其子节点的初始成本。
一般情况下，找到第一个匹配项可能需要读取部分外部或内部数据集。
为了估算这一比例，可以使用直方图比较两个数据集中连接键的最小值[^internal-ru-487-1]。但在本例中，两张表的票号范围完全重合。（参见 [356](/zh18/17-statistics/#internal-ru-page-357)）
合并连接的总成本由从子节点获取数据的成本和计算成本组成。
由于连接算法在其中一个数据集结束时停止（外连接除外），另一个数据集可能不会被完全读取。可以通过比较两个数据集中键的最大值来估算已读行的比例。在本例中，两个数据集都将被完全遍历，因此合并连接的总成本将包括两个子节点的完整成本之和。
此外，由于存在重复项，内部数据集的部分行可能被多次读取。重复读取次数可通过连接结果集与内部数据集的基数之差来估算[^internal-ru-487-2]。在本查询中，这两个基数相同，表明不存在重复项。
算法比较两个数据集的连接键。单次比较的成本由参数 *cpu\_operator\_cost* 估算，比较次数可估算为两个数据集行数之和（加上由重复项引起的重复读取次数）。每条结果行的处理成本通常由参数 *cpu\_tuple\_cost* 估算。（默认值：`0.0025`）（默认值：`0.01`）
因此，本例中合并连接的成本计算如下[^internal-ru-487-3]：
```text {label="psql"}
=> SELECT 0.43 + 0.56 AS startup,
round((
139110.29 + 571098.73 +
current_setting('cpu_tuple_cost')::real * 8391852 +
current_setting('cpu_operator_cost')::real * (2949857 + 8391852)
)::numeric, 2) AS total;
startup | total
---------+-----------
0.99 | 822481.81
(1 row)
```
### 并行模式 {#internal-ru-subsection-star-333}
合并连接没有专门的并行实现，但可以在并行计划中使用[^internal-ru-488-1]。
外部数据集的扫描由并行工作进程并行执行，但每个工作进程始终独立读取内部数据集。
由于并行哈希连接几乎总是成本更低，我暂时禁用它：（参见 [471](/zh18/22-hashing/#internal-ru-page-472)）
```text {label="psql"}
=> SET enable_hashjoin = off;
```
以下是使用合并连接的并行计划示例：
```text {label="psql"}
=> EXPLAIN (costs off)
SELECT count(*), sum(tf.amount)
FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no;
QUERY PLAN
---------------------------------------------------------------------
Finalize Aggregate
-> Gather
Workers Planned: 2
-> Partial Aggregate
-> Merge Join
Merge Cond: (tf.ticket_no = t.ticket_no)
-> Parallel Index Scan using ticket_flights_pkey o...
-> Index Only Scan using tickets_pkey on tickets t
(8 rows)
```
并行计划中不支持完全外连接和右外连接的合并连接。
### 调整 {#internal-ru-subsection-star-335}
合并连接支持任何类型的连接。对于完全外连接和右外连接，唯一的限制是连接条件必须仅包含适用于合并的表达式（外部和内部数据集的列相等，或列与常量相等）[^internal-ru-489-1]。对于内连接和左外连接，合并结果只需过滤掉不合适的条件即可，但对于完全外连接和右外连接，这种过滤不可行。
以下是使用合并算法的完全连接示例：
```text {label="psql"}
=> EXPLAIN (costs off) SELECT *
FROM tickets t
FULL JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
ORDER BY t.ticket_no;
QUERY PLAN
--------------------------------------------------------------------
Sort
Sort Key: t.ticket_no
-> Merge Full Join
Merge Cond: (t.ticket_no = tf.ticket_no)
-> Index Scan using tickets_pkey on tickets t
-> Index Scan using ticket_flights_pkey on ticket_flights tf
(6 rows)
```
内连接和左外连接的合并连接保留排序顺序。但对于完全外连接和右外连接则不然，因为有序的外部数据集值之间可能插入空值——这会破坏排序[^internal-ru-489-2]。因此，此处引入了 Sort 节点以恢复所需顺序。这当然增加了计划成本，使哈希连接更具吸引力，而优化器仅在禁用哈希连接的情况下才选择此计划。
但在下一个示例中，没有其他执行方式：嵌套循环在原则上不支持完全连接，而此处由于条件类型不匹配，合并连接不可用。因此，即使被禁用，仍使用了哈希连接（节点 Hash Full Join 下的 Disabled: true 行提醒了这一点）：（v. 18）
```text {label="psql" hl_lines="13"}
=> EXPLAIN (costs off) SELECT *
FROM tickets t
FULL JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
AND tf.amount > 0
ORDER BY t.ticket_no;
QUERY PLAN
-----------------------------------------------
Sort
Sort Key: t.ticket_no
-> Hash Full Join
Disabled: true
Hash Cond: (tf.ticket_no = t.ticket_no)
Join Filter: (tf.amount > '0'::numeric)
-> Seq Scan on ticket_flights tf
-> Hash
-> Seq Scan on tickets t
(9 rows)
```
恢复之前禁用的哈希连接使用功能：
```text {label="psql"}
=> RESET enable_hashjoin;
```
## 23.2. 排序 {#internal-ru-section-23-2}
如果某个数据集（或两个）未按连接键排序，则在执行合并前必须重新排序。这种显式排序在执行计划中由 Sort 节点表示[^internal-ru-490-1]：
```text {label="psql"}
=> EXPLAIN (costs off)
SELECT *
FROM flights f
JOIN airports_data dep ON f.departure_airport = dep.airport_code
ORDER BY dep.airport_code;
QUERY PLAN
--------------------------------------------------------
Merge Join
Merge Cond: (f.departure_airport = dep.airport_code)
-> Sort
Sort Key: f.departure_airport
-> Seq Scan on flights f
-> Sort
Sort Key: dep.airport_code
-> Seq Scan on airports_data dep
(8 rows)
```
这种排序也可在连接上下文之外使用，例如在 `ORDER BY` 子句中，无论是单独使用还是作为窗口函数的一部分：
```text {label="psql"}
=> EXPLAIN (costs off)
SELECT flight_id,
row_number() OVER (PARTITION BY flight_no ORDER BY flight_id)
FROM flights f;
QUERY PLAN
---------------------------------------------------------------------
WindowAgg
Window: w1 AS (PARTITION BY flight_no ORDER BY flight_id ROWS ...
-> Sort
Sort Key: flight_no, flight_id
-> Seq Scan on flights f
(5 rows)
```
此处 WindowAgg 节点[^internal-ru-491-1] 在 Sort 节点预先排序的数据集上计算窗口函数。
优化器提供了多种排序数据的方法。在我之前展示的示例中，使用了其中两种（Sort Method）。这些细节可通过 `EXPLAIN ANALYZE` 命令获取：
```text {label="psql" hl_lines="12 16"}
=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT *
FROM flights f
JOIN airports_data dep ON f.departure_airport = dep.airport_code
ORDER BY dep.airport_code;
QUERY PLAN
---------------------------------------------------------------------
Merge Join (actual rows=214867.00 loops=1)
Merge Cond: (f.departure_airport = dep.airport_code)
-> Sort (actual rows=214867.00 loops=1)
Sort Key: f.departure_airport
Sort Method: external merge Disk: 17120kB
-> Seq Scan on flights f (actual rows=214867.00 loops=1)
-> Sort (actual rows=104.00 loops=1)
Sort Key: dep.airport_code
Sort Method: quicksort Memory: 42kB
-> Seq Scan on airports_data dep (actual rows=104.00 loops=1)
(10 rows)
```
### 快排 {#internal-ru-subsection-star-337}
如果待排序数据集可放入由参数 *work\_mem* 限制的内存中，则使用传统的快速排序（quick sort）。该算法在所有教材中都有描述，因此不再赘述。（默认值：`4MB`）
从实现角度看，排序由一个特殊组件[^internal-ru-492-1]执行，该组件根据可用内存和其他因素选择最合适的算法。
**成本估算。** 以小表排序为例。此时在内存中执行快速排序：
```text {label="psql" hl_lines="6"}
=> EXPLAIN SELECT *
FROM airports_data
ORDER BY airport_code;
QUERY PLAN
---------------------------------------------------------------------
Sort (cost=7.52..7.78 rows=104 width=145)
Sort Key: airport_code
-> Seq Scan on airports_data (cost=0.00..4.04 rows=104 width=...
(3 rows)
```
已知对 *n* 个值进行排序的时间复杂度为 *O*(*n* log2 *n*)。一次比较操作的成本由参数 *cpu\_operator\_cost* 的两倍估算。由于必须读取并排序整个数据集才能获得结果，排序的初始成本由子节点的完整成本和所有比较操作成本组成。（默认值：`0.0025`）
排序的总成本还包括对每条结果行的处理，其成本由参数 *cpu\_operator\_cost* 估算（而非通常的 *cpu\_tuple\_cost*，因为 Sort 节点的开销较小）[^internal-ru-493-1]。
在本例中，成本计算如下：
```text {label="psql"}
=> WITH costs(startup) AS (
SELECT 4.04 + round((
current_setting('cpu_operator_cost')::real * 2 *
104 * log(2, 104)
)::numeric, 2)
)
SELECT startup,
startup + round((
current_setting('cpu_operator_cost')::real * 104
)::numeric, 2) AS total
FROM costs;
startup | total
---------+-------
7.52 | 7.78
(1 row)
```
### Top-N 堆排序 {#internal-ru-subsection-star-341}
如果只需对数据集的一部分进行排序（由 `LIMIT` 子句定义），则可使用部分堆排序（top-N heapsort）。更准确地说，当排序后行数至少减少一半，或输入数据集无法完全放入分配的内存中（但输出数据集仍可容纳）时，该算法被启用。
```text {label="psql" hl_lines="6 11"}
=> EXPLAIN (analyze, timing off, summary off, buffers off)
SELECT * FROM seats
ORDER BY seat_no LIMIT 100;
QUERY PLAN
-------------------------------------------------------------------
Limit (cost=72.57..72.82 rows=100 width=15)
(actual rows=100.00 loops=1)
-> Sort (cost=72.57..75.91 rows=1339 width=15)
(actual rows=100.00 loops=1)
Sort Key: seat_no
Sort Method: top-N heapsort Memory: 32kB
-> Seq Scan on seats (cost=0.00..21.39 rows=1339 width=15)
(actual rows=1339.00 loops=1)
(8 rows)
```
为了从 *n* 个值中找出 *k* 个最大（最小）值，首先将前 *k* 行加入称为堆（heap）的数据结构中。然后逐个添加其余行，但每次添加后，从堆中移除最小（最大）值。最终，堆中将保留 *k* 个所需值。
> [!NOTE]
> 本算法中使用的堆（heap）是一种数据结构，与通常被称为堆的数据库表无关。
**成本估算。** 算法复杂度为 *O*(*n* log2 *k*)，但每次操作成本高于快速排序。因此，成本计算公式[^internal-ru-494-1] 使用 *n* log2 2*k*。
```text {label="psql"}
=> WITH costs(startup) AS (
SELECT 21.39 + round((
current_setting('cpu_operator_cost')::real * 2 *
1339 * log(2, 2 * 100)
)::numeric, 2)
)
SELECT startup,
startup + round((
current_setting('cpu_operator_cost')::real * 100
)::numeric, 2) AS total
FROM costs;
startup | total
---------+-------
72.57 | 72.82
(1 row)
```
### 外排 {#internal-ru-subsection-star-345}
如果在读取数据集时发现其过大，无法在内存中排序，则排序节点将切换到外部合并排序（external merge）。
已读取的行使用快速排序算法在内存中排序，并写入临时文件。
{#internal-ru-fig-23-1 num="23.1" caption="外部排序" .book-original-figure width=503 height=205}
在释放的内存中读取下一批行，重复此过程，直到所有数据被写入多个文件，每个文件各自有序。
{#internal-ru-fig-23-2 num="23.2" caption="外部排序" .book-original-figure width=528 height=205}
接下来，使用与合并连接相同的算法，将多个文件合并为一个文件。主要区别在于，可以同时合并超过两个文件。
合并不需要大量内存。原则上，只需为每个文件保留一个行的空间即可。从文件中读取第一行，从中选择最小（或最大，取决于排序方向）的行作为结果的一部分返回，并用同一文件中的新行替换它。
实际上，行不是逐个读取的，而是以每批32页的方式读取；这减少了输入/输出操作的次数。一次迭代中合并的文件数量由可用内存决定，但永远不会少于六个。该数量也受到上限（500）的限制，因为当文件过多时效率会下降[^internal-ru-496-1]。
> [!NOTE]
> 在英语中，排序算法有其历史形成的专门术语。外部排序最初使用磁带存储设备，PostgreSQL 中负责临时文件的组件保留了这一名称[^internal-ru-496-2]。部分排序的数据集被称为 run（俄语译本中译为“序列”[^internal-ru-496-3]）。参与合并的序列数量称为 merge order（合并顺序）。我未使用这些术语，但了解它们有助于理解代码和注释。
如果无法在一次迭代中合并所有已排序的临时文件，则必须分部分合并文件，并将结果写入新的临时文件。每次迭代都会增加读取和写入的数据量，因此可用的内存越多，外部排序的效率就越高。
{#internal-ru-fig-23-3 num="23.3" caption="外部排序" .book-original-figure width=682 height=205}
{#internal-ru-fig-23-4 num="23.4" caption="外部排序" .book-original-figure width=552 height=205}
在下一次迭代中，合并操作将使用新的文件继续进行。
{#internal-ru-fig-23-5 num="23.5" caption="外部排序" .book-original-figure width=342 height=205}
最终合并通常被延迟执行，直到上层计划节点请求数据时才实时完成。
命令 `EXPLAIN ANALYZE` 显示了外部排序所需的磁盘空间量。添加 `buffers` 关键字后，还可以获取临时文件缓冲区的使用统计信息（temp read 和 written）。写入的缓冲区数量（大致）等于读取的缓冲区数量，而计划中 Disk 位置显示的正是该值换算成千字节的结果。
```text {label="psql" hl_lines="8 9"}
=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM flights
ORDER BY scheduled_departure;
QUERY PLAN
----------------------------------------------------------
Sort (actual rows=214867.00 loops=1)
Sort Key: scheduled_departure
Sort Method: external merge Disk: 17120kB
Buffers: shared hit=2627, temp read=2140 written=2145
-> Seq Scan on flights (actual rows=214867.00 loops=1)
Buffers: shared hit=2624
(6 rows)
```
更详细的临时文件使用统计信息可以通过设置参数 *log\_temp\_files* 在日志消息中获取。
**成本估算。** 以同一个带有外部排序的计划为例：
```text {label="psql" hl_lines="6 8"}
=> EXPLAIN SELECT *
FROM flights
ORDER BY scheduled_departure;
QUERY PLAN
---------------------------------------------------------------------
Sort (cost=31883.96..32421.12 rows=214867 width=63)
Sort Key: scheduled_departure
-> Seq Scan on flights (cost=0.00..4772.67 rows=214867 width=63)
(3 rows)
```
此处除了与内存快速排序相同数量的比较成本外，还增加了输入/输出成本[^internal-ru-498-1]。所有输入数据必须首先写入磁盘上的临时文件，然后在合并时从磁盘读取（可能多次，如果创建的文件数量超过可同时合并的集合数量）。
磁盘访问（读取和写入）被估算为 75% 顺序访问，25% 随机访问。
落入磁盘的数据量由待排序的行数和查询中使用的列数决定[^internal-ru-498-2]。本例中，查询输出了 `flights` 表的所有列，因此写入磁盘的数据量几乎等于整个表的大小，减去行和页面中的元信息（2309 页而非 2624 页）。
在我们的示例中，一次迭代就足以完成排序。
因此，我们计划中的排序成本计算如下：
```text {label="psql"}
=> WITH costs(startup) AS (
SELECT 4772.67 + round((
current_setting('cpu_operator_cost')::real * 2 *
214867 * log(2, 214867) +
(current_setting('seq_page_cost')::real * 0.75 +
current_setting('random_page_cost')::real * 0.25) *
2 * 2309 * 1 -- одна итерация
)::numeric, 2)
)
SELECT startup,
startup + round((
current_setting('cpu_operator_cost')::real * 214867
)::numeric, 2) AS total
FROM costs;
startup | total
----------+----------
31883.96 | 32421.13
(1 row)
```
### 增量排序v. 13 {#internal-ru-subsection-star-349}
如果需要按键 *K*1 … *K*m … *K*n 对数据集进行排序，且已知该数据集已按前 *m* 个键排序，则无需重新对整个数据集进行排序。可以将数据集划分为若干组，这些组在前 *m* 个键上具有相同的值（这些组的值彼此相邻），然后分别对每组按剩余的键 *K*m+1 … *K*n 进行排序。这种方法称为 *增量排序*。
增量排序通过将整个数据集划分为多个较小的组来降低内存需求，并允许在处理完第一组后立即输出结果，而无需等待整个数据集排序完成。
实现方式[^internal-ru-499-1] 更为精细：仅对相对较大的行组进行单独处理，而较小的组则合并后整体排序。这减少了排序调用的开销[^internal-ru-499-2]。
执行计划中，增量排序由 Incremental Sort 节点表示：
```text {label="psql"}
=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT *
FROM bookings
ORDER BY total_amount, book_date;
QUERY PLAN
--------------------------------------------------------------------
Incremental Sort (actual rows=2111110.00 loops=1)
Sort Key: total_amount, book_date
Presorted Key: total_amount
Full-sort Groups: 2823 Sort Method: quicksort Average
Memory: 27kB Peak Memory: 27kB
Pre-sorted Groups: 2624 Sort Method: quicksort Average
Memory: 1953kB Peak Memory: 2014kB
-> Index Scan using bookings_total_amount_idx on bookings (ac...
Index Searches: 1
(9 rows)
```
从计划中可以看出，行集已按 `total_amount` 排序，因为它是通过按该列构建的索引扫描得到的（Presorted Key）。`EXPLAIN ANALYZE` 命令还显示了执行时间统计信息。Full-sort Groups 行对应于被合并并完全排序的小组，Presorted Groups 行对应于较大的组，这些组在 `book_date` 列上进行了二次排序。两种情况下均使用了内存中的快速排序。不同大小的组的存在是由于预订成本分布不均所致。
增量排序也可用于窗口函数的计算：（v. 14）
```text {label="psql"}
=> EXPLAIN (costs off)
SELECT row_number() OVER (ORDER BY total_amount, book_date)
FROM bookings;
QUERY PLAN
---------------------------------------------------------------------
WindowAgg
Window: w1 AS (ORDER BY total_amount, book_date ROWS UNBOUNDED...
-> Incremental Sort
Sort Key: total_amount, book_date
Presorted Key: total_amount
-> Index Scan using bookings_total_amount_idx on bookings
(6 rows)
```
**成本估算。** 增量排序的成本估算[^internal-ru-501-1] 基于对组数的估算[^internal-ru-501-2] 以及对中等大小组排序的估算（我们已讨论过）。
初始成本反映了对第一个（即第一个）组排序的估算，此时节点已可输出已排序的行；而总成本则包含了对所有组排序的估算。
关于估算的详细计算过程，我将不再赘述。
### 并行模式 {#internal-ru-subsection-star-353}
排序可以并行执行。尽管工作进程以已排序的形式输出其数据部分，但 Gather 节点并不知道这一点，只能按到达顺序合并数据。为了保持排序顺序，需使用另一个节点——Gather Merge[^internal-ru-501-3]。
```text {label="psql"}
=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT *
FROM flights
ORDER BY scheduled_departure
LIMIT 10;
QUERY PLAN
---------------------------------------------------------------------
Limit (actual rows=10.00 loops=1)
-> Gather Merge (actual rows=10.00 loops=1)
Workers Planned: 1
Workers Launched: 1
-> Sort (actual rows=8.50 loops=2)
Sort Key: scheduled_departure
Sort Method: top-N heapsort Memory: 27kB
Worker 0: Sort Method: top-N heapsort Memory: 27kB
-> Parallel Seq Scan on flights (actual rows=107433.50...
(9 rows)
```
Gather Merge 节点使用二叉堆[^internal-ru-501-4] 对来自多个进程的行进行排序。本质上，它执行了多个已排序行集的合并，类似于外部排序，但算法针对不同工作条件进行了优化：固定数量的源（较小且固定），按单行获取，不支持块访问。
**成本估算。** Gather Merge 节点的初始成本基于其子节点的初始成本。此外（与 Gather 节点类似），还需加上进程启动成本，该成本由参数 *parallel\_setup\_cost* 估算。（参见 [382](/zh18/18-table-access-methods/#internal-ru-page-383)）（默认值：`1000`）
此外还需估算二叉堆的构建成本，这需要对并行进程数量 *n* 个值进行排序（即 *n* log2 *n*）。每次比较成本为 *cpu\_operator\_cost* 的两倍，由于 *n* 较小，总成本通常可忽略不计。（默认值：`0.0025`）
总成本包括子节点获取所有数据的成本（由多个并行进程执行）以及这些进程间行传输的成本。每行传输成本为 *parallel\_tuple\_cost* 的 1.05 倍，以考虑等待后续值时可能的延迟。（默认值：`0.1`）
总成本还包括二叉堆的更新成本。对每条输入行，这需要 log2 *n* 次比较操作以及若干辅助操作（估算为 *cpu\_operator\_cost*）[^internal-ru-502-1]。
以下是另一个带有 Gather Merge 节点的计划示例。该示例有趣之处在于，工作进程使用哈希方法执行部分聚合，然后将结果由 Sort 节点排序（由于聚合后行数较少，成本较低），再传递给主进程，主进程在 Gather Merge 节点中合并完整结果。最终的聚合则基于已排序的值列表执行：（参见 [478](/zh18/22-hashing/#internal-ru-page-479)）
```text {label="psql" hl_lines="8"}
=> EXPLAIN SELECT amount, count(*)
FROM ticket_flights
GROUP BY amount;
QUERY PLAN
---------------------------------------------------------------------
Finalize GroupAggregate (cost=123426.68..123528.57 rows=338 wid...
Group Key: amount
-> Gather Merge (cost=123426.68..123521.13 rows=811 width=14)
Workers Planned: 2
-> Sort (cost=122426.65..122427.50 rows=338 width=14)
Sort Key: amount
-> Partial HashAggregate (cost=122409.07..122412.46 r...
Group Key: amount
-> Parallel Seq Scan on ticket_flights (cost=0.00...
(9 rows)
```
本例中并行进程数量为三个（含主进程），Gather Merge 节点的成本计算如下：
```text {label="psql"}
=> WITH costs(startup, run) AS (
SELECT round((
-- запуск процессов
current_setting('parallel_setup_cost')::real +
-- построение кучи
current_setting('cpu_operator_cost')::real * 2 * 3 * log(2, 3)
)::numeric, 2),
round((
-- передача строк
current_setting('parallel_tuple_cost')::real * 1.05 * 676 +
-- обновление кучи
current_setting('cpu_operator_cost')::real * 2 * 676 * log(2, 3) +
current_setting('cpu_operator_cost')::real * 676
)::numeric, 2)
)
SELECT 122426.65 + startup AS startup,
122427.50 + startup + run AS total
FROM costs;
startup | total
-----------+-----------
123426.67 | 123505.55
(1 row)
```
## 23.3. 非重复值和分组 {#internal-ru-section-23-3}
正如我们刚刚看到的，聚合（以及去重）可以通过哈希或排序实现。在已排序的列表中，重复值的组可以仅通过一次遍历就轻易识别出来。（参见 [479](/zh18/22-hashing/#internal-ru-page-480)）
从已排序列表中提取唯一值在计划中由一个非常简单的节点 Unique [^internal-ru-504-1] 表示：
```text {label="psql"}
=> EXPLAIN (costs off) SELECT DISTINCT book_ref
FROM bookings
ORDER BY book_ref;
QUERY PLAN
------------------------------------------------------
Unique
-> Index Only Scan using bookings_pkey on bookings
(2 rows)
```
Unique 节点可以参与并行计划，用于消除工作进程返回列表中的重复项：（v. 15）
```text {label="psql"}
=> EXPLAIN (costs off) SELECT DISTINCT fare_conditions
FROM ticket_flights;
QUERY PLAN
------------------------------------------------------
Unique
-> Gather Merge
Workers Planned: 2
-> Sort
Sort Key: fare_conditions
-> HashAggregate
Group Key: fare_conditions
-> Parallel Seq Scan on ticket_flights
(8 rows)
```
在本例中，工作进程通过 HashAggregate 节点使用哈希方法在各自数据集中提取唯一值；由 Gather 节点收集的汇总列表在 Sort 节点中排序后，传递给 Unique 节点以最终去除重复项。
聚合使用另一个节点 GroupAggregate [^internal-ru-504-2]：
```text {label="psql"}
=> EXPLAIN (costs off) SELECT book_ref, count(*)
FROM bookings
GROUP BY book_ref
ORDER BY book_ref;
QUERY PLAN
------------------------------------------------------
GroupAggregate
Group Key: book_ref
-> Index Only Scan using bookings_pkey on bookings
(3 rows)
```
在并行计划中，该节点称为 Partial GroupAggregate，而完成聚合的节点称为 Finalize GroupAggregate。
哈希和排序两种策略可以在同一节点中结合使用，用于对多个集合进行分组（在 `GROUPING SETS`、`CUBE` 或 `ROLLUP` 子句中）。我不会深入探讨算法的复杂细节。仅举一个例子，其中分组需基于三个不同的列：
```text {label="psql" hl_lines="7 8 9"}
=> EXPLAIN (costs off) SELECT count(*)
FROM ticket_flights
GROUP BY GROUPING SETS (fare_conditions, ticket_no, amount);
QUERY PLAN
-------------------------------------
MixedAggregate
Hash Key: amount
Group Key: fare_conditions
Sort Key: ticket_no
Group Key: ticket_no
-> Sort
Sort Key: fare_conditions
-> Seq Scan on ticket_flights
(8 rows)
```
执行此查询时发生的情况如下：计划中标记为 MixedAggregate 的聚合节点接收按 `fare_conditions` 列排序的数据集。
在第一阶段，该数据集被扫描，并按 `fare_conditions` 列分组（Group Key）。在扫描过程中，行按 `ticket_no` 列重新排序（与普通 Sort 节点相同：若内存足够则使用内存快速排序，否则使用磁盘外部排序），同时将这些行写入以 `amount` 为键的哈希表中（与哈希聚合相同：若内存足够则在内存中，否则使用临时文件）。
在第二个阶段，扫描在前一阶段按 `ticket_no` 列排序的行集，并根据同一列（排序键和嵌套分组键）对值进行分组。如果需要按另一列进行排序分组，行将被重新排序为所需顺序。
最后，扫描在第一阶段准备好的哈希表，并根据 `amount` 列（哈希键）对值进行分组。
## 23.4. 连接方式的比较 {#internal-ru-section-23-4}
因此，连接两个数据集可以使用三种不同的方法，每种方法都有其优缺点。
*嵌套循环连接* 不需要任何预处理工作，可立即开始返回结果行。这是唯一一种在内部数据集存在高效索引访问时，无需完全扫描内部数据集的连接方式。这些特性使得嵌套循环算法（与索引结合使用）成为处理短 OLTP 查询的理想机制，这类查询基于少量行的子集构建。
嵌套循环的缺点随着数据量的增长而显现。对于笛卡尔积，该算法具有二次复杂度——开销与连接数据集大小的乘积成正比。笛卡尔积在实践中并不常见；通常情况下，对于外部数据集的每一行，通过索引仅需扫描内部数据集的若干行，而这一平均数量与整个数据集的大小无关（例如，每次预订的平均票数不会随预订数量和售出票数的增加而改变）。因此，复杂度通常表现为线性增长，而非二次增长，尽管系数较大。
嵌套循环的一个重要特点是其通用性：它支持任意连接条件，而其他方法仅支持等值连接。这使得可以执行任何带有任意条件的查询（除完全连接外，完全连接无法通过嵌套循环实现），但需注意，非等值连接在处理大量数据时几乎肯定比预期更慢。
*哈希连接* 对于大数据集非常高效。在有足够的内存时，它只需对两个数据集各扫描一次，即具有线性复杂度。与表的顺序扫描结合使用时，哈希连接在计算大量数据结果的 OLAP 查询中经常出现。
在响应时间比吞吐量更重要的场景中，哈希连接表现较差，因为结果行必须等到哈希表完全构建后才能返回。
哈希连接的应用受限于等值连接。此外，数据类型必须支持哈希运算（这几乎总是成立）。
嵌套循环有时可通过在 Memoize 节点（基于哈希表）中缓存内部数据集的行而与哈希连接竞争。优势源于哈希连接始终必须完全扫描内部数据集，而嵌套循环算法则不需要。（v. 14）
*合并连接* 既适用于短 OLTP 查询，也适用于长 OLAP 查询。它具有线性复杂度（只需对连接的数据集各扫描一次），对内存要求不高，并且无需预处理即可输出结果——前提是数据集必须按正确顺序排序。实现这一条件的最有效方法是通过索引扫描获取数据。对于少量行而言，这是自然的选择；对于大量数据，索引访问也可能高效，但前提是访问表的次数较少或完全没有。
如果没有合适的索引，则必须对数据集进行排序，而排序需要内存且复杂度高于线性：*O*(*n* log2 *n*）。
在这种情况下，合并连接几乎总是不如哈希连接——除非结果需要保持排序。
合并连接的一个优点是外部和内部数据集的对称性。嵌套循环和哈希连接的效率高度依赖于查询规划器是否正确选择哪个数据集作为外部，哪个作为内部。
合并连接的应用受限于等值连接。此外，数据类型必须具有 B-树操作符类。（*参见* [546](/zh18/25-b-tree/#internal-ru-page-547)）
下图展示了不同连接方式的成本随连接行比例变化的近似关系。
{#internal-ru-fig-23-6 num="23.6" caption="连接方式比较" .book-original-figure width=710 height=436}
在高选择性情况下，嵌套循环连接利用两个表的索引访问；随后规划器切换为完全扫描外部表，成本曲线变为线性。
本例中，哈希连接使用了两个表的完全扫描。成本曲线上的“台阶”出现在哈希表无法完全放入内存，开始将数据包写入磁盘时。
使用索引的合并连接显示出较小的线性成本增长。当 *work\_mem* 足够大时，哈希连接通常更高效，但当涉及临时文件时，合并连接反而占优。
合并连接加排序的上图显示了在无索引可用、必须对数据排序时成本的增长情况。与哈希连接类似，成本曲线上的“台阶”由内存不足引起，需使用临时文件进行排序。
这只是示例；在每个具体场景中，成本关系显然会有所不同。
[^internal-ru-484-1]: [backend/optimizer/path/joinpath.c](), 函数 generate\_mergejoin\_paths.
[^internal-ru-484-2]: [backend/executor/nodeMergejoin.c]().
[^internal-ru-486-1]: [backend/executor/nodeMergejoin.c](), 函数 ExecMergeJoin.
[^internal-ru-486-2]: 例如, [commitfest.postgresql.org/33/3160]().
[^internal-ru-487-1]: [backend/utils/adt/selfuncs.c](), 函数 mergejoinscansel.
[^internal-ru-487-2]: [backend/optimizer/path/costsize.c](), 函数 final\_cost\_mergejoin.
[^internal-ru-487-3]: [backend/optimizer/path/costsize.c](), 函数 initial\_cost\_mergejoin и final\_cost\_mergejoin.
[^internal-ru-488-1]: [backend/optimizer/path/joinpath.c](), 函数 consider\_parallel\_mergejoin.
[^internal-ru-489-1]: [backend/optimizer/path/joinpath.c](), 函数 select\_mergejoin\_clauses.
[^internal-ru-489-2]: [backend/optimizer/path/pathkeys.c](), 函数 build\_join\_pathkeys.
[^internal-ru-490-1]: [backend/executor/nodeSort.c]().
[^internal-ru-491-1]: [backend/executor/nodeWindowAgg.c]().
[^internal-ru-492-1]: [backend/utils/sort/tuplesort.c]().
[^internal-ru-493-1]: [backend/optimizer/path/costsize.c](), 函数 cost\_sort.
[^internal-ru-494-1]: [backend/optimizer/path/costsize.c](), 函数 cost\_sort.
[^internal-ru-496-1]: [backend/utils/sort/tuplesort.c](), 函数 tuplesort\_merge\_order.
[^internal-ru-496-2]: [backend/utils/sort/logtape.c]().
[^internal-ru-496-3]: *Дональд Кнут*. Искусство программирования. Т. 3: Сортировка и поиск.
[^internal-ru-498-1]: [backend/optimizer/path/costsize.c](), 函数 cost\_sort.
[^internal-ru-498-2]: [backend/optimizer/path/costsize.c](), 函数 relation\_byte\_size.
[^internal-ru-499-1]: [backend/executor/nodeIncrementalSort.c]().
[^internal-ru-499-2]: [backend/utils/sort/tuplesort.c]().
[^internal-ru-501-1]: [backend/optimizer/path/costsize.c](), 函数 cost\_incremental\_sort.
[^internal-ru-501-2]: [backend/utils/adt/selfuncs.c](), 函数 estimate\_num\_groups.
[^internal-ru-501-3]: [backend/executor/nodeGatherMerge.c]().
[^internal-ru-501-4]: [backend/lib/binaryheap.c]().
[^internal-ru-502-1]: [backend/optimizer/path/costsize.c](), 函数 cost\_gather\_merge.
[^internal-ru-504-1]: [backend/executor/nodeUnique.c]().
[^internal-ru-504-2]: [backend/executor/nodeAgg.c](), 函数 agg\_retrieve\_direct.