微信群：数据库Hacker, 已超200人，现在无法通过扫描直接加入。需要入群的朋友，请直接微信联系我(个人微信：_iihero)，标上您的全名_数据库Hacker作为备注即可。
21 嵌套循环
21.1 连接类型和方法
连接是该语言的一个关键特性；它们是其力量和灵活性的基础。行集（要么直接从表中检索，要么作为某些其他操作的结果接收）总是成对连接。
有几种类型的连接：
内部连接。内部连接（指定为 INNER JOIN，或简称为 JOIN）由满足特定连接条件的两个集合的行对组成。连接条件将一组行的一些列与另一组行的一些列结合起来；所有涉及的列都构成连接键。
如果连接条件要求两个集合的连接键相等，这样的连接称为等连接；这是最常见的连接类型。
两个集合的笛卡尔积（CROSS JOIN）包含了这些集合的所有可能的行对——它是具有真条件的内连接的一种特殊情况。
外部连接。左外部连接（指定为，或简称为）通过左集合中在右集合中没有匹配的行扩展内部连接的结果（相应的右侧列填充值）。
右外连接（RIGHT JOIN）也是如此，直到集合的排列。
完整的外部连接（指定为 FULL JOIN）包括左外部连接和右外部连接，并添加未找到匹配的右侧和左侧行。
反连接和半连接。半连接看起来很像内部连接，但它只包括左集中与右集中有匹配的行（即使有几个匹配，也只包括一行）。
反连接包括一个集合中在另一个集合中没有匹配的行。SQL 语言没有显式的半连接和反连接，但是使用 EXISTS 和 NOT EXISTS 这样的谓词可以实现相同的结果。
所有这些连接都是逻辑操作。例如，内部连接通常被描述为已经清除了不满足连接条件的行的笛卡尔积。但是在物理级别上，内连接通常是通过成本较低的方式实现的。
PostgreSQL 提供了几种连接方法：
嵌套循环连接 哈希连接 合并连接
连接方法是实现连接逻辑操作的算法。这些基本算法通常具有为特定连接类型量身定制的特殊风格，即使它们可能只支持其中的一些。例如，嵌套循环支持内部连接（在计划中由嵌套循环节点表示）和左外部连接（由嵌套循环左连接节点表示），但它不能用于完全连接。
相同算法的某些风格也可以用于其他操作，例如聚合。
不同的连接方式在不同的条件下表现最佳；计划器的工作是选择最具成本效益的一种。
21.2 嵌套循环连接
嵌套循环连接函数的基本算法如下。外部循环会遍历外部集合的所有行。对其中的每一行，嵌套循环会再遍历内部集合中的每一行，以找到满足连接条件的记录行。最后找到的每一行会作为查询结果立即返回。
这个算法访问内部集合的次数跟它访问外部集合的行数一样多。因此，嵌套循环连接算法的效率依赖于如下几个因素：
外部集合中行的基数 （行数) 有效访问内部集合中所需行的可用访问方法 重复访问内部集合中同一行的效率
21.2.1 迪卡尔积
嵌套循环连接是求笛卡尔积最有效的方法，不管这个集合有多少行，它都是通用的：
=> 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)
嵌套循环节点使用上述算法执行连接。它总是有两个子节点：在计划中显示较高位置的那个对应于外部的行集，而较低的那个代表内部的行集。
在本例中，内部集合由 Materialize 节点 1 表示该节点将从其子节点接收到的行重新转过来，并保存它们以供将来使用(这些行在内存中累积，直到它们的总大小达到（4MB）；然后 PostgreSQL 开始将它们溢出到磁盘上的临时文件中。如果再次访问，该节点将读取累积的行，而不调用子节点。这样，前执行器就可以避免再次扫描整个表，而只读取满足条件的行。
类似的计划也可以用于使用常规对等连接的查询：
=> 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.58 rows=3 width=32)
Index Cond: (ticket_no = '0005432000284'::bpchar)
(7 rows)
识别出两个值相等后，规划器将替换连接条件 tf.Ticket_no = t.ticket_no 为新的条件:ticket_no = 常量，实际上将相等连接简化为笛卡尔积[1]。
**基数估计．**笛卡尔积的基数是估计连接数据集的基数的乘积：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)
Index Cond: (ticket_no = '0005432000284'::bpchar)
−> Index Scan using ticket_flights_pkey on ticket_flights tf
(cost=0.56..16.58 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)
我们再回到前一个例子：
=> 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)
该计划现在包含 Materialize 节点；一旦积累了从子节点接收到的行，Materialize（物化）就可以更快地为所有后续调用返回它们。
一般来说，连接的总成本包括以下费用[2]：
获取外部集合中所有行的成本
内部集合中所有行的初始取值的成本（在此期间执行物化）
(N−1)-内部集合的行重复获取的成本（这里 N 是外部集合的行数）
处理要返回的每一行的成本
这里的依赖关系图如下：
在本例中，物化减少了重复数据获取的成本。计划中显示了第一次 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)
21.2.2 参数化连接
现在让我们考虑一个更常见的例子，它不能归结为笛卡尔积：
=> 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.68 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.58 rows=3 width=32)
Index Cond: (ticket_no = t.ticket_no)
(7 rows)
这里，Nested Loop 节点遍历外部集合（机票）的行，并对每一行搜索内部集合（航班）的对应行，将机票号（t.t ticket_no）作为参数传递给条件。当调用内部节点（Index Scan）时，它必须处理条件 ticket_no = 常量。
基数估计. 规划器估计预订号的过滤条件由外部集合的两行（rows=2）满足，并且这些行中的每一行平均匹配内部集合的三行（rows=3）。
连接选择率是连接后剩下的两个集合的笛卡尔积的一个分数。很明显，我们必须排除两个集合中包含连接键中的 NULL 值的行，因为它们永远不会满足相等条件。
估计的基数等于笛卡尔积的基数（即两个集合的基数的乘积）乘以选择率.
这里，第一个（外部）集合的估计基数是两行。由于除了连接条件本身之外，没有任何条件应用于第二个（内部）集，因此将第二个集的基数作为 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 (1/nd1, 1/nd2)，其中 nd1 和 nd2 分别表示连接键在第一个和第二个集合中不同值的数量。
对不同值的统计表明，ticket 表中的机票号是唯一的（这是意料之中的，因为 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.30362356
(1 row)
该结果将与外键值连接的估计相匹配：
=> SELECT round(2 * tf.reltuples *
least(1.0/t.reltuples, 1.0/tf.reltuples/0.30362356)
) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets' AND tf.relname = 'ticket_flights';
rows
−−−−−−
6
(1 row)
计划器尽可能地改进这个基线估计。它目前不能使用直方图，但是如果在两个表的连接键上收集了这样的统计信息，它会考虑 MCV 列表可以更准确地估计列表中出现的行的选择性[3]，只有剩下的行必须依赖基于均匀分布的计算。
一般来说，如果定义了外键，连接选择性估计可能会更准确。对于复合连接键尤其如此，因为在这种情况下，选择率通常被大大低估了。
使用 explain analyze 命令，您不仅可以查看实际的行数，还可以查看内部循环执行的次数：
=> EXPLAIN (analyze, timing off, summary 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.68 rows=6 width=136)
(actual rows=8 loops=1)
−> Index Scan using tickets_book_ref_idx on tickets t
(cost=0.43..12.46 rows=2 width=104) (actual rows=2 loops=1)
Index Cond: (book_ref = '03A76D'::bpchar)
−> Index Scan using ticket_flights_pkey on ticket_flights tf
(cost=0.56..16.58 rows=3 width=32) (actual rows=4 loops=2)
Index Cond: (ticket_no = t.ticket_no)
(8 rows)
外部集包含两行（实际行=2）；估计是正确的。因此，Index Scan 节点执行了两次（loops=2），每次它平均选择 4 行（实际行=4）。因此，找到的行的总数：实际行=8。
我没有显示 plan（TIMING OFF）的每个阶段的执行时间，以便输出适合有限的页面宽度；此外，在某些平台上，启用定时的输出可以显著降低查询的执行速度。但是如果我们包含它，PostgreSQL 将显示一个平均值，就像行数一样。要获得总执行时间，应该将该值乘以迭代（循环）的次数。
成本估计. 成本估计公式与前一个例子是相同的。
我们回忆一下我们的查询计划：
=> 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.68 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.58 rows=3 width=32)
Index Cond: (ticket_no = t.ticket_no)
(7 rows)
在这种情况下，内部集合的每次后续扫描的代价与第一次扫描的代价相同。因此，我们最终得到以下数字：
=> SELECT 0.43 + 0.56 AS startup_cost,
round((
12.46 + 2 * 16.57 +
6 * current_setting('cpu_tuple_cost')::real
)::numeric, 2) AS total_cost;
startup_cost | total_cost
−−−−−−−−−−−−−−+−−−−−−−−−−−−
0.99 | 45.66
(1 row)
21.2.3 行缓存（记忆化）
如果使用相同的参数值重复扫描内部集合（从而得到相同的结果），那么缓存该集合的行可能是有益的。
这种缓存由Memoize[4]节点执行。与 Materialize 节点类似，它被设计用于处理参数化连接，并且具有更复杂的实现：
