慢 SQL 优化实战：从一例线上慢 SQL 探究执行引擎工作过程
作者： vivo 互联网服务器团队- Li Xin
本文通过一个线上慢 SQL 案例，介绍了 Join 的两种算法和 Order by 的工作原理，并通过 Explain 和 Optimizer_trace 工具完整推演了慢 SQL 的执行过程。基于对原理和执行过程的分析，本文给出一种“引导执行引擎选择效率更高的算法”的方案，从而使查询性能得到大幅提升。
1、线上慢 SQL 背景
慢 SQL 会影响用户使用体验，降低数据库的整体性能，严重的甚至会导致服务器挂掉、整个系统瘫痪。笔者通过监控平台发现线上存在这样一条慢 SQL（原始 SQL 已脱敏，表结构出于简化的目的做了一定删减，实际执行耗时以文中提供数据为准），其执行耗时在分钟级。
表结构如下：
其他信息：
当发现慢 SQL 时，笔者的第一反应是使用 Explain 查看 SQL 的执行计划，结果如下：
通过 Explain 初步分析：两张表均执行了全表扫描，结合两张表的数据规模分析全表扫描并非耗时达到分钟级的主要原因。另外执行计划 extra 种提示的 Using temporary; Using filesort; Using join buffer (Block Nested Loop)又分别代表什么含义呢？
2、原理探究
2.1 Join 算法原理
2.1.1 驱动表和被驱动表
在 Join 语句中，执行引擎优先扫描的表被称为驱动表，另一张表被称为被驱动表。执行引擎在选择驱动表时，除了必须要遵守的特定语义外，最重要的考虑便是执行效率。
首先列举两种特定语义约束驱动表选取的场景：
场景一：Straight join 指定连接顺序，强制要求执行引擎优先扫描左侧的表。
场景二：Left/Right [outer] join，方向连接的特点是反方向表中如果不存在关联的数据则填充 NULL 值，这一特性要求方向查询时优先扫描相同方向的表。倘若 where 条件中明确指明反方向表中的部分列非空，则驱动表的选择就不受此语义的限制，执行引擎会依据效率选取驱动表。
当没有特定语义的约束时，执行引擎便会依据执行效率选取驱动表，如何判断哪张表作为驱动表的效率更高呢？下文会结合 Join 的两种算法更深入地探讨这个问题。
2.1.2 Block Nested-Loop Join
假设一个数据量为 m 行的驱动表与一个数据量为 n 行的被驱动表进行 join 查询。
最简单的一种算法：
从驱动表扫描一行数据；
对被驱动表进行全表扫描，得到的结果依次与驱动表的数据进行 join 并把满足条件的数据加入结果集；
接着扫描驱动表，每扫描一行数据，均重复执行一次步骤 2，直至驱动表的全部数据被扫描完毕。
这种算法的磁盘扫描开销为 m*n，非常低效，MySQL 在实际中并未直接使用该算法，而是采用缓存的思想（分配一块 Join buffer）对该算法进行改进，并命名为 Block Nested-Loop join(BNL)。
BNL 的算法步骤为：
从驱动表一次扫描 K 条数据，并把数据缓存在 Join buffer；
对被驱动表进行全表扫描，得到的结果依次与驱动表的 K 条数据进行 join 并把满足条件的数据加入结果集；
清空 join_buffer；
接着从驱动表再取出 K 条数据，重复步骤 2、3，直至扫描完驱动表的全部数据。
上述算法中，驱动表分段取数的次数记为 l，整个算法的磁盘扫描开销为 m+ln。由于分段的次数与驱动表的数据成正相关，所以公式可以记为 m+λmn，λ的取值范围为(0,1)。
当两张表的行数（m、n 大小）固定的情况下，m 对结果的影响更大，m 越小整体扫描的代价越小，所以执行引擎优先选择数据量更小的表作为驱动表(符合“小表驱动大表”的说法)。
2.1.3 Index Nested-Loop Join
BNL 算法使用了 Join buffer 结构，虽然有可能通过减少重复扫描来降低磁盘扫描开销，然而驱动表分段扫描的次数过多依然可能会导致查询的低效。索引是 MySQL 查询提效的重要结构，当被驱动表的关联键存在索引时，MySQL 会使用 Index Nested-Loop Join（NLJ）算法。
该算法的步骤为：
从驱动表扫描一行数据；
使用驱动表的关联键搜索被驱动表的索引树，通过被驱动表的索引结构找到被驱动表的主键，再通过主键回表查询出被驱动表的关联数据（暂不考虑覆盖索引的情况）；
接着扫描驱动表，每扫描一行数据，均重复执行一次步骤 2，直至驱动表的全部数据被扫描完毕。
每次搜索一棵树的复杂度近似为 log2 n，上述过程在被驱动表扫描一行数据的时间复杂度是 2log2 n，算法的整体复杂度为 m+2mlog2 n，在该算法中，依旧是 m 对结果的影响更大，m 越小整体扫描的代价越小，所以执行引擎总是选择数据量更小的表作为驱动表(符合“小表驱动大表”的说法)。
2.2 Order by 算法原理
2.2.1 全字段排序
MySQL 会为每个线程分配一块内存（Sort buffer）用于排序，当 Sort buffer 的空间不足时（通过系统参数 sort_buffer_size 设置 Sort buffer 的大小），执行引擎不得不开辟磁盘临时文件用于排序，此时排序的性能也会大幅降低。
全字段排序是将查询需要的所有字段进行暂存，并按照排序字段进行排序，并将排序后的结果集直接返回。
2.2.2 Rowid 排序
若要查询的数据单行占用空间较大，Sort buffer 中可以容纳的排序行数将会减少，此时使用磁盘临时文件进行排序的概率将会增大。为了提高排序性能，执行引擎提供一种只存储排序字段的算法，称为 Rowid 排序算法。
该算法的步骤为：
将参与排序的字段和主键进行临时存储；
按照排序字段进行排序，得到有序的主键；
根据有序的主键进行回表，按顺序将所有要查询的数据返回。
Rowid 排序在单行查询数据较大时可以通过节省临时排序空间从而达到降低排序开销的目的，然而该算法的代价是会增加磁盘扫描的次数（主键回表），所以是否选择使用该算法需要根据实际情况进行取舍（通过系统参数 max_length_for_sort_data 设置）。
3、调优过程
3.1 执行过程分析
了解了 Join 和 Order by 的工作原理，我们推测执行计划的大致过程为：
t_table_1 与 t_table_2 进行 Join 查询，使用了 BNL 算法（Using join buffer (Block Nested Loop)）
将 Join 的结果暂存临时表（Using temporary）
对临时表中的数据进行排序后返回（Using filesort）
为了佐证笔者的推测以及了解每一步的开销情况，Optimizer_trace 命令可以提供更多执行过程细节。
上图展示的即为执行引擎预估的执行计划，从 Optimizer_trace 的输出结果中可以佐证上述对于执行过程的推测。另外我们可以得到执行代价的结果为：
t_table1 的扫描行数为 3000，代价为 615;
t_table2 的扫描行数为 69882，由于 BNL 算法 t_table2 会被多次全表扫描，整体代价为 4.19e7;
对 Join 结果进行排序的开销为 2.1e8。
从执行引擎预估的执行计划可以看出执行引擎认为排序的开销最大，另外由于使用 BNL 算法会导致被驱动表执行多次全表扫描，其执行代价仅次于排序。然而预估的执行计划并不代表真正的执行结果，下面展示 Optimizer_trace 命令对于真实执行结果部分参数：
从执行结果参数来看：
执行引擎使用临时表保存 Join 的结果，且临时表是一张内存表。
参与排序的数据行数为 3000 行，没有使用磁盘临时文件进行排序，排序算法选择的是 Rowid 排序。
综合执行引擎的预估的执行计划和真实的执行结果参数可以得出，执行引擎预估最大的执行开销为排序，但实际上排序并未使用到磁盘临时文件，且 Rowid 排序的回表操作是在内存中进行的（在内存临时表中进行回表），3000 条数据的内存排序开销是极快的，所以真实的最大开销是 BNL 算法导致的对被驱动表多次进行全表扫描的开销。
3.2 最终的优化
对于 BNL 算法，可以通过在被驱动表添加索引使其转化为 NLJ 算法来进行优化（此处注意一些索引失效的场景，笔者在实际调优中遇到了字符集不同导致的索引失效场景）。在 t_table2 表添加索引后，观察一周内的 SQL 监控如下，可以看到 SQL 最大响应时间不超过 20ms，执行效率得到了大幅提升。
4、总结
本文完整的介绍了一个 SQL 调优案例，通过这个案例可以归纳出 SQL 调优的基本思想。首先，需要了解 SQL 语句中的关键字（Join、Order by...）的基本工作原理，并辅助一些执行过程数据（Explain、Optimizer_trace），通过实验验证猜想，最终达成调优的目的。
版权声明: 本文为 InfoQ 作者【vivo互联网技术】的原创文章。
原文链接:【http://xie.infoq.cn/article/c38ed03a9faedfdd2d6047138】。文章转载请联系作者。
官方公众号：vivo互联网技术，ID：vivoVMIC 2020-07-10 加入
分享 vivo 互联网技术干货与沙龙活动，推荐最新行业动态与热门会议。
评论