order by

1.全字段排序

分析以下SQL语句执行流程，city字段建立了索引。

select city,name,age from t where city='杭州' order by name limit 1000 ;

• 首先从city的索引B+树叶子节点，获取每行记录的主键ID，然后从主键索引树的每一行记录中，取出查询的三个字段。
• 在内存开辟一个用于排序的空间sort_buffer，并指定空间大小。
• 将每行记录的city,name,age三个字段都放入sort_buffer，然后根据name字段进行快排(内部排序)。放入内存排序可能存在两种情况：
  • sort_buffer空间大小 > 所有要排序的数据量：此时需要进行外部排序，将所有数据分块并依次放入sort_buffer进行排序，每个有序的块排序好后会存放在“临时文件”中，最后将每块有序的临时文件通过归并排序合并成一个大的有序的文件。
  • sort_buffer空间大小 ＜ 所有要排序的数据量：直接在内存进行排序。
• 把排序后前1000条结果返回给客户端。

SQL语句排序时可以通过查看OPTIMIZER_TRACE结果，对执行排序的SQL语句进行分析，其中介绍几个字段的含义：

“number_of_tmp_files”：表示使用到了临时文件的数量，内存开辟的排序空间越小，使用到的临时文件越多。

“examined_rows”：参与排序的行数。

“sort_mode ”里面的packed_additional_fields：表示对字符串进行了紧凑处理，按照实际字符串长度分配空间。Varchar定义的长度无效。

缺点：单行数据大或者sort_buffer分配内存空间小的情况下，效率比较低，不能充分利用内存进行排序。

2.rowId排序

max_length_for_sort_data：单行数据的长度超过设定阈值，则更换rowId排序法。

rowId排序方法用于解决单行数据长度过大,排序效率低的问题，与全字段排序相比，区别如下：

• sort_buffer内放入的字段，只有order by需要排序的字段name，以及主键ID。
• 最后根据排序结果的主键ID，再进行一次回表，从磁盘中取出查询的所有字段并返回。

3.优化

MySQL设计思想：内存够就多用内存，减少磁盘访问。因此优先考虑全字段排序，然后才考虑rowId排序优化。

3.1建立<where字段，排序字段>联合索引

建立联合索引之后，在联合索引树根据where字段，查询到的每一条记录主键ID都是有序的。因此直接根据ID回表读数据返回即可，直到不满足查询条件，或者是超过limit记录数。

explain结果可以发现extra字段没有using filesort，整个过程不需要排序。

3.2建立<where字段，排序字段，select字段>覆盖索引

只要当前联合索引已经覆盖了所有查询所需要的字段，那么就不需要进行回表。explain结果可以发现extra字段出现using index，表示使用了覆盖索引。

注意：如果where使用了in条件，可能会破坏有序性，导致虽然使用了联合索引，但依旧需要重新排序。优化策略是分别单独读取每一个in字段的记录到内存，然后业务端再继续归并排序。这样可以避免MySQL的临时文件或者是rowId多一次回表。

3.3其它

减少select字段：为防止单行数据长度过大，导致创建过多的临时文件，select查询时可以减少查询的字段。

limit行数小于表记录数：此时优化器会认为全表扫描比用索引方式快。

4.临时表

什么情况下排序时会使用临时表？

SQL语句”所要操作排序的表“不是磁盘中的表，而是进一步经过函数处理、表拼接等处理过后的表。这些表称之为临时表。

P.S子查询不一定会产生临时表。

4.1内存临时表

内存临时表：整个临时表的所有行数据存储在内存中。使用的引擎默认是MEMORY。

对于内存表的排序，优化器会选择rowId排序。因为回表时只需要在内存中读取数据，而不需要从磁盘读。

select word from t order by rand() limit 3;

分析上述SQL语句的排序过程：

• 首先在磁盘中对t表进行全表扫描，调用rand()计算得到结果(称为字段A)，然后将select需要查询的字段word+字段A都存入内存的一个临时表中。扫描行数为10000。
• 采用rowId排序，从内存临时表中，把排序字段A与”位置信息“字段存入sort_buffer当中。扫描行数变为20000
• 对sort_buffer进行排序
• 得到有序sort_buffer后，根据”位置信息“进行在内存中回表，取出前三条记录。最后返回结果集。

其中”位置信息“用于定位标识每一行数据。MEMORY引擎中为数组的索引；而InnoDB引擎中为主键ID。

4.2磁盘临时表

tmp_table_size：当内存临时表大小超过设定阈值时，就会转化为磁盘临时表。默认使用InnoDB引擎。

filesort_priority_queue_optimization中chosen=true：表示使用了优先队列排序算法。

🔥归并排序VS优先队列算法(堆排序)

上述SQL语句包含limit字段，只需要查出前3条记录，如果依旧使用归并排序，那么9997条记录也是有序的，而最后需要返回给用户的只有三条，因此就浪费了非常多的计算量。

而使用堆排序，维护一个大小为3的堆，最后只需要返回这个堆里的元素即可。剩余数据有序与否不需要关心。

如果SQL语句排序时使用了优先队列算法，那么使用到的临时文件number_of_tmp_files为0。因为只有归并排序才会用到临时文件保存有序块。

最终具体采用哪种排序算法，取决于以下几点：

• 如果不存在limit，则对整个临时表进行归并排序
• 如果存在limit m，需要根据m的大小进一步确定：
  • 如果m条记录的长度(字节数)大于sort_buffer_size大小，那么说明内存不能维护这么大的堆。只能采用归并排序。
  • 如果内存能够维护大小为m的堆，那么此时可以采用优先队列堆排序。

5.取随机n条记录

• order by rand() limit 3

上面的这种方法存在的问题在于，会使用临时表以及文件排序，因此查询的代价比较大。

• limit Y,1

前面的算法之所以查询代价比较大，是因为表中每行记录都参与计算了rand()构建临时表，并且只需要取出随机n个值，排序过程实际上也是多余的。

如果查询时只使用limit，则是直接从主键树取出对应的行记录，相比于第一种方法少了排序(先order排序再取出limit个行记录)，整个过程会快很多。具体算法：

①全表扫描，得到全表行数C。计算随机行数Y=floor(C*rand())，或者客户端根据表行数生成随机数再对C取模。

②直接select * fron t limit Y,1取出一条随机记录。

③重复上述操作三次，最终取出三条记录。

MySQL执行limit Y,1时会一行行扫描，得到Y行数据后全部丢弃，最终返回下一行扫描到的数据。因此这里要扫描Y+1行，然后再加上前面第一步全表扫描C，所以总扫描行数为C+Y+1。

其中随机数的计算可以在客户端进行，最后再到MySQL中查询拼接语句。

• limit Ymin, Ymax-Ymin+1

前面介绍方法中，查询三次数据，总行数为C+(Y1+1)+(Y2+1)+(Y3+1)。这里可以进一步优化：

首先求出Y1,Y2,Y3的最大值和最小值，然后直接执行以下语句即可，此时查询行数为C+Ymax+1。

💡客户端拿到行数为Ymin,Ymin+1...Ymax+1的所有数据后，再根据Y1,Y2,Y3之间的offset计算即可。

select * from t limit Ymin, Ymax-Ymin+1;

💡另一种方式是可以在limit查询语句中，插入where限定字段条件，此时limit行扫描会从满足where条件的第一行开始计算：

select * from t where id>id2 limit Y3-Y2,1;