MySQL相关的JOIN算法

先来回顾一下单机版MySQL的Join算法。

1.1 Nested-Loop Join Algorithm（嵌套循环Join算法）

最简单的Join算法及外循环读取一行数据，根据关联条件列到内循环中匹配关联，在这种算法中，我们通常称外循环表为驱动表，称内循环表为被驱动表。

Nested-Loop Join 算法的伪代码如下:

1.2 Block Nested-Loop Join Algorithm（BNL算法）

BNL算法是对 Nested-Loop Join 算法的优化。具体做法是将外循环的行缓存起来，读取缓冲区中的行，减少内循环表被扫描的次数。例如，外循环表与内循环表均有100行记录，普通的嵌套内循环表需要扫描100次，如果使用块嵌套循环，则每次外循环读取10行记录到缓冲区中，然后把缓冲区数据传递给下一个内循环，将内循环读取到的每行和缓冲区中的10行进行比较，这样内循环表只需要扫描10次即可完成，使用块嵌套循环后内循环整体扫描次数少了一个数量级。使用块嵌套循环，内循环表扫描方式应是全表扫描，因为是内循环表匹配Join Buffer中的数据的。使用块嵌套循环连接，MySQL会使用连接缓冲区（Join Buffer），且会遵循下面一些原则：

• 连接类型为ALL、index、range，会使用到 Join Buffer。
• Join Buffer 是由 join_buffer_size 变量控制的。
• 每次连接都使用一个 Join Buffer，多表的连接可以使用多个 Join Buffer。
• Join Buffer 只存储与查询操作相关的字段数据，而不是整行记录。

BNL算法的伪代码如下：

对上面的过程解释如下：

①将t1、t2的连接结果放到缓冲区中，直到缓冲区满为止。

②遍历t3，与缓冲区内的数据匹配，找到匹配的行，发送到客户端。

③清空缓冲区。

④重复上面的步骤，直至缓冲区不满。

⑤处理缓冲区中剩余的数据，重复步骤②。

假设S是每次存储t1、t2组合的大小，C是组合的数量，则t3被扫描的次数为：(S * C) / join_buffer_size + 1

由此可见，随着join_buffer_size的增大，t3被扫描的次数会减少，如果join_buffer_size足够大，大到可以容纳所有t1和t2连接产生的数据，那么t3只会被扫描一次。

来看一个具体的案例：

1.3 Index Nested-Loop Join Algorithm（INLJ算法）

索引嵌套循环连接算法是基于嵌套循环算法的改进版，其优化的思路主要是为了减少了内层循环匹配次数，就是通过外层数据循环与内存索引数据进行匹配，这样就避免了内层循环数据逐个与外层循环的数据进行对比，从 “原来的匹配次数 = 外层所有行数据 * 内层所有行数据” 优化成 “外层所有行数据 * 索引树的高度”，极大的提高的查询效率。

SQL案例：

上面SQL大致执行流程如下图所示：

• 从t2表中读取一行记录
• 从第1步记录中,取出关联字段a到t表的辅助索引树中进行查找
• 从t1表中取出辅助索引树中满足条件的记录拿出主键ID到主键索引中根据主键ID将剩下字段的数据取出与t2中获取到的结果进行合并，将结果放入结果集
• 循环上面三个步骤，直到无法满足条件，将结果集返回给客户端

基于嵌套循环连接算法进行优化，虽然还是双层循环进行匹配数据，但是内层循环（被驱动表）是使用索引树的高度决定循环次数的，这样的话，无论驱动表和被驱动表的数据多大，效率还是很高的。

1.4 Batched Key Access（BKA）

BKA是对BNL算法的更进一步扩展及优化，其作用是在表连接时可以进行顺序I/O，所以BKA是在MRR（Multi-Range Read）基础之上实现的，同时BKA支持内连接、外连接和半连接操作。

当两个表连接时，在没有BKA的情况下如下图所示，可以看到访问t2表时是随机I/O。

有了BKA之后如下图所示，可以看到对t2表进行连接访问时，先将t1中相关的字段放入 Join buffer 中，然后利用MRR特性接口进行排序（根据rowid），排序之后即可通过rowid到t2表中进行查找。

这里也有一个隐含的条件，就是关联字段需要有索引，否则还是会使用BNL算法的。

Hash Join

在8.0.18之前，MySQL只支持NestLoopJoin算法。虽然MySQL对于Join做过若干优化，比如NBLJ、INLJ以及BKA等，但这些代替不了HashJoin的作用。

Hash join 跟 Block Nested-Loop Join 类似，都是把一批数据放进hash table里面再与另一个表进行join操作，区别是 Block Nested-Loop Join 有固定的buffer大小，而 hash join 没有固定的大小，是把整张表的数据都放进内存中的 hash table 里面。如果放不下的话怎么办呢？放不下的话就会分成若干个partition，写入磁盘的 temporary segment。

所以hash join这种方式适用于表比较小的情况，适用于较小的表整张表都能放入内存中的情况，如果一次放不完，IO次数就会变多，影响性能。时间复杂度为O(n)级别。

Merge Join

Merge join 又称 Sorted-Merge join，就是先对两张表所关联的列进行排序。例如有两张表tA和tB：

执行下面SQL：

select * from tA 
left join tB on tA.id=tB.id;

先对tA和tB分别按照id进行排序，那么tA和tB的id的顺序都变成了1、2、3、4。

这样再做join的时候，就能从上到下一一对应了。Merge join 的时间复杂度为O(nlogn)级别（即排序的时间复杂度），不如 Hash join，但是若两张表的关联列本来就是有序的，那就省去了排序的过程，这时候时间复杂度为O(n)级别，优于 Hash join，节约了找hash值的时间。

JOIN在MapReduce中的实现

直接上具体的栗子：

select 
    u.name
    , o.orderid 
from order o 
join user u on o.uid = u.uid;

在map的输出value中为不同表的数据打上tag标记，在reduce阶段根据tag判断数据来源。MapReduce的过程如下（这里只是说明最基本的Join的实现，还有其他的实现方式）：

从上图可以看到key相同的记录经过shuffle后排在一起。

ShardingSphere中的Join

ShardingSphere由Federation执行引擎（开发中）提供支持，对关联查询、子查询等复杂查询进行优化，同时支持跨多个数据库实例的分布式查询，内部使用关系代数优化查询计划，通过最优计划查询出结果。

ShardingSphere的3个产品的数据分片主要流程是完全一致的，按照是否进行查询优化，可以分为Standard内核流程和Federation执行引擎流程：

• Standard内核流程由 SQL 解析 => SQL 路由 => SQL 改写 => SQL 执行 => 结果归并 组成，主要用于处理标准分片场景下的 SQL 执行
• Federation执行引擎流程由 SQL 解析 => 逻辑优化 => 物理优化 => 优化执行 => Standard 内核流程 组成，Federation执行引擎内部进行逻辑优化和物理优化，在优化执行阶段依赖Standard内核流程，对优化后的逻辑SQL进行路由、改写、执行和归并