一 簡介 偏向于業(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 排序的原理之前，強(qiáng)烈安利兩篇關(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)對，則進(jìn)行排序；否則sort buffer滿后，進(jìn)行排序并固化到臨時文件中。(排序算法采用的是快速排序算法)
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)生大量的隨機(jī)IO。對于第二次MySQL本身一個優(yōu)化，即在撈之前首先將id排序，并放入緩沖區(qū)，這個緩存區(qū)大小由參數(shù)read_rnd_buffer_size控制，然后有序去撈記錄，將隨機(jī)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é)果，無論怎樣，我們都需要將所有滿足條件的記錄進(jìn)行排序才能返回。那么相對于優(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)致需要臨時文件進(jìn)行歸并排序的問題。對于升序，采用大頂堆，最終堆中的元素組成了最小的N個元素，對于降序，采用小頂堆，最終堆中的元素組成了最大的N的元素。
三 優(yōu)化 通過上面的原理分析，我們知道排序的本質(zhì)是通過一定的算法(耗費cpu 運算,內(nèi)存,臨時文件IO)將結(jié)果集變成有序的結(jié)果集。如何優(yōu)化呢？答案是分兩個方面利用索引的有序性(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
溫馨提示 ，各位看官要辯證的看待官方給的例子，自己多動手實踐。
無法利用到索引排序的情況，其實我覺得這是本文的重點，對于廣大開發(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中的升降序和索引中的默認(rèn)升降不一致，無法使用索引排序
-
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 選擇使用第二種單路算法來進(jìn)行排序。這樣可以減少大量的隨機(jī)IO操作,很大幅度地提高排序的效率。
1 加大 max_length_for_sort_data 參數(shù)的設(shè)置
在 MySQL 中,決定使用老式排序算法還是改進(jìn)版排序算法是通過參數(shù)max_length_for_sort_data來決定的。當(dāng)所有返回字段的最大長度小于這個參數(shù)值時,MySQL 就會選擇改進(jìn)后的排序算法,反之,則選擇老式的算法。所以,如果有充足的內(nèi)存讓MySQL 存放須要返回的非排序字段,就可以加大這個參數(shù)的值來讓 MySQL 選擇使用改進(jìn)版的排序算法。
2 去掉不必要的返回字段
當(dāng)內(nèi)存不是很充裕時,不能簡單地通過強(qiáng)行加大上面的參數(shù)來強(qiáng)迫 MySQL 去使用改進(jìn)版的排序算法,否則可能會造成 MySQL 不得不將數(shù)據(jù)分成很多段,然后進(jìn)行排序,這樣可能會得不償失。此時就須要去掉不必要的返回字段,讓返回結(jié)果長度適應(yīng) max_length_for_sort_data 參數(shù)的限制。
同時也要規(guī)范MySQL開發(fā)規(guī)范，盡量避免大字段。當(dāng)有select 查詢列含有大字段blob或者text 的時候,MySQL 會選擇常規(guī)排序。
"The optimizer selects which filesort algorithm to use. It normally uses the modified algorithm except when BLOB or TEXT columns are involved, in which case it uses the original algorithm."
3 增大 sort_buffer_size 參數(shù)設(shè)置
這個值如果過小的話,再加上你一次返回的條數(shù)過多,那么很可能就會分很多次進(jìn)行排序,然后最后將每次的排序結(jié)果再串聯(lián)起來,這樣就會更慢,增大 sort_buffer_size 并不是為了讓 MySQL選擇改進(jìn)版的排序算法,而是為了讓MySQL盡量減少在排序過程中對須要排序的數(shù)據(jù)進(jìn)行分段,因為分段會造成 MySQL 不得不使用臨時表來進(jìn)行交換排序。但是這個值不是越大越好：
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() 來進(jìn)行內(nèi)存分配,導(dǎo)致效率降低。
四 參考文章[1]MySQL order by 調(diào)優(yōu)官方文檔
[2]MySQL排序原理與案例分析
[3]淘寶MySQL 月報
本文的原理分析部分 采取偷懶策略，直接從我的前同事 雁閑 的博客[2]摘抄了，強(qiáng)烈安利 雁閑的
博客 ，MySQL 源碼研究者，精通MySQL 業(yè)務(wù)和底層運維。
分享標(biāo)題：【MySQL】orderby原理以及優(yōu)化
網(wǎng)頁路徑：
http://weahome.cn/article/ppjjod.html
重慶分公司
重慶分公司
