MySQL ORDER BY 的几种排序算法

  • 表结构
1
2
3
4
5
6
7
8
9

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `city` varchar(16) NOT NULL,
  `name` varchar(16) NOT NULL,
  `age` int(11) NOT NULL,
  `addr` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `city` (`city`)
) ENGINE=InnoDB;

全字段排序

1

mysql> select city,name,age from t where city='山东省' order by name limit 10000  ;

说明

  • 全字段排序相当于将要SELECT的、WHERE后的、要ORDER BY排序的字段，全部取出，存入内存或磁盘文件中进行排序

执行过程

  • 初始化 sort_buffer，确定放入 name、city、age 这三个字段；
  • 从索引 city 找到第一个满足 city='山东省’条件的主键 id，也就是图中的 ID_X；
  • 到主键 id 索引取出整行，取 name、city、age 三个字段的值，存入 sort_buffer 中；
  • 从索引 city 取下一个记录的主键 id；
  • 重复步骤 3、4 直到 city 的值不满足查询条件为止，对应的主键 id 也就是图中的 ID_Y；
  • 对 sort_buffer 中的数据按照字段 name 做快速排序；
  • 按照排序结果取前 10000 行返回给客户端。

判断方式

  • 可通过 OPTIMIZER_TRACE 查看
    • filesort_summary 中的 sort_mode 为 packed_additional_fields，则表示使用全字段排序
    • chosen 为 false 则说明未使用优先队列排序算法(下文会介绍此算法)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

"filesort_priority_queue_optimization": {
  "limit": 10000,
  "rows_estimate": 12079764,
  "row_size": 170,
  "memory_available": 1048576,
  "strip_additional_fields": {
    "row_size": 44,
    "sort_merge_cost": 2.38e7,
    "priority_queue_cost": 9.89e7,
    "chosen": false       -- 表示未使用优先排序算法
  }
},
"filesort_execution": [
],
"filesort_summary": {
  "rows": 45608,
  "examined_rows": 45608,
  "number_of_tmp_files": 4,   -- 表示排序过程中，使用了4个临时文件  
  "sort_buffer_size": 1048504,
  "sort_mode": "<sort_key, packed_additional_fields>" -- 表示使用全字段排序
}

rowid 排序

1
2
3

--  针对本线程调整 max_length_for_sort_data 大小，以触发 rowid
mysql> SET max_length_for_sort_data = 16;
mysql> select city,name,age from t where city='山东省' order by name limit 10000  ;

说明

  • 全字段排序会将所有要返回的数据全部放入sort buffer中，然后再执行排序
  • 如果查询字段过多，内存里能够同时放下的行数很少，要分成很多个磁盘临时文件，排序的性能会很差
  • 当 MySQL 认为排序的单行长度过大时，MySQL会采用rowid算法进行排序
  • 使用rowid算法进行排序，相对于全字段排序，会多一次 limit行数 的回表的开销
  • 使用rowid的值由 max_length_for_sort_data 控制;当使用全字段排序写入临时表的字段长度超过 max_length_for_sort_data时，数据库会使用rowid排序
  • 实际处理方式是只取where所需字段、排序所需字段及主键id进行排序，之后回表查询要返回的数据

执行过程

  • 执行过程
    • 初始化 sort_buffer，确定放入两个字段，即 name 和 id；
    • 从索引 city 找到第一个满足 city='山东省’条件的主键 id，也就是图中的 ID_X；
    • 到主键 id 索引取出整行，取 name、id 这两个字段，存入 sort_buffer 中；
    • 从索引 city 取下一个记录的主键 id；
    • 重复步骤 3、4 直到不满足 city='杭州’条件为止，也就是图中的 ID_Y；
    • 对 sort_buffer 中的数据按照字段 name 进行排序；
    • 遍历排序结果，取前 10000 行，并按照 id 的值回到原表中取出 city、name 和 age 三个字段返回给客户端。

判断方式

  • 可通过 OPTIMIZER_TRACE 查看
    • filesort_summary 中的 sort_mode 为 packed_additional_fields，则表示使用全字段排序
    • chosen 为 true 则说明使用优先队列排序算法(下文会介绍此算法)
      • 由于使用 rowid 算法，排序字段较少，排序时 sort_buffer_pool 的大小可以容纳 10000 行值，所以使用优先队列排序算法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

"filesort_priority_queue_optimization": {
  "limit": 10000,
  "rows_estimate": 12079764,
  "row_size": 36,
  "memory_available": 1048576,
  "chosen": true       -- 由于使用 rowid 算法，排序字段较少，足够使用优先队列排序算法
},
"filesort_execution": [
],
"filesort_summary": {
  "rows": 10001,
  "examined_rows": 45608,
  "number_of_tmp_files": 0,       -- 由于使用 rowid 和 优先队列排序算法，sort_buffer_pool空间足够使用，不使用临时文件进行排序
  "sort_buffer_size": 440048,
  "sort_mode": "<sort_key, rowid>" -- 表示使用了 rowid 算法进行排序
}

优先队列排序算法

  • 表结构
1
2
3
4
5

mysql> CREATE TABLE `words` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `word` varchar(64) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;
  • 查询 sql
1

mysql> select word from words order by rand() limit 3;

说明

  • 当 limit 后数值不大时，InnoDB 并不会先进行取值
  • 而是创建一个堆，先读入limit后指定数量的值，然后继续对符合条件的值进行比较，替换堆中的值
  • 直至扫描完满足条件的值后，返回结果
  • 如果 limit 过大，超过 sort_buffer_size ，则会忽略此算法(由于堆维护成本比数组大，不能用 行数 * 字段长度 的方式进行估算)

执行过程

  • 以取 3 行为例子
    • 先取前三行，构造成一个堆
    • 取下一个行 (R’,rowid’)，跟当前堆里面最大的 R 比较，如果 R’小于 R，把这个 (R,rowid) 从堆中去掉，换成 (R’,rowid’)
    • 重复第 2 步，直到第 10000 个 (R’,rowid’) 完成比较

判断方式

  • 可通过 OPTIMIZER_TRACE
    • 查看 filesort_priority_queue_optimization 中的 chosen=true 表示使用了优先队列排序算法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

"filesort_priority_queue_optimization": {
  "limit": 1000,
  "rows_estimate": 3073480,
  "row_size": 45,
  "memory_available": 1048576,
  "chosen": true                 -- 表示使用优先队列排序算法
},
"filesort_execution": [
],
"filesort_summary": {
  "rows": 1001,
  "examined_rows": 439446,
  "number_of_tmp_files": 0,
  "sort_buffer_size": 53056,
  "sort_mode": "<sort_key, rowid>"
}

使用 OPTIMIZER_TRACE 判断 SQL 的具体执行过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/* 打开optimizer_trace，只对本线程有效 */
SET optimizer_trace='enabled=on'; 

/* 执行语句 */
select city,name,age from t where city='山东省' order by name limit 10000  ;

/* 查看 OPTIMIZER_TRACE 输出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G

/* 关闭本线程 optimizer_trace */
SET optimizer_trace='enabled=off';

ORDER BY 优化思路

通过复合索引获取有序数据避免 sort_buffer

1

mysql> alter table t add index city_user(city, name);
  • 增加索引后执行过程
    • 从索引 (city,name) 找到第一个满足 city='山东省’条件的主键 id；
    • 到主键 id 索引取出整行，取 name、city、age 三个字段的值，作为结果集的一部分直接返回；
    • 从索引 (city,name) 取下一个记录主键 id；
    • 重复步骤 2、3，直到查到第 10000 条记录，或者是不满足 city='山东省’条件时循环结束

使用覆盖索引

1

mysql> alter table t add index city_user_age(city, name, age);
  • 增加索引后执行过程
    • 从索引 (city,name,age) 找到第一个满足 city='山东省’条件的记录，取出其中的 city、name 和 age 这三个字段的值，作为结果集的一部分直接返回；
    • 从索引 (city,name,age) 取下一个记录，同样取出这三个字段的值，作为结果集的一部分直接返回；
    • 重复执行步骤 2，直到查到第 10000 条记录，或者是不满足 city='山东省’条件时循环结束。

参考

  • 极客时间 丁奇 « MySQL实战45讲 » 专栏