MIT Notes by Ron

中文

English

中文

English

Appearance

PostgreSQL 查询系列 — 5. 嵌套循环连接 ​

原文：https://habr.com/en/companies/postgrespro/articles/579024/ （作者 Egor Rogov，PostgresPro）

引言 ​

前面两篇讨论的都是"怎么访问单张表"，从这一篇开始，系列进入多表连接（join）的领域。连接分两个层面理解：一是逻辑层面——连接条件表达的语义是什么（内连接、外连接、半/反连接等）；二是物理层面——PostgreSQL 具体用什么算法去实现这个逻辑连接。本篇聚焦三种物理连接算法中最直观的一种：嵌套循环连接（Nested Loop）。

逻辑连接类型速览 ​

在讨论算法之前，先厘清连接的语义种类，因为不同语义会限制哪些物理算法可用：

  • 内连接（inner join）：只保留两个集合中满足连接条件的行对；最常见的是等值连接（equijoin，用 = 判断），但连接条件也可以是任意谓词；
  • 交叉连接（cross join）：没有连接条件限制，两个集合的笛卡尔积；
  • 外连接（outer join）：左外连接、右外连接、全外连接，除了满足条件的行对外，还要把"没有匹配上"的一侧的行也保留下来（缺失的一侧补 NULL）；
  • 半连接 / 反连接（semi-join / anti-join）：不是把两侧的行拼接输出，而是根据"另一个集合里是否存在匹配"来决定是否保留某一侧的行，通常对应 SQL 里的 EXISTS / NOT EXISTS（或 IN / NOT IN）写法，输出的列只来自一侧。

三种物理连接算法 ​

PostgreSQL 的优化器可以从三种物理算法中选择来实现一个逻辑连接：嵌套循环（Nested Loop）、哈希连接（Hash Join）、归并连接（Merge Join）。本篇专讲第一种，后两种分别是系列的第 6、7 篇主题。

嵌套循环的基本原理 ​

嵌套循环连接的思路非常朴素，直接对应最原始的"双重 for 循环"：外层循环遍历"外层集合"（outer set）中的每一行；对外层的每一行，内层循环都会去"内层集合"（inner set）里找出所有能与之匹配的行；每找到一对匹配的行，就输出一条连接结果。

这个算法本身不要求任何一侧提前排好序，也不要求任何一侧预先建好哈希表，可以说是最通用、限制最少的连接方式——理论上什么样的连接条件（不管是不是等值条件）它都能处理。它的效率高低取决于三个关键因素：

  • 外层集合的行数：外层每多一行，内层循环就要多跑一遍，所以外层集合越小越好；
  • 内层集合是否有高效的访问方式：如果每次内层查找都要对内层表做一次全表顺序扫描，那么总体复杂度接近"外层行数 × 内层表大小"，是相当昂贵的；但如果内层能够用索引快速定位到匹配行（也就是所谓的"参数化"内层扫描——用外层当前这一行的值作为参数去查内层索引），单次内层查找的代价会大幅降低；
  • 是否会对相同的内层行反复重复扫描：如果外层集合有多行会用到内层集合中相同的一批数据，重复扫描本身就是一种浪费，这也是后面 Materialize/Memoize 节点要解决的问题。

代价公式 ​

对于一个参数化的嵌套循环连接，代价大致按下面的方式累加（N 表示外层集合的估算行数）：

startup_cost = outer_startup_cost + inner_startup_cost
total_cost   = outer_total_cost
             + N × inner_scan_cost
             + 结果行数 × cpu_tuple_cost

其中 inner_scan_cost 会因内层节点是否被"参数化"（是否能利用索引条件把外层的值直接推给内层，避免每次都全表扫描）、是否被物化（见下）而有很大差异。可以直观地看出：如果 inner_scan_cost 很小（比如内层用索引一击命中一两行），即便 N 很大，总代价依然可控；反之如果内层每次都要付出全表扫描的代价，N 一旦增大，总代价会近似线性甚至更快地膨胀。

Materialize 节点：缓存内层结果 ​

当内层集合的扫描代价较高、又会被外层集合重复多次访问（比如内层是一个子查询或不带索引条件的顺序扫描）时，PostgreSQL 可以在内层节点外面包一层 Materialize 节点：第一次执行内层扫描时，把结果实实在在缓存到内存（必要时溢出到临时文件）里；后续外层每来一行新的，都不用重新触发底层扫描，而是直接从这份缓存里重新读取，省下了重复扫描的代价，用空间换时间。

PostgreSQL 14 的新特性：Memoize（记忆化） ​

Materialize 节点是"无差别缓存所有内层结果"，而 PostgreSQL 14 引入的 Memoize 节点做得更精细：它是按参数值分别缓存的——外层每一行传入内层的参数值不同，Memoize 会针对每个不同的参数值维护一份独立的缓存条目，内部用哈希表组织，并采用 LRU（最近最少使用）策略淘汰旧条目以控制内存占用。

关键特性和参数：

  • 分配的内存上限大致是 work_mem × hash_mem_multiplier；
  • EXPLAIN ANALYZE 的输出里会报告缓存命中（cache hits）、未命中（misses）、淘汰（evictions）和溢出（overflows）等具体统计，便于事后判断这个 Memoize 节点到底有没有真正发挥作用；
  • 文章特别提醒：Memoize 节点在规划阶段给出的估算代价，往往不能真实反映实际运行时的收益或损耗——它"真正"的价值是要靠重复扫描节省下来的代价来体现的，这部分在纯粹的静态代价估算里很难精确建模，必须结合 EXPLAIN ANALYZE 的实际执行统计（尤其是 loops 次数和命中率）才能判断这个节点是不是真的划算。

Join Filter 与 Index Cond 的区别 ​

延续上一篇讲索引扫描时的思路：在参数化的嵌套循环里，如果连接条件是等值条件，并且内层恰好在对应列上有索引，那么这个条件可以被直接下推成内层索引扫描的 Index Cond，让内层扫描本身就变得高效精准；但如果连接条件不是简单等值（比如涉及范围比较、复杂表达式等非等值连接），索引往往无法直接利用这类条件做定位，这时条件就只能以 Join Filter 的形式出现——也就是说内层还是要先按某种方式把候选行取出来，再逐行核对这个复杂条件，无法在索引层面直接"跳过"不满足条件的部分。

嵌套循环的局限 ​

  • 不支持右外连接和全外连接：嵌套循环的外层/内层在算法结构上是不对称的（外层驱动、内层被查找），而右外连接、全外连接要求"未匹配的内层行也要被保留输出"，这和嵌套循环天然的驱动方向是冲突的，所以 PostgreSQL 不会为这两种连接语义选择嵌套循环算法（左外连接则没有这个问题，因为外层本身就是需要保留未匹配行的一侧）；
  • 非等值连接条件只能靠过滤，不能被索引直接加速（如上一节所述）；
  • 外层集合很大、内层又缺乏高效访问路径时效果会很差——退化为近似"笛卡尔积"级别的开销，这也是嵌套循环最容易被诟病、最需要警惕的失败模式，通常是索引缺失或统计信息误导优化器选错算法导致的。

并行执行下的嵌套循环 ​

在并行计划中，外层集合的扫描可以被拆给多个并行 worker 各自负责一部分（比如外层是一个 Parallel Seq Scan），但内层的循环逻辑本身在每个 worker 内部依然是串行执行的——也就是说并行化只发生在"外层分片"这个维度，内层针对每一行的查找过程并不会被进一步拆分。

小结 ​

嵌套循环是最通用、最"朴素"的连接算法：外层驱动、内层查找，没有排序或建哈希表的前置要求，因此对连接条件的类型几乎没有限制。它的性能高度依赖"外层集合小 + 内层能高效定位（通常靠索引）"这个组合；当内层缺乏索引或需要被外层反复扫描时，Materialize（无差别缓存）和 PostgreSQL 14 引入的 Memoize（按参数值缓存 + LRU 淘汰）能够显著降低重复扫描的代价，但两者的真实收益都需要结合 EXPLAIN ANALYZE 的实际运行统计来判断，而不能只看规划阶段的估算代价。等值连接条件可以下推为内层的 Index Cond，非等值条件只能退化为 Join Filter。嵌套循环不支持右外连接/全外连接，在 OLTP 场景、小驱动集合配合索引良好的内层表时通常表现优异，但一旦外层集合过大且内层缺乏索引，很容易成为性能瓶颈。下一篇文章将讨论哈希连接，看看当条件是等值连接、且需要处理大数据量时，PostgreSQL 是如何用哈希表来避免嵌套循环这种"重复查找"开销的。