MySQL技术|MySQL排序1 2 3

MySQL排序其实是一个老生长谈的问题了,但是我们这次想由浅入深详细的说说MySQL排序模式,怎么影响MySQL选择不同的排序模式和怎么优化排序。

警示:不好意思,我们太想把排序的前前后后说清楚了,导致这是一篇长文!

我们要解决什么问题

MySQL排序其实是一个老生长谈的问题了,但是我们这次想由浅入深详细的说说MySQL排序模式,怎么影响MySQL选择不同的排序模式和怎么优化排序。

也希望通过这篇文章解决大家的以下疑问:

  1. MySQL在哪些地方会使用排序,怎么判断MySQL使用了排序

  2. MySQL有几种排序模式,我们可以通过什么方法让MySQL选择不同的排序模式

  3. MySQL排序跟read_rnd_buffer_size 有啥关系,在哪些情况下增加read_rnd_buffer_size能优化排序

  4. 怎么判断MySQL使用到了磁盘来排序,怎么避免或者优化磁盘排序

  5. 排序时变长字段(varchar)数据在内存是怎么存储的,5.7有哪些改进

  6. 在limit情况下,排序模式有哪些改进

  7. sort_merge_pass到底是什么鬼,该状态值过大说明了什么问题,可以通过什么方法解决

  8. 最后MySQL使用到了排序的话,依次可以通过什么办法分析和优化让排序更快

排序,排序,排序

我们通过explain查看MySQL执行计划的时候,经常会看到在Extra列中显示Using filesort。
其实这种情况就说明MySQL就使用了排序。

Using filesort经常出现在order by、group by、distinct、join等情况下。

索引优化排序

看到排序,我们的DBA首先想到的肯定是,是否可以利用索引来优化。

INNODB默认采用的是B tree索引,B tree索引本身就是有序的,如果有一个查询如下

1.  select * from film where actor_name='苍老师' order by prod_time;

那么只需要加一个(name,prod_time)的索引就能够利用B tree的特性来避免额外排序。
如下图所示:

通过B-tree查找到actor_name=’苍老师’演员为苍老师的数据以后,只需要按序往右查找就可以了,不需要额外排序操作。

对应的哪些可以利用索引优化排序的列举如下:

1.  SELECT * FROM t1
2.    ORDER BY key_part1,key_part2,... ;
3.  
4.  SELECT * FROM t1
5.    WHERE key_part1 = constant
6.    ORDER BY key_part2;
7.  
8.  SELECT * FROM t1
9.    ORDER BY key_part1 DESC, key_part2 DESC;
10. 
11. SELECT * FROM t1
12.   WHERE key_part1 = 1
13.   ORDER BY key_part1 DESC, key_part2 DESC;
14. 
15. SELECT * FROM t1
16.   WHERE key_part1 > constant
17.   ORDER BY key_part1 ASC;
18. 
19. SELECT * FROM t1
20.   WHERE key_part1 < constant
21.   ORDER BY key_part1 DESC;
22. 
23. SELECT * FROM t1
24.   WHERE key_part1 = constant1 AND key_part2 > constant2
25.   ORDER BY key_part2;

从以上例子里面我们也可以看到,如果要让MySQL使用索引优化排序应该怎么建组合索引。

排序模式

实际trace结果

但是还是有非常多的SQL没法使用索引进行排序,例如

1.  select * from film where Producer like '东京热%'  and prod_time>'2015-12-01' order by actor_age;

我们想查询’东京热’出品的,从去年12月1号以来,并且按照演员的年龄排序的电影信息。
(好吧,假设我这里有一个每一位男DBA都想维护的数据库:)

这种情况下,使用索引已经无法避免排序了,那MySQL排序到底会怎么做呢?

笼统的来说,它会按照:

  1. 依据“Producer like ‘东京热%’ and prod_time>’2015-12-01’ ”过滤数据,查找需要的数据
  2. 对查找到的数据按照“order by actor_age”进行排序,并 按照“select *”将必要的数据按照actor_age依序返回给客户端

空口无凭,我们可以利用MySQL的optimize trace来查看是否如上所述。

如果通过optimize trace看到更详细的MySQL优化器trace信息,
可以查看阿里印风的博客初识5.6的optimizer trace
trace结果如下:

•   依据“Producer like ‘东京热%’ and prod_time>’2015-12-01’ ”过滤数据,查找需要的数据
1.              "attaching_conditions_to_tables": {
2.                "original_condition": "((`film`.`Producer` like '东京热%') and (`film`.`prod_time` > '2015-12-01'))",
3.                "attached_conditions_computation": [
4.                ],
5.                "attached_conditions_summary": [
6.                  {
7.                    "table": "`film`",
8.                    "attached": "((`film`.`Producer` like '东京热%') and (`film`.`prod_time` > '2015-12-01'))"
9.                  }
10.               ]
11.             }

• 对查找到的数据按照“order by actor_age”进行排序,并 按照“select *”将必要的数据按照actor_age依序返回给客户端

1.        "join_execution": {
2.          "select#": 1,
3.          "steps": [
4.            {
5.              "filesort_information": [
6.                {
7.                  "direction": "asc",
8.                  "table": "`film`",
9.                  "field": "actor_age"
10.               }
11.             ],
12.             "filesort_priority_queue_optimization": {
13.               "usable": false,
14.               "cause": "not applicable (no LIMIT)"
15.             },
16.             "filesort_execution": [
17.             ],
18.             "filesort_summary": {
19.               "rows": 1,
20.               "examined_rows": 5,
21.               "number_of_tmp_files": 0,
22.               "sort_buffer_size": 261872,
23.               "sort_mode": "<sort_key, packed_additional_fields>"
24.             }
25.           }
26.         ]
27.       }

这里,我们可以明显看到,MySQL在执行这个select的时候执行了针对film表.actor_age字段的asc排序操作。

1.  "filesort_information": [
2.                {
3.                  "direction": "asc",
4.                  "table": "`film`",
5.                  "field": "actor_age"
6.                }

排序模式概览
我们这里主要关心MySQL到底是怎么排序的,采用了什么排序算法。
请关注这里

1.                "sort_mode": "<sort_key, packed_additional_fields>"
MySQL的sort_mode有三种 
摘录5.7.13中sql/filesort.cc源码如下:
1.    Opt_trace_object(trace, "filesort_summary")
2.      .add("rows", num_rows)
3.      .add("examined_rows", param.examined_rows)
4.      .add("number_of_tmp_files", num_chunks)
5.      .add("sort_buffer_size", table_sort.sort_buffer_size())
6.      .add_alnum("sort_mode",
7.                 param.using_packed_addons() ?
8.                 "<sort_key, packed_additional_fields>" :
9.                 param.using_addon_fields() ?
10.                "<sort_key, additional_fields>" : "<sort_key, rowid>");
“< sort_key, rowid >”和”< sort_key, additional_fields >” 

看过其他介绍介绍MySQL排序文章的同学应该比较清楚,相对较新。

• 对应的是MySQL 4.1之前的“原始排序模式”
• 对应的是MySQL 4.1以后引入的“修改后排序模式”
• 是MySQL 5.7.3以后引入的进一步优化的”打包数据排序模式”

下面我们来一一介绍这三个模式:

回表排序模式

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

• 将要排序的列值和row ID组成键值对,存入sort buffer中

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

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

• sort buffer装不下临时文件的,需要利用磁盘外部排序,将row id写入到结果文件中

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

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

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

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

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

• sort buffer装不下临时文件的,需要利用磁盘外部排序,将排序后的数据写入到结果文件中

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

打包数据排序模式

第三种排序模式的改进仅仅在于将char和varchar字段存到sort buffer中时,更加紧缩。在之前的两种模式中,存储了”yes”3个字符的定义为VARCHAR(255)的列会在内存中申请255个字符内存空间,但是5.7.3改进后,只需要存储2个字节的字段长度和3个字符内存空间(用于保存”yes”这三个字符)就够了,内存空间整整压缩了50多倍。可以让更多的键值对保存在sort buffer中。

三种模式比较

第二种模式是第一种模式的改进,避免了二次回表,采用的是用空间换时间的方法。但是由于sort buffer就那么大,如果用户要查询的数据非常大的话,很多时间浪费在多次磁盘外部排序,导致更多的IO操作,效率可能还不如第一种方式。所以,MySQL给用户提供了一个max_length_for_sort_data的参数。当排序的键值对大小 > max_length_for_sort_data时,认为磁盘外部排序的IO效率不如回表的效率,会选择第一种;反之,会选择第二种不回表的方式。

第三种模式主要是解决字符数据存储空间浪费的问题,对于实际数据不多,但是字段定义较长的改进效果会更加明显。

能看到这里的同学绝逼是真爱,但是还没完,后面的东西可能会更烧脑…

建议大家喝杯咖啡再继续看

很多文章写到这里可能就差不多了,但是大家忘记关注一个问题了:“如果排序的数据不能完全放在sort buffer内存里面,是怎么通过外部排序完成整个排序过程的列?”

要解决这个问题,我们首先需要简单查看一下外部排序到底是怎么做的。

外部排序

普通外部排序

两路外部排序

我们先来看一下最简单,最普遍的两路外部排序算法。

假设内存只有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排好序的数据了

多路外部排序

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

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

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

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

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

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

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

MySQL外部排序

MySQL外部排序算法

那MySQL使用的外部排序是怎么样的列,我们以回表排序模式为例:

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

  2. 将要排序的列值和row ID组成键值对,存入sort buffer中

  3. 如果sort buffer内存大于这些键值对的内存,就不需要创建临时文件了。否则,每次sort buffer填满以后,需要直接用qsort(快速排序模式)在内存中排好序,作为一个block写到临时文件中。跟正常的外部排序写到多个文件中不一样,MySQL只会写到一个临时文件中,并通过保存文件偏移量的方式来模拟多个文件归并排序。

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

  5. 每MERGEBUFF (7) 个block抽取一批数据进行排序,归并排序到另外一个临时文件中,直到所有的数据都排序好到新的临时文件中

  6. 重复以上归并排序过程,直到剩下不到MERGEBUFF2 (15)个block。
    通俗一点解释:
    第一次循环中,一个block对应一个sort buffer(大小为sort_buffer_size)排序好的数据;每7个做一个归并。
    第二次循环中,一个block对应MERGEBUFF (7) 个sort buffer的数据,每7个做一个归并。
    … 直到所有的block数量小于MERGEBUFF2 (15)。

  7. 最后一轮循环,仅将row ID写入到结果文件中

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

这里我们需要注意的是:

  1. MySQL把外部排序好的分片写入同一个文件中,通过保存文件偏移量的方式来区别各个分片位置

  2. MySQL每MERGEBUFF (7)个分片做一个归并,最终分片数达到MERGEBUFF2 (15)时,做最后一次归并。这两个值都写死在代码中了…

sort_merge_passes

MySQL手册中对Sort_merge_passes的描述只有一句话

  1. Sort_merge_passes

  2. The number of merge passes that the sort algorithm has had to do. If this value is large, you should consider increasing the value of the sort_buffer_size system variable.

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

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

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

对应的,我们可以在源码中看到证据。

上述MySQL外部排序的算法中第5到第7步,是通过sql/filesort.cc文件中merge_many_buff()函数来实现,第5步单次归并使用merge_buffers()实现,源码摘录如下:

1.  int merge_many_buff(Sort_param *param, Sort_buffer sort_buffer,
2.                      Merge_chunk_array chunk_array,
3.                      size_t *p_num_chunks, IO_CACHE *t_file)
4.  {
5.  ...
6.  
7.      for (i=0 ; i < num_chunks - MERGEBUFF * 3 / 2 ; i+= MERGEBUFF)
8.      {
9.        if (merge_buffers(param,                  // param
10.                         from_file,              // from_file
11.                         to_file,                // to_file
12.                         sort_buffer,            // sort_buffer
13.                         last_chunk++,           // last_chunk [out]
14.                         Merge_chunk_array(&chunk_array[i], MERGEBUFF),
15.                         0))                     // flag
16.       goto cleanup;
17.     }
18.     if (merge_buffers(param,
19.                       from_file,
20.                       to_file,
21.                       sort_buffer,
22.                       last_chunk++,
23.                       Merge_chunk_array(&chunk_array[i], num_chunks - i),
24.                       0))
25.       break;                                    /* purecov: inspected */
26. ...
27. }

截取部分merge_buffers()的代码如下,

1.  
2.  int merge_buffers(Sort_param *param, IO_CACHE *from_file,
3.                    IO_CACHE *to_file, Sort_buffer sort_buffer,
4.                    Merge_chunk *last_chunk,
5.                    Merge_chunk_array chunk_array,
6.                    int flag)
7.  {
8.  ...
9.    current_thd->inc_status_sort_merge_passes();
10. ...
11. }

可以看到每个merge_buffers()都会增加sort_merge_passes,也就是说每一次对MERGEBUFF (7) 个block归并排序都会让sort_merge_passes加一,sort_merge_passes越多表示排序的数据太多,需要多次merge pass。解决的方案无非就是缩减要排序数据的大小或者增加sort_buffer_size。

打个小广告,在我们的qmonitor中就有sort_merge_pass的性能指标和参数值过大的报警设置。

trace 结果解释

说明白了三种排序模式和外部排序的方法,我们回过头来看一下trace的结果。

  1. "number_of_tmp_files": 0,
    number_of_tmp_files表示有多少个分片,如果number_of_tmp_files不等于0,表示一个sort_buffer_size大小的内存无法保存所有的键值对,也就是说,MySQL在排序中使用到了磁盘来排序。

由于我们的这个SQL里面没有对数据进行分页限制,所以filesort_priority_queue_optimization并没有启用

1.  "filesort_priority_queue_optimization": {
2.                "usable": false,
3.                "cause": "not applicable (no LIMIT)"
4.              },

而正常情况下,使用了Limit会启用优先队列的优化。优先队列类似于FIFO先进先出队列。

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

如果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)。

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

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

MySQL其他相关排序参数

max_sort_length

这里需要区别max_sort_length 和max_length_for_sort_data。max_length_for_sort_data是为了让MySQL选择”< sort_key, rowid >”还是”< sort_key, additional_fields >”的模式。而max_sort_length是键值对的大小无法确定时(比如用户要查询的数据包含了 SUBSTRING_INDEX(col1, ‘.’,2))MySQL会对每个键值对分配max_sort_length个字节的内存,这样导致内存空间浪费,磁盘外部排序次数过多。

innodb_disable_sort_file_cache

innodb_disable_sort_file_cache设置为ON的话,表示在排序中生成的临时文件不会用到文件系统的缓存,类似于O_DIRECT打开文件。

innodb_sort_buffer_size

这个参数其实跟我们这里讨论的SQL排序没有什么关系。innodb_sort_buffer_size设置的是在创建InnoDB 索引时,使用到的sort buffer的大小。

以前写死为1M,现在开放出来,可以设置这个参数了。

MySQL排序优化总结

最后整理一下优化MySQL排序的手段

  1. 排序和查询的字段尽量少。只查询你用到的字段,不要使用select * ;使用limit查询必要的行数据

  2. 要排序或者查询的字段,尽量不要用不确定字符函数,避免MySQL直接分配max_sort_length,导致sort buffer空间不足

  3. 使用索引来优化或者避免排序

  4. 增加sort_buffer_size大小,避免磁盘排序

  5. 不得不使用original 排序算法时,增加read_rnd_buffer_size

  6. 字段长度定义合适就好(避免过长)

  7. tmpdir建议独立存放,放在高速存储设备上

写到这里,大家可以回顾一下文章开头的那八个问题,如果回答不了这些问题,说明其实你没有真正的理解透MySQL的排序,或者说我们的这篇文章写的太烂了:)

是不是感觉累觉不爱了,我们的文章也终于要结束了,引用一个图片作为文章的结尾,向Christophe致敬。当下次其他同学问你,MySQL的排序到底是怎么做的,你可以告诉他这是一个:

http://coding-geek.com/wp-content/uploads/2015/08/magic_low2.gif

参考文献

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

How does a relational database work

发表评论

电子邮件地址不会被公开。 必填项已用*标注