Mysql JOIN 的物理执行流程

一、关联字段在两个表中都没有索引当两个参与join的表在关联字段上都没有索引时MySQL 无法使用高效的索引树搜索而是被迫采用Block Nested-Loop Join (BNL)算法。为了清晰讲解物理流程我们设定如下 SQL 示例 表t1t1t1驱动表100 行数据字段bbb无索引 。表t2t2t2被驱动表1000 行数据字段bbb无索引 。SQL 语句select * from t1 straight_join t2 on (t1.bt2.b);1. 物理执行流程详解在物理层面该操作不再是“点对点”的查找而是一次大规模的“内存对撞”过程 扫描并装载驱动表MySQL 首先全表扫描驱动表t1t1t1将这 100 行数据全部读入线程内存join_buffer中 。注意由于是select *整行数据都会被存入内存 。顺序扫描被驱动表随后MySQL 开始全表扫描被驱动表t2t2t2。它每从磁盘读入t2t2t2的一行数据并不会立即写回结果集 。内存高速比对对于t2t2t2读入内存的每一行MySQL 都会将其与join_buffer中缓存的 100 行t1t1t1数据逐一进行等值判断 。如果匹配成功则作为结果集的一行返回。循环直至结束重复上述过程直到t2t2t2的 1000 行数据全部扫描并比对完毕。2. 核心物理指标在这个示例中虽然 SQL 看似简单但底层的物理开销非常巨大 磁盘扫描行数10010001100100 1000 110010010001100行 。驱动表t1t1t1扫一遍被驱动表t2t2t2扫一遍。内存判断次数100×100010100 \times 1000 \mathbf{10}100×100010万次。这是最消耗 CPU 资源的地方。因为没有索引辅助每一行都必须和内存中所有的行“对撞”一次。3. 极端情况如果join_buffer不够大怎么办如果驱动表t1t1t1很大例如 10 万行而join_buffer只能放得下 1 万行物理流程会演变为分段处理Block从t1t1t1取出前 1 万行放入join_buffer。扫描t2t2t2全表100 万行在内存中进行1万×100万1\text{万} \times 100\text{万}1万×100万次比对 。清空join_buffer。从t1t1t1取出接下来的 1 万行再次全表扫描t2t2t2进行比对 。物理后果此时被驱动表t2t2t2会被重复扫描多次。如果t1t1t1被分成KKK段总扫描行数将变成NK×MN K \times MNK×M。这会产生剧烈的磁盘 IO 波动并严重污染 Buffer Pool导致整个数据库实例响应变慢。二、关联字段在其中一个表中有索引当join关联字段在两个表中呈现“一有一无”的索引状态时MySQL 的物理执行过程取决于优化器对驱动表Driver Table的选择。核心结论是MySQL 优化器会为了利用索引而极力避免BNL 算法通常会选择将带索引的表作为被驱动表。1. 物理流程的两种可能性假设表t1t1t1无索引100 行表t2t2t2有索引1000 行。情况一带索引的表t2t2t2作为“被驱动表”这是最优选此时物理上执行的是Index Nested-Loop Join (NLJ)算法 扫描驱动表全表扫描不带索引的t1t1t1100 行。点对点查找每读出t1t1t1的一行就拿着关联字段的值去t2t2t2的索引树上搜索。物理开销扫描行数100100100 100100100假设 1:1 匹配。计算复杂度100×log⁡21000100 \times \log_2 1000100×log2​1000。结果这是最快的方式因为利用了索引的对数级搜索能力。情况二不带索引的表t1t1t1作为“被驱动表”这是最差选如果因为某些极端原因如t2t2t2过滤后的结果集极小优化器选了t1t1t1倒过来驱动则物理上执行的是Block Nested-Loop Join (BNL)算法 扫描驱动表扫描带索引的t2t2t2将数据放入join_buffer。暴力对撞由于被驱动表t1t1t1没有索引系统必须对t1t1t1执行全表扫描。内存比对将t1t1t1的每一行与内存中的数据进行暴力比对。物理开销内存判断次数1000×100101000 \times 100 \mathbf{10}1000×10010万次。结果性能极差且会大量消耗 CPU 资源 。2. 优化器的“智取”索引权重高于表大小在之前的讲解中我们提到过“小表驱动大表”的原则 。但在“一有一无”的情况下是否有索引对算法效率的影响NLJ vs BNL通常远超表的大小。具体示例表AAA100 行没有索引。表BBB100 万行有索引。虽然表AAA很小但如果选AAA驱动BBB可以走索引NLJ如果选BBB驱动AAA则必须走暴力内存比对BNL。A 驱动 B (NLJ)扫描 100 行 100 次索引树搜索→\rightarrow→毫秒级完成。B 驱动 A (BNL)扫描 100 万行 1 亿次内存比对→\rightarrow→秒级甚至分钟级。因此物理交互的真相是优化器会优先选择那个不带索引的表作为驱动表从而强行让那个带索引的表成为被驱动表以触发 NLJ 或 BKA 算法来提升性能 。三、BKA优化NLJ算法BKABatched Key Access算法是 MySQL 对 Index Nested-Loop JoinNLJ的进一步优化。它的核心逻辑是利用join_buffer批量缓存驱动表的数据并配合MRRMulti-Range Read技术将原本随机的磁盘访问转化为顺序访问。以下是关于 BKA 算法的详细拆解1. 适用场景BKA 算法主要适用于以下场景使用了索引关联即被驱动表的关联字段上有索引这是 NLJ 算法的前提。磁盘 IO 瓶颈当被驱动表数据量较大且无法全部加载进内存时随机回表的代价很高此时 BKA 的提速效果最显著。配置开启由于 BKA 依赖于 MRR而 MRR 的开启策略通常较为保守因此需要手动设置参数以确保 BKA 能够生效setoptimizer_switchmrron,mrr_cost_basedoff,batched_key_accesson;2. 物理执行流程传统的 NLJ 算法是“拿一行驱动表数据去被驱动表查一次索引”。而 BKA 算法改成了“批量处理”批量读入驱动表从驱动表t1中读取满足条件的行并存入join_buffer内存中。构造批量键值当join_buffer存满或者数据读完后将这批记录的关联字段Key一次性发送给被驱动表t2的引擎层。触发 MRR 排序被驱动表t2接收到这批 Key 后利用 MRR 机制进行如下物理操作在普通索引树上找到所有匹配记录的主键 ID。将这些 ID 放入read_rnd_buffer中进行递增排序。按照排序后的主键顺序顺序访问主键索引聚簇索引拉取整行数据。返回结果将取出的t2数据与join_buffer中的t1原始数据进行匹配返回给 Server 层。3. 算法开销分析BKA 虽然极大地提升了查询速度但也带来了一定的资源开销内存开销join_buffer用于缓存驱动表的数据其大小由join_buffer_size决定 。read_rnd_buffer用于 MRR 阶段的主键 ID 排序大小由read_rnd_buffer_size决定。CPU 开销在 MRR 阶段系统需要对主键 ID 序列进行排序操作。如果一次性处理的 ID 数量极其庞大会产生一定的 CPU 计算负担。IO 模式改变正向开销扫描行数不变物理上扫描的行数与传统的 NLJ 并没有区别 。性能提升根源开销的减少主要源于减少了磁头寻道时间。将随机的磁盘跳转改成了连续的块读取这在机械硬盘上是量级的提升在 SSD 上也能减少内部控制器的随机寻址压力。四、HashJoin优化BNL算法由于 MySQL 5.6 和 5.7 版本在内核中并未内置原生的 Hash Join 执行引擎文档主要通过“应用层 Hash Join”来展示其逻辑以解决被驱动表无索引时 Block Nested-Loop Join (BNL) 算法性能低下的问题。Hash Join 的核心物理逻辑是将原本需要“暴力比对”的N×MN \times MN×M次判断通过在内存中构建哈希表降级为近似O(1)O(1)O(1)的定位操作。1. 适用场景无索引关联Join 关联字段在两张表中都没有索引导致无法使用 NLJ 或 BKA 算法。等值连接仅适用于等值 Join如t1.b t2.b因为哈希表无法处理范围查询如或。内存充足内存或应用端内存必须能够容纳较小表Build Table过滤后的全部数据集。2. 物理执行流程以select * from t1 join t2 on t1.b t2.b为例假设t1t1t1为 1000 行t2t2t2为 100 万行。1. 构建阶段 (Build Phase)扫描小表全表扫描驱动表t1t1t1。内存建模在内存中创建一个哈希表Hash Table。哈希计算将t1t1t1的每一行根据关联字段bbb的值计算哈希值然后以bbb为 Key整行数据为 Value 存入哈希表。2. 探测阶段 (Probe Phase)扫描大表全表扫描被驱动表t2t2t2。命中检索对于t2t2t2读入内存的每一行取其字段bbb的值进行同样的哈希计算。定位匹配直接去哈希表中检索对应的 Key。匹配成功直接取出t1t1t1的数据进行拼装返回结果。匹配失败继续处理t2t2t2的下一行。3. 算法开销分析1. 扫描行数 (IO 开销)磁盘扫描NMN MNM。优势每个表都只做一次物理全表扫描彻底规避了 BNL 算法中被驱动表可能被重复扫描多次的问题 。2. CPU 计算开销复杂度由 BNL 的O(N×M)O(N \times M)O(N×M)暴力比对降级为O(NM)O(N M)O(NM)。物理意义内存中进行的不再是数亿次的字符串或数值比较而是极快且次数极少的哈希计算与指针定位。3. 内存开销空间占用必须在内存中开辟足以存储整个驱动表Build表结果集的空间。风险如果结果集超过内存上限会导致严重的内存溢出OOM或必须借用磁盘临时文件进行分块处理Graceful Hash Join这会引入额外的磁盘 IO 损耗 。4. 具体示例对比背景t1t1t11000行t2t2t2100万行字段bbb均无索引。指标Block Nested-Loop (BNL)Hash Join (应用层)物理逻辑扫描t2t2t2时每一行都要跟内存里的 1000 行t1比对扫描t2t2t2时每一行只算一次哈希直接定位t1t1t1内存判断次数10 亿次(1000×100万1000 \times 100万1000×100万)100 万次哈希查找执行耗时约71.95 秒 1 秒总结Hash Join 的物理精髓是“空间换时间”。它通过在内存中提前构建高效的索引结构哈希表消除了 Join 过程中最昂贵的笛卡尔积式暴力比对。