MySQL排序原理

青旅半醒 2024-02-18 22:09 6阅读 0赞

【**目录**】

一、解决什么问题  
二、排序  
三、索引优化排序  
四、排序模式  
五、外部排序  
六、trace结果解释  
七、MySQL其他相关排序参数  
八、MySQL排序优化总结  
九、案例

### 一、解决什么问题 ###

由浅入深详细说说MySQL排序模式，怎么影响MySQL选择不同的排序模式和怎么优化排序。

排序是数据库中的一个基本功能，MySQL也不例外。用户通过Order by语句即能达到将指定的结果集排序的目的，其实不仅仅是Order by语句，Group by语句，Distinct语句都会隐含使用排序。本文首先会简单介绍SQL如何利用索引避免排序代价，然后会介绍MySQL实现排序的内部原理。

解决大家的以下疑问：

1.  MySQL在哪些地方会使用排序，怎么判断MySQL使用了排序；
2.  MySQL有几种排序模式，通过什么方法让MySQL选择不同的排序模式；
3.  MySQL排序跟`read_rnd_buffer_size`有啥关系，在哪些情况下增加`read_rnd_buffer_size`能优化排序；
4.  怎么判断MySQL使用到了磁盘来排序，怎么避免或者优化磁盘排序；
5.  排序时变长字段（varchar）数据在内存是怎么存储的，5.7有哪些改进；
6.  在情况下，排序模式有哪些改进；
7.  `sort_merge_pass`到底是什么 ，该状态值过大说明了什么问题，可以通过什么方法解决；
8.  MySQL使用到了排序的话，依次可以通过什么办法分析和优化让排序更快？

### 二、排序 ###

我们通过explain查看MySQL执行计划时，经常会看到在Extra列中显示Using filesort。

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

其实这种情况就说明MySQL使用了排序。Using filesort经常出现在order by、group by、distinct、join等情况下。

MySQL内部实现排序主要有3种方式，常规排序，优化排序和优先队列排序，主要涉及3种排序算法：快速排序、归并排序和堆排序。假设表结构和SQL语句如下：

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> <p>2</p> </td> 
   <td> <p><code>CREATE</code> <code>TABLE</code> <code>t1(id </code><code>int</code><code>, col1 </code><code>varchar</code><code>(64), col2 </code><code>varchar</code><code>(64), col3 </code><code>varchar</code><code>(64), </code><code>PRIMARY</code> <code>KEY</code><code>(id),</code><code>key</code><code>(col1,col2));</code></p> <p><code>SELECT</code> <code>col1,col2,col3 </code><code>FROM</code> <code>t1 </code><code>WHERE</code> <code>col1&gt;100 </code><code>ORDER</code> <code>BY</code> <code>col2;</code></p> </td> 
  </tr> 
 </tbody> 
</table>

a.常规排序  
(1).从表t1中获取满足WHERE条件的记录  
(2).对于每条记录，将记录的主键+排序键(id,col2)取出放入sort buffer  
(3).如果sort buffer可以存放所有满足条件的(id,col2)对，则进行排序；否则sort buffer满后，进行排序并固化到临时文件中。(排序算法采用的是快速排序算法)  
(4).若排序中产生了临时文件，需要利用归并排序算法，保证临时文件中记录是有序的  
(5).循环执行上述过程，直到所有满足条件的记录全部参与排序  
(6).扫描排好序的(id,col2)对，并利用id去捞取SELECT需要返回的列(col1,col2,col3)  
(7).将获取的结果集返回给用户。  
从上述流程来看，是否使用文件排序主要看sort buffer是否能容下需要排序的(id,col2)对，这个buffer的大小由sort\_buffer\_size参数控制。此外一次排序需要两次IO，一次是捞(id,col2),第二次是捞(col1,col2,col3)，由于返回的结果集是按col2排序，因此id是乱序的，通过乱序的id去捞(col1,col2,col3)时会产生大量的随机IO。对于第二次MySQL本身一个优化，即在捞之前首先将id排序，并放入缓冲区，这个缓存区大小由参数read\_rnd\_buffer\_size控制，然后有序去捞记录，将随机IO转为顺序IO。  
b.优化排序  
常规排序方式除了排序本身，还需要额外两次IO。优化的排序方式相对于常规排序，减少了第二次IO。主要区别在于，放入sort buffer不是(id,col2),而是(col1,col2,col3)。由于sort buffer中包含了查询需要的所有字段，因此排序完成后可以直接返回，无需二次捞数据。这种方式的代价在于，同样大小的sort buffer，能存放的(col1,col2,col3)数目要小于(id,col2)，如果sort buffer不够大，可能导致需要写临时文件，造成额外的IO。当然MySQL提供了参数max\_length\_for\_sort\_data，只有当排序元组小于max\_length\_for\_sort\_data时，才能利用优化排序方式，否则只能用常规排序方式。  
c.优先队列排序  
为了得到最终的排序结果，无论怎样，我们都需要将所有满足条件的记录进行排序才能返回。那么相对于优化排序方式，是否还有优化空间呢？5.6版本针对Order by limit M，N语句，在空间层面做了优化，加入了一种新的排序方式--优先队列，这种方式采用堆排序实现。堆排序算法特征正好可以解limit M，N 这类排序的问题，虽然仍然需要所有元素参与排序，但是只需要M+N个元组的sort buffer空间即可，对于M，N很小的场景，基本不会因为sort buffer不够而导致需要临时文件进行归并排序的问题。对于升序，采用大顶堆，最终堆中的元素组成了最小的N个元素，对于降序，采用小顶堆，最终堆中的元素组成了最大的N的元素。

### 三、索引优化排序 ###

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

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

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

那么只需要加一个(`actor_name,prod_time`)的索引就能够利用B tree的特性来避免额外排序。

如下图所示：

![图片描述][20161008142334625]

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

下面我通过一些典型的SQL来说明哪些SQL可以利用索引减少排序，哪些SQL不能。假设t1表存在索引key1(key\_part1,key\_part2),key2(key2)

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

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> <p>2</p> <p>3</p> <p>4</p> </td> 
   <td> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>t1 </code><code>ORDER</code> <code>BY</code> <code>key_part1,key_part2;</code></p> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>t1 </code><code>WHERE</code> <code>key_part1 = constant </code><code>ORDER</code> <code>BY</code> <code>key_part2;</code></p> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>t1 </code><code>WHERE</code> <code>key_part1 &gt; constant </code><code>ORDER</code> <code>BY</code> <code>key_part1 </code><code>ASC</code><code>;</code></p> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>t1 </code><code>WHERE</code> <code>key_part1 = constant1 </code><code>AND</code> <code>key_part2 &gt; constant2 </code><code>ORDER</code> <code>BY</code> <code>key_part2;</code></p> </td> 
  </tr> 
 </tbody> 
</table>

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

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> <p>2</p> <p>3</p> <p>4</p> <p>5</p> <p>6</p> <p>7</p> <p>8</p> <p>9</p> <p>10</p> <p>11</p> </td> 
   <td> <p><code>//排序字段在多个索引中，无法使用索引排序</code></p> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>t1 </code><code>ORDER</code> <code>BY</code> <code>key_part1,key_part2, key2;</code></p> <p><code>&nbsp;</code>&nbsp;</p> <p><code>//排序键顺序与索引中列顺序不一致，无法使用索引排序</code></p> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>t1 </code><code>ORDER</code> <code>BY</code> <code>key_part2, key_part1;</code></p> <p><code>&nbsp;</code>&nbsp;</p> <p><code>//升降序不一致，无法使用索引排序</code></p> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>t1 </code><code>ORDER</code> <code>BY</code> <code>key_part1 </code><code>DESC</code><code>, key_part2 </code><code>ASC</code><code>;</code></p> <p><code>&nbsp;</code>&nbsp;</p> <p><code>//key_part1是范围查询，key_part2无法使用索引排序</code></p> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>t1 </code><code>WHERE</code> <code>key_part1&gt; constant </code><code>ORDER</code> <code>BY</code> <code>key_part2;</code></p> </td> 
  </tr> 
 </tbody> 
</table>

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

### 四、排序模式 ###

#### 4.1 实际trace结果 ####

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

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

我们想查询“东京热”出品的，从去年12月1号以来，并且按照演员的年龄排序的电影信息。

这种情况下，使用索引已经无法避免排序了，那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’`过滤数据，查找需要的数据
    
        "attaching_conditions_to_tables": {
              "original_condition": "((`film`.`Producer` like '东京热%') and (`film`.`prod_time` > '2015-12-01'))",
              "attached_conditions_computation": [
              ],
              "attached_conditions_summary": [
                {
                  "table": "`film`",
                  "attached": "((`film`.`Producer` like '东京热%') and (`film`.`prod_time` > '2015-12-01'))"
                }
              ]
            }
 *  对查找到的数据按照`order by actor_age`进行排序,并按照`select *`将必要的数据按照`actor_age`依序返回给客户端

"join_execution": {
            "select#": 1,
            "steps": [
              {
                "filesort_information": [
                  {
                    "direction": "asc",
                    "table": "`film`",
                    "field": "actor_age"
                  }
                ],
                "filesort_priority_queue_optimization": {
                  "usable": false,
                  "cause": "not applicable (no LIMIT)"
                },
                "filesort_execution": [
                ],
                "filesort_summary": {
                  "rows": 1,
                  "examined_rows": 5,
                  "number_of_tmp_files": 0,
                  "sort_buffer_size": 261872,
                  "sort_mode": "<sort_key, packed_additional_fields>"
                }
              }
            ]
          }

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

"filesort_information": [
                  {
                    "direction": "asc",
                    "table": "`film`",
                    "field": "actor_age"
                  }

#### 4.2 排序模式概览 ####

主要关心MySQL到底是怎么排序的，采用了什么排序算法。

请关注这里

`"sort_mode": "<sort_key, packed_additional_fields>"`

MySQL的sort\_mode有三种。

摘录5.7.13中sql/filesort.cc源码如下：

Opt_trace_object(trace, "filesort_summary")
        .add("rows", num_rows)
        .add("examined_rows", param.examined_rows)
        .add("number_of_tmp_files", num_chunks)
        .add("sort_buffer_size", table_sort.sort_buffer_size())
        .add_alnum("sort_mode",
                   param.using_packed_addons() ?
                   "<sort_key, packed_additional_fields>" :
                   param.using_addon_fields() ?
                   "<sort_key, additional_fields>" : "<sort_key, rowid>");

`< sort_key, rowid >”和“< sort_key, additional_fields >`看过其他介绍介绍MySQL排序文章的同学应该比较清楚，`< sort_key, packed_additional_fields >`相对较新。

*  `< sort_key, rowid >`对应的是MySQL 4.1之前的“原始排序模式”
 *  `< sort_key, additional_fields >`对应的是MySQL 4.1以后引入的“修改后排序模式”
 *  `< sort_key, packed_additional_fields >`是MySQL 5.7.3以后引入的进一步优化的”打包数据排序模式”

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

**4.2.1 回表排序模式**

*  根据索引或者全表扫描，按照过滤条件获得需要查询的排序字段值和row ID；
 *  将要排序字段值和row ID组成键值对，存入sort buffer中；
 *  如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(快速排序算法)在内存中排好序，并写到临时文件中；
 *  重复上述步骤，直到所有的行数据都正常读取了完成；
 *  用到了临时文件的，需要利用磁盘外部排序，将row id写入到结果文件中；
 *  根据结果文件中的row ID按序读取用户需要返回的数据。由于row ID不是顺序的，导致回表时是随机IO，为了进一步优化性能（变成顺序IO），MySQL会读一批row ID，并将读到的数据按排序字段顺序插入缓存区中(内存大小`read_rnd_buffer_size`)。

![图片描述][20161008142357031]

**4.2.2 不回表排序模式**

*  根据索引或者全表扫描，按照过滤条件获得需要查询的数据；
 *  将要排序的列值和**用户需要返回的字段**组成键值对，存入sort buffer中；
 *  如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(快速排序算法)在内存中排好序，并写到临时文件中；
 *  重复上述步骤，直到所有的行数据都正常读取了完成；
 *  用到了临时文件的，需要利用磁盘外部排序，将排序后的数据写入到结果文件中；
 *  直接从结果文件中返回用户需要的字段数据，而不是根据row ID再次回表查询。

![图片描述][20161008142408188]

**4.2.3 打包数据排序模式**

第三种排序模式的改进仅仅在于将char和varchar字段存到sort buffer中时，更加紧缩。

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

**4.2.4 三种模式比较**

第二种模式是第一种模式的改进，避免了二次回表，采用的是用空间换时间的方法。

但是由于sort buffer就那么大，如果用户要查询的数据非常大的话，很多时间浪费在多次磁盘外部排序，导致更多的IO操作，效率可能还不如第一种方式。

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

![图片描述][20161008142418633]

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

关注一个问题了：“如果排序的数据不能完全放在sort buffer内存里面，是怎么通过外部排序完成整个排序过程的呢？”

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

### 五、外部排序 ###

#### 5.1 普通外部排序 ####

**5.1.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排好序的数据了。

![图片描述][20161008142430367]

**5.1.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的有序文件进行归并排序，形成最终排序结果文件。

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

![图片描述][20161008142439321]

#### 5.2 MySQL外部排序 ####

**5.2.1 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)时，做最后一次归并。这两个值都写死在代码中了……

**5.2.2 `sort_merge_passes`**

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

Sort_merge_passes
    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()`实现，源码摘录如下：

int merge_many_buff(Sort_param *param, Sort_buffer sort_buffer,
                        Merge_chunk_array chunk_array,
                        size_t *p_num_chunks, IO_CACHE *t_file)
    {
    ...
    
        for (i=0 ; i < num_chunks - MERGEBUFF * 3 / 2 ; i+= MERGEBUFF)
        {
          if (merge_buffers(param,                  // param
                            from_file,              // from_file
                            to_file,                // to_file
                            sort_buffer,            // sort_buffer
                            last_chunk++,           // last_chunk [out]
                            Merge_chunk_array(&chunk_array[i], MERGEBUFF),
                            0))                     // flag
          goto cleanup;
        }
        if (merge_buffers(param,
                          from_file,
                          to_file,
                          sort_buffer,
                          last_chunk++,
                          Merge_chunk_array(&chunk_array[i], num_chunks - i),
                          0))
          break;                                    /* purecov: inspected */
    ...
    }

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

int merge_buffers(Sort_param *param, IO_CACHE *from_file,
                      IO_CACHE *to_file, Sort_buffer sort_buffer,
                      Merge_chunk *last_chunk,
                      Merge_chunk_array chunk_array,
                      int flag)
    {
    ...
      current_thd->inc_status_sort_merge_passes();
    ...
    }

可以看到：每个`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的结果。

#### 6.1 是否存在磁盘外部排序 ####

`"number_of_tmp_files": 0,`

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

#### 6.2 是否存在优先队列优化排序 ####

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

"filesort_priority_queue_optimization": {
                  "usable": false,
                  "cause": "not applicable (no LIMIT)"
                },

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

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

**`sort_buffer_size`足够大**

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

算法如下：

*  根据索引或者全表扫描，按照过滤条件获得需要查询的数据
 *  将要排序的列值和row ID组成键值对，按序存入中priority queue中
 *  如果priority queue满了，直接淘汰最尾端记录。
 *  重复上述步骤，直到所有的行数据都正常读取了完成
 *  最后一轮循环，仅将row ID写入到结果文件中
 *  根据结果文件中的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数据比较小的情况，优化效果是很明显的。

### 七、MySQL其他相关排序参数 ###

#### 7.1 `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`个字节的内存，这样导致内存空间浪费，磁盘外部排序次数过多。

#### 7.2 `innodb_disable_sort_file_cache` ####

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

#### 7.3 `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建议独立存放，放在高速存储设备上。

九、 案例

**排序不一致问题**

案例1

Mysql从5.5迁移到5.6以后，发现分页出现了重复值。  
测试表与数据：

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> <p>2</p> <p>3</p> <p>4</p> <p>5</p> <p>6</p> <p>7</p> <p>8</p> </td> 
   <td> <p><code>create</code> <code>table</code> <code>t1(id </code><code>int</code> <code>primary</code> <code>key</code><code>, c1 </code><code>int</code><code>, c2 </code><code>varchar</code><code>(128));</code></p> <p><code>insert</code> <code>into</code> <code>t1 </code><code>values</code><code>(1,1,</code><code>'a'</code><code>);</code></p> <p><code>insert</code> <code>into</code> <code>t1 </code><code>values</code><code>(2,2,</code><code>'b'</code><code>);</code></p> <p><code>insert</code> <code>into</code> <code>t1 </code><code>values</code><code>(3,2,</code><code>'c'</code><code>);</code></p> <p><code>insert</code> <code>into</code> <code>t1 </code><code>values</code><code>(4,2,</code><code>'d'</code><code>);</code></p> <p><code>insert</code> <code>into</code> <code>t1 </code><code>values</code><code>(5,3,</code><code>'e'</code><code>);</code></p> <p><code>insert</code> <code>into</code> <code>t1 </code><code>values</code><code>(6,4,</code><code>'f'</code><code>);</code></p> <p><code>insert</code> <code>into</code> <code>t1 </code><code>values</code><code>(7,5,</code><code>'g'</code><code>);</code></p> </td> 
  </tr> 
 </tbody> 
</table>

假设每页3条记录，第一页limit 0,3和第二页limit 3,3查询结果如下：

[![201603220853091.png][]][201603220853091.png]

我们可以看到 id为4的这条记录居然同时出现在两次查询中，这明显是不符合预期的，而且在5.5版本中没有这个问题。产生这个现象的原因就是5.6针对limit M,N的语句采用了优先队列，而优先队列采用堆实现，比如上述的例子order by c1 asc limit 0，3 需要采用大小为3的大顶堆；limit 3，3需要采用大小为6的大顶堆。由于c1为2的记录有3条，而堆排序是非稳定的(对于相同的key值，无法保证排序后与排序前的位置一致)，所以导致分页重复的现象。为了避免这个问题，我们可以在排序中加上唯一值，比如主键id，这样由于id是唯一的，确保参与排序的key值不相同。将SQL写成如下：

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> <p>2</p> </td> 
   <td> <p><code>select</code> <code>* </code><code>from</code> <code>t1 </code><code>order</code> <code>by</code> <code>c1,id </code><code>asc</code> <code>limit 0,3;</code></p> <p><code>select</code> <code>* </code><code>from</code> <code>t1 </code><code>order</code> <code>by</code> <code>c1,id </code><code>asc</code> <code>limit 3,3;</code></p> </td> 
  </tr> 
 </tbody> 
</table>

案例2

两个类似的查询语句，除了返回列不同，其它都相同，但排序的结果不一致。  
测试表与数据：

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> <p>2</p> <p>3</p> <p>4</p> <p>5</p> <p>6</p> <p>7</p> <p>8</p> </td> 
   <td> <p><code>create</code> <code>table</code> <code>t2(id </code><code>int</code> <code>primary</code> <code>key</code><code>, status </code><code>int</code><code>, c1 </code><code>varchar</code><code>(255),c2 </code><code>varchar</code><code>(255),c3 </code><code>varchar</code><code>(255),</code><code>key</code><code>(c1));</code></p> <p><code>insert</code> <code>into</code> <code>t2 </code><code>values</code><code>(7,1,</code><code>'a'</code><code>,repeat(</code><code>'a'</code><code>,255),repeat(</code><code>'a'</code><code>,255));</code></p> <p><code>insert</code> <code>into</code> <code>t2 </code><code>values</code><code>(6,2,</code><code>'b'</code><code>,repeat(</code><code>'a'</code><code>,255),repeat(</code><code>'a'</code><code>,255));</code></p> <p><code>insert</code> <code>into</code> <code>t2 </code><code>values</code><code>(5,2,</code><code>'c'</code><code>,repeat(</code><code>'a'</code><code>,255),repeat(</code><code>'a'</code><code>,255));</code></p> <p><code>insert</code> <code>into</code> <code>t2 </code><code>values</code><code>(4,2,</code><code>'a'</code><code>,repeat(</code><code>'a'</code><code>,255),repeat(</code><code>'a'</code><code>,255));</code></p> <p><code>insert</code> <code>into</code> <code>t2 </code><code>values</code><code>(3,3,</code><code>'b'</code><code>,repeat(</code><code>'a'</code><code>,255),repeat(</code><code>'a'</code><code>,255));</code></p> <p><code>insert</code> <code>into</code> <code>t2 </code><code>values</code><code>(2,4,</code><code>'c'</code><code>,repeat(</code><code>'a'</code><code>,255),repeat(</code><code>'a'</code><code>,255));</code></p> <p><code>insert</code> <code>into</code> <code>t2 </code><code>values</code><code>(1,5,</code><code>'a'</code><code>,repeat(</code><code>'a'</code><code>,255),repeat(</code><code>'a'</code><code>,255));</code></p> </td> 
  </tr> 
 </tbody> 
</table>

分别执行SQL语句：

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> <p>2</p> </td> 
   <td> <p><code>select</code> <code>id,status,c1,c2 </code><code>from</code> <code>t2 </code><code>force</code> <code>index</code><code>(c1) </code><code>where</code> <code>c1&gt;=</code><code>'b'</code> <code>order</code> <code>by</code> <code>status;</code></p> <p><code>select</code> <code>id,status </code><code>from</code> <code>t2 </code><code>force</code> <code>index</code><code>(c1) </code><code>where</code> <code>c1&gt;=</code><code>'b'</code> <code>order</code> <code>by</code> <code>status;</code></p> </td> 
  </tr> 
 </tbody> 
</table>

执行结果如下：

[![201603220853092.png][]][201603220853092.png]

看看两者的执行计划是否相同

[![201603220853093.png][]][201603220853093.png]

为了说明问题，我在语句中加了force index的hint，确保能走上c1列索引。语句通过c1列索引捞取id，然后去表中捞取返回的列。根据c1列值的大小，记录在c1索引中的相对位置如下：

(c1,id)===(b,6),(b,3),(5,c),(c,2)，对应的status值分别为2 3 2 4。从表中捞取数据并按status排序，则相对位置变为(6,2,b),(5,2,c),(3,3,c),(2,4,c)，这就是第二条语句查询返回的结果，那么为什么第一条查询语句(6,2,b),(5,2,c)是调换顺序的呢？这里要看我之前提到的a.常规排序和b.优化排序中标红的部分，就可以明白原因了。由于第一条查询返回的列的字节数超过了max\_length\_for\_sort\_data，导致排序采用的是常规排序，而在这种情况下MYSQL将rowid排序，将随机IO转为顺序IO，所以返回的是5在前，6在后；而第二条查询采用的是优化排序，没有第二次捞取数据的过程，保持了排序后记录的相对位置。对于第一条语句，若想采用优化排序，我们将max\_length\_for\_sort\_data设置调大即可，比如2048。

[![201603220853094.png][]][201603220853094.png]

下面是本人关于mysql 自定义排序（field，INSTR，locate）的一点心得，希望对大家有所帮助  
首先说明这里有三个函数（order by field，ORDER BY INSTR，ORDER BY locate）

原表：

下面是我执行后的结果：

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> </td> 
   <td> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>`</code><code>user</code><code>` </code><code>order</code> <code>by</code> <code>field(2,3,5,4,id) </code><code>asc</code></p> </td> 
  </tr> 
 </tbody> 
</table>

根据结果分析：order by field(2,3,5,4,1,6) 结果显示顺序为：1 3 4 5 6 2

根据结果分析：order by field(2,3,5,4,1,6) 结果显示顺序为：2 1 3 4 5 6

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> </td> 
   <td> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>`</code><code>user</code><code>` </code><code>ORDER</code> <code>BY</code> <code>INSTR( </code><code>'2,3,5,4'</code><code>, id ) </code><code>ASC</code></p> </td> 
  </tr> 
 </tbody> 
</table>

根据结果分析：order by INSTR(2,3,5,4,1,6) 结果显示顺序为：1 6 2 3 5 4

根据结果分析：order by INSTR(2,3,5,4,1,6) 结果显示顺序为：4 5 3 2 1 6

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> </td> 
   <td> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>`</code><code>user</code><code>` </code><code>ORDER</code> <code>BY</code> <code>locate( id, </code><code>'2,3,5,4'</code> <code>) </code><code>ASC</code></p> </td> 
  </tr> 
 </tbody> 
</table>

id user pass

根据结果分析：order by locate(2,3,5,4,1,6) 结果显示顺序为：1 6 2 3 5 4

<table> 
 <tbody> 
  <tr> 
   <td> <p>1</p> </td> 
   <td> <p><code>SELECT</code> <code>* </code><code>FROM</code> <code>`</code><code>user</code><code>` </code><code>ORDER</code> <code>BY</code> <code>locate( id, </code><code>'2,3,5,4'</code> <code>) </code><code>DESC</code></p> </td> 
  </tr> 
 </tbody> 
</table>

根据结果分析：order by locate(2,3,5,4,1,6) 结果显示顺序为：4 5 3 2 1 6  
如我想要查找的数据库中的ID顺序首先是（2,3,5,4）然后在是其它的ID顺序，你首先要把他降序排即（4 5 3 2），然后在 SELECT \* FROM \`user\` ORDER BY INSTR( '4,5,3,2', id ) DESC limit 0,10 或用 SELECT \* FROM \`user\` ORDER BY locate( id, '4,5,3,2' ) DESC 就得到你想要的结果了。

[20161008142334625]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8a3b3c8e16614a859715675fbd620aeb.png
[20161008142357031]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/75b56b47a0bd4c52a6666d38a40ed27a.png
[20161008142408188]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/275b1b33ae6645828a8eb37a37547053.png
[20161008142418633]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/234c6d95da2f4afea9912bf1c8d4583a.png
[20161008142430367]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/d9fe5b520d2c4925a7aa237264abbde2.png
[20161008142439321]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a0280cbd3c374bb891ad447495e89c7e.png
[201603220853091.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/ca5344cc698c4992af22451158953b9d.png
[201603220853092.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/03aef5ac14764f02b37b19b2ddc9b8d8.png
[201603220853093.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/b042e60582f64ce5a92b24717bf8ca78.png
[201603220853094.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/2d90fa302a874ae6879748c0b837cf64.png