21 嵌套循环

PostgreSQL 18 · 基于俄文 PG18 原版的简体中文译本

简体中文 · PG14 English · PG14简体中文 · PG18Русский · PG18

21.1. 连接类型和方式

连接 — SQL 语言的关键功能，是其灵活性和强大性的基础。来自表的行集（或作为其他操作结果获得的行集）始终成对连接。

存在多种 连接类型。

内连接。 内连接（INNER JOIN，或简写为 JOIN）包含两个行集中的行对，这些行对满足 连接条件。连接条件将一个行集的某些列与另一个行集的某些列关联起来；所有参与的列构成 连接键。

如果连接条件要求两个行集中对应列的值相等，则该连接称为 等值连接；这是最常见的场景。

笛卡尔积（CROSS JOIN）包含两个行集的所有可能行对——这是连接条件恒为真时的内连接特例。

外连接。 左外连接（LEFT OUTER JOIN，或简写为 LEFT JOIN）在内连接的基础上，添加了左行集中未在右行集中找到匹配项的行（右行集中缺失的列将获得空值）。

右外连接（RIGHT JOIN）的情况与此类似，仅行集顺序相反。

全外连接（FULL JOIN）结合了左外连接和右外连接，同时添加了左行集和右行集中未找到匹配项的行。

半连接与反连接。 半连接 类似于内连接，但仅包含在另一个行集中存在匹配项的行集中的行（即使存在多个匹配项，该行也仅在结果中出现一次）。

反连接 包含在另一个行集中未找到匹配项的行集中的行。

SQL 语言中没有显式的半连接和反连接操作，但诸如 EXISTS 和 NOT EXISTS 等结构可实现类似效果。

所有这些操作都是逻辑操作。例如，内连接常被描述为：在笛卡尔积中仅保留满足连接条件的行。但物理上，内连接通常可通过更高效的方式实现。

PostgreSQL 提供了多种 连接方式：

嵌套循环连接（nested loop）；
哈希连接（hash join）；
合并连接（merge join）。

连接方式是实现 SQL 逻辑连接操作的算法。这些基础算法常有针对特定连接类型的变体，尽管未必支持所有类型。例如，嵌套循环既可用于内连接（此时计划节点为 Nested Loop），也可用于左外连接（计划节点为 Nested Loop Left Join），但无法用于全外连接。

此外，同一算法的变体也可用于执行其他操作，例如聚合。

与访问方法类似，连接方式在不同场景下的表现各异；查询规划器会选择成本最低的方案。

21.2. 嵌套循环连接

嵌套循环连接的基本算法如下：在外层循环中遍历第一个行集（称为 外部行集）。对于每个外部行集中的行，在内层循环中遍历第二个行集（称为 内部行集），筛选出满足连接条件的行。每找到一对匹配行，立即作为结果的一部分返回¹。

该算法访问内部行集的次数等于外部行集的行数。因此，嵌套循环连接的效率受以下因素影响：

外部行集的基数；
内部行集是否存在可高效获取所需行的访问方法；
对内部行集相同行的重复访问。

笛卡尔积

嵌套循环连接是执行笛卡尔积的最有效方式，无论行集大小如何：

=> EXPLAIN SELECT * FROM aircrafts_data a1
  CROSS JOIN aircrafts_data a2
WHERE a2.range > 5000;
                     QUERY PLAN
-----------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1                 ← внешний набор
       (cost=0.00..1.09 rows=9 width=72)
   -> Materialize  (cost=0.00..1.14 rows=5 width=72)
       -> Seq Scan on aircrafts_data a2             ← внутренний набор
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(7 rows)

Nested Loop 节点使用嵌套循环算法执行连接。它始终有两个子节点。计划输出中位于上方的节点表示外部行集；位于下方的节点表示内部行集。

在此例中，内部行集由 Materialize 节点表示²。该节点将下层节点返回的行进行物化，使得后续访问时无需重新扫描整个表，可直接读取已保存的、满足条件的行。（参见 338）

相同类型的计划也可能由普通等值连接查询产生：

=> EXPLAIN SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.ticket_no = '0005432000284';
                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..25.05 rows=3 width=136)
   -> Index Scan using tickets_pkey on tickets t
       (cost=0.43..8.45 rows=1 width=104)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
(7 rows)

此处规划器识别到两个值相等，将连接条件 tf.ticket_no = t.ticket_no 替换为 tf.ticket_no = 常量，实际上将等值连接简化为笛卡尔积³。

基数估算。 笛卡尔积的基数等于两个连接行集基数的乘积：3 = 1 × 3。

成本估算。 连接的初始成本等于两个子节点初始成本之和。

此例中，连接的总成本由以下部分构成：

获取所有外部行集行的成本；
获取所有内部行集行的单次成本（因外部行集基数估算为 1）；
处理每行结果的成本。

成本估算的依赖关系如下：

                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..25.05 rows=3 width=136)
   -> Index Scan using tickets_pkey on tickets t
       (cost=0.43..8.45 rows=1 width=104)

× 1

       Index Cond: (ticket_no = '0005432000284'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
(7 rows)

此例中连接成本的计算方式如下：

=> SELECT 0.43 + 0.56 AS startup_cost,
  round((
    8.45 + 16.57 +
    3 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.99 |      25.05
(1 row)

现在回到包含 Materialize 节点的前一个示例：

=> EXPLAIN SELECT *
FROM aircrafts_data a1
  CROSS JOIN aircrafts_data a2
WHERE a2.range > 5000;
                     QUERY PLAN
-----------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1
       (cost=0.00..1.09 rows=9 width=72)
   -> Materialize  (cost=0.00..1.14 rows=5 width=72)
       -> Seq Scan on aircrafts_data a2
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(7 rows)

一般情况下，连接的总成本由以下部分构成⁴：

获取所有外部行集行的成本；
初始获取所有内部行集行的单次成本（此过程执行物化）；
（N−1）次重复获取内部行集行的成本（其中 N 为外部行集的行数）；
处理每行结果的成本。

此处的依赖关系结构如下：

                    QUERY PLAN
--------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1
       (cost=0.00..1.09 rows=9 width=72)

× 9

   -> Materialize
       (cost=0.00..1.14 rows=5 width=72)
       -> Seq Scan on aircrafts_data a2
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(8 rows)

由于物化，重复获取数据的成本更低。计划中显示了首次访问 Materialize 节点的成本，但未显示重复访问的成本。我不会详细说明该估算的计算方式⁵，但在此例中其值为 0.0125。

因此，此例中连接的成本计算如下：

=> SELECT 0.00 + 0.00 AS startup_cost,
  round((
    1.09 + (1.14 + 8 * 0.0125) +
    45 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.00 |       2.78
(1 row)

参数化连接

考虑另一个更典型的例子，该例子不能简化为简单的笛卡尔积：

=> CREATE INDEX ON tickets(book_ref);
=> EXPLAIN SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.book_ref = '03A76D';
                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..45.67 rows=6 width=136)
   -> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104)
       Index Cond: (book_ref = '03A76D'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = t.ticket_no)
(7 rows)

此处嵌套循环节点遍历外部集合（机票）的行，并为每一行访问内部集合（航班）的行，将机票编号 t.ticket_no 作为参数传递给访问条件。当调用内部索引扫描节点时，它处理的是 ticket_no = 常量条件。

基数估计。 根据规划器的估计，满足预订号条件的外部集合有两行（rows=2），且对于每一行，内部集合平均将找到三行（rows=3）。

连接的选择性是指两个集合的笛卡尔积中，在连接后保留的行所占的比例。显然，必须立即排除两个集合中在连接列上包含空值的行（因为对于这些行，相等条件必然不成立）。

基数估计为两个集合的笛卡尔积基数（即两个集合基数的乘积），再乘以选择性⁶。

在此情况下，已知第一个（外部）集合的基数估计为两行。第二个（内部）集合除了连接条件外没有其他条件。因此，第二个集合的基数被取为 ticket_flights 表的基数。

由于连接的表通过外键关联，选择性的估计基于每个子表行在父表中恰好有一对匹配行的假设。此时选择性取为外键所引用表大小的倒数⁷。

因此（考虑到 ticket_no 列没有空值），估计结果为

=> SELECT round(2 * tf.reltuples * (1.0 / t.reltuples)) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets'
  AND tf.relname = 'ticket_flights';
 rows
------
    6
(1 row)

当然，即使没有外键也可以连接表。此时连接的选择性将基于具体连接条件的选择性估计⁸。

对于我们的等值连接情况，假设值均匀分布的“基础”选择性计算公式为 $\min\left(\frac{1}{nd_1},\frac{1}{nd_2}\right)$ ，其中 nd₁ 是第一个行集合中连接键的唯一值数量，nd₂ 是第二个行集合中的唯一值数量⁹。（参见 351）

关于唯一值数量的统计显示，tickets 表中的机票编号是唯一的（这是自然的，因为 ticket_no 列是主键），而 ticket_flights 表中每张机票平均对应约三行：

=> SELECT t.n_distinct, tf.n_distinct
FROM pg_stats t, pg_stats tf
WHERE t.tablename = 'tickets' AND t.attname = 'ticket_no'
  AND tf.tablename = 'ticket_flights' AND tf.attname = 'ticket_no';
 n_distinct | n_distinct
------------+-------------
         -1 | -0.30457819
(1 row)

最终，估计结果与基于外键的估计一致：

=> SELECT round(2 * tf.reltuples *
  least(1.0/t.reltuples, 1.0/tf.reltuples/0.30457819)
) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets' AND tf.relname = 'ticket_flights';
 rows
------
    6
(1 row)

规划器会尽可能地细化基础估计。目前它不使用直方图，但若对两个表的连接键收集了最频繁值列表，则会考虑这些统计信息¹⁰。在这种情况下，可以相对准确地计算出落入列表部分的行的选择性，而其余部分则基于均匀分布进行估计。（参见 353）

然而，在一般情况下，没有外键时的连接选择性估计可能不如有外键时的估计准确。特别是对于复合连接键，低估的风险更大。

通过 EXPLAIN ANALYZE 命令，不仅可以查看实际行数，还可以查看对内部循环的访问次数：

=> EXPLAIN (analyze, timing off, summary off, buffers off) SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.book_ref = '03A76D';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop  (cost=0.99..45.67 rows=6 width=136)
   (actual rows=8.00 loops=1)
   -> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104) (actual rows=2.00 loop...
       Index Cond: (book_ref = '03A76D'::bpchar)
       Index Searches: 1
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32) (actual rows=4.00 loops=2)
       Index Cond: (ticket_no = t.ticket_no)
       Index Searches: 2
(10 rows)

估计得到验证：外部集合实际有两行（actual rows=2）。因此内部索引扫描节点执行了两次（loops=2），每次平均选择四行（actual rows=4）。由此得出总查找行数：actual rows=8。（参见 166）

说明

我关闭了计划每一步执行时间的输出（timing off），以避免输出宽度因书页尺寸限制而过大；此外，在某些平台上，这种输出可能会显著减慢查询执行。但即使保留时间输出，显示的值也是平均值，与行数相同。要获得完整时间，需将平均值乘以迭代次数（loops）。

成本估计。 成本的计算方式与之前讨论的示例相同。在此情况下，对内部集合的重复扫描与首次扫描的成本无异。

最终结果如下：

=> SELECT 0.43 + 0.56 AS startup_cost,
  round((
    12.46 + 2 * 16.58 +
    6 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.99 |      45.68
(1 row)

缓存行 (Memoization)v. 14

如果对内部集合的重复扫描使用相同的参数值，并因此产生相同的结果，那么缓存内部集合的行可能更有利。

该功能由 Memoize 节点实现¹¹。它类似于 Materialize 节点，但专为参数化连接设计，结构复杂得多：

Materialize 节点简单地物化其子节点的所有行，而 Memoize 节点则为每个参数值分别缓存行；
当 Materialize 节点的存储空间溢出时，它会将数据写入磁盘，而 Memoize 节点的存储空间不会（否则缓存将失去意义）。

以下是使用 Memoize 节点的查询计划示例：

=> EXPLAIN SELECT *
FROM flights f
  JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code
WHERE f.flight_no = 'PG0003';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop  (cost=5.44..387.10 rows=113 width=135)
   -> Bitmap Heap Scan on flights f
       (cost=5.30..382.22 rows=113 width=63)
       Recheck Cond: (flight_no = 'PG0003'::bpchar)
       -> Bitmap Index Scan on flights_flight_no_scheduled_depart...
           (cost=0.00..5.27 rows=113 width=0)
           Index Cond: (flight_no = 'PG0003'::bpchar)
   -> Memoize  (cost=0.15..0.27 rows=1 width=72)
       Cache Key: f.aircraft_code
       Cache Mode: logical
       -> Index Scan using aircrafts_pkey on aircrafts_data a
           (cost=0.14..0.26 rows=1 width=72)
           Index Cond: (aircraft_code = f.aircraft_code)
(13 rows)

用于缓存行的内存大小为 work_mem × hash_mem_multiplier。从第二个参数的名称可知，内部使用哈希表（开放定址法¹²）进行行查找。哈希键（Cache Key）是参数值（或多个参数值的组合）。在逻辑模式（Cache Mode: logical）下，键通过值比较（使用普通相等操作符），在二进制模式下则通过位比较。(默认值: 4MB) (默认值: 2.0) (参见: 520)

此外，所有哈希键都链接成一个列表，一端被视为“冷”（长时间未使用），另一端为“热”（最近使用）。

当访问 Memoize 节点时，若对应参数值的行已在缓存中，它们将直接返回给父节点（嵌套循环节点），而无需访问子节点。使用的哈希键将移动到列表的热端。

如果缓存中没有所需行，Memoize 节点将从子节点获取行，将其存入缓存，并返回给上层节点。新哈希键同样被设为热键。

在缓存填充新数据期间，可用内存可能耗尽。为释放内存，将从缓存中移除对应冷键的行。这种淘汰算法不同于缓冲区缓存所用的算法，但完成相同任务。（参见 196）

可能会出现某些参数值对应大量行，即使其他所有行已被淘汰，也无法完全放入缓存。此时这些参数将被跳过——因为只缓存部分行毫无意义，下一次仍需访问子节点获取完整结果。

基数与成本估计。 估计计算方式与前述内容无本质区别。但需注意，计划中显示的 Memoize 节点成本与实际情况无关：它只是子节点成本加上 cpu_tuple_cost 值¹³。（默认值：0.01）

但要使 Memoize 节点有意义，其成本应低于子节点成本，而非高于。我们之前在 Materialize 节点示例中也遇到过类似情况：‘真实’成本是针对 重复扫描 的计算结果¹⁴，在计划中不显示。

Memoize 节点的重复扫描成本考虑了可用于缓存的内存大小以及对缓存访问的预期模式。计算高度依赖于对内部行集合扫描时可能使用的不同参数值数量的估计准确性¹⁵。获得该估计后，可粗略判断命中缓存的概率和行被驱逐的概率。预期的缓存命中会降低成本估计，而潜在的驱逐则会提高成本估计。成本计算的细节在此不展开。

通常，要理解查询执行时的真实情况，EXPLAIN ANALYZE 命令最有帮助。

在我们的示例中，查询的是由单一机型服务的单一航线的航班；因此，所有对 Memoize 节点的访问都使用相同的哈希键。第一次访问需从表中读取所需行（Misses: 1），但所有后续访问均由缓存处理（Hits: 112）。总共仅需一 KB 内存。

另外两个输出值为零：缓存驱逐次数（Evictions）和因无法保存同一参数集的所有行而导致的内存溢出次数（Overflows）。较大的数值表明分配给缓存的内存不足，很可能是由于对不同参数值数量的估计不准确。在这种情况下，使用 Memoize 节点可能非常昂贵。极端情况下，可禁用缓存功能，通过关闭参数 enable_memoize 来阻止规划器使用缓存。（默认值：on）

=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT * FROM flights f
  JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code
WHERE f.flight_no = 'PG0003';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop (actual rows=113.00 loops=1)
   -> Bitmap Heap Scan on flights f
       (actual rows=113.00 loops=1)
       Recheck Cond: (flight_no = 'PG0003'::bpchar)
       Heap Blocks: exact=2
       -> Bitmap Index Scan on flights_flight_no_scheduled_depart...
           (actual rows=113.00 loops=1)
           Index Cond: (flight_no = 'PG0003'::bpchar)
           Index Searches: 1
   -> Memoize (actual rows=1.00 loops=113)
       Cache Key: f.aircraft_code
       Cache Mode: logical
       Hits: 112  Misses: 1  Evictions: 0  Overflows: 0  Memory
       Usage: 1kB
       -> Index Scan using aircrafts_pkey on aircrafts_data a
           (actual rows=1.00 loops=1)
           Index Cond: (aircraft_code = f.aircraft_code)
           Index Searches: 1
(18 rows)

外连接

嵌套循环连接可用于 左外连接（节点 Nested Loop Left Join）。在此示例中，规划器选择了非参数化连接：

=> EXPLAIN SELECT * FROM ticket_flights tf
  LEFT JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no
                              AND bp.flight_id = tf.flight_id
WHERE tf.ticket_no = '0005434026720' and tf.flight_id = 82977;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Left Join  (cost=1.12..17.17 rows=1 width=57)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..8.58 rows=1 width=32)
       Index Cond: ((ticket_no = '0005434026720'::bpchar) AND (fl...
   -> Index Scan using boarding_passes_pkey on boarding_passes bp
       (cost=0.56..8.58 rows=1 width=25)
       Index Cond: ((ticket_no = '0005434026720'::bpchar) AND (fl...
(7 rows)

左外连接的基数估计方式与内连接相同，但结果取估计值与外部行集合基数的较大值¹⁶。换句话说，左外连接永远不会减少行数（但可能增加）。

成本估计与内连接类似。

不支持 右连接¹⁷，因为嵌套循环算法中外部和内部行集合不等价。外部集合必须完全扫描，而内部集合在索引访问时仅读取满足连接条件的行。这可能导致部分行未被访问。

由于相同原因，也不支持 全连接。

反连接和半连接

反连接和半连接的相似之处在于：对于第一个（外部）集合的每一行，只需在第二个（内部）集合中找到一行匹配即可。

反连接返回第一个集合的行，前提是这些行在另一个集合中未找到匹配项。换句话说，如果在第二个集合中找到了一个匹配行，第一个集合的该行将不再进入结果，后续检查可停止。

反连接可用于计算 NOT EXISTS 谓词。例如，找出尚未配置客舱布局的飞机型号。嵌套循环反连接在计划中由节点 Nested Loop Anti Join 表示：

=> EXPLAIN SELECT *
FROM aircrafts a
WHERE NOT EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Anti Join  (cost=0.28..5.26 rows=1 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..10.64 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

对于等价的无 NOT EXISTS 查询，也将生成相同的计划：

=> EXPLAIN SELECT a.*
FROM aircrafts a
  LEFT JOIN seats s ON a.aircraft_code = s.aircraft_code
WHERE s.aircraft_code IS NULL;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Anti Join  (cost=0.28..5.26 rows=1 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..10.64 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

半连接返回第一个集合中至少有一个匹配项存在于第二个集合中的行（同样，后续匹配无需检查——结果已知）。

半连接可用于计算 EXISTS 谓词。现在找出客舱中已安装座椅的飞机型号：

=> EXPLAIN SELECT *
FROM aircrafts a
WHERE EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Semi Join  (cost=0.28..7.28 rows=9 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..10.64 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

嵌套循环半连接由节点 Nested Loop Semi Join 表示。在此计划（以及上述反连接计划）中，seats 表的行数估计为普通值（rows=149），尽管实际上只需获取一行。查询执行时，循环在第一行后即停止：

=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT * FROM aircrafts a
WHERE EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
                          QUERY PLAN
---------------------------------------------------------------
 Nested Loop Semi Join (actual rows=9.00 loops=1)
   -> Seq Scan on aircrafts_data ml (actual rows=9.00 loops=1)
   -> Index Only Scan using seats_pkey on seats s
       (actual rows=1.00 loops=9)
       Index Cond: (aircraft_code = ml.aircraft_code)
       Heap Fetches: 9
       Index Searches: 9
(7 rows)

基数估算。 对于半连接，基数按常规方式计算，但内部行集的基数被视为 1。对于反连接，计算出的选择性从 1 中减去，如同否定操作¹⁸。

成本估算。 对于反连接和半连接，成本估算考虑了第二个行集并非完全读取，而是在找到与第一个行集的某一行匹配的配对后即停止¹⁹。

非等值连接

嵌套循环算法允许根据任意连接条件连接行集。

当然，如果内部行集是基础表，该表上已创建索引，且连接条件的操作符属于该索引的操作符类，则可以对内部行集进行高效访问。但始终存在行集的笛卡尔积结合条件过滤的选项——在这种情况下，条件可以是完全任意的。例如，以下查询选择距离较近的机场对：（参见 397）

=> CREATE EXTENSION earthdistance CASCADE;
=> EXPLAIN (costs off) SELECT *
FROM airports a1
  JOIN airports a2 ON a1.airport_code != a2.airport_code
                  AND a1.coordinates <@> a2.coordinates < 100;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop
   Join Filter: ((ml.airport_code <> ml_1.airport_code) AND
   ((ml.coordinates <@> ml_1.coordinates) < '100'::double precisi...
   -> Seq Scan on airports_data ml
   -> Materialize
       -> Seq Scan on airports_data ml_1
(6 rows)

并行模式

嵌套循环连接可以在并行模式下使用²⁰。（参见 379）

并行化仅在外部行集级别发生，该行集可由多个工作进程同时读取。每个进程获取外部行集的下一行后，再依次遍历与之匹配的内部行集的行——即顺序执行。

以下是包含多个连接的查询示例，用于查找购买了特定航班机票的乘客：

=> EXPLAIN (costs off) SELECT t.passenger_name
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
  JOIN flights f ON f.flight_id = tf.flight_id
WHERE f.flight_id = 12345;
                             QUERY PLAN
---------------------------------------------------------------------
 Gather
   Workers Planned: 2
   -> Nested Loop
       -> Nested Loop
           -> Parallel Seq Scan on ticket_flights tf
               Filter: (flight_id = 12345)
           -> Index Scan using tickets_pkey on tickets t
               Index Cond: (ticket_no = tf.ticket_no)
       -> Materialize
           -> Index Only Scan using flights_flight_id_status_idx ...
               Index Cond: (flight_id = 12345)
(11 rows)

获取内部行集时使用并行计划。每个进程读取 ticket_flights 表的若干行，并与 tickets 表通过嵌套循环连接。（参见 380）

随后，每个进程将所得行集与通过唯一键获取并物化于 Materialize 节点的一行 flights 表数据连接——因此，即使内部行集较大，嵌套循环也是合理的。（v. 18）

backend/executor/nodeNestloop.c. ↩︎
backend/executor/nodeMaterial.c. ↩︎
backend/optimizer/path/equivclass.c. ↩︎
backend/optimizer/path/costsize.c, 函数 initial_cost_nestloop 和 final_cost_nestloop. ↩︎
backend/optimizer/path/costsize.c, 函数 cost_rescan. ↩︎
backend/optimizer/path/costsize.c, 函数 calc_joinrel_size_estimate. ↩︎
backend/optimizer/path/costsize.c, 函数 get_foreign_key_join_selectivity. ↩︎
backend/optimizer/path/clausesel.c, 函数 clauselist_selectivity. ↩︎
backend/utils/adt/selfuncs.c, 函数 eqjoinsel. ↩︎
backend/utils/adt/selfuncs.c, 函数 eqjoinsel. ↩︎
backend/executor/nodeMemoize.c. ↩︎
include/lib/simplehash.h. ↩︎
backend/optimizer/util/pathnode.c, 函数 create_memoize_path. ↩︎
backend/optimizer/path/costsize.c, 函数 cost_memoize_rescan. ↩︎
backend/utils/adt/selfuncs.c, 函数 estimate_num_groups. ↩︎
backend/optimizer/path/costsize.c, 函数 calc_joinrel_size_estimate. ↩︎
backend/optimizer/path/joinpath.c, 函数 match_unsorted_outer. ↩︎
backend/optimizer/path/costsize.c, 函数 calc_joinrel_size_estimate. ↩︎
backend/optimizer/path/costsize.c, 函数 final_cost_nestloop. ↩︎
backend/optimizer/path/joinpath.c, 函数 consider_parallel_nestloop. ↩︎