从排序原理到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上的源码
-
/*
-
std::stable_sort has some extra overhead in allocating the temp buffer,
-
which takes some time. The cutover point where it starts to get faster
-
than quicksort seems to be somewhere around 10 to 40 records.
-
So we're a bit conservative, and stay with quicksort up to 100 records.
-
*/
-
if (count <= 100)
-
{
-
if (param->sort_length < 10)
-
{
-
std::sort(m_sort_keys, m_sort_keys + count,
-
Mem_compare(param->sort_length));
-
return;
-
}
-
std::sort(m_sort_keys, m_sort_keys + count,
-
Mem_compare_longkey(param->sort_length));
-
return;
-
}
-
// Heuristics here: avoid function overhead call for short keys.
-
if (param->sort_length < 10)
-
{
-
std::stable_sort(m_sort_keys, m_sort_keys + count,
-
Mem_compare(param->sort_length));
-
return;
-
}
-
std::stable_sort(m_sort_keys, m_sort_keys + count,
-
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
-
/*************************************************************************
-
> File Name: qsort.c
-
> Author: gaopeng QQ:22389860
-
> Mail: gaopp_200217@163.com
-
> Created Time: Fri 06 Jan 2017 03:04:08 AM CST
-
************************************************************************/
-
-
-
#include<stdio.h>
-
#include<stdlib.h>
-
-
-
int partition(int *k,int low,int high)
-
{
-
-
int point;
-
point = k[low]; //基准点,采用数组的第一个值,这里实际可以优化
-
while(low<high) //等待low=high一趟交换完成
-
{
-
-
while(low<high && k[high] >=point) //过滤掉尾部大于基准点的值,不需要交换
-
{
-
high--;
-
}
-
k[low] = k[high]; //基准点多次交换为无谓交换直接赋值即可
-
while(low<high && k[low] <=point) //过滤掉头部小于基准点的值,不需要交换
-
{
-
-
low++;
-
}
-
k[high] = k[low]; //基准点多次交换为无谓交换直接赋值即可
-
}
-
k[low] = point;
-
return low;
-
}
-
-
int q_sort(int *k,int low,int high)
-
{
-
-
int point;
-
if(low<high)
-
{
-
-
point = partition(k,low,high);
-
q_sort(k,low,point-1); //实现递归前半部分
-
q_sort(k,point+1,high); //实现递归后半部分
-
}
-
return 0;
-
}
-
-
int main()
-
{
-
-
int i,a[10]={13,3,2,9,34,5,102,90,20,2}; //测试数据
-
q_sort(a,0,9); //数组下标0 9
-
-
printf("sort result:");
-
for(i=0;i<10;i++)
-
{
-
printf("%d ",a[i]);
-
}
-
printf("\n");
-
}