【MySQL filesort原理及优化】01
概述
在MySQL中的ORDER BY有两种排序实现方式：
1、利用有序索引获取有序数据；
2、文件排序 。
在使用explain分析查询的时候 ， 利用有序索引获取有序数据显示Using index 。如果MySQL在排序的时候没有使用到索引那么就会输出using filesort ， 即使用文件排序 。
文件排序是通过相应的排序算法 ， 将取得的数据在内存中进行排序：MySQL需要将数据在内存中进行排序 ， 所使用的内存区域也就是我们通过sort_buffer_size系统变量所设置的sort buffer（排序区） 。这个sort buffer是每个Thread独享的 ， 所以说可能在同一时刻在MySQL中可能存在多个sort buffer内存区域 。
02
原理
MySQL对排序有两种实现：2.1 双路排序原理第一遍扫描出需要排序的字段 ， 然后进行排序后 ， 根据排序结果 ， 第二遍再扫描一下需要select的列数据 。这样会引起大量的随机IO ， 效率不高 ， 但是节约内存 。排序使用quick sort ， 但是如果内存不够则会按照block进行排序 ， 将排序结果写入磁盘文件 ， 然后再将结果合并 。
具体过程：
1、读取所有满足条件的记录 。
2、对于每一行 ， 存储一对值到缓冲区（排序列 ， 行记录指针） ， 一个是排序的索引列的值 ， 即order by用到的列值 ， 和指向该行数据的行指针（缓冲区的大小为sort_buffer_size大小） 。
3、当缓冲区满后 ， 运行一个快速排序（qsort）来将缓冲区中数据排序 ， 并将排序完的数据存储到一个临时文件 ， 并保存一个存储块的指针 ， 当然如果缓冲区不满 ， 则不会重建临时文件了 。
4、重复以上步骤 ， 直到将所有行读完 ， 并建立相应的有序的临时文件 。
5、对块级进行排序 ， 这个类似于归并排序算法 ， 只通过两个临时文件的指针来不断交换数据 ， 最终达到两个文件 ， 都是有序的 。
6、重复5直到所有的数据都排序完毕 。
7、采取顺序读的方式 ， 将每行数据读入内存 ， 并取出数据传到客户端 ， 这里读取数据时并不是一行一行读 ， 读取缓存大小由read_rnd_buffer_size来指定 。
特点
采取的方法为：快速排序 + 归并排序 。
但有一个问题 ， 就是 ， 一行数据会被读两次 ， 第一次是where条件过滤时 ， 第二个是排完序后还得用行指针去读一次 ， 一个优化的方法是 ， 直接读入数据 ， 排序的时候也根据这个排序 ， 排序完成后 ， 就直接发送到客户端了 。
2.2 单路排序在MySQL4.1版本之前只有第一种排序算法双路排序 ， 第二种算法是从MySQL4.1开始的改进算法 ， 主要目的是为了减少第一次算法中需要两次访问表数据的IO操作 ， 将两次变成了一次 ， 但相应也会耗用更多的sortbuffer空间 。当然 ， MySQL4.1开始的以后所有版本同时也支持第一种算法 。
原理即一遍扫描数据后将select需要的列数据以及排序的列数据都取出来 ， 然后在sort buffer中排序 ， 这样就不需要进行第二遍扫描了 ， 当然内存不足时也会使用磁盘临时文件进行外排 。
具体过程：
1、读取满足条件的记录
2、对于每一行 ， 记录排序的key和数据行指针 ， 并且把要查询的列也读出来
推荐阅读
- 蜂鸣器电路,五款蜂鸣器驱动电路原理图
- 内墙隔断的原理是什么
- 自动门工作原理图 自动门工作原理
- 第2版 闪存技术、产品和原理全面解析
- 主动式平衡杆什么原理
- 数控是什么,工作原理是什么
- 漂移是什么原理
- 接触器作用,分类及工作原理
- 光纤原理,基本结构及原理
- 硬盘工作原理,电脑硬盘分区管家