MySQL -- order by rand

目的:隨機選擇3個單詞

CREATE TABLE `words` (
  `id` INT(11) NOT NULL AUTO_INCREMENT,
  `word` VARCHAR(64) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

DELIMITER ;;
CREATE PROCEDURE wdata()
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 wdata();

查詢語句

SELECT word FROM words ORDER BY RAND() LIMIT 3;

內存臨時表

explain

mysql> EXPLAIN SELECT word FROM words ORDER BY RAND() LIMIT 3\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: words
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 9980
     filtered: 100.00
        Extra: Using temporary; Using filesort
  1. Using temporary; :表示需要使用到 臨時表
    • 如果採用的是 內存臨時表 ,存儲引擎可以選擇 TempTable (默認)或 MEMORY
    • 如果採用的是 磁盤臨時表 ,存儲引擎可以選擇 InnoDB (默認)或 MyISAM
  2. Using filesort :表示需要執行 排序 操作
  3. 綜合起來:需要 在臨時表上排序 ,該操作往往 執行代價比較大 ,儘量避免
-- internal_tmp_mem_storage_engine introduced 8.0.2
mysql> SHOW VARIABLES LIKE '%storage_engine%';
+----------------------------------+--------+
| Variable_name                    | Value  |
+----------------------------------+--------+
| default_storage_engine           | InnoDB |
| default_tmp_storage_engine       | InnoDB |
| disabled_storage_engines         |        |
| internal_tmp_disk_storage_engine | InnoDB |
| internal_tmp_mem_storage_engine  | MEMORY |
+----------------------------------+--------+

排序算法

  1. 對於 磁盤臨時表 而言,會優先選擇 全字段排序 ,因為可以 減少磁盤訪問
  2. 對於 內存臨時表 而言,會優先選擇 rowid排序 ,因為不需要磁盤操作, 回表的開銷很低

rowid

  1. 每個存儲引擎用來 唯一標識一行數據的字段
  2. InnoDB
    • InnoDB採用的是索引組織表,必然有“主鍵”(顯式聲明或隱式自動生成)
    • 如有 有顯式 聲明 主鍵唯一主鍵 ,rowid就是 主鍵 (主鍵優先)或 唯一主鍵
    • 如果 沒有顯式 聲明 主鍵唯一主鍵 ,rowid是由 系統自動生成 (6 Bytes)的
  3. MEMORY
    • MEMORY採用的不是 索引組織表 ,可以簡單理解為一個 數組 ,rowid就是 數組的下標
    • 下面執行過程中講到的 位置信息pos ),其實就是 MEMORY引擎的rowid數組下標 ),即 rowid = pos

tmp_table_size

  1. 當臨時表需要的空間 小於 tmp_table_size (默認16MB),臨時表將採用內存臨時表
  2. 內存臨時表存放兩個字段:R( 8 Bytes)和W( 64*3 Bytes,按UTF8最大佔用空間計算)
  3. 最大佔用空間: (8+64*3)*10000=2,000,000 < 16,777,216 ,因此可以採用 內存臨時表
-- 16777216 Bytes = 16 MB
-- 線上配置為128 MB
mysql> SHOW VARIABLES LIKE '%tmp_table_size%';
+----------------+----------+
| Variable_name  | Value    |
+----------------+----------+
| tmp_table_size | 16777216 |
+----------------+----------+

sort_buffer_size

-- 262144 Bytes = 256 KB
mysql> SHOW VARIABLES LIKE 'sort_buffer_size';
+------------------+--------+
| Variable_name    | Value  |
+------------------+--------+
| sort_buffer_size | 262144 |
+------------------+--------+
  1. 對於使用 內存臨時表 而言,由於 回表開銷很低 (都在 內存 中),優先選擇 rowid排序
  2. 而對 sort buffer 按R進行排序時,在空間充足的情況下,會優先現在 優先級隊列排序 (MySQL 5.6引入)
  3. 262144 / size(R)+size(pos) = 262144/14 = 18724 > 3 ,因此會選擇 優先級隊列排序

執行過程

MySQL -- order by rand
MySQL -- order by rand
  1. 創建一個採用 MEMORY 引擎的 內存臨時表 數組 沒有索引 ),表內有兩個字段: RW
    • R: double類型 ,用於存放 隨機小數
    • W: VARCHAR(64)類型 ,用於存放 原表的word字段
  2. 原表 中,按 主鍵順序 依次取出 所有的word值
    • 對於每一個word值,調用 rand() 函數生成一個 (0,1) 之間的 隨機小數
    • 將生成的隨機小數和word值分別存入內存臨時表的R和W字段
    • 此時,行掃描行數為10000
  3. 內存臨時表已經有10000行數據,下面需要在 沒有索引的內存臨時表 上, 按照字段R排序
    • 後續操作就沒有原表什麼事情了, 內存臨時表相當於下一階段的原表
  4. 初始化 sort buffer ,確定放入兩個字段:一個是 double 類型的R字段,一個是 整型類型 的pos
    • R:用於存放 內存臨時表的R字段
    • pos:用於存放 內存臨時表的rowid字段
    • 類似於 rowid排序 ,但實際可能會優化為 優先級隊列排序
  5. 內存臨時表 中一行一行地取出 Rpos ,分別存入 sort buffer 的兩個字段
    • 此時,行掃描行數為20000
  6. sort buffer 中根據字段 R排序 (如果優化為 優先級隊列排序 ,跳過)
    • 該過程 不涉及表操作不會增加掃描行數
  7. 排序完成後,取出前3個結果的 pos ,依據pos依次到 內存臨時表 中取出word值,返回客户端
    • 此時,行掃描行數為 20003

觀察指標

慢查詢日誌

Rows_examined 為20003,與上面分析結論一致

# Time: 2019-02-11T09:27:42.472723Z
# User@Host: root[root] @ localhost []  Id:    13
# Query_time: 0.007515  Lock_time: 0.000179 Rows_sent: 3  Rows_examined: 20003
SET timestamp=1549877262;
SELECT word FROM words ORDER BY RAND() LIMIT 3;

OPTIMIZER_TRACE

"filesort_information": [
    {
        "direction": "asc",
        "table": "intermediate_tmp_table",
        "field": "tmp_field_0"
    }
],
"filesort_priority_queue_optimization": {
    "limit": 3,
    "chosen": true
},
...
"filesort_summary": {
    "memory_available": 262144,
    "key_size": 24,
    "row_size": 24,
    "max_rows_per_buffer": 4,
    "num_rows_estimate": 10010,
    "num_rows_found": 4,
    "num_examined_rows": 10000,
    "num_initial_chunks_spilled_to_disk": 0,
    "peak_memory_used": 128,
    "sort_algorithm": "std::sort",
    "unpacked_addon_fields": "using_priority_queue",
    "sort_mode": "<fixed_sort_key, rowid>"
}
  1. filesort_priority_queue_optimization.chosen=trueunpacked_addon_fields=using_priority_queue
    • 表示使用了 優先級隊列排序
  2. peak_memory_used < memory_availablenum_initial_chunks_spilled_to_disk=0
    • 表示排序過程中沒有使用 磁盤臨時文檔 ,完全在 sort buffer 中進行,峯值內存才為 128 Bytes
  3. num_examined_rows :參與排序的有10000行,這些行需要從 內存臨時表 中讀取,掃描行數+10000
  4. sort_mode 中有 rowid 關鍵字:表示採用的是 rowid排序

優先級隊列排序

  1. 需要取回R值 最小 的3個rowid,如果使用 歸併排序 ,結束後,10000行數據都是有序的,這樣會 浪費 很多計算量
  2. 而採用優先級隊列排序,可以 精確 地只得到3個最小的值

構建最大堆

MySQL -- order by rand
MySQL -- order by rand
  1. 在內存臨時表中,有10000個準備參與排序的行,一行為 (R,rowid) ,先取前3行放入 sort buffer ,構造成一個
  2. 取下一行 (R',rowid') ,與當前堆中最大的 R 比較
    • 如果 R' 小於 R ,則把這個 (R,rowid) 從堆中去掉,替換成 (R',rowid')
  3. 重複上述步驟,直到第10000行比較完成

回表返回

  1. 構造 最大堆 (在 sort buffer 中)完成後,堆裏面存放的是10000行中R值 最小 的3行
  2. 依次取出對應的rowid,然後 回表 (內存臨時表)取出word字段,返回給客户端

磁盤臨時表

當臨時表需要的空間 大於 tmp_table_size (默認16MB),內存臨時表就會轉成 磁盤臨時表 (默認InnoDB存儲引擎)

優先級隊列排序

執行過程

-- 構造使用磁盤臨時表的場景,最小為1024
SET tmp_table_size=1024;

-- 構造使用磁盤臨時文檔的場景,最小為32768
-- 如果內存空間不能滿足優先級隊列排序,會降級為歸併排序(需要使用磁盤臨時文檔)
SET sort_buffer_size=32768;

-- 打開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

觀察指標

慢查詢日誌

# Time: 2019-02-11T10:32:49.301884Z
# User@Host: root[root] @ localhost []  Id:    13
# Query_time: 0.013087  Lock_time: 0.000124 Rows_sent: 3  Rows_examined: 20003
SET timestamp=1549881169;
SELECT word FROM words ORDER BY RAND() LIMIT 3;

OPTIMIZER_TRACE

"filesort_information": [
    {
        "direction": "asc",
        "table": "intermediate_tmp_table",
        "field": "tmp_field_0"
    }
],
"filesort_priority_queue_optimization": {
    "limit": 3,
    "chosen": true
},
...
"filesort_summary": {
    "memory_available": 32768,
    "key_size": 8,
    "row_size": 210,
    "max_rows_per_buffer": 4,
    "num_rows_estimate": 1170,
    "num_rows_found": 4,
    "num_examined_rows": 10000,
    "num_initial_chunks_spilled_to_disk": 0,
    "peak_memory_used": 872,
    "sort_algorithm": "std::sort",
    "unpacked_addon_fields": "using_priority_queue",
    "sort_mode": "<fixed_sort_key, additional_fields>"
}
  1. 臨時表需要佔用的最小空間: (8+4*1)*10000=120,000 > 32,768=tmp_table_size ,因此採用的是 磁盤臨時表
  2. 採用 磁盤臨時表 ,那就必須考慮 回表開銷 了,優先選擇 全字段排序
  3. 磁盤臨時表包含三個字段: rowid(6 Bytes)R(8 Bytes)word(4*1~64*3 Bytes)
    • 單行最大長度為 6+8+64*3=206 < 4096=max_length_for_sort_data ,依然採用 全字段排序
  4. sort_mode 中有 additional_fields 關鍵字:表示採用的是 全字段排序
  5. sort_buffer_size / row_max_size = 32768/206 = 159 > 3 ,因此可以選擇 優先級隊列排序 ,佐證如下:
    peak_memory_used=872 < memory_available
    filesort_priority_queue_optimization.chosen=true
    unpacked_addon_fields=using_priority_queue
    num_initial_chunks_spilled_to_disk=0
    

歸併排序

執行過程

SELECT word FROM words ORDER BY RAND() LIMIT 3000;

慢查詢日誌

# Time: 2019-02-11T11:07:01.812796Z
# User@Host: root[root] @ localhost []  Id:    13
# Query_time: 0.018456  Lock_time: 0.000113 Rows_sent: 3000  Rows_examined: 23000
SET timestamp=1549883221;
SELECT word FROM words ORDER BY RAND() LIMIT 3000;

OPTIMIZER_TRACE

"filesort_information": [
    {
        "direction": "asc",
        "table": "intermediate_tmp_table",
        "field": "tmp_field_0"
    }
],
"filesort_priority_queue_optimization": {
    "limit": 3000,
    "strip_additional_fields": {
        "row_size": 22,
        "chosen": false,
        "cause": "not_enough_space"
    }
},
...
"filesort_summary": {
    "memory_available": 32768,
    "key_size": 8,
    "row_size": 212,
    "max_rows_per_buffer": 154,
    "num_rows_estimate": 1170,
    "num_rows_found": 10000,
    "num_examined_rows": 10000,
    "num_initial_chunks_spilled_to_disk": 8,
    "peak_memory_used": 47968,
    "sort_algorithm": "std::stable_sort",
    "sort_mode": "<fixed_sort_key, packed_additional_fields>"
}
  1. sort_mode 中含有 packed_additional_fields 關鍵字
    • 採用 全字段排序 ,並且對字段有做 緊湊 處理(word為VARCHAR類型)
    • 佐證: filesort_priority_queue_optimization.strip_additional_fields
  2. filesort_priority_queue_optimization..chosen=false
    • row_size=22 ,而 sort_buffer_size / row_size = 32768/22 = 1489 < 3000
    • 因此 sort buffer 不足以滿足採用 優先級隊列排序 ,降級為 歸併排序 (外部排序)
    • 佐證: cause=not_enough_spacenum_initial_chunks_spilled_to_disk=8

隨機排序

  1. 無論採用 內存臨時表 還是 磁盤臨時表order by rand 都會讓 計算過程很複雜 ,需要 掃描大量行資源消耗嚴重
  2. 解決思路: 數據庫只負責讀寫數據職責儘量單一 ),隨機排序的邏輯交由 業務層 實現

隨機算法1

簡化問題:隨機選擇1個word

SELECT MAX(id),MIN(id) INTO @M,@N FROM words;
SET @X=FLOOR(@N+(@M-@N+1)*RAND());
SELECT * FROM words WHERE id >= @X LIMIT 1;
  1. MAX和MIN都 不需要將索引遍歷一遍效率很高
  2. 第3步可以利用 索引 快速定位
  3. 但算法本身並 非嚴格隨機 ,因為ID中間可能存在 空洞 ,因此選擇不同行的概率是不一樣的

隨機算法2

SELECT COUNT(*) INTO @C FROM words;
SET @Y = FLOOR(@C*RAND());
SET @sql = CONCAT("SELECT * FROM words LIMIT ", @Y, ",1");
PREPARE stmt from @sql;
EXECUTE stmt;
DEALLOCATE PREPARE stmt;
  1. 優點: 嚴格隨機
  2. LIMIT Y,1 :按順序一個個讀出,丟掉前面Y個,然後把第 Y+1 個記錄返回,因此該過程需要掃描Y+1行
  3. 整個過程的掃描行數: C+Y+1
    • 執行代價比隨機算法1要高
    • 但相對於 order by rand ,執行代價還是很小的
      • 因為隨機算法2是 直接根據主鍵 排序獲取的
      • order by rand 很繁瑣: 生成臨時表按R字段排序獲取rowid後回查臨時表 (如果是rowid排序)

隨機算法3

恢復到取3個word,整個過程的掃描行數: C+(Y1+1)+(Y2+1)+(Y3+1)

SELECT COUNT(*) INTO @C FROM words;
SET @Y1 = FLOOR(@C * RAND());
SET @Y2 = FLOOR(@C * RAND());
SET @Y3 = FLOOR(@C * RAND());
-- 在應用代碼裏面取Y1、Y2、Y3,拼出SQL後執行
SELECT * FROM words LIMIT @Y1,1;
SELECT * FROM words LIMIT @Y2,1;
SELECT * FROM words LIMIT @Y3,1;

隨機算法4

整個過程的掃描行數: C+MAX(Y1,Y2,Y3)+1+3

SELECT COUNT(*) INTO @C FROM words;
SET @Y1 = FLOOR(@C * RAND());
SET @Y2 = FLOOR(@C * RAND());
SET @Y3 = FLOOR(@C * RAND());
SET @M = MAX(@Y1,@Y2,@Y3);
SET @N = MIN(@Y1,@Y2,@Y3);
SELECT id FROM words LIMIT N,M-N+1;
-- 業務代碼隨機選擇ID1、ID2、ID3
SELECT * FROM words WHERE id IN (ID1,ID2,ID3);

參考資料

《MySQL實戰45講》

轉載請註明出處:http://zhongmingmao.me/2019/02/10/mysql-order-by-rand/

訪問原文「 MySQL -- order by rand 」獲取最佳閲讀體驗並參與討論