本文转载自微信公众号“程序员李小兵”，可通过以下二维码关注。转载本文请联系程序员李小兵公众号。大家好，我是李小兵。今天我们就来学习和吐槽MySQL的Join功能。关于MySQL的加入，想必大家对它的“奇闻轶事”知之甚多。比如两张表的join需要小表带动大表，阿里开发者规范禁止超过三张表的join操作，MySQL的join功能弱等等等。这些规范或言论或对或错，时而对时而错，需要对join有深刻的理解才能看得清楚。下面我们来全面了解一下MySQL的join操作。文本在日常的数据库查询中，我们经常需要对多张表进行join操作，一次性获取多张表的合并数据。这是数据库的连接语法。join是数据领域中非常常见的操作，用于合并两个数据集。如果你更了解它，你会发现MySQL、Oracle、PostgreSQL和Spark都支持这个操作。本文的主角是MySQL。下面如果没有特别说明，就以MySQL的join为主。另一方面，Oracle、PostgreSQL和Spark算得上是吊打他们的大佬，他们对join的算法优化和实现方式都比MySQL好。MySQL的join有很多规则，可能有点粗心。错误的join语句不仅可能导致对某个表进行全表查询，还可能影响数据库的缓存，导致大部分热数据被替换掉。out，拖累了整个数据库的性能。因此，业界总结了很多MySQLjoin的规范或原则，比如小表带动大表，禁止超过三张表的join操作。下面我们将依次介绍MySQL的join算法，将其与Oracle、Spark的join实现进行对比，并穿插回答为什么会形成上述规范或原则。对于join操作的实现，常见的算法大概有3种：NestedLoopJoin（循环嵌套连接）、HashJoin（哈希连接）和SortMergeJoin（排序合并连接），各有优缺点适用条件。接下来，我们将依次介绍它们。MySQLNestedLoopJoin的实现NestedLoopJoin是扫描驱动表，每读取一条记录，根据join关联字段上的索引，在驱动表中查询对应的数据。适用于需要join的数据子集较小的场景，也是mysqljoin的唯一算法实现。接下来我们将详细解释它的细节。MySQL中的NestedLoopJoin算法有两种变体，即IndexNested-LoopJoin和BlockNested-LoopJoin。在IndexNested-LoopJoin算法下面，我们先初始化相关的表结构和数据CREATETABLE`t1`(`id`int(11)NOTNULL,`a`int(11)DEFAULTNULL,`b`int(11)DEFAULTNULL,PRIMARYKEY(`id`),KEY`a`(`a`))ENGINE=InnoDB;delimiter;;#定义存储过程初始化t1createprocedureinit_data()begindeclareiint;seti=1;while(i<=10000)doinsertintot1values(i,i,i);seti=i+1;endwhile;end;;delimiter;#调用并存储初始化t1callinit_data();#创建并初始化t2createtablet2liket1;insertintot2(select*fromt1whereid<=500)可以看出以上命令，这两个表都有一个主键索引id和一个索引a，字段b上没有索引。存储过程init_data向表t1插入10000行数据，向表t2插入500行数据。为了防止MySQL优化器自己选择表作为驱动表，影响分析SQL语句的执行过程，我们直接使用straight_join让MySQL使用固定的连接表顺序进行查询。在下面的语句中，t1是驱动台面，t2是从动台面。选择*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的结果中得到，根据不同的case场景有所不同）。假设驱动表的行数为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条件，放入结果集中。例如下面的SQLselect*fromt2straight_joint1on(t2.b=t1.b);该语句的解释结果如下。可以看出join过程对t1和t2都进行了全表扫描，将t2表中的500条数据全部放入内存join_buffer中，而对于t1表中的每一行数据，都对遍历一次join_buffer，需要进行500次比较，所以总共需要500*10000次内存比较操作。具体过程如下图所示。主要需要注意的是，在第一步中并不是将表t2中的所有数据都放入join_buffer中，而是根据具体的SQL语句放入不同行、不同字段的数据。比如下面的join语句，只会将t2表中匹配b>=100的数据的b字段存储到join_buffer中。select2.b,t1.bfromt2straight_joint1on(t2.b=t1.b)wheret2.b>=100;join_buffer不是无限的，由join_buffer_size控制，默认值为256K。当存储的数据太大时，只有分段存储，整个执行过程变成：扫描表t2，将符合条件的数据行存储到join_buffer中，因为它的大小是有限的，100行就满了stored如果是，则执行第二步；扫描表t1，将每一行数据与join_buffer中的数据进行比较，如果满足join条件，则放入结果集中；清除join_buffer；再次执行第一步，直到所有数据都被扫描完，由于t2表中有500行数据，所以这个过程一共重复5次。这个过程体现了算法名称中Block的由来，join操作是以block为单位进行的。因为表t2的数据被分成5次存放在join_buffer中，所以表t1需要全表扫描5次。全部存储5次，存入内存操作10000*50010000*(100*5)扫描行数10000+50010000*5+500如上图，对比join_buffer中可以存入的表数据，数量ofmemory判断没有变化，是两个表行数的乘积，为10000*500，但是会多次扫描从动表，每次追加存入，从动表会再次扫描，影响最终的执行效率。基于以上两种算法，我们可以得出以下结论，这也是网上大多数MySQLjoin语句的规范。被驱动表上有索引，即可以使用IndexNested-LoopJoin算法时，可以使用join操作。IndexNested-LoopJoin算法和BlockNested-LoopJoin算法都必须使用小表作为驱动表。由于以上两种join算法的时间复杂度至少与涉及表的行数有一阶关系，且占用内存空间大，阿里巴巴开发者规范严禁join操作也是可以理解的超过三个表就是这样。但以上两种算法只是join算法中的一种，还有更高效的join算法，如HashJoin和SortedMergedjoin。遗憾的是，这两种算法目前在MySQL的主流版本中是没有的，但是Oracle、PostgreSQL和Spark都支持。这也是MySQL在网上弱的原因（MySQL8.0版本支持Hashjoin，但8.0还不是主流版本）。事实上，由于MySQL的join操作性能较差，阿里巴巴开发者规范也禁止在从Oracle迁移到MySQL时进行超过三张表的join操作。HashJoin算法HashJoin扫描驱动表，利用join的关联字段在内存中构建哈希表，然后扫描驱动表，每次读出一行数据，从哈希表中找到对应的数据。是大数据集连接操作的常用方法。适用于表驱动数据量较小，可以存入内存的场景。它可以为没有索引的大表和并行查询场景提供最佳性能。可惜只适用于等价连接场景，比如ona.id=whereb.a_id。依旧是上面两张表的join语句，其执行过程如下：取出驱动表t2中符合条件的数据，对每一行的join字段值进行hash运算，然后存入hash中内存中的表；遍历驱动表t1，每取出一行符合条件的数据，对其join字段值也进行哈希运算，在内存哈希表中查找匹配结果。如果找到，它将成为结果集的一部分。可以看出该算法与BlockNested-LoopJoin类似，只是将无序的JoinBuffer改为哈希表，这样数据匹配就不需要遍历joinbuffer中的所有数据。而是直接通过hash，以接近O(1)的时间复杂度得到匹配行，大大提高了两表的join速度。但是由于hash的特性，该算法只能应用于等价连接的场景，其他连接场景不能使用该算法。SortedMergeJoin算法SortMergeJoin首先根据join关联的字段对两个表进行排序（如果已经排序，比如字段上有索引，就不需要再排序），然后对两个表执行合并操作。如果两张表已经排好序，那么在进行排序归并连接时就不需要再重新排好序了。这时候MergeJoin的性能会比HashJoin好。MergeJoin适用于非等价Join（>、<、>=、<=，但不包含!=，即<>）。需要注意的是，如果连接的字段已经有索引，也就是说已经排序，则可以直接进行合并操作，但是如果连接的字段没有索引，其执行过程如下图所示.遍历表t2，读取符合条件的数据，根据连接字段a的值排序；遍历表t1，读取符合条件的数据，同样按照连接字段a的值排序；对两个数据进行排序合并得到结果集。SortedMergeJoin算法的主要耗时是对两张表的排序操作，所以如果两张表已经按照join字段排序，该算法甚至比HashJoin算法还要快。在一种情况下，该算法比NestedLoopJoin算法更快。接下来我们总结一下以上三种算法的区别和优缺点。NestedLoopJoinHashJoinSortedMergeJoinjoin条件适用于任何条件只适用于equivalencejoin(=)equivalenceornon-equivalencejoin(>,<,=,>=,<=),except'<>'primaryConsumeresourcesCPU、磁盘I/O内存、临时空间内存、临时空间特性当有高选择性索引或限制性搜索时，效率比较高，可以快速返回第一个搜索结果当没有索引或索引条件比较模糊，HashJoin比NestedLoop更有效。通常比MergeJoin快。在数据仓库环境中，如果表中记录数多，效率就高。当没有索引或者索引条件不明确时，SortMergeJoin比NestedLoop更有效。当预先对连接字段进行索引或排序时，比hashjoin速度更快，支持更多的连接条件。缺点：没有索引或者表记录多效率低。构建哈希表需要大量内存，第一个结果返回缓慢。所有的表都需要排序。它是为最佳吞吐量而设计的，在没有找到所有结果之前不返回数据需要索引是（没有索引效率太低）否连接条件适用于任何条件仅适用于等价连接（=）或非等价连接（>,<,=,>=,<=),除了'<>'主要消耗资源CPU,磁盘I/O内存,临时空间内存,临时空间特性当有高选择性的索引或限制时效率比较高在搜索中，可以快速返回第一个搜索结果。当没有索引或者索引条件模糊时，HashJoin比NestedLoop更有效。通常比MergeJoin快。在数据仓库环境中，如果表中记录数多，效率就高。当没有索引或者索引条件不明确时，SortMergeJoin比NestedLoop更有效。当预先对连接字段进行索引或排序时，比hashjoin速度更快，支持更多的连接条件。缺点：没有索引或者表记录多效率低。构建哈希表需要大量内存，第一个结果返回缓慢。所有的表都需要排序。它旨在实现最佳吞吐量，并且在找到所有结果之前不会返回数据。需要建立索引（没有索引效率太差）NoNo对于Join操作的理解，Join相关的算法我们已经讲完了。这里先谈谈业务对join操作的理解。在业务不复杂的情况下，大多数join都不是不可替代的。比如订单记录中一般只有订单用户的user_id，返回信息时需要获取用户名。可能的实现方案如下：数据库操作，使用join操作，join订单表和用户表，并返回用户名；两次数据库操作，分为两次查询，第一次获取订单信息和user_id，第二次根据user_id获取姓名，使用代码程序合并信息；使用冗余用户名或从非关系数据库（如ES）读取。以上方案都可以解决数据聚合的问题，而且基于程序代码，比数据库join更容易调试和优化。例如，用户名不是从数据库中获取的，而是先从缓存中查找。当然join操作也不是没用，所以该技术有它的使用场景。以上解决方案或规则是互联网开发团队总结出来的。它们适用于高并发、轻写重读、分布式、简单的业务逻辑。这些场景一般对数据一致性要求不高，甚至允许脏读。但是在金融银行或者金融等企业应用场景中，join操作是必不可少的。这些应用一般是低并发、频繁且复杂的数据写入，CPU密集型而非IO密集型，主要业务逻辑通过数据库处理，甚至包括存储过程数量多、一致性要求高的系统和诚信。
