本页内容受版权保护 · 已添加水印 · 禁止任何形式转载
查询基础（SELECT / JOIN / 聚合 / 排序） · JOIN 多表连接

MySQL 的 NLJ（Nested Loop Join）、BNL（Block Nested Loop）、Hash Join 各自适用场景？8.0 之前为什么没有 Hash Join？

What are the applicable scenarios for MySQL's NLJ (Nested Loop Join), BNL

答案语言

考察要点

这道题面试官想看你是否深入理解 MySQL 查询执行引擎的内部机制，特别是多表连接（JOIN）的核心算法。考察点包括：

  1. 算法理解：你是否清楚 NLJ、BNL、Hash Join 的工作原理、执行流程和各自的优缺点。
  2. 场景判断：你是否能根据有无索引、数据量大小等条件，准确判断 MySQL 优化器会选择哪种连接算法。
  3. 版本认知：你是否了解 MySQL 在不同版本（特别是 8.0 前后）在 JOIN 策略上的重大演进，并能解释其背后的设计哲学。

核心概念

MySQL 执行 JOIN 时，主要依赖三种算法：Nested Loop Join (NLJ)、Block Nested Loop Join (BNL) 和 Hash Join。优化器会根据成本估算自动选择最优算法。

1. NLJ (Nested Loop Join / 索引嵌套循环连接)

这是 MySQL 最常用、最高效的 JOIN 方式，其本质是利用索引进行快速查找。

  • 工作原理：

    1. 选择一张表作为驱动表（Driving Table）。
    2. 遍历驱动表的每一行数据。
    3. 对于驱动表的每一行，将其 join_key 的值作为查询条件，去被驱动表（Driven Table）中进行查找。关键：这个查找过程必须使用被驱动表上的索引。

  • 图示：

    text
     1for row_d in driving_table:
     2    lookup row_p in driven_table where row_p.join_key = row_d.join_key (via index)

  • 适用场景： 被驱动表的 join_key 列上必须有高效的索引。这是 NLJ 的唯一且必要条件。通常适用于一个表小（作驱动表）、另一个表大但有索引的场景。

  • 复杂度： 设驱动表行数为 M，被驱动表行数为 N。由于被驱动表上有索引，每次查找的时间复杂度约为 O(log⁡N)O(\log N)（B+树）。 总时间复杂度约为 O(M×log⁡N)O(M \times \log N)。

  • SQL 示例：

    sql
     1-- 假设 t2.b 列上有索引
     2SELECT * FROM t1 JOIN t2 ON t1.a = t2.b;

    EXPLAIN 结果中，t2 表的 type 字段通常为 ref 或 eq_ref，表示用到了索引。

2. BNL (Block Nested Loop Join / 块嵌套循环连接)

BNL 是在 MySQL 8.0 之前，当被驱动表没有可用索引时的一种补救措施，性能较差。

  • 工作原理：

    1. 选择一张表作为驱动表。
    2. 开辟一块内存区域，称为 join_buffer（大小由 join_buffer_size 参数控制）。
    3. 将驱动表的多行数据（一个“块”）读入 join_buffer。
    4. 全表扫描被驱动表，将其每一行与 join_buffer 中的所有行进行比较，匹配则输出。
    5. 重复步骤 3 和 4，直到驱动表的所有数据都被处理完。

  • 图示：

    text
     1for block_d in driving_table:  // 一次读取一个数据块
     2    load block_d into join_buffer
     3    for row_p in driven_table:  // 全表扫描
     4        for row_d_in_buffer in join_buffer:
     5            if row_p.join_key == row_d_in_buffer.join_key:
     6                // match

  • 适用场景： 被驱动表的 join_key 列上没有索引。BNL 通过在内存中批量比较，减少了对外层循环的迭代次数，相对于原始的、不使用 join_buffer 的 Simple Nested Loop（O(M×N)O(M \times N) 的磁盘 I/O），它优化了 I/O，但 CPU 计算量和对被驱动表的扫描次数依然巨大。

  • 复杂度： 设驱动表行数为 M，被驱动表行数为 N，join_buffer 能容纳 C 行。 总时间复杂度约为 O(M+(M/C)×N)O(M + (M/C) \times N)。被驱动表 t2 会被全表扫描 M/C 次。

  • 版本差异： 在 MySQL 8.0.18 引入 Hash Join 后，BNL 已被废弃。在 8.0.20 中，优化器代码中关于 BNL 的逻辑被彻底移除。

3. Hash Join

Hash Join 是 MySQL 8.0.18 版本引入的、用于替代 BNL 的高效算法，专门处理无索引的 JOIN 场景。

  • 工作原理： 分为两个阶段：Build（构建）阶段和 Probe（探测）阶段。

    1. Build 阶段：选择较小的表作为构建表（Build Table），将其所有数据读入内存中的 join_buffer，并基于 join_key 构建一个哈希表。
    2. Probe 阶段：顺序扫描较大的表（Probe Table），对于每一行，用其 join_key 计算哈希值，然后去内存中的哈希表查找匹配的行。

  • 图示：

    text
     1// 1. Build Phase
     2hash_table = {}
     3for row_build in build_table (smaller table):
     4    hash_table[hash(row_build.join_key)].append(row_build)
     5

     6// 2. Probe Phase
     7for row_probe in probe_table (larger table):
     8    if hash_table.contains(hash(row_probe.join_key)):
     9        // match

  • 适用场景：

    • 被驱动表的 join_key 列上没有索引。
    • 等值连接（ON t1.a = t2.b）。
    • 至少有一个表（构建表）能够完全或大部分放入 join_buffer 中。如果内存不足，MySQL 会使用更复杂的磁盘溢出（spill-to-disk）策略，性能会下降，但依然能完成。

  • 复杂度： 设两表行数分别为 M 和 N。 总时间复杂度为 O(M+N)O(M + N)，因为每个表都只被完整扫描一次。这远优于 BNL。

  • 版本差异：

    • ✅ MySQL 8.0.18+：默认启用。
    • ❌ MySQL 5.7 及更早版本：不支持。

8.0 之前为什么没有 Hash Join？

这是一个历史和设计哲学问题：

  1. OLTP 优先的设计：MySQL 诞生之初的核心定位是 OLTP（在线事务处理）数据库。这类场景的特点是高并发、短事务，查询大多通过主键或二级索引完成。Index Nested Loop Join (NLJ) 对于有索引的查询极为高效，完全满足了核心 OLTP 场景的需求。
  2. 架构惯性：MySQL 的优化器和执行引擎长期围绕“基于索引的迭代查找”模型构建。引入一套全新的、基于哈希的执行模型是一项重大的架构改造，需要对查询执行路径进行深度重构。
  3. 存储引擎的解耦：MySQL 的可插拔存储引擎架构（如 InnoDB, MyISAM）使得查询执行层需要与具体的存储层解耦。实现一个通用的、高效的 Hash Join 机制，同时要考虑不同引擎的特性，增加了复杂性。
  4. BNL 作为权宜之计：BNL 虽然性能不佳，但在当时被认为是一个“够用”的解决方案，用于处理无索引 JOIN 的边缘情况。 随着 MySQL 的应用场景扩展到更多 OLAP（在线分析处理）和复杂查询领域，BNL 的性能瓶颈日益凸显，社区和官方才下定决心在 8.0 版本中引入了现代数据库标配的 Hash Join。

常见低分回答

  1. 混淆 NLJ 和 BNL：误以为 NLJ 就是简单的两层 for 循环，性能很差。高分回答应明确指出 NLJ 的全称是 Index Nested Loop Join，其高效性依赖于索引。
  2. 认为 join_buffer 对所有 JOIN 都有效：错误地认为 NLJ 也会使用 join_buffer。join_buffer 主要服务于 BNL 和 Hash Join，即无索引的场景。
  3. 断言 Hash Join 永远比 NLJ 好：这是错误的。当被驱动表有良好索引时，NLJ 通常更快。因为它不需要读取整个构建表来创建哈希表，而是直接进行精确的索引查找，I/O 和 CPU 开销可能更小，特别是当驱动表结果集很小时。
  4. 对 BNL 原理描述不清：只说“把数据放内存里”，但没说清楚是“分块读取驱动表”和“全表扫描被驱动表”这两个关键动作，导致其性能差的原因没解释到位。
  5. 对版本支持模糊不清：只说“新版 MySQL 支持 Hash Join”，而不能准确说出是 8.0.18 这个关键版本号，会显得知识掌握不精确。

工程实践与优化

  • 首要优化原则：尽可能通过创建索引，让 JOIN 走 NLJ。这是最高效的方式。检查 JOIN 条件的列，确保被驱动表（通常是数据量较大的表）的关联列上有索引。
  • 监控与诊断：使用 EXPLAIN 是定位 JOIN 性能问题的关键。
    • EXPLAIN SELECT ...
    • 看到 Extra 列出现 Using join buffer (Block Nested Loop)：这是严重警告（MySQL 8.0 之前）。立即检查 JOIN 列的索引情况。
    • 看到 Extra 列出现 Using join buffer (Hash Join)：表示正在使用 Hash Join。这在无索引场景下是正常的、最优的选择。此时可以考虑调大 join_buffer_size 以容纳更小的表，避免磁盘溢出。
    • 看到被驱动表的 type 是 ALL：表示全表扫描，如果此时没有出现 BNL 或 Hash Join 的提示，说明可能在用最原始的 Simple Nested Loop，性能灾难。
  • EXPLAIN ANALYZE (MySQL 8.0.18+)：这个命令不仅会展示执行计划，还会实际执行查询并返回各阶段的真实耗时和行数，对于分析 Hash Join 的 Build/Probe 阶段耗时、是否发生磁盘溢出等问题非常有用。
  • 调整 join_buffer_size：当无法添加索引，必须使用 Hash Join 时，确保 join_buffer_size 足够大，能容纳下小表，是避免性能急剧下降的关键。但此参数是 session 级别，不可无限调大，会消耗大量内存。

常见追问与延伸题目

  1. 追问：如果数据量增长 100 倍，这三种 JOIN 算法的性能会如何变化？

    • NLJ：性能下降相对平缓。其复杂度为 O(M×log⁡N)O(M \times \log N)。如果驱动表 M 增长 100 倍，执行时间大致也增长 100 倍。如果被驱动表 N 增长 100 倍，执行时间增长 M×log⁡(100N)M \times \log(100N)，增长非常缓慢。NLJ 的扩展性最好。
    • BNL：性能会急剧恶化甚至崩溃。其复杂度为 O(M+(M/C)×N)O(M + (M/C) \times N)。M 或 N 任何一个增长 100 倍，都会导致被驱动表的扫描次数或每次扫描的数据量剧增，I/O 和 CPU 会被迅速耗尽。BNL 的扩展性最差。
    • Hash Join：性能呈线性下降。其复杂度为 O(M+N)O(M + N)。如果 M 或 N 增长 100 倍，执行时间大致也增长 100 倍。只要内存（join_buffer_size）能容纳下构建表，其扩展性非常好。如果内存不足导致磁盘溢出，性能会下降一个数量级，但仍远好于 BNL。

  2. 追问：在 EXPLAIN 中看到优化器选择了 Hash Join，但你认为走 NLJ 会更快，该怎么办？

    • 分析原因：首先要理解为什么优化器没选 NLJ。
      1. 索引不存在或不适用：检查 JOIN 列上是否有索引，索引是否因函数、类型转换等原因失效。例如 ON t1.varchar_col = t2.int_col 会导致 t2 的索引失效。
      2. 成本估算偏差：MySQL 优化器可能因为统计信息不准（ANALYZE TABLE 可更新），认为全表扫描+Hash Join 的成本低于索引回表+NLJ。例如，当驱动表结果集非常大时，即使有索引，大量的随机 I/O（回表）也可能比一次性顺序扫描更慢。
    • 解决方案：
      1. 强制索引：使用 FORCE INDEX 提示，强制优化器使用指定索引，然后用 EXPLAIN ANALYZE 验证实际性能是否真的更好。这通常用于临时验证或紧急修复。
      2. 优化查询：改写 SQL，确保索引能被使用，例如消除列上的函数。
      3. 更新统计信息：执行 ANALYZE TABLE t1, t2;，让优化器有更准确的决策依据。

  3. 追问：PostgreSQL 或 TiDB 在 JOIN 算法上和 MySQL 有什么不同？

    • PostgreSQL：
      • 算法更丰富：除了 Nested Loop Join 和 Hash Join，PostgreSQL 还支持 Merge Join。Merge Join 要求两个输入源都已按 join_key 排序，然后像拉链一样合并，对于已排序或可以廉价排序的大数据量 JOIN 非常高效。
      • 优化器更成熟：PostgreSQL 的成本优化器在业界享有盛誉，对复杂查询的计划选择通常更智能、更稳定。它很早就支持 Hash Join，并作为处理大数据量无索引 JOIN 的标准方式。
    • TiDB (分布式数据库)：
      • 分布式执行：TiDB 的 JOIN 算法是为分布式环境设计的。它支持 Index Nested Loop Join、Hash Join 和 Merge Join。
      • 特有算法：Index Join 类似于 MySQL 的 NLJ，但它是在分布式架构下，由 TiDB Server 向 TiKV 发起索引读取请求。Hash Join 也是分布式的，数据可能需要在不同节点间通过网络进行 Shuffle（重分布），以确保相同 join_key 的数据在同一个节点上进行计算。
      • 执行策略：TiDB 优化器会根据数据分布、网络成本等因素，选择 Broadcast Join（小表广播）或 Shuffle Join（大表重分布）等不同的物理执行方式。其复杂性远高于单机版的 MySQL。
← Previous
ON 子句和 WHERE 子句对 LEFT JOIN 结果的影响有什么不同？
Next →
什么是驱动表？如何判断哪个表应该作为驱动表？STRAIGHT_JOIN 的作用？