MySQL Join 算法演进从 BNL 到 Block Nested-Loop 的内存缓冲机制在关系型数据库查询优化器中如何高效处理多表之间的JOIN关联操作是决定查询吞吐与响应延迟的最核心战役之一。在 MySQL 的演进历程中连接算法经历了几代重大的架构跃迁。在没有被驱动表索引可用的最恶劣工况下MySQL 曾经长期依赖Block Nested-Loop JoinBNL块嵌套循环连接算法来支撑全表的关联查询。理解 BNL 的物理机制与内存缓冲原理不仅能帮我们搞清楚为什么旧版本 MySQL 处理无索引 JOIN 时极易卡死更能看清为什么 MySQL 8.0.20 之后官方会痛下决心用Hash Join彻底将其淘汰。// 伪代码解析Block Nested-Loop (BNL) 的双层分块循环逻辑 void BlockNestedLoopJoin(Table outer_table, Table inner_table, size_t join_buffer_size) { JoinBuffer join_buffer(join_buffer_size); while (!outer_table.is_eof()) { // 1. 清空内存 Join Buffer尽可能多地装入外表驱动表的记录与投影字段 join_buffer.clear(); while (!outer_table.is_eof() !join_buffer.is_full()) { Row outer_row outer_table.next_row(); if (matches_outer_predicates(outer_row)) { join_buffer.append(outer_row); } } // 2. 将内表被驱动表游标重置回表头执行一次全表物理扫描 inner_table.rewind(); while (!inner_table.is_eof()) { Row inner_row inner_table.next_row(); // 3. 在内存中将内表单行与 Join Buffer 中的所有外表行逐一进行 CPU 内存比对 for (const Row outer_cached_row : join_buffer.rows()) { if (matches_join_condition(outer_cached_row, inner_row)) { output_result(outer_cached_row, inner_row); } } } } }从朴素 SNLJ 到 BNL减少磁盘扫描次数的自救假设外表驱动表$R$ 包含 10 万行数据内表被驱动表$S$ 包含 100 万行数据且连接字段上没有任何索引1. 朴素嵌套循环Simple Nested-Loop Join, SNLJ外表每读出一行记录就去内表做一次全表扫描。内表被扫描的总次数$100,000$ 次总共需要读取的记录数$100,000 \times 1,000,000 1000 \text{ 亿次}$在单机磁盘上这种查询耗时通常以天为单位系统必崩无疑。2. 块嵌套循环Block Nested-Loop Join, BNL为了拯救这种灾难MySQL 引入了join_buffer。如上述代码所示优化器不再一行一行读外表而是先将外表的大量数据装入内存的join_buffer由参数join_buffer_size控制默认 256KB。假设 256KB 内存一次能装下 10,000 行外表数据那么处理完 10 万行外表只需要分 10 个批次Chunks内表的物理扫描次数从 10 万次断崖式下降到了 10 次[BNL 块缓存与内表扫描时序对比] 外表 10万行 ──▶ [批次 1: 10,000行 写入 Join Buffer] ──▶ 内表全表扫描 1次 (内存比对 1000万次) ──▶ [批次 2: 10,000行 写入 Join Buffer] ──▶ 内表全表扫描 1次 (内存比对 1000万次) ... ──▶ [批次 10: 10,000行 写入 Join Buffer] ──▶ 内表全表扫描 1次 (内存比对 1000万次) ───────────────────────────────────────────────────────────── 内表物理全表扫描次数从 100,000 次骤降至 10 次BNL 的致命死穴Buffer Pool 污染与 CPU 空转虽然 BNL 大幅减少了内表的磁盘扫描次数但在高并发生产环境中它依然是一颗危险的定时炸弹1. 内存比对复杂度依然是 $O(M \times N)$内表虽然只被扫描了 10 次但内表的每一行在内存中依然需要与 Join Buffer 中的 10,000 行记录进行遍历比对。总的 CPU 内存比较次数依然是 $10 \times 10,000 \times 1,000,000 1000 \text{ 亿次}$单核 CPU 会瞬间被拉升至 100%。2. 对 InnoDB Buffer Pool 的毁灭性冷数据污染在扫描内表这 10 次的过程中由于内表体积庞大例如 20GBMySQL 会频繁从磁盘将大量冷数据页加载进内存 Buffer Pool。虽然 InnoDB 拥有 LRU 改进算法老生代与新生代隔离但如果单次 BNL 扫描耗时超过了innodb_old_blocks_time默认 1000ms大量原本属于其他核心 OLTP 业务的高频热点缓存页就会被无情挤出内存引发全站范围的缓存穿透与磁盘 IO 尖刺。-- MySQL 8.0.20 执行计划展示BNL 已被现代 Hash Join 全面替代 mysql EXPLAIN FORMATtree SELECT * FROM t_user u JOIN t_order o ON u.user_level o.discount_level\G *************************** 1. row *************************** EXPLAIN: - Inner hash join (u.user_level o.discount_level) (cost1250000.00 rows500000) - Table scan on o (cost50000.00 rows1000000) - Hash - Table scan on u (cost10000.00 rows100000)终结者降临Hash Join 的全面替代在 MySQL 8.0.20 之后官方全面废弃了 BNL引入了现代分析型数据库标准的Hash Join在内存中基于外表直接构建 $O(1)$ 时间复杂度的哈希表扫描内表时每行记录直接计算 Hash 探针Probe命中匹配项全表扫描仅需 1 次CPU 比较时间复杂度直接从 $O(M \times N)$ 降至 $O(M N)$理解 BNL 的兴衰史是看懂关系型数据库如何从早期的“磁盘节约型设计”迈向现代“内存与 CPU 友好型架构”的绝佳窗口。