转载请说明出处,谢谢!
一、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个宏
这个在官方文档上有出现所以提出来说明一下
#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上的源码
点击(此处)折叠或打开
免责声明:
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
软考中级精品资料免费领
- 历年真题答案解析
- 备考技巧名师总结
- 高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1148
183.71 KB下载数642
644.84 KB下载数2756
相关文章
发现更多好内容- 在 JavaScript 中,split 方法究竟该如何使用?(split方法在javascript中怎么用)
- 如何解决 java log4j2 的安全漏洞?(java log4j2安全漏洞解决方案)
- 如何在 Java 中对幂函数的性能进行优化?(如何在Java中优化幂函数的性能)
- 如何编写 Java 获取文件行数的代码?(Java获取文件行数的代码怎么写)
- Java 中 == 和 equals 的区别究竟有哪些?(java中==和equals的区别是什么)
- Java 如何读取外部配置文件?(详细教程及 SEO 优化指南)(java怎么读取外部配置文件)
- 如何使用 Java 将文件移动到指定文件夹?(怎么用java移动文件到指定文件夹)
- 在 Java 中,for 循环究竟有哪些特点呢?(java中for循环的特点是什么)
- Java 中 write 方法的详细使用指南及示例解析(java中write方法如何使用)
- 如何使用 Java 遍历 Map 集合以获取值?(java怎么遍历map集合获取值)
猜你喜欢
AI推送时光机从排序原理到MYSQL中的排序方式
数据库2024-04-02
sql中从大到小排序怎么排的
数据库2024-05-15
sql中从大到小排序的方法
数据库2024-05-10
MySQL中排序的原理是什么
数据库2024-04-02
javascript冒泡排序从大到小排序的方法是什么
数据库2023-05-13
详解MySQL中Order By排序和filesort排序的原理及实现
数据库2022-08-16
深入了解pandas排序:从单列排序到多列排序的技巧
数据库2024-01-24
MySQL中有哪些排序方式
数据库2023-06-14
mysql怎么实现从大到小排序
数据库2024-04-28
mysql order by 排序原理解析
数据库2024-04-02
MySQL排序的内部原理是什么
数据库2024-04-02
MySQL中一些鲜为人知的排序方式
数据库2024-04-02
MySQL中order by排序语句的原理是什么
数据库2023-07-04
mysql之DML的select分组排序方式
数据库2024-09-14
MySQL原理 - 字符集与排序规则
数据库2021-04-11
TreeSet中的排序方式有哪些
数据库2023-05-31
springdataJPA中的多属性排序方式
数据库2024-04-02
JAVA中数组怎么从小到大排序
数据库2023-07-05
如何理解MySQL中filesort排序
数据库2024-04-02
咦!没有更多了?去看看其它编程学习网 内容吧