MySQL调优篇 | 表连接方式及算法（3）

【前言】

经常有一些朋友向我咨询，如何写出高效的SQL，这不是三言两语能说得清的，索性认真来写一下，增删查改方面的知识我不再赘述，如果有基础薄弱的同学，可以好好的补一补再来看。

以MySQL为基础，MySQL调优篇内容主要包含MySQL逻辑架构、索引知识、表关联算法、explain执行计划解读及SQL调优实战等。

文章受众主要为两类人：

第一类人是工作中不可避免的会接触到MySQL的人，比如说一些项目人员、开发人员、测试人员等。

第二类人是专职DBA。

其实不管是专职的还是非专职的，就我接触到的情况而言，很多DBA平时维护MySQL看起来没什么问题，但其实没有很好的理论支撑，知其然而不知其所以然，解释一个简单的问题就能问倒一大部分的人。

比如说：MySQL的逻辑架构，分析当前业务架构优缺点？SQL工作原理是什么样的？

而且很多公司招聘面试的时候，考验的也是背后的原理居多，基本上没有机试。面试官问一个问题，即便你会解决但就是说不出原理，那么你肯定要不了高薪。

理论+实战=高薪

文章能够让大家有所收获、有所借鉴那是最好的。

【表连接方式】

常见的七种Join理论，如图所示：

image

1、左连接：A独有+在A中的B部分

image

语法：

select * from A left join B on A.key = B.key

没有满足A的B补Null。

2、内连接：A和B的交集

image

语法：

select * from A inner join B on A.key = B.key

3、右连接：B独有+在B中的A部分

image

语法：

select * from A right join B on A.key = B.key

没有满足B的A补Null。

上面三个是非常常见且常用的Join，那么还有四类Join：

4、A去掉B的部分，A的独有

image

对比左连接，其实是把中间属于A的B部分给干掉了。
语法：

select * from A LEFT JOIN B on A.aid = B.bid    左连接
where B.bid is null   B不在A的部分

因为本身左连接已经把所有A的值都包含出来了，同时多了的部分，就是B在A的部分，只要拿到为空的部分，其实就是B不在A的部分。

5、B去掉A的部分，B的独有

image

对比右连接，其实是把中间属于B的A部分给干掉了
语法：

select * from A RIGHT JOIN B on A.aid = B.bid    右连接
where A.aid is null   A不在B的部分

6、A和B去掉交集部分

image

语法：

select * from A LEFT JOIN B on A.aid = B.bid    左连接
where B.bid is null   B不在A的部分
union
select * from A RIGHT JOIN B on A.aid = B.bid    右连接
where A.aid is null   A不在B的部分

实际上是不是上面两个的合体？

7、外连接：A和B的并集
语法：

select * from A LEFT JOIN B on A.aid = B.bid  
union
select * from A RIGHT JOIN B on A.aid = B.bid

【表连接算法】 MySQL数据库根据不同的使用场合，支持两种Nested-Loops Join算法，一种是Simple Nested-Loops Join（NLJ）算法，另一种是Block Nested-Loops Join（BNL）算法。

image

1、简单嵌套循环连接（Simple Netsted-Loop Join） 对于两表连接，驱动表只会被访问一遍，被驱动表具体访问几遍取决于对驱动表执行单表查询后的结果集中的记录条数。

对于内连接，选取哪个表为驱动表都没关系，而外连接的驱动表是固定的，也就是说左外连接的驱动表就是左边的那个表，而右外连接的驱动表就是右边那个表。
两表连接的大致过程：

• 选取驱动表，使用与驱动表相关的过滤条件，选取代价最低的单表访问方法来执行对驱动表的单表查询。

• 对上一步中查询驱动得到的结果集中每一条记录都被分别到被驱动表中查找匹配的记录。

如图：

image

如果有3个表进行连接的话，那么步骤2中得到的结果集就像是新的驱动表，然后第三个表就成为了被驱动表，重复上边过程。

这种驱动表只访问一次，但被驱动表却可能被多次访问的连接执行方式称之为嵌套循环连接（Nested-Loop Join）。

2、索引嵌套循环连接（Index Nested Loops Join），
有一方在连接字段上有索引，这种场景在MySQL的使用中见的比较多。

优化器会考虑选择有索引的一方作为被驱动表，双方都有索引则选择索引高度低的，索引高度一样则选择记录数多的作为被驱动表，对于驱动表的每一条记录，在被驱动表中使用索引查询，大大减少了比较次数，提高了查询效率。
索引是主键时效率更高。

如图：

image

3、基于块的嵌套循环连接（Block Nested-Loop Join）
扫描一个表的过程其实就是把这个表的数据从磁盘上加载到内存中，然后在内存中比较匹配条件。

在实际环境中，面对百千万的数，内存放不下，所以在扫描表前边记录的时候后边的记录可能还在磁盘上，等扫描后面的记录的时候可能内存不足，需要把前面的数据在内存中释放掉。

而采用嵌套循环连接算法的两个表中，被驱动表要被访问好多次，如果被驱动表中的数据特别多而且不能使用索引访问的话，那就相当于从磁盘上读好多次这个表，这个IO代价就非常大，所以我们应该尽量减少访问被驱动表的次数。

在嵌套循环连接中，驱动表查询结果集中有多少条记录，就需要驱动表数据被加载多少次来进行匹配，那可不可以把被驱动表的记录加载到内存的时候，一次性和多条驱动表中的记录做匹配，这样就可以大大减少重复从磁盘上加载被驱动表的代价了。

所以提出可join buffer的概念，join buffer就是执行连接查询前申请的一块固定大小的内存，先把若干条驱动表结果集中的记录装在这个join buffer中，然后扫描被驱动表，每一条被驱动表的记录一次性和join buffer中的多条驱动表记录进行匹配，因为匹配的过程是在内存中完成的，所以这样可以减少被驱动表的IO代价。

image

这种只需要访问一次被驱动表就可以完成的连接操作称为基于块的嵌套连接算法；

4、批量键访问联接（Batched Key Access Join） 当被驱动表的链接字段有非主键索引时，而是通过范围扫描读取一部分记录放入内存中，然后按照主键排序，这样匹配到数据后需要按对应的主键索引去查询被驱动表的真实数据时，可以按照排好序的主键进行顺序访问，因为InnoDB叶子节点的数据也是按主键排序的，所以这种读取方式能提高查询效率。

MRR的使用流程中用到了排序，有一定的开销，有些sql中效率可能没有那么高。

image

5、Hash Join
MySQL8.0正式引入了Hash Join的连接方式，Hash Join可以在被驱动表没有索引的情况下进行快速的连接并查询。

• Hash Join首先使用了Join Buffer，把驱动表相关字段存入内存。这一步和块嵌套循环连接套路相同。

• 把Join Buffer中对应的字段值生成一个散列表，保存在内存中。这一步叫build。

• 扫描被驱动表，对被驱动表中的相关字段进行散列并比较。这一步叫probe。

可见，Hash Join也依赖Join Buffer，在最好的场景下，如果Join Buffer能覆盖驱动表所有相关字段，那么在查询的过程中驱动表和被驱动表都只需要扫描一次，如果散列算法够好，比较次数也只是被驱动表的记录数。

Hash Join只能用于等值连接，大表连接Hash Join的优化效果比较明显。

优化思路

• 用小结果集驱动大结果集，尽量减少 join 语句中的Nested Loop循环总次数。

• 优先优化 Nested Loop 内层循环，因为内层循环是循环中执行次数最多的，每次循环提升很小的性能都能在整个循环中提升很大的性能。

• 对被驱动表的 join 字段上建立索引，并且Join ON 条件的字段应该是相同类型的。

• 当被驱动表的 join 字段上无法建立索引的时候，设置足够的 Join Buffer Size。

• 对于非主键的连接查询，如果被驱动表数据特别多，建议先使用子查询查出一个临时的结果集然后再连接。（待验证）

• 对于可以直接从一个表中取数据的情况。（例如同一个表中取交集，例如好友表，互相关注才是好友）这样的情况，使用 Join 效率是要高于子查询的。

【总结】
掌握表连接算法，结合实践中不断的实验和摸索，从而真正达到高效使用MySQL算法的目的。

下一篇讲explain执行计划相关的知识，希望对大家的学习或者工作具有一定的参考价值。
【参考】

• InnoDB存储引擎 – 姜承尧

• MySQL Join算法与调优白皮书 – 姜承尧