MySQL：排序（filesort）詳細(xì)解析（8000字長文）

導(dǎo)讀：

作者：高鵬（網(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)先隊(duì)列 order by limit 返回少量行常用，提高排序效率旭旭，但是注意order by limit n,m 如果n過大可能會涉及到排序算法的切換）
內(nèi)存排序（快速排序）
外部排序（歸并排序）

但是由于能力有限本文不解釋這些算法谎脯，并且本文不考慮優(yōu)先隊(duì)列算法的分支邏輯，只以快速排序和歸并排序作為基礎(chǔ)進(jìn)行流程剖析持寄。我們在執(zhí)行計劃中如果出現(xiàn)filesort字樣通常代表使用到了排序源梭，但是執(zhí)行計劃中看不出來下面問題：

是否使用了臨時文件。
是否使用了優(yōu)先隊(duì)列稍味。
是original filesort algorithm（回表排序）還是modified filesort algorithm（不回表排序）废麻。

如何查看將在后面進(jìn)行描述。本文還會給出大量的排序接口供感興趣的朋友使用模庐，也給自己留下筆記烛愧。

一、從一個問題出發(fā)

這是最近一個朋友遇到的案例掂碱，大概意思就是說我的表在Innodb中只有30G左右怜姿，為什么使用如下語句進(jìn)行排序操作后臨時文件居然達(dá)到了200多G，當(dāng)然語句很變態(tài)沧卢，我們可以先不問為什么會有這樣的語句但狭，我們只需要研究原理即可，在本文的第13節(jié)會進(jìn)行原因解釋和問題重現(xiàn)熟空。

臨時文件如下：

image

下面是這些案例信息：

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的臨時文件這個問題绍刮。

接下來我將分階段進(jìn)行排序的流程解析，注意了整個排序的流程均處于狀態(tài)‘Creating sort index’下面挨摸，我們以filesort函數(shù)接口為開始進(jìn)行分析孩革。

二、測試案例

為了更好的說明后面的流程我們使用2個除了字段長度不同得运，其他完全一樣的表來說明膝蜈，但是需要注意這兩個表數(shù)據(jù)量很少，不會出現(xiàn)外部排序熔掺，如果涉及外部排序的時候我們需要假設(shè)它們數(shù)據(jù)量很大饱搏。其次這里根據(jù)original filesort algorithm和modified filesort algorithm進(jìn)行劃分，但是這兩種方法還沒講述置逻，不用太多理會推沸。

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:確認(rèn)排序字段及順序

這里主要將排序順序存入到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)了贸街，下面進(jìn)行討論捐川。

四、階段2:計算sort字段的長度

這里主要調(diào)用使用sortlength函數(shù)岩齿，這一步將會帶入max_sort_length參數(shù)的設(shè)置進(jìn)行判斷吃谣，默認(rèn)情況下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哮笆。同時需要注意這里是約等于，因?yàn)樵创a中還是其他的考慮，比如字符是否為空鲁冯，但是占用不多不考慮了。

3跨扮、帶入max_sort_length參數(shù)進(jìn)行計算

好了有了上面一個sort字段的長度，那么這里就和max_sort_length進(jìn)行比較，如果這個這個sort字段大于max_sort_length的值一也，那么以max_sort_length設(shè)置為準(zhǔn)，這步代碼如下：

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個字符來計算長度的，而不是我們通骋人眨看到的Innodb中實(shí)際占用的字符數(shù)量法焰。這是排序使用空間大于Innodb實(shí)際數(shù)據(jù)文件大小的一個原因。

下面我們以（a2 varchar(300) a3 varchar(300) order by a2,a3）為例實(shí)際看看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í)際的數(shù)據(jù)，那么無外乎兩種方式如下：

original filesort algorithm：只存儲rowid或者主鍵做為額外的字段扬卷，然后進(jìn)行回表抽取數(shù)據(jù)。我們按照源碼的描述蚕断，將這種關(guān)聯(lián)回表的字段叫做ref字段（源碼中變量叫做ref_length）。
modified filesort algorithm：將處于read_set（需要讀取的字段）全部放到額外字段中，這樣不需要回表讀取數(shù)據(jù)了桐款。我們按照源碼的描述，將這些額外存儲的字段叫做addon字段（源碼中變量叫做addon_length）。

這里一步就是要來判斷到底使用那種算法朋凉，其主要標(biāo)準(zhǔn)就是參數(shù)max_length_for_sort_data，其默認(rèn)大小為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、獲取字段的長度

這里就是實(shí)際的長度了比如我們的a1 varchar(300)，且字符集為UTF8，那么其長度≈ 300*3 （900）。

4做修、獲取可以pack（打包）字段的長度

和上面不同霍狰，對于int這些固定長度類型的字段抡草，只有可變長度的類型的字段才需要進(jìn)行打包技術(shù)。

5蔗坯、循環(huán)結(jié)束康震，獲取addon字段的總長度，獲取可以pack（打包）字段的總長度

循環(huán)結(jié)束后可以獲取addon字段的總長度，但是需要注意addon字段和sort字段可能包含重復(fù)的字段鹦付，比如例2中sort字段為a2辑鲤、a3决左，addon字段為a1漩勤、a2、a3谅阿。

如果滿足如下條件：

addon字段的總長度+sort字段的總長度 > max_length_for_sort_data

那么將使用original filesort algorithm（回表排序）的方式糯崎，否則使用modified filesort algorithm的方式進(jìn)行。下面是這一句代碼：

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個案例痹届，因?yàn)槲覀儗1,a2,a3都是需要訪問的，且他們的大小均為varchar(300) UTF8，那么addon字段長度大約為300 * 3 * 3=2700字節(jié) ，其次我們前面計算了sort字段大約為1202字節(jié)碉渡，因此 2700+1202 是遠(yuǎn)遠(yuǎn)大于max_length_for_sort_data的默認(rèn)設(shè)置1024字節(jié)的，因此會使用original filesort algorithm方式進(jìn)行排序。

如果是第2節(jié)例子中的第2個案例呢，顯然要小很多了（每個字段varchar（20）），大約就是20 * 3 * 3（addon字段）+82（sort字段）它是小于1024字節(jié)的捅暴，因此會使用modified filesort algorithm的排序方式，并且這些addon字段基本都可以使用打包（pack）技術(shù)，來節(jié)省空間。但是需要注意的是無論如何（sort字段）是不能進(jìn)行打包（pack）的，而固定長度類型不需要打包（pack）壓縮空間梯捕。

六魁兼、階段4:確認(rèn)每行的長度

有了上面的就計算后每一行的長度（如果可以打包是打包前的長度）章钾，下面就是這個計算過程糊啡。

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; //實(shí)際上就是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(主鍵) +排序字段長度 ，因?yàn)閍ddon_length為0

好了我們稍微總結(jié)一下：

original filesort algorithm：每行長度為sort字段的總長度+ref字段長度（主鍵或者rowid）棚蓄。
modified filesort algorithm：每行的長度為sort字段的總長度+addon字段的長度（需要訪問的字段總長度）堕扶。

當(dāng)然到底使用那種算法參考上一節(jié)。但是要注意了對于varchar這種可變長度是以定義的大小為準(zhǔn)了梭依，比如UTF8 varchar（300）就是300*3= 900 而不是實(shí)際存儲的大小稍算，而固定長度沒有變化。好了役拴，還是回頭看看第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:確認(rèn)最大內(nèi)存分配

這里的分配內(nèi)存就和參數(shù)sort_buffer_size大小有關(guān)了。但是是不是每次都會分配至少sort_buffer_size大小的內(nèi)存的呢儡炼？其實(shí)不是妓湘，MySQL會判斷是否表很小的情況，也就是做一個簡單的運(yùn)算乌询，目的在于節(jié)省內(nèi)存的開銷榜贴，這里我們將來描述。

1妹田、大概計算出Innodb層主鍵葉子結(jié)點(diǎn)的行數(shù)

這一步主要通過（聚集索引葉子結(jié)點(diǎn)的空間大小/聚集索引每行大小 * 2）計算出一個行的上限唬党，調(diào)入函數(shù)ha_innobase::estimate_rows_upper_bound，源碼如下：

num_rows= table->file->estimate_rows_upper_bound();
//上限來自于Innodb 葉子聚集索引葉子結(jié)點(diǎn)/聚集索引長度 *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)存的標(biāo)準(zhǔn)

然后對比兩個值以小值為準(zhǔn)，如下：

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ù)進(jìn)行分配驻龟。

八温眉、階段6:讀取數(shù)據(jù)，進(jìn)行內(nèi)存排序

到這里準(zhǔn)備工作已經(jīng)完成了翁狐，接下就是以行為單位讀取數(shù)據(jù)了类溢，然后對過濾掉where條件的剩下的數(shù)據(jù)進(jìn)行排序。如果需要排序的數(shù)據(jù)很多露懒，那么等排序內(nèi)存寫滿后會進(jìn)行內(nèi)存排序闯冷，然后將排序的內(nèi)容寫入到排序臨時文件中，等待下一步做外部的歸并排序懈词。

作為歸并排序而言蛇耀，每一個歸并的文件片段必須是排序好的，否則歸并排序是不能完成的坎弯，因此寫滿排序內(nèi)存后需要做內(nèi)存排序纺涤。如果寫不滿呢，那么做一次內(nèi)存排序就好了抠忘。下面我們來看看這個過程撩炊，整個過程集中在find_all_keys函數(shù)中。

1崎脉、讀取需要的數(shù)據(jù)

實(shí)際上在這一步之前還會做read_set的更改拧咳，因?yàn)閷τ趏riginal filesort algorithm（回表排序）的算法來講不會讀取全部需要的字段，為了簡單起見不做描述了荧嵌。這一步就是讀取一行數(shù)據(jù)了呛踊，這里會進(jìn)入Innodb層讀取數(shù)據(jù)砾淌，具體流程不做解釋了啦撮，下面是這一行代碼：

error= file->ha_rnd_next(sort_form->record[0]); //讀取一行數(shù)據(jù)

2、將Rows_examined 加1

這里這個指標(biāo)對應(yīng)的就是慢查中的Rows_examined了汪厨，這個指標(biāo)在有排序的情況下會出現(xiàn)重復(fù)計算的情況赃春，但是這里還是正確的，重復(fù)的部分后面再說劫乱。

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）的字段進(jìn)行壓縮操作座每。對于varchar字段的打包函數(shù)就是Field_varstring::pack，簡單的說存儲的是實(shí)際的大小摘悴，而非定義的大小峭梳。

整個過程位于find_all_keys->Sort_param::make_sortkey 函數(shù)中。這一步還涉及到了我們非常關(guān)心的一個問題蹂喻，到底排序的數(shù)據(jù)如何存儲的問題葱椭，需要仔細(xì)閱讀。下面我們就debug一下第2節(jié)中兩個例子的不同存儲方式口四。

既然要去看內(nèi)存中的數(shù)據(jù)挫以，我們只要看它最終拷貝的內(nèi)存數(shù)據(jù)是什么就好了，那么真相將會大白窃祝，我們只需要將斷點(diǎn)放到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)
    
我們以第二行為查看目標(biāo)

由于篇幅的關(guān)系探膊，我展示其中的一部分杠愧，因?yà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í)際有用的數(shù)據(jù)也就只有0x45 0x00這兩個字節(jié)了，而0x45正是我們的大寫字母E腌闯，也就是數(shù)據(jù)中的e绳瘟，這和比較字符集有關(guān)。這里的0X20 0X00占用了大量的空間姿骏，我們最初計算sort 字段大約為1200字節(jié)糖声，實(shí)際上只有少量的幾個字節(jié)有用。

這里對于sort字段而言分瘦，比實(shí)際存儲的數(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    |
+------+------+------+
我們以第一行為查看目標(biāo)

這里數(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）而言，這里小了很多蹋肮，因?yàn)樽隽舜虬╬ack）即：

0x01 0x62：數(shù)據(jù)b0x01 0x64：數(shù)據(jù)d0x01 0x64：數(shù)據(jù)d而0x01應(yīng)該就是長度了出刷。

不管怎么說，對于sort字段而言依舊比實(shí)際存儲的數(shù)據(jù)大很多坯辩。

**5馁龟、如果sort buffer存滿，對sort buffer中的數(shù)據(jù)進(jìn)行排序漆魔，然后寫入到臨時文件 **

如果需要排序的數(shù)據(jù)量很大的話坷檩，那么sort buffer肯定是不能容下的，因此如果寫滿后就進(jìn)行一次內(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ù)進(jìn)行排序和寫入外部排序文件，這里核心就是先排序藐窄，然后循環(huán)每條排序文件寫入到外部排序文件资昧。下面我來驗(yàn)證一下寫入臨時文件的長度，我將第2節(jié)中的例子2數(shù)據(jù)擴(kuò)大了N倍后枷邪，讓其使用外部文件排序榛搔，下面是驗(yàn)證結(jié)果诺凡，斷點(diǎn)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，這里是準(zhǔn)確的結(jié)果蒙袍，沒有重復(fù)計數(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:進(jìn)行最終排序

這里涉及2個部分如下：

如果sort buffer不滿豆胸，則這里開始進(jìn)行排序，調(diào)入函數(shù)save_index巷疼。
如果sort buffer滿了晚胡，則進(jìn)行歸并排序，調(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存在。

這個很容易驗(yàn)證猿规，將斷點(diǎn)放到merge_buffers和merge_index上就可以驗(yàn)證了衷快，如下：

臨時文件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)

但是由于能力有限對于歸并排序的具體過程我并沒有仔細(xì)學(xué)習(xí)了，這里給一個大概的接口姨俩。注意這里每次調(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（回表排序）缔恳，但是對于回表操作有如下標(biāo)準(zhǔn)：

如果沒有使用到外部排序臨時文件則說明排序量不大，則使用普通的回表方式洁闰，調(diào)入函數(shù)rr_from_pointers歉甚，也就是單行回表方式。
如果使用到了外部排序臨時文件則說明排序量較大扑眉，需要使用到批量回表方式纸泄，這個時候大概的步驟就是讀取rowid（主鍵）排序，然后批量回表腰素，這將會在read_rnd_buffer_size指定的內(nèi)存中完成聘裁，調(diào)入函數(shù)rr_from_cache。這也是一種優(yōu)化方式耸弄，因?yàn)榛乇硪话闶巧⒘械倪只ⅲ鷥r很大。

2计呈、關(guān)于排序中Rows_examined的計算

首先這個值我說的是慢查詢的中的Rows_examined砰诵，在排序中會出現(xiàn)重復(fù)計數(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)缦吕矸危灰m結(jié)時間（因?yàn)槲夜室鈊ebug停止了一會），我們只關(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ù)會重復(fù)計數(shù)一次品洛。因此就是8+3=11锰提，也就是說有3條數(shù)據(jù)重復(fù)計數(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é)實(shí)際上是在執(zhí)行階段生成的，需要注意幾點(diǎn)如下：

這里的examined_rows和慢查詢中的Rows_examined不一樣士飒，因?yàn)檫@里不會有重復(fù)計數(shù)挽霉，是準(zhǔn)確的。
這里還會說明是否使用了優(yōu)先隊(duì)列排序即“filesort_priority_queue_optimization”部分变汪。
通過“sort_buffer_size”可以發(fā)現(xiàn)侠坎，這里并沒有分配參數(shù)sort_buffer_size指定的大小，節(jié)約了內(nèi)存裙盾，這在第7節(jié)說明了实胸。

其他指標(biāo)在第9節(jié)已經(jīng)說明過了，不在描述番官。

十三庐完、回到問題本身

好了，大概的流程我描述了一遍徘熔，這些流程都是主要流程门躯，實(shí)際上的流程復(fù)雜很多。那么我們回到最開始的案例上來酷师。他的max_sort_length和max_length_for_sort_data均為默認(rèn)值1024讶凉。

案例中的group by實(shí)際就是一個排序操作染乌，我們從執(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 字段是不會進(jìn)行壓縮的谨读。

我大概算了一下sort字段的全部大小約為（3900 * 2) 字節(jié)局装，可以看到一行數(shù)據(jù)的sort字段基本達(dá)到了8K的容量，而addon字段的長度（未打包壓縮前）會更大漆腌，顯然超過max_length_for_sort_data的設(shè)置贼邓，因此對于這樣的排序顯然不可能使用modified filesort algorithm（不回表排序了），使用的是original filesort algorithm（回表排序）闷尿，因此一行的記錄就是（sort 字段+主鍵）了塑径，主鍵大小可以忽略，最終一行記錄的大小就是8K左右填具，這個值通常會遠(yuǎn)遠(yuǎn)大于Innodb壓縮后存儲varchar字段的大小统舀，這也是為什么本例中雖然表只有30G左右但是臨時文件達(dá)到了200G以上的原因了。

好了劳景，我們來重現(xiàn)一下問題誉简，我們使用第2節(jié)的例1，我們將其數(shù)據(jù)增多盟广，原理上我們的例1會使用到original filesort algorithm（回表排序）的方式闷串，因?yàn)檫@里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文件的大小：

[root@gp1 test]# du -hs bgtest5.ibd
11M bgtest5.ibd
[root@gp1 test]#

下面我們就需要將gdb的斷點(diǎn)打在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é)果一致先较。這遠(yuǎn)遠(yuǎn)超過了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)

因此得到證明闲勺，排序的臨時文件遠(yuǎn)遠(yuǎn)大于ibd文件的現(xiàn)象是可能出現(xiàn)的。

十四扣猫、全文總結(jié)

本文寫了很多菜循，這里需要做一個詳細(xì)的總結(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ù)進(jìn)行壓縮，節(jié)省空間橄务♂Ｍ校可以參考第3、第4、第5重挑、第6嗓化、第8節(jié)。

總結(jié)2：排序使用什么樣的方法進(jìn)行谬哀？

original filesort algorithm（回表排序）

如果使用的是sort字段+ref字段進(jìn)行排序刺覆，那么必須要回表獲取需要的數(shù)據(jù)，如果排序使用了臨時文件（也就是說使用外部歸并排序史煎，排序量較大）則會使用批量回表谦屑，批量回表會涉及到read_rnd_buffer_size參數(shù)指定的內(nèi)存大小，主要用于排序和結(jié)果返回篇梭。

如果排序沒有使用臨時文件（內(nèi)存排序就可以完成氢橙，排序量較小）則采用單行回表恬偷。

modified filesort algorithm（不回表排序）

如果使用的是sort字段+addon字段進(jìn)行排序悍手，那么使用不回表排序，所有需要的字段均在排序過程中進(jìn)行存儲袍患，addon字段中的可變長度字段可以進(jìn)行打包（pack）壓縮節(jié)省空間坦康。

其次sort字段和addon字段中可能有重復(fù)的字段，比如例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)存可以容納的行上限曲秉，獲取它們小值進(jìn)行確認(rèn)最終內(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包含了重復(fù)計數(shù)妆够，重復(fù)的部分為where條件過濾后做了排序的部分识啦。
OPTIMIZER_TRACE中的examined_rows不包含重復(fù)計數(shù)，為實(shí)際Innodb層掃描的行數(shù)神妹。

可以參考11節(jié)颓哮。

總結(jié)5：外部排序臨時文件的使用是什么樣的？

實(shí)際上一個語句的臨時文件不止一個鸵荠，但是它們都以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)先隊(duì)列 order by limit 返回少量行常用顷牌，提高排序效率，但是注意order by limit n,m 如果n過大可能會涉及到排序算法的切換）
內(nèi)存排序（快速排序）在通過OPTIMIZER_TRACE可以查看是否使用使用了優(yōu)先隊(duì)列算法塞淹，參考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)該考慮是否可以使用索引來避免排序，如果不能則需要考慮下面的要點(diǎn)：

order by 后面的字段滿足需求即可套耕，盡可能的少谁帕。
order by 后面涉及的字段盡量為固定長度的字段類型，而不是可變字段類型如varchar冯袍。因?yàn)?strong>sort字段不能壓縮匈挖。
不要過大的定義可變字段長度，應(yīng)該合理定義，例如varchar（10）能夠滿足需求不要使用varchar（50）关划，這些空間雖然在Innodb層存儲會壓縮小染，但是MySQL層確可能使用全長度（比如sort字段）。
在查詢中盡量不要用（select *）而使用需要查詢的字段贮折，這將會減少addon字段的個數(shù)裤翩，在我另外一個文章還講述了（select *）的其他的缺點(diǎn)

參考：http://www.reibang.com/p/ce063e2024ad

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市调榄，隨后出現(xiàn)的幾起案子踊赠，更是在濱河造成了極大的恐慌，老刑警劉巖每庆，帶你破解...
沈念sama閱讀 211,743評論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件筐带，死亡現(xiàn)場離奇詭異，居然都是意外死亡缤灵，警方通過查閱死者的電腦和手機(jī)伦籍，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,296評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來腮出，“玉大人帖鸦，你說我怎么就攤上這事∨叱埃” “怎么了作儿？”我有些...
開封第一講書人閱讀 157,285評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長馋劈。經(jīng)常有香客問我攻锰，道長，這世上最難降的妖魔是什么妓雾？我笑而不...
開封第一講書人閱讀 56,485評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任娶吞，我火速辦了婚禮，結(jié)果婚禮上君珠，老公的妹妹穿的比我還像新娘寝志。我一直安慰自己，他們只是感情好策添，可當(dāng)我...
茶點(diǎn)故事閱讀 65,581評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布材部。她就那樣靜靜地躺著，像睡著了一般唯竹。火紅的嫁衣襯著肌膚如雪乐导。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,821評論 1贊 290
城市分裂傳說
那天浸颓，我揣著相機(jī)與錄音物臂，去河邊找鬼旺拉。笑死，一個胖子當(dāng)著我的面吹牛棵磷，可吹牛的內(nèi)容都是我干的蛾狗。我是一名探鬼主播，決...
沈念sama閱讀 38,960評論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼仪媒，長吁一口氣：“原來是場噩夢啊……” “哼沉桌！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起算吩，我...
開封第一講書人閱讀 37,719評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤留凭，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后偎巢，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蔼夜，經(jīng)...
沈念sama閱讀 44,186評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,516評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年压昼，在試婚紗的時候發(fā)現(xiàn)自己被綠了求冷。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,650評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡巢音，死狀恐怖遵倦，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情官撼，我是刑警寧澤，帶...
沈念sama閱讀 34,329評論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布似谁，位于F島的核電站傲绣，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏巩踏。R本人自食惡果不足惜秃诵，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,936評論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望塞琼。院中可真熱鬧菠净，春花似錦、人聲如沸彪杉。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,757評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽派近。三九已至攀唯，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間渴丸，已是汗流浹背侯嘀。一陣腳步聲響...
開封第一講書人閱讀 31,991評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工另凌，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人戒幔。一個月前我還...
沈念sama閱讀 46,370評論 2贊 360
代替公主和親
正文我出身青樓吠谢，卻偏偏與公主長得像，于是被迫代替她去往敵國和親诗茎。傳聞我的和親對象是個殘疾皇子囊卜，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,527評論 2贊 349

MySQL：排序（filesort）詳細(xì)解析（8000字長文）

推薦閱讀更多精彩內(nèi)容