本章目录

第 5 章：连接方法

5.1 什么是连接方法

通过前面几章讨论的访问方法获取行，只完成了一部分工作。我们还需要将行集组合起来。

连接方法是组合两个行集的算法。PostgreSQL 不仅用这些算法实现 SQL JOIN 操作，也用它们处理 EXISTS 等其他 SQL 结构。这里有两个不同的层次：SQL 连接是逻辑操作，定义哪些行应当包含在结果中；连接方法则是高效生成该结果的一种物理算法。

我们经常说 PostgreSQL 连接表。这是一种便于表达的简称，但执行器实际连接的是行集。一个行集可以通过访问方法直接来自表，也可以是另一个连接、聚合、子查询或其他计划子树的结果。

连接是二元操作：每个连接节点都组合两个输入。对于普通的内连接，多个关系的连接顺序通常不改变逻辑结果，却可能极大地影响性能。同一个物理连接中，两个输入的先后顺序也可能很重要。

PostgreSQL 主要有三种连接方法：嵌套循环连接、哈希连接和归并连接。

5.2 嵌套循环连接

嵌套循环的基本算法很简单：对于一个输入中的每一行，扫描另一个输入，并返回匹配的行。从概念上看，这就是两个嵌套的循环，名称也由此而来。

第一个输入通常称为外集合，第二个称为内集合。如果 PostgreSQL 能利用外集合当前行中的值，以很低的成本在内集合中查找，嵌套循环就尤其有吸引力。索引是典型的例子。如果外集合的每一行都要求从头到尾扫描内集合，同样的无关行就可能被反复检查。

对于很小的输入，即使重复扫描，成本也可能很低。下面是一个返回少量结果的典型嵌套循环计划。我们查找两张机票对应的航段：

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)

这是一个参数化的嵌套循环连接。外集合的 Index Scan 返回一行机票数据，该行的 t.ticket_no 值成为内集合中 segments 的 Index Scan 的参数。每次迭代时，内集合中的查找实际上都采用 ticket_no = constant 这样的条件。这个过程持续到外集合读取完毕。

再看另一个嵌套循环。对于两个给定距离，我们分别列出航程足够的飞机：

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 能够求值的连接谓词，基本都可以由它实现。

5.2.1 缓存行 (Memoize)

如果参数化的内集合查找多次使用相同的参数值，反复执行同样的工作就会造成浪费。PostgreSQL 可以在内集合计划上方放置 Memoize 节点，缓存这些查找结果。

如果规划器的估算错误地认为缓存行会有收益，可以将 enable_memoize 设为 off 来禁用它。

来看 routes 和 airports 的连接：

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)

这个例子是特意选择的：传给内集合的参数只有 BOM 和 SVO 两个非重复值。

每个值的首次查找都未命中缓存，因此 Misses: 2。

其余 106 次查找都由缓存提供结果，因此 Hits: 106。

没有条目需要被逐出 (Evictions: 0)，也没有某个参数对应的缓存结果超出可用空间 (Overflows: 0)，整个缓存只使用了 1 kB。

在内部，缓存以内集合扫描的参数值为键。如果外集合反复出现相同的键，Memoize 就可以将重复的内集合扫描转变为成本很低的缓存查找。这里实际执行内集合查找的是 Memoize 下方的 Index Scan。

5.2.2 执行成本

一个有用的初步近似是 N×cost(inner probe)N \times \operatorname{cost}(\text{inner probe})，其中 N 为外集合的行数，cost(inner probe) 为一次内集合查找的成本。如果每次都完整地重新扫描内集合，而内集合大约有 M 行，就得到熟悉的 O(N×M)O(N \times M) 比较模式。

不过，对于参数化的嵌套循环，一次内集合查找的成本可能远小于扫描 M 行。例如，沿唯一 B 树索引经过很短的向下查找，就能找到至多一行匹配结果。重复查找还可能受益于缓存或 Memoize。

当外集合较小，而访问内集合中的行成本很低时，嵌套循环连接很有效。尤其是结合索引访问时，它是 OLTP 查询中的典型方法：这类查询需要快速返回少量行。

5.2.3 并行计划中的嵌套循环

嵌套循环可以参与并行计划。

多个工作进程并行扫描外集合。每个工作进程获取一部分外集合行，并独立执行相应的内集合扫描。

查找低价航段对应的机票：

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;

                        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)

每个参与进程扫描 segments 的一部分。对于每个满足条件的航段，它都在 tickets 中独立执行一次仅索引查找。外集合的扫描是并行的，并不意味着内集合也自动变成共享的；每个进程都要针对分配给自己的外集合行执行内集合计划。

5.3 哈希连接

5.3.1 单批次哈希连接

在构建阶段，PostgreSQL 读取内集合中的行，并根据连接键计算哈希值。

内存中的哈希表保存连接后续需要的数据：哈希值，以及连接本身或上层节点所需的内集合行的投影数据。

哈希操作的内存额度基于 work_mem × hash_mem_multiplier。

对于串行哈希连接，最理想的情况是整个哈希表都能放入这一额度内。此时，EXPLAIN ANALYZE 会显示 Batches: 1。

在探测阶段，PostgreSQL 顺序读取外集合。对于外集合中的每一行，它都会计算相应的哈希值，定位候选桶，然后检查实际的连接条件。

仅检查哈希码还不够。首先，并非查询中的所有连接条件都能用于哈希连接：哈希函数不保留值的顺序，因此哈希定位需要使用等值连接键。 其次，不同的值可能得到相同的哈希码，也就是发生哈希冲突。发生的概率虽然较小，但不能排除。

下面的例子需要读取两个输入中的大部分数据，因此选择哈希连接很自然：

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)

Hash Join 首先让其 Hash 子节点读取内集合并构建哈希表，然后读取外集合，在哈希表中查找匹配项，找到后就返回。

运行查询：

EXPLAIN (analyze, costs off, timing off, buffers off)
SELECT *
FROM airplanes a
  JOIN seats s ON a.airplane_code = s.airplane_code;

                         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 作为构建侧输入。

5.3.2 多批次哈希连接

如果规划器估算哈希表无法放入 work_mem × hash_mem_multiplier 大小的内存，就会将内集合划分为多个批次，分别处理。与桶数一样，批次数始终是 2 的幂；批次编号由哈希值中的若干位决定。可能相互匹配的行总是属于同一个批次。理想情况下，各批次的行数大致相同，但如果行中的值有重复，就可能出现数据倾斜。

规划查询时，会预先计算所需的最少批次数，使每个批次对应的哈希表能够放入内存。即使后来发现规划器的估算偏保守，这个批次数也不会减少，但会根据需要动态增加。

首先，PostgreSQL 读取内集合并构建哈希表。属于第一个批次的行保留在内存中，其他批次的行则分别写入临时文件。

然后，PostgreSQL 读取外集合。属于第一个批次的行会立即与内存中的第一批哈希表匹配；属于其他批次的行则分别写入临时文件。因此，N 个批次最多使用 2(N−1)2(N-1) 个临时文件；如果有空批次，文件数可能更少。

单个进程使用的临时文件总空间受 temp_file_limit 限制；临时表不计入这一限制。

随后释放哈希表占用的内存。此时，连接已经得到第一个批次的部分结果。

接下来，PostgreSQL 逐个处理保存在磁盘上的批次：从临时文件中将该批次的内集合行载入哈希表，从另一个临时文件中读取对应的外集合行，然后进行连接。已处理的临时文件会被删除。这个过程不断重复，直到所有批次都完成连接。

连接 bookings 和 tickets 这两张大表：

EXPLAIN (analyze, costs off, timing off, summary off)
SELECT *
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=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 节点也会读写临时数据。

现在只返回一列：

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 表中一行的三个字段。

因此，下面两点很重要：

  • 只将真正需要的字段放入哈希表。
  • 在较小的输入上构建哈希表。

第一点是查询编写者的责任，第二点则由规划器负责。

5.3.3 执行成本

如果哈希值分布均匀，且哈希表能够放入内存，构建和探测的基本工作量预期大致与 N+MN+M 成正比，其中 N 和 M 分别为两个输入的规模。

不过，开始连接之前必须先构建哈希表，因此对于少量行，嵌套循环更高效。

哈希连接结合全表扫描，是 OLAP 查询中的典型方式。这类查询处理大量行，更看重总体吞吐量，而不是响应时间。

5.3.4 并行哈希连接

与其他连接方法不同，哈希连接不仅可以参与并行计划，还具有高效的并行协作算法。它会将连接的两个阶段都并行化：从内集合构建哈希表，以及利用外集合中的行探测哈希表。该功能由 enable_parallel_hash 控制。

此时的内存额度为 work_mem × hash_mem_multiplier × 进程数。所有进程都可以参与扫描内集合，并共同构建一张共享哈希表。构建阶段完成后，它们再协作扫描外集合，探测这张共享哈希表。

增加每个进程可用于构建哈希表的内存，然后运行一个聚合查询：

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 的哈希表，但这些表位于共享内存中，因此每个并行工作进程都可以访问各张哈希表。

一个进程完成某个批次后，就选择下一个批次。如果已经没有尚未开始处理的批次，空闲进程可以帮助处理另一个进程尚未完成的批次，因为哈希表位于共享内存中。

与让所有进程共同处理一张大型共享哈希表相比，采用多张较小的哈希表可以简化协调，减少同步开销。

减小内存设置：

SET work_mem = '16MB';

运行相同的查询：

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)

这次连接使用了八个批次。

5.4 归并连接

第三种主要的连接方法是归并连接。它利用有序输入：如果两个行集已经按相容的连接键排序，PostgreSQL 就可以按键的顺序推进两个输入，组合匹配的行组。Gather Merge 节点的工作方式与此相似：它将已经有序的多个数据流归并成一个有序数据流。

排序的成本可能很高，基于比较的排序通常需要 O(NlogN)O(N \log N) 的工作量，但不一定需要显式排序。B 树索引可能已经提供了所需的顺序，前面的计划节点也可能保留了这一顺序。

可以用一个简化过程来理解归并连接：当前键较小的输入向前推进，直到两个键相同；键相等时，就生成匹配的行。重复的连接键会让这一过程复杂一些。如果一个或两个输入中有多行具有相同的键，PostgreSQL 就必须生成该键对应的所有匹配组合。

来看一个两个输入都已经具有所需顺序的连接：

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)

本例利用了归并连接的一个重要性质：按排序顺序返回连接结果。 因此，生成的行集可以直接用于另一次归并连接，无须额外排序；也可以像本例一样直接返回给客户端。

在下一个例子中，一个 Merge Join 从另一个 Merge Join 接收有序行集：

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;

                         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 与这个已经按机票号排序的行集连接。

5.4.1 执行成本

如果两个输入都已经按归并键排序，基本归并过程的工作量与输入规模呈线性关系，即 O(N+M)O(N+M)。与哈希连接不同，归并连接无须先构建哈希表。因此，它既可以用于 OLTP 查询，也可以用于 OLAP 查询。

不过，如果需要排序，成本就会与 NlogNN \log N 成正比。对于大量数据，这种方法很可能不如哈希连接。

5.4.2 并行计划中的归并连接

归并连接可以参与并行计划，但 Merge Join 节点本身并不像 Parallel Hash Join 那样，是一种支持并行协作的连接算法。

一种常见的执行方式是并行扫描一个输入，另一个输入则不作并行划分，每个工作进程都独立读取其中的数据，直到找到自己所需的匹配项。

对于大型连接，这些重复工作可能使并行哈希连接更有吸引力，因为并行哈希在设计上就让各进程共同承担构建和探测工作。

创建一个索引，使 PostgreSQL 能以较低成本按 book_ref 顺序获取 tickets：

CREATE INDEX ON tickets(book_ref);

现在来看下面的查询：

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 上的分组子查询，每个执行归并连接的参与进程都会独立读取它。

删除演示用的索引：

DROP INDEX tickets_book_ref_idx;
DROP INDEX