Coding Interview Prep · 课时

连接算法：嵌套循环、哈希与归并

Q: 「连接算法：嵌套循环、哈希与归并」这节课中我会学到什么？

了解每种连接的执行方式，以及各自在何时最合适。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

了解每种连接的执行方式，以及各自在何时最合适。

连接算法：嵌套循环、哈希与归并 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

连接是算法，而不只是语法

您已经了解 INNER JOIN 这种语法。在高级职位面试中，面试官会询问数据库如何实际执行连接。共有三种算法：

嵌套循环连接
哈希连接
合并连接（排序合并）

逻辑连接类型（INNER、LEFT）与所使用的算法相互独立。规划器会根据表大小、索引和排序顺序选择算法。了解每种算法何时更有优势，是本课的核心。

嵌套循环连接

嵌套循环是最简单的连接方式：对于外表中的每一行，都扫描内表来查找匹配项。用伪代码表示，就是两个循环，其中一个位于另一个内部。

直接这样执行时，复杂度为 O(外表 * 内表)，对于大型表来说非常糟糕。但如果内侧在连接键上有索引，性能就会非常好：每一行外表数据只需触发一次廉价的索引查找，而不必完整扫描内表。

当外表较小且内侧的连接列有索引时，规划器通常最偏爱这种方式。

Nested Loop  (cost=0.42..120.5 rows=15 width=72)
  ->  Seq Scan on customers c  (rows=3)
  ->  Index Scan using idx_orders_cust on orders o
        Index Cond: (o.customer_id = c.id)
        (loops=3)

读取嵌套循环中的循环次数

嵌套循环的明显特征是内侧节点上的 loops。示例显示 loops=3，因为外侧产生了 3 行，所以内侧索引扫描运行了 3 次。

当外侧数据量很大时，危险就出现了。如果外侧产生 200 万行，内侧就会运行 200 万次。即使每次查找只需 0.01 毫秒，累计也会达到 20 秒。

在面试中，如果看到内表没有合适索引且 loops 很大的嵌套循环，就应指出这是慢查询。

哈希连接

哈希连接非常适合处理大型未排序表。它分为两个阶段：

构建：读取较小的表，并将其加载到以内存中的哈希表中，使用连接列作为键。
探测：扫描较大的表；对于每一行，对连接键进行哈希计算，然后在哈希表中查找。

每张表只读取一次，因此复杂度大致为 O(外表 + 内表)。它既不需要索引，也不需要已排序的输入，所以在基于等值条件的大型分析型连接中通常占据优势。

Hash Join  (cost=18.0..520.0 rows=900 width=72)
  Hash Cond: (o.customer_id = c.id)
  ->  Seq Scan on orders o  (rows=100000)
  ->  Hash  (rows=500)
        ->  Seq Scan on customers c  (rows=500)

哈希连接的限制

谈到哈希连接时，您必须提到两点：

它们只能处理等值连接条件（a.id = b.id）。像 a.x < b.y 这样的范围条件不能使用哈希连接。
构建侧必须能够放入工作内存。如果放不下，数据库会将批次溢写到磁盘（您会看到 Batches: > 1 以及磁盘使用情况），这会严重拖慢连接。

因此，构建侧巨大而 work_mem 很小的哈希连接，是实际系统中需要指出的性能错误。

Hash  (actual rows=2000000 loops=1)
  Buckets: 65536  Batches: 16  Memory Usage: 4096kB

合并连接

合并连接（排序合并）要求两个输入都按照连接键排序。随后它会像合并两个有序列表一样同步遍历两者，让落后的指针向前移动。

当输入已经排好序时，这种方式非常高效。例如，数据可以直接按照键的顺序从索引中读取，这样就不需要额外的排序步骤。与哈希连接不同，它还支持范围连接和不等式连接。

如果输入没有预先排序，规划器就会添加显式的 Sort 节点，而排序成本可能会使哈希连接反而更加便宜。

Merge Join  (cost=0.85..210.0 rows=900 width=72)
  Merge Cond: (o.customer_id = c.id)
  ->  Index Scan using idx_orders_cust on orders o
  ->  Index Scan using customers_pkey on customers c

决策速查表

请记住每种算法何时占优：

嵌套循环：外表较小，且内侧连接键有索引；在输入未排序时，它也是非等值连接的唯一选择。
哈希连接：大型未排序表按等值条件连接；不需要索引。
合并连接：两个输入已经按照连接键排序（通常通过索引实现），或者需要进行范围连接；非常适合大型预排序数据集。

规划器会估算每种算法的成本，并根据行数估算选择成本最低的方案。

内存和排序成本

不同连接方式的资源使用差异很大，面试官经常会追问这一点：

嵌套循环：内存占用极小；成本主要来自反复查找内表。
哈希连接：需要为哈希表分配内存；如果哈希表过大，就会溢写到磁盘。
合并连接：合并本身成本很低，但如果必须先排序，成本就会很高；排序也会使用 work_mem，并且可能溢写到磁盘。

因此，调大 work_mem 可以将因磁盘溢写而变慢的哈希或排序转变为在内存中完成的操作，这是一个具体的优化回答。

嵌套循环为何会出问题

典型场景是：查询在开发环境中运行很快，在生产环境中却很慢。执行计划显示一个 嵌套循环，且 loops=3000000。

规划器低估了外侧行数（过时的统计信息显示为 3 行，而实际有 300 万行），因此选择了嵌套循环。如果统计信息准确，规划器本会选择哈希连接。

您在面试中可以这样回答：运行 ANALYZE，使估算结果准确；规划器随后会切换到哈希连接，查询速度也会大幅提升。

Nested Loop  (cost=0.42..50.0 rows=3 width=72)
  ->  Seq Scan on big_outer  (actual rows=3000000 loops=1)
  ->  Index Scan on inner_t  (actual rows=1 loops=3000000)

影响算法选择

通常不应强制指定算法，但您可以在测试中这样做，以便进行比较。数据库提供了按方法设置的开关：

SET enable_nestloop = off;，以及针对 enable_hashjoin 和 enable_mergejoin 的类似设置。关闭其中一个选项后，重新运行 EXPLAIN ANALYZE，观察替代方案是否确实更快。

正确的解决方案仍然是：更新统计信息、建立合适的索引、提供足够的 work_mem，以及使用选择性高的谓词。强制指定算法只能用于诊断。

SET enable_nestloop = off;
EXPLAIN ANALYZE
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id;
SET enable_nestloop = on;

大规模连接总结

把这些知识应用到一个分析型工作负载中：按标识列连接两个大型事实表和维度表：

如果维度表能够放入内存，通常会选择哈希连接，这往往是最佳方案。
如果两个表都通过索引按连接键排序后到达，合并连接可以避免构建哈希表。
在这种场景下使用嵌套循环会是一个危险信号，通常表示行数估算有误。

读出规划器选择了哪种算法，并判断它是否应该这样选择，正是这类问题考察高级水平的关键。

快速检查

您要在两个大型未排序表之间按照等值条件 a.id = b.id 进行连接，两个表都没有有用的索引，并且统计信息准确。规划器最有可能选择哪种连接算法？

回顾

三种连接算法：

嵌套循环：外表行数乘以内表查找次数；外表较小且内侧连接键有索引时非常好，但 loops 很大时会很危险。
哈希连接：构建并探测；最适合大型未排序的等值连接，但仅限等值条件，并受 work_mem 限制。
合并连接：在已排序的输入上同步推进；数据已经排序或需要进行范围连接时最为理想。

规划器会根据成本和统计信息进行选择。出现循环次数巨大的异常嵌套循环，几乎总是意味着行数估算有误；修正统计信息即可。

常见问题解答

「连接算法：嵌套循环、哈希与归并」课时是免费的吗？

是的 — 「连接算法：嵌套循环、哈希与归并」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「连接算法：嵌套循环、哈希与归并」这节课中我会学到什么？

了解每种连接的执行方式，以及各自在何时最合适。你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「连接算法：嵌套循环、哈希与归并」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Coding Interview Prep