专栏首页java相关资料Mysql几种join连接算法

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时,如果可以不回表查询,即利用到覆盖索引,则可能可以提示速度。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 看完这篇文章,99%的人都会使用Mysql Explain工具

    注意:本文基于mysql5.7进行操作,各个版本的mysql使用Explan会有微小的差异

    黎明大大
  • elasticsearch-DSL高级查询语法

    》比如,query的时候,会先比较查询条件,然后计算分值,最后返回文档结果; 而filter则是先判断是否满足查询条件,如果不满足,会缓存查询过程(记录该文档...

    黎明大大
  • 利用logstash将mysql多表数据增量同步到es

    我的数据库是5.7版本,我这里下载5.1.47的驱动了,当然如果你们的数据库是8.0以上的版本,那么就下相应的版本就行

    黎明大大
  • 一文搞懂MySQL的Join,聊一聊秒杀架构设计

    其实对于上面的观点一定程度上是正确的,但不是完全正确。但之所以流传这么广,主要还是没有搞清楚实际状态,而根据实际使用中总结出来的一些模糊规律。只有了解的MySQ...

    Java_老男孩
  • Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) A. Be Positive(水题)

    题目链接:http://codeforces.com/contest/1130/problem/A

    Ch_Zaqdt
  • 如何评测语音技能的智能程度(4)——人格特质

    “若产品能够在人格层面与用户建立关联,则能够更好地促进使用过程中产生积极正面的情绪,形成愉悦的记忆,继而促进用户的使用意愿、包容度和信任。”

    半吊子全栈工匠
  • 怎么用photoshop改变图片背景天空

    有时候我们需要处理图片或者需要制作漂亮的视频封面,这里介绍一种使用photoshop来处理背景天空的技巧。

    力力
  • 一文了解数据库和数据仓库

    互联网已经高速发展了很多年,各大企业都根据自己的业务搭建了自己的门户网站,拥有自己的服务器,以及自己的用户。用户在对企业的服务进行交互访问时,用户给企业反馈的信...

    王知无
  • ALHLS:Apple低延迟HLS技术

    https://mux.com/blog/the-community-gave-us-low-latency-live-streaming-then-apple...

    LiveVideoStack
  • ALHLS:Apple低延迟HLS技术

    在WWDC 2019上,Apple 依照惯例宣布了一系列的软件更新。并且像过去4年的传统一样,Roger Pantos上台宣布了HTTP直播视频流(HLS)规范...

    LiveVideoStack

扫码关注云+社区

领取腾讯云代金券