前言

业务中的各种查询通常对应了用户所看到的各项列表,列表一般是根据某个维度进行排序。

换句话说,业务中使用 SELECT 语句的时候除了不可避免的搭配 WHERE 以外,还会配合 ORDER BY 进行使用。

今天来好好聊聊 MySQL 的 ORDER BY 排序。

排序算法

说到排序算法,有插入排序、选择排序、归并排序、堆排序、快速排序、计数排序、桶排序、基数排序、冒泡排序、希尔排序、梳排序 ...

关于各种排序算法的排序流程和具体实现,不是本篇博客的重点,不作详细说明。

这里直接贴各类排序算法的时空复杂度:

通常我们实现的这些排序算法,都是在”纯内存“环境中进行。

MySQL 作为数据库难道是在先将所有要排序的数据加载到内存,再应用排序算法吗?

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 字段上有索引,全字段排序的过程:

  1. 从 city 索引树上找到第一条值为深圳的数据,取得 id 之后回表(回到主键索引)取得 nick_name、age、phone 三个字段放入 sort buffer

  2. 从 city 索引树取下一条值为深圳的数据,重复 1 过程,直到下一条数据不满足值为深圳条件

  3. 到这一步,所有 city = 深圳 的数据都在 sort buffer 了。对 nick_name 执行快速排序

  4. 将排序结果返回

可以看到当查询条件本身有索引可用的话,全字段排序的排序过程都在 sort buffer(内存)进行,回表次数为符合条件的数据个数。

当然,如果我们建立的是 city、nick_name、age、phone 的联合索引,还可以实现“索引覆盖”,即在一棵索引树上取得全部所需数据,减少回表(随机读)次数。

不过针对每个查询或排序语句建立联合索引,会导致索引过多,大大降低写入更新数据的速度,以及大大提升数据所需要的存储空间。

生产商对索引的建立修改需要格外谨慎。

rowId 排序

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 排序全过程:

  1. 从 city 索引树上找到第一条值为深圳的数据,取得 id 之后回表(回到主键索引)取得 nick_name 这个与排序相关的字段和主键 id 一起放入 sort buffer

  2. 从 city 索引树取下一条值为深圳的数据,重复 1 过程,直到下一条数据不满足值为深圳条件

  3. 这时候,所有 city = 深圳 的数据都在 sort buffer 了(sort buffer 里面的数据包含两个字段: id 和 nick_name)。对 nick_name 执行快速排序

  4. 利用排序好的数据,使用主键 id 再次回表取其他字段,将结果返回

注意:该步骤 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;

优先队列进行排序的流程:

  1. 在所有待排序的数据,取数量为 LIMIT (本例中为 3)的数据,构建一个堆

  2. 不断地取下一行数据,更新堆节点

  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 总是使用 「“最快”」 的排序方案:

  • 当排序数据量不超过 sort buffer 容量时,MySQL 将会在内存使用快速排序算法进行排序(内部排序);当排序数据量超过 sort buffer 容量时,MySQL 将会借助临时磁盘文件使用归并排序算法进行排序(外部排序)

  • 在进行真正排序时,MySQL 会根据数据判断单行长度是否超过 max_length_for_sort_data而决定使用 rowId 排序还是全字段排序,优先选择全字段排序,以减少回表次数

  • 当需要借助临时表的时候,MySQL 会优先使用内存临时表(此时表引擎为 memory 引擎),回内存临时表取数据并不涉及随机读,也不涉及扫描行,效率较高。所以在配合内存临时表的时候,会使用 rowId 排序方式;当内存临时表大小超过 tmp_table_size 限制时,则需要将内存临时表转换为磁盘临时表,这时候由于回表意味着随机读,所以会搭配全字段排序方式

原文链接: https://mp.weixin.qq.com/s/hFkN8XpGA6mZfQtszZMu3w

 

 如果本文对你有帮助的话,麻烦点赞关注支持一下