排序這個(gè)詞牺六，我的第一感覺(jué)是幾乎所有App都有排序的地方陈莽，淘寶商品有按照購(gòu)買(mǎi)時(shí)間的排序键闺、B站的評(píng)論有按照熱度排序的...寿烟，當(dāng)然我們今天說(shuō)的并不是大數(shù)據(jù)下該如何優(yōu)雅的排序，如何提升排序性能的問(wèn)題辛燥，我們說(shuō)一說(shuō)MySQL中的排序筛武。
對(duì)于MySQL，一說(shuō)到排序挎塌，你第一時(shí)間想到的是什么徘六？關(guān)鍵字order by？order by的字段最好有索引榴都？葉子結(jié)點(diǎn)已經(jīng)是順序的待锈？還是說(shuō)盡量不要在MySQL內(nèi)部排序？
事情的起因
現(xiàn)在假設(shè)有一張用戶(hù)的朋友表：
CREATE TABLE `user` (
`id` int(10) AUTO_INCREMENT,
`user_id` int(10),
`friend_addr` varchar(1000),
`friend_name` varchar(100),
PRIMARY KEY (`id`),
KEY `user_id` (`user_id`)
) ENGINE=InnoDB;
表中目前有兩個(gè)點(diǎn)需要關(guān)注下：
- 用戶(hù)的 user_id 嘴高，朋友的姓名 friend_name 竿音、朋友的地址 friend_addr
- user_id 是有 索引 的
有一天，有個(gè)初級(jí)開(kāi)發(fā)工程師小猿拴驮，收到了來(lái)自初級(jí)產(chǎn)品經(jīng)理小汪的需求：
小汪 ：小猿同志春瞬，現(xiàn)在需要在后臺(tái)加個(gè)功能，這個(gè)功能要支持根據(jù)用戶(hù) id 能查到他所有的朋友姓名和地址套啤，并且要求朋友的姓名是按照字典排序的宽气。
小猿
：好的，這個(gè)功能簡(jiǎn)單，我馬上就上線抹竹。
于是小猿書(shū)寫(xiě)了這樣的sql：
select friend_name线罕，friend_addr from user where user_id=? order by name
在電光石火的瞬間止潮，小猿趾高氣昂的上線了窃判，這一切都很順利，直到有一天有個(gè)運(yùn)營(yíng)同學(xué)導(dǎo)致了這樣的查詢(xún)：
select friend_name喇闸，friend_addr from user where user_id=10086 order by name
然而袄琳，這個(gè)查詢(xún)竟然比平時(shí)慢很多，數(shù)據(jù)庫(kù)報(bào)了慢查詢(xún)燃乍，小猿此時(shí)慌的一b：這是怎么回事唆樊？user_id 明明有索引啊，而且機(jī)智地我還只用了 select friend_name,friend_addr刻蟹，并沒(méi)有用 select *呀逗旁。小猿此時(shí)不停地安慰自己，要淡定要淡定舆瘪，然后突然想到有個(gè)explain命令片效，用explain來(lái)查看下那條sql的執(zhí)行計(jì)劃吧，當(dāng)小猿用了explain之后英古，發(fā)現(xiàn)extra字段里面有個(gè)看起來(lái)很危險(xiǎn)的字眼： using filesort 淀衣。
“這個(gè)查詢(xún)竟然用到了傳說(shuō)中的文件排序，但是如果一個(gè)人朋友不是很多召调，就算了用了文件排序膨桥，應(yīng)該也很快吧”，除非這個(gè)user_id=10086的朋友很多唠叛，后來(lái)小猿去查了下只嚣，這個(gè)用戶(hù)的朋友竟然有10w多個(gè)～。
陷入了沉思的小猿心想：這個(gè)鍋看來(lái)是背定了艺沼，10w數(shù)據(jù)是有點(diǎn)大了介牙，還有這個(gè) using filesort 到底是怎么個(gè)排序原理？
解剖文件排序
有人可能說(shuō)上面的問(wèn)題是10w數(shù)據(jù)太大了澳厢，就算不排序也慢环础，這個(gè)其實(shí)是有道理的，10w數(shù)據(jù)一次性查出來(lái)剩拢，無(wú)論是MySQL內(nèi)存緩沖區(qū)的占用线得，還是網(wǎng)絡(luò)帶寬的消耗都是非常大的，那如果我加了limit 1000呢徐伐？網(wǎng)絡(luò)帶寬的問(wèn)題肯定是解決了贯钩，因?yàn)閿?shù)據(jù)包整體變小了，但是 using filesort 的問(wèn)題其實(shí)還是沒(méi)有解決，看到這里你可能會(huì)有疑問(wèn)角雷，using filesort 難道是在文件中排序的祸穷？在文件中到底是怎么排序的？或者我這樣問(wèn)：如果給你來(lái)設(shè)計(jì)排序你會(huì)怎么處理勺三？帶著這些疑問(wèn)和思考我們來(lái)看看 using filesort 會(huì)涉及到哪些技術(shù)難點(diǎn)以及是如何解決的雷滚？
- 首先我們的 user_id 是有索引的，所以會(huì)先在 user_id 索引樹(shù)上檢索我們的目標(biāo)數(shù)據(jù)吗坚，即 user_id=10086 的數(shù)據(jù)祈远，但是我們要查詢(xún)的是 friend_name 和 friend_addr 字段，很不幸商源，光靠 user_id 索引是找不到這兩個(gè)字段值的
- 于是需要回表车份，通過(guò) user_id 對(duì)應(yīng)的主鍵去主鍵索引樹(shù)上去查找，ok牡彻，我們找到了第一條 user_id=10086 的 friend_name 和 friend_addr 字段
- 這時(shí)該怎么辦扎附？直接返回回去肯定不對(duì)怀酷，因?yàn)槲倚枰獙?duì) friend_name 排序，如何排？數(shù)據(jù)都還沒(méi)找全钦讳，那么就得把查到的數(shù)據(jù)先放在一個(gè)地方囱桨，這個(gè)地方就是 sort_buffer 膛檀，看到名字我想你應(yīng)該猜出來(lái)芒粹，沒(méi)錯(cuò)，sort_buffer 就是用于這種情況下排序用的緩沖區(qū)废菱，這里需要注意的是每個(gè)線程都會(huì)有一個(gè)單獨(dú)的 sort_buffer技矮，這么做的目的主要是為了避免多個(gè)線程對(duì)同一塊內(nèi)存進(jìn)行操作帶來(lái)鎖競(jìng)爭(zhēng)的問(wèn)題。
- 當(dāng)?shù)谝粭l數(shù)據(jù)的 friend_name 和 friend_addr 已經(jīng)放入 sort_buffer 中殊轴，這當(dāng)然沒(méi)完衰倦，會(huì)一直重復(fù)同步的步驟，直至把所有 user_id=10086 的 friend_name 和 friend_addr 都放入到 sort_buffer 中才結(jié)束
- sort_buffer 中的數(shù)據(jù)已經(jīng)放入完畢旁理，接下來(lái)就該排序了樊零，這里 MySQL 會(huì)對(duì) friend_name 進(jìn)行快排，通過(guò)快排后孽文，sort_buffer 中 friend_name 就是有序的了
- 最后返回 sort_buffer 中的前1000條驻襟，結(jié)束。
一切看起來(lái)很絲滑芋哭，但是 sort_buffer 占用的是內(nèi)存空間沉衣，這就尷尬了，內(nèi)存本身就不是無(wú)限大的减牺，它肯定是有上限的豌习，當(dāng)然 sort_buffer 也不能太小存谎，太小的話(huà)，意義不大肥隆。在 InnoDB 存儲(chǔ)引擎中既荚，這個(gè)值是默認(rèn)是256K。
mysql> show variables like 'sort_buffer_size';
+------------------+--------+
| Variable_name | Value |
+------------------+--------+
| sort_buffer_size | 262144 |
+------------------+--------+
也就是說(shuō)栋艳，如果要放進(jìn) sort_buffer 中的數(shù)據(jù)是大于256K的話(huà)恰聘，那么采用在 sort_buffer 中快排的方式肯定是行不通的，這時(shí)候嘱巾，你可能會(huì)問(wèn)：MySQL難道不能根據(jù)數(shù)據(jù)大小自動(dòng)擴(kuò)充嗎憨琳？額诫钓，MySQL是多線程模型旬昭，如果每個(gè)線程都擴(kuò)充，那么分給其他功能buffer就小了（比如change buffer等）菌湃，就會(huì)影響其他功能的質(zhì)量问拘。
這時(shí)就得換種方式來(lái)排序了，沒(méi)錯(cuò)惧所，此時(shí)就是真正的文件排序了骤坐，也就是磁盤(pán)的臨時(shí)文件，MySQL會(huì)采用歸并排序的思想下愈，把要排序的數(shù)據(jù)分成若干份纽绍，每一份數(shù)據(jù)在內(nèi)存中排序后會(huì)放入臨時(shí)文件中，最終對(duì)這些已經(jīng)排序好的臨時(shí)文件的數(shù)據(jù)再做一次合并排序就ok了势似，典型的分而治之原理拌夏，它的具體步驟如下：
- 先將要排序的數(shù)據(jù)分割，分割成每塊數(shù)據(jù)都可以放到 sort_buffer 中
- 對(duì)每塊數(shù)據(jù)在 sort_buffer 中進(jìn)行排序履因，排序好后障簿，寫(xiě)入某個(gè)臨時(shí)文件中
- 當(dāng)所有的數(shù)據(jù)都寫(xiě)入臨時(shí)文件后，這時(shí)對(duì)于每個(gè)臨時(shí)文件而言栅迄，內(nèi)部都是有序的站故，但是它們并不是一個(gè)整體，整體還不是有序的毅舆，所以接下來(lái)就得合并數(shù)據(jù)了
- 假設(shè)現(xiàn)在存在 tmpX 和 tmpY 兩個(gè)臨時(shí)文件西篓，這時(shí)會(huì)從 tmpX 讀取一部分?jǐn)?shù)據(jù)進(jìn)入內(nèi)存，然后從 tmpY 中讀取一部分?jǐn)?shù)據(jù)進(jìn)入內(nèi)存憋活，這里你可能會(huì)好奇為什么是一部分而不是整個(gè)或者單個(gè)岂津？因?yàn)槭紫却疟P(pán)是緩慢的，所以盡量每次多讀點(diǎn)數(shù)據(jù)進(jìn)入內(nèi)存余掖，但是不能讀太多寸爆，因?yàn)檫€有 buffer 空間的限制礁鲁。
- 對(duì)于 tmpX 假設(shè)讀進(jìn)來(lái)了的是 tmpX[0-5] ,對(duì)于 tmpY 假設(shè)讀進(jìn)來(lái)了的是 tmpY[0-5]，于是只需要這樣比較：如果 tmpX[0] < tmpY[0]赁豆，那么 tmpX[0] 肯定是最小的仅醇，然后 tmpX[1] 和 tmpY[0] 比如，如果 tmpX[1] > tmpY[0]魔种，那么 tmpY[0] 肯定是第二小的...析二，就這樣兩兩比較最終就可以把 tmpX 和 tmpY 合并成一個(gè)有序的文件tmpZ，多個(gè)這樣的tmpZ再次合并...节预，最終就可以把所有的數(shù)據(jù)合并成一個(gè)有序的大文件叶摄。
文件排序很慢，還有其他辦法嗎
通過(guò)上面的排序流程我們知道安拟，如果要排序的數(shù)據(jù)很大蛤吓，超過(guò) sort_buffer 的大小，那么就需要文件排序糠赦，文件排序涉及到分批排序與合并会傲，很耗時(shí)，造成這個(gè)問(wèn)題的根本原因是 sort_buffer 不夠用 拙泽，不知道你發(fā)現(xiàn)沒(méi)有我們的 friend_name 需要排序淌山，但是卻把 friend_addr 也塞進(jìn)了 sort_buffer 中，這樣 單行數(shù)據(jù)的大小就等于 friend_name 的長(zhǎng)度 + friend_addr 的長(zhǎng)度 顾瞻，能否讓 sort_buffer 中只存 friend_name 字段泼疑，這樣的話(huà)，整體的利用空間就大了荷荤，不一定用得到到臨時(shí)文件退渗。沒(méi)錯(cuò)，這就是接下來(lái)要說(shuō)的另一種排序優(yōu)化 rowid排序 梅猿。
rowid 排序的思想就是把不需要的數(shù)據(jù)不要放到 sort_buffer 中氓辣，讓 sort_buffer 中只保留必要的數(shù)據(jù)，那么你認(rèn)為什么是必要的數(shù)據(jù)呢袱蚓？只放 friend_name钞啸？這肯定不行，排序完了之后喇潘，friend_addr 怎么辦体斩？因此還要把主鍵id放進(jìn)去，這樣排完之后颖低，通過(guò) id 再回次表絮吵，拿到 friend_addr 即可，因此它的大致流程如下：
- 根據(jù) user_id 索引忱屑，查到目標(biāo)數(shù)據(jù)蹬敲，然后回表暇昂，只把 id 和 friend_name 放進(jìn) sort_buffer 中
- 重復(fù)1步驟，直至全部的目標(biāo)數(shù)據(jù)都在 sort_buffer 中
- 對(duì) sort_buffer 中的數(shù)據(jù)按照 friend_name 字段進(jìn)行排序
- 排序后根據(jù) id 再次回表查到 friend_addr 返回伴嗡，直至返回1000條數(shù)據(jù)急波，結(jié)束。
這里面其實(shí)有幾點(diǎn)需要注意的：
- 這種方式需要兩次回表的
- sort_buffer 雖然小了瘪校，但是如果數(shù)據(jù)量本身還是很大澄暮，應(yīng)該還是要臨時(shí)文件排序的
那么問(wèn)題來(lái)了，兩種方式阱扬，MySQL 該如何選擇泣懊？得根據(jù)某個(gè)條件來(lái)判斷走哪種方式吧，這個(gè)條件就是進(jìn) sort_buffer 單行的長(zhǎng)度麻惶，如果長(zhǎng)度太大（friend_name + friend_addr的長(zhǎng)度）馍刮，就會(huì)采用 rowid 這種方式，否則第一種用踩，長(zhǎng)度的標(biāo)準(zhǔn)是根據(jù) max_length_for_sort_data 來(lái)的渠退，這個(gè)值默認(rèn)是1024字節(jié)：
mysql> show variables like 'max_length_for_sort_data';
+--------------------------+-------+
| Variable_name | Value |
+--------------------------+-------+
| max_length_for_sort_data | 1024 |
+--------------------------+-------+
不想回表忙迁，不想再次排序
其實(shí)不管是上面哪種方法脐彩，他們都需要 回表 + 排序 ，回表是因?yàn)槎?jí)索引上沒(méi)有目標(biāo)字段姊扔，排序是因?yàn)閿?shù)據(jù)不是有序的惠奸，那如果二級(jí)索引上有目標(biāo)字段并且已經(jīng)是排序好的了，那不就兩全其美了嘛恰梢。
沒(méi)錯(cuò)佛南，就是聯(lián)合索引，我們只需要建立一個(gè) （user_id嵌言，friend_name嗅回，friend_addr）的聯(lián)合索引即可，這樣我就可以通過(guò)這個(gè)索引拿到目標(biāo)數(shù)據(jù)摧茴，并且friend_name已經(jīng)是排序好的绵载，同時(shí)還有friend_addr字段，一招搞定苛白，不需要回表娃豹，不需要再次排序。因此對(duì)于上述的sql购裙，它的大致流程如下：
- 通過(guò)聯(lián)合索引找到user_id=10086的數(shù)據(jù)懂版，然后讀取對(duì)應(yīng)的 friend_name 和 friend_addr 字段直接返回，因?yàn)?friend_name 已經(jīng)是排序好的了躏率，不需要額外處理
- 重復(fù)第一步驟躯畴，順著葉子節(jié)點(diǎn)接著向后找民鼓，直至找到第一個(gè)不是10086的數(shù)據(jù)，結(jié)束蓬抄。
聯(lián)合索引雖然可以解決這種問(wèn)題摹察，但是在實(shí)際應(yīng)用中切不可盲目建立，要根據(jù)實(shí)際的業(yè)務(wù)邏輯來(lái)判斷是否需要建立倡鲸，如果不是經(jīng)常有類(lèi)似的查詢(xún)供嚎，可以不用建立，因?yàn)槁?lián)合索引會(huì)占用更多的存儲(chǔ)空間和維護(hù)開(kāi)銷(xiāo)峭状。
總結(jié)
- 對(duì)于 order by 沒(méi)有用到索引的時(shí)候克滴，這時(shí) explain 中 Extra 字段大概是會(huì)出現(xiàn) using filesort 字眼
- 出現(xiàn) using filesort 的時(shí)候也不用太慌張，如果本身數(shù)據(jù)量不大优床，比如也就幾十條數(shù)據(jù)劝赔，那么在 sort buffer 中使用快排也是很快的
- 如果數(shù)據(jù)量很大，超過(guò)了 sort buffer 的大小胆敞，那么是要進(jìn)行臨時(shí)文件排序的着帽，也就是歸并排序，這部分是由 MySQL 優(yōu)化器決定的
- 如果查詢(xún)的字段很多移层，想要盡量避免使用臨時(shí)文件排序仍翰，可以嘗試設(shè)置下 max_length_for_sort_data 字段的大小，讓其小于所有查詢(xún)字段長(zhǎng)度的總和观话，這樣放入或許可以避免予借，但是會(huì)多一次回表操作
- 實(shí)際業(yè)務(wù)中，我們也可以給經(jīng)常要查詢(xún)的字段組合建立個(gè)聯(lián)合索引频蛔，這樣既不用回表也不需要單獨(dú)排序灵迫，但是聯(lián)合索引會(huì)占用更多的存儲(chǔ)和開(kāi)銷(xiāo)
- 大量數(shù)據(jù)查詢(xún)的時(shí)候，盡量分批次晦溪，提前 explain 來(lái)觀察 sql 的執(zhí)行計(jì)劃是個(gè)不錯(cuò)的選擇瀑粥。
