天天看點
傳回

MySQL45講 讀書筆記 17講如何正确地顯示随機消息記憶體臨時表随機排序方法小結

一序

本文屬于極客時間MySQL45講讀書筆記。

今天的主題為了加深對于排序的了解，是MySQL中的另外一種排序需求.

業務場景：有個英語學習App首頁有一個随機顯示單詞的功能，也就是根據每個使用者的級别有一個單詞表，然後這個使用者每次通路首頁的時候，都會随機滾動顯示三個單詞。他們發現随着單詞表變大，選單詞這個邏輯變得越來越慢，甚至影響到了首頁的打開速度。

現在，如果讓你來設計這個SQL語句，你會怎麼寫呢？

為了便于了解，我對這個例子進行了簡化：去掉每個級别的使用者都有一個對應的單詞表這個邏輯，直接就是從一個單詞表中随機選出三個單詞。這個表的建表語句和初始資料的指令如下：

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

為了便于量化說明，我在這個表裡面插入了10000行記錄。接下來，我們就一起看看要随機選擇3個單詞，有什麼方法實作，存在什麼問題以及如何改進。

記憶體臨時表

首先，你會想到用order by rand()來實作這個邏輯。

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

這個語句的意思很直白，随機排序取前3個。雖然這個SQL語句寫法很簡單，但執行流程卻有點複雜的。

我們先用explain指令來看看這個語句的執行情況。

MySQL45講 讀書筆記 17講如何正确地顯示随機消息記憶體臨時表随機排序方法小結

圖1 使用explain指令檢視語句的執行情況

Extra字段顯示Using temporary，表示的是需要使用臨時表；Using filesort，表示的是需要執行排序操作。

是以這個Extra的意思就是，需要臨時表，并且需要在臨時表上排序。可以看上一篇  MySQL45講 讀書筆記 16講“orderby”是怎麼工作的 中全字段排序和rowid排序的内容。

對于InnoDB表來說，執行全字段排序會減少磁盤通路，是以會被優先選擇。對于記憶體表，回表過程隻是簡單地根據資料行的位置，直接通路記憶體得到資料，根本不會導緻多通路磁盤。優化器沒有了這一層顧慮，那麼它會優先考慮的，就是用于排序的行越少越好了，是以，MySQL這時就會選擇rowid排序。

了解了這個算法選擇的邏輯，我們再來看看語句的執行流程。

這條語句的執行流程是這樣的：

  1. 建立一個臨時表。這個臨時表使用的是memory引擎，表裡有兩個字段，第一個字段是double類型，為了後面描述友善，記為字段R，第二個字段是varchar(64)類型，記為字段W。并且，這個表沒有建索引。
  2. 從words表中，按主鍵順序取出所有的word值。對于每一個word值，調用rand()函數生成一個大于0小于1的随機小數，并把這個随機小數和word分别存入臨時表的R和W字段中，到此，掃描行數是10000。
  3. 現在臨時表有10000行資料了，接下來你要在這個沒有索引的記憶體臨時表上，按照字段R排序。
  4. 初始化 sort_buffer。sort_buffer中有兩個字段，一個是double類型，另一個是整型。
  5. 從記憶體臨時表中一行一行地取出R值和位置資訊（我後面會和你解釋這裡為什麼是“位置資訊”），分别存入sort_buffer中的兩個字段裡。這個過程要對記憶體臨時表做全表掃描，此時掃描行數增加10000，變成了20000。
  6. 在sort_buffer中根據R的值進行排序。注意，這個過程沒有涉及到表操作，是以不會增加掃描行數。
  7. 排序完成後，取出前三個結果的位置資訊，依次到記憶體臨時表中取出word值，傳回給用戶端。這個過程中，通路了表的三行資料，總掃描行數變成了20003。

接下來，我們通過慢查詢日志（slow log）來驗證一下我們分析得到的掃描行數是否正确。

# 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就表示這個語句執行過程中掃描了20003行，也就驗證了我們分析得出的結論。

MySQL45講 讀書筆記 17講如何正确地顯示随機消息記憶體臨時表随機排序方法小結

圖4 随機排序完整流程圖1

圖中的pos就是位置資訊，你可能會覺得奇怪，這裡的“位置資訊”是個什麼概念？在上一篇文章中，我們對InnoDB表排序的時候，明明用的還是ID字段。MySQL的表是用什麼方法來定位“一行資料”的。

rowid實際上它表示的是：每個引擎用來唯一辨別資料行的資訊。

  • 對于有主鍵的InnoDB表來說，這個rowid就是主鍵ID；
  • 對于沒有主鍵的InnoDB表來說，這個rowid就是由系統生成的，6位元組長度；
  • MEMORY引擎不是索引組織表。在這個例子裡面，你可以認為它就是一個數組。是以，這個rowid其實就是數組的下标。

到這裡，我來稍微小結一下：order by rand()使用了記憶體臨時表，記憶體臨時表排序的時候使用了rowid排序方法。

磁盤臨時表

  tmp_table_size這個配置限制了記憶體臨時表的大小，預設值是16M。如果臨時表大小超過了tmp_table_size，那麼記憶體臨時表就會轉成磁盤臨時表。磁盤臨時表使用的引擎預設是InnoDB，是由參數internal_tmp_disk_storage_engine控制的。

當使用磁盤臨時表的時候，對應的就是一個沒有顯式索引的InnoDB表的排序過程。為了複現這個過程，我把tmp_table_size設定成1024，把sort_buffer_size設定成 32768, 把 max_length_for_sort_data 設定成16。

set tmp_table_size=1024;
set sort_buffer_size=32768;
set max_length_for_sort_data=16;
/* 打開 optimizer_trace，隻對本線程有效 */
SET optimizer_trace='enabled=on'; 

/* 執行語句 */
select word from words order by rand() limit 3;

/* 檢視 OPTIMIZER_TRACE 輸出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G
MySQL45講 讀書筆記 17講如何正确地顯示随機消息記憶體臨時表随機排序方法小結
MySQL45講 讀書筆記 17講如何正确地顯示随機消息記憶體臨時表随機排序方法小結

  圖5 OPTIMIZER_TRACE部分結果

然後，我們來看一下這次OPTIMIZER_TRACE的結果。

因為将max_length_for_sort_data設定成16，小于word字段的長度定義，是以我們看到sort_mode裡面顯示的是rowid排序，這個是符合預期的，參與排序的是随機值R字段和rowid字段組成的行。

  這個SQL語句的排序确實沒有用到臨時檔案，采用是MySQL 5.6版本引入的一個新的排序算法，即：優先隊列排序算法。接下來，我們就看看為什麼沒有使用臨時檔案的算法，也就是歸并排序算法，而是采用了優先隊列排序算法。

其實，我們現在的SQL語句，隻需要取R值最小的3個rowid。但是，如果使用歸并排序算法的話，雖然最終也能得到前3個值，但是這個算法結束後，已經将10000行資料都排好序了。

也就是說，後面的9997行也是有序的了。但，我們的查詢并不需要這些資料是有序的。是以，想一下就明白了，這浪費了非常多的計算量。

而優先隊列算法，就可以精确地隻得到三個最小值，執行流程如下：

  1. 對于這10000個準備排序的(R,rowid)，先取前三行，構造成一個堆；

（對資料結構印象模糊的同學，可以先設想成這是一個由三個元素組成的數組）

  1. 取下一個行(R’,rowid’)，跟目前堆裡面最大的R比較，如果R’小于R，把這個(R,rowid)從堆中去掉，換成(R’,rowid’)；
  2. 重複第2步，直到第10000個(R’,rowid’)完成比較。
MySQL45講 讀書筆記 17講如何正确地顯示随機消息記憶體臨時表随機排序方法小結

圖6是模拟6個(R,rowid)行，通過優先隊列排序找到最小的三個R值的行的過程。整個排序過程中，為了最快地拿到目前堆的最大值，總是保持最大值在堆頂，是以這是一個最大堆。

圖5的OPTIMIZER_TRACE結果中，filesort_priority_queue_optimization這個部分的chosen=true，就表示使用了優先隊列排序算法，這個過程不需要臨時檔案，是以對應的number_of_tmp_files是0。

這個流程結束後，我們構造的堆裡面，就是這個10000行裡面R值最小的三行。然後，依次把它們的rowid取出來，去臨時表裡面拿到word字段，這個過程就跟上一篇文章的rowid排序的過程一樣了。

我們再看一下上面一篇文章的SQL查詢語句：

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

你可能會問，這裡也用到了limit，為什麼沒用優先隊列排序算法呢？原因是，這條SQL語句是limit 1000，如果使用優先隊列算法的話，需要維護的堆的大小就是1000行的(name,rowid)，超過了我設定的sort_buffer_size大小，是以隻能使用歸并排序算法。

總之，不論是使用哪種類型的臨時表，order by rand()這種寫法都會讓計算過程非常複雜，需要大量的掃描行數，是以排序過程的資源消耗也會很大。

再回到我們文章開頭的問題，怎麼正确地随機排序呢？

随機排序方法

我們先把問題簡化一下，如果隻随機選擇1個word值，可以怎麼做呢？思路上是這樣的：

  1. 取得這個表的主鍵id的最大值M和最小值N;
  2. 用随機函數生成一個最大值到最小值之間的數 X = (M-N)*rand() + N;
  3. 取不小于X的第一個ID的行。

我們把這個算法，暫時稱作随機算法1。這裡，我直接給你貼一下執行語句的序列:

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

這個方法效率很高，因為取max(id)和min(id)都是不需要掃描索引的，而第三步的select也可以用索引快速定位，可以認為就隻掃描了3行。但實際上，這個算法本身并不嚴格滿足題目的随機要求，因為ID中間可能有空洞，是以選擇不同行的機率不一樣，不是真正的随機。

比如你有4個id，分别是1、2、4、5，如果按照上面的方法，那麼取到 id=4的這一行的機率是取得其他行機率的兩倍。

如果這四行的id分别是1、2、40000、40001呢？這個算法基本就能當bug來看待了。

是以，為了得到嚴格随機的結果，你可以用下面這個流程:

  1. 取得整個表的行數，并記為C。
  2. 取得 Y = floor(C * rand())。 floor函數在這裡的作用，就是取整數部分。
  3. 再用limit Y,1 取得一行。

我們把這個算法，稱為随機算法2。下面這段代碼，就是上面流程的執行語句的序列。

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 後面的參數不能直接跟變量，是以我在上面的代碼中使用了prepare+execute的方法。你也可以把拼接SQL語句的方法寫在應用程式中，會更簡單些。

這個随機算法2，解決了算法1裡面明顯的機率不均勻問題。

MySQL處理limit Y,1 的做法就是按順序一個一個地讀出來，丢掉前Y個，然後把下一個記錄作為傳回結果，是以這一步需要掃描Y+1行。再加上，第一步掃描的C行，總共需要掃描C+Y+1行，執行代價比随機算法1的代價要高。

當然，随機算法2跟直接order by rand()比起來，執行代價還是小很多的。

你可能問了，如果按照這個表有10000行來計算的話，C=10000，要是随機到比較大的Y值，那掃描行數也跟20000差不多了，接近order by rand()的掃描行數，為什麼說随機算法2的代價要小很多呢？我就把這個問題留給你去課後思考吧。

現在，我們再看看，如果我們按照随機算法2的思路，要随機取3個word值呢？你可以這麼做：

  1. 取得整個表的行數，記為C；
  2. 根據相同的随機方法得到Y1、Y2、Y3；
  3. 再執行三個limit Y, 1語句得到三行資料。

我們把這個算法，稱作随機算法3。下面這段代碼，就是上面流程的執行語句的序列。

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； //在應用代碼裡面取Y1、Y2、Y3值，拼出SQL後執行
select * from t limit @Y2，1；
select * from t limit @Y3，1；

小結

今天這篇文章，我是借着随機排序的需求，跟你介紹了MySQL對臨時表排序的執行過程。

如果你直接使用order by rand()，這個語句需要Using temporary 和 Using filesort，查詢的執行代價往往是比較大的。是以，在設計的時候你要量避開這種寫法。

   好了，這篇文章裡面，我覺得了解Using temporary 和 Using filesort 代價大，盡量避免就好了，至于使用sql來解決，真心覺得不太适合，就是業務層應該做的事，不要交給MySQL來做，它不太适合。結合業務來看，詞典資料量假設10W級詞彙。就算一個單詞20位元組，那就是2M方記憶體更好使。或者使用Redis，就算随機也是外面業務系統算出ID的範圍，直接根據主鍵查詢。

還有就是不要使用order by rand() 排序了。子查詢不一定會需要臨時表，你要看explain的結果哈，如果需要臨時表，還要再看臨時表大小，小的用memory引擎，大的用innodb。

mysql 随機 rand 臨時表
上一篇: C/C++怎樣産生随機數
下一篇: C++學習筆記之rand函數用法

繼續閱讀