不經(jīng)一番寒徹骨，怎得梅花撲鼻香閱讀這篇文章大概需要20分鐘！

大家好前面我們了解了count(*)的一些實(shí)現(xiàn)方式。今天我們介紹一下order by的實(shí)現(xiàn)方式以及內(nèi)部的涉及到的知識(shí)點(diǎn)。

常規(guī)排序

先準(zhǔn)備一些案例，假設(shè)我們的表是這樣的。

CREATE TABLE `t` (
	`id` INT ( 11 ) NOT NULL,
	`city` VARCHAR ( 16 ) NOT NULL,
	`name` VARCHAR ( 16 ) NOT NULL,
	`age` INT ( 11 ) NOT NULL,
	`addr` VARCHAR ( 128 ) DEFAULT NULL,
PRIMARY KEY ( `id` ),
KEY `city` ( `city` )) ENGINE = INNODB;

根據(jù)上述表結(jié)構(gòu)，我們執(zhí)行以下SQL

select city,name,age from t where city='杭州' order by name limit 1000  ;

這個(gè)SQL我相信很多人都是用的非常熟練了。那么我們今天講一些內(nèi)部是如何實(shí)現(xiàn)的。

先從丁奇老師那邊借鑒一下圖

從圖中可以看到，滿足 city='杭州’條件的行，是從 ID_X 到 ID_(X+N) 的這些記錄。

那么它的執(zhí)行流程就是

因?yàn)槭切枰判虻模孕枰跏蓟痵ort_buffer，這個(gè)sort_buffer就是用來存放數(shù)據(jù)的（放入需要排序的字段，上文中是 name，city，age）
從索引city上找到每一個(gè)滿足 city='杭州' 的id，就是上文的ID_X
然后再通過ID_X去主鍵索引樹上尋找對(duì)應(yīng)的ID_X的整行數(shù)據(jù)（name，city，age）存入sort_buffer
再回到索引city上繼續(xù)尋找city='杭州' 的ID
循環(huán)重復(fù)的執(zhí)行3,4步驟，直到不滿足條件退出
退出后對(duì)sort_buffer中的數(shù)據(jù)按照字段name做快速排序（也就order by 后面的字段）
最后就是返回1000行數(shù)據(jù)。如果沒有limit 1000 的話就是全部返回，下圖就是流程圖

sort_buffer_size

MySQL考慮了在排序的性能上做了如下的優(yōu)化。通過一個(gè)參數(shù)做分界值。如果低于這個(gè)分界值就采用在內(nèi)存中完成排序。如果高于分界值就采用在磁盤中完成排序操作。因?yàn)閿?shù)據(jù)足夠大內(nèi)存顯然是不夠用的，然后還會(huì)影響其他SQL。

可以用下面介紹的方法，來確定一個(gè)排序語句是否使用了臨時(shí)文件。

/* 打開optimizer_trace，只對(duì)本線程有效 */
SET optimizer_trace='enabled=on'; 

/* @a保存Innodb_rows_read的初始值 */
select VARIABLE_VALUE into @a from  performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 執(zhí)行語句 */
select city, name,age from t where city='杭州' order by name limit 1000; 

/* 查看 OPTIMIZER_TRACE 輸出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G

/* @b保存Innodb_rows_read的當(dāng)前值 */
select VARIABLE_VALUE into @b from performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 計(jì)算Innodb_rows_read差值 */
select @b-@a;

執(zhí)行上述SQL可得到

number_of_tmp_files

通過該參數(shù)可以得到是否使用了臨時(shí)文件，并且使用了多少臨時(shí)文件。

由圖得知 MySQL 將需要排序的數(shù)據(jù)分成 12 份，每一份單獨(dú)排序后存在這些臨時(shí)文件中。然后把這 12 個(gè)有序文件再合并成一個(gè)有序的大文件。

如果sort_buffer_size大于需要排序的數(shù)據(jù)量，number_of_tmp_files就為對(duì)應(yīng)的分頁數(shù)，如果小于，number_of_tmp_files就為0。sort_buffer_size 越小，需要分成的份數(shù)越多，number_of_tmp_files 的值就越大。

examined_rows

examined_rows=4000，表示參與排序的行數(shù)是 4000 行。

packed_additional_fields

sort_mode 里面的 packed_additional_fields 的意思是，排序過程對(duì)字符串做了“緊湊”處理。即使 name 字段的定義是 varchar(16)，在排序過程中還是要按照實(shí)際長(zhǎng)度來分配空間的。

同時(shí)，最后一個(gè)查詢語句 select @b-@a 的返回結(jié)果是 4000，表示整個(gè)執(zhí)行過程只掃描了 4000 行。

這里介紹一下innodb與myisam的差別。

為了避免對(duì)結(jié)論造成干擾，我把 internal_tmp_disk_storage_engine 設(shè)置成 MyISAM。否則，select @b-@a 的結(jié)果會(huì)顯示為 4001。這是因?yàn)椴樵?OPTIMIZER_TRACE 這個(gè)表時(shí)，需要用到臨時(shí)表，而 internal_tmp_disk_storage_engine 的默認(rèn)值是 InnoDB。如果使用的是 InnoDB 引擎的話，把數(shù)據(jù)從臨時(shí)表取出來的時(shí)候，會(huì)讓 Innodb_rows_read 的值加 1。

rowid 排序

上述流程只對(duì)原表的數(shù)據(jù)讀了一遍，剩下的操作都是在 sort_buffer 和臨時(shí)文件中執(zhí)行的。但這個(gè)算法有一個(gè)問題，就是如果查詢要返回的字段很多的話，那么 sort_buffer 里面要放的字段數(shù)太多，這樣內(nèi)存里能夠同時(shí)放下的行數(shù)很少，要分成很多個(gè)臨時(shí)文件，排序的性能會(huì)很差。

所以如果單行很大，這個(gè)方法效率不夠好。

max_length_for_sort_data

接下來，就用上這個(gè)參數(shù)了。max_length_for_sort_data

max_length_for_sort_data，是 MySQL 中專門控制用于排序的行數(shù)據(jù)的長(zhǎng)度的一個(gè)參數(shù)。它的意思是，如果單行的長(zhǎng)度超過這個(gè)值，MySQL 就認(rèn)為單行太大，要換一個(gè)算法。

city，name，age這三個(gè)字段的長(zhǎng)度大小為36，如果把max_length_for_sort_data設(shè)置成16，那么放入sort_buffer的只是name與主鍵id。排序的結(jié)果就因?yàn)樯倭?city 和 age 字段的值，不能直接返回了，整個(gè)執(zhí)行流程就變成如下所示的樣子：

初始化 sort_buffer，確定放入兩個(gè)字段，即 name 和 id；
從索引 city 找到第一個(gè)滿足 city='杭州’條件的主鍵 id，也就是圖中的 ID_X；
到主鍵 id 索引取出整行，取 name、id 這兩個(gè)字段，存入 sort_buffer 中；
從索引 city 取下一個(gè)記錄的主鍵 id；
重復(fù)步驟 3、4 直到不滿足 city='杭州’條件為止，也就是圖中的 ID_Y；
對(duì) sort_buffer 中的數(shù)據(jù)按照字段 name 進(jìn)行排序
遍歷排序結(jié)果，取前 1000 行，并按照 id 的值回到原表中取出 city、name 和 age 三個(gè)字段返回給客戶端。如下圖

對(duì)比第一個(gè)算法，rowid排序多了一步回表操作。所以

examined_rows 的值還是 4000，表示用于排序的數(shù)據(jù)是 4000 行。但是 select @b-@a 這個(gè)語句的值變成 5000。因?yàn)檫@時(shí)候除了排序過程外，在排序完成后，還要根據(jù) id 去原表取值。由于語句是 limit 1000，因此會(huì)多讀 1000 行。

sort_mode也變成了sort_key, rowid ，表示參與排序的只有 name 和 id 這兩個(gè)字段。

number_of_tmp_files 變成 10 了，是因?yàn)檫@時(shí)候參與排序的行數(shù)雖然仍然是 4000 行，但是每一行都變小了，因此需要排序的總數(shù)據(jù)量就變小了，需要的臨時(shí)文件也相應(yīng)地變少了。

常規(guī)排序 VS rowid 排序

如果 MySQL 實(shí)在是擔(dān)心排序內(nèi)存太小，會(huì)影響排序效率，才會(huì)采用 rowid 排序算法，這樣排序過程中一次可以排序更多行，但是需要再回到原表去取數(shù)據(jù)。
如果 MySQL 認(rèn)為內(nèi)存足夠大，會(huì)優(yōu)先選擇全字段排序，把需要的字段都放到 sort_buffer 中，這樣排序后就會(huì)直接從內(nèi)存里面返回查詢結(jié)果了，不用再回到原表去取數(shù)據(jù)。

這也就體現(xiàn)了 MySQL 的一個(gè)設(shè)計(jì)思想：如果內(nèi)存夠，就要多利用內(nèi)存，盡量減少磁盤訪問。

對(duì)于 InnoDB 表來說，rowid 排序會(huì)要求回表多造成磁盤讀，因此不會(huì)被優(yōu)先選擇。

介紹了那么多。應(yīng)該也了解了MySQL 做排序是一個(gè)成本比較高的操作。那么你會(huì)問，是不是所有的 order by 都需要排序操作呢？如果不排序就能得到正確的結(jié)果，那對(duì)系統(tǒng)的消耗會(huì)小很多，語句的執(zhí)行時(shí)間也會(huì)變得更短。

所有order by都需要排序嗎？

答案肯定是錯(cuò) 的。并不是所有的order by都需要排序。之所以需要排序是因?yàn)樯厦姹碇械臄?shù)據(jù)是無序的，如果表中是有序的不就不需要排序了嘛！

你可以設(shè)想下，如果能夠保證從 city 這個(gè)索引上取出來的行，天然就是按照 name 遞增排序的話，是不是就可以不用再排序了呢？

確實(shí)是這樣的。所以，我們可以在這個(gè)市民表上創(chuàng)建一個(gè) city 和 name 的聯(lián)合索引，對(duì)應(yīng)的 SQL 語句是：

alter table t add index city_user(city, name);

再借鑒一下丁奇老師的圖

在這個(gè)索引里面，我們依然可以用樹搜索的方式定位到第一個(gè)滿足 city='杭州’的記錄，并且額外確保了，接下來按順序取“下一條記錄”的遍歷過程中，只要 city 的值是杭州，name 的值就一定是有序的。

這樣整個(gè)查詢過程的流程就變成了：

從索引 (city,name) 找到第一個(gè)滿足 city='杭州’條件的主鍵 id；
到主鍵 id 索引取出整行，取 name、city、age 三個(gè)字段的值，作為結(jié)果集的一部分直接返回；
從索引 (city,name) 取下一個(gè)記錄主鍵 id；
重復(fù)步驟 2、3，直到查到第 1000 條記錄，或者是不滿足 city='杭州’條件時(shí)循環(huán)結(jié)束。

可以看到，這個(gè)查詢過程不需要臨時(shí)表，也不需要排序。接下來，我們用 explain 的結(jié)果來印證一下。

從圖中可以看到，Extra 字段中沒有 Using filesort 了，也就是不需要排序了。而且由于 (city,name) 這個(gè)聯(lián)合索引本身有序，所以這個(gè)查詢也不用把 4000 行全都讀一遍，只要找到滿足條件的前 1000 條記錄就可以退出了。也就是說，在我們這個(gè)例子里，只需要掃描 1000 次。

進(jìn)一步優(yōu)化

通過覆蓋索引，解決上一段段落的聯(lián)合索引缺點(diǎn)

針對(duì)這個(gè)查詢，我們可以創(chuàng)建一個(gè) city、name 和 age 的聯(lián)合索引，對(duì)應(yīng)的 SQL 語句就是：

alter table t add index city_user_age(city, name, age);

這時(shí)，對(duì)于 city 字段的值相同的行來說，還是按照 name 字段的值遞增排序的，此時(shí)的查詢語句也就不再需要排序了。這樣整個(gè)查詢語句的執(zhí)行流程就變成了：

從索引 (city,name,age) 找到第一個(gè)滿足 city='杭州’條件的記錄，取出其中的 city、name 和 age 這三個(gè)字段的值，作為結(jié)果集的一部分直接返回；
從索引 (city,name,age) 取下一個(gè)記錄，同樣取出這三個(gè)字段的值，作為結(jié)果集的一部分直接返回；
重復(fù)執(zhí)行步驟 2，直到查到第 1000 條記錄，或者是不滿足 city='杭州’條件時(shí)循環(huán)結(jié)束。流程圖explain圖如下

可以看到，Extra 字段里面多了“Using index”，表示的就是使用了覆蓋索引，性能上會(huì)快很多。當(dāng)然，這里并不是說要為了每個(gè)查詢能用上覆蓋索引，就要把語句中涉及的字段都建上聯(lián)合索引，畢竟索引還是有維護(hù)代價(jià)的。這是一個(gè)需要權(quán)衡的決定。

總結(jié)

大概介紹了order by的兩種算法的流程。以及優(yōu)化方式。

只有知道實(shí)現(xiàn)流程，才能清楚在潛意識(shí)中埋下優(yōu)秀的表設(shè)計(jì)觀念！

order by是如何工作的？