MySQL连接的原理⭐️4种优化连接的手段性能提升240%🚀

前言

上两篇文章我们说到MySQL优化回表的三种方式：索引条件下推ICP、多范围读取MRR与覆盖索引

MySQL的优化利器⭐️索引条件下推，千万数据下性能提升273%🚀

MySQL的优化利器⭐️Multi Range Read与Covering Index是如何优化回表的？

这篇文章我们来聊聊MySQL中连接的原理以及连接的四种优化手段

为了更好的讲述文章内容，我们准备的两张表

一张是ICP文章中用到的学生表，学生表中有联合索引（age,studnet_name）

CREATE TABLE `student` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `student_name` varchar(20) DEFAULT NULL COMMENT '名称',
  `age` smallint(6) DEFAULT NULL COMMENT '年龄',
  `info` varchar(30) DEFAULT NULL COMMENT '信息',
  PRIMARY KEY (`id`),
  KEY `idx_age_name` (`age`,`student_name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

另一张座位表用于关联学生表，标识某个座位是某个学生的，座位与学生的关系是多对一（比如学生菜菜有多个座位）

CREATE TABLE `seat` (
  `seat_id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT '座位ID',
  `seat_code` char(10) DEFAULT NULL COMMENT '座位码',
  `student_id` bigint(20) DEFAULT NULL COMMENT '座位关联的学生ID',
  PRIMARY KEY (`seat_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

连接原理

关联多张表的查询叫做联表查询（联表又叫连接），常见的连接有：左连接、右连接、内连接

在左连接中，left join左边的表为驱动表，右边的表为被驱动表

当发生连接查询时，先在驱动表中开始寻找记录，当找到满足条件的记录，再去被驱动表中寻找满足关联条件on的记录

SELECT
  s1.*,
  s2.seat_code 
FROM
  student s1
  LEFT JOIN seat s2 ON s1.id = s2.student_id 
WHERE
  s1.age = 18 
  AND s1.student_name LIKE 'c%' 
;

比如这个例子中执行流程（1-3是循环的步骤，直到不满足条件）：

1. 先去学生表student的（age,studnet_name）联合索引中寻找满足条件的记录
2. 拿到这条记录的id去被驱动表seat中找到满足关联条件的记录（ON s1.id = s2.student_id ）
3. 将找到的记录放入结果集中，再去循环步骤1

直到图中第四条记录（18，ddseat，25）不满足查询条件s1.age = 18 AND s1.student_name LIKE 'c%'时则退出循环

连接寻找的过程是不是就像双层for循环一样？驱动表为外层循环，被驱动表为内存循环，伪代码如下：

//驱动表student
for(long studentIndex = initStudentIndex; studentIndex < student.size(); studentIndex++){
    //如果不满足条件就退出 
    if(){
       break;   
    }    
    
    //满足条件就去访问被驱动表seat
    for(long seatIndex = initSeatIndex; seatIndex < seat.size(); seatIndex++){
        //如果不满足条件就退出（继续循环驱动表）
        if(){
            break;
        }
        
        //在被驱动表中找到满足关联的条件就加入结果集
        result.add(XX);
    }

}

通过流程与代码我们可以分析：访问驱动表时，会访问多次被驱动表（驱动表每有一条满足条件的记录就要去访问被驱动表）

因此在设计上应该尽量选择驱动表为小表，用小表驱动大表

当使用内连接时，由优化器决定哪个表是驱动表，哪个表是被驱动表

当两个表时相当于双层循环，三个表时相当于三层循环，联表越多时间复杂度呈指数级别增长，联表的性能开销会非常大

优化连接

如果想要优化联表的开销有什么手段呢？

通过刚刚的分析，我们可以通过减少访问被驱动表的次数、加快查询被驱动表等方面来进行优化连接

索引

说到加快查询速度， 第一个想到的就是建立索引

为被驱动表关联字段加上索引，优化查询被驱动表的速度

以这条SQL为例，就是在seat表中加上（student_id）索引

SELECT
  s1.*,
  s2.seat_code 
FROM
  student s1
  LEFT JOIN seat s2 ON s1.id = s2.student_id 
WHERE
  s1.age = 18 
  AND s1.student_name LIKE 'c%' 
;

当在驱动表中找到记录后，去被驱动表的（student_id）索引寻找满足条件的记录

被驱动表（student_id）索引会对student_id排序，当student_id相同时对主键seat_id排序

索引student_id有序，等值比较查找会很快，从而优化查询被驱动表的速度

SELECT
  s1.*,
  s2.seat_code 
FROM
  student s1
  left JOIN seat s2 ON s1.id = s2.student_id 
WHERE
  s1.age = 18 
  AND s1.student_name LIKE 'c%'
> OK
> 时间: 2.063s

执行计划中显示，被驱动表用到student_id索引

但是还会出现回表的问题，由于（student_id）索引中不存在要查询的seat_code字段，还要回表查询聚簇索引

也可以通过在索引中增加seat_code列使用覆盖索引解决，回表相关知识前两篇文章说过，这里就不过多叙述

Block Nested Loop （BNL）

创建索引是有代价的，不仅查询时需要分析使用哪个索引的成本低，在进行写操作时还要去维护索引

因此并不是每连接一张表就要为被驱动表建立索引，在用不上索引的情况下，该如何优化连接的开销呢？

MySQL提供Block Nested Loop算法对被驱动表无法使用索引的场景，减少访问被驱动表的次数来进行优化

Block Nested Loop 算法是使用一块缓冲池（join buffer）记录满足驱动表的记录，将缓冲池装满后再去被驱动表中寻找

在被驱动表中寻找时，每遍历一条记录就用join buffer中存储的驱动表记录来进行匹配，满足关联条件就放入结果集中

SET optimizer_switch='block_nested_loop=on'用于开启BNL算法（默认开启）

开启BNL算法耗时5.215s （测试前记得把被驱动表的student_id索引删除）

SET optimizer_switch='block_nested_loop=on'
> OK
> 时间: 0.053s


SELECT
  s1.*,
  s2.seat_code 
FROM
  student s1
  left JOIN seat s2 ON s1.id = s2.student_id 
WHERE
  s1.age = 18 
  AND s1.student_name LIKE 'c%'
> OK
> 时间: 5.215s

执行计划的附加信息说明使用join buffer，算法为BNL

将BNL算法关闭测试原理中描述的双层循环，耗时12.804s

SET optimizer_switch='block_nested_loop=off'
> OK
> 时间: 0.048s


SELECT
  s1.*,
  s2.seat_code 
FROM
  student s1
  left JOIN seat s2 ON s1.id = s2.student_id 
WHERE
  s1.age = 18 
  AND s1.student_name LIKE 'c%'
> OK
> 时间: 12.804s

执行计划的附加信息中说明没用join buffer

从原来的满足一条记录就去寻找一遍被驱动表变成收集多条记录后再去访问被驱动表

如果使用的缓存池够大，还可以将驱动表中满足条件的记录装完再去访问被驱动表，相当于只访问一次

join buffer存储需要查询的列和查询条件的列，因此不要使用select *避免浪费join buffer的空间

默认情况下join buffer 占用262144 B（256KB），如果不能使用索引优化连接的情况下，可以把join buffer 设置大一些  set global join_buffer_size = 262144

Batched Key Access (BKA)

在Block Nested Loop 算法是用于优化被驱动表中不能使用索引的场景

而Batched Key Access BKA算法用于优化被驱动表上能使用索引的场景

在驱动表（age，student_name）索引中满足条件的记录，id不一定是有序的，使用乱序的id去被驱动表中查找就可能发生随机IO

BKA算法是基于MRR的，对驱动表结果的id进行排序后，再去被驱动表中查找

不懂MRR的同学可以查看上篇文章（在文章前言有链接）

由于MySQL对使用MRR的成本太高，如果想使用BKA算法，还需要关闭基于成本判断是否使用MRR

SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

mrr=on 开启mrr （默认开启）

mrr_cost_based=off 关闭基于成本判断是否使用MRR （默认开启）

batched_key_access 开启BKA  （默认关闭）

测试使用BKA算法耗时1.533s

SET optimizer_switch = 'mrr=on,mrr_cost_based=off,batched_key_access=on'
> OK
> 时间: 0.049s


SELECT
  s1.*,
  s2.seat_code 
FROM
  student s1
  LEFT JOIN seat s2 ON s1.id = s2.student_id 
WHERE
  s1.age = 18 
  AND s1.student_name LIKE 'c%'
> OK
> 时间: 1.533s

执行计划中显示，驱动表使用MRR，被驱动表使用student_id索引和BKA算法

hash join

关联条件往往是等值比较的

散列表（哈希表）是一种非常适合寻找等值比较的数据结构

在MySQL高版本中8.0默认使用 hash 的 join buffer，通过空间换时间的方式来加速查找被驱动表

测试总结

本篇文章使用该SQL对多种优化连接的方式进行测试并将结果进行汇总分析其特点（暂时还没测试hash join）

SELECT
  s1.*,
  s2.seat_code 
FROM
  student s1
  LEFT JOIN seat s2 ON s1.id = s2.student_id 
WHERE
  s1.age = 18 
  AND s1.student_name LIKE 'c%' 
;

默认情况下就算不用索引也不会使用无优化的嵌套查询，最少也是使用Join Buffer 5.215s

为被驱动表关联列增加索引后，相比于Join Buffer查询性能提升近150%

使用BKA算法优化后查询速度达到1.533s，相比于Join Buffer查询性能提升近240%

总结

连接的原理就是循环嵌套查询，根据驱动表满足查询条件的记录数量去多次访问被驱动表，因此连接时需要小表驱动大表；内连接Inner Join由优化器来选择驱动表

多表连接的时间复杂度呈指数级别，开销非常大，通过减少访问被驱动表数量、加速访问被驱动表等方面进行优化

在被驱动表使用不到索引的场景下，会使用缓冲池Join Buffer的BNL算法来存储驱动表满足条件记录，相当于多条记录一起访问被驱动表，以此来减少访问被驱动表次数

Join Buffer中存储查询需要的列和查询条件的列，因此不要使用select * 避免浪费Join Buffer，在不能使用索引的场景下可以增大Join Buffer的空间

为被驱动表关联条件的列建立索引可以加快访问被驱动表，将访问被驱动表聚簇索引的无序查询优化为二级索引的有序查询，但满足条件的驱动表记录中关联条件的列并不一定有序，来查被驱动表时可能是随机IO

BKA算法基于被驱动表的关联条件列建立索引和使用MRR，以此对驱动表中满足条件的列排序，将访问被驱动表时的随机IO优化为顺序IO

默认下BKA算法不开启并且MRR预估成本较大，如果确认访问被驱动表时的随机IO开销太大，可以关闭基于成本使用MRR和开启BKA算法

在MySQL 8.0高版本中Join Buffer默认使用hash join，由于关联条件常是等值比较，数据结构哈希表非常适合这种场景下的查询

最后（不要白嫖，一键三连求求拉~）

本篇文章被收入专栏 由点到线，由线到面，构建MySQL知识体系，感兴趣的同学可以持续关注喔

本篇文章笔记以及案例被收入 gitee-StudyJava、 github-StudyJava 感兴趣的同学可以stat下持续关注喔~

有什么问题可以在评论区交流，如果觉得菜菜写的不错，可以点赞、关注、收藏支持一下~

关注菜菜，分享更多干货，公众号：菜菜的后端私房菜