本文從一個(gè)App的性能問題說起，和你說說 MySQL 中的另外一種排序需求，希望能夠加深你對(duì) MySQL 排序邏輯的理解。

這個(gè)App 首頁有一個(gè)隨機(jī)顯示單詞的功能，也就是根據(jù)每個(gè)用戶的級(jí)別有一個(gè)單詞表，然后這個(gè)用戶每次訪問首頁的時(shí)候，都會(huì)隨機(jī)滾動(dòng)顯示三個(gè)單詞。他們發(fā)現(xiàn)隨著單詞表變大，選單詞這個(gè)邏輯變得越來越慢，甚至影響到了首頁的打開速度。

現(xiàn)在，如果讓你來設(shè)計(jì)這個(gè) SQL 語句，你會(huì)怎么寫呢？這個(gè)表的建表語句和初始數(shù)據(jù)的命令如下：

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();

為了便于量化說明，在這個(gè)表里面插入了 10000 行記錄。接下來，我們就一起看看要隨機(jī)選擇 3 個(gè)單詞，有什么方法實(shí)現(xiàn)，存在什么問題以及如何改進(jìn)。

內(nèi)存臨時(shí)表

• 首先，你會(huì)想到用 order by rand() 來實(shí)現(xiàn)這個(gè)邏輯。

mysql> select word from words order by rand() limit 3;

• 這個(gè)語句的意思很直白，隨機(jī)排序取前 3 個(gè)。雖然這個(gè) SQL 語句寫法很簡(jiǎn)單，但執(zhí)行流程卻有點(diǎn)復(fù)雜的。我們先用 explain 命令來看看這個(gè)語句的執(zhí)行情況。

explain查詢方法

• Extra 字段顯示 Using temporary，表示的是需要使用臨時(shí)表；Using filesort，表示的是需要執(zhí)行排序操作。因此這個(gè) Extra 的意思就是，需要臨時(shí)表，并且需要在臨時(shí)表上排序。
• 如下圖看回顧一下上文章中全字段排序和 rowid 排序的內(nèi)容。

全字段排序

rowid排序

• 對(duì)于臨時(shí)內(nèi)存表的排序來說，它會(huì)選擇哪一種算法呢？回顧一下上文的一個(gè)結(jié)論：對(duì)于 InnoDB 表來說，執(zhí)行全字段排序會(huì)減少磁盤訪問，因此會(huì)被優(yōu)先選擇。
• 強(qiáng)調(diào)了“InnoDB 表”，你肯定想到了，對(duì)于內(nèi)存表，回表過程只是簡(jiǎn)單地根據(jù)數(shù)據(jù)行的位置，直接訪問內(nèi)存得到數(shù)據(jù)，根本不會(huì)導(dǎo)致多訪問磁盤。優(yōu)化器沒有了這一層顧慮，那么它會(huì)優(yōu)先考慮的，就是用于排序的行越小越好了，所以，MySQL 這時(shí)就會(huì)選擇 rowid 排序。
• 理解了這個(gè)算法選擇的邏輯，我們?cè)賮砜纯凑Z句的執(zhí)行流程。同時(shí)，通過今天的這個(gè)例子，我們來嘗試分析一下語句的掃描行數(shù)。這條語句的執(zhí)行流程是這樣的：
  1. 創(chuàng)建一個(gè)臨時(shí)表。這個(gè)臨時(shí)表使用的是 memory 引擎，表里有兩個(gè)字段，第一個(gè)字段是 double 類型，為了后面描述方便，記為字段 R，第二個(gè)字段是 varchar(64) 類型，記為字段 W。并且，這個(gè)表沒有建索引。
  2. 從 words 表中，按主鍵順序取出所有的 word 值。對(duì)于每一個(gè) word 值，調(diào)用 rand() 函數(shù)生成一個(gè)大于 0 小于 1 的隨機(jī)小數(shù)，并把這個(gè)隨機(jī)小數(shù)和 word 分別存入臨時(shí)表的 R 和 W 字段中，到此，掃描行數(shù)是 10000。
  3. 現(xiàn)在臨時(shí)表有 10000 行數(shù)據(jù)了，接下來你要在這個(gè)沒有索引的內(nèi)存臨時(shí)表上，按照字段 R 排序。
  4. 初始化 sort_buffer。sort_buffer 中有兩個(gè)字段，一個(gè)是 double 類型，另一個(gè)是整型。
  5. 從內(nèi)存臨時(shí)表中一行一行地取出 R 值和位置信息（我后面會(huì)和你解釋這里為什么是“位置信息”），分別存入 sort_buffer 中的兩個(gè)字段里。這個(gè)過程要對(duì)內(nèi)存臨時(shí)表做全表掃描，此時(shí)掃描行數(shù)增加 10000，變成了 20000。
  6. 在 sort_buffer 中根據(jù) R 的值進(jìn)行排序。注意，這個(gè)過程沒有涉及到表操作，所以不會(huì)增加掃描行數(shù)。
  7. 排序完成后，取出前三個(gè)結(jié)果的位置信息，依次到內(nèi)存臨時(shí)表中取出 word 值，返回給客戶端。這個(gè)過程中，訪問了表的三行數(shù)據(jù)，總掃描行數(shù)變成了 20003。
• 我們通過慢查詢?nèi)罩荆╯low log）來驗(yàn)證一下我們分析得到的掃描行數(shù)是否正確。

# Query_time: 0.900376  Lock_time: 0.000347 Rows_sent: 3 Rows_examined: 20003
SET timestamp=1541402277;
select word from words order by rand() limit 3;

• 其中，Rows_examined：20003 就表示這個(gè)語句執(zhí)行過程中掃描了 20003 行，也就驗(yàn)證了我們分析得出的結(jié)論。

隨機(jī)排序完整流程圖

• 圖中的 pos 就是位置信息，這里的“位置信息”是個(gè)什么概念？在上一篇文章中，我們對(duì) InnoDB 表排序的時(shí)候，明明用的還是 ID 字段。
  • 基本概念：MySQL 的表是用什么方法來定位“一行數(shù)據(jù)”的。
  • 如果你創(chuàng)建的表沒有主鍵，或者把一個(gè)表的主鍵刪掉了，那么 InnoDB 會(huì)自己生成一個(gè)長度為 6 字節(jié)的 rowid 來作為主鍵。
• 這也就是排序模式里面，rowid 名字的來歷。實(shí)際上它表示的是：每個(gè)引擎用來唯一標(biāo)識(shí)數(shù)據(jù)行的信息。
  • 對(duì)于有主鍵的 InnoDB 表來說，這個(gè) rowid 就是主鍵 ID；
  • 對(duì)于沒有主鍵的 InnoDB 表來說，這個(gè) rowid 就是由系統(tǒng)生成的；
  • MEMORY 引擎不是索引組織表。在這個(gè)例子里面，你可以認(rèn)為它就是一個(gè)數(shù)組。因此，這個(gè) rowid 其實(shí)就是數(shù)組的下標(biāo)。
• 總結(jié)如下：order by rand() 使用了內(nèi)存臨時(shí)表，內(nèi)存臨時(shí)表排序的時(shí)候使用了 rowid 排序方法。

磁盤臨時(shí)表

• 那么，是不是所有的臨時(shí)表都是內(nèi)存表呢？其實(shí)不是的。tmp_table_size 這個(gè)配置限制了內(nèi)存臨時(shí)表的大小，默認(rèn)值是 16M。如果臨時(shí)表大小超過了 tmp_table_size，那么內(nèi)存臨時(shí)表就會(huì)轉(zhuǎn)成磁盤臨時(shí)表。
  • 磁盤臨時(shí)表使用的引擎默認(rèn)是 InnoDB，是由參數(shù) internal_tmp_disk_storage_engine 控制的。
  • 當(dāng)使用磁盤臨時(shí)表的時(shí)候，對(duì)應(yīng)的就是一個(gè)沒有顯式索引的 InnoDB 表的排序過程。
  • 為了復(fù)現(xiàn)這個(gè)過程，把 tmp_table_size 設(shè)置成 1024，把 sort_buffer_size 設(shè)置成 32768, 把 max_length_for_sort_data 設(shè)置成 16。

set tmp_table_size=1024;
set sort_buffer_size=32768;
set max_length_for_sort_data=16;
/* 打開 optimizer_trace，只對(duì)本線程有效 */
SET optimizer_trace='enabled=on'; 
/* 執(zhí)行語句 */
select word from words order by rand() limit 3;
/* 查看 OPTIMIZER_TRACE 輸出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G

OPTIMIZER_TRACE部分結(jié)果

• 因?yàn)閷?max_length_for_sort_data 設(shè)置成 16，小于 word 字段的長度定義，所以我們看到 sort_mode 里面顯示的是 rowid 排序，這個(gè)是符合預(yù)期的，參與排序的是隨機(jī)值 R 字段和 rowid 字段組成的行。
• 這時(shí)候你可能心算了一下，發(fā)現(xiàn)不對(duì)。R 字段存放的隨機(jī)值就 8 個(gè)字節(jié)，rowid 是 6 個(gè)字節(jié)，數(shù)據(jù)總行數(shù)是 10000，這樣算出來就有 140000 字節(jié)，超過了 sort_buffer_size 定義的 32768 字節(jié)了。但是，number_of_tmp_files 的值居然是 0，難道不需要用臨時(shí)文件嗎？
• 這個(gè) SQL 語句的排序確實(shí)沒有用到臨時(shí)文件，采用是 MySQL 5.6 版本引入的一個(gè)新的排序算法，即：優(yōu)先隊(duì)列排序算法。接下來，我們就看看為什么沒有使用臨時(shí)文件的算法，也就是歸并排序算法，而是采用了優(yōu)先隊(duì)列排序算法。
  • 其實(shí)，我們現(xiàn)在的 SQL 語句，只需要取 R 值最小的 3 個(gè) rowid。但是，如果使用歸并排序算法的話，雖然最終也能得到前 3 個(gè)值，但是這個(gè)算法結(jié)束后，已經(jīng)將 10000 行數(shù)據(jù)都排好序了。
  • 也就是說，后面的 9997 行也是有序的了。但，我們的查詢并不需要這些數(shù)據(jù)是有序的。所以，想一下就明白了，這浪費(fèi)了非常多的計(jì)算量。
• 而優(yōu)先隊(duì)列算法，就可以精確地只得到三個(gè)最小值，執(zhí)行流程如下：
  • 對(duì)于這 10000 個(gè)準(zhǔn)備排序的 (R,rowid)，先取前三行，構(gòu)造成一個(gè)堆；
  • 取下一個(gè)行 (R’,rowid’)，跟當(dāng)前堆里面最大的 R 比較，如果 R’小于 R，把這個(gè) (R,rowid) 從堆中去掉，換成 (R’,rowid’)；
  • 重復(fù)第 2 步，直到第 10000 個(gè) (R’,rowid’) 完成比較。

優(yōu)先隊(duì)列排序算法示意圖

• 上圖模擬 6 個(gè) (R,rowid) 行，通過優(yōu)先隊(duì)列排序找到最小的三個(gè) R 值的行的過程。整個(gè)排序過程中，為了最快地拿到當(dāng)前堆的最大值，總是保持最大值在堆頂，因此這是一個(gè)最大堆。
• OPTIMIZER_TRACE 結(jié)果中，filesort_priority_queue_optimization 這個(gè)部分的 chosen=true，就表示使用了優(yōu)先隊(duì)列排序算法，這個(gè)過程不需要臨時(shí)文件，因此對(duì)應(yīng)的 number_of_tmp_files 是 0。
• 這個(gè)流程結(jié)束后，我們構(gòu)造的堆里面，就是這個(gè) 10000 行里面 R 值最小的三行。然后，依次把它們的 rowid 取出來，去臨時(shí)表里面拿到 word 字段，這個(gè)過程就跟上文的 rowid 排序的過程一樣了。
• 回顧上文的查詢語句：

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

• 這里也用到了 limit，為什么沒用優(yōu)先隊(duì)列排序算法呢？原因是，這條 SQL 語句是 limit 1000，如果使用優(yōu)先隊(duì)列算法的話，需要維護(hù)的堆的大小就是 1000 行的 (name,rowid)，超過了我設(shè)置的 sort_buffer_size 大小，所以只能使用歸并排序算法。
• 總之，不論是使用哪種類型的臨時(shí)表，order by rand() 這種寫法都會(huì)讓計(jì)算過程非常復(fù)雜，需要大量的掃描行數(shù)，因此排序過程的資源消耗也會(huì)很大。那怎么正確地隨機(jī)排序呢？

隨機(jī)排序方法

• 我們先把問題簡(jiǎn)化一下，如果只隨機(jī)選擇 1 個(gè) word 值，可以怎么做呢？思路上是這樣的：
  • 取得這個(gè)表的主鍵 id 的最大值 M 和最小值 N;
  • 用隨機(jī)函數(shù)生成一個(gè)最大值到最小值之間的數(shù) X = (M-N)*rand() + N;
  • 取不小于 X 的第一個(gè) ID 的行。
  • 我們把這個(gè)算法，暫時(shí)稱作隨機(jī)算法 1。這里，直接給你貼一下執(zhí)行語句的序列:

mysql> select max(id),min(id) into @M,@N from t ;
set @X= floor((@M-@N+1)*rand() + @N);
select * from t where id >= @X limit 1;

• 這個(gè)方法效率很高，因?yàn)槿?max(id) 和 min(id) 都是不需要掃描索引的，而第三步的 select 也可以用索引快速定位，可以認(rèn)為就只掃描了 3 行。但實(shí)際上，這個(gè)算法本身并不嚴(yán)格滿足題目的隨機(jī)要求，因?yàn)?ID 中間可能有空洞，因此選擇不同行的概率不一樣，不是真正的隨機(jī)。
  • 比如你有 4 個(gè) id，分別是 1、2、4、5，如果按照上面的方法，那么取到 id=4 的這一行的概率是取得其他行概率的兩倍。
  • 如果這四行的 id 分別是 1、2、40000、40001 呢？這個(gè)算法基本就能當(dāng) bug 來看待了。
• 所以，為了得到嚴(yán)格隨機(jī)的結(jié)果，你可以用下面這個(gè)流程:
  1. 取得整個(gè)表的行數(shù)，并記為 C。
  2. 取得 Y = floor(C * rand())。 floor 函數(shù)在這里的作用，就是取整數(shù)部分。
  3. 再用 limit Y,1 取得一行。
  • 我們把這個(gè)算法，稱為隨機(jī)算法 2。下面這段代碼，就是上面流程的執(zhí)行語句的序列。

mysql> select count(*) into @C from t;
set @Y = floor(@C * rand());
set @sql = concat("select * from t limit ", @Y, ",1");
prepare stmt from @sql;
execute stmt;
DEALLOCATE prepare stmt;

• 由于 limit 后面的參數(shù)不能直接跟變量，所以我在上面的代碼中使用了 prepare+execute 的方法。你也可以把拼接 SQL 語句的方法寫在應(yīng)用程序中，會(huì)更簡(jiǎn)單些。
  • 這個(gè)隨機(jī)算法 2，解決了算法 1 里面明顯的概率不均勻問題。
  • MySQL 處理 limit Y,1 的做法就是按順序一個(gè)一個(gè)地讀出來，丟掉前 Y 個(gè)，然后把下一個(gè)記錄作為返回結(jié)果，因此這一步需要掃描 Y+1 行。再加上，第一步掃描的 C 行，總共需要掃描 C+Y+1 行，執(zhí)行代價(jià)比隨機(jī)算法 1 的代價(jià)要高。
  • 當(dāng)然，隨機(jī)算法 2 跟直接 order by rand() 比起來，執(zhí)行代價(jià)還是小很多的。
• 現(xiàn)在，我們?cè)倏纯?，如果我們按照隨機(jī)算法 2 的思路，要隨機(jī)取 3 個(gè) word 值呢？你可以這么做：
  1. 取得整個(gè)表的行數(shù)，記為 C；
  2. 根據(jù)相同的隨機(jī)方法得到 Y1、Y2、Y3；
  3. 再執(zhí)行三個(gè) limit Y, 1 語句得到三行數(shù)據(jù)。
  • 我們把這個(gè)算法，稱作隨機(jī)算法 3。下面這段代碼，就是上面流程的執(zhí)行語句的序列。

mysql> select count(*) into @C from t;
set @Y1 = floor(@C * rand());
set @Y2 = floor(@C * rand());
set @Y3 = floor(@C * rand());
select * from t limit @Y1，1； //在應(yīng)用代碼里面取Y1、Y2、Y3值，拼出SQL后執(zhí)行
select * from t limit @Y2，1；
select * from t limit @Y3，1；

小結(jié)

• 如果你直接使用 order by rand()，這個(gè)語句需要 Using temporary 和 Using filesort，查詢的執(zhí)行代價(jià)往往是比較大的。所以，在設(shè)計(jì)的時(shí)候你要盡量避開這種寫法。
• 今天的例子里面，我們不是僅僅在數(shù)據(jù)庫內(nèi)部解決問題，還會(huì)讓應(yīng)用代碼配合拼接 SQL 語句。在實(shí)際應(yīng)用的過程中，比較規(guī)范的用法就是：盡量將業(yè)務(wù)邏輯寫在業(yè)務(wù)代碼中，讓數(shù)據(jù)庫只做“讀寫數(shù)據(jù)”的事情。因此，這類方法的應(yīng)用還是比較廣泛的。