Mysql几种join连接算法

概述

相信有开发或DBA小伙伴,对于mysql处理多表关联方式或者说性能方面一直不太满意,对于开发提交的join查询,一般都是比较抗拒的,从而建议将join进行拆分,避免join带来的性能问题,同时也避免了程序与数据库带来网络开销的问题

5.5 版本之前，MySQL本身只支持一种表间关联方式，就是嵌套循环(Nested Loop Join)。如果关联表的数据量很大，则join关联的执行时间会非常长。在5.5以后的版本中，MySQL通过引入INLJ和BNL算法来优化嵌套执行, 今天主要介绍三种join算法 Nested-Loop Join (NLJ) 和 Index Nested-Loop Join (INLJ) 和Block Nested-Loop Join(BNL) .

Mysql常见的几种算法

1.嵌套循环连接算法（Nested-Loop Join(NLJ)）
2.基于索引的嵌套循环连接算法（Index Nested-Loop Join(INLJ)）
3.基于块的嵌套循环连接算法（Block Nested-Loop Join(BNL）

示例表

CREATE TABLE `t1` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_a` (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

create table t2 like t1;

-- 插入一些示例数据
-- 往t1表插入1万行记录
drop procedure if exists insert_t1; 
delimiter ;;
create procedure insert_t1()        
begin
  declare i int;                    
  set i=1;                          
  while(i<=10000)do                 
    insert into t1(a,b) values(i,i);  
    set i=i+1;                       
  end while;
end;;
delimiter ;
call insert_t1();

-- 往t2表插入100行记录
drop procedure if exists insert_t2; 
delimiter ;;
create procedure insert_t2()        
begin
  declare i int;                    
  set i=1;                          
  while(i<=100)do                 
    insert into t2(a,b) values(i,i);  
    set i=i+1;                       
  end while;
end;;
delimiter ;
call insert_t2();

嵌套循环连接算法（Simple Nested-Loop Join(NLJ)）

适用于关联的两个字段都是索引的情况下,首先会查询驱动表的全部数据,然后一次一行循环的去和被驱动表进行关联,直至全部关联完成

SQL案例:

EXPLAIN select * from t1 inner join t2 on t1.a= t2.a;

从执行计划中可以知道这些信息:

t2是为驱动表,t1是为被驱动表,先执行驱动表(执行计划结果id列值为一样的话,是从上往下进行执行的),mysql底层优化器会优先选择小表作为驱动表,用where条件过滤完驱动表,再和被驱动表进行关联查询。所以使用Inner join 时,排在前面的表并一定就是驱动表
当使用了left join,那么左表就是驱动表,右表作为被驱动表
当使用了right join,那么右表就是驱动表,左表为被驱动表
当使用了join,那么mysql优化器会以小表作为驱动表,大表为被驱动表
一般使用了join语句中,如果执行计划中的 Extra列中没有出现Using join buffer 则表示该join使用算法是NLJ

上面SQL大致执行流程如下

从t2表中读取一行记录(如果t2表有查询过滤条件,会先执行完过滤条件,再从过滤后结果中取一行记录)
从第1步记录中,取出关联字段 a 到 t1表查找
取出 t1表满足条件的记录与t2中获取到的结果进行合并,将结果放入结果集
循环上3个步骤,直到无法满足条件,将结果集返回给客户端

整个过程会读取t2表所有数据(100行数据),然后遍历每行数据字段a的值,根据t2表中a的值扫描t1表中对应行数据(扫描100次 t1 表的索引，1次扫描可以认为最终只扫描 t1 表一行完整数据，也就是总共 t1 表也扫描了100行)。因此整个过程扫描了 200 行。

代码案例理解

List<结果集> lists = new ArrayList<>();
for(t2 t2 : t2){  //外存循环
    for(t1 t1 : t1){  //内存循环
        if(t2.a().equals(t1.a())){  //条件匹配
            //存放结果到结果集
            结果集 = t1的结果 + t2的结果
            lists.add(结果集);
        }
    }
}

这里可以将外层循环看作为驱动表,内层循环看作为被驱动表,每次进行join时,会先从驱动表中拿取一条完整的数据和被驱动表进行条件匹配,如果匹配成功,则将数据连接后放入结果集中(就是外层循环的结果和内存结果组合成一条数据),然后,外层的驱动表扫描获取第二条数据,并和被驱动表进行条件匹配,将匹配成功数据连接后放入结果集中,剩余的数据以此类推,最后,将结果集返回给客户端

特点:NLJ该算法,比较容易理解,简单来说就是通过双层循环来进行比较值获取结果,这种算法太过于冗余粗鲁,如果驱动表和被驱动表的数据都是一万条数据,那么比较数据的次数就是 1万次 * 1万次 = 1亿次,那么这种比较效率会非常低

执行过程

基于索引的嵌套循环连接算法（Index Nested-Loop Join (INLJ）

索引嵌套循环连接算法是基于嵌套循环算法的改进版,其优化的思路,主要是为了减少了内层循环匹配次数,就是通过外层数据循环与内存索引数据进行匹配,这样就避免了内层循环数据逐个与外层循环的数据进行对比,从原来的匹配次数 = 外层所有行数据 * 内层所有行数据优化成外层所有行数据 * 索引树的高度,极大的提高的查询效率

SQL案例:

EXPLAIN select * from t1 inner join t2 on t1.a= t2.a;

上面SQL大致执行流程如下

从t2表中读取一行记录
从第1步记录中,取出关联字段 a 到 t1表的辅助索引树中进行查找
从t1表中取出辅助索引树中满足条件的记录拿出主键ID到主键索引中根据主键ID将剩下字段的数据取出与t2中获取到的结果进行合并,将结果放入结果集
循环上三个步骤,直到无法满足条件,将结果集返回给客户端

特点:基于嵌套循环连接算法进行优化,虽然还是双层循环进行匹配数据,但是内层循环（被驱动表）是使用索引树的高度决定循环次数的,这样的话,无论驱动表和被驱动表的数据多大,效率还是很高的

执行过程

基于块的嵌套循环连接算法（Block Nested-Loop Join(BNL）

如果关联字段不是索引或者有一个字段不是索引，MySQL则会采用此算法，和NLJ不同的是，BNL算法会多加一个join_buffer缓存块，关联时会把驱动表的数据读入到缓存块中，然后扫描被驱动表，把被驱动表每一行取出来跟 join_buffer 中的数据批量做对比。

案例:

EXPLAIN select * from t1 inner join t2 on t1.b= t2.b;

Extra列中的 Using join buffer (Block Nested Loop) 说明该关联查询使用了BNL算法

上面SQL大致执行流程如下

将t2（驱动表）的所有数据读入到join_buffer中（默认内存大小为256k,如果数据量多,会进行分段存放,然后进行比较）
把表t1的每一行数据,跟join_buffer中的数据批量进行对比
循环上两个步骤,直到无法满足条件,将结果集返回给客户端

这个例子里表 t2 才 100 行，要是表 t2 是一个大表，join_buffer 放不下怎么办呢？·
join_buffer 的大小是由参数 join_buffer_size 设定的，默认值是 256k。如果放不下表 t2 的所有数据话，策略很简单，就是分段放。
比如 t2 表有1000行记录， join_buffer 一次只能放800行数据，那么执行过程就是先往 join_buffer 里放800行记录，然后从 t1 表里取数据跟 join_buffer 中数据对比得到部分结果，然后清空 join_buffer ，再放入 t2 表剩余200行记录，再次从 t1 表里取数据跟 join_buffer 中数据对比。所以就多扫了一次 t1 表。

特点:优化思路是减少外层表的循环次数，Block Nested-Loop Join 通过一次性缓存多条数据（或者所有数据），把参与查询的列缓存到join buffer 里,然后拿join buffer里的数据批量与内层表的数据进行匹配，从而减少了外层循环的次数（循环遍历内层表每行数据就会匹配一次Join Buffer里面的外层表数据），当我们不使用Index Nested-Loop Join的时候，默认使用的是Block Nested-Loop Join。

结算结果为: 如果外层表需要存放两次数据放入Join Buffer中,Join Buffer最多能够存放10条数据那么就是 2 * 10 * 100= 2000次循环

什么是Join Buffer

Join Buffer会缓存所有参与查询的列而不是只有Join的列。
可以通过调整join_buffer_size缓存大小
join_buffer_size的默认值是256K，join_buffer_size的最大值在MySQL 5.1.22版本前是4G，而之后的版本才能在64位操作系统下申请大于4G的Join Buffer空间。
使用Block Nested-Loop Join算法需要开启优化器管理配置的optimizer_switch的设置block_nested_loop为on，默认为开启。

注意：
1、使用Block Nested-Loop Join 默认是开启状态的

通过指令：Show variables like 'optimizer_switc%'; 查看配置

2、设置join buffer 的大小
通过join_buffer_size参数可设置join buffer的大小

指令：Show variables like 'join_buffer_size%';

被驱动表的关联字段没索引为什么要选择使用 BNL 算法而不使用 Nested-Loop Join 呢？

如果上面第二条sql使用 Nested-Loop Join，那么扫描行数为 100 * 10000 = 100万次，这个是磁盘扫描。
很显然，用BNL磁盘扫描次数少很多，相比于磁盘扫描，BNL的内存计算会快得多。
因此MySQL对于被驱动表的关联字段没索引的关联查询，一般都会使用 BNL 算法。如果有索引一般选择 NLJ 算法，有索引的情况下 NLJ 算法比 BNL算法性能更高

Join 算法总结

不论是Index Nested-Loop Join 还是 Block Nested-Loop Join 都是在Simple Nested-Loop Join
的算法的基础上减少嵌套的循环次数，不同的是 Index Nested-Loop Join 是通过索引的机制减少内层表的循环次数，Block Nested-Loop Join 是通过一次缓存多条数据批量匹配的方式来减少外层表的循环次数，通过理解join 的算法原理我们可以得出以下表连接查询的优化思路。

1、永远用小结果集驱动大结果集(其本质就是减少外层循环的数据数量)
2、为匹配的条件增加索引(减少内层表的循环次数)
3、增大join buffer size的大小（一次缓存的数据越多，那么外层表循环的次数就越少）
4、减少不必要的字段查询（字段越少，join buffer 所缓存的数据就越多，外层表的循环次数就越少）

当用到BNLJ时，字段越少，join buffer 所缓存的数据就越多，外层表的循环次数就越少；
当用到INLJ时，如果可以不回表查询，即利用到覆盖索引，则可能可以提示速度。