全字段排序和rowId排序
建表語(yǔ)句如下：
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;
sql語(yǔ)句如下：
select city,name,age from t where city='杭州' order by name limit 1000 ;
相關(guān)概念定義
sort_buffer：MySQL會(huì)給每個(gè)線程分配一塊內(nèi)存區(qū)域用于排序捧毛，這塊區(qū)域叫sort_buffer昔汉。如果待排序的數(shù)據(jù)足夠存放在sort_buffer中，那么就會(huì)直接用這塊區(qū)域進(jìn)行排序瘸味，算法為快速排序宫仗；如果待排序的數(shù)據(jù)超過(guò)了sort_buffer大小够挂，會(huì)使用磁盤臨時(shí)文件來(lái)輔助排序旁仿，算法為歸并排序。
全字段排序：sort_buffer中存儲(chǔ)的待排序數(shù)據(jù)孽糖，包括需要返回的所有字段枯冈，比如，上面sql語(yǔ)句中的city,name,age办悟，雖然只用name來(lái)排序尘奏，但是還是冗余存放了city和age的數(shù)據(jù)，排序完直接返回即可病蛉。
rowId排序：sort_buffer中存儲(chǔ)的待排序數(shù)據(jù)炫加，只包括待排序字段和對(duì)應(yīng)行的主鍵id，比如铺然，上面sql語(yǔ)句俗孝，如果使用rowId排序，那么sort_buffer中只會(huì)存儲(chǔ)name和rowID字段魄健，等到排序完畢赋铝，需要回表查詢出來(lái)需要返回的其他字段數(shù)據(jù)蝶棋。
什么時(shí)候選擇全字段排序答毫？什么時(shí)候選擇rowID排序怖辆？
當(dāng)MySQL判斷拱撵，當(dāng)待處理表為InnoDB磁盤表時(shí)螺垢，會(huì)優(yōu)先使用全字段排序捷沸，目的是為了減少rowID排序最后需要再次回表查詢需要返回的字段的操作開銷焊刹，但是全字段排序如果需要冗余的單行數(shù)據(jù)量太大時(shí)矗钟，就不會(huì)選擇全字段排序助隧，而選擇rowID排序筑凫。
- 如何判斷單行數(shù)據(jù)是否過(guò)大？MySQL中會(huì)使用max_length_for_sort_data來(lái)判斷。
為什么單行數(shù)據(jù)量大漏健，就需要切換算法嚎货？
如果單行數(shù)據(jù)量太大，內(nèi)存中能存儲(chǔ)下的行數(shù)就會(huì)變少蔫浆，就需要使用更多的磁盤臨時(shí)文件來(lái)存儲(chǔ)殖属，排序的性能會(huì)比較差。
內(nèi)存臨時(shí)表和磁盤臨時(shí)表
看這個(gè)業(yè)務(wù)：
有一張單詞表瓦盛，我們需要隨機(jī)顯示三個(gè)單詞給用戶洗显。
建表語(yǔ)句和生成數(shù)據(jù)存儲(chǔ)過(guò)程：
mysql> CREATE TABLE `words` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`word` varchar(64) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB;
delimiter ;;
create procedure idata()
begin
declare i int;
set i=0;
while i<10000 do
insert into words(word) values(concat(char(97+(i div 1000)), char(97+(i % 1000 div 100)), char(97+(i % 100 div 10)), char(97+(i % 10))));
set i=i+1;
end while;
end;;
delimiter ;
call idata();
SQL語(yǔ)句：
mysql> select word from words order by rand() limit 3;
注：rand() 這個(gè)函數(shù)會(huì)返回一個(gè)0~1之間的隨機(jī)小數(shù)值。
當(dāng)需要使用這個(gè)隨機(jī)值來(lái)排序時(shí)原环，就需要使用臨時(shí)表來(lái)存儲(chǔ)這個(gè)隨機(jī)數(shù)據(jù)挠唆。
內(nèi)存臨時(shí)表
執(zhí)行過(guò)程如下：
- 首先生成Memory引擎的內(nèi)存臨時(shí)表，在主鍵索引中嘱吗，依次取出所有的word值玄组，調(diào)用rand函數(shù)生成 一個(gè)隨機(jī)值，把word和隨機(jī)值存儲(chǔ)到臨時(shí)表中谒麦。
- 然后針對(duì)這個(gè)臨時(shí)表開始排序俄讹。使用sort_buffer并且使用rowId算法。
- 這里為什么使用rowID算法了呢绕德？因?yàn)樯厦嫣岬竭^(guò)的全字段排序會(huì)被優(yōu)先選擇患膛，前提是待排序的表是磁盤表；現(xiàn)在的待排序表為Memory引擎的內(nèi)存表耻蛇，雖然使用rowID踪蹬，但是最后的回表查詢都是在內(nèi)存中完成的，開銷大大降低臣咖，MySQL當(dāng)然會(huì)選擇可以一次排序更多行的rowId算法跃捣。
磁盤臨時(shí)表
MySQL中有一個(gè)參數(shù)，tmp_table_size 這個(gè)參數(shù)限制了內(nèi)存臨時(shí)表的大小亡哄，默認(rèn)值是 16M枝缔。如果臨時(shí)表大于16M，就會(huì)使用磁盤臨時(shí)表來(lái)存儲(chǔ)臨時(shí)數(shù)據(jù)蚊惯，默認(rèn)是InnoDB引擎表愿卸。關(guān)于默認(rèn)的InnoDB引擎表的排序過(guò)程，在上面的全字段排序和rowId排序中已經(jīng)介紹過(guò)了截型。
新的排序算法
上面介紹過(guò)趴荸，InnoDB磁盤表，要么使用基于全內(nèi)存的快排宦焦，要么基于輔助的磁盤臨時(shí)文件的歸并排序发钝，其實(shí)在MySQL5.6之后顿涣，還引入了一種新的排序算法，優(yōu)先隊(duì)列排序算法酝豪。
為什么需要這種算法涛碑？
考慮剛才的SQL語(yǔ)句
mysql> select word from words order by rand() limit 3;
無(wú)論是使用快排還是歸并排序，他們都是基于所有的數(shù)據(jù)進(jìn)行排序孵淘。
但分析上面的sql語(yǔ)句蒲障，其實(shí)我們只需要排序后的前面三條數(shù)據(jù)，并且后面的排序數(shù)據(jù)在計(jì)算上來(lái)說(shuō)是浪費(fèi)資源的瘫证。有沒(méi)有一種算法揉阎，可以通過(guò)排序，只得到我們需要的最小的三條或者最大的三條數(shù)據(jù)背捌，并且盡量不使用磁盤臨時(shí)文件呢毙籽？
優(yōu)先隊(duì)列排序算法
優(yōu)先隊(duì)列排序算法，如果執(zhí)行上面的sql語(yǔ)句毡庆，會(huì)先從表中順序取最開始的3條數(shù)據(jù)坑赡，存儲(chǔ)到一個(gè)最大堆中（最大堆：堆頭永遠(yuǎn)是容器內(nèi)數(shù)據(jù)的最大值）。然后遍歷后面的所有數(shù)據(jù)扭仁，判斷當(dāng)前取值和堆最大值比較垮衷，如果比堆最大值小厅翔，就把新數(shù)據(jù)入堆乖坠，并且重新排序堆中的順序，保持堆頭為最大值刀闷。
經(jīng)過(guò)這種排序以后熊泵，堆中就是我們需要的前三個(gè)最小值了。
示意圖如下：
什么時(shí)候會(huì)選擇這種算法甸昏？
當(dāng)存在limit字句時(shí)顽分，并且limit需要的維護(hù)的最大堆的大小小于 sort_buffer，就會(huì)使用這個(gè)算法施蜜。
