这篇文章，我们从更宏观的角度来看一下MySQL中关键字的原理。在本文中，我们主要探讨orderby语句的底层原理。阅读本文后，您将了解：orderby语句的排序模式有哪些，以及每种排序模式的优缺点；orderby语句会使用哪些排序算法，在哪些场景下会选择哪种排序算法；如何通过sql的优化方式（执行计划+OPTIMIZER_TRACE日志）查看和分析顺序；如何优化orderby语句的执行效率？（思路：减少行大小，尽量使用索引，最好使用覆盖索引，适当增加排序缓冲区的内存大小）这里我们从数据的维度来看数据和索引structure，也就是把它们都看做是B+树，我们需要数据的时候就从存储引擎的B+树中读取。下面是我们在本文中用作演示示例的表格。假设我们有如下表：索引如下：对应的idx_d索引结构如下（这里我们做了一些夸张的技巧，让一个页面的数据变小，为了展示在索引树中查找的过程）：1.如何跟踪执行优化为了方便分析sql的执行过程，我们可以在当前session中开启optimizer_trace：SEToptimizer_trace='enabled=on';然后执行sql，执行后可以通过如下堆栈信息查看执行情况Details:SELECT*FROMinformation_schema.OPTIMIZER_TRACE\G;下面是1selecta,b,c,dfromt20forceindex(idx_abc)wherea=3orderbydlimit100,2;的执行结果，其中匹配a=3的记录有8457条，关注orderbyAttribute:"filesort_priority_queue_optimization":{//是否启用优先级队列"limit":102,//排序后需要取的行数，这里是limit100,2，也就是100+2=102"rows_estimate":24576,//预估参与排序的行数"row_size":123,//行大小"memory_available":32768,//可用内存大小，即设置的sortbuffer大小"chosen":true//是否启用优先队列},..."filesort_summary":{"rows":103,//排序过程中持有的行数"examined_rows":8457,//参与排序的行数，InnoDB层返回的行数"number_of_tmp_files":0,//外部排序时使用的临时文件个数"sort_buffer_size":13496,//内存排序使用的内存大小"sort_mode":"sort_key,additional_fields"//排序方式1.1、排序方式wheresort_mode有以下几种形式：sort_key,rowid：表示排序缓冲区元组包含排序键值和原表行的行id。排序后，需要使用rowid返回表。该算法也称为原始文件排序算法（返回表排序算法）；sort_key、additional_fields：表示排序缓冲区元组包含排序键值和查询需要的列。排序后直接从buffertuple中取数据，不返回表。该算法也称为改进的文件排序算法（不返回表排序）；sort_key、packed_additional_fields：与前面的形式类似，但是将附加的列（比如varchar类型）紧密地打包在一起，而不是使用定长编码。max_length_for_sort_data属性相关，该属性默认值为1024字节：如果查询列和排序列占用的大小超过该值，则改用sort_key、rowid方式；如果不是，则所有列将被放入排序缓冲区，使用sort_key,additional_fields或sort_key,packed_additional_fields模式；如果查询中的记录过多，则使用sort_key、packed_additional_fields压缩可变列。1.2.排序算法根据参与排序的数据量大小，可以选择不同的排序算法：如果排序结果很小，小于内存，则使用优先队列进行堆排序；例如，下面只取前10条记录将通过优先队列排序：selecta,b,c,dfromt20forceindex(idx_abc)wherea=3orderbydlimit10;如果排序限制n,m,n太大，也就是很晚才需要排序的数据，会使用sortbuffer进行快速排序：如下，其中a=1的数据项有3个表，但是由于记录需要限制在最后面，MySQL会比较优先队列排序和快速排序的开销，选择更合适的排序算法，这里最后放弃了优先队列，改用排序缓冲区用于快速排序：selecta,b,c,dfromt20forceindex(idx_abc)wherea=1orderbydlimit300,2;快速对内存中的排序缓冲区进行排序，将结果放入排序后的临时文件中，最后对所有排序后的临时文件进行合并排序，得到最终结果；如下，a=3的记录超出了sortbuffer，我们需要找到排序后的数据从1000行开始，sortbuffer放不下1000行数据。最终MySQL选择使用sortbuffer进行批量快速排序，对最终结果进行合并排序：selecta,b,c,dfromt20forceindex(idx_abc)wherea=3orderbydlimit1000,10;2.按索引排序，避免排序执行如下sql：selecta,b,c,dfromt20forceindex(idx_d)wheredlike't%'orderbydlimit2;我们看一下执行计划：发现Extra列为：Usingindexcondition，也就是这里只有索引没有了。执行过程如下图所示：使用idx_d索引进行range_scan查找，扫描到4条记录，然后继续用orderby去索引，顺序已经排好了，直接取前两个，然后去到聚簇索引查询完整记录，返回最终需要的字段作为查询结果。这个过程只需要索引的帮助。如何查看和修改排序缓冲区的大小？让我们看一下当前排序缓冲区的大小：可以发现排序缓冲区的默认大小是512k。我们可以设置这个属性的大小：SETGLOBALsort_buffer_size=32*1024；或SETsort_buffer_size=32*1024；下面我们统一设置sortbuffer为32kSETsort_buffer_size=32*1024；如果排序结果小且小于排序缓冲区，则使用优先队列进行堆排序；比如只取前10条记录如下：selecta,b,c,dfromt20forceindex(idx_abc)wherea=3orderbydlimit10;a=3记录总数：8520查看执行计划：发现where条件使用索引，orderbylimit使用排序。我们仔细看看执行的optimizer_trace日志："filesort_priority_queue_optimization":{"limit":10,"rows_estimate":27033,"row_size":123,"memory_available":32768,"chosen":true//使用优先级排队排序}，“filesort_execution”：[]，“filesort_summary”：{“rows”：11，“examined_rows”：8520，“number_of_tmp_files”：0，“sort_buffer_size”：1448，“sort_mode”：“sort_key，additional_fields”}found这里使用了一个优先级队列来进行排序。排序方式为：sort_key,additional_fields，即先回表查询完整记录，将所有需要查找排序的字段放入排序缓冲区进行排序。所以执行过程如下图所示：通过where条件a=3扫描到8520条记录；回表查找记录；将8520条记录中的必填字段放入排序缓冲区；在排序缓冲区中进行堆排序；好的结果中，取limit10的前10个entry，写入netbuffer，准备发送给client。3.2.内部快速排序如果排序限制n,m,n太大，也就是说需要在排序结束时取数据，那么会使用排序缓冲区进行快速排序。MySQL会比较优先队列排序和归并排序的开销，选择更合适的排序算法。如何衡量是使用优先队列还是内存快速排序？一般来说，快速排序算法比堆排序效率更高，但是堆排序实现的优先级队列不需要对所有元素进行排序就可以得到按限制排序的结果。.MySQL源码中声明快速排序的速度是堆排序的三倍。在实际排序中，算法会根据待排序数的大小进行切换。如果数据量太大，则使用快速排序代替。有如下SQL：selecta,b,c,dfromt20forceindex(idx_abc)wherea=1orderbydlimit300,2;我们将排序缓冲区设置为32k：SETsort_buffer_size=32*1024;有3条记录a=1。查看执行计划：可以发现where条件使用了索引，orderbylimit使用了排序。让我们仔细看看执行的optimizer_trace日志："filesort_priority_queue_optimization":{"limit":302,"rows_estimate":27033,"row_size":123,"memory_available":32768,"strip_additional_fields":{"row_size":57,"sort_merge_cost":33783,"priority_queue_cost":61158,"chosen":false//对比发现快排的开销比优先队列低，这里优先队列不适用}},"filesort_execution":[],"filesort_summary":{"rows":3,"examined_rows":3,"number_of_tmp_files":0,"sort_buffer_size":32720,"sort_mode":"
