order by工作原理

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `city` varchar(16) NOT NULL,
  `name` varchar(16) NOT NULL,
  `age` int(11) NOT NULL,
  `addr` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `city` (`city`)
) ENGINE=InnoDB;-- 市民表，city字段建普通索引city

查询城市是“杭州”的所有人名字，并且按照姓名排序返回前1000个人的姓名、年龄。

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

全字段排序

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	T	NULL	ref	city	city	51	const	4000	100.00	Using index condition;Using filesort

Extra字段中的”Using filesort”表示需要排序，MySQL会给每个线程分配一块内存用于排序，称为sort_buffer。

语句执行流程：

初始化sort_buffer，确定放入name、city、age这三个字段；
从索引city找到第一个满足city=’杭州’条件的主键id；
到主键id索引取出整行，取name、city、age三个字段的值，存入sort_buffer中；
从索引city取下一个记录的主键id；
重复步骤3、4直到city的值不满足查询条件为止；
对sort_buffer中的数据按照字段name做快速排序；(全字段排序)
按照排序结果取前1000行返回给客户端。

按照name排序这个动作，可能在内存中完成，也可能需要使用外部排序，取决于排序所需的内存和参数sort_buffer_size。
sort_buffer_size就是MySQL为排序开辟的内存(sort_buffer)的大小。如果要排序的数据量小于sort_buffer_size，排序就在内存中完成。如果排序数据量太大，内存放不下，则不得不利用磁盘临时文件辅助排序。

/* 打开optimizer_trace，只对本线程有效 */
SET optimizer_trace='enabled=on'; 

/* @a保存Innodb_rows_read的初始值 */
select VARIABLE_VALUE into @a from  performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 执行语句 */
select city, name,age from t where city='杭州' order by name limit 1000; 

/* 查看 OPTIMIZER_TRACE 输出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G

/* @b保存Innodb_rows_read的当前值 */
select VARIABLE_VALUE into @b from performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 计算Innodb_rows_read差值 */
select @b-@a;-- 4000
```  

通过查看OPTIMIZER_TRACE的结果来确认，可以从number_of_tmp_files中看到是否使用了临时文件。  
``` json  
"filesort_execution":[],
"filesort_summary":{
    "rows":4000,
    "examined_rows":4000,
    "number_of_tmp_files":12,
    "sort_buffer_size":32664,
    "sort_mode":"<sort_key,packed_additional_fields>"
}

examined_rows表示参与排序的行数。市民表中有4000条满足city=’杭州’的记录。
number_of_tmp_files表示排序过程使用的临时文件数。内存放不下时，就需要使用外部排序，外部排序一般使用归并排序算法。

如果sort_buffer_size超过了需要排序的数据量的大小，number_of_tmp_files就是0，表示排序可以直接在内存中完成。否则就需要再临时文件中排序。sort_buffer_size越小，需要分成的份数越多，number_of_tmp_files的值就越大。
sort_mode中的packed_additional_fields的意思是排序过程对字符串做了”紧凑”处理。即使name字段的定义是varchar(16)，在排序过程中还是要按照实际长度来分配空间。
select @b-@a的结果为4000，整个执行过程只扫描了4000行。(MyISAM)

查询optimizer_trace这个表时，需要用到临时表，而internal_tmp_disk_storage_engine的默认值是InnoDB。把数据从临时表取出来的时候，会让innodb_rows_read的值加1。

rowid排序

原始算法过程中，只对原表的数据读了一遍，剩下的操作都是在sort_buffer和临时文件中执行的。如果查询要返回的字段很多的话，那么sort_buffer里面要放的字段数太多，这样内存里能同时放下的行数很少，要分成很多个临时文件，排序的性能会很差。

set max_length_for_sort_data=16;– 控制用于排序的行数据的长度(需要的字段的定义大小的和)，如果单行的长度超过这个值，MySQL就认为单行太大，要换一个算法。(city\name\age一共36)

新的算法放入sort_buffer的字段，只有要排序的列(name字段)和主键id。(因为排序的结果少了city和age字段的值，就不能直接返回了)

初始化sort_buffer，确定放入两个字段，name和id；
从索引city找到第一个满足city=’杭州’条件的主键id；
到主键id索引取出整行，取name、id这两个字段，存入sort_buffer中；
从索引city取下一个记录的主键id；
重复步骤3、4直到不满足city=’杭州’条件为止；
对sort_buffer中的数据按照字段name进行排序；(rowid排序)
遍历排序结果，取前1000行，并按照id的值回到原表中取出city、name、age三个字段返回给客户端。

rowid排序多访问了一次表t的主键索引。(回表)
MySQL服务端从排序后的sort_buffer中依次取出id，然后到原表查到city、name、age三个字段的结果，不需要在服务端再耗费内存存储结果，是直接返回给客户端的。

"filesort_execution":[],
"filesort_summary":{
    "rows":4000,
    "examined_rows":4000,
    "number_of_tmp_files":10,
    "sort_buffer_size":32728,
    "sort_mode":"<sort_key,rowid>"
}

examined_rows的值还是4000，表示用于排序的数据是4000行。但是select @b-@a的结果为5000。除了排序过程外，在排序完成后，还要根据id去原表取值。语句limit 1000，会多读1000行。

rows_examined。server层调用引擎取一行的时候加1；引擎内部自己调用读取行不加1。
number_of_tmp_file变小，参与排序的行数虽然是4000行，但是每一行都变小了，需要排序的总数据量就变小了，需要的临时问价也变小。
sort_mode变成了<sort_key,rowid>表示参与排序的只有name和id这两个字段。

对比与优化

如果MySQL是在使担心排序内存太小，会影响排序效率，才会采用rowid排序算法，这样排序过程中依次可以排序更多行，但是需要再回到原表去取数据。

如果MySQL认为内存足够大，会优先选择全字段排序，把需要的字段都放到sort_buffer中，这样排序后就会直接从内存里返回查询结果，不用再回到原表去取数据。

MySQL做排序是一个成本比较高的操作。并不是所有的order by语句，都需要排序操作。因为原来的数据是无序的，所以MySQL需要生成临时表，并且在临时表上做排序操作。

创建查询条件字段和排序字段的联合索引

alter table t add index city_user(city, name);

在联合索引里面，可以用树搜索的方式定位到第一个满足city=’杭州’的记录，并且额外保证了，接下来按顺序取”下一条记录”的遍历过程中，只要city的值是杭州，name的值就一定是有序的。

从索引(city,name)找到第一个满足city=’杭州’条件的主键id;
到主键id索引取出整行，取name、city、age三个字段的值，作为结果集的一部分直接返回；
从索引(city,name)取下一条记录主键id；
重复步骤2、3，直到查到第1000条记录，或者是不满足city=’杭州’条件时循环结束。

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	T	NULL	ref	city,city_user	city_user	51	const	4000	100.00	Using index condition

这个查询过程不需要临时表，也不需要排序。
Extra字段中没有Using filesort，不需要排序。而且由于(city,name)这个联合索引本身有序，所以查询也不用把4000行全都读一遍，只要找到满足条件的前1000条记录就可以退出了，只需要扫描1000次。

创建覆盖索引避免回表

alter table t add index city_user_age(city,name,age);

对于city字段的值相同的行来说，还是按照name字段的值递增排序的，此时的查询语句也不再需要排序了。

从索引(city、name、age)找到第一个满足city=’杭州’条件的记录，取出其中的city、name、age三个字段的值，作为结果集的一部分直接返回；
从索引(city、name、age)取下一个记录，同样取出这三个字段的值，作为结果集的一部分直接返回；
重复执行步骤2，直到查到第1000条记录，或者是不满足city=’杭州’条件时循环结束。

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	T	NULL	ref	city,city_user,city_user_age	city_user_age	51	const	4000	100.00	Using where;Using index

Extra字段多了”Using index”，表示使用了覆盖索引，性能上会快很多。
索引维护代价需要权衡。

扩展

select * from t where city in (“杭州”,”苏州”) order by name limit 100;

联合索引(city,name)对于单个city内部，name是递增的；对于多个city则所有满足条件的name不是递增的，需要排序。

避免排序：

执行select * from t where city = “杭州” order by name limit 100;这个语句不需要排序，客户端用一个长度为100的内存数组A保存结果。
执行select * from t where city = “苏州” order by name limit 100;同上，结果存在内存数组B。
对于两个有序数组A、B，用归并排序的思想，得到name最小的前100值。

进一步limit 100–>limit 10000,100;处理方式类似。但数据库返回给客户端的数据量变大。
优化select *–>select id,name;取值并排序后，拿到100个id值再到数据中查出所有记录。