在前面的文章中，介绍了查询执行阶段、统计信息、顺序扫描和索引扫描，以及三种联接方法中的两种：嵌套循环和哈希联接。本系列的最后一篇文章将介绍合并算法和排序。我还将演示这三种连接方法如何相互比较。
合并联接算法采用两个按合并键排序的数据集，并返回有序输出。输入数据集可以通过索引扫描进行预排序，也可以显式排序。
合并排序集
下面是合并联接的示例。记下计划中的“合并联接”节点。
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
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: (tf.ticket_no = t.ticket_no)
−> Merge Join
Merge Cond: ((tf.ticket_no = bp.ticket_no) AND (tf.flight_...
−> Index Scan using ticket_flights_pkey on ticket_flights tf
−> Index Scan using boarding_passes_pkey on boarding_passe...
−> Index Scan using tickets_pkey on tickets t
(7 rows)
icket_flights和 boarding_passes 表首先合并。这些表具有复合主键 （ticket_no，flight_id ），因此输出按这两列排序。然后，生成的行集将与tickets表合并，表按 ticket_no排序。
合并在两个数据集上一次完成，不需要任何额外的内存。该算法使用两个指针，指向两个集合的当前（或最初为第一行）。
如果当前行的键不匹配，则其中一个指针（指向具有较低键的行的指针）将向前移动一步。此操作将重复，直到找到匹配项。匹配的行将返回到父节点，并且内部集指针向前移动一步。该算法将重复，直到到达任一集合的末尾。
此特定算法可以处理内部集合中的重复键，但不能处理外部集中的重复键。引入了一个额外的步骤来解决这个问题：每当外部指针移动但键保持不变时，内部指针将返回到与键匹配的第一行。这样，每个外部集行都将与具有相同键的所有内集行匹配。
该算法还有另一种可以执行外连接的变体，但它基于相同的原理。
合并联接旨在与公平运算符一起使用，因此它仅支持等联接（但也努力支持其他比较运算符）。
成本估算。考虑之前的例子：
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..822358.66 rows=8391852 width=136)
Merge Cond: (t.ticket_no = tf.ticket_no)
−> Index Scan using tickets_pkey on tickets t
(cost=0.43..139110.29 rows=2949857 width=104)
−> Index Scan using ticket_flights_pkey on ticket_flights tf
(cost=0.56..570975.58 rows=8391852 width=32)
(6 rows)
最初，启动成本至少包括子节点的启动成本。
除此之外，在找到第一个匹配项之前，您通常必须至少扫描两个数据集的一部分。要估计此分数，可以使用直方图来比较两组中的最小连接键。但是，在这种情况下，两个表中的机票号码范围是相同的。
节点的总成本是来自其子节点的数据检索成本和数据处理成本的总和。
由于算法在到达两个集合中的任何一个的末尾时停止（当然，执行外连接时除外），因此第二个集合的一小部分可能保持未扫描状态。您可以通过比较两个集合的最大键来估计该分数的大小。在这种情况下，我们的两个集合都将被完全扫描，因此我们将子节点的全部总成本包含在父节点的总成本中。
此外，重复的键可能会导致多次扫描某些内部集行。重复扫描的次数与连接结果和内部集基数之间的差值成正比。
在这里，这些基数是相同的，这意味着没有重复。
数据处理成本包括关键比较和结果输出。比较次数可以通过将两个集合的基数和重复的外部集合行扫描的数量相加来估计。一个比较的成本估计为cpu_operator_cost，行输出成本估计为cpu_tuple_cost。
现在我们可以计算我们示例的加入成本：
SELECT 0.43 + 0.56 AS startup,
round((
139110.29 + 570975.58 +
current_setting('cpu_tuple_cost')::real * 8391852 +
current_setting('cpu_operator_cost')::real * (2949857 + 8391852)
)::numeric, 2) AS total;
startup | total
−−−−−−−−−+−−−−−−−−−−−
0.99 | 822358.66
(1 row)
合并联接算法可用于并行化计划。
工作线程可以并行扫描外部集，但每个工作线程单独扫描内部集。
下面是具有合并联接的并行计划的示例：
SET enable_hashjoin = off;
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)
在此模式下不支持完全外连接和右外连接。
合并联接支持所有逻辑联接类型。唯一的限制是，对于完全连接和右外连接，连接条件必须是合并操作（ outer column equals inner column或 column equals constant）的有效表达式。对于其他逻辑联接类型，任何不可合并的条件都将在合并完成后应用于输出，但对于完全连接和右外联接，不可能这样做。
下面是完全合并连接的示例：
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 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)
内侧和左外侧合并联接保留排序。完整和右外连接不会，因为数据中可能出现的 NULL 值将中断排序。这是 Sort 节点用于对输出重新排序的位置。它增加了成本，使哈希加入成为一种更具吸引力的替代方案，因此我们必须在演示中显式禁用它。
但是，在下一个示例中，无论如何都会选择哈希联接，因为无法以任何其他方式完成具有不可合并连接条件的完全联接。
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 Key: t.ticket_no
−> Hash Full Join
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
(8 rows)
RESET enable_hashjoin;
如果其中一个集（或两者）未按连接键排序，则必须在合并之前对其进行排序。此必要的排序在计划中的 Sort 节点下完成。
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
EXPLAIN (costs off)
SELECT flight_id,
row_number() OVER (PARTITION BY flight_no ORDER BY flight_id)
FROM flights f;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
WindowAgg
−> Sort
Sort Key: flight_no, flight_id
−> Seq Scan on flights f
(4 rows)
在这里，WindowAgg 节点在排序节点预先排序的数据集上计算窗口函数。
计划器具有多种排序模式可供选择。上面的示例展示了其中的两个（排序方法）。与往常一样，您可以使用 EXPLAIN ANALYZE 了解更多详细信息：
EXPLAIN (analyze,costs off,timing off,summary 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 loops=1)
Merge Cond: (f.departure_airport = dep.airport_code)
−> Sort (actual rows=214867 loops=1)
Sort Key: f.departure_airport
Sort Method: external merge Disk: 17136kB
−> Seq Scan on flights f (actual rows=214867 loops=1)
−> Sort (actual rows=104 loops=1)
Sort Key: dep.airport_code
Sort Method: quicksort Memory: 52kB
−> Seq Scan on airports_data dep (actual rows=104 loops=1)
(10 rows)
如果要排序的数据完全适合允许的内存（work_mem），则使用旧的快速排序算法。你可以在任何计算机科学教科书的第一页上找到它的描述，所以我不会在这里重复它。
对于实现，排序由为任务选择最合适的算法的特定组件完成。
成本估算。让我们看一下该算法如何对小表进行排序：
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 对数）2一次比较操作的成本是cpu_operator_cost值的两倍。您需要对整个集合进行扫描和排序才能获得结果，因此启动排序成本将包括比较操作成本和子节点的总成本。
除此之外，总排序成本还将包括 Sort 节点输出的每一行的处理成本，估计为每行 cpu_operator_cost（而不是默认cpu_tuple_cost因为它很便宜）。
因此，上述示例的排序成本将按如下方式计算：
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 堆
top-N 堆是当你只想对集合的一部分进行排序（最多是某个LIMIT）而不是整个集合时，你会这样做。更准确地说，当LIMIT将过滤掉至少一半的输入行时，或者当输入不适合内存，但输出适合时，使用此算法。
EXPLAIN (analyze, timing off, summary 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 loops=1)
−> Sort (cost=72.57..75.91 rows=1339 width=15)
(actual rows=100 loops=1)
Sort Key: seat_no
Sort Method: top−N heapsort Memory: 33kB
−> Seq Scan on seats (cost=0.00..21.39 rows=1339 width=15)
(actual rows=1339 loops=1)
(8 rows)
为了从 n 中找出 k 个最高（最低）值，该算法首先创建一个称为堆的数据结构，并向其中添加 k 个前行。然后，它继续逐行添加到堆中，但在每个行之后，它会从堆中排出一个最低（最高）值。当要添加的新行用完时，堆将保留 k 个最大值或最低值。
此处的术语堆是指特定的数据结构，不应与数据库表混淆，后者通常具有相同的名称。
成本估算。算法复杂度为 O（n 对数）2k），但与快速排序相比，每个操作的成本更高，因此成本计算公式使用n log22k 作为估计值。
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)
每当执行程序发现它正在读取的数据集也无法在内存中排序时，Sort 节点就会切换到外部合并排序模式。
到目前为止扫描的行按快速排序排序并转储到临时文件中。
然后扫描、排序和转储另一批行，依此类推。重复此操作，直到所有数据都存储在磁盘上的一堆排序文件中。
然后，算法开始合并文件。该过程与合并联接非常相似，尽管此处可以同时合并两个以上的文件。
合并不会占用大量内存。从本质上讲，每个文件一行的大小就足够了。该算法扫描每个文件的第一行并存储它们。然后，它在存储的值中选择最低（或最高）值，并将其作为输出返回。之后，它采用另一行并将其放入存储返回行的内存中。
实际上，不是逐个扫描行，而是分批扫描，每行 32 页，以节省 I/O 成本。一次合并的文件数由可用内存量决定，但永远不会少于六个。它也永远不会超过500，因为算法效率在大量并发合并的文件时会受到影响。
如果无法在单个迭代中合并所有临时文件，则第一次合并的结果将转储到其自己的临时文件中。每次迭代都会增加从磁盘读取和写入磁盘的数据量，从而减慢该过程，因此拥有尽可能多的内存以使外部合并排序高效运行是有益的。
第二次迭代采用第一次迭代生成的临时文件并重复该过程。
最终合并通常会推迟，并且仅在父节点提取数据时执行。
让我们应用 EXPLAIN ANALYZE 来看看排序用了多少磁盘空间。您还可以使用 buffers 选项检出临时文件（临时读取和写入）的缓冲区使用情况统计信息。读取和写入的缓冲区的编号将大致相同，并且转换为 KB 时，将与计划中的“磁盘”值匹配。
EXPLAIN (analyze, buffers, costs off, timing off, summary off)
SELECT *
FROM flights
ORDER BY scheduled_departure;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Sort (actual rows=214867 loops=1)
Sort Key: scheduled_departure
Sort Method: external merge Disk: 17136kB
Buffers: shared hit=610 read=2017, temp read=2142 written=2150
−> Seq Scan on flights (actual rows=214867 loops=1)
Buffers: shared hit=607 read=2017
(6 rows)
有关要在服务器日志中找到的临时文件的更多统计信息（参数log_temp_buffers打开）。
成本估算。让我们再看一下外部合并排序计划：
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)
在这里，基本比较成本与快速排序相同，但顶部还添加了 I/O 成本。首先将所有输入数据转储到磁盘，然后从磁盘读取以进行合并（如果单个文件太多而无法在一次传递中合并，则多次）。
写入磁盘的数据量取决于输入数据集中行的数量和大小。在此示例中，查询从表中提取所有列，因此数据大小将接近表大小，只是它不包含任何元组标头和页面元数据（2309 页 vs 2624 页）。在这里，一次迭代就足以对数据进行排序。flights
I/O 操作（读取和写入）估计为连续 3/4 的时间和随机的 1/4 时间。
所以最后，分拣成本的计算方式是这样的：
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 -- one iteration
)::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)
假设您要按键对集合进行排序K1…Km…Kn，并且已知该集合已按某些第一个键排序K1…Km.然后，您可以通过不对整个集合进行排序来节省时间。相反，您可以将集合拆分为多个组，每个组仅包含具有相同K1…Km值（连续排列），然后按其余键对每个组进行排序K米+1…Kn.此方法称为增量排序，在 PostgreSQL 13 及更高版本中可用。
增量排序通过将集合拆分为多个较小的组来降低内存需求，并且还可以开始逐个组地为输出组提供数据，而无需等待整个集被处理。
实际的实现采用了额外的优化：虽然它将较大的行块分成组进行单独排序，但较小的子集被放入一个组中并一起排序。与基本算法相比，这降低了排序启动开销成本。
计划中的“增量排序”节点是进行排序发生的位置：
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT *
FROM bookings
ORDER BY total_amount, book_date;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Incremental Sort (actual rows=2111110 loops=1)
Sort Key: total_amount, book_date
Presorted Key: total_amount
Full−sort Groups: 2823 Sort Method: quicksort Average
Memory: 30kB Peak Memory: 30kB
Pre−sorted Groups: 2624 Sort Method: quicksort Average
Memory: 3152kB Peak Memory: 3259kB
−> Index Scan using bookings_total_amount_idx on bookings (ac...
(8 rows)
从计划中可以明显看出，该集按 total_amount 进行预排序，作为针对此列的索引扫描的输出（预排序键）。EXPLAIN ANALYZ 命令还向我们显示了处理数据所花费的时间。“完全排序组”值显示聚集在一起并定期排序的行数，“预排序组”显示按Ebook_date列增量排序的大型组数。在这两种情况下都使用了内存中快速排序。团体规模的变化是由预订费用的分布引起的，这是不均匀的。
在 PostgreSQL 14 及更高版本中，增量排序也适用于窗口函数：
EXPLAIN (costs off)
SELECT row_number() OVER (ORDER BY total_amount, book_date)
FROM bookings;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
WindowAgg
−> Incremental Sort
Sort Key: total_amount, book_date
Presorted Key: total_amount
−> Index Scan using bookings_total_amount_idx on bookings
(5 rows)
成本估算。增量排序成本取决于估计的组数和对平均组进行排序的估计成本（我们之前已经介绍过）。
启动成本显示对一个（第一个）组进行排序的成本，因为这足以让节点开始输出。总成本包括对所有组进行排序的成本。
EXPLAIN SELECT *
FROM bookings
ORDER BY total_amount, book_date;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Incremental Sort (cost=45.10..282293.40 rows=2111110 width=21)
Sort Key: total_amount, book_date
Presorted Key: total_amount
−> Index Scan using bookings_total_amount_idx on bookings (co...
(4 rows)
我将在此处跳过计算的详细信息。
可以并行执行排序。也就是说，当工作线程返回其已排序的输出时，Gather 节点不会以任何方式对它们进行排序，而只会以输入的任何顺序附加输入。为了保持行的顺序，使用了另一个节点：收集合并。
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT *
FROM flights
ORDER BY scheduled_departure
LIMIT 10;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Limit (actual rows=10 loops=1)
−> Gather Merge (actual rows=10 loops=1)
Workers Planned: 1
Workers Launched: 1
−> Sort (actual rows=8 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=107434 lo...
(9 rows)
“收集合并”节点使用二进制堆对来自工作线程的行进行排序。从本质上讲，它只是合并了几组行，就像外部合并排序一样，但是在引擎盖下存在一些差异，其中之一是“收集合并”节点针对处理少量固定数量的数据源和逐个接收行进行了优化，没有块I / O。
成本估算。“收集合并”启动成本取决于子节点启动成本。与“收集”节点一样，还有工作进程启动成本，估计为parallel_setup_cost参数值。
除此之外，还有二进制堆构建成本，其中包括对 n 个项目进行排序，其中 n 是并行工作线程的数量，即 n 个日志2n. 比较运营成本估计为cpu_operator_cost乘以二。由此产生的成本通常是微不足道的，因为工人的数量永远不会那么高。
然后，总成本加上子节点的数据检索成本（由多个工作线程执行）和工作线程的数据输出成本。检索和输出成本估计为每行parallel_tuple_cost加上5%（由于可能的延迟）。
最后，还有二进制堆更新，它需要日志2n 比较操作加上辅助操作。其成本估计为每行的对数 N（2 cpu_operator_cost）+ cpu_operator_cost。
这是另一个包含“收集合并”的计划：
EXPLAIN SELECT amount, count(*)
FROM ticket_flights
GROUP BY amount;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Finalize GroupAggregate (cost=123399.62..123485.00 rows=337 wid...
Group Key: amount
−> Gather Merge (cost=123399.62..123478.26 rows=674 width=14)
Workers Planned: 2
−> Sort (cost=122399.59..122400.44 rows=337 width=14)
Sort Key: amount
−> Partial HashAggregate (cost=122382.07..122385.44 r...
Group Key: amount
−> Parallel Seq Scan on ticket_flights (cost=0.00...
(9 rows)
请注意，此处的工作线程在将结果传递到 Sort 节点之前执行部分哈希聚合。这是有效的，因为聚合减少了行数。然后，“排序”节点将输出传递到由“收集合并”节点组装的领导进程。最终聚合使用经过排序的值列表，而不是散列。
在此示例中，有三个并行进程（包括引线），因此收集合并成本的计算方法如下：
WITH costs(startup, run) AS (
SELECT round((
-- starting up the processes
current_setting('parallel_setup_cost')::real +
-- building the heap
current_setting('cpu_operator_cost')::real 2 3 * log(2, 3)
)::numeric, 2),
round((
-- transmitting the rows
current_setting('parallel_tuple_cost')::real 1.05 674 +
-- updating the heap
current_setting('cpu_operator_cost')::real 2 674 * log(2, 3) +
current_setting('cpu_operator_cost')::real * 674
)::numeric, 2)
SELECT 122399.59 + startup AS startup,
122400.44 + startup + run AS total
FROM costs;
startup | total
−−−−−−−−−−−+−−−−−−−−−−−
123399.61 | 123478.26
(1 row)
分组和不同值
前面的示例表明，聚合值的分组（以及删除重复值）既可以通过散列来完成，也可以通过排序来完成。在排序列表中，可以在单个传递中找到重复值组。
名为 Unique 的简单节点执行从给定列表中选择非重复值的任务：
EXPLAIN (costs off) SELECT DISTINCT book_ref
FROM bookings
ORDER BY book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Result
−> Unique
−> Index Only Scan using bookings_pkey on bookings
(3 rows)
聚合本身在“组聚合”节点下执行。
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)
在并行计划中，此节点将被“部分组聚合”替换，聚合将在“最终确定组聚合”下完成。
在 PostgreSQL 10 及更高版本中，当对多个集（在 GROUPING SETS 、CUB和 EROLLUP子句下）执行分组时，同一节点可以使用哈希和排序。该算法的细节太复杂，无法在本文的范围内涵盖，但我们可以看一个示例。在此计划中，分组在三个不同的列上执行，并且内存有限。
SET work_mem = '64kB';
EXPLAIN (costs off)
SELECT count(*)
FROM flights
GROUP BY GROUPING SETS (aircraft_code, flight_no, departure_airport);
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
MixedAggregate
Hash Key: departure_airport
Group Key: aircraft_code
Sort Key: flight_no
Group Key: flight_no
−> Sort
Sort Key: aircraft_code
−> Seq Scan on flights
(8 rows)
聚合节点混合聚合接收一组按aircraft_code预先排序的行。
首先，扫描集合，并按aircraft_code（组键）对行进行分组。扫描行时，将按flight_no（按内存中的快速排序（如果足够）或磁盘上的外部排序（如“排序”节点）对行进行重新排序，就像“排序”节点所做的那样）对行进行重新排序。同时，行被记录到键departure_airport下的哈希表中（内存中或磁盘上的临时文件中，就像哈希聚合一样）。
接下来，按flight_no扫描刚刚按flight_no排序的集合，并按同一键（排序键和嵌套的组键）进行分组。如果需要按另一列进行分组，则在此阶段将相应地对行进行重新排序。
最后，扫描第一步中的哈希表，并按departure_airport（哈希键）对值进行分组。
连接方法比较
有三种方法可用于连接两个数据集，每种方法都有自己的优点和缺点。
嵌套循环联接需要零设置时间，并且可以立即开始返回结果行。这是唯一不需要扫描整个集的方法，前提是索引访问可用。这些属性使嵌套循环联接（与索引一起）成为具有许多短查询一次仅返回几行的 OLTP 系统的完美选择。
当数据量增加时，该算法的缺点变得明显。对于笛卡尔积计算，算法的复杂性是二次的：成本与两个数据集大小的乘积成比例。在实践中，纯笛卡尔积计算并不经常出现。通常，每个外集行都会扫描内集索引中的一定行数，并且此数字与内集中的总行数无关（例如，每次预订的平均票数不取决于预订总数或预订的机票总数）。因此，复杂性的增加通常是线性的，而不是二次的，尽管线性系数很高。
嵌套循环连接的另一个重要特征是其多功能性。虽然其他连接方法仅支持等联接，但此算法可以对任何连接条件进行操作。这使得该算法几乎适用于任何类型的查询和条件（完全连接除外，这不能在嵌套循环中完成）。但是，请记住，大型数据集的非等连接本质上是低效的。
哈希联接是要用于大型数据集的内容。如果有足够的内存，哈希联接可以在一次传递中联接两个数据集。换句话说，它的复杂性是线性的。与顺序扫描配对的哈希联接最常见于具有处理大量数据的 OLAP 查询的环境中。
该算法不适合延迟比吞吐量更重要的用例，因为它在整个哈希表完成之前无法开始返回数据。
除此之外，哈希连接仅限于等连接。最后，您正在使用的数据类型必须是可哈希的（但这很少是问题）。
在 PostgreSQL 14 及更高版本中，嵌套循环联接偶尔会与哈希联接竞争，这要归功于 Memorize 节点（也基于哈希表）缓存内部集行的能力。在某些情况下，嵌套循环连接可以向前拉，因为它不必在哈希连接时扫描整个内部集。
合并联接适用于短 OLTP 查询和长 OLAP 查询。它具有线性复杂性（两个集合都只需扫描一次），需要很少的内存，并且可以立即开始输出。唯一需要注意的是，数据集必须预先排序。理想的情况是当输入直接来自索引扫描时。对于小行集来说，这也是一个自然的选择。对于大量数据，索引访问只有在几乎没有表访问的情况下才能保持高效。
如果没有适当的索引，则必须对数据集进行排序，并且排序具有高于线性的复杂性：O（n log2正因为如此，合并连接通常落后于哈希连接，除了输出也必须排序的情况。
合并连接不会区分内部集和外部集，这是一个不错的福利。如果计划程序错误地分配了内部和外部集，则嵌套循环连接和哈希连接的效率都将下降，而对于合并连接，这不是问题。
与哈希连接一样，合并连接只能对等连接进行操作。此外，数据类型必须具有 B 树运算符类。
下图说明了不同连接选择性值下不同连接方法的近似成本。
当选择性较高时，嵌套循环联接按索引扫描两个表，但在高选择性下，它将切换到完全扫描，并且图形变为线性。
在此示例中，哈希联接对两个表都使用完全扫描。图表上的“步骤”表示哈希表不再适合内存并且数据开始溢出到磁盘的时刻。
与索引扫描的合并联接显示，随着选择性的增加，成本略有增加。如果有足够的work_mem，哈希联接的性能优于合并联接，但是当涉及到临时文件时，合并联接会提前进行。
合并联接和排序图显示当索引扫描不可用且需要预排序时，成本如何增加。与哈希联接一样，“step”表示算法耗尽内存并开始将数据溢出到临时文件中的时刻。
这只是一个示例，图表看起来会因情况而异。
我们已阅读本系列文章的结尾！还有很多话要说，但我希望现在你已经了解了基础知识。
这个系列以及我之前的文章成为我的书“PostgreSQL内部”的基础。我们已经向公众发布了第一章，可在此处获得。非常感谢我所有的读者！您的反馈有助于我改进工作。
请继续关注更多！
原文标题：Queries in PostgreSQL: 7. Sort and merge