sql排序取第⼀条数据_算法的艺术：MySQLorderby对各种排
序算法的巧⽤
在 【精华】洞悉MySQL底层架构：游⾛在缓冲与磁盘之间 这篇⽂章中，我们介绍了索引树的页⾯怎么加载到内存中，如何淘汰，等底层细节。这篇⽂章我们从⽐较宏观的⾓度来看MySQL中关键字的原理。本⽂，我们主要探索order by语句的底层原理。阅读完本⽂，您将了解到：
order by语句有哪些排序模式，以及每种排序模式的优缺点；
order by语句会⽤到哪些排序算法，在什么场景下会选择哪种排序算法；
如何查看和分析sql的order by优化⼿段(执⾏计划 + OPTIMIZER_TRACE⽇志)；
如何优化order by语句的执⾏效率？(思想：减⼩⾏⼤⼩，尽量⾛索引，能够⾛覆盖索引最佳，可适当增加sort buffer内存⼤⼩)
这⾥我们从数据结构的维度来看数据和索引，也就是都当成B+树的的，我们需要数据的时候再从存储引擎的B+树中读取。
以下是我们本⽂作为演⽰例⼦的表，假设我们有如下表：
索引如下：
对应的idx_d索引结构如下(这⾥我们做了⼀些夸张的⼿法，让⼀个页数据变⼩，为了展现在索引树中的查流程)：
1、如何跟踪执⾏优化
为了⽅便分析sql的执⾏流程，我们可以在当前session中开启 optimizer_trace:
SET optimizer_trace='enabled=on';
然后执⾏sql，执⾏完之后，就可以通过以下堆栈信息查看执⾏详情了：
SELECT * FROM information_schema.OPTIMIZER_TRACEG;
以下是
1select a, b, c, d from t20 force index(idx_abc)  where a=3 order by d limit 100,2;
的执⾏结果，其中符合a=3的有8457条记录，针对order by重点关注以下属性：
1"filesort_priority_queue_optimization": {  // 是否启⽤优先级队列 2  "limit": 102,          // 排序后需要取的⾏数，这⾥为 limit 100,2，也就是100+2=102 3  "rows_esti
1.1、排序模式
其中 sort_mode有如下⼏种形式：
sort_key, rowid：表明排序缓冲区元组包含排序键值和原始表⾏的⾏id，排序后需要使⽤⾏id进⾏回表，这种算法也称为original
filesort algorithm(回表排序算法)；
sort_key, additional_fields：表明排序缓冲区元组包含排序键值和查询所需要的列，排序后直接从缓冲区元组取数据，⽆需回表，这种算法也称为modified filesort algorithm(不回表排序)；
sort_key, packed_additional_fields：类似上⼀种形式，但是附加的列(如varchar类型)紧密地打包在⼀起，⽽不是使⽤固定长度的编码。
如何选择排序模式
选择哪种排序模式，与max_length_for_sort_data这个属性有关，这个属性默认值⼤⼩为1024字节：
如果查询列和排序列占⽤的⼤⼩超过这个值，那么会转⽽使⽤sort_key, rowid模式；
如果不超过，那么所有列都会放⼊sort buffer中，使⽤sort_key, additional_fields或者sort_key, packed_additional_fields模式；
如果查询的记录太多，那么会使⽤sort_key, packed_additional_fields对可变列进⾏压缩。
1.2、排序算法
基于参与排序的数据量的不同，可以选择不同的排序算法：
如果排序取的结果很⼩，⼩于内存，那么会使⽤优先级队列进⾏堆排序；
例如，以下只取了前⾯10条记录，会通过优先级队列进⾏排序：
1select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 10;
如果排序limit n, m，n太⼤了，也就是说需要去排序很后⾯的数据，那么会使⽤sort buffer进⾏快速排序：
一i一一高考一一冫新闻
如下，表中a=1的数据有三条，但是由于需要limit到很后⾯的记录，MySQL会对⽐优先级队列排序和快速排序的开销，选择⼀个⽐较合适的排序算法，这⾥最终放弃了优先级队列，转⽽使⽤sort buffer进⾏快速排序：
1select a, b, c, d from t20 force index(idx_abc) where a=1 order by d limit 300,2;
如果参与排序的数据sort buffer装不下了，那么我们会⼀批⼀批的给sort buffer进⾏内存快速排序，结果放⼊排序临时⽂件，最终使对所有排好序的临时⽂件进⾏归并排序，得到最终的结果;
如下，a=3的记录超过了sort buffer，我们要查的数据是排序后1000⾏起，sort buffer装不下1000⾏数据了，最终MySQL选择使⽤sort buffer进⾏分批快排，把最终结果进⾏归并排序：
1select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 1000,10;
2、order by⾛索引避免排序
执⾏如下sql：
1select a, b, c, d from t20 force index(idx_d) where d like 't%' order by d limit 2;
我们看⼀下执⾏计划：
发现Extra列为：Using index condition，也就是这⾥只⾛了索引。
databinder系统分析执⾏流程如下图所⽰：
通过idx_d索引进⾏range_scan查，扫描到4条记录，然后order by继续⾛索引，已经排好序，直接取前⾯两条，然后去聚集索引查询完整记录，返回最终需要的字段作为查询结果。这个过程只需要借
助索引。
如何查看和修改sort buffer⼤⼩？
我们看⼀下当前的sort buffer⼤⼩：
可以发现，这⾥默认配置了sort buffer⼤⼩为512k。
mysql语句顺序我们可以设置这个属性的⼤⼩：
SET GLOBAL sort_buffer_size = 32*1024;
或者
SET sort_buffer_size = 32*1024;
下⾯我们统⼀把sort buffer设置为32k
1SET sort_buffer_size = 32*1024;
3、排序算法案例
3.1、使⽤优先级队列进⾏堆排序
如果排序取的结果很⼩，并且⼩于sort buffer，那么会使⽤优先级队列进⾏堆排序；
例如，以下只取了前⾯10条记录：
1select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 10;
a=3的总记录数：8520。查看执⾏计划：
发现这⾥where条件⽤到了索引，order by limit⽤到了排序。我们进⼀步看看执⾏的optimizer_trace⽇志：
1"filesort_priority_queue_optimization": { 2  "limit": 10, 3  "rows_estimate": 27033, 4  "row_size": 123, 5  "memory_available": 32768, 6  "chosen": true  // 使⽤优先delphi txt
rage流行发现这⾥是⽤到了优先级队列进⾏排序。排序模式是：sort_key, additional_fields，即先回表查询完整记录，把排序需要查的所有字段
都放⼊sort buffer进⾏排序。
所以这个执⾏流程如下图所⽰：
1. 通过where条件a=3扫描到8520条记录；
2. 回表查记录；
3. 把8520条记录中需要的字段放⼊sort buffer中；
4. 在sort buffer中进⾏堆排序；
5. 在排序好的结果中取limit 10前10条，写⼊net buffer，准备发送给客户端。
3.2、内部快速排序
如果排序limit n, m，n太⼤了，也就是说需要去排序很后⾯的数据，那么会使⽤sort buffer进⾏快速排序。MySQL会对⽐优先级队列排序
个人主页配图
和归并排序的开销，选择⼀个⽐较合适的排序算法。
如何衡量究竟是使⽤优先级队列还是内存快速排序？⼀般来说，快速排序算法效率⾼于堆排序，但是堆排序实现的优先级队列，⽆需
排序完所有的元素，就可以得到order by limit的结果。MySQL源码中声明了快速排序速度是堆排序的3倍，在实际排序的时候，会
根据待排序数量⼤⼩进⾏切换算法。如果数据量太⼤的时候，会转⽽使⽤快速排序。
有如下SQL：
1select a, b, c, d from t20 force index(idx_abc)  where a=1 order by d limit 300,2;
我们把sort buffer设置为32k：
1SET sort_buffer_size = 32*1024;
其中a=1的记录有3条。查看执⾏计划：
可以发现，这⾥where条件⽤到了索引，order by limit ⽤到了排序。我们进⼀步看看执⾏的optimizer_trace⽇志：
1"filesort_priority_queue_optimization": { 2  "limit": 302, 3  "rows_estimate": 27033, 4  "row_size": 123, 5  "memory_available": 32768, 6  "strip_additional_可以发现这⾥最终放弃了优先级队列，转⽽使⽤sort buffer进⾏快速排序。
所以这个执⾏流程如下图所⽰：
1. 通过where条件a=1扫描到3条记录；
2. 回表查记录；
3. 把3条记录中需要的字段放⼊sort buffer中；
4. 在sort buffer中进⾏快速排序；
5. 在排序好的结果中取limit 300, 2第300、301条记录，写⼊net buffer，准备发送给客户端。
3.3、外部归并排序
当参与排序的数据太多，⼀次性放不进去sort buffer的时候，那么我们会⼀批⼀批的给sort buffer进⾏内存排序，结果放⼊排序临时⽂件，最终使对所有排好序的临时⽂件进⾏归并排序，得到最终的结果。
有如下sql：
1select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 1000,10;
其中a=3的记录有8520条。执⾏计划如下：
image-20200614171147989
可以发现，这⾥where⽤到了索引，order by limit⽤到了排序。进⼀步查看执⾏的optimizer_trace⽇志：
1"filesort_priority_queue_optimization": { 2  "limit": 1010, 3  "rows_estimate": 27033, 4  "row_size": 123, 5  "memory_available": 32768, 6  "strip_additiona
我们可以看到，由于limit 1000，要返回排序后1000⾏以后的记录，显然sort buffer已经不能⽀撑这么⼤的优先级队列了，所以转⽽使
⽤sort buffer内存排序，⽽这⾥需要在sort buffer中分批执⾏快速排序，得到多个排序好的外部临时⽂件，最终执⾏归并排序。(外部临时⽂件的位置由tmpdir参数指定)
其流程如下图所⽰：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。