大家好，我是李杜。上一期我们讲了Mysql的索引。本期我们就来说说Mysql中join的原理。join的用法基本都会用，不管是leftjoin，rightjoin，innerjoin语法都比较简单。不过join的原理确实博大精深。对于一些传统的IT公司来说，几乎就是一句sql走遍天下。连接了五六个表。当数据量上来的时候，就会变得很慢。必要的。阿里的开发手册规定join不能三查。有的网上明明规定不能用join。那么在实际场景中，我们真的可以不用join吗？让我们详细谈谈。Mysql的join主要涉及三种算法，分别是SimpleNested-LoopJoin、BlockNested-LoopJoin和IndexNested-LoopJoin。下面我们来详细了解一下这三种算法的原理、区别和效率。首先准备两张表作为测试表进行测试，使用存储过程初始化一些测试数据。初始化表结构sql如下：col1`int(20)NOTNULLDEFAULT'0'COMMENT'testfield1',`col2`int(20)NOTNULLDEFAULT'0'COMMENT'testfield2',PRIMARYKEY(`id`),KEY`col1`(`idx_col1`))ENGINE=InnoDBAUTO_INCREMENT=782DEFAULTCHARSET=utf8mb4COMMENT='测试表1';CREATETABLE`testb`(`id`int(20)NOTNULLAUTO_INCREMENTCOMMENT'活动主键',`col1`int(20)NOTNULLDEFAULT'0'COMMENT'测试字段1',`col2`int(20)NOTNULLDEFAULT'0'COMMENT'testfield2',PRIMARYKEY(`id`),KEY`col1`(`idx_col1`))ENGINE=InnoDBAUTO_INCREMENT=782DEFAULTCHARSET=utf8mb4COMMENT='testtable2';初始化数据：CREATEDEFINER=`root`@`localhost`PROCEDURE`init_data`()BEGINDECLAREiINT;SETi=1;WHILE(i<=100)DOINSERTIINTOtestaVALUES(i,i,i);SETi=i+1;ENDWHILE;SETi=1;WHILE(i<=2000)DOINSERTINTOtest2VALUES(i,i,i);SETi=i+1;ENDWHILE;END分别初始化testa表为100条数据，testb为2000条数据SimpleNested-LoopJoin首先，我们执行下面的sql：select*fromtestataleftjointestbtbon(ta.col1=tb.col2);SimpleNested-LoopJoin是最简单粗暴的join方式方法，上面的sql没有在testb的col2字段建立索引，所以当testa是驱动表，testb是从动表时，会hold住testa的每一行，然后扫描testb的全表。执行过程如下：从表testa中取出一行数据，记录为ta从ta中取出col1字段，扫描testb中的全表进行查询。在testb中找到满足条件的数据，与ta组成结果集返回。重复1-3步，直到testa表的数据全部取完。所以扫描的时间复杂度是100*2000=20W行，所以在被驱动表的关联字段没有加索引的情况下，效率很低。如果testb有百万以上的数据，扫描的时间复杂度会更加恐怖，但是Mysql中并没有使用这个算法，而是使用了另外一个算法BlockNested-LoopJoin，目的是优化驱动表而不用索引时间查询。BlockNested-LoopJoin还是上面的sql，不过可以通过加上explain关键字查看这条sql的执行计划：explainselect*fromtestataleftjointestbtbon(ta.col1=tb.col2);可以看到testb依然是全表扫描，在Extra字段中可以看到testb的Usingjoinbuffer(hashjoin)字样。在行中，可以看到扫描的总行数是驱动表的行数+从动表的行数。那么这个算法和SimpleNested-LoopJoin一样有什么区别呢？BlockNested-LoopJoin算法引入了join缓冲区，join缓冲区是一块内存区域，其大小由join_buffer_size参数控制。默认大小为256k：在执行上述sql时，会将testa表的所有数据加载到joinbuffer中，因为joinbuffer是内存操作，所以比上面的简单算法效率更高。具体执行过程如下：首先，将testa表的所有数据添加到joinbuffer中，这里所有的数据都是select之后的testa字段，因为这里是select*，所以是加载所有的testa字段。然后遍历并取出testb表中的每一行数据，与joinbuffer中的数据进行比较，如果满足条件，则作为结果集返回。具体流程图如下：因此，由以上执行步骤（假设驱动表行数为N，被驱动表行数据为M），BlockNested扫描的行数-LoopJoin依然是驱动表+被驱动表行数（N+M），内存中的总比较次数为驱动表*被驱动表行数（N*M）。上面我们提到joinbuffer是一个内存区域，有自己的size，如果joinbuffer的大小不足以容纳drivertable这个数量级怎么办？答案是细分。如果joinbuffer不能容纳drivertable中的所有数据，那么就不要将所有数据加载到joinbuffer中，先加载一部分，后面再加载另一部分，例如：先加载testa中的80条数据，与testb对比数据后，清空并载入testa中最后20条数据，再与testb对比。具体执行过程如下：首先将testa中的80条数据加载到joinbuffer中，然后一次性遍历testb中的所有数据，与joinbuffer中的数据进行比较，形成满足条件的结果集.清空joinbuffer，然后加载testa后的20条数据。然后一次性遍历testb中的所有数据，与joinbuffer中的数据进行比较，形成满足条件的结果集并返回。执行流程图如下：从上面的结果来看，分段的joinbuffer相比内存充足的joinbuffer，多了一次testb的full-table全表遍历，而且分的段越多，驱动越多表被更频繁地扫描，性能越差，所以在某些场景下，适当增大joinbuffer的值可以提高join的效率。若驱动表行数为N，切分参数为K，驱动表行数为M，则扫描总行数仍为N+K*M，内存数比较还是N*M，保持不变。K段的个数与N中的数据量有关，如果N中的数据量越大，则可能将K分成更多的段，这样重复扫描的驱动表的个数就更多。因此，当joinbuffer不够用时，驱动表越小越好，可以降低K值，减少被驱动表的重复扫描次数。这就是为什么提倡小桌子作为驱动桌子的原因。所以这里提到小表的概念。小桌子算小桌子吗？其实小表真正的是实际参与join的数据量，比如下面两条SQL：select*fromtestataleftjointestbtbon(ta.col1=tb.col2)wheretb.id<=20;select*fromtestbtbleftjointestataon(ta.col1=tb.col2)wheretb.id<=20;第二条sql中，虽然testb盘表的数据量比较大，但是在where条件下，实际参与join的行数是id小于等于20的数据，完全变小了比testa的数据量大，所以这里选择testb作为驱动表比较合适。在实际开发中，也严格禁止BlockNested-LoopJoin，严格要求根据关联条件建立索引，因此性能最好的索引Nested-LoopJoin算法是该算法。IndexNested-LoopJoin当我们执行下面的SQL时：select*fromtestataleftjointestbtbon(ta.col1=tb.col1);它的执行过程如下：首先从testa表中取出一行数据。使用上述行数据的col1字段查询testb表。在testb中找到符合条件的数据行，与testa中的数据行合并为结果集。重复步骤1-3，直到检索到testa表中的所有数据。因为testb的col1字段有索引，所以在使用testa表的字段col1查找testb时，testb使用的是col1索引的b+树查找，时间复杂度约为log2M，又因为是select*，所以也就是把testb的所有字段都找出来，所以这个也涉及到回表查询，所以就变成了2*log2M。不知道怎么回表的可以参考这篇文章：十万个为什么，精通Mysql索引在这过程中，testa表扫描的行数是all，所以需要扫描100行，而testa的每一行也和testb是一一对应的，所以col1索引查询扫描的行数也是100行，所以扫描的总行数就是200行。我们假设驱动表的数据行为N，驱动表的数据行为M，那么大概的复杂度为：N+N*2*logM，因为驱动表的扫描行数为N，和驱动表因为每次对应驱动表的一次，而一次的时间复杂度约为2*logM，所以驱动表为N*2*logM。显然，取值N对N+N*2*logM的结果影响比较大，所以N越小越好，所以选择小表作为驱动表是最好的选择。某些情况下的优化，如果joindriver表需要的字段很少（两个），可以构建联合索引来优化join查询，如果业务允许，可以使用冗余字段来减少join数量，提高查询效率.好了，本期将分享join的原理，以及join的一些优化方法和注意事项，下期见。本文转载自微信公众号“丽都编程”，可通过以下二维码关注。转载本文请联系李杜编程公众号。
