从排序原理到MYSQL中的排序方式

本文参考MYSQL官方文档，算法书籍，部分为自己观点可能有误,如果有误请指出共同讨论
转载请说明出处，谢谢！


一、MYSQL排序可能用到的排序算法

从MYSQL官方文档和源码的接口来看MYSQL使用BUFFER内部快速排序算法，外部多路归并排序算法，相应的接口函数为
filesort()函数，注意filesort()是一个总的接口，内部排序实际调用save_index()下的std::stable_sort\std::sort、归并排序
也包含在下面接口可能为merge_many_buff()，也就像执行计划中using filesort的含义，他只能代表使用了排序，但是
是否使用到tempfile排序是看不出来的，但是这个可以再trace看到但是线上是不可以trace的研究是可以的，随后我会演示。
还要注意using temporary只是说明使用了临时表存储中间结果，这里先不讨论，只看排序。

下面简要介绍两种算法原理

1、buffer内部 快速排序算法
   快速排序是交换排序类算法，是冒泡排序的升级版，其原理是采用分而治之的思想，在于每趟交换设置一个基准点，
   将大于这个基准点的数据放到一边，大于的放到另一边，不断的进行递归完成，对于大数据量的排序快速排序一般
   效率优秀，在文章的最后是一个简单的快速排序的实现，如果对算法感兴趣的可以参考一下。但是至少还能进
   行3种优化
   --小数据优化，因为快速排序对数据量小的时候并不是最优，可以使用其他排序算法如插入排序。
   --尾递归优化，减少栈的使用
   --基准点优化，尽量取到数据中的中间值作为基准点，这样能够让快速排序更加优化。
   
2、外部磁盘多路归并排序
   将内部快速排序后有序的数据文件进行不断的比较得到有序的文件，每次归并多少个文件就是归并的路数
  图中每一个R当然代表的一个有序的磁盘文件
   下图2路归并排序(截取数据结构C语言版)
   
   下图5路归并排序(截取数据结构C语言版)


二、MYSQL相关参数
    sort_buffer_size:
        当然也就是每次排序的buffer，用作内部快速排序用，如果buffer越大当然产生的物理文件也就越少，但是这个
    参数是会话级别的，过分加大会造成内存不足，默认256K。注意：
    On Linux, there are thresholds of 256KB and
    2MB where larger values may significantly slow down memory allocation, so you should consider staying
    below one of those values
    
    read_rnd_buffer_size：
        除了MRR用到，这里也用到了用于 二次排序的时候对排序好的数据按照primary key(ROW_ID)按照分块的方式再次排序，
    意义同样在回表取数据可以尽量顺序化
    
    max_length_for_sort_data：
        单位为字节(bytes)，如果排序返回行的字段长度综合大约这个值，使用二次排序而不是一次排序，默认1024，最小
    值为4，如果加大这个值可能过多的使用一次排序造成高TEMPFILE空间使用而CPU不高,为什么如此后面解释。
    
    max_sort_length：
        单位为字节(bytes)，如果排序字段的长度超过这个值，只是用这个参数设置的长度，默认1024，比如text这种字段
    经常会大于这个值，如果加大这个值明显会提高排序的准确性，但是也意味着更高的BUFFER使用和TEMPFILE使用
    
三、监控磁盘排序
    Sort_merge_passes：磁盘排序归并次数，减少sort_buffer_size大小会显著减少Sort_merge_passes值，并且临时文件也
    会变少，第五部分证明
    sys.statements_with_sorting视图
     
四、MYSQL二次访问排序(original method)和一次访问排序(modified method)

1、二次访问排序
--读取数据只包含排序键值和rowid(primary key)放到sort buffer
--在buffer中进行快速排序，如果buffer 满则把内存中的排序数据写入tempfile
--重复上面的过程直到内部快速排序完成，并且生成多个tmepfile文件
--进行多路归并排序源码接口在merge_many_buff()，其中定义了MERGEBUFF，MERGEBUFF2 2个宏
  这个在官方文档上有出现所以提出来说明一下
  /* Defines used by filesort and uniques */
#define MERGEBUFF 7
#define MERGEBUFF2 15
  如果有兴趣的可以仔细看看源码..
--最后一次归并的时候，只有rowid(priamry key)到最后的文件中
--对最后的文件根据rowid(primary key)访问表数据，这样就可以得到排序好的数据
  这里有一个类似MRR的优化，将数据进行分块读入read_rnd_buffer_size进行
  按照rowid(primary key)排序在去访问表的数据，目的在于减少随机读取造成的影响
  但是这是分块的，只能减少不能杜绝，特别是数据量特别大的情况下，因为
  read_rnd_buffer_size只有默认256K.

问题在于对表数据的二次访问，一次在读取数据的时候，后一次在通过排序好的
rowid(primary key)进行数据的访问，并且会出现大量随机访问。

2、一次访问排序
这个就简单了，二次访问排序是把排序键值和rowid(primary key)放到sort buffer，
这个就是关于需要的数据字段全部放到sort buffer比如：
select id,name1,name2 from test order by id;

这里id,name1,name2都会存放到sort buffer中。这样排序好就好了，不需要回表取
数据了，当然这样做的劣势就是更大的sort buffer占用，更大tempfile占用。所以
mysql使用max_length_for_sort_data来限制默认1024，这是指id,name1,name2字段
的bytes长度。
因为不需要回表，所以只要一次访问数据

3、5.7.3后一次访问排序算法的优化
使用一个叫做pack优化的方法，目的在于压缩NULL减少一次访问排序算法对sort buffer和tempfile的过多使用
原文：
without packing, a VARCHAR(255)
column value containing only 3 characters takes 255 characters in the sort buffer. With packing, 
the value requires only 3 characters plus a two-byte length indicator. NULL values require only 
a bitmask.
但是我在做MYSQL TRACE的时候发现这还有一个unpack的过程，并且每一行每一个字段都需要pack unpack
随后证明

关于使用了的那种排序方式在执行计划中都体现为filesort不好弄清楚，但是我们可以通过trace的方式，
在官方文档也说了，但是我使用了对MYSQLD的trace方式来做，效果一致，详细参考第五部分

五、证明观点

1、首先需要证明是使用的是二次访问排序还是一次访问排序，是否启用了pack
官方文档说明
"filesort_summary": {
"rows": 100,
"examined_rows": 100,
"number_of_tmp_files": 0,
"sort_buffer_size": 25192,
"sort_mode": ""
}
sort_mode:
: This indicates use of the original algorithm. 
: This indicates use of the modified algorithm.
: This indicates use of the modified algorithm. Sort
buffer tuples contain the sort key value and packed columns referenced by the query. 
也就是说
sort_key, rowid是二次访问排序
sort_key, additional_fields是一次访问排序
sort_key, packed_additional_fields是一次访问排序+pack方式
好了我们来证明，使用测试表
mysql> show create table testmer \G;
*************************** 1. row ***************************
       Table: testmer
Create Table: CREATE TABLE `testmer` (
  `seq` int(11) NOT NULL,
  `id1` int(11) DEFAULT NULL,
  `id2` int(11) DEFAULT NULL,
  `id3` int(11) DEFAULT NULL,
  `id4` int(11) DEFAULT NULL,
  PRIMARY KEY (`seq`),
  KEY `id1` (`id1`,`id2`),
  KEY `id3` (`id3`,`id4`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.01 sec)

mysql>  select * from testmer ;
+-----+------+------+------+------+
| seq | id1  | id2  | id3  | id4  |
+-----+------+------+------+------+
|   1 |    1 |    2 |    4 |    4 |
|   2 |    1 |    3 |    4 |    5 |
|   3 |    1 |    2 |    4 |    4 |
|   4 |    2 |    4 |    5 |    6 |
|   5 |    2 |    6 |    5 |    8 |
|   6 |    2 |   10 |    5 |    3 |
|   7 |    4 |    5 |    8 |   10 |
|   8 |    0 |    1 |    3 |    4 |
+-----+------+------+------+------+
8 rows in set (0.01 sec)

分别在max_length_for_sort_data为1024和max_length_for_sort_data为4对
select * from testmer order by id1;
生成trace文件
意义也就是使用一次访问排序和二次访问排序,因为数据量少也就在sort_buffer
排序就好了。

一次访问排序：
opt: filesort_execution: ending struct
opt: filesort_summary: starting struct
opt: rows: 8
opt: examined_rows: 8
opt: number_of_tmp_files: 0
opt: sort_buffer_size: 34440
opt: sort_mode: ""
opt: filesort_summary: ending struct

为 一次访问排序+pack方式

二次访问排序：
opt: filesort_execution: ending struct
opt: filesort_summary: starting struct
opt: rows: 8
opt: examined_rows: 8
opt: number_of_tmp_files: 0
opt: sort_buffer_size: 18480
opt: sort_mode: ""
opt: filesort_summary: ending struct

为是二次访问排序
可以看到不同，证明了max_length_for_sort_data的作用

其实这个是filesort()函数中的一个调用而已，其实gdb也可以打上断点也能看到
  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() ?
               "" :
               param.using_addon_fields() ?
               "" : "");

2、证明减少sort_buffer_size大小会显著减少Sort_merge_passes值，并且临时文件也
   会变少

 为了完成这个证明我建立了一个大表，降低先sort_buffer为使用如下的语句使用更多的
 tempfile进行排序
 
mysql> select count(*) from  testshared3;
+----------+
| count(*) |
+----------+
|  1048576 |
+----------+
1 row in set (28.31 sec)
 
mysql> set sort_buffer_size=50000;
Query OK, 0 rows affected (0.00 sec)

mysql> show variables like '%sort_buffer_size%';
+-------------------------+---------+
| Variable_name           | Value   |
+-------------------------+---------+
| sort_buffer_size        | 50000   |
+-------------------------+---------+

 mysql> show status like '%Sort_merge%';
+-------------------+-------+
| Variable_name     | Value |
+-------------------+-------+
| Sort_merge_passes | 0     |
+-------------------+-------+
1 row in set (0.00 sec)

mysql> explain select * from  testshared3 order by id limit 1048570,1;
+----+-------------+-------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
| id | select_type | table       | partitions | type | possible_keys | key  | key_len | ref  | rows    | filtered | Extra          |
+----+-------------+-------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
|  1 | SIMPLE      | testshared3 | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 1023820 |   100.00 | Using filesort |
+----+-------------+-------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
mysql> select * from  testshared3 order by id limit 1048570,1;
+------+
| id   |
+------+
|    1 |
+------+
1 row in set (5 min 4.76 sec)
完成后
mysql> show status like '%Sort_merge%';
+-------------------+-------+
| Variable_name     | Value |
+-------------------+-------+
| Sort_merge_passes | 63    |
+-------------------+-------+
1 row in set (0.21 sec)

opt: number_of_tmp_files: 378 
临时文件数量378

然后加大sort_buffer_size

mysql>  show variables like '%sort_buffer_size%';
+-------------------------+---------+
| Variable_name           | Value   |
+-------------------------+---------+
| sort_buffer_size        | 262144  |
+-------------------------+---------+

mysql> show status like '%Sort_merge%';
+-------------------+-------+
| Variable_name     | Value |
+-------------------+-------+
| Sort_merge_passes | 0     |
+-------------------+-------+
1 row in set (0.04 sec)

还是同样的语句

mysql> select * from  testshared3 order by id limit 1048570,1;
+------+
| id   |
+------+
|    1 |
+------+
1 row in set (5 min 4.76 sec)
mysql> show status like '%Sort_merge%';
+-------------------+-------+
| Variable_name     | Value |
+-------------------+-------+
| Sort_merge_passes | 11    |
+-------------------+-------+
opt: number_of_tmp_files: 73
临时文件数量73

得到证明

3、证明有pack和unpack操作，并且每一行每一个字段都需要pack unpack

这个直接查看trace文件是否有接口就好了
实际上可以看到8段如下的操作
>Field::unpack      
Field::unpack
Field::unpack
Field::unpack
Field::unpack
Field::unpack     
Field::unpack"|wc -l
40                                                              
[root@testmy tmp]# cat sortys2.trace|grep ">Field::pack"|wc -l  
40             

刚好是5(字段)*8(行)               

当然我随后对一个大表只有一个字段的表进行一样的测试，既然是一个字段使用
一次访问排序的时候排序的全部字段就是这个字段而已，所以pack和unpack的次数应该
和行数差不多
mysql> select count(*) from  testshared3;
+----------+
| count(*) |
+----------+
|  1048576 |
+----------+
1 row in set (28.31 sec)
mysql> desc testshared3;
+-------+---------+------+-----+---------+-------+
| Field | Type    | Null | Key | Default | Extra |
+-------+---------+------+-----+---------+-------+
| id    | int(11) | YES  |     | NULL    |       |
+-------+---------+------+-----+---------+-------+
1 row in set (0.26 sec)

[root@testmy tmp]# cat mysqld11.trace|grep ">Field::unpack"|wc -l
1048571                    

也得到同样基本相同的结构，证明了一次访问排序中每一行每一个字段都需
要pack、unpack操作，其实在整个trace中还能看到很多类容比如列取出了
一次访问排序的全部字段，这里就不在详解了

六、源码GDB发现内部排序调用STD容器的std::stable_sort std::sort 进行排序

(gdb) n
250         if (param->sort_length < 10)
(gdb) list
245         than quicksort seems to be somewhere around 10 to 40 records.
246         So we're a bit conservative, and stay with quicksort up to 100 records.
247       */
248       if (count <= 100)
249       {
250         if (param->sort_length < 10)
251         {
252           std::sort(m_sort_keys, m_sort_keys + count,
253                     Mem_compare(param->sort_length));
254           return;

这部分mysql上的源码





最后附上快速排序的代码
带排序数据是13,3,2,9,34,5,102,90,20,2
排序完成后如下：
gaopeng@bogon:~/datas$ ./a.out 
sort result:2 2 3 5 9 13 20 34 90 102