導讀：
作者：高鵬（網(wǎng)名八怪），《深入理解MySQL主從原理32講》系列文的作者。
能力有限有誤請指出。
本文使用源碼版本：5.7.22
引擎為：Innodb
排序（filesort）作為DBA繞不開的話題，也經(jīng)常有朋友討論它，比如常見的問題如下：
排序的時候，用于排序的數(shù)據(jù)會不會如Innodb一樣壓縮空字符存儲，比如varchar(30)，我只是存儲了1個字符是否會壓縮，還是按照30個字符計算？
max_length_for_sort_data/max_sort_length 到底是什么含義？
original filesort algorithm（回表排序） 和 modified filesort algorithm（不回表排序） 的根本區(qū)別是什么？
為什么使用到排序的時候慢查詢中的Rows_examined會更大，計算方式到底是什么樣的？
在MySQL通常有如下算法來完成排序：
內(nèi)存排序（優(yōu)先隊列 order by limit 返回少量行常用，提高排序效率，但是注意order by limit n,m 如果n過大可能會涉及到排序算法的切換）
內(nèi)存排序（快速排序）
外部排序（歸并排序）
但是由于能力有限本文不解釋這些算法，并且本文不考慮優(yōu)先隊列算法的分支邏輯，只以快速排序和歸并排序作為基礎(chǔ)進行流程剖析。我們在執(zhí)行計劃中如果出現(xiàn)filesort字樣通常代表使用到了排序，但是執(zhí)行計劃中看不出來下面問題：
是否使用了臨時文件。
是否使用了優(yōu)先隊列。
是original filesort algorithm（回表排序）還是modified filesort algorithm（不回表排序）。
如何查看將在后面進行描述。本文還會給出大量的排序接口供感興趣的朋友使用，也給自己留下筆記。
一、從一個問題出發(fā)
這是最近一個朋友遇到的案例，大概意思就是說我的表在Innodb中只有30G左右，為什么使用如下語句進行排序操作后臨時文件居然達到了200多G，當然語句很變態(tài)，我們可以先不問為什么會有這樣的語句，我們只需要研究原理即可，在本文的第13節(jié)會進行原因解釋和問題重現(xiàn)。
臨時文件如下：
下面是這些案例信息：
show create table t\G
*************************** 1. row ***************************
Table: t
CreateTable: CREATE TABLE `t`(`
`ID` bigint(20) NOT NULL COMMENT 'ID',`
`UNLOAD_TASK_NO` varchar(50) NOT NULL ,`
`FORKLIFT_TICKETS_COUNT` bigint(20) DEFAULT NULL COMMENT '叉車票數(shù)',`
`MANAGE_STATUS` varchar(20) DEFAULT NULL COMMENT '管理狀態(tài)',`
`TRAY_BINDING_TASK_NO` varchar(50) NOT NULL ,`
`STATISTIC_STATUS` varchar(50) NOT NULL ,`
`CREATE_NO` varchar(50) DEFAULT NULL ,`
`UPDATE_NO` varchar(50) DEFAULT NULL ,`
`CREATE_NAME` varchar(200) DEFAULT NULL COMMENT '創(chuàng)建人名稱',`
`UPDATE_NAME` varchar(200) DEFAULT NULL COMMENT '更新人名稱',`
`CREATE_ORG_CODE` varchar(200) DEFAULT NULL COMMENT '創(chuàng)建組織編號',`
`UPDATE_ORG_CODE` varchar(200) DEFAULT NULL COMMENT '更新組織編號',`
`CREATE_ORG_NAME` varchar(1000) DEFAULT NULL COMMENT '創(chuàng)建組織名稱',`
`UPDATE_ORG_NAME` varchar(1000) DEFAULT NULL COMMENT '更新組織名稱',`
`CREATE_TIME` datetime DEFAULT NULL COMMENT '創(chuàng)建時間',`
`UPDATE_TIME` datetime DEFAULT NULL COMMENT '更新時間',`
`DATA_STATUS` varchar(50) DEFAULT NULL COMMENT '數(shù)據(jù)狀態(tài)',`
`OPERATION_DEVICE` varchar(200) DEFAULT NULL COMMENT '操作設(shè)備',`
`OPERATION_DEVICE_CODE` varchar(200) DEFAULT NULL COMMENT '操作設(shè)備編碼',`
`OPERATION_CODE` varchar(50) DEFAULT NULL COMMENT '操作碼',`
`OPERATION_ASSIST_CODE` varchar(50) DEFAULT NULL COMMENT '輔助操作碼',`
`CONTROL_STATUS` varchar(50) DEFAULT NULL COMMENT '控制狀態(tài)',`
`OPERATOR_NO` varchar(50) DEFAULT NULL COMMENT '操作人工號',`
`OPERATOR_NAME` varchar(200) DEFAULT NULL COMMENT '操作人名稱',`
`OPERATION_ORG_CODE` varchar(50) DEFAULT NULL COMMENT '操作部門編號',`
`OPERATION_ORG_NAME` varchar(200) DEFAULT NULL COMMENT '操作部門名稱',`
`OPERATION_TIME` datetime DEFAULT NULL COMMENT '操作時間',`
`OPERATOR_DEPT_NO` varchar(50) NOT NULL COMMENT '操作人所屬部門編號',`
`OPERATOR_DEPT_NAME` varchar(200) NOT NULL COMMENT '操作人所屬部門名稱',`
`FORKLIFT_DRIVER_NAME` varchar(200) DEFAULT NULL ,`
`FORKLIFT_DRIVER_NO` varchar(50) DEFAULT NULL ,`
`FORKLIFT_DRIVER_DEPT_NAME` varchar(200) DEFAULT NULL ,`
`FORKLIFT_DRIVER_DEPT_NO` varchar(50) DEFAULT NULL ,`
`FORKLIFT_SCAN_TIME` datetime DEFAULT NULL ,`
`OUT_FIELD_CODE` varchar(200) DEFAULT NULL,`
PRIMARY KEY (`ID`),`
KEY `IDX_TRAY_BINDING_TASK_NO`(`TRAY_BINDING_TASK_NO`),`
KEY `IDX_OPERATION_ORG_CODE`(`OPERATION_ORG_CODE`),`
KEY `IDX_OPERATION_TIME`(`OPERATION_TIME`)`
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=8
desc
SELECT
ID,
UNLOAD_TASK_NO,
FORKLIFT_TICKETS_COUNT,
MANAGE_STATUS,
TRAY_BINDING_TASK_NO,
STATISTIC_STATUS,
CREATE_NO,
UPDATE_NO,
CREATE_NAME,
UPDATE_NAME,
CREATE_ORG_CODE,
UPDATE_ORG_CODE,
CREATE_ORG_NAME,
UPDATE_ORG_NAME,
CREATE_TIME,
UPDATE_TIME,
DATA_STATUS,
OPERATION_DEVICE,
OPERATION_DEVICE_CODE,
OPERATION_CODE,
OPERATION_ASSIST_CODE,
CONTROL_STATUS,
OPERATOR_NO,
OPERATOR_NAME,
OPERATION_ORG_CODE,
OPERATION_ORG_NAME,
OPERATION_TIME,
OPERATOR_DEPT_NO,
OPERATOR_DEPT_NAME,
FORKLIFT_DRIVER_NAME,
FORKLIFT_DRIVER_NO,
FORKLIFT_DRIVER_DEPT_NAME,
FORKLIFT_DRIVER_DEPT_NO,
FORKLIFT_SCAN_TIME,
OUT_FIELD_CODE
FROM
t
GROUP BY id , UNLOAD_TASK_NO , FORKLIFT_TICKETS_COUNT ,
MANAGE_STATUS , TRAY_BINDING_TASK_NO , STATISTIC_STATUS ,
CREATE_NO , UPDATE_NO , CREATE_NAME , UPDATE_NAME ,
CREATE_ORG_CODE , UPDATE_ORG_CODE , CREATE_ORG_NAME ,
UPDATE_ORG_NAME , CREATE_TIME , UPDATE_TIME , DATA_STATUS ,
OPERATION_DEVICE , OPERATION_DEVICE_CODE , OPERATION_CODE ,
OPERATION_ASSIST_CODE , CONTROL_STATUS , OPERATOR_NO ,
OPERATOR_NAME , OPERATION_ORG_CODE , OPERATION_ORG_NAME ,
OPERATION_TIME , OPERATOR_DEPT_NO , OPERATOR_DEPT_NAME ,
FORKLIFT_DRIVER_NAME , FORKLIFT_DRIVER_NO ,
FORKLIFT_DRIVER_DEPT_NAME , FORKLIFT_DRIVER_DEPT_NO ,
FORKLIFT_SCAN_TIME , OUT_FIELD_CODE;
+----+-------------+-------------------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
+----+-------------+-------------------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
| 1| SIMPLE | t | NULL | ALL | NULL | NULL | NULL | NULL | 5381145| 100.00| Using filesort |
+----+-------------+-------------------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
1 row inset, 1 warning (0.00 sec)
也許你會懷疑這個語句有什么用，我們先不考慮功能，我們只考慮為什么它會生成200G的臨時文件這個問題。
接下來我將分階段進行排序的流程解析，注意了整個排序的流程均處于狀態(tài)‘Creating sort index’下面，我們以filesort函數(shù)接口為開始進行分析。
二、測試案例
為了更好的說明后面的流程我們使用2個除了字段長度不同，其他完全一樣的表來說明，但是需要注意這兩個表數(shù)據(jù)量很少，不會出現(xiàn)外部排序，如果涉及外部排序的時候我們需要假設(shè)它們數(shù)據(jù)量很大。其次這里根據(jù)original filesort algorithm和modified filesort algorithm進行劃分，但是這兩種方法還沒講述，不用太多理會。
- original filesort algorithm（回表排序）
mysql> show create table tests1 \G
*************************** 1. row ***************************
Table: tests1
CreateTable: CREATE TABLE `tests1`(
`a1` varchar(300) DEFAULT NULL,
`a2` varchar(300) DEFAULT NULL,
`a3` varchar(300) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row inset(0.00 sec)
mysql> select* from tests1;
+------+------+------+
| a1 | a2 | a3 |
+------+------+------+
| a | a | a |
| a | b | b |
| a | c | c |
| b | d | d |
| b | e | e |
| b | f | f |
| c | g | g |
| c | h | h |
+------+------+------+
8 rows inset(0.00 sec)
mysql> desc select* from tests1 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| 1| SIMPLE | tests1 | NULL | ALL | NULL | NULL | NULL | NULL | 8| 12.50| Usingwhere; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row inset, 1 warning (0.00 sec)
- modified filesort algorithm（不回表排序）
mysql> desc select* from tests2 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| 1| SIMPLE | tests2 | NULL | ALL | NULL | NULL | NULL | NULL | 8| 12.50| Usingwhere; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row inset, 1 warning (0.00 sec)
mysql> show create table tests2 \G
*************************** 1. row ***************************
Table: tests2
CreateTable: CREATE TABLE `tests2`(
`a1` varchar(20) DEFAULT NULL,
`a2` varchar(20) DEFAULT NULL,
`a3` varchar(20) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row inset(0.00 sec)
mysql> select* from tests2;
+------+------+------+
| a1 | a2 | a3 |
+------+------+------+
| a | a | a |
| a | b | b |
| a | c | c |
| b | d | d |
| b | e | e |
| b | f | f |
| c | g | g |
| c | h | h |
+------+------+------+
8 rows inset(0.00 sec)
mysql> desc select* from tests2 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| 1| SIMPLE | tests2 | NULL | ALL | NULL | NULL | NULL | NULL | 8| 12.50| Usingwhere; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row inset, 1 warning (0.01 sec)
整個流程我們從filesort函數(shù)接口開始討論。下面第3到第10節(jié)為排序的主要流程。
三、階段1:確認排序字段及順序
這里主要將排序順序存入到Filesort 類的 sortorder中，比如我們例子中的order by a2,a3就是a2和a3列，主要接口為Filesort::make_sortorder，我們按照源碼描述為sort字段（源碼中為sort_length），顯然我們在排序的時候除了sort字段以外，還應(yīng)該包含額外的字段，到底包含哪些字段就與方法 original filesort algorithm（回表排序） 和 modified filesort algorithm（不回表排序）有關(guān)了，下面進行討論。
四、階段2:計算sort字段的長度
這里主要調(diào)用使用sortlength函數(shù)，這一步將會帶入max_sort_length參數(shù)的設(shè)置進行判斷，默認情況下max_sort_length為1024字節(jié)。
這一步大概步驟為：
1、循環(huán)每一個sort字段
2、計算每一個sort字段的長度：公式為 ≈ 定義長度 * 2
比如這里例子中我定義了a1 varchar(300)，那么它的計算長度 ≈ 300 * 2（600），為什么是*2呢，這應(yīng)該是和Unicode編碼有關(guān)，這一步可以參考函數(shù)my_strnxfrmlen_utf8。同時需要注意這里是約等于，因為源碼中還是其他的考慮，比如字符是否為空，但是占用不多不考慮了。
3、帶入max_sort_length參數(shù)進行計算
好了有了上面一個sort字段的長度，那么這里就和max_sort_length進行比較，如果這個這個sort字段大于max_sort_length的值，那么以max_sort_length設(shè)置為準，這步代碼如下：
set_if_smaller(sortorder->length, thd->variables.max_sort_length);
因此，如果sort字段的某個字段的超過了max_sort_length設(shè)置，那么排序可能不那么精確了。
到了這里每個sort字段的長度以及sort字段的總長度已經(jīng)計算出來，比如前面給的兩個不同列子中：
（a2 varchar(300) a3 varchar(300) order by a2,a3）：每個sort字段約為300*2字節(jié)，兩個字段的總長度約為1200字節(jié)。
（a2 varchar(20) a3 varchar(20) order by a2,a3）：每個sort字段約為20*2字節(jié)，兩個字段的總長度約為80字節(jié)。
并且值得注意的是，這里是按照定義大小，如varchar(300) ，以300個字符來計算長度的，而不是我們通?？吹降腎nnodb中實際占用的字符數(shù)量。這是排序使用空間大于Innodb實際數(shù)據(jù)文件大小的一個原因。
下面我們以（a2 varchar(300) a3 varchar(300) order by a2,a3）為例實際看看debug的結(jié)果如下：
(gdb) p sortorder->field->field_name
$4 = 0x7ffe7800fadf"a3"
(gdb) p sortorder->length
$5 = 600
(gdb) p total_length
$6 = 1202（這里a2,a3 可以為NULL各自加了1個字節(jié)）
(gdb)
可以看出沒有問題。
4、循環(huán)結(jié)束，計算出sort字段的總長度。
后面我們會看到sort字段不能使用壓縮（pack）技術(shù)。
五、階段3:計算額外字段的空間
對于排序而言，我們很清楚除了sort字段以外，通常我們需要的是實際的數(shù)據(jù)，那么無外乎兩種方式如下：
original filesort algorithm：只存儲rowid或者主鍵做為額外的字段，然后進行回表抽取數(shù)據(jù)。我們按照源碼的描述，將這種關(guān)聯(lián)回表的字段叫做ref字段（源碼中變量叫做ref_length）。
modified filesort algorithm：將處于read_set（需要讀取的字段）全部放到額外字段中，這樣不需要回表讀取數(shù)據(jù)了。我們按照源碼的描述，將這些額外存儲的字段叫做addon字段（源碼中變量叫做addon_length）。
這里一步就是要來判斷到底使用那種算法，其主要標準就是參數(shù)max_length_for_sort_data，其默認大小為1024字節(jié)，但是后面會看到這里的計算為（sort字段長度+addon字段的總和）是否超過了max_length_for_sort_data。其次如果使用了modified filesort algorithm算法，那么將會對addon字段的每個字段做一個pack（打包），主要目的在于壓縮那些為空的字節(jié)，節(jié)省空間。
這一步的主要入口函數(shù)為Filesort::get_addon_fields下面是步驟解析。
1、循環(huán)本表全部字段
2、根據(jù)read_set過濾出不需要存儲的字段
這里如果不需要訪問到的字段自然不會包含在其中，下面這段源碼過濾代碼：
if(!bitmap_is_set(read_set, field->field_index)) //是否在read set中
continue;
3、獲取字段的長度
這里就是實際的長度了比如我們的a1 varchar(300)，且字符集為UTF8，那么其長度≈ 300*3 （900）。
4、獲取可以pack（打包）字段的長度
和上面不同，對于int這些固定長度類型的字段，只有可變長度的類型的字段才需要進行打包技術(shù)。
5、循環(huán)結(jié)束，獲取addon字段的總長度，獲取可以pack（打包）字段的總長度
循環(huán)結(jié)束后可以獲取addon字段的總長度，但是需要注意addon字段和sort字段可能包含重復的字段，比如例2中sort字段為a2、a3，addon字段為a1、a2、a3。
如果滿足如下條件：
addon字段的總長度+sort字段的總長度 > max_length_for_sort_data
那么將使用original filesort algorithm（回表排序）的方式，否則使用modified filesort algorithm的方式進行。下面是這一句代碼：
if(total_length + sortlength > max_length_for_sort_data) //如果長度大于了max_length_for_sort_data 則退出了
{
DBUG_ASSERT(addon_fields == NULL);
return NULL;
//返回NULL值 不打包了 使用 original filesort algorithm（回表排序）
}
我們在回到第2節(jié)例子中的第1個案例，因為我們對a1,a2,a3都是需要訪問的，且他們的大小均為varchar(300) UTF8，那么addon字段長度大約為300 * 3 * 3=2700字節(jié) ，其次我們前面計算了sort字段大約為1202字節(jié)，因此 2700+1202 是遠遠大于max_length_for_sort_data的默認設(shè)置1024字節(jié)的，因此會使用original filesort algorithm方式進行排序。
如果是第2節(jié)例子中的第2個案例呢，顯然要小很多了（每個字段varchar（20）），大約就是20 * 3 * 3（addon字段）+82（sort字段） 它是小于1024字節(jié)的，因此會使用modified filesort algorithm的排序方式，并且這些addon字段基本都可以使用打包（pack）技術(shù)，來節(jié)省空間。但是需要注意的是無論如何（sort字段）是不能進行打包（pack）的，而固定長度類型不需要打包（pack）壓縮空間。
六、階段4:確認每行的長度
有了上面的就計算后每一行的長度（如果可以打包是打包前的長度），下面就是這個計算過程。
if(using_addon_fields())
//如果使用了 打包技術(shù) 檢測 addon_fields 數(shù)組是否存在 使用modified filesort algorithm算法 不回表排序
{
res_length= addon_length; //總的長度 3個 varchar(300) uft8 為 3*300*3
}
else//使用original filesort algorithm算法
{
res_length= ref_length; //rowid(主鍵長度)
/*
The reference to the record is considered
as an additional sorted field
*/
sort_length+= ref_length; //實際上就是rowid(主鍵) +排序字段長度 回表排序
}
/*
Add hash at the end of sort key to order cut values correctly.
Needed for GROUPing, rather than for ORDERing.
*/
if(use_hash)
sort_length+= sizeof(ulonglong);
rec_length= sort_length + addon_length;
//modified filesort algorithm sort_length 為排序鍵長度 addon_lenth 為訪問字段長度，original filesort algorithm rowid(主鍵) +排序字段長度 ，因為addon_length為0
好了我們稍微總結(jié)一下：
original filesort algorithm：每行長度為sort字段的總長度+ref字段長度（主鍵或者rowid）。
modified filesort algorithm：每行的長度為sort字段的總長度+addon字段的長度（需要訪問的字段總長度）。
當然到底使用那種算法參考上一節(jié)。但是要注意了對于varchar這種可變長度是以定義的大小為準了，比如UTF8 varchar（300）就是300*3= 900 而不是實際存儲的大小，而固定長度沒有變化。好了，還是回頭看看第2節(jié)的兩個例子，分別計算它們的行長度：
- 例子1：根據(jù)我們的計算，它將使用original filesort algorithm排序方式，最終的計算行長度應(yīng)該為（sort字段長度+rowid長度）及 ≈ 1202+6 字節(jié)，下面是debug的結(jié)果：
(gdb) p rec_length
$1 = 1208
- 例子2：根據(jù)我們的計算，它將使用modified filesort algorithm排序方式，最終計算行長度應(yīng)該為（sort字段長度+addon字段長度）及 ≈ 82 + 20 * 3 * 3 （結(jié)果為262），注意這里是約等于沒有計算非空等因素和可變長度因素，下面是debug的結(jié)果：
(gdb) p rec_length
$2 = 266
可以看出誤差不大。
七、階段5:確認最大內(nèi)存分配
這里的分配內(nèi)存就和參數(shù)sort_buffer_size大小有關(guān)了。但是是不是每次都會分配至少sort_buffer_size大小的內(nèi)存的呢？其實不是，MySQL會判斷是否表很小的情況，也就是做一個簡單的運算，目的在于節(jié)省內(nèi)存的開銷，這里我們將來描述。
1、大概計算出Innodb層主鍵葉子結(jié)點的行數(shù)
這一步主要通過（聚集索引葉子結(jié)點的空間大小/聚集索引每行大小 * 2）計算出一個行的上限，調(diào)入函數(shù)ha_innobase::estimate_rows_upper_bound，源碼如下：
num_rows= table->file->estimate_rows_upper_bound();
//上限來自于Innodb 葉子聚集索引葉子結(jié)點/聚集索引長度 *2
然后將結(jié)果存儲起來，如果表很小那么這個值會非常小。
2、根據(jù)前面計算的每行長度計算出sort buffer可以容下的最大行數(shù)
這一步將計算sort buffer可以容納的最大行數(shù)如下：
ha_rows keys= memory_available / (param.rec_length + sizeof(char*));
//可以排序的 行數(shù) sort buffer 中最大 可以排序的行數(shù)
3、對比兩者的最小值，作為分配內(nèi)存的標準
然后對比兩個值以小值為準，如下：
param.max_keys_per_buffer= (uint) min(num_rows > 0? num_rows : 1, keys);
//存儲行數(shù)上限 和 可以排序 行數(shù)的 小值
4、根據(jù)結(jié)果分配內(nèi)存
分配如下：
table_sort.alloc_sort_buffer(param.max_keys_per_buffer, param.rec_length);
也就是根據(jù)總的計算出的行長度和計算出的行數(shù)進行分配。
八、階段6:讀取數(shù)據(jù)，進行內(nèi)存排序
到這里準備工作已經(jīng)完成了，接下就是以行為單位讀取數(shù)據(jù)了，然后對過濾掉where條件的剩下的數(shù)據(jù)進行排序。如果需要排序的數(shù)據(jù)很多，那么等排序內(nèi)存寫滿后會進行內(nèi)存排序，然后將排序的內(nèi)容寫入到排序臨時文件中，等待下一步做外部的歸并排序。
作為歸并排序而言，每一個歸并的文件片段必須是排序好的，否則歸并排序是不能完成的，因此寫滿排序內(nèi)存后需要做內(nèi)存排序。如果寫不滿呢，那么做一次內(nèi)存排序就好了。下面我們來看看這個過程，整個過程集中在find_all_keys函數(shù)中。
1、讀取需要的數(shù)據(jù)
實際上在這一步之前還會做read_set的更改，因為對于original filesort algorithm（回表排序）的算法來講不會讀取全部需要的字段，為了簡單起見不做描述了。這一步就是讀取一行數(shù)據(jù)了，這里會進入Innodb層讀取數(shù)據(jù)，具體流程不做解釋了，下面是這一行代碼：
error= file->ha_rnd_next(sort_form->record[0]); //讀取一行數(shù)據(jù)
2、將Rows_examined 加1
這里這個指標對應(yīng)的就是慢查中的Rows_examined了，這個指標在有排序的情況下會出現(xiàn)重復計算的情況，但是這里還是正確的，重復的部分后面再說。
3、過濾掉where條件
這里將會過濾掉where條件中不滿足條件的行，代碼如下：
if(!error && !qep_tab->skip_record(thd, &skip_record) && !skip_record)
//這里做where過濾條件 的比較
**4、將行數(shù)據(jù)寫入到sort buffer中 **
這一步將會把數(shù)據(jù)寫入到sort buffer中，需要注意這里不涉及排序操作，只是存儲數(shù)據(jù)到內(nèi)存中。其中分為了2部分：
寫入sort字段。如果是original filesort algorithm那么rowid（主鍵）也包含在其中了。
寫入addon字段，這是modified filesort algorithm才會有的，在寫入之前還會調(diào)用Field::pack對可以打包（pack）的字段進行壓縮操作。對于varchar字段的打包函數(shù)就是Field_varstring::pack，簡單的說存儲的是實際的大小，而非定義的大小。
整個過程位于find_all_keys->Sort_param::make_sortkey 函數(shù)中。這一步還涉及到了我們非常關(guān)心的一個問題，到底排序的數(shù)據(jù)如何存儲的問題，需要仔細閱讀。下面我們就debug一下第2節(jié)中兩個例子的不同存儲方式。
既然要去看內(nèi)存中的數(shù)據(jù)，我們只要看它最終拷貝的內(nèi)存數(shù)據(jù)是什么就好了，那么真相將會大白，我們只需要將斷點放到find_all_keys函數(shù)上，做完一行數(shù)據(jù)的Sort_param::make_sortkey操作后看內(nèi)存就行了，如下：
- 例子1（字段都是varchar（300））：它將使用original filesort algorithm（回表排序）的方式，最終應(yīng)該存儲的是sort字段（a2，a3）+rowid。排序的結(jié)果如下：
mysql> select* from test.tests1 where a1='b' order by a2,a3;
+------+------+------+
| a1 | a2 | a3 |
+------+------+------+
| b | d | d |
| b | e | e |
| b | f | f |
+------+------+------+
3 rows inset(9.06 sec)
我們以第二行為查看目標
由于篇幅的關(guān)系，我展示其中的一部分，因為這里大約有1200多個字節(jié)，如下：
(gdb) x/1300bx start_of_rec
0x7ffe7ca79998: 0x01 0x00 0x45 0x00 0x20 0x00 0x20 0x00
0x7ffe7ca799a0: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7ca799a8: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7ca799b0: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7ca799b8: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7ca799c0: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7ca799c8: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
...
這后面還有大量的 0X20 0X00
我們看到了大量的0X20 0X00，這正是占位符號，實際有用的數(shù)據(jù)也就只有0x45 0x00這兩個字節(jié)了，而0x45正是我們的大寫字母E，也就是數(shù)據(jù)中的e，這和比較字符集有關(guān)。這里的0X20 0X00占用了大量的空間，我們最初計算sort 字段大約為1200字節(jié)，實際上只有少量的幾個字節(jié)有用。
這里對于sort字段而言，比實際存儲的數(shù)據(jù)大得多。
- 例子2（字段都是varchar（20））：它將使用modified filesort algorithm，最終應(yīng)該存儲的是sort字段（a2，a3）+addon字段（需要的字段，這里就是a1，a2，a3）
排序的結(jié)果如下：
mysql> select* from test.tests2 where a1='b' order by a2,a3;
+------+------+------+
| a1 | a2 | a3 |
+------+------+------+
| b | d | d |
| b | e | e |
| b | f | f |
+------+------+------+
我們以第一行為查看目標
這里數(shù)據(jù)不大，通過壓縮后只有91個字節(jié)了，我們整體查看如下：
(gdb) p rec_sz
$6 = 91
gdb) x/91x start_of_rec
0x7ffe7c991bc0: 0x01 0x00 0x44 0x00 0x20 0x00 0x20 0x00
0x7ffe7c991bc8: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7c991bd0: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7c991bd8: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7c991be0: 0x20 0x00 0x20 0x00 0x20 0x00 0x20 0x00
0x7ffe7c991be8: 0x20 0x01 0x00 0x44 0x00 0x20 0x00 0x20
0x7ffe7c991bf0: 0x00 0x20 0x00 0x20 0x00 0x20 0x00 0x20
0x7ffe7c991bf8: 0x00 0x20 0x00 0x20 0x00 0x20 0x00 0x20
0x7ffe7c991c00: 0x00 0x20 0x00 0x20 0x00 0x20 0x00 0x20
0x7ffe7c991c08: 0x00 0x20 0x00 0x20 0x00 0x20 0x00 0x20
0x7ffe7c991c10: 0x00 0x20 0x07 0x00 0x00 0x01 0x62 0x01
0x7ffe7c991c18: 0x64 0x01 0x64
這就是整行記錄了，我們發(fā)現(xiàn)對于sort字段而言沒有壓縮，依舊是0x20 0x00占位，而對于addon字段（需要的字段，這里就是a1，a2，a3）而言，這里小了很多，因為做了打包（pack）即：
0x01 0x62：數(shù)據(jù)b0x01 0x64：數(shù)據(jù)d0x01 0x64：數(shù)據(jù)d而0x01應(yīng)該就是長度了。
不管怎么說，對于sort字段而言依舊比實際存儲的數(shù)據(jù)大很多。
**5、如果sort buffer存滿，對sort buffer中的數(shù)據(jù)進行排序，然后寫入到臨時文件 **
如果需要排序的數(shù)據(jù)量很大的話，那么sort buffer肯定是不能容下的，因此如果寫滿后就進行一次內(nèi)存排序操作，然后將排序好的數(shù)據(jù)寫入到外部排序文件中去，這叫做一個chunk。外部文件的位置由tmpdir參數(shù)指定，名字以MY開頭，注意外部排序通常需要2個臨時文件，這里是第1個用于存儲內(nèi)存排序結(jié)果的臨時文件，以chunk的方式寫入。如下：
if(fs_info->isfull()) //如果sort buffer滿了 并且sort buffer已經(jīng)排序完成
{
if(write_keys(param, fs_info, idx, chunk_file, tempfile)) //寫入到物理文件 完成內(nèi)存排序 如果內(nèi)存不會滿這里不會做 會在create_sort_index 中排序完成
{
num_records= HA_POS_ERROR;
goto cleanup;
}
idx= 0;
indexpos++;
}
最終會調(diào)入write_keys函數(shù)進行排序和寫入外部排序文件，這里核心就是先排序，然后循環(huán)每條排序文件寫入到外部排序文件。下面我來驗證一下寫入臨時文件的長度，我將第2節(jié)中的例子2數(shù)據(jù)擴大了N倍后，讓其使用外部文件排序，下面是驗證結(jié)果，斷點write_keys即可：
1161if(my_b_write(tempfile, record, rec_length))
(gdb) p rec_length
$8 = 91
可以每行的長度還是91字節(jié)（打包壓縮后），和前面看到的長度一致，說明這些數(shù)據(jù)會完完整整的寫入到外部排序文件，這顯然會比我們想象的大得多。
好了到這里數(shù)據(jù)已經(jīng)找出來了，如果超過sort buffer的大小，外部排序需要的結(jié)果已經(jīng)存儲在臨時文件1了，并且它是分片（chunk）存儲到臨時文件的，它以MY開頭。
九、階段7:排序方式總結(jié)輸出
這里對上面的排序過程做了一個階段性的總結(jié)，代碼如下：
Opt_trace_object(trace, "filesort_summary")
.add("rows", num_rows)
.add("examined_rows", param.examined_rows)
.add("number_of_tmp_files", num_chunks)
.add("sort_buffer_size", table_sort.sort_buffer_size())
.add_alnum("sort_mode",
param.using_packed_addons() ?
"<sort_key, packed_additional_fields>":
param.using_addon_fields() ?
"<sort_key, additional_fields>": "<sort_key, rowid>");
我們解析一下：
rows：排序的行數(shù)，也就是應(yīng)用where過濾條件后剩下的行數(shù)。
examined_rows：Innodb層掃描的行數(shù)，注意這不是慢查詢中的Rows_examined，這里是準確的結(jié)果，沒有重復計數(shù)。
number_of_tmp_files：外部排序時，用于保存結(jié)果的臨時文件的chunk數(shù)量，每次sort buffer滿排序后寫入到一個chunk，但是所有chunk共同存在于一個臨時文件中。
sort_buffer_size：內(nèi)部排序使用的內(nèi)存大小，并不一定是sort_buffer_size參數(shù)指定的大小。
sort_mode：這里解釋如下
1、sort_key, packed_additional_fields：使用了modified filesort algorithm（不回表排序） ，并且有打包（pack）的字段，通常為可變字段比如varchar。
2、sort_key, additional_fields：使用了modified filesort algorithm（不回表排序），但是沒有需要打包（pack）的字段，比如都是固定長度字段。
3、sort_key, rowid：使用了original filesort algorithm（回表排序）。
十、階段8:進行最終排序
這里涉及2個部分如下：
如果sort buffer不滿，則這里開始進行排序，調(diào)入函數(shù)save_index。
如果sort buffer滿了，則進行歸并排序，調(diào)入函數(shù)merge_many_buff->merge_buffers，最后調(diào)入merge_index完成歸并排序。
對于歸并排序來講，這里可能會生成另外2個臨時文件用于存儲最終排序的結(jié)果，它們依然以MY開頭，且依然是存儲在tmpdir參數(shù)指定的位置。因此在外部排序中將可能會生成3個臨時文件，總結(jié)如下：
臨時文件1：用于存儲內(nèi)存排序的結(jié)果，以chunk為單位，一個chunk的大小就是sort buffer的大小。
臨時文件2：以前面的臨時文件1為基礎(chǔ)，做歸并排序。
臨時文件3：將最后的歸并排序結(jié)果存儲，去掉sort字段，只保留addon字段（需要訪問的字段）或者ref字段（ROWID或者主鍵），因此它一般會比前面2個臨時文件小。
但是它們不會同時存在，要么 臨時文件1和臨時文件2存在，要么 臨時文件2和臨時文件3存在。
這個很容易驗證，將斷點放到merge_buffers和merge_index上就可以驗證了，如下：
臨時文件1和臨時文件2同時存在：
[root@gp1 test]# lsof|grep tmp/MY
mysqld 8769 mysql 70u REG 252,3 79167488 2249135/mysqldata/mysql3340/tmp/MYt1QIvr(deleted)
mysqld 8769 mysql 71u REG 252,3 58327040 2249242/mysqldata/mysql3340/tmp/MY4CrO4m (deleted)
臨時文件2和臨時文件3共同存在：
[root@gp1 test]# lsof|grep tmp/MY
mysqld 8769 mysql 70u REG 252,3 360448 2249135/mysqldata/mysql3340/tmp/MYg109Wp(deleted)
mysqld 8769 mysql 71u REG 252,3 79167488 2249242/mysqldata/mysql3340/tmp/MY4CrO4m (deleted)
但是由于能力有限對于歸并排序的具體過程我并沒有仔細學習了，這里給一個大概的接口。注意這里每次調(diào)用merge_buffers將會增加Sort_merge_passes 1次，應(yīng)該是歸并的次數(shù)，這個值增量的大小可以側(cè)面反映出外部排序使用臨時文件的大小。
十一、排序的其他問題
這里將描述2個額外的排序問題。
1、original filesort algorithm（回表排序）的回表
最后對于original filesort algorithm（回表排序）排序方式而言，可能還需要做一個回表獲取數(shù)據(jù)的操作，這一步可能會用到參數(shù)read_rnd_buffer_size定義的內(nèi)存大小。
比如我們第2節(jié)中第1個例子將會使用到original filesort algorithm（回表排序），但是對于回表操作有如下標準：
如果沒有使用到外部排序臨時文件則說明排序量不大，則使用普通的回表方式，調(diào)入函數(shù)rr_from_pointers，也就是單行回表方式。
如果使用到了外部排序臨時文件則說明排序量較大，需要使用到批量回表方式，這個時候大概的步驟就是讀取rowid（主鍵）排序，然后批量回表，這將會在read_rnd_buffer_size指定的內(nèi)存中完成，調(diào)入函數(shù)rr_from_cache。這也是一種優(yōu)化方式，因為回表一般是散列的，代價很大。
2、關(guān)于排序中Rows_examined的計算
首先這個值我說的是慢查詢的中的Rows_examined，在排序中會出現(xiàn)重復計數(shù)的可能，前面第8節(jié)已經(jīng)說明了一下，這個值在第8節(jié)還是正確的，但是最后符合where條件的數(shù)據(jù)在返回的時候還會調(diào)用函數(shù)evaluate_join_record，結(jié)果Rows_examined會增加符合where條件的行數(shù)。還是以我們第2節(jié)的兩個例子為例：
mysql> select* from test.tests1 where a1='b' order by a2,a3;
+------+------+------+
| a1 | a2 | a3 |
+------+------+------+
| b | d | d |
| b | e | e |
| b | f | f |
+------+------+------+
3 rows inset(5.11 sec)
mysql> select* from test.tests2 where a1='b' order by a2,a3;
+------+------+------+
| a1 | a2 | a3 |
+------+------+------+
| b | d | d |
| b | e | e |
| b | f | f |
+------+------+------+
3 rows inset(5.28 sec)
mysql> desc select* from tests2 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| 1| SIMPLE | tests2 | NULL | ALL | NULL | NULL | NULL | NULL | 8| 12.50| Usingwhere; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row inset, 1 warning (0.00 sec)
8 rows inset(0.00 sec)
mysql> desc select* from tests2 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| 1| SIMPLE | tests2 | NULL | ALL | NULL | NULL | NULL | NULL | 8| 12.50| Usingwhere; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row inset, 1 warning (0.01 sec)
慢查詢?nèi)缦?，不要糾結(jié)時間（因為我故意debug停止了一會），我們只關(guān)注Rows_examined，如下：
# Time: 2019-12-23T12:03:26.108529+08:00
# User@Host: root[root] @ localhost [] Id: 4
# Schema: Last_errno: 0 Killed: 0
# Query_time: 5.118098 Lock_time: 0.000716 Rows_sent: 3 Rows_examined: 11 Rows_affected: 0
# Bytes_sent: 184
SET timestamp=1577073806;
select* from test.tests1 where a1='b' order by a2,a3;
# Time: 2019-12-23T12:03:36.138274+08:00
# User@Host: root[root] @ localhost [] Id: 4
# Schema: Last_errno: 0 Killed: 0
# Query_time: 5.285573 Lock_time: 0.000640 Rows_sent: 3 Rows_examined: 11 Rows_affected: 0
# Bytes_sent: 184
SET timestamp=1577073816;
select* from test.tests2 where a1='b' order by a2,a3;
我們可以看到Rows_examined都是11，為什么是11呢？顯然我們要掃描總的行數(shù)為8（這里是全表掃描，表總共8行數(shù)據(jù)），然后過濾后需要排序的結(jié)果為3條數(shù)據(jù)，這3條數(shù)據(jù)會重復計數(shù)一次。因此就是8+3=11，也就是說有3條數(shù)據(jù)重復計數(shù)了。
十二、通過OPTIMIZER_TRACE查看排序結(jié)果
要使用OPTIMIZER_TRACE只需要“SET optimizer_trace="enabled=on";”，跑完語句后查看information_schema.OPTIMIZER_TRACE即可。前面第9節(jié)我們解釋了排序方式總結(jié)輸出的含義，這里我們來看看具體的結(jié)果，我們還是以第2節(jié)的2個例子為例：
- 例1：
"filesort_priority_queue_optimization": {
"usable": false,
"cause": "not applicable (no LIMIT)"
},
"filesort_execution": [
],
"filesort_summary": {
"rows": 3,
"examined_rows": 8,
"number_of_tmp_files": 0,
"sort_buffer_size": 1285312,
"sort_mode": "<sort_key, rowid>"
- 例2：
"filesort_priority_queue_optimization": {
"usable": false,
"cause": "not applicable (no LIMIT)"
},
"filesort_execution": [
],
"filesort_summary": {
"rows": 3,
"examined_rows": 8,
"number_of_tmp_files": 0,
"sort_buffer_size": 322920,
"sort_mode": "<sort_key, packed_additional_fields>"
現(xiàn)在我們清楚了，這些總結(jié)實際上是在執(zhí)行階段生成的，需要注意幾點如下：
這里的examined_rows和慢查詢中的Rows_examined不一樣，因為這里不會有重復計數(shù)，是準確的。
這里還會說明是否使用了優(yōu)先隊列排序即“filesort_priority_queue_optimization”部分。
通過“sort_buffer_size”可以發(fā)現(xiàn)，這里并沒有分配參數(shù)sort_buffer_size指定的大小，節(jié)約了內(nèi)存，這在第7節(jié)說明了。
其他指標在第9節(jié)已經(jīng)說明過了，不在描述。
十三、回到問題本身
好了，大概的流程我描述了一遍，這些流程都是主要流程，實際上的流程復雜很多。那么我們回到最開始的案例上來。他的max_sort_length和max_length_for_sort_data均為默認值1024。
案例中的group by實際就是一個排序操作，我們從執(zhí)行計劃可以看出來，那么先分析一下它的sort字段。很顯然group by 后的都是sort字段，其中字段CREATE_ORG_NAME其定義為 varchar（1000），它的占用空間為（1000 * 2）及2000字節(jié)，但是超過了max_sort_length的大小，因此為1024字節(jié)，相同的還有UPDATE_ORG_NAME字段也是varchar（1000），也會做同樣處理，其他字段不會超過max_sort_length的限制，并且在第5節(jié)說過sort 字段是不會進行壓縮的。
我大概算了一下sort字段的全部大小約為 （3900 * 2) 字節(jié)，可以看到一行數(shù)據(jù)的sort字段基本達到了8K的容量，而addon字段的長度（未打包壓縮前）會更大，顯然超過max_length_for_sort_data的設(shè)置，因此對于這樣的排序顯然不可能使用modified filesort algorithm（不回表排序了），使用的是original filesort algorithm（回表排序），因此一行的記錄就是（sort 字段+主鍵）了，主鍵大小可以忽略，最終一行記錄的大小就是8K左右，這個值通常會遠遠大于Innodb壓縮后存儲varchar字段的大小，這也是為什么本例中雖然表只有30G左右但是臨時文件達到了200G以上的原因了。
好了，我們來重現(xiàn)一下問題，我們使用第2節(jié)的例1，我們將其數(shù)據(jù)增多，原理上我們的例1會使用到original filesort algorithm（回表排序）的方式，因為這里sort字段（a2，a3）的總長度+addon字段（a1，a2，a3）的長度約為300 * 2 * 2+300 * 3 * 3 這顯示大于了max_length_for_sort_data的長度， 因此這個排序一行的長度就是sort字段（a2，a3）+ref字段（ROWID），大約就是300 * 2 * 2+6=1206字節(jié)了。下面是這個表的總數(shù)據(jù)和Innodb文件大小（我這里叫做bgtest5表）：
mysql> show create table bgtest5 \G
*************************** 1. row ***************************
Table: bgtest5
CreateTable: CREATE TABLE `bgtest5`(
`a1` varchar(300) DEFAULT NULL,
`a2` varchar(300) DEFAULT NULL,
`a3` varchar(300) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row inset(0.01 sec)
mysql> SELECT COUNT(*) FROM bgtest5;
+----------+
| COUNT(*) |
+----------+
| 65536|
+----------+
1 row inset(5.91 sec)
mysql> desc select* from bgtest5 order by a2,a3;
+----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+----------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
+----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+----------------+
| 1| SIMPLE | bgtest5 | NULL | ALL | NULL | NULL | NULL | NULL | 66034| 100.00| Using filesort |
+----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+----------------+
1 row inset, 1 warning (0.00 sec)
注意這里是全表排序了，沒有where過濾條件了，下面是這個表ibd文件的大?。?/p>
[root@gp1 test]# du -hs bgtest5.ibd
11M bgtest5.ibd
[root@gp1 test]#
下面我們就需要將gdb的斷點打在merge_many_buff，我們的目的就是觀察臨時文件1的大小，這個文件前面說過了是存儲內(nèi)存排序結(jié)果的，如下：
[root@gp1 test]# lsof|grep tmp/MY
mysqld 8769 mysql 69u REG 252,3 79101952 2249135/mysqldata/mysql3340/tmp/MYzfek5x(deleted)
可以看到這個文件的大小為79101952字節(jié)，即80M左右，這和我們計算的總量1206（每行大小） * 65535（行數(shù)） 約為 80M 結(jié)果一致。這遠遠超過了ibd文件的大小11M，并且要知道，隨后還會生成一個大小差不多的文件來存儲歸并排序的結(jié)果如下：
[root@gp1 test]# lsof|grep tmp/MY
mysqld 8769 mysql 69u REG 252,3 79167488 2249135/mysqldata/mysql3340/tmp/MYzfek5x(deleted)
mysqld 8769 mysql 70u REG 252,3 58327040 2249242/mysqldata/mysql3340/tmp/MY8UOLKa (deleted)
因此得到證明，排序的臨時文件遠遠大于ibd文件的現(xiàn)象是可能出現(xiàn)的。
十四、全文總結(jié)
本文寫了很多，這里需要做一個詳細的總結(jié)：
總結(jié)1 ：排序中一行記錄如何組織？
一行排序記錄，由sort字段+addon字段組成，其中sort字段為order by 后面的字段，而addon字段為需要訪問的字段，比如‘select a1,a2,a3 from test order by a2,a3’，其中sort字段為‘a(chǎn)2,a3’，addon字段為‘a(chǎn)1,a2,a3’。sort字段中的可變長度字段不能打包（pack）壓縮，比如varchar，使用的是定義的大小計算空間，注意這是排序使用空間較大的一個重要因素。
如果在計算sort字段空間的時候，某個字段的空間大小大于了max_sort_length大小則按照max_sort_length指定的大小計算。
一行排序記錄，如果sort字段+addon字段的長度大于了max_length_for_sort_data的大小，那么addon字段將不會存儲，而使用sort字段+ref字段代替，ref字段為主鍵或者ROWID，這個時候就會使用original filesort algorithm（回表排序）的方式了。
如果addon字段包含可變字段比如varchar字段，則會使用打包（pack）技術(shù)進行壓縮，節(jié)省空間?？梢詤⒖嫉?、第4、第5、第6、第8節(jié)。
總結(jié)2：排序使用什么樣的方法進行？
- original filesort algorithm（回表排序）
如果使用的是sort字段+ref字段進行排序，那么必須要回表獲取需要的數(shù)據(jù)，如果排序使用了臨時文件（也就是說使用外部歸并排序，排序量較大）則會使用批量回表，批量回表會涉及到read_rnd_buffer_size參數(shù)指定的內(nèi)存大小，主要用于排序和結(jié)果返回。
如果排序沒有使用臨時文件（內(nèi)存排序就可以完成，排序量較小）則采用單行回表。
- modified filesort algorithm（不回表排序）
如果使用的是sort字段+addon字段進行排序，那么使用不回表排序，所有需要的字段均在排序過程中進行存儲，addon字段中的可變長度字段可以進行打包（pack）壓縮節(jié)省空間。
其次sort字段和addon字段中可能有重復的字段，比如例2中，sort字段為a2、a3，addon字段為a1、a2、a3，這是排序使用空間較大的另外一個原因。
在OPTIMIZER_TRACE中可以查看到使用了那種方法，參考12節(jié)。
總結(jié)3：每次排序一定會分配sort_buffer_size參數(shù)指定的內(nèi)存大小嗎？
不是這樣的，MySQL會做一個初步的計算，通過比較Innodb中聚集索引可能存儲的行上限和sort_buffer_size參數(shù)指定大小內(nèi)存可以容納的行上限，獲取它們小值進行確認最終內(nèi)存分配的大小，目的在于節(jié)省內(nèi)存空間。
在OPTIMIZER_TRACE中可以看到使用的內(nèi)存大小，參考第8、第12節(jié)。
總結(jié)4：關(guān)于OPTIMIZER_TRACE中的examined_rows和慢查詢中的Rows_examined有什么區(qū)別？
慢查詢中的Rows_examined包含了重復計數(shù)，重復的部分為where條件過濾后做了排序的部分。
OPTIMIZER_TRACE中的examined_rows不包含重復計數(shù)，為實際Innodb層掃描的行數(shù)。
可以參考11節(jié)。
總結(jié)5：外部排序臨時文件的使用是什么樣的？
實際上一個語句的臨時文件不止一個，但是它們都以MY開頭，并且都放到了tmpdir目錄下，lsof可以看到這種文件。
臨時文件1：用于存儲內(nèi)存排序的結(jié)果，以chunk為單位，一個chunk的大小就是sort buffer的大小。
臨時文件2：以前面的臨時文件1為基礎(chǔ)，做歸并排序。
臨時文件3：將最后的歸并排序結(jié)果存儲，去掉sort字段，只保留addon字段（需要訪問的字段）或者ref字段（ROWID或者主鍵），因此它一般會比前面2個臨時文件小。
但是它們不會同時存在，要么臨時文件1和臨時文件2存在，要么臨時文件2和臨時文件3存在。對于臨時文件的使用可以查看Sort_merge_passes，本值多少會側(cè)面反應(yīng)出外部排序量的大小。
可以參考第10節(jié)。
總結(jié)6：排序使用了哪種算法？
雖然本文不涉及算法，但是內(nèi)部排序有2種算法需要知道：
內(nèi)存排序（優(yōu)先隊列 order by limit 返回少量行常用，提高排序效率，但是注意order by limit n,m 如果n過大可能會涉及到排序算法的切換）
內(nèi)存排序（快速排序）在通過OPTIMIZER_TRACE可以查看是否使用使用了優(yōu)先隊列算法，參考12節(jié)。
總結(jié)7：“Creating sort index”到底是什么狀態(tài)？
我們前面講的全部排序流程都會包含在這個狀態(tài)下，包括：
獲取排序需要的數(shù)據(jù)（比如例子中全表掃描從Innodb層獲取數(shù)據(jù)）
根據(jù)where條件過濾數(shù)據(jù)
內(nèi)存排序
外部排序
總結(jié)8：如何避免臨時文件過大的情況？
首先應(yīng)該考慮是否可以使用索引來避免排序，如果不能則需要考慮下面的要點：
order by 后面的字段滿足需求即可，盡可能的少。
order by 后面涉及的字段盡量為固定長度的字段類型，而不是可變字段類型如varchar。因為sort字段不能壓縮。
不要過大的定義可變字段長度，應(yīng)該合理定義，例如varchar（10）能夠滿足需求不要使用varchar（50），這些空間雖然在Innodb層存儲會壓縮，但是MySQL層確可能使用全長度（比如sort字段）。
在查詢中盡量不要用（select *） 而使用需要查詢的字段，這將會減少addon字段的個數(shù)，在我另外一個文章還講述了（select *）的其他的缺點
