17 | 如何正確地顯示隨機訊息？

場景：從一個單詞表中隨機選出三個單詞，

表的建表陳述句和初始資料的命令如下，在這個表里面插入了 10000 行記錄：

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

記憶體臨時表

用 order by rand() 來實作這個邏輯，隨機排序取前 3 個，

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

雖然這個 SQL 陳述句寫法很簡單，但執行流程卻有點復雜的，

使用 explain 命令查看陳述句的執行情況

Extra 欄位顯示 Using temporary，表示的是需要使用臨時表；Using filesort，表示的是需要執行排序操作，因此這個 Extra 的意思就是，需要臨時表，并且需要在臨時表上排序，

Q：對于臨時記憶體表的排序來說，它會選擇全欄位排序演算法還是rowid演算法？

A：回顧一下上一篇文章的一個結論：對于 InnoDB 表來說，執行全欄位排序會減少磁盤訪問，因此會被優先選擇，

對于記憶體表，回表程序只是簡單地根據資料行的位置，直接訪問記憶體得到資料，根本不會導致多訪問磁盤，優化器沒有了這一層顧慮，那么它會優先考慮的，就是用于排序的行越小越好了，所以，MySQL 這時就會選擇 rowid 排序，

這條陳述句的執行流程是這樣的：

創建一個臨時表，這個臨時表使用的是 memory 引擎，表里有兩個欄位，第一個欄位是 double 型別，為了后面描述方便，記為欄位 R，第二個欄位是 varchar(64) 型別，記為欄位 W，并且，這個表沒有建索引，
從 words 表中，按主鍵順序取出所有的 word 值，對于每一個 word 值，呼叫 rand() 函式生成一個大于 0 小于 1 的隨機小數，并把這個隨機小數和 word 分別存入臨時表的 R 和 W 欄位中，到此，掃描行數是 10000，
現在臨時表有 10000 行資料了，接下來要在這個沒有索引的記憶體臨時表上，按照欄位 R 排序，
初始化 sort_buffer，sort_buffer 中有兩個欄位，一個是 double 型別，另一個是整型，
從記憶體臨時表中一行一行地取出 R 值和位置資訊，分別存入 sort_buffer 中的兩個欄位里，這個程序要對記憶體臨時表做全表掃描，此時掃描行數增加 10000，變成了 20000，
在 sort_buffer 中根據 R 的值進行排序，注意，這個程序沒有涉及到表操作，所以不會增加掃描行數，
排序完成后，取出前三個結果的位置資訊，依次到記憶體臨時表中取出 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;

完整的排序執行流程圖

MySQL 的表是用什么方法來定位“一行資料”

如果把一個 InnoDB 表的主鍵刪掉，是不是就沒有主鍵，就沒辦法回表了？

其實不是的，如果你創建的表沒有主鍵，或者把一個表的主鍵刪掉了，那么 InnoDB 會自己生成一個長度為 6 位元組的 rowid 來作為主鍵

如果你創建的表沒有主鍵，或者把一個表的主鍵刪掉了，那么 InnoDB 會自己生成一個長度為 6 位元組的 rowid 來作為主鍵，

這也就是排序模式里面，rowid 名字的來歷，實際上它表示的是：每個引擎用來唯一標識資料行的資訊，

對于有主鍵的 InnoDB 表來說，這個 rowid 就是主鍵 ID（上一節的ID）；
對于沒有主鍵的 InnoDB 表來說，這個 rowid 就是由系統生成的；
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=https://www.cnblogs.com/ydssx7/p/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

OPTIMIZER_TRACE 的結果如下：

因為將 max_length_for_sort_data 設定成 16，小于 word 欄位的長度定義，所以我們看到 sort_mode 里面顯示的是 rowid 排序，這個是符合預期的，參與排序的是隨機值 R 欄位和 rowid 欄位組成的行，

Q：R 欄位存放的隨機值就 8 個位元組，rowid 是 6 個位元組，資料總行數是 10000，這樣算出來就有 140000 位元組，超過了 sort_buffer_size 定義的 32768 位元組了，但是，number_of_tmp_files 的值居然是 0，難道不需要用臨時檔案嗎？

A：這個 SQL 陳述句的排序確實沒有用到臨時檔案，采用是 MySQL 5.6 版本引入的一個新的排序演算法，即：優先佇列排序演算法

優先佇列排序演算法

現在的 SQL 陳述句，只需要取 R 值最小的 3 個 rowid，但是，如果使用歸并排序演算法的話，雖然最終也能得到前 3 個值，但是這個演算法結束后，已經將 10000 行資料都排好序了，也就是說，后面的 9997 行也是有序的了，但查詢并不需要這些資料是有序的，這浪費了非常多的計算量，

優先佇列演算法，就可以精確地只得到三個最小值，執行流程如下：

對于這 10000 個準備排序的 (R,rowid)，先取前三行，構造成一個堆；（可以設想成這是一個由三個元素組成的陣列）
取下一個行 (R’,rowid’)，跟當前堆里面最大的 R 比較，如果 R’小于 R，把這個 (R,rowid) 從堆中去掉，換成 (R’,rowid’)；
重復第 2 步，直到第 10000 個 (R’,rowid’) 完成比較，

優先佇列排序程序的示意圖如下，模擬 6 個 (R,rowid) 行，通過優先佇列排序找到最小的三個 R 值的行的程序，整個排序程序中，為了最快地拿到當前堆的最大值，總是保持最大值在堆頂，因此這是一個最大堆，

上面的OPTIMIZER_TRACE 結果中，filesort_priority_queue_optimization 這個部分的 chosen=true，就表示使用了優先佇列排序演算法，這個程序不需要臨時檔案，因此對應的 number_of_tmp_files 是 0，

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

Q：上一篇也用了limit，為什么沒有用優先佇列排序演算法？

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

A：

這條 SQL 陳述句是 limit 1000，如果使用優先佇列演算法的話，需要維護的堆的大小就是 1000 行的 (name,rowid)，超過了設定的 sort_buffer_size 大小，所以只能使用歸并排序演算法，

tmp_table_size 管是記憶體臨時表還是磁盤臨時表

sort_buffer_size 管歸并還是其他

max_length_for_sort_data 控制是否是全欄位

小結：

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

隨機排序方法

盡量將業務邏輯寫在業務代碼中，讓資料庫只做“讀寫資料”的事情

簡化問題，如果只隨機選擇 1 個 word 值，可以怎么做：

方法一：

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

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;

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

比如你有 4 個 id，分別是 1、2、4、5，如果按照上面的方法，那么取到 id=4 的這一行的概率是取得其他行概率的兩倍，如果這四行的 id 分別是 1、2、40000、40001 ，這個演算法 bug 了，

方法二：

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

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

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;

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

按照隨機演算法 2 的思路，要隨機取 3 個 word 值

取得整個表的行數，記為 C；
根據相同的隨機方法得到 Y1、Y2、Y3；
再執行三個 limit Y, 1 陳述句得到三行資料，

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；

總掃描行數是 C+(Y1+1)+(Y2+1)+(Y3+1)

Q：怎么做來減少掃描行數呢？說說你的方案，并說明你的方案需要的掃描行數，

A：

讓表里面保存一個無空洞的自增值，這樣就可以用演算法 1 來實作

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/500326.html

標籤：MySQL

上一篇：MySQL實戰45講 16

下一篇：【萬字長文】使用 LSM-Tree 思想基于.Net 6.0 C# 實作 KV 資料庫（案例版）

MySQL實戰45講 17