业务中的各种查询通常对应了用户所看到的各项列表,列表一般是根据某个维度进行排序。
换句话说,业务中使用 SELECT
语句的时候除了不可避免的搭配 WHERE
以外,还会配合 ORDER BY
进行使用。
今天来好好聊聊 MySQL 的 ORDER BY
排序。
说到排序算法,有插入排序、选择排序、归并排序、堆排序、快速排序、计数排序、桶排序、基数排序、冒泡排序、希尔排序、梳排序 ...
关于各种排序算法的排序流程和具体实现,不是本篇博客的重点,不作详细说明。
这里直接贴各类排序算法的时空复杂度:
通常我们实现的这些排序算法,都是在”纯内存“环境中进行。
MySQL 作为数据库难道是在先将所有要排序的数据加载到内存,再应用排序算法吗?
在分析 MySQL 的不同的排序方案之前,先来了解 sort buffer 概念。
MySQL 会为每个线程分配固定大小的 sort buffer 用作排序。
sort buffer 是具有逻辑概念的内存区域,大小由 sort_buffer_size
参数控制,默认为 256 kb。
由于 sort buffer 大小固定,而 data(待排序的数据量)并不固定,所以根据 sort buffer 与 data(待排序数据量)的大小差值,可分为内部排序和外部排序:
data <= sort buffer
:即 sort buffer 够用,这时候 MySQL 只需要在内存中进行排序即可。内部排序使用的是快速排序data > sort buffer
:这时候 sort buffer 不够用,MySQL 需要借助外部“容器”(通常是文件)进行排序。通常会将待排序数据分成多个“小文件”,对各个“小文件”进行排序,再汇总成一个有序的“大文件”。外部排序使用的是归并排序如何验证当前执行的排序语句使用的是内部排序还是外部排序?
可以通过 EXPLAIN
命令来查看,如果在分析结果中的 Extra
字段里包含 Using filesort
字眼,说明执行了外部排序操作。
全字段排序是指,只要与最终结果集有关的字段都会被放进 sort buffer,而不管该字段本身是否参与排序。
以下面的 SQL 为例子:
SELECT nick_name, age, phone
FROM t_user
WHERE city = "深圳"
ORDER BY nick_name;
假设 city 字段上有索引,全字段排序的过程:
可以看到当查询条件本身有索引可用的话,全字段排序的排序过程都在 sort buffer(内存)进行,回表次数为符合条件的数据个数。
当然,如果我们建立的是 city、nick_name、age、phone 的联合索引,还可以实现“索引覆盖”,即在一棵索引树上取得全部所需数据,减少回表(随机读)次数。
不过针对每个查询或排序语句建立联合索引,会导致索引过多,大大降低写入更新数据的速度,以及大大提升数据所需要的存储空间。
生产上对索引的建立修改需要格外谨慎。
rowId 就是 MySQL 对每行数据的唯一标识符。
当数据表有主键时,rowId 就是表主键;当数据表没有主键或者主键被删除时,MySQL 会自动生成一个长度为 6 字节的 rowId 为作为 rowId。
rowId 排序是指只将与排序相关的字段和 rowId 放入 sort buffer,其余结果集需要用到的数据在排序完成后,通过 rowId 回表取得。
全字段排序的流程看着已经十分合理,为什么还需要有个 rowId 排序?
这是我们只需要输出三个字段的情况,假如我们有上百个字段需要返回呢?sort buffer 默认只有 256 kb。能够装下多少行的原始数据行?
所以当待排序的数据行很大的时候,使用全字段排序必然会导致“外部排序”。而且是使用很多临时文件的“外部排序”,效率很低下。
相比全字段排序,rowId 排序的好处是在 sort buffer 大小固定的情况下,sort buffer 能够容纳更多的数据行,能够避免使用或者少使用“外部排序文件”。
缺点是最终返回结果集的时候,需要再次进行回表。
还是之前那个例子:
SELECT nick_name, age, phone
FROM t_user
WHERE city = "深圳"
ORDER BY nick_name;
rowId 排序全过程:
注意:在步骤 4 中不会等所有排序好的 id 回表完再返回,而是每个 id 回表一次,取得该行数据之后立即返回,所以不会消耗额外的内存。
无论是使用全字段排序还是 rowId 排序,都不可避免了对所有符合 WHRER
条件的数据进行了排序。
有读者可能会认为,那不是应该的吗?
设想一下,如果我们还搭配着 LIMIT
使用呢?
例如我们在排序语句后添加 LIMIT 3
,哪怕查出来的数据有 10W 行,我们也只需要前 3 行有序。
为了得到前 3 行数据,而不得不将 10W 行数据载入内存,大大降低了 sort buffer 的利用率。
这时候你可能想到利用“最小堆”、“最大堆”来进行排序。
没错,这正是 MySQL 针对带有 LIMIT
的 ORDER BY
语句的优化:使用优先队列进行排序。
以下面的 SQL 为例子:
SELECT nick_name, age, phone
FROM t_user
WHERE city = "深圳"
ORDER BY nick_name LIMIT 3;
优先队列进行排序的流程:
LIMIT
(本例中为 3)的数据,构建一个堆现在我们知道有全字段排序和 rowId 排序,那么 MySQL 是如何在这两种排序方案中做选择呢?
由于 rowId 排序相对于全字段排序,不可避免的多了一次回表操作,回表操作意味着随机读,而随机 IO 是数据库中最昂贵的操作。
所以 MySQL 会在尽可能的情况下选择全字段排序。
那么什么情况下 MySQL 会选择 rowId 排序呢,是否有具体的值可以量度?
答案是有的,通过参数 max_length_for_sort_data
可以控制用于排序的行数据最大长度,默认值为 1024 字节。
当单行数据长度超过该值,MySQL 就会觉得如果还用全字段排序,会导致 sort buffer 容纳下的行数太少,从而转为使用 rowId 排序。
通常对于一个执行较慢的排序语句,在使用 EXPLAIN
进行执行过程分析的时候除了能看到 Using filesort
以外,还能看到 Using temporary
,代表在排序过程中使用到了临时表。
MySQL 优先使用内存临时表。当 MySQL 使用内存临时表时,临时表存储引擎为 memory 。
如果当前 MySQL 使用的是内存临时表的话,将会直接使用 rowId 排序,因为这时候所谓的“回表”只是在内存表中读数据,操作不涉及硬盘的随机 IO 读。
使用 rowId 可以在 sort buffer 容纳更多的行,避免或减少外部排序文件的使用。
如果系统中很多使用临时表的排序语句需要执行,而又不加以限制,全都使用临时表的话,内存很快就会被打满。
所以 MySQL 提供了 tmp_table_size
参数限制了内存临时表的大小,默认值是 16M。
如果临时表大小超过了tmp_table_size
,那么内存临时表就会转成磁盘临时表。
当使用磁盘临时表的时候,表储存引擎将不再是 memory,而是由 internal_tmp_disk_storage_engine
参数控制,默认为 InnoDB
。
这时候 MySQL 会根据单行大小是否超过 max_length_for_sort_data
决定采用全字段排序还是 rowId 排序。
总结一下,MySQL 总是使用 「最快」 的排序方案:
max_length_for_sort_data而决定使用
rowId 排序还是全字段排序,优先选择全字段排序,以减少回表次数tmp_table_size
限制时,则需要将内存临时表转换为磁盘临时表,这时候由于回表意味着随机读,所以会搭配全字段排序方式通过本篇文章,除了和大家分享「MySQL 排序」知识以外,还想让大家感受「算法是如何融合在工程」的。
曾经我只是一名小小 OIer,不懂开发,对工程项目和框架一无所知。
随着我从事 Java 后端开发一段时间,阅读过一些优秀的源码,每次我都被工程对「数据结构与算法」的运用所震撼。
JDK 中的 Arrays.sort()
综合排序实现、HashMap
的链表转红黑树;MySQL
的 B+ 树索引搭配分 Slot 实现的数据页设计(为了能够实现二分查找)、Redis 的压缩列表与跳表设计 ...
算法在日常开发看不到的地方,发挥着巨大作用。
但同时,我也经常听到不少开发圈的同学吐槽算法无用。甚至在开源软件作者群聊中,每次谈到算法都会有群友跑出来踩一波算法,说算法与八股文一样,除了加速内卷一无所用,当中不乏一些国内知名互联网大厂的资深开发专家。
我相信他们也是看过源码的,甚至可能是著名开源项目的 committer。
作为在某些领域的「权威」,又是众多职场新人的领导前辈,在上百人的群聊中传递「算法无用」这样不讲逻辑的价值观念,我觉得可笑。
当然,碍于面子与职称,我没有在对话中反驳他们。
如果你是持有这类观念的人,也许你不会遇到一个在正面场合与你争论的人(我认识的 OIer 大多是学生,很安静的一群人,不喜欢争论),但不代表的你的观念正确。
对于算法,你可以不懂,那你没资格评论;你可以很懂,觉得算法就那样了,索然无味,这也没有问题,但请不要以正确价值的姿态去传播「算法无用」的观点。
如果你是对算法充满好奇,想去了解学习,但又经常会听到前辈说「那玩意没什么用」的同学(特别是中学生),请你赶紧拥抱算法,你们才是未来。
声明:本文谨代表个人观点。