一、 前言
本文描述了团队在工作中遇到的一个MySQL分页查询问题，顺带讲解相关知识点，为后来者鉴。本文重点不是"怎样"优化表结构和SQL语句，而是探索不同查询方式"为什么"会有显著差异，涉及下列知识点：
- MySQL 延迟关联
- MySQL Optimizer Trace使用
- MySQL 排序原理
二、 问题
工作中用到了一张表，字段比较多，每行大概500字节，总行数大概80万。场景中，需要根据某个非索引字段排序，然后进行分页读取。现把脱敏之后的表结构奉上（只修改了字段名），通过简单脚本插入80万行模拟数据即可以测试了。
2.1 表结构
CREATE TABLE `t` (
`a0` varchar(16) NOT NULL,
`a1` bigint(20) NOT NULL,
`a2` decimal(27,9) NOT NULL DEFAULT '0', `a3` decimal(27,9) NOT NULL DEFAULT '0',
`a4` decimal(27,9) NOT NULL DEFAULT '0', `a5` decimal(27,9) NOT NULL DEFAULT '0',
`a6` decimal(27,9) NOT NULL DEFAULT '0', `a7` decimal(27,9) NOT NULL DEFAULT '0',
`a8` decimal(18,9) NOT NULL DEFAULT '0', `a9` decimal(18,9) NOT NULL DEFAULT '0',
`b1` decimal(27,9) NOT NULL DEFAULT '0', `b2` decimal(27,9) NOT NULL DEFAULT '0',
`b3` decimal(18,9) NOT NULL DEFAULT '0', `b4` decimal(18,9) NOT NULL DEFAULT '0',
`b5` decimal(18,9) NOT NULL DEFAULT '0', `b6` decimal(18,9) NOT NULL DEFAULT '0',
`b7` decimal(18,9) NOT NULL DEFAULT '0', `b8` decimal(18,9) NOT NULL DEFAULT '0',
`b9` decimal(18,9) NOT NULL DEFAULT '0', `c1` decimal(18,9) NOT NULL DEFAULT '0',
`c2` decimal(18,9) NOT NULL DEFAULT '0', `c3` decimal(18,9) NOT NULL DEFAULT '0',
`c4` decimal(18,9) NOT NULL DEFAULT '0', `c5` decimal(18,9) NOT NULL DEFAULT '0',
`c6` decimal(18,9) NOT NULL DEFAULT '0', `c7` int(11) NOT NULL DEFAULT '0',
`c8` int(11) NOT NULL DEFAULT '0', `c9` int(11) NOT NULL DEFAULT '0',
`d1` int(11) NOT NULL DEFAULT '0', `d2` int(11) NOT NULL DEFAULT '0',
`d3` decimal(18,9) NOT NULL DEFAULT '0', `d4` decimal(18,9) NOT NULL DEFAULT '0',
`d5` decimal(18,9) NOT NULL DEFAULT '0', `d6` decimal(18,9) NOT NULL DEFAULT '0',
`d7` decimal(18,9) NOT NULL DEFAULT '0', `d8` decimal(18,9) NOT NULL DEFAULT '0',
`d9` int(11) NOT NULL DEFAULT '0', `e1` decimal(27,9) NOT NULL DEFAULT '0',
`e2` decimal(27,9) NOT NULL DEFAULT '0', `e3` decimal(27,9) NOT NULL DEFAULT '0',
`e4` decimal(18,9) NOT NULL DEFAULT '0', `e5` decimal(18,9) NOT NULL DEFAULT '0',
`e6` decimal(18,9) NOT NULL DEFAULT '0', `e7` decimal(18,9) NOT NULL DEFAULT '0',
`e8` decimal(18,9) NOT NULL DEFAULT '0', `e9` decimal(18,9) NOT NULL DEFAULT '0',
`f1` decimal(18,9) NOT NULL DEFAULT '0', `f2` decimal(18,9) NOT NULL DEFAULT '0',
PRIMARY KEY (`a0`,`a1`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
查询显式用到的字段是a0和a1。再看一下表信息：
# select * from information_schema.tables where table_name='t'\G
SELECT * FROM tables where table_name='t'\G
*************************** 1. row ***************************
TABLE_CATALOG: def
TABLE_SCHEMA: test
TABLE_NAME: t
TABLE_TYPE: BASE TABLE
ENGINE: InnoDB
VERSION: 10
ROW_FORMAT: Compact
TABLE_ROWS: 799304
AVG_ROW_LENGTH: 482
DATA_LENGTH: 385875968
MAX_DATA_LENGTH: 0
INDEX_LENGTH: 0
DATA_FREE: 5242880
AUTO_INCREMENT: NULL
CREATE_TIME: 2017-01-13 09:34:59
UPDATE_TIME: NULL
CHECK_TIME: NULL
TABLE_COLLATION: utf8_general_ci
CHECKSUM: NULL
CREATE_OPTIONS:
TABLE_COMMENT:
2.2 两种查询
最初，使用最直接的查询语句，耗时6.67秒：
SQL_1: SELECT * FROM t ORDER BY a1 DESC LIMIT 100000,1;
随后，使用"延迟关联"，耗时0.90秒：
SQL_2: SELECT * FROM t INNER JOIN (SELECT a0, a1 FROM t ORDER BY a1 DESC LIMIT 100000,1) AS A USING (a0, a1);
延迟关联，先根据条件查询需要的主键，再根据主键关联原表获得需要的数据。
问题： 为什么SQL_2比SQL_1执行快那么多？
三、背景知识
工欲善其事，必先利其器。MySQL查询分析的利器，就似乎其自带的"MySQL Optimizer Trace"。 另外，还必须对MySQL的查询执行过程有一个基本了解，特别是排序过程。
3.1 Optimizer Trace 使用简介
Optimizer Trace 是MySQL 5.6.3里新加的一个特性，可以把MySQL Optimizer的决策和执行过程输出成文本，结果为JSON格式，兼顾了程序分析和阅读的便利。
【使用方法】
- 启用Optimizer Trace，它默认是关闭的。
SET optimizer_trace="enabled=on"; - 设置Trace使用的内存，默认内存比较小，有时候不够用:
SET optimizer_trace_max_mem_size=1024000; - 执行SQL语句
SQL_1: SELECT * FROM t ORDER BY a1 DESC LIMIT 100000,1;
SQL_2: SELECT * FROM t INNER JOIN (SELECT a0, a1 FROM t ORDER BY a1 DESC LIMIT 100000,1) AS A USING (a0, a1); - 查看Trace输出
select trace from information_schema.optimizer_trace\G
Trace输出分为3大部分，如下，分别对应到mysql中的三个函数： JOIN::prepare(), JOIN::optimize(), JOIN::exec()
{
trace: {
steps: [
{ join_preparation: {} }, <--> JOIN::prepare()
{ join_optimization: {} }, <--> JOIN::optiomize()
{ join_execution: {} } <--> JOIN::exec()
]
}
}
【系统参数】
追踪行为完全由OPTIMIZER_TRACE系列参数控制，关于这些参数的详细说明参考MySQL在线文档。
# show variables like '%optimizer_trace%';
+------------------------------+----------------------------------------------------------------------------+
| Variable_name | Value |
+------------------------------+----------------------------------------------------------------------------+
| optimizer_trace | enabled=off,one_line=off |
| optimizer_trace_features | greedy_search=on,range_optimizer=on,dynamic_range=on,repeated_subselect=on |
| optimizer_trace_limit | 1 |
| optimizer_trace_max_mem_size | 16384 |
| optimizer_trace_offset | -1 |
+------------------------------+----------------------------------------------------------------------------+
一般只要关心optimizer_trace/optimizer_trace_max_mem_size这两个参数。optimizer_trace可以开启和关闭追踪，结果打印方式等，optimizer_trace_max_mem_size决定追踪工具最多可以使用多少内容。
optimizer_trace enabled=on 启用追踪
enabled=off 不启用追踪
one_line=on TRACE输出在一行里面，便于程序处理
one_line=off TRACE输出在多行，便于阅读
optimizer_trace_max_mem_size 追踪时最多允许使用多少内存，内存太小可能输出不完整。
这些参数都是基于SESSION的，并且optimizer_trace默认情况下没有开启，使用起来很安全。随后的章节会有详细实用案例，此处不再赘述。
3.2 MySQL排序简介
对于MySQL排序有篇文章写的不错：MySQL排序内部原理探秘, 也可以阅读MySQL源代码的filesort.cc。这里挑选几个重点列举下：
- MySQL会把需要排序的数据从磁盘读取到"Sort_buffer"。放到Sort_buffer的字段由 max_length_for_sort_data 决定：
a) 字段总长度>max_length_for_sort_data，读取"排序字段+RowID"。这种方式称为回表模式，记为：< sort_key,rowid>
b) 字段总长度<=max_length_for_sort_data，读取"排序字段+SELECT字段+WHERE字段"。这种方式称为不回表模式，记为：<sort_key,additional_fields> - Sort_buffer有大小限制，在我们的场景中，是8MB。
- 数据量超过Sort_buffer时，会初步排序，然后写入外部临时表。
- 若使用了临时表，通过"多路归并排序"逐步合并，直到最后输出有序结果。
- 使用了临时表时，查询性能一般来说会急剧下降。
- 对于带Order By+Limit的语句，会进行"优先队列"评估，如果适用，可以只取若干元素，加速排序。
优先队列评估 是非常重要的一个步骤，对TopN查询性能提升很大，过程简要描述如下：
* 估算数据表的数据总量上限 N
* 计算需要返回的数据总量 M = (LIMIT + OFFSET)
* 计算Sort_buffer容量 X
* Case 1: 如果 X > N
Case 1.1: 如果 M < N / PQ_slowness，启用优先队列
Case 1.2: 否则，不启用优先队列，而是直接用快速排序。
* Case 2: 如果 X > M + 1，启用优先队列
* Case 3: 如果当前是不回表模式，尝试去除非排序字段重新计算Sort_buffer容量 Y，
Case 3.1 如果 Y > M + 1，估算启用优先队列+回表模式的代价 C1，估算使用临时表多路归并+不回表模式的代价 C2
Case 3.1.1: 如果 C1 < C2，启用优先队列，并修改为回表模式；
Case 3.1.2: 否则不启用优先队列。
* Final: 各条件不满足，不启用优先队列。
图3-1 优先队列评估过程
四、 观察案例中SQL的执行
准备测试环境：
# SHOW variables like '%sort%';
+--------------------------------+---------------------+
| Variable_name | Value |
+--------------------------------+---------------------+
| max_length_for_sort_data | 1024 |
| sort_buffer_size | 8388608 |
+--------------------------------+---------------------+
# SET optimizer_trace="enabled=on";
# SET optimizer_trace_max_mem_size=1000000;
# SELECT trace FROM information_schema.optimizer_trace\G
注意两个重要变量
max_length_for_sort_data: 1024
sort_buffer_size: 8388608
4.1 SQL_1 执行过程
SELECT * FROM t ORDER BY a1 DESC LIMIT 100000,1;
图4-1 SQL_1 执行过程
解析
* ORDER BY a1, 排序字段a1无索引，使用全文扫描
* SELECT *, 需要读取所有字段
* SELECT字段+排序字段+WHERE字段长度=454，454 < max_length_for_sort_data(1024)，使用不回表模式。
* 查询中存在Order By+Limit，需进行优先队列评估
Case 1 不满足: 1850799*454 > 8388608
Case 2 不满足: 100001*454 > 8388608
Case 3.1 满足: 74*(100001+1) < 8388608
计算PQ代价 C1 = 1.18e9
计算外排代价 C2 = 3.04e6
C1 > C2，优先队列得不偿失，不启用
* 执行结果：无优先队列，不回表模式，使用了46个临时表
4.2 SQL_2 执行过程
SELECT * FROM t INNER JOIN (SELECT a0, a1 FROM t ORDER BY a1 DESC LIMIT 100000,1) AS A USING (a0, a1);
图4-2 SQL_2 执行过程
解析
*首先执行子查询 SELECT a0, a1 FROM t ORDER BY a1 DESC LIMIT 100000,1
SELECT a0,a1, 只需要读取a0和a1两个字段
ORDER BY a1, 排序字段a1无索引，使用全文扫描
SELECT字段+排序字段+WHERE字段长度=66，66 < max_length_for_sort_data(1024)，使用不回表模式。
查询中存在 Order By+Limit，进行优先队列评估
Case 1 不满足: 1850799*66 > 8388608
Case 2 可满足: 100001*66 > 8388608
启用优先队列
执行结果：启用优先队列，不回表模式，没有使用临时表
执行完毕，结果存储在临时表A里面
* 临时表A只有1行，连表查询时，可以使用 t 的主键，非常快速。
4.3 小结
- 全表扫描时，SQL_1需要读取所有字段（大约500字节），SQL_2只需要读取2个字段（小于100字节）。
- SQL1需要使用外部排序，临时表数量又比较多（46个），所以比较慢。
- SQL2可以启用优先队列优化，排序用数据全部存放在sort_buffer，加速明显。
五、场景扩展
5.1 Limit 大小对执行过程的影响
稍微修改下SQL语句，把 LIMIT 100000,1 修改为 LIMIT 600000,1，再看执行过程。
5.1.1 SQL_1 执行过程
SELECT * FROM t ORDER BY a1 DESC LIMIT 600000,1;
1 row in set (8.82 sec)
图5-1 Limit 600000 时 SQL_1 执行过程
解析
这次的执行结果和4.1完全一样，还是"无优先队列+不会表模式"，但决策依据稍有不同：
(600001+1)*74 > 8388608，Case 3.1不满足，而之前是Case 3.1.1不满足。
5.1.2 SQL_2 执行过程
SELECT * FROM t INNER JOIN (SELECT a0, a1 FROM t ORDER BY a1 DESC LIMIT 600000,1) AS A USING (a0, a1);
1 row in set (1.05 sec)
图5-2 Limit 600000 时 SQL_2 执行过程
解析
- 这次查询比4.2慢，因为Case 2和Case 3.1都不满足，未启用优先队列，使用"无优先队列+不回表模式"。
- 但是和5.1.1相比，子查询的数据总量变少，只使用了8个临时表，还是更快。
5.2 回表排序的影响
以上测试，都是不回表模式，如果是回表模式，会怎么样呢？先把关键参数设置更小，迫使MySQL使用回表模式：SET max_length_for_sort_data=100;
5.2.1 SQL_1 执行过程
SELECT * FROM t ORDER BY a1 DESC LIMIT 600000,1;
1 row in set (4.16 sec)
解析
- 因为(SELECT字段+排序字段+WHERE字段)(454字节) > max_length_for_sort_data(100)，这次使用了回表模式，但还是无法启用优先队列优化。
- 因为排序时只需要读取排序字段和rowid，临时表数量减少到8个。
5.2.2 SQL_2 执行过程
SELECT * FROM t INNER JOIN (SELECT a0, a1 FROM t ORDER BY a1 DESC LIMIT 600000,1) AS A USING (a0, a1);
1 row in set (1.05 sec)
解析
由于(SELECT字段+排序字段+WHERE字段)(66字节) < max_length_for_sort_data(100)，依然还是"无优先队列+不回表模式""，使用了8个临时表。
六、参考资料
- MySQL: Tracing the Optimizer
- MySQL: Optimizing SELECT Statements
- Using delayed JOIN to optimize count and LIMIT queries
- MySQL排序内部原理探秘
- MySQL Server 5.6.34 Source Code
- 高性能 MySQL 3rd Edition
