一 簡(jiǎn)介

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

二 原理

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

2.1 常規(guī)排序

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

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

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

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

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

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

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

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

2.2 優(yōu)化排序

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

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

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

三 優(yōu)化

通過(guò)上面的原理分析，我們知道排序的本質(zhì)是通過(guò)一定的算法 (耗費(fèi) cpu 運(yùn)算, 內(nèi)存, 臨時(shí)文件 IO) 將結(jié)果集變成有序的結(jié)果集。如何優(yōu)化呢?答案是分兩個(gè)方面利用索引的有序性 (MySQL 的 B+ 樹索引是默認(rèn)從小到大遞增排序) 減少排序, ***的方式是直接不排序。

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 

溫馨提示 ，各位看官要辯證的看待官方給的例子，自己多動(dòng)手實(shí)踐。

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

1. 最常見的情況 用來(lái)查找結(jié)果的索引 (key2) 和 排序的索引 (key1) 不一樣,where a=x and b=y order by id;

SELECT * FROM t1 WHERE key2=constant ORDER BY key1; 

2. 排序字段在不同的索引中，無(wú)法使用索引排序

SELECT * FROM t1 ORDER BY key1,key2; 

3. 排序字段順序與索引中列順序不一致，無(wú)法使用索引排序，比如索引是 key idx_kp1_kp2(key_part1,key_part2)

SELECT * FROM t1 ORDER BY key_part2, key_part1; 

4. order by 中的升降序和索引中的默認(rèn)升降不一致，無(wú)法使用索引排序

SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC; 

5. ey_part1 是范圍查詢，key_part2 無(wú)法使用索引排序

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. 索引本身是無(wú)序存儲(chǔ)的，比如 hash 索引，不能利用索引的有序性。

7. order by 字段只被索引了前綴 ，key idx_col(col(10))

select * from t1 order by col ; 

8. 對(duì)于還有 join 的關(guān)聯(lián)查詢，排序字段并非全部來(lái)自于***個(gè)表，使用 explain 查看執(zhí)行計(jì)劃***個(gè)表 type 值不是 const 。

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

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

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

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

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

同時(shí)也要規(guī)范 MySQL 開發(fā)規(guī)范，盡量避免大字段。當(dāng)有 select 查詢列含有大字段 blob 或者 text 的時(shí)候, MySQL 會(huì)選擇常規(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è)置

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

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

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

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

四 參考文章

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

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

[3] 淘寶 MySQL 月報(bào)