• 进入"运维那点事"后,希望您第一件事就是阅读“关于”栏目,仔细阅读“关于Ctrl+c问题”,不希望误会!

MySQL查询优化:ORDER BY

MySQL SQL 彭东稳 7年前 (2017-06-13) 21040次浏览 已收录 0个评论

通常我们通过explain查看MySQL执行计划时,经常会看到在Extra列中显示Using filesort。其实这种情况就说明MySQL使用了排序。Using filesort经常出现在order by、group by、distinct、join查询等情况下。

一、使用索引来满足ORDER BY

为了优化SQL语句的排序性能,最好的情况是避免排序,合理利用索引是一个不错的方法,因为索引本身也是有序的,如果在需要排序的字段上面建立了合适的索引,那么就可以跳过排序的过程,提高SQL的查询速度。下面我通过一些典型的SQL来说明哪些SQL可以利用索引减少排序,哪些SQL不能。

假设t1表存在索引:idx_k_c(k,c),idx_pad(pad)

1. 可以利用索引避免排序的SQL

ORDER BY的索引优化

WHERE + ORDER BY的索引优化

2. 不能利用索引避免排序的SQL

当你逻辑表达式为OR时,使用索引排序会丢失:

这可以通过使用UNION来解决:

我们要注意的是:

  • MySQL一次查询只能使用一个索引,如果要对多个字段使用索引,建立复合索引。
  • 在ORDER BY操作中,MySQL只有在排序条件不是一个查询条件表达式的情况下才使用索引。

另外,重点说一下下面两个SQL,一个可以走索引排序,一个不可以走索引排序:

主要区别索引k是不是等于,我们发现k条件是等于时order by c就可以走索引排序,k条件不是等于时order by c就不能走索引排序。这个主要跟组合索引的数据分布规则有关。在MySQL中,组合索引的第一个字段一定是升序的,而第二个字段就不一定了。所以当k>591670 order by c desc时就需要额外的排序动作。

看一下组合索引的规则就明白了为什么会这样,提供下面一些数据:

如果给a,b添加一个组合索引,那么这个组合索引的数据分布规则其实就是select a,b from t1 order by a,b的结果,如下:

第一列a肯定是排序好的(默认是升序),而第二个字段b其实就不是排序的了。但是如果a字段有相同的值时,那么b字段就是排序的了。明白了这个其实就很好明白上面的两条SQL了,为什么k=?时可以使用到索引排序,而k>?时无法使用到索引排序了。

二、排序实现的算法

对于不能利用索引避免排序的SQL,数据库不得不自己实现排序功能以满足用户需求,此时SQL的执行计划中会出现“Using filesort”,这里需要注意的是filesort并不意味着就是文件排序,其实也有可能是内存排序,这个主要由sort_buffer_size参数与结果集大小确定。

MySQL内部实现排序主要有3种方式:原始排序算法(回表排序),优化后的排序算法(不回表排序)和优先队列排序算法;主要涉及3种排序算法:快速排序、归并排序和堆排序。

  • 原始排序算法(回表排序算法)

原始filesort算法的工作原理如下:

1)根据索引或者全表扫描,按照过滤条件获得需要查询的排序字段值和row ID;

2)将要排序字段值和row ID组成键值对,存入sort buffer中;是一对元组;

3)如果sort buffer内存大于这些键值对的内存,就不需要创建临时文件了。否则,每次sort buffer填满以后,需要直接用qsort(快速排序算法)在内存中排好序,并写到临时文件中;

4)重复上述步骤,直到所有的行数据都正常读取了完成;

5)若排序中产生了临时文件,需要利用磁盘外部排序,将row ID写入到结果文件中;

6)根据结果文件中的row ID按序读取用户需要返回的数据。由于row ID不是顺序的,导致回表时是随机IO,为了进一步优化性能(变成顺序IO),MySQL会读一批row ID,并将读到的数据按排序字段顺序插入缓存区中(内存大小read_rnd_buffer_size)。然后有序去取记录,将随机IO转为顺序IO,将获取的结果集返回给用户。

从上述流程来看,是否使用文件排序主要看sort buffer是否能容下需要排序的的结果集,这个buffer的大小由sort_buffer_size参数控制。此外一次排序还需要两次IO,一次是取排序字段+row ID到sort buffer中,第二次是通过上面取出的row ID回表取其他所需要返回的列。由于返回的结果集是按排序字段排序,因此row ID是乱序的,通过乱序的row ID回表取数据时会产生大量的随机IO,所以对于回表取数据MySQL本身会优化,即在取之前先将row ID排序,并放入缓冲区,这个缓存区大小由参数read_rnd_buffer_size控制,然后有序去取记录,将随机IO转为顺序IO。这就是最原始的排序算法了。

  • 优化后的排序算法(不回表排序)

1)根据索引或者全表扫描,按照过滤条件获得需要查询的数据;

2)将要排序的列值和用户需要返回的字段组成键值对,存入sort buffer中;

3)如果sort buffer内存大于这些键值对的内存,就不需要创建临时文件了。否则,每次sort buffer填满以后,需要直接用qsort(快速排序算法)在内存中排好序,并写到临时文件中;

4)重复上述步骤,直到所有的行数据都正常读取了完成;

5)用到了临时文件的,需要利用磁盘外部排序,将排序后的数据写入到结果文件中;

6)直接从结果文件中返回用户需要的字段数据,而不是根据row ID再次回表查询。

原始排序算法除了排序本身,还需要额外两次IO操作。优化后的排序算法相对于原始排序算法减少了第二次IO操作。主要区别在于,优化后的排序算法一次性取出SQL中出现的所有字段并放入sort buffer中,而不是只取排序需要的字段和row ID。由于sort buffer中包含了查询需要的所有字段,因此排序完成后可以直接返回,无需二次回表。这种方式的代价在于,同样大小的sort buffer,能存放的“SQL所有字段”数目要小于“排序字段+row ID”,如果sort buffer不够大,可能导致需要写临时文件,造成额外的IO。当然MySQL提供了参数max_length_for_sort_data,只有当排序SQL里出现的所有字段小于max_length_for_sort_data时,才能利用优化排序方式,否则只能使用原始排序算法。

  • 优先队列排序(内存中排序)

为了得到最终的排序结果,我们都需要将所有满足条件的记录进行排序才能返回。那么相对于优化后的排序算法,是否还有优化空间呢?MySQL 5.6版本开始针对Order by limit M,N语句,在空间层面做了优化,加入了一种新的排序方式–优先队列,类似于FIFO先进先出队列。

算法稍微有点改变,以原始排序(回表排序)模式为例。

sort_buffer_size足够大

如果Limit限制返回N条数据,并且N条数据比sort_buffer_size小,那么MySQL会把sort buffer作为priority queue,在第二步插入priority queue时会按序插入队列;在第三步,队列满了以后,并不会写入外部磁盘文件,而是直接淘汰最尾端的一条数据,直到所有的数据都正常读取完成。

算法如下:

1)根据索引或者全表扫描,按照过滤条件获得需要查询的数据;

2)将要排序的列值和row ID组成键值对,按序存入中priority queue中;

3)如果priority queue满了,直接淘汰最尾端记录;

4)重复上述步骤,直到所有的行数据都正常读取了完成;

5)最后一轮循环,仅将row ID写入到结果文件中;

6)根据结果文件中的row ID按序读取用户需要返回的数据。为了进一步优化性能,MySQL会读一批row ID,并将读到的数据按排序字段要求插入缓存区中(内存大小read_rnd_buffer_size)。

sort_buffer_size不够大

否则,N条数据比sort_buffer_size大的情况下,MySQL无法直接利用sort buffer作为priority queue,正常的文件外部排序还是一样的,只是在最后返回结果时,只根据N个row ID将数据返回出来。具体的算法就不列举了。

这里MySQL到底是否选择priority queue是在sql/filesort.cc的check_if_pq_applicable()函数中确定的,具体的代码细节这里就不展开了。

另外,我们也没有讨论Limit m,n的情况,如果是Limit m,n,上面对应的“N个row ID”就是“M+N个row ID”了,MySQL的Limit m,n其实是取m+n行数据,最后把M条数据丢掉。从上面我们也可以看到sort_buffer_size足够大对Limit数据比较小的情况,优化效果是很明显的。

这种方式采用堆排序实现。堆排序算法特征正好可以解limit这类排序的问题,虽然仍然需要所有字段参与排序,但是只需要M+N个元组的sort buffer空间即可,对于M,N很小的场景,基本不会因为sort buffer不够而导致需要临时文件进行归并排序的问题。对于升序,采用大顶堆,最终堆中的元素组成了最小的N个元素,对于降序,采用小顶堆,最终堆中的元素组成了最大的N的元素。

三、文件排序算法比较

优化器通常选择使用优化后的排序算法,但除了列BLOB或TEXT列之外,在这种情况下它使用原始排序算法。第二种模式是第一种模式的改进,避免了二次回表,采用的是用空间换时间的方法。但是由于sort buffer就那么大,如果用户要查询的数据非常大的话,很多时间浪费在多次磁盘外部排序,导致更多的IO操作,效率可能还不如第一种方式。

所以,MySQL给用户提供了一个max_length_for_sort_data的参数。当“排序的键值对大小” > max_length_for_sort_data时,MySQL认为磁盘外部排序的IO效率不如回表的效率,会选择第一种排序模式;反之,会选择第二种不回表的模式。

假设一个表t1有四个VARCHAR列a,b,c和d,使用filesort查询:

该查询按照a和b,但返回所有列,因此查询所引用的列是a,b,c和d。根据该filesort算法优化选择,查询的执行过程如下:

对于原始算法,sort buffer元组具有以下内容:

优化程序对固定大小值进行排序。排序后, 优化器将按顺序读取元组, 并使用每个元数据中的row ID从t1中读取行以获取选择列表列值。

对于优化排序算法,排序缓冲区元组具有以下内容:

优化程序对固定大小值进行排序。排序后, 优化器将按顺序读取元组, 并使用a、b、c和d的值来获取选择列表列值, 而无需再次读取t1。

对于优化后的算法,排序缓冲区元组具有以下内容:

如果a、b、c或d的任何一个为null,则它们在排序缓冲区中不带空格,而不是在位掩码中。

优化程序对固定大小值进行排序。排序后,优化器将按顺序读取元组,并使用a、b、c和d的值来获取选择列表列值, 而无需再次读取t1。

四、外部排序

1. 两路外部排序

我们先来看一下最简单,最普遍的两路外部排序算法。假设内存只有100M,但是排序的数据有900M,那么对应的外部排序算法如下:

1)从要排序的900M数据中读取100MB数据到内存中,并按照传统的内部排序算法(快速排序)进行排序;

2)将排序好的数据写入磁盘;

3)重复1,2两步,直到每个100MB chunk大小排序好的数据都被写入磁盘;

4)每次读取排序好的chunk中前10MB(= 100MB / (9 chunks + 1))数据,一共9个chunk需要90MB,剩下的10MB作为输出缓存;

5)对这些数据进行一个“9路归并”,并将结果写入输出缓存。如果输出缓存满了,则直接写入最终排序结果文件并清空输出缓存;如果9个10MB的输入缓存空了,从对应的文件再读10MB的数据,直到读完整个文件。最终输出的排序结果文件就是900MB排好序的数据了。

2. 多路外部排序

上述排序算法是一个两路排序算法(先排序,后归并)。但是这种算法有一个问题,假设要排序的数据是50GB而内存只有100MB,那么每次从500个排序好的分片中取200KB(100MB / 501 约等于200KB)就是很多个随机IO,效率非常慢,对应可以这样来改进:

1)从要排序的50GB数据中读取100MB数据到内存中,并按照传统的内部排序算法(快速排序)进行排序;

2)将排序好的数据写入磁盘;

3)重复1,2两步,直到每个100MB chunk大小排序好的数据都被写入磁盘;

4)每次取25个分片进行归并排序,这样就形成了20个(500/25=20)更大的2.5GB有序的文件;

5)对这20个2.5GB的有序文件进行归并排序,形成最终排序结果文件。

对应的数据量更大的情况可以进行更多次归并。

3. sort_merge_passes

MySQL手册中并没有把sort_merge_passes到底是什么,该值比较大时说明了什么,通过什么方式可以缓解这个问题说明。

我们把上面MySQL的外部排序算法搞清楚了,这个问题就清楚了。

其实sort_merge_passes对应的就是MySQL做归并排序的次数,也就是说,如果sort_merge_passes值比较大,说明sort_buffer和要排序的数据差距越大,我们可以通过增大sort_buffer_size或者让填入sort_buffer_size的键值对更小来缓解sort_merge_passes归并排序的次数。

五、优化ORDER BY

  • 使用索引来优化或者避免排序。
  • 排序和查询的字段尽量少。只查询你用到的字段,不要使用select *;使用Limit查询必要的行数据,这样会使用优先队列排序。
  • 对于未使用优化后的排序算法的语句,请尝试将max_length_for_sort_data值增大,触发使用优化后的排序算法。
  • tmpdir建议独立存放,放在高速存储设备上。
  • 要提高ORDER BY速度,请检查是否可以让MySQL使用索引而不是额外的排序阶段。如果不可能,您可以尝试以下策略:
  • 增加sort_buffer_size变量值,避免磁盘排序。理想情况下,该值应足够大,以使整个结果集适合于排序缓冲区 (以避免写入磁盘和合并传递),至少该值必须足够容纳十五个元组。
  • 考虑到存储在排序缓冲区中的列值的大小受max_sort_length系统变量值的影响。例如,如果元组存储长字符串列的值,并且您增加了max_sort_length的值,则排序缓冲区元组的大小也会增加,并且可能要求您增加sort_buffer_size。对于作为字符串表达式的结果计算的列值 (如调用字符串值函数的),filesort算法无法判断表达式值的最大长度,因此它必须为每个元组分配max_sort_length字节。
  • 增加read_rnd_buffer_size变量值。
  • 每行使用较少的内存,只需声明列大小,因为它们需要保存存储在其中的值。例如,如果值从不超过16个字符,则char(16)比char(200)好。
  • 监控Sort_merge_passes状态变量。sort_merge_passes对应的就是MySQL做归并排序的次数,也就是说,如果sort_merge_passes值比较大,说明sort_buffer和要排序的数据差距越大,我们可以通过增大sort_buffer_size或者让填入sort_buffer_size的键值对更小来缓解sort_merge_passes归并排序的次数。

注意:Using where; Using temporary; Using filesort和Using where; Using temporary这两种情况,解说如下:

Using where; Using temporary; Using filesort:表示进行关联查询时(MySQL中关联查询的概念要更宽泛,不仅仅指两张表的关联才叫关联查询),使用了临时表,并在生成临时表后,又进行了文件排序。而Using where; Using temporary表示,仅仅生成了临时表,而没有进行文件排序(在生成临时表的时候已经排序完毕了)。

有人可能注意了:什么时候会Using temporary,比如 group by 的时候就会创建临时表,而且group by一定包含了排序,因此,当group by字段和查询的字段和order by的字段都是同一个字段时,那么就会发生explain的Extra列就会出现:Using where; Using temporary(使用了临时表,而且使用了索引排序,而不是文件排序(filesort)。

六、ORDER BY执行计划信息

用EXPLAIN SELECT … ORDER BY,你可以检查MySQL是否可以使用索引来解决查询。如果你在Extra列中看到Using filesort,说明不能使用索引排序 。Filesort使用类似于MEMORY存储引擎所使用的固定长度的行存储格式,诸如VARCHAR使用固定长度存储的可变长度类型 。

另外,如果使用优化器跟踪输出会包含一个filesort_summary模块。例如:

该sort_mode值提供有关使用的filesort算法以及排序缓冲区中的元组内容的信息:

<sort_key, rowid>:这表示使用原始排序算法。排序缓冲区元组是包含原始表行的排序键值和row ID的对,元组按排序键值排序,row ID用于读取表中的行。

<sort_key, additional_fields>:这表示使用优化后的排序算法。排序缓冲区元组包含查询引用的排序键值和列,元组按排序键值排序,列值直接从元组中读取。

<sort_key, packed_additional_fields>:这表示使用优化后的排序算法。排序缓冲区元组包含查询引用的排序键值和打包列,元组按排序键值排序,列值直接从元组中读取。

EXPLAIN不区分ORDER BY是使用优化后的排序算法还是内存排序(优先队列)算法,但在优化器跟踪输出中可以看到,如果存在内存排序算法,则会存在”filesort_priority_queue_optimization”模块。

有关优化器跟踪的信息,请参阅MySQL内部:跟踪优化器初识MySQL 5.6的optimizer trace

七、补充

假设一个表t1有一个主键id,以及a、b字段;a字段有一个idx_a索引,b字段有一个idx_b字段。下面进行如下查询:

因为经常看见有人这么写查询语句,其实这个ORDER BY id是不需要的,除非是想降序需要添加ORDER BY id DESC。大致原因就是 a 字段已经有了索引,并且是“=”查询,所以查出来的结果必然是顺序的(索引默认是升序的)。又由于InnoDB数据组织方式是根据主键排序的,所以a = ‘xxx’的查询结果必然是根据主键排序的。

大概的数据插入及查询转换如下:

比如查询a = 2,那么查询出来的数据就是根据id升序的。

如果把ORDER BY变成b字段呢?

由于b不是主键,所以需要排序操作。

另外即使采用的是InnoDB存储引擎表,对于没有使用ORDER BY子句的选择查询,其结果也可能不会是按照主键顺序进行排序的。因为没有ORDER BY子句的查询只代表从集合中查询数据,而集合是没有顺序概念的。因此要牢记,不要为表中的行假定任何特定的顺序。就是说,在实际使用环境中,如果确实需要有序输出行记录,则必须使用ORDER BY子句。当然,排序需要成本,可以通过变量来查看数据库的排序操作。示例如下:

其中Sort_scan为1,Sort_rows为7,表示进行了一次排序扫描操作,工排序了7条数据。在实际的生成环境中,需要观察这些变量,判断是否可以通过添加索引来避免额外的排序开销。

<参考>

MySQL:排序(filesort)详细解析

https://dev.mysql.com/doc/refman/5.7/en/order-by-optimization.html


如果您觉得本站对你有帮助,那么可以支付宝扫码捐助以帮助本站更好地发展,在此谢过。
喜欢 (2)
[资助本站您就扫码 谢谢]
分享 (0)

您必须 登录 才能发表评论!