一 簡介

偏向于業(yè)務(wù)的 (MySQL)DBA 或者業(yè)務(wù)的開發(fā)者來說，order by 排序是一個常見的業(yè)務(wù)功能，將結(jié)果根據(jù)指定的字段排序，滿足前端展示的需求。然而排序操作也是經(jīng)常出現(xiàn)慢查詢排行榜的座上賓。本文將從原理和實際案例優(yōu)化，order by 使用限制等幾個方面來逐步了解 order by 排序。

二 原理

在了解 order by 排序的原理之前，強烈安利兩篇關(guān)于排序算法的文章 《歸并排序的實現(xiàn)》 《經(jīng)典排序算法》。MySQL 支持兩種排序算法，常規(guī)排序和優(yōu)化，并且在 MySQL 5.6 版本中 針對 order by limit M,N 做了特別的優(yōu)化，這里列為第三種。

2.1 常規(guī)排序

a 從表 t1 中獲取滿足 WHERE 條件的記錄

b 對于每條記錄，將記錄的主鍵 + 排序鍵 (id,col2) 取出放入 sort buffer

c 如果 sort buffer 可以存放所有滿足條件的 (id,col2) 對，則進行排序;否則 sort buffer 滿后，進行排序并固化到臨時文件中。(排序算法采用的是快速排序算法)

d 若排序中產(chǎn)生了臨時文件，需要利用歸并排序算法，保證臨時文件中記錄是有序的

e 循環(huán)執(zhí)行上述過程，直到所有滿足條件的記錄全部參與排序

f 掃描排好序的 (id,col2) 對，并利用 id 去撈取 SELECT 需要返回的列 (col1,col2,col3)

g 將獲取的結(jié)果集返回給用戶。

從上述流程來看，是否使用文件排序主要看 sort buffer 是否能容下需要排序的 (id,col2) 對，這個 buffer 的大小由 sort_buffer_size 參數(shù)控制。此外一次排序需要兩次 IO，一次是撈 (id,col2), 第二次是撈 (col1,col2,col3)，由于返回的結(jié)果集是按 col2 排序，因此 id 是亂序的，通過亂序的 id 去撈 (col1,col2,col3) 時會產(chǎn)生大量的隨機 IO。對于第二次 MySQL 本身一個優(yōu)化，即在撈之前首先將 id 排序，并放入緩沖區(qū)，這個緩存區(qū)大小由參數(shù) read_rnd_buffer_size 控制，然后有序去撈記錄，將隨機 IO 轉(zhuǎn)為順序 IO。

2.2 優(yōu)化排序

常規(guī)排序方式除了排序本身，還需要額外兩次 IO。優(yōu)化的排序方式相對于常規(guī)排序，減少了第二次 IO。主要區(qū)別在于，放入 sort buffer 不是 (id,col2), 而是 (col1,col2,col3)。由于 sort buffer 中包含了查詢需要的所有字段，因此排序完成后可以直接返回，無需二次撈數(shù)據(jù)。這種方式的代價在于，同樣大小的 sort buffer，能存放的 (col1,col2,col3) 數(shù)目要小于 (id,col2)，如果 sort buffer 不夠大，可能導(dǎo)致需要寫臨時文件，造成額外的 IO。當(dāng)然 MySQL 提供了參數(shù) max_length_for_sort_data，只有當(dāng)排序元組小于 max_length_for_sort_data 時，才能利用優(yōu)化排序方式，否則只能用常規(guī)排序方式。

2.3 優(yōu)先隊列排序

為了得到最終的排序結(jié)果，無論怎樣，我們都需要將所有滿足條件的記錄進行排序才能返回。那么相對于優(yōu)化排序方式，是否還有優(yōu)化空間呢?5.6 版本針對 Order by limit M，N 語句，在空間層面做了優(yōu)化，加入了一種新的排序方式: 優(yōu)先隊列，這種方式采用堆排序?qū)崿F(xiàn)。堆排序算法特征正好可以解 limit M，N 這類排序的問題，雖然仍然需要所有元素參與排序，但是只需要 M+N 個元組的 sort buffer 空間即可，對于 M，N 很小的場景，基本不會因為 sort buffer 不夠而導(dǎo)致需要臨時文件進行歸并排序的問題。對于升序，采用大頂堆，最終堆中的元素組成了最小的 N 個元素，對于降序，采用小頂堆，最終堆中的元素組成了***的 N 的元素。

三 優(yōu)化

通過上面的原理分析，我們知道排序的本質(zhì)是通過一定的算法 (耗費 cpu 運算, 內(nèi)存, 臨時文件 IO) 將結(jié)果集變成有序的結(jié)果集。如何優(yōu)化呢?答案是分兩個方面利用索引的有序性 (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 

溫馨提示 ，各位看官要辯證的看待官方給的例子，自己多動手實踐。

無法利用到索引排序的情況，其實我覺得這是本文的重點，對于廣大開發(fā)同學(xué)而言，記住那種不能利用索引排序會更簡單些。

1. 最常見的情況 用來查找結(jié)果的索引 (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 的關(guān)聯(lián)查詢，排序字段并非全部來自于***個表，使用 explain 查看執(zhí)行計劃***個表 type 值不是 const 。

當(dāng)無法避免排序操作時, 又該如何來優(yōu)化呢?很顯然, 優(yōu)先選擇 using index 的排序方式，在無法滿足利用索引排序的情況下，盡可能讓 MySQL 選擇使用第二種單路算法來進行排序。這樣可以減少大量的隨機 IO 操作, 很大幅度地提高排序的效率。

1. 加大 max_length_for_sort_data 參數(shù)的設(shè)置

在 MySQL 中, 決定使用老式排序算法還是改進版排序算法是通過參數(shù) max_length_for_sort_data 來決定的。當(dāng)所有返回字段的***長度小于這個參數(shù)值時, MySQL 就會選擇改進后的排序算法, 反之, 則選擇老式的算法。所以, 如果有充足的內(nèi)存讓 MySQL 存放須要返回的非排序字段, 就可以加大這個參數(shù)的值來讓 MySQL 選擇使用改進版的排序算法。

2. 去掉不必要的返回字段

當(dāng)內(nèi)存不是很充裕時, 不能簡單地通過強行加大上面的參數(shù)來強迫 MySQL 去使用改進版的排序算法, 否則可能會造成 MySQL 不得不將數(shù)據(jù)分成很多段, 然后進行排序, 這樣可能會得不償失。此時就須要去掉不必要的返回字段, 讓返回結(jié)果長度適應(yīng) max_length_for_sort_data 參數(shù)的限制。

同時也要規(guī)范 MySQL 開發(fā)規(guī)范，盡量避免大字段。當(dāng)有 select 查詢列含有大字段 blob 或者 text 的時候, MySQL 會選擇常規(guī)排序。

" 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 參數(shù)設(shè)置

這個值如果過小的話, 再加上你一次返回的條數(shù)過多, 那么很可能就會分很多次進行排序, 然后***將每次的排序結(jié)果再串聯(lián)起來, 這樣就會更慢, 增大 sort_buffer_size 并不是為了讓 MySQL 選擇改進版的排序算法, 而是為了讓 MySQL 盡量減少在排序過程中對須要排序的數(shù)據(jù)進行分段, 因為分段會造成 MySQL 不得不使用臨時表來進行交換排序。但是這個值不是越大越好：

1. sort_buffer_size 是一個 connection 級參數(shù), 在每個 connection ***次需要使用這個 buffer 的時候, 一次性分配設(shè)置的內(nèi)存。

2. sort_buffer_size 并不是越大越好, 由于是 connection 級的參數(shù), 過大的設(shè)置 + 高并發(fā)可能會耗盡系統(tǒng)內(nèi)存資源。

3. 據(jù)說 sort_buffer_size 超過 2M 的時候, 就會使用 mmap() 而不是 malloc() 來進行內(nèi)存分配, 導(dǎo)致效率降低。

四 參考文章

[1] MySQL order by 調(diào)優(yōu)官方文檔

[2] MySQL 排序原理與案例分析

[3] 淘寶 MySQL 月報