MySQL order by 原理

转自 16 | “order by”是怎么工作的?

16 “order by”是怎么工作的?

select city,name,age from t where city='杭州' order by name limit 1000 ;

全字段排序

以我们前面举例用过的市民表为例,假设你要查询城市是“杭州”的所有人名字,并且按照姓名排序返回前 1000 个人的姓名、年龄。

Extra 这个字段中的“Using filesort”表示的就是需要排序,MySQL 会给每个线程分配一块内存用于排序,称为 sort_buffer。

通常情况下,这个语句执行流程如下所示 :

1.初始化 sort_buffer,确定放入 name、city、age 这三个字段;

2.从索引 city 找到第一个满足 city=’杭州’条件的主键 id,也就是图中的 ID_X;

3.到主键 id 索引取出整行,取 name、city、age 三个字段的值,存入 sort_buffer 中;

4.从索引 city 取下一个记录的主键 id;

5.重复步骤 3、4 直到 city 的值不满足查询条件为止,对应的主键 id 也就是图中的 ID_Y;

6.对 sort_buffer 中的数据按照字段 name 做快速排序;

7.按照排序结果取前 1000 行返回给客户端。

sort_buffer_size,就是 MySQL 为排序开辟的内存(sort_buffer)的大小。如果要排序的数据量小于 sort_buffer_size,排序就在内存中完成。但如果排序数据量太大,内存放不下,则不得不利用磁盘临时文件辅助排序。

可以用下面的方法,来确定一个排序语句是否使用了临时文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

/* @a 保存 Innodb_rows_read 的初始值 */
select VARIABLE_VALUE into @a from performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 执行语句 */
select city, name,age from t where city='杭州' order by name limit 1000;

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

/* @b 保存 Innodb_rows_read 的当前值 */
select VARIABLE_VALUE into @b from performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 计算 Innodb_rows_read 差值 */
select @b-@a;

number_of_tmp_files 表示的是,排序过程中使用的临时文件数。你一定奇怪,为什么需要 12 个文件?内存放不下时,就需要使用外部排序,外部排序一般使用归并排序算法。可以这么简单理解,MySQL 将需要排序的数据分成 12 份,每一份单独排序后存在这些临时文件中。然后把这 12 个有序文件再合并成一个有序的大文件。

rowid 排序

MySQL 认为排序的单行长度太大会怎么做呢?

max_length_for_sort_data,是 MySQL 中专门控制用于排序的行数据的长度的一个参数。它的意思是,如果单行的长度超过这个值,MySQL 就认为单行太大,要换一个算法。

1.初始化 sort_buffer,确定放入两个字段,即 name 和 id;

2.从索引 city 找到第一个满足 city=’杭州’条件的主键 id,也就是图中的 ID_X;

3.到主键 id 索引取出整行,取 name、id 这两个字段,存入 sort_buffer 中;

4.从索引 city 取下一个记录的主键 id;

5.重复步骤 3、4 直到不满足 city=’杭州’条件为止,也就是图中的 ID_Y;

6.对 sort_buffer 中的数据按照字段 name 进行排序;

7.遍历排序结果,取前 1000 行,并按照 id 的值回到原表中取出 city、name 和 age 三个字段返回给客户端。

全字段排序 VS rowid 排序

如果 MySQL 实在是担心排序内存太小,会影响排序效率,才会采用 rowid 排序算法,这样排序过程中一次可以排序更多行,但是需要再回到原表去取数据。

如果 MySQL 认为内存足够大,会优先选择全字段排序,把需要的字段都放到 sort_buffer 中,这样排序后就会直接从内存里面返回查询结果了,不用再回到原表去取数据。

这也就体现了 MySQL 的一个设计思想:如果内存够,就要多利用内存,尽量减少磁盘访问。

对于 InnoDB 表来说,rowid 排序会要求回表多造成磁盘读,因此不会被优先选择。

1.从索引 (city,name) 找到第一个满足 city=’杭州’条件的主键 id;

2.到主键 id 索引取出整行,取 name、city、age 三个字段的值,作为结果集的一部分直接返回;

3.从索引 (city,name) 取下一个记录主键 id;

4.重复步骤 2、3,直到查到第 1000 条记录,或者是不满足 city=’杭州’条件时循环结束。

假设你的表里面已经有了 city_name(city, name) 这个联合索引,然后你要查杭州和苏州两个城市中所有的市民的姓名,并且按名字排序,显示前 100 条记录。如果 SQL 查询语句是这么写的 :

select * from t where city in ('杭州'," 苏州 ") order by name limit 100;

那么,这个语句执行的时候会有排序过程吗,为什么?

如果业务端代码由你来开发,需要实现一个在数据库端不需要排序的方案,你会怎么实现呢?

进一步地,如果有分页需求,要显示第 101 页,也就是说语句最后要改成 “limit 10000,100”, 你的实现方法又会是什么呢?

1) 需要排序,虽然有 (city,name) 联合索引,对于单个 city 内部,name 是递增的。但是由于这条 SQL 语句不是要单独地查一个 city 的值,而是同时查了”杭州”和” 苏州 “两个城市,因此所有满足条件的 name 就不是递增的了。也就是说,这条 SQL 语句需要排序。
2) 执行 select from t where city=“杭州” order by name limit 100; 这个语句是不需要排序的,客户端用一个长度为 100 的内存数组 A 保存结果。
执行 select
from t where city=“苏州” order by name limit 100; 用相同的方法,假设结果被存进了内存数组 B。
现在 A 和 B 是两个有序数组,然后你可以用归并排序的思想,得到 name 最小的前 100 值,就是我们需要的结果了。

select from (
select
from t where city = ‘杭州’ limit 100
union all
select * from t where city = ‘苏州’ limit 100
) as tt order by name limit 100

select * from t join
(select id from t where city in(‘杭州’,’苏州’) order by name limit 10000,100) t_id
on t.id=t_id.id;

3) select from t where city=” 杭州 “ order by name limit 10100;
select
from t where city=” 苏州 “ order by name limit 10100。
然后,再用归并排序的方法取得按 name 顺序第 10001~10100 的 name、id 的值,然后拿着这 100 个 id 到数据库中去查出所有记录。

3)对分页的优化。
没有特别好的办法。如果业务允许不提供排序功能,不提供查询最后一页,只能一页一页的翻,基本上前几页的数据已经满足客户需求。
为了意义不大的功能优化,可能会得不偿失。
如果一定要优化可以 select id from t where city in (‘杭州’,” 苏州 “) order by name limit 10000,100
因为有city\name索引,上面的语句走覆盖索引就可以完成,不用回表。
最后使用 select * from t where id in (); 取得结果
对于这个优化方法,我不好确定的是临界点,前几页直接查询就可以,最后几页使用这个优化方法。
但是中间的页码应该怎么选择不太清楚

References

[1] 16 | “order by”是怎么工作的?