目录

Index Nested-Loop Join（NLJ）

Block Nested-loop Join（BNL）

Batch Key Access（BKA）

总结：

---

    上一篇博客分析了想要实现的各种join方式和效果，但是对于join（inner join、left join、right join）操作还是一个黑盒子，现在就需要知道join操作内部的运作机制，才能更好的进行优化。join操作按照被驱动表的链接字段是否有索引分为：Index Nested-loop join（简称NLJ）、Block Nested loop join。比如 select * from A inner join B on A.key = B.key where b.key2 = ?，此时到底A表是驱动表还是B表是驱动表由 Mysql Server层的 优化器决定，而Mysql - 优化器阶段的索引选择过程我们知道优化器会根据表的数据页进行采样分析，重新采样分析有自己的触发机制，我们也可以使用命令 analyze table t强制重新执行采样分析。

    影响优化器选择驱动表的选择因素有：采样统计分析，是否使用索引，是否回表等，此处join操作还有选择的原因就是选择小表做作为驱动表，而小表不一定是表数据总条数少。可能表条数非常多但是后面的where条件过滤后的条数非常少；并且与每条数据的大小有关，可能一条数据100个字段1K大小，另一张表的一条数据只有3个字段10字节。当线上执行的sql不是按照我们想要的inner join方式选择驱动表，那么我们就可以使用 A straght_join B的方式强制选择A为驱动表，因为join执行的时候驱动表就是走的主键索引（即全表扫描），而被驱动表会按照（on）链接字段查找、对比，被驱动表查找的过程就是：有索引就使用索引的B+树，没有索引才会全表。如下图中，强制表 t1为驱动表【type为ALL全表扫描】，t2为被驱动表【type为ref】：

Index Nested-Loop Join（NLJ）

    比如执行上面的sql执行计划，t1为1驱动表，t2为被驱动表，并且t2表的a字段添加了索引，那么会执行 Index Nested-loop Join流程，如下：

1. 从驱动表t1中读取一条数据【比如为R】，即从t1表是主键索引上获取一条记录行（全表扫描）；【如果驱动表的字段 a 有索引，那么会先从a字段的二级索引查询，再回表到主键索引查询；否则直接查询主键索引的数据，过滤满足a字段的条件】
2. 从数据行R中获取到字段a，再去表t2中查找（此时的时间复杂度为O(logN)）；
3. 取出t2中满条件的行，与t1表的记录R组成结果集的一行数据（此时需要根据select后面想要的字段决定）；【被驱动表的字段 a 有索引，那么会先从a字段的二级索引查询，再回表到主键索引查询】
4. 重复1~3的步骤，一直到获取完驱动表的满足条件的数据；（如果sql增加了where t1的 id < 20，则只从驱动表上获取满足条件的数据行）

即整个过程就是从驱动表上全表扫描获取满足条件的数据行，比如总条数为 X，那么整个查询驱动表的时间复杂度就是 X； 如果被驱动表的总条数为Y，那么根据二级索引再回表查询的时间复杂度为：2*log₂Y； 所以join的整体时间复杂度为：X + X*2*log₂Y，忽略常数和系数使用大O时间复杂度表示，Index Nested-loop join的时间复杂度为：X+X*logY。     O(N)与O(logN)的时间复杂度对比是，当数据规模到达 42亿时，O(N)的处理次数为 42亿，而O(logN)处理次数为 32次，这也是指数级的性能恐怖之处。所以根据该复杂度，选择数据量比较小的表作为驱动表，执行O(N)。

总结：Index Nested-loop join选择小表作为驱动表，性能会从O(N)提升到O(logN)。

 

Block Nested-loop Join（BNL）

    如果被驱动表链接字段上没有索引，此时整个过程会在join buffer中处理，称为 Block Nested-loop Join。join buffer是Mysql分给每一个执行线程的，由配置 join_buffer_size决定，默认大小为 256k。此时分为两种情况，可以一次性将两张表的数据加载到join buffer中，和需要分段加载到 join buffer中的过程分析：

join buffer足够大：

1. 两张表都全表扫描，执行的总行数就是 X + Y；
2. 内存中判断两张表的链接字段是否相等，判断此时就是 X*Y；

   所以此时无论使用 X+Y还是X*Y判断，谁作为驱动表，执行的效率是一样的。

分段加入：join buffer 【info：从B+树上只能一行一行的读取数据】

1. 将驱动表中是数据顺序读取出来放入join buffer，如果读取到某一行时，join buffer放不下了，从此处开始分块，下次继续读取；
2. 扫描被驱动表，一行一行的读取出来，与join buffer中的数据对比满足 on 链接字段的条件，则放入结果集中作为一部分；
3. 清空 join buffer；
4. 继续扫描驱动表中的下一个段的数据，执行上面的1~3步，一直到将驱动表的满足条件的数据都在join buffer中加载一遍。

    此时可以看出 Block Nested-loop Join中的Block（块）就是上面的join buffer分成的块，即 驱动表的扫描一遍的总大小 / join buffer = Block块数。所以，执行大表的join操作时，如果被驱动表的链接字段没有索引，执行Block Nested loop join流程，适当增加 join buffer的大小可以提升执行效率，因为Block每多一次，就需要多扫描一遍被驱动表的满足条件的总数据。

    整个过程内存中判断的次数任然是 X*Y次。 而扫描的段数除了与join buffer的带下有关，并且 驱动表的总大小数越大则 需要分的块数越多，所以需要分段的情况下，任然是小表作为驱动表性能高一些。

    当执行两张大表的join操作时，即使选择较小的表作为驱动表，分的块也会比较多，那么被驱动表扫描 块 次。性能影响：执行的时间会比较长，对io的性能影响在执行完成后就结束了。但是Mysql - InnoDB三大特性之Buffer Pool缓冲池我们知道，Mysql的 Buffer Pool LRU即使分为young和old区，来防止大表的全表扫描对缓存淘汰策略lru的影响。但是innodb_old_blocks_time控制old区晋升为young区的时间默认为1s，当执行 块 次被驱动表的全表扫描后，超过1s，那么就会对LRU照成冲击，降低缓存命中率，需要很长一段时间才能将命中率恢复。

   即大表join操作的影响有：

1. 执行效率低，执行延迟高，客户端等待时间长
2. 两张大表多次全表扫描，瞬间io比较高
3. 需要在内存中判断 X*Y次，对CPU影响比较高
4. 对InnoDB缓冲池 LRU的缓存命中率影响，将热点数据淘汰，需要一段时间后才能恢复。

 

Batch Key Access（BKA）

    Index Nesed-loop Join操作就是性能最好的吗？ 还可以优化。其过程中会涉及在被驱动表中执行大量的 二级索引 -> 主键索引的查询过程，就会涉及大量的 随机访问磁盘的可能。随机访问磁盘，是Mysql中性能影响非常大的操作。因为大多数的数据都是按照主键递增顺序插入得到的，所以我们可以认为，如果按照主键的递增顺序查询的话，对磁盘的读比较接近顺序读，能够提升读性能。

MRR（Mutil-Range Read）

    Mrr就是针对上面将 随机io 尽量转变为局部顺序io的原理，将大量回标操作的主键集合在 read_rnd_buffer中进行排序达到局部有序的效果，由配置参数 read_rnd_buffer_size控制。整体过程如下：

1. 根据二级索引B+树，获取到大量的主键索引的id集合，并将主键id的值放入 read_rnd_buffer；
2. 将read_rnd_buffer中的id集合进行升序排序；
3. 根据排序后的id依次再到主键索引中获取数据，即提升了回标的性能。

MRR不仅仅可以体现在join操作，其实只要涉大量及从二级索引到主键索引的回标操作，都可以使用MRR，比如范围查询操作。执行流程如下图：

 

    Index Nested-loop Join操作的大量回标可以使用MRR进行优化，此方式称为：Batched Access Key（BKA），即NLJ join还可以优化为 BKA。在Mysql 5.6引入了 Batched Access Key（BKA）算法，只是优化成BKA需要执行下面的命令（或设置该参数）。官方文档的说法，是现在的优化器策略，判断消耗的时候，会更倾向于不使用 MRR，把 mrr_cost_based 设置为 off，就是固定使用 MRR 了。

set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

    Index Nested-Loop Join操作时，Mysql分配的该执行线程的 Join Buffer是没有使用的。MRR操作，比如执行区间查询时使用 read_rnd_buffer进行回表主键字段的排序操作，将BKA join方式 = Index Nesed-loop Join + MRR，此时就直接利用 join buffer将回表的主键进行排序。BKA整体流程图如下：

 

总结：

1、inner join时谁作为驱动表和被驱动表由优化器进行决定，而前面分析过优化器根据对索引进行才有分析，重新采样分析有自己的触发机制。索引包括：整个表数据的主键聚簇索引、其他二级索引。但是如果我们根据执行计划发现，并没有按照我们想要的方式选择驱动表，那么可以使用 straight_join 强制指定驱动表。straight_join 只对inner join 有效，left join 和 right join无效。

2、Index Nested-loop Join方式，可以将驱动表的时间复杂度从O(N)降低为O(logN)。 使用Block Nested-loop join如果可以一次将两张表的数据都加载到内存中，谁作为驱动表效果都一样；只是join buffer大小默认为256K,并且该参数针对每一个线程设置不能过大，执行时将驱动表根据join buffer 分块，执行 块 * 被驱动表扫描全数据次数，所以分块时也应该尽量选择小表作为驱动表。整体来说，无论使用哪种方式join，都尽量使用小表作为驱动表。

3、如果可以对join的被驱动表链接字段添加索引，让 Block Nested-loop join变成 Index Nested-loop join 最好。否则，可以适当调整Join buffer大小，并且一定保证小表是驱动表，否则可以使用 straight_join。

4、Index Nested-loop Join可以再优化为 BKA算法。底层就是利用 Join buffer，将大量需要回表查询的主键进行排序，将随机io转换为大量局部有序io。