# 连接方法
> 比较嵌套循环、哈希和归并连接，了解 Memoize 缓存、哈希批次、并行连接计划以及连接顺序选择。
---
LLMS 索引： [llms.txt](/llms.txt)
---
## 1. 什么是连接方法 {#qpt-section-5-1}
使用前几章讨论的访问方法获取行，只是工作的一部分。我们还需要组合行集。
连接方法是组合两个行集的一种算法。PostgreSQL 不仅使用这些算法实现 SQL `JOIN` 操作，也用它们实现其他 SQL 结构，例如 `EXISTS`。这里有两个不同的层次：**SQL 连接**是一种逻辑操作，用来定义哪些行属于结果；连接**方法**则是高效产生该结果的一种可能的物理算法。
我们经常说 PostgreSQL 连接表。这是一种方便的简写，但执行器实际连接的是行集。行集可以通过访问方法直接来自表，也可以是另一个连接、聚合、子查询或其他计划子树的结果。
连接是二元的：每个连接节点组合两个输入。对于普通内连接，多个关系的连接顺序通常不会改变逻辑结果，但可能显著改变性能。一个物理连接的两个输入顺序也可能影响性能。
PostgreSQL 有三种主要连接方法：嵌套循环、哈希连接和归并连接。
## 2. 嵌套循环连接 {#qpt-section-5-2}
基本的嵌套循环算法很简单：对于一个输入中的每一行，扫描另一个输入，并返回匹配的行。从概念上看，它就是两个嵌套循环，因此得名。
第一个输入通常称为**外部**输入（outer input），第二个输入称为**内部**输入（inner input）。当 PostgreSQL 可以使用当前外部行中的值，在内部输入中执行廉价查找时，嵌套循环尤其有吸引力。索引就是典型例子。如果内部一侧必须针对每个外部行从头到尾扫描，那么可能会多次检查同一批无关的行。
对于非常小的输入，即使重复扫描也可能很便宜。下面是一个小结果集的典型嵌套循环计划。我们查找属于两张机票的航段：
```sql
EXPLAIN (costs off) SELECT *
FROM tickets t
JOIN segments tf ON tf.ticket_no = t.ticket_no
WHERE t.ticket_no IN ('0005432312163','0005432312164');
QUERY PLAN
------------------------------------------------------------
Nested Loop
-> Index Scan using tickets_pkey on tickets t
Index Cond: (ticket_no = ANY ('{0005432312163,000...
-> Index Scan using segments_pkey on segments tf
Index Cond: (ticket_no = t.ticket_no)
(5 rows)
```
> [!NOTE]
> 外部输入：tickets t 上的 Index Scan。内部输入：segments tf 上的 Index Scan。
{#qpt-fig-5-1 num="5.1" caption="嵌套循环连接" .book-original-figure .d-flex .flex-column .align-items-center width=428 height=139}
这是一个**参数化**嵌套循环。外部 `Index Scan` 产生一行机票数据。该行中的 `t.ticket_no` 值会成为对 `segments` 执行内部 `Index Scan` 时的一个参数。在每次迭代中，内部查找实际上会使用类似 `ticket_no` = 常量的条件执行。
这个过程会持续到外部输入耗尽。
现在考虑另一个嵌套循环。我们列出航程足以覆盖两个所需距离的飞机：
```sql
EXPLAIN (costs off) SELECT *
FROM ( VALUES (1000), (10000) ) d(range)
JOIN airplanes a ON a.range >= d.range;
QUERY PLAN
-------------------------------------------------
Nested Loop
Join Filter: (ml.range >= "*VALUES*".column1)
-> Seq Scan on airplanes_data ml
-> Materialize
-> Values Scan on "*VALUES*"
(5 rows)
```
这个连接**不是参数化的**。内部输入没有使用从当前外部行推导出的访问条件。相反，内部行集会被反复读取，并由 `Join Filter` 检查行对。`Materialize` 保留很小的 `VALUES` 结果，以便重复扫描，因此 PostgreSQL 不必在每次迭代时都从头构造它。从概念上说，这是先做笛卡尔积，再进行过滤。
嵌套循环不要求存在相等条件。它基本上可以实现 PostgreSQL 能够计算的任何连接谓词。
### Memoize {#qpt-p88-memoize}
如果参数化的内部查找会以相同的参数值执行很多次，重复完成相同工作就很浪费。PostgreSQL 可以把结果缓存在放置于内部计划之上的 `Memoize` 节点中。
如果规划器的估计错误地表明记忆化（memoization）有益，可以使用 `enable_memoize = off` 将其禁用。
考虑 routes 和 airports 之间的连接：
```sql
EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT * FROM routes r
JOIN airports a ON a.airport_code = r.departure_airport
WHERE r.departure_airport in ('BOM', 'SVO');
QUERY PLAN
------------------------------------------------------------
Nested Loop (actual rows=108.00 loops=1)
-> Bitmap Heap Scan on routes r (actual rows=108.00 l...
Recheck Cond: (departure_airport = ANY
('{BOM,SVO}'::bpchar[]))
Heap Blocks: exact=33
-> Bitmap Index Scan on routes_departure_airport_...
Index Cond: (departure_airport = ANY
('{BOM,SVO}'::bpchar[]))
Index Searches: 2
-> Memoize (actual rows=1.00 loops=108)
Cache Key: r.departure_airport
Cache Mode: logical
Hits: 106 Misses: 2 Evictions: 0 Overflows: 0
Memory Usage: 1kB
-> Index Scan using airports_data_pkey on airport...
Index Cond: (airport_code =
r.departure_airport)
Index Searches: 2
(18 rows)
```
> [!NOTE]
> 缓存：Memoize。内部输入：airports_data 上的 Index Scan。
{#qpt-fig-5-2 num="5.2" caption="Memoize" .book-original-figure .d-flex .flex-column .align-items-center width=428 height=332}
这个例子经过有意选择，使得只有两个非重复的参数值到达内部一侧：`BOM` 和 `SVO`。
每个值的第一次查找都会发生缓存未命中：`Misses: 2`。
其余 106 次查找都由缓存提供：`Hits: 106`。
没有条目需要被驱逐（`Evictions: 0`），没有缓存结果溢出其空间（`Overflows: 0`），缓存只使用了 1 kB。
在内部，缓存以内部扫描的参数值为键。如果外部一侧重复使用相同的键，`Memoize` 就可以把重复的内部扫描变成廉价的缓存查找。
### 执行代价 {#qpt-p90-execution-cost}
一个好的第一近似是 \\(N \times \operatorname{cost}(\text{inner probe})\\)，其中 N 是外部行数。如果内部一侧每次都被完整重新扫描，并且包含大约 M 行，那么这就变成了熟悉的 \\(O(N \times M)\\) 比较模式。
不过，对于参数化嵌套循环，一次内部探测的代价可能远小于扫描 M 行的代价。例如，唯一 B-树查找经过一次很短的树下降后，至多可以找到一个匹配行。重复探测也可能受益于缓存或 `Memoize`。
当外部输入很小，并且内部输入的行可以廉价访问时，嵌套循环连接很有效。特别是，这种方法与索引访问结合使用，是 OLTP 查询的典型方式，适合快速返回少量行。
### 并行计划中的嵌套循环 {#qpt-p90-nested-loop-in-parallel-plans}
嵌套循环可以参与并行计划。
多个工作进程会并行扫描外部行集。每个工作进程接收一些外部行，并独立执行相应的内部扫描。
查找与低价航段关联的机票：
```sql
EXPLAIN (costs off)
SELECT t.ticket_no, s.price
FROM tickets t
JOIN segments s ON s.ticket_no = t.ticket_no
WHERE s.price < 1000;
```
```text
QUERY PLAN
----------------------------------------------------------
Gather
Workers Planned: 2
-> Nested Loop
-> Parallel Seq Scan on segments s
Filter: (price < '1000'::numeric)
-> Index Only Scan using tickets_pkey on tickets t
Index Cond: (ticket_no = s.ticket_no)
(7 rows)
```
> [!NOTE]
> 外部输入：segments s 上的 Parallel Seq Scan。内部输入：tickets t 上的 Index Only Scan。
{#qpt-fig-5-3 num="5.3" caption="并行计划中的嵌套循环" .book-original-figure .d-flex .flex-column .align-items-center width=428 height=169}
每个参与的进程都会扫描 `segments` 的一部分。对于每个符合条件的航段，它都会在 `tickets` 中执行一次自己的仅索引查找。内部一侧不会因为外部扫描是并行的就自动共享；每个进程都会为分配给它的外部行执行内部计划。
## 3. 哈希连接 {#qpt-section-5-3}
### 单批次哈希连接 {#qpt-p91-single-batch-hash-join}
在**构建阶段**（build phase），PostgreSQL 读取内部行，并根据连接键计算哈希值。
内存中的哈希表保存连接在后续阶段所需的数据：哈希值，以及连接本身或其上方节点所需的内部行投影数据。
哈希操作的内存预算基于 `work_mem` × `hash_mem_multiplier`。
对于串行哈希连接，最佳情况是完整哈希表能够放进这个预算。在这种情况下，`EXPLAIN ANALYZE` 会报告 `Batches: 1`。
在**探测阶段**（probe phase），PostgreSQL 按顺序读取外部输入。对于每个外部行，它计算相应的哈希值，定位候选桶，然后检查实际的连接条件。
仅检查哈希码是不够的。首先，查询中的并非所有连接条件都能用于哈希连接：由于哈希函数不保持值的顺序，哈希连接只支持等值连接。其次，冲突是可能发生的，不同的值可能得到相同的哈希码。发生冲突的概率很小，但不能排除。
下面的例子需要两个输入的大部分内容，因此哈希连接是自然的选择：
```sql
EXPLAIN (costs off)
SELECT *
FROM airplanes a
JOIN seats s ON a.airplane_code = s.airplane_code;
QUERY PLAN
---------------------------------------------------
Hash Join
Hash Cond: (s.airplane_code = ml.airplane_code)
-> Seq Scan on seats s
-> Hash
-> Seq Scan on airplanes_data ml
(5 rows)
```
> [!NOTE]
> 哈希表：airplanes_data 上的 Seq Scan 之上的 Hash 节点。
{#qpt-fig-5-4 num="5.4" caption="单批次哈希连接" .book-original-figure .d-flex .flex-column .align-items-center width=428 height=132}
`Hash Join` 首先请求其 `Hash` 子节点读取内部输入并构建哈希表。然后它读取外部输入并探测该表，在找到匹配项时返回它们。
运行查询：
```sql
EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT *
FROM airplanes a
JOIN seats s ON a.airplane_code = s.airplane_code;
```
```text
QUERY PLAN
------------------------------------------------------------
Hash Join (actual rows=1741.00 loops=1)
Hash Cond: (s.airplane_code = ml.airplane_code)
-> Seq Scan on seats s (actual rows=1741.00 loops=1)
-> Hash (actual rows=10.00 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 10kB
-> Seq Scan on airplanes_data ml (actual rows=10....
Planning Time: 0.047 ms
Execution Time: 1.255 ms
(8 rows)
```
哈希表可以放进内存。它使用 1024 个桶，约占 10 kB。规划器选择小得多的 `airplanes_data` 输入作为构建侧。
规划器选择小得多的 `airplanes_data` 输入作为构建侧。
### 多批次哈希连接 {#qpt-p93-multi-batch-hash-join}
如果规划器估计哈希表无法放进大小为 `work_mem` × `hash_mem_multiplier` 的内存中，就会把内部输入划分成多个**批次**，分别处理每个批次。和桶的数量一样，批次的数量总是 2 的幂；批次编号由哈希值中的若干位决定。可能彼此匹配的行总是属于同一个批次。理想情况下，每个批次包含大致相同数量的行，但如果行中的值重复，就可能出现偏斜。
规划查询时，会预先计算所需的最小批次数，以便每个批次的哈希表都能放入内存。即使规划器的估计后来被证明过于保守，这个数量也不会减少，但需要时可以动态增加。
首先，PostgreSQL 读取内部输入并构建哈希表。属于第一个批次的行保留在内存中。属于其他批次的行则写入不同的临时文件。
然后 PostgreSQL 读取外部输入。属于第一个批次的行会立即与内存中的第一个哈希表批次匹配。属于其他批次的行会写入不同的临时文件。因此，对于 N 个批次，最多会使用 \\(2(N-1)\\) 个临时文件；如果某些批次为空，实际使用的文件可能更少。
会话中临时文件使用的磁盘空间受 `temp_file_limit` 的值限制；临时表不包含在这个限制中。
之后，哈希表占用的内存会被释放。此时，连接已经得到第一个批次的部分结果。
接着 PostgreSQL 逐个处理保存在磁盘上的批次。它从临时文件把某个批次的内部行加载进哈希表，从另一个临时文件读取匹配的外部行，然后将它们连接起来。已经处理过的临时文件会被删除。这个过程会重复，直到所有批次都完成连接。
连接 `bookings` 和 `tickets` 这两张大表：
```sql
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT *
FROM bookings b
JOIN tickets t ON b.book_ref = t.book_ref;
```
```text
QUERY PLAN
------------------------------------------------------------
Hash Join (actual rows=5598473.00 loops=1)
Hash Cond: (t.book_ref = b.book_ref)
Buffers: shared hit=15839 read=57833 written=2, temp
read=60337 written=60337
-> Seq Scan on tickets t (actual rows=5598473.00 loop...
Buffers: shared read=57816 written=2
-> Hash (actual rows=2486710.00 loops=1)
Buckets: 131072 Batches: 32 Memory Usage: 5155kB
Buffers: shared hit=15839 read=17, temp
written=12364
-> Seq Scan on bookings b (actual rows=2486710.00...
Buffers: shared hit=15839 read=17
Planning:
Buffers: shared hit=34 read=14
(14 rows)
```
哈希连接使用 32 个批次。`Hash` 节点会溢出构建侧数据，而在处理这些批次时，`Hash Join` 节点也会读写临时数据。
现在只返回一列：
```sql
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT b.book_ref
FROM bookings b
JOIN tickets t ON b.book_ref = t.book_ref;
QUERY PLAN
------------------------------------------------------------
Hash Join (actual rows=5598473.00 loops=1)
Hash Cond: (t.book_ref = b.book_ref)
Buffers: shared hit=15950 read=57722, temp read=25850
written=25850
-> Seq Scan on tickets t (actual rows=5598473.00 loop...
Buffers: shared hit=94 read=57722
-> Hash (actual rows=2486710.00 loops=1)
Buckets: 262144 Batches: 32 Memory Usage: 5002kB
Buffers: shared hit=15856, temp written=7927
-> Seq Scan on bookings b (actual rows=2486710.00...
Buffers: shared hit=15856
Planning:
Buffers: shared hit=18
(13 rows)
```
内存消耗降低了，因为现在哈希表只包含一个字段，而不是构成 `bookings` 表一行的三个字段。
因此，下面两点很重要：
- 只有实际需要的字段才应放进哈希表；
- 哈希表应在较小的输入上构建。
第一点是查询作者的责任，第二点是规划器的责任。
### 执行代价 {#qpt-p96-execution-cost}
如果哈希分布良好且哈希表位于内存中，构建和探测的基本工作量预计大致与两个输入大小之和 \\(N+M\\) 成正比。
不过，哈希表必须构建完成后连接才能开始，因此对于少量行，嵌套循环更高效。
哈希连接与整表扫描结合，典型用于处理大量行的 OLAP 查询；这类查询更重视总体吞吐量，而不是响应时间。
### 并行哈希连接 {#qpt-p96-parallel-hash-join}
与其他连接方法不同，哈希连接不仅可以参与并行计划，还拥有高效的并行感知算法。它会将连接的两个阶段都并行化：从内部输入构建哈希表，以及使用外部输入的行探测哈希表。该功能由 `enable_parallel_hash` 控制，默认启用。
在这种情况下，内存预算是 `work_mem` × `hash_mem_multiplier` × 进程数。所有进程都可以协助扫描内部输入并构建一张共享哈希表。构建阶段完成后，它们协作扫描外部输入并探测这张共享表。
增加每个进程可用于构建哈希表的内存量，并运行聚合查询：
```sql
SET work_mem = '32MB';
EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT count(*)
FROM bookings b
JOIN tickets t ON b.book_ref = t.book_ref;
QUERY PLAN
------------------------------------------------------------
Finalize Aggregate (actual rows=1.00 loops=1)
-> Gather (actual rows=3.00 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Partial Aggregate (actual rows=1.00 loops=3)
-> Parallel Hash Join (actual rows=1866157.67...
Hash Cond: (t.book_ref = b.book_ref)
-> Parallel Seq Scan on tickets t (actual...
-> Parallel Hash (actual rows=828903.33 l...
Buckets: 4194304 Batches: 1 Memory
Usage: 130080kB
-> Parallel Seq Scan on bookings b (a...
Planning Time: 0.161 ms
Execution Time: 625.430 ms
(14 rows)
```
注意，分配的内存超过了单个进程的预算：在这个例子中，`work_mem` × `hash_mem_multiplier` = 64 MB。`Batches: 1` 表明连接保持为**单批次**。
如果并行进程合计可用的内存仍不足以容纳整个哈希表，PostgreSQL 会使用**多批次**并行算法。
首先，进程并行读取内部输入，将其划分为批次，并把批次写入临时文件。与串行算法不同，包括第一个批次在内的所有批次都会写入磁盘：每个进程只读取内部输入的一部分，因此没有任何一个进程单独拥有完整批次。
之后，外部输入也会并行读取、划分为批次并写入临时文件。外部输入读取完成后，对于 N 个批次会有 2N 个临时文件：每个批次各有一个内部文件和一个外部文件。
然后，每个进程选择一个尚未处理的批次，将该批次的内部行加载进哈希表，读取对应的外部行，并执行连接。在多批次算法中，每个进程都有一张大小为 `work_mem` × `hash_mem_multiplier` 的哈希表，但这些表位于共享内存中，这意味着每个并行工作进程都可以访问每张表。
一个进程完成一个批次后，会选择另一个批次。如果没有未处理的批次，空闲进程可以协助处理其他进程尚未完成的批次，因为哈希表位于共享内存中。
使用多张较小的哈希表可以让协调更简单。与让所有进程共同使用一张大型共享哈希表相比，这种方式也能减少同步开销。
降低内存设置：
```sql
SET work_mem = '16MB';
```
运行同一查询：
```sql
EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT count(*)
FROM bookings b
JOIN tickets t ON b.book_ref = t.book_ref;
QUERY PLAN
------------------------------------------------------------
Finalize Aggregate (actual rows=1.00 loops=1)
-> Gather (actual rows=3.00 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Partial Aggregate (actual rows=1.00 loops=3)
-> Parallel Hash Join (actual rows=1866157.67...
Hash Cond: (t.book_ref = b.book_ref)
-> Parallel Seq Scan on tickets t (actual...
-> Parallel Hash (actual rows=828903.33 l...
Buckets: 1048576 Batches: 8 Memory
Usage: 20416kB
-> Parallel Seq Scan on bookings b (a...
Planning Time: 0.112 ms
Execution Time: 647.388 ms
(14 rows)
```
连接现在使用八个批次。
## 4. 归并连接 {#qpt-section-5-4}
第三种主要连接方法是归并连接。归并连接利用有序输入。如果两个行集都按兼容的连接键排序，PostgreSQL 就可以按键顺序推进它们，并组合匹配的组。`Gather Merge` 节点的工作方式类似：它把已经排序的流合并成一个有序流。
排序可能很昂贵——比较排序通常为 \\(O(N \log N)\\)——但并不总是需要显式排序。
B-树索引可能已经提供了所需顺序，或者较早的计划节点可能保留了这个顺序。
一个简化的思维模型是：当前键较小的输入不断前进，直到其键值追上另一侧。当键相等时，就产生匹配行。重复的连接键会使这个模型复杂一些。如果一侧或两侧输入都包含多个相同键的行，PostgreSQL 必须为该键产生所有匹配组合。
考虑一个连接，其中两个输入已经具有所需的顺序：
```sql
EXPLAIN (costs off) SELECT *
FROM tickets t
JOIN segments 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 segments_pkey on segments tf
(4 rows)
```
> [!NOTE]
> 一个输入：tickets t 上的 Index Scan。另一个输入：segments tf 上的 Index Scan。
{#qpt-fig-5-5 num="5.5" caption="归并连接" .book-original-figure .d-flex .flex-column .align-items-center width=428 height=126}
归并连接的一个重要性质是，它按排序顺序返回连接结果。特别是，得到的行集可以在无需再次排序的情况下用于另一个归并连接；也可以像这个例子一样，直接返回给客户端。
下面的例子中，一个 `Merge Join` 从另一个 `Merge Join` 接收已经排序的行集：
```sql
EXPLAIN (costs off)
SELECT t.ticket_no, bp.flight_id, bp.seat_no
FROM tickets t
JOIN segments 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;
```
```text
QUERY PLAN
------------------------------------------------------------
Merge Join
Merge Cond: (tf.ticket_no = t.ticket_no)
-> Merge Join
Merge Cond: ((tf.ticket_no = bp.ticket_no) AND (t...
-> Index Only Scan using segments_pkey on segment...
-> Index Scan using boarding_passes_pkey on board...
-> Index Only Scan using tickets_pkey on tickets t
(7 rows)
```
这里，`segments` 与 `boarding_passes` 连接，然后 `tickets` 再与这个已经按机票号排序的行集连接。
### 执行代价 {#qpt-p101-execution-cost}
如果两个输入都已经按归并键排序，基本的归并过程与输入大小成线性关系：\\(O(N+M)\\)。与哈希连接不同，归并连接不需要先构建哈希表。因此，归并连接既可以在 OLTP 查询中工作，也可以在 OLAP 查询中工作。
不过，如果需要排序，代价会与 N log N 成正比；对于大量数据，这种方法很可能输给哈希连接。
### 并行计划中的归并连接 {#qpt-p101-merge-join-in-parallel-plans}
归并连接可以参与并行计划，但 `Merge Join` 节点本身并不是一种与 `Parallel Hash Join` 同意义上的并行感知连接算法。
一种常见模式是：并行扫描一个输入，同时每个工作进程独立读取另一个完整输入，直到找到自己需要的匹配行。
对于大型连接，这种重复工作可能使并行哈希连接更有吸引力，因为并行哈希连接的设计就是为了共享构建工作和探测工作。
创建一个索引，让 PostgreSQL 能够廉价地按 `book_ref` 顺序获取 `tickets`：
```sql
CREATE INDEX ON tickets(book_ref);
```
现在考虑：
```sql
EXPLAIN (costs off) SELECT count(*)
FROM bookings b
JOIN (
SELECT book_ref FROM tickets GROUP BY book_ref
) t ON b.book_ref = t.book_ref;
QUERY PLAN
------------------------------------------------------------
Finalize Aggregate
-> Gather
Workers Planned: 2
-> Partial Aggregate
-> Merge Join
Merge Cond: (b.book_ref = tickets.book_ref)
-> Parallel Index Only Scan using booking...
-> Group
Group Key: tickets.book_ref
-> Index Only Scan using tickets_book...
(10 rows)
```
`bookings_pkey` 的扫描是并行的。不过，`tickets` 上的分组子查询会由每个执行归并连接的参与进程独立读取。
移除演示索引：
```text
DROP INDEX tickets_book_ref_idx;
DROP INDEX
```