一 簡介
偏向於業務的 (MySQL)DBA 或者業務的開發者來說，order by 排序是一個常見的業務功能，將結果根據指定的字段排序，滿足前端展示的需求。然而排序操作也是經常出現慢查詢排行榜的座上賓。本文將從原理和實際案例優化，order by 使用限制等幾個方面來逐步瞭解 order by 排序。
二 原理
在瞭解 order by 排序的原理之前，強烈安利兩篇關於排序算法的文章 《歸併排序的實現》 《經典排序算法》。MySQL 支持兩種排序算法，常規排序和優化，並且在 MySQL 5.6 版本中 針對 order by limit M,N 做了特別的優化，這裡列為第三種。
2.1 常規排序
a 從表 t1 中獲取滿足 WHERE 條件的記錄
b 對於每條記錄，將記錄的主鍵 + 排序鍵 (id,col2) 取出放入 sort buffer
c 如果 sort buffer 可以存放所有滿足條件的 (id,col2) 對，則進行排序；否則 sort buffer 滿後，進行排序並固化到臨時文件中。(排序算法採用的是快速排序算法)
d 若排序中產生了臨時文件，需要利用歸併排序算法，保證臨時文件中記錄是有序的
e 循環執行上述過程，直到所有滿足條件的記錄全部參與排序
f 掃描排好序的 (id,col2) 對，並利用 id 去撈取 SELECT 需要返回的列 (col1,col2,col3)
g 將獲取的結果集返回給用戶。
從上述流程來看，是否使用文件排序主要看 sort buffer 是否能容下需要排序的 (id,col2) 對，這個 buffer 的大小由 sort_buffer_size 參數控制。此外一次排序需要兩次 IO，一次是撈 (id,col2), 第二次是撈 (col1,col2,col3)，由於返回的結果集是按 col2 排序，因此 id 是亂序的，通過亂序的 id 去撈 (col1,col2,col3) 時會產生大量的隨機 IO。對於第二次 MySQL 本身一個優化，即在撈之前首先將 id 排序，並放入緩衝區，這個緩存區大小由參數 read_rnd_buffer_size 控制，然後有序去撈記錄，將隨機 IO 轉為順序 IO。
2.2 優化排序
常規排序方式除了排序本身，還需要額外兩次 IO。優化的排序方式相對於常規排序，減少了第二次 IO。主要區別在於，放入 sort buffer 不是 (id,col2), 而是 (col1,col2,col3)。由於 sort buffer 中包含了查詢需要的所有字段，因此排序完成後可以直接返回，無需二次撈數據。這種方式的代價在於，同樣大小的 sort buffer，能存放的 (col1,col2,col3) 數目要小於 (id,col2)，如果 sort buffer 不夠大，可能導致需要寫臨時文件，造成額外的 IO。當然 MySQL 提供了參數 max_length_for_sort_data，只有當排序元組小於 max_length_for_sort_data 時，才能利用優化排序方式，否則只能用常規排序方式。
2.3 優先隊列排序
為了得到最終的排序結果，無論怎樣，我們都需要將所有滿足條件的記錄進行排序才能返回。那麼相對於優化排序方式，是否還有優化空間呢？5.6 版本針對 Order by limit M，N 語句，在空間層面做了優化，加入了一種新的排序方式: 優先隊列，這種方式採用堆排序實現。堆排序算法特徵正好可以解 limit M，N 這類排序的問題，雖然仍然需要所有元素參與排序，但是隻需要 M+N 個元組的 sort buffer 空間即可，對於 M，N 很小的場景，基本不會因為 sort buffer 不夠而導致需要臨時文件進行歸併排序的問題。對於升序，採用大頂堆，最終堆中的元素組成了最小的 N 個元素，對於降序，採用小頂堆，最終堆中的元素組成了較大的 N 的元素。
三 優化
通過上面的原理分析，我們知道排序的本質是通過一定的算法 (耗費 cpu 運算, 內存, 臨時文件 IO) 將結果集變成有序的結果集。如何優化呢？答案是分兩個方面利用索引的有序性 (MySQL 的 B+ 樹索引是默認從小到大遞增排序) 減少排序, 較好的方式是直接不排序。
create table t1(
id int not null primary key ,
key_part1 int(10) not null,
key_part2 varchar(10) not null default '',
key_part3
key idx_kp1_kp2(key_part1,key_part2,key_part4)，
key idx_kp3(id)
) engine=innodb default charset=utf8
以下種類的查詢是可以利用到索引 idx_kp1_kp2 的
SELECT * FROM t1 ORDER BY key_part1,key_part2,... ;
SELECT * FROM t1 WHERE key_part1 = constant ORDER BY key_part2;
SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 DESC;
SELECT * FROM t1 WHERE key_part1 = 1 ORDER BY key_part1 DESC, key_part2 DESC;
SELECT * FROM t1 WHERE key_part1 > constant ORDER BY key_part1 ASC;
SELECT * FROM t1 WHERE key_part1 < constant ORDER BY key_part1 DESC;
SELECT * FROM t1 WHERE key_part1 = constant1 AND key_part2 > constant2 ORDER BY key_part2
溫馨提示 ，各位看官要辯證的看待官方給的例子，自己多動手實踐。
無法利用到索引排序的情況，其實我覺得這是本文的重點，對於廣大開發同學而言，記住那種不能利用索引排序會更簡單些。
1 最常見的情況 用來查找結果的索引 (key2) 和 排序的索引 (key1) 不一樣,where a=x and b=y order by id;
SELECT * FROM t1 WHERE key2=constant ORDER BY key1;
2 排序字段在不同的索引中，無法使用索引排序
SELECT * FROM t1 ORDER BY key1,key2;
3 排序字段順序與索引中列順序不一致，無法使用索引排序，比如索引是 key idx_kp1_kp2(key_part1,key_part2)
SELECT * FROM t1 ORDER BY key_part2, key_part1;
4 order by 中的升降序和索引中的默認升降不一致，無法使用索引排序
SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;
5 ey_part1 是範圍查詢，key_part2 無法使用索引排序
SELECT * FROM t1 WHERE key_part1> constant ORDER BY key_part2;
5 rder by 和 group by 字段列不一致
SELECT * FROM t1 WHERE key_part1=constant ORDER BY key_part2 group by key_part4;
6 索引本身是無序存儲的，比如 hash 索引，不能利用索引的有序性。
7 order by 字段只被索引了前綴 ，key idx_col(col(10))
select * from t1 order by col ;
8 對於還有 join 的關聯查詢，排序字段並非全部來自於第一個表，使用 explain 查看執行計劃第一個表 type 值不是 const 。
當無法避免排序操作時, 又該如何來優化呢？很顯然, 優先選擇 using index 的排序方式，在無法滿足利用索引排序的情況下，儘可能讓 MySQL 選擇使用第二種單路算法來進行排序。這樣可以減少大量的隨機 IO 操作, 很大幅度地提高排序的效率。
1、加大 max_length_for_sort_data 參數的設置
在 MySQL 中, 決定使用老式排序算法還是改進版排序算法是通過參數 max_length_for_sort_data 來決定的。當所有返回字段的較大長度小於這個參數值時, MySQL 就會選擇改進後的排序算法, 反之, 則選擇老式的算法。所以, 如果有充足的內存讓 MySQL 存放須要返回的非排序字段, 就可以加大這個參數的值來讓 MySQL 選擇使用改進版的排序算法。
2、去掉不必要的返回字段
當內存不是很充裕時, 不能簡單地通過強行加大上面的參數來強迫 MySQL 去使用改進版的排序算法, 否則可能會造成 MySQL 不得不將數據分成很多段, 然後進行排序, 這樣可能會得不償失。此時就須要去掉不必要的返回字段, 讓返回結果長度適應 max_length_for_sort_data 參數的限制。
同時也要規範 MySQL 開發規範，儘量避免大字段。當有 select 查詢列含有大字段 blob 或者 text 的時候, MySQL 會選擇常規排序。
" algorithm to use. It normally uses the modified algorithm except when or columns are involved, in which case it uses the original algorithm."
3、增大 sort_buffer_size 參數設置
這個值如果過小的話, 再加上你一次返回的條數過多, 那麼很可能就會分很多次進行排序, 然後最後將每次的排序結果再串聯起來, 這樣就會更慢, 增大 sort_buffer_size 並不是為了讓 MySQL 選擇改進版的排序算法, 而是為了讓 MySQL 儘量減少在排序過程中對須要排序的數據進行分段, 因為分段會造成 MySQL 不得不使用臨時表來進行交換排序。但是這個值不是越大越好：
1 sort_buffer_size 是一個 connection 級參數, 在每個 connection 第一次需要使用這個 buffer 的時候, 一次性分配設置的內存。
2 sort_buffer_size 並不是越大越好, 由於是 connection 級的參數, 過大的設置 + 高併發可能會耗盡系統內存資源。
3 據說 sort_buffer_size 超過 2M 的時候, 就會使用 mmap() 而不是 malloc() 來進行內存分配, 導致效率降低。
閱讀更多 IT生涯 的文章
