MySQL的join的实现是怎么样的？

1.什么是Nested-Loop Join？ 2.Index Nested-Loop Join怎么优化连接？ 3.Block Nested-Loop Join怎么优化连接？ Nested-Loop Join 在Mysql中，使用Nested-Loop Join的算法思想去优化join，Nested-Loop Join翻译成中文则是“嵌套循环连接”。 举个例子： ```java select * from t1 inner join t2 on t1.id=t2.tid ``` （1）t1称为外层表，也可称为驱动表。 （2）t2称为内层表，也可称为被驱动表。 //伪代码表示： ```java List<Row> result = new ArrayList<>(); for(Row r1 in List<Row> t1){ for(Row r2 in List<Row> t2){ if(r1.id = r2.tid){ result.add(r1.join(r2)); } } } ``` 在Mysql的实现中，Nested-Loop Join具体有3种实现的算法： Simple Nested-Loop Join：SNLJ，简单嵌套循环连接 Index Nested-Loop Join：INLJ，索引嵌套循环连接 Block Nested-Loop Join：BNLJ，缓存块嵌套循环连接 在选择Join算法时，会有优先级，理论上会优先判断能否使用INLJ、BNLJ： Index Nested-LoopJoin > Block Nested-Loop Join > Simple Nested-Loop Join ### 一.Simple Nested-Loop 简单嵌套循环连接实际上就是简单粗暴的嵌套循环，如果table1有1万条数据，table2有1万条数据，那么数据比较的次数=1万 * 1万 =1亿次，这种查询效率会非常慢。实现伪代码就跟上面的一样。 所以Mysql继续优化，然后衍生出Index Nested-LoopJoin、Block Nested-Loop Join两种NLJ算法。在执行join查询时mysql会根据情况选择两种之一进行join查询。 ### 二.Index Nested-LoopJoin（减少内层表数据的匹配次数） 索引嵌套循环连接是基于索引进行连接的算法，索引是基于内层表的，通过外层表匹配条件直接与内层表索引进行匹配，避免和内层表的每条记录进行比较， 从而利用索引的查询减少了对内层表的匹配次数，优势极大的提升了 join的性能： 原来的匹配次数 = 外层表行数 * 内层表行数 优化后的匹配次数= 外层表的行数 * 内层表索引的高度 伪代码实现： ```java select * from t1 inner join t2 on t1.id=t2.tid /* 假设要执行上面的这个查询，然后t1作为外层表(也就是驱动表)，每次从t1表中取一行数据出来，然后根据t1.id去t2表的聚集索引下查询主键id等于t1.id的数据行，如果存在，就添加到结果集中，所以 每次查询的匹配次数=t2表的聚集索引的层数 总的查询匹配次数=外层表t1的行数 * t2表的聚集索引的层数 */ List<Row> result = new ArrayList<>(); for(Row r1 in List<Row> t1){ Row> r2 = searchBTree(t1.id); result.add(r1.join(r2)); } ``` 使用场景：只有内层表join的列有索引时，才能用到Index Nested-Loop Join进行连接。 使用Index Nested-Loop Join算法时SQL的EXPLAIN结果extral列是Using index。 由于用到索引，如果索引是辅助索引而且返回的数据还包括内层表的其他数据，则会回内层表查询数据，多了一些IO操作。 ### 三.Block Nested-Loop Join（减少内层表数据的循环次数） 当有时候Join字段没法使用索引的时候，那样就不能用Index Nested-Loop Join的时候，次数默认就会使用Block Nested-Loop Join。 大体的原理 Block Nested-Loop Join通过一次性缓存多条数据，把参与查询的列缓存到Join Buffer 里，然后拿join buffer里的数据批量与内层表的数据进行匹配，从而减少了内层循环的次数（遍历一次内层表就可以批量匹配一次Join Buffer里面的外层表数据）。 伪代码表示 ```java select * from t1 inner join t2 on t1.tid=t2.tid 假设字段tid在t1表，t2表中都没有建立索引，那么查找时就不能使用索引了，采用Block Nested-Loop Join算法就是每次从驱动表t1中加载一部分数据行到内存缓冲区Join Buffer 中来，然后对t2表进行全表扫描，扫描时每次拿t2表中的数据行与Join Buffer中的数据进行匹配，匹配完成就添加到结果集。 所以全表扫描的次数=驱动表t1的行数/Join Buffer的大小。 因为Join Buffer是内存缓冲区，在内存中进行元素比较是比较快的，而对t2表进行全表扫描是磁盘Io，是比较慢的，所以应该是尽可能减少全表扫描的次数。所以优化的方式一般是增大Join Buffer的大小，或者是选取数据量小的表作为驱动表，这样可以减少全表扫描的次数，减少磁盘IO。 List<Row> result = new ArrayList<>(); //可以把subList理解为每次从t1表中取出，加载到join buufer的那一部分数据 for( List<Row> subList in List<Row> t1){ for(Row r2 in List<Row> t2){ if(subList.contains(r2.tid){ result.add(r1.join(r2)); } } } ``` 使用Block Nested-Loop Join算法时SQL的EXPLAIN结果extral列是Using join buffer 什么是Join Buffer？ （1）Join Buffer会缓存所有参与查询的列而不是只有Join的列。 （2）可以通过调整join_buffer_size缓存大小 （3）join_buffer_size的默认值是256K，join_buffer_size的最大值在MySQL 5.1.22版本前是4G，而之后的版本才能在64位操作系统下申请大于4G的Join Buffer空间。 （4）使用Block Nested-Loop Join算法需要开启优化器管理配置的optimizer_switch的设置block_nested_loop为on，默认为开启。 [https://blog.csdn.net/u010841296/article/details/89790399](https://blog.csdn.net/u010841296/article/details/89790399) [https://mp.weixin.qq.com/s/8W3RzKE1HjKifGzJvzBYzA](https://mp.weixin.qq.com/s/8W3RzKE1HjKifGzJvzBYzA)