MySQL中Nest-Loop Join 与 Block Nes

一、原理

1.1 Nest-Loop Join

NLJ算法：将驱动表/外部表的结果集作为循环基础数据，然后循环从该结果集每次一条获取数据作为下一个表的过滤条件查询数据，然后合并结果。如果有多表join，则将前面的表的结果集作为循环数据，取到每行再到联接的下一个表中循环匹配，获取结果集返回给客户端。

NJL伪代码：

    for each row in t1 matching range {
      for each row in t2 matching reference key {
         for each row in t3 {
          if row satisfies join conditions,
          send to client
        }
      }
     }

可以看到，NLJ每次只会将一行传入内层循环，外层循环的结果集有多少行，内层循环就要执行多少次，如果内层表较大，或没关联字段没索引的情况下，执行效率就会很差

1.2 Block Nest-Loop Join

BNL算法：将外层循环的行/结果存入join buffer，内层循环的每一行与整个buffer中的记录做比较，从而减少循环的次数。

举例来说，外层循环的结果集是100行，使用NLJ 算法需要扫描内部表100次，如果使用BNL算法，先把对Outer Loop表(外部表)每次读取的10行记录放到join buffer,然后在InnerLoop表(内部表)中直接匹配这10行数据，内存循环就可以一次与这10行进行比较, 这样只需要比较10次，对内部表的扫描减少了9/10。所以BNL算法就能够显著减少内层循环表扫描的次数。

BNL伪代码：

    for each row in t1 matching range {
       for each row in t2 matching reference key {
        store used columns from t1, t2 in join buffer
        if buffer is full {
          for each row in t3 {
             for each t1, t2 combination in join buffer {
              if row satisfies join conditions,
              send to client
            }
           }
          empty buffer
        }
      }
    }


    if buffer is not empty {
       for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions,
          send to client
         }
      }
    }

二、JOIN BUFFER

2.1 mysql中join buffer的注意事项

1、join_buffer_size变量决定buffer大小。
2、只有在join类型为all、index、range的时候才可以使用join buffer
3、能够被buffer的每一个join都会分配一个buffer，一个quary最终可能会有多个buffer
4、第一个nonconst table不会分配join buffer，即使其扫描类型是all或者index
5、join buffer中只会保存参与join的列，并非整个数据行

三、如何使用BNL

5.6版本及以后，优化器管理参数optimizer_switch中中的block_nested_loop参数控制着BNL是否被用于优化器。默认条件下是开启，若果设置为off，优化器在选择 join方式的时候会选择NLJ算法。