1. 首页
  2. IT资讯

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

我的《深入理解MySQL主从原理》,具体可以点击:ttps://j.youzan.com/yEY_Xi

本文参考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语言版)
    从排序原理到MYSQL中的排序方式
   下图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上的源码

点击( 此处 )折叠或打开

  1. / *
  2.     std : : stable_sort has some extra overhead in allocating the temp buffer ,
  3.     which takes some time . The cutover point where it starts to get faster
  4.     than quicksort seems to be somewhere around 10 to 40 records .
  5.     So we ' re a bit conservative , and stay with quicksort up to 100 records .
  6.    * /
  7.    if ( count < = 100 )
  8.    {
  9.      if ( param > sort_length < 10 )
  10.      {
  11.       std : : sort ( m_sort_keys , m_sort_keys + count ,
  12.                 Mem_compare ( param > sort_length ) ) ;
  13.       return ;
  14.      }
  15.     std : : sort ( m_sort_keys , m_sort_keys + count ,
  16.               Mem_compare_longkey ( param > sort_length ) ) ;
  17.     return ;
  18.    }
  19.    / / Heuristics here : avoid function overhead call for short keys .
  20.    if ( param > sort_length < 10 )
  21.    {
  22.     std : : stable_sort ( m_sort_keys , m_sort_keys + count ,
  23.                      Mem_compare ( param > sort_length ) ) ;
  24.     return ;
  25.    }
  26.   std : : stable_sort ( m_sort_keys , m_sort_keys + count ,
  27.                    Mem_compare_longkey ( param > sort_length ) ) ;

最后附上快速排序的代码
带排序数据是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 

点击( 此处 )折叠或打开

  1. / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  2.    > File Name : qsort . c
  3.    > Author : gaopeng QQ : 22389860
  4.    > Mail : gaopp_200217@163 . com
  5.    > Created Time : Fri 06 Jan 2017 03 : 04 : 08 AM CST
  6.   * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
  7. #include < stdio . h >
  8. #include < stdlib . h >
  9. int partition ( int * k , int low , int high )
  10. {
  11.          int point ;
  12.         point = k [ low ] ; / / 基准点 , 采用数组的第一个值,这里实际可以优化
  13.          while ( low < high ) / / 等待low = high一趟交换完成
  14.          {
  15.                  while ( low < high & & k [ high ] > = point ) / / 过滤掉尾部大于基准点的值 , 不需要交换
  16.                  {
  17.                         high ;
  18.                  }
  19.                 k [ low ] = k [ high ] ; / / 基准点多次交换为无谓交换直接赋值即可
  20.                  while ( low < high & & k [ low ] < = point ) / / 过滤掉头部小于基准点的值 , 不需要交换
  21.                  {
  22.                         low + + ;
  23.                  }
  24.                 k [ high ] = k [ low ] ; / / 基准点多次交换为无谓交换直接赋值即可
  25.          }
  26.         k [ low ] = point ;
  27.         return low ;
  28. }
  29. int q_sort ( int * k , int low , int high )
  30. {
  31.          int point ;
  32.          if ( low < high )
  33.          {
  34.                 point = partition ( k , low , high ) ;
  35.                 q_sort ( k , low , point 1 ) ; / / 实现递归前半部分
  36.                 q_sort ( k , point + 1 , high ) ; / / 实现递归后半部分
  37.          }
  38.         return 0 ;
  39. }
  40. int main ( )
  41. {
  42.          int i , a [ 10 ] = { 13 , 3 , 2 , 9 , 34 , 5 , 102 , 90 , 20 , 2 } ; / / 测试数据
  43.         q_sort ( a , , 9 ) ; / / 数组下标0 9
  44.         printf ( "sort result:" ) ;
  45.          for ( i = ; i < 10 ; i + + )
  46.          {
  47.                 printf ( "%d " , a [ i ] ) ;
  48.          }
  49.         printf ( "n" ) ;
  50. }

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7728585/viewspace-2130743/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:深沉的少年,转转请注明出处:http://www.cxybcw.com/183464.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code