MySQL中，有兩種方式生成有序結果集：一是使用filesort，二是按索引順序掃描。利用索引進行排序操作是非常快的，而且可以利用同一索引同時進行查找和排序操作。當索引的順序與ORDER BY中的列順序相同且所有的列是同一方向(全部升序或者全部降序)時，可以使用索引來排序。如果查詢是連接多個表，僅當ORDER BY中的所有列都是第一個表的列時才會使用索引。其它情況都會使用filesort。
MySQL索引通常是被用於提高WHERE條件的數據行匹配或者執行聯結操作時匹配其它表的數據行的搜索速度。
MySQL也能利用索引來快速地執行ORDER BY和GROUP BY語句的排序和分組操作。
通過索引優化來實現MySQL的ORDER BY語句優化：
create table actor(
actor_id int unsigned NOT NULL AUTO_INCREMENT,
name varchar(16) NOT NULL DEFAULT '',
password varchar(16) NOT NULL DEFAULT '',
PRIMARY KEY(actor_id),
KEY (name)
) ENGINE=InnoDB
insert into actor(name,password) values('cat01','1234567');
insert into actor(name,password) values('cat02','1234567');
insert into actor(name,password) values('ddddd','1234567');
insert into actor(name,password) values('aaaaa','1234567');
mysql> explain select actor_id from actor order by actor_id \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: actor
type: index
possible_keys: NULL
key: PRIMARY
key_len: 4
ref: NULL
rows: 4
Extra: Using index
1 row in set (0.00 sec)
mysql> explain select actor_id from actor order by password \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: actor
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 4
Extra: Using filesort
1 row in set (0.00 sec)
mysql> explain select actor_id from actor order by name \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: actor
type: index
possible_keys: NULL
key: name
key_len: 18
ref: NULL
rows: 4
Extra: Using index
1 row in set (0.00 sec)
下面來羅列一些常見的索引對ORFER BY的優化情況：
1、如果一個SQL語句形如：
SELECT [column1],[column2],…. FROM [TABLE] ORDER BY [sort];
在[sort]這個欄位上建立索引就可以實現利用索引進行order by 優化。
2、WHERE + ORDER BY的索引優化，形如：
SELECT [column1],[column2],…. FROM [TABLE] WHERE [columnX] = [value] ORDER BY [sort];
建立一個聯合索引(columnX,sort)來實現order by 優化。
注意：如果columnX對應多個值，如下面語句就無法利用索引來實現order by的優化
SELECT [column1],[column2],…. FROM [TABLE] WHERE [columnX] IN ([value1],[value2],…) ORDER BY[sort];
3、WHERE+ 多個字段ORDER BY
SELECT * FROM [table] WHERE uid=1 ORDER x,y LIMIT 0,10;
建立索引(uid,x,y)實現order by的優化,比建立(x,y,uid)索引效果要好得多。
MySQL Order By不能使用索引來優化排序的情況
* 對不同的索引鍵做 ORDER BY ：(key1,key2分別建立索引)
SELECT * FROM t1 ORDER BY key1, key2;
* 在非連續的索引鍵部分上做 ORDER BY：(key_part1,key_part2建立聯合索引;key2建立索引)
SELECT * FROM t1 WHERE key2=constant ORDER BY key_part2;
* 同時使用了 ASC 和 DESC：(key_part1,key_part2建立聯合索引)
SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;
* 用於搜索記錄的索引鍵和做 ORDER BY 的不是同一個：(key1,key2分別建立索引)
SELECT * FROM t1 WHERE key2=constant ORDER BY key1;
* 如果在WHERE和ORDER BY的欄位上應用表達式(函數)時，則無法利用索引來實現order by的優化
SELECT * FROM t1 ORDER BY YEAR(logindate) LIMIT 0,10;
當MySQL不能使用索引進行排序時，就會利用自己的排序算法(快速排序算法)在內存(sort buffer)中對數據進行排序，如果內存裝載不下，它會將磁盤上的數據進行分塊，再對各個數據塊進行排序，然後將各個塊合並成有序的結果集（實際上就是外排序）。對於filesort，MySQL有兩種排序算法。
1.兩遍掃描算法(Two passes)
實現方式是先將須要排序的字段和可以直接定位到相關行數據的指針信息取出，然後在設定的內存（通過參數sort_buffer_size設定）中進行排序，完成排序之後再次通過行指針信息取出所需的Columns。
注：該算法是4.1之前采用的算法，它需要兩次訪問數據，尤其是第二次讀取操作會導致大量的隨機I/O操作。另一方面，內存開銷較小。
2. 一次掃描算法(single pass)
該算法一次性將所需的Columns全部取出，在內存中排序後直接將結果輸出。
注：從 MySQL 4.1 版本開始使用該算法。它減少了I/O的次數，效率較高，但是內存開銷也較大。如果我們將並不需要的Columns也取出來，就會極大地浪費排序過程所需要的內存。在 MySQL 4.1 之後的版本中，可以通過設置 max_length_for_sort_data 參數來控制 MySQL 選擇第一種排序算法還是第二種。當取出的所有大字段總大小大於 max_length_for_sort_data 的設置時，MySQL 就會選擇使用第一種排序算法，反之，則會選擇第二種。為了盡可能地提高排序性能，我們自然更希望使用第二種排序算法，所以在 Query 中僅僅取出需要的 Columns 是非常有必要的。
當對連接操作進行排序時，如果ORDER BY僅僅引用第一個表的列，MySQL對該表進行filesort操作，然後進行連接處理，此時，EXPLAIN輸出“Using filesort”；否則，MySQL必須將查詢的結果集生成一個臨時表，在連接完成之後進行filesort操作，此時，EXPLAIN輸出“Using temporary;Using filesort”。
