• 在 MySQL 中，只有一种 Join 算法，也就是 Nested Loop Join，没有其他很多数据库所提供的Hash Join，也没有Sort Merge Join

  Nested Loop Join 实际上就是通过驱动表的结果集作为循环基础数据，然后一条一条的通过该结果集中的数据作为过滤条件到下一个表中查询数据，然后合并结果。如果还有第三个参与Join，则再通过前两个表的Join 结果集作为循环基础数据，再一次通过循环查询条件到第三个表中查询数据，如此往复。

• Nested Loop Join 就是多个表的for循环,以幂次增长

  例如

  select * from t1 inner join t2 on t1.a = t2.a;
  # 等价的是:
  select * from t1,t2 where t1.a = t2.a;

  这时会以一个表作为驱动表,然后拿到一行记录就做为新的条件去另一个表过滤数据

  类似

  for(tt1 in t1){
      if(tt1 is true){
          for(tt2 in t2){
              if(tt2 is true for condition){
                  return
              }
          }
      }
  }

• MySQL 就使用 BNL 算法以及 join buffer 优化:

  BNL (Block Nested Loop Join)算法原理：将外层循环的行/结果集存入 join buffer,内存循环的每一行数据与整个 buffer 中的记录做比较,可以减少内层循环的扫描次数

  • 适用条件

    join buffer 只有当我们的 join 类型为 ALL,index,rang 或者是index_merge 的时候才能够使用

  直接嵌套查询效率肯定很低,因为当驱动表得到一条数据之后,就会在被驱动表里面找符合条件的数据,而被驱动表需要从磁盘加载到内存才能进行条件匹配

  而每次访问被驱动表,都要进行一次IO,并且在内存中的每一条记录只会和驱动表结果集的一条记录做匹配,之后就会被从内存中清除掉,然后再从驱动表结果集中拿出另一条记录,再一次把被驱动表的记录加载到内存中一遍

  周而复始，驱动表结果集中有多少条记录，就得把被驱动表从磁盘上加载到内存中多少次。所以我们可以在把被驱动表的记录加载到内存的时候，一次性和多条驱动表中的记录做匹配，这样就可以大大减少重复从磁盘上加载被驱动表的代价了

  MySQL 使用 join buffer 就是这么做的

  它不再是每次从驱动表取出一条数据就在另一个表里面找,而是取出一定大小之后,再一起在另一张表里找,批量查找比单次查找效率高一些

  join buffer 就是执行连接查询前申请的一块固定大小的内存，先把若干条驱动表结果集中的记录装在这个 join buffer 中，然后开始扫描被驱动表，每一条被驱动表的记录一次性和 join buffer 中的多条驱动表记录做匹配，，所以这样可以显著减少被驱动表的 I/O 代价

  最好的情况是 join buffer 足够大，能容纳驱动表结果集中的所有记录，这样只需要访问一次被驱动表就可以完成连接操作了。这种加入了 join buffer 的嵌套循环连接算法称之为基于块的嵌套连接(Block Nested-Loop Join)算法

  另外需要注意的是，驱动表的记录并不是所有列都会被放到join buffer中，只有查询列表中的列和过滤条件中的列才会被放到join buffer中，所以再次提醒我们，最好不要把*作为查询列表，只需要把我们关心的列放到查询列表就好了，这样可以在join buffer中放置更多的记录

  注意: join buffer 只是通过先查驱动表,在一起放到另一个表的条件里面,如果驱动表还是很多,应该还是会有多次读取驱动表的情况

  • join 优化总结:

    1. 让驱动表得到的数据尽可能的少,减少内层循环次数

    2. 优化内层循环次数,

    3. 被驱动表 join 字段加索引(使用 index nested loop join 优化)

    4. join buffer,并增大 buffer size

• 消除外联接

  内连接的驱动表和被驱动表的位置可以相互转换，而左连接和右连接的驱动表和被驱动表是固定的。这就导致内连接可能通过优化表的连接顺序来降低整体的查询成本，而外连接却无法优化表的连接顺序

  外连接和内连接的本质区别就是：对于外连接的驱动表的记录来说，如果无法在被驱动表中找到匹配 对于外连接的驱动表的记录来说，如果无法在被驱动表中找到匹配ON子句中的过滤条件的记录，那么该记录仍然会被加入到结果集中，对应的被驱动表记录的各个字段使用子句中的过滤条件的记录，NULL值填充；而内连接的驱动表的记录如果无法在被驱动表中找到匹配ON子句中的过滤条件的记录，那么该记录会被舍弃