大家好，我是历小冰，今天我们来学习和吐槽一下MySQL的Join功能。
关于MySQL的join，大家一定了解过很多它的“轶事趣闻”，比如两表join要小表驱动大表，阿里开发者规范禁止三张表以上的join操作，MySQL的join功能弱爆了等等。这些规范或者言论亦真亦假，时对时错，需要大家自己对join有深入的了解后才能清楚地理解。
下面，我们就来全面的了解一下MySQL的join操作。
正文
在日常数据库查询时，我们经常要对多表进行连表操作来一次性获得多个表合并后的数据，这是就要使用到数据库的join语法。join是在数据领域中十分常见的将两个数据集进行合并的操作，如果大家了解的多的话，会发现MySQL，Oracle，PostgreSQL和Spark都支持该操作。本篇文章的主角是MySQL，下文没有特别说明的话，就是以MySQL的join为主语。而Oracle，PostgreSQL和Spark则可以算做将其吊打的大boss，其对join的算法优化和实现方式都要优于MySQL。
MySQL的join有诸多规则，可能稍有不慎，可能一个不好的join语句不仅会导致对某一张表的全表查询，还有可能会影响数据库的缓存，导致大部分热点数据都被替换出去，拖累整个数据库性能。
所以，业界针对MySQL的join总结了很多规范或者原则，比如说小表驱动大表和禁止三张表以上的join操作。下面我们会依次介绍MySQLjoin的算法，和Oracle和Spark的join实现对比，并在其中穿插解答为什么会形成上述的规范或者原则。
对于join操作的实现，大概有NestedLoopJoin(循环嵌套连接)，HashJoin(散列连接)和SortMergeJoin(排序归并连接)三种较为常见的算法，它们各有优缺点和适用条件，接下来我们会依次来介绍。
MySQL中的NestedLoopJoin实现
NestedLoopJoin是扫描驱动表，每读出一条记录，就根据join的关联字段上的索引去被驱动表中查询对应数据。它适用于被连接的数据子集较小的场景，它也是MySQLjoin的唯一算法实现，关于它的细节我们接下来会详细讲解。
MySQL中有两个NestedLoopJoin算法的变种，分别是IndexNested-LoopJoin和BlockNested-LoopJoin。
IndexNested-LoopJoin算法
下面，我们先来初始化一下相关的表结构和数据
有上述命令可知，这两个表都有一个主键索引id和一个索引a，字段b上无索引。存储过程init_data往表t1里插入了行数据，在表t2里插入的是行数据。
为了避免MySQL优化器会自行选择表作为驱动表，影响分析SQL语句的执行过程，我们直接使用straight_join来让MySQL使用固定的连接表顺序进行查询，如下语句中，t1是驱动表，t2是被驱动表。
select*fromt2straight_joint1on(t2.a=t1.a);
使用我们之前文章介绍的explain命令查看一下该语句的执行计划。
从上图可以看到，t1表上的a字段是由索引的，join过程中使用了该索引，因此该SQL语句的执行流程如下：
从t2表中读取一行数据L1；使用L1的a字段，去t1表中作为条件进行查询；取出t1中满足条件的行，跟L1组成相应的行，成为结果集的一部分；重复执行，直到扫描完t2表。这个流程我们就称之为IndexNested-LoopJoin，简称NLJ，它对应的流程图如下所示。
需要注意的是，在第二步中，根据a字段去表t1中查询时，使用了索引，所以每次扫描只会扫描一行(从explain结果得出，根据不同的案例场景而变化)。
假设驱动表的行数是N，被驱动表的行数是M。因为在这个join语句执行过程中，驱动表是走全表扫描，而被驱动表则使用了索引，并且驱动表中的每一行数据都要去被驱动表中进行索引查询，所以整个join过程的近似复杂度是N2log2M。显然，N对扫描行数的影响更大，因此这种情况下应该让小表来做驱动表。
当然，这一切的前提是join的关联字段是a，并且t1表的a字段上有索引。
如果没有索引时，再用上图的执行流程时，每次到t1去匹配的时候，就要做一次全表扫描。这也导致整个过程的时间复杂度编程了N*M，这是不可接受的。所以，当没有索引时，MySQL使用BlockNested-LoopJoin算法。
BlockNested-LoopJoin
BlockNested-LoopJoin的算法，简称BNL，它是MySQL在被驱动表上无可用索引时使用的join算法，其具体流程如下所示：
把表t2的数据读取当前线程的join_buffer中，在本篇文章的示例SQL没有在t2上做任何条件过滤，所以就是讲t2整张表放入内存中；扫描表t1，每取出一行数据，就跟join_buffer中的数据进行对比，满足join条件的，则放入结果集。比如下面这条SQL
select*fromt2straight_joint1on(t2.b=t1.b);
这条语句的explain结果如下所示。可以看出
可以看出，这次join过程对t1和t2都做了一次全表扫描，并且将表t2中的条数据全部放入内存join_buffer中，并且对于表t1中的每一行数据，都要去join_buffer中遍历一遍，都要做次对比，所以一共要进行*次内存对比操作，具体流程如下图所示。
主要注意的是，第一步中，并不是将表t2中的所有数据都放入join_buffer，而是根据具体的SQL语句，而放入不同行的数据和不同的字段。比如下面这条join语句则只会将表t2中符合b=的数据的b字段存入join_buffer。
selectt2.b,t1.bfromt2straight_joint1on(t2.b=t1.b)wheret2.b=;
join_buffer并不是无限大的，由join_buffer_size控制，默认值为K。当要存入的数据过大时，就只有分段存储了，整个执行过程就变成了：
扫描表t2，将符合条件的数据行存入join_buffer，因为其大小有限，存到行时满了，则执行第二步；扫描表t1，每取出一行数据，就跟join_buffer中的数据进行对比，满足join条件的，则放入结果集；清空join_buffer；再次执行第一步，直到全部数据被扫描完，由于t2表中有行数据，所以一共重复了5次这个流程体现了该算法名称中Block的由来，分块去执行join操作。因为表t2的数据被分成了5次存入join_buffer，导致表t1要被全表扫描5次。
如上所示，和表数据可以全部存入join_buffer相比，内存判断的次数没有变化，都是两张表行数的乘积，也就是*，但是被驱动表会被多次扫描，每多存入一次，被驱动表就要扫描一遍，影响了最终的执行效率。
基于上述两种算法，我们可以得出下面的结论，这也是网上大多数对MySQLjoin语句的规范。
被驱动表上有索引，也就是可以使用IndexNested-LoopJoin算法时，可以使用join操作。无论是IndexNested-LoopJoin算法或者BlockNested-LoopJoin都要使用小表做驱动表。因为上述两个join算法的时间复杂度至少也和涉及表的行数成一阶关系，并且要花费大量的内存空间，所以阿里开发者规范所说的严格禁止三张表以上的join操作也是可以理解的了。
但是上述这两个算法只是join的算法之一，还有更加高效的join算法，比如HashJoin和SortedMergedjoin。可惜这两个算法MySQL的主流版本中目前都不提供，而Oracle，PostgreSQL和Spark则都支持，这也是网上吐槽MySQL弱爆了的原因(MySQL8.0版本支持了Hashjoin，但是8.0目前还不是主流版本)。
其实阿里开发者规范也是在从Oracle迁移到MySQL时，因为MySQL的join操作性能太差而定下的禁止三张表以上的join操作规定的。
HashJoin算法
HashJoin是扫描驱动表，利用join的关联字段在内存中建立散列表，然后扫描被驱动表，每读出一行数据，并从散列表中找到与之对应数据。它是大数据集连接操时的常用方式，适用于驱动表的数据量较小，可以放入内存的场景，它对于没有索引的大表和并行查询的场景下能够提供最好的性能。可惜它只适用于等值连接的场景，比如ona.id=whereb.a_id。
还是上述两张表join的语句，其执行过程如下
将驱动表t2中符合条件的数据取出，对其每行的join字段值进行hash操作，然后存入内存中的散列表中；遍历被驱动表t1，每取出一行符合条件的数据，也对其join字段值进行hash操作，拿结果到内存的散列表中查找匹配，如果找到，则成为结果集的一部分。可以看出，该算法和BlockNested-LoopJoin有类似之处，只不过是将无序的JoinBuffer改为了散列表hashtable，从而让数据匹配不再需要将joinbuffer中的数据全部遍历一遍，而是直接通过hash，以接近O(1)的时间复杂度获得匹配的行，这极大地提高了两张表的join速度。
不过由于hash的特性，该算法只能适用于等值连接的场景，其他的连接场景均无法使用该算法。
SortedMergeJoin算法
SortMergeJoin则是先根据join的关联字段将两张表排序(如果已经排序好了，比如字段上有索引则不需要再排序)，然后在对两张表进行一次归并操作。如果两表已经被排过序，在执行排序合并连接时不需要再排序了，这时MergeJoin的性能会优于HashJoin。MergeJoin可适于于非等值Join（，，=，=，但是不包含!=，也即）。
需要注意的是，如果连接的字段已经有索引，也就说已经排好序的话，可以直接进行归并操作，但是如果连接的字段没有索引的话，则它的执行过程如下图所示。
遍历表t2，将符合条件的数据读取出来，按照连接字段a的值进行排序；遍历表t1，将符合条件的数据读取出来，也按照连接字段a的值进行排序；将两个排序好的数据进行归并操作，得出结果集。SortedMergeJoin算法的主要时间消耗在于对两个表的排序操作，所以如果两个表已经按照连接字段排序过了，该算法甚至比HashJoin算法还要快。在一边情况下，该算法是比NestedLoopJoin算法要快的。
下面，我们来总结一下上述三种算法的区别和优缺点。
对于Join操作的理解
讲完了Join相关的算法，我们这里也聊一聊对于join操作的业务理解。
在业务不复杂的情况下，大多数join并不是无可替代。比如订单记录里一般只有订单用户的user_id，返回信息时需要取得用户姓名，可能的实现方案有如下几种：
一次数据库操作，使用join操作，订单表和用户表进行join，连同用户名一起返回；两次数据库操作，分两次查询，第一次获得订单信息和user_id，第二次根据user_id取姓名，使用代码程序进行信息合并；使用冗余用户名称或者从ES等非关系数据库中读取。上述方案都能解决数据聚合的问题，而且基于程序代码来处理，比数据库join更容易调试和优化，比如取用户姓名不从数据库中取，而是先从缓存中查找。
当然，join操作也不是一无是处，所以技术都有其使用场景，上边这些方案或者规则都是互联网开发团队总结出来的，适用于高并发、轻写重读、分布式、业务逻辑简单的情况，这些场景一般对数据的一致性要求都不高，甚至允许脏读。
但是，在金融银行或者财务等企业应用场景，join操作则是不可或缺的，这些应用一般都是低并发、频繁复杂数据写入、CPU密集而非IO密集，主要业务逻辑通过数据库处理甚至包含大量存储过程、对一致性与完整性要求很高的系统。
个人博客，欢迎来玩