单词表 目的:随机选择3个单词
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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();
查询语句 1 SELECT word FROM words ORDER BY RAND() LIMIT 3 ;
内存临时表 explain 1 2 3 4 5 6 7 8 9 10 11 12 13 14 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
Using temporary;
:表示需要使用到临时表
如果采用的是内存临时表 ,存储引擎可以选择TempTable (默认)或MEMORY
如果采用的是磁盘临时表 ,存储引擎可以选择InnoDB (默认)或MyISAM
Using filesort
:表示需要执行排序 操作
综合起来:需要在临时表上排序 ,该操作往往执行代价比较大 ,尽量避免
1 2 3 4 5 6 7 8 9 10 11 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 | +
排序算法
对于磁盘临时表 而言,会优先选择全字段排序 ,因为可以减少磁盘访问
对于内存临时表 而言,会优先选择rowid排序 ,因为不需要磁盘操作,回表的开销很低
rowid
每个存储引擎用来唯一标识一行数据的字段
InnoDB
InnoDB采用的是索引组织表,必然有“主键”(显式声明或隐式自动生成)
如有有显式 声明主键 或唯一主键 ,rowid就是主键 (主键优先)或唯一主键
如果没有显式 声明主键 和唯一主键 ,rowid是由系统自动生成 (6 Bytes)的
MEMORY
MEMORY采用的不是索引组织表 ,可以简单理解为一个数组 ,rowid就是数组的下标
下面执行过程中讲到的位置信息 (pos ),其实就是MEMORY引擎的rowid (数组下标 ),即rowid = pos
tmp_table_size
当临时表需要的空间小于 tmp_table_size
(默认16MB),临时表将采用内存临时表
内存临时表存放两个字段:R(8 Bytes)和W(64*3 Bytes,按UTF8最大占用空间计算)
最大占用空间:(8+64*3)*10000=2,000,000 < 16,777,216
,因此可以采用内存临时表
1 2 3 4 5 6 7 8 mysql> SHOW VARIABLES LIKE '%tmp_table_size%' ; + | Variable_name | Value | + | tmp_table_size | 16777216 | +
sort_buffer_size 1 2 3 4 5 6 7 mysql> SHOW VARIABLES LIKE 'sort_buffer_size' ; + | Variable_name | Value | + | sort_buffer_size | 262144 | +
对于使用内存临时表 而言,由于回表开销很低 (都在内存 中),优先选择rowid排序
而对sort buffer
按R进行排序时,在空间充足的情况下,会优先现在优先级队列排序 (MySQL 5.6引入)
262144 / size(R)+size(pos) = 262144/14 = 18724 > 3
,因此会选择优先级队列排序
执行过程
创建一个采用MEMORY 引擎的内存临时表 (_数组 , 没有索引 _),表内有两个字段:R 和W
R:double类型 ,用于存放随机小数
W:VARCHAR(64)类型 ,用于存放原表的word字段
从原表 中,按主键顺序 依次取出所有的word值
对于每一个word值,调用rand()
函数生成一个(0,1)
之间的随机小数
将生成的随机小数和word值分别存入内存临时表的R和W字段
此时,行扫描行数为10000
内存临时表已经有10000行数据,下面需要在没有索引的内存临时表 上,按照字段R排序
后续操作就没有原表什么事情了,内存临时表相当于下一阶段的原表
初始化sort buffer
,确定放入两个字段:一个是double 类型的R字段,一个是整型类型 的pos
R:用于存放内存临时表的R字段
pos:用于存放内存临时表的rowid字段
类似于rowid排序 ,但实际可能会优化为优先级队列排序
从内存临时表 中一行一行地取出R 和pos ,分别存入sort buffer
的两个字段
在sort buffer
中根据字段R排序 (如果优化为优先级队列排序 ,跳过)
排序完成后,取出前3个结果的pos ,依据pos依次到内存临时表 中取出word值,返回客户端
观察指标 慢查询日志 Rows_examined
为20003,与上面分析结论一致
1 2 3 4 5 # Time : 2019 -02 -11 T09:27 :42.472723 Z # 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 "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>" }
filesort_priority_queue_optimization.chosen=true
和unpacked_addon_fields=using_priority_queue
peak_memory_used < memory_available
和num_initial_chunks_spilled_to_disk=0
表示排序过程中没有使用磁盘临时文件 ,完全在sort buffer
中进行,峰值内存才为128 Bytes
num_examined_rows
:参与排序的有10000行,这些行需要从内存临时表 中读取,扫描行数+10000
sort_mode
中有rowid
关键字:表示采用的是rowid排序
优先级队列排序
需要取回R值最小 的3个rowid,如果使用归并排序 ,结束后,10000行数据都是有序的,这样会浪费 很多计算量
而采用优先级队列排序,可以精确 地只得到3个最小的值
构建最大堆
在内存临时表中,有10000个准备参与排序的行,一行为(R,rowid)
,先取前3行放入sort buffer
,构造成一个堆
取下一行(R',rowid')
,与当前堆中最大的R
比较
如果R'
小于R
,则把这个(R,rowid)
从堆中去掉,替换成(R',rowid')
重复上述步骤,直到第10000行比较完成
回表返回
构造最大堆 (在sort buffer
中)完成后,堆里面存放的是10000行中R值最小 的3行
依次取出对应的rowid,然后回表 (内存临时表)取出word字段,返回给客户端
磁盘临时表 当临时表需要的空间大于 tmp_table_size
(默认16MB),内存临时表就会转成磁盘临时表 (默认InnoDB存储引擎)
优先级队列排序 执行过程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 SET tmp_table_size= 1024 ;SET sort_buffer_size= 32768 ;SET optimizer_trace= 'enabled=on' ;SELECT word FROM words ORDER BY RAND() LIMIT 3 ;SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G
观察指标 慢查询日志 1 2 3 4 5 # Time : 2019 -02 -11 T10:32 :49.301884 Z # 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 "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>" }
临时表需要占用的最小空间:(8+4*1)*10000=120,000 > 32,768=tmp_table_size
,因此采用的是磁盘临时表
采用磁盘临时表 ,那就必须考虑回表开销 了,优先选择全字段排序
磁盘临时表包含三个字段:rowid(6 Bytes) 、R(8 Bytes) 、word(4*1~64*3 Bytes)
单行最大长度为6+8+64*3=206 < 4096=max_length_for_sort_data
,依然采用全字段排序
sort_mode
中有additional_fields
关键字:表示采用的是全字段排序
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
归并排序 执行过程 1 SELECT word FROM words ORDER BY RAND() LIMIT 3000 ;
慢查询日志 1 2 3 4 5 # Time : 2019 -02 -11 T11:07 :01.812796 Z # 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 "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>" }
sort_mode
中含有packed_additional_fields
关键字
采用全字段排序 ,并且对字段有做紧凑 处理(word为VARCHAR类型)
佐证:filesort_priority_queue_optimization.strip_additional_fields
filesort_priority_queue_optimization..chosen=false
row_size=22
,而sort_buffer_size / row_size = 32768/22 = 1489 < 3000
因此sort buffer
不足以满足采用优先级队列排序 ,降级为归并排序 (外部排序)
佐证:cause=not_enough_space
和num_initial_chunks_spilled_to_disk=8
随机排序
无论采用内存临时表 还是磁盘临时表 ,order by rand
都会让计算过程很复杂 ,需要扫描大量行 ,资源消耗严重
解决思路:数据库只负责读写数据 (职责尽量单一 ),随机排序的逻辑交由业务层 实现
随机算法1 简化问题:随机选择1个word
1 2 3 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 ;
MAX和MIN都不需要将索引遍历一遍 ,效率很高
第3步可以利用索引 快速定位
但算法本身并非严格随机 ,因为ID中间可能存在空洞 ,因此选择不同行的概率是不一样的
随机算法2 1 2 3 4 5 6 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;
优点:严格随机
LIMIT Y,1
:按顺序一个个读出,丢掉前面Y个,然后把第Y+1 个记录返回,因此该过程需要扫描Y+1行
整个过程的扫描行数:C+Y+1
执行代价比随机算法1要高
但相对于order by rand
,执行代价还是很小的
因为随机算法2是直接根据主键 排序获取的
而order by rand
很繁琐:生成临时表 ,按R字段排序 ,获取rowid后回查临时表 (如果是rowid排序)
随机算法3 恢复到取3个word,整个过程的扫描行数:C+(Y1+1)+(Y2+1)+(Y3+1)
1 2 3 4 5 6 7 8 SELECT COUNT (* ) INTO @C FROM words;SET @Y1 = FLOOR (@C * RAND());SET @Y2 = FLOOR (@C * RAND());SET @Y3 = FLOOR (@C * RAND());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
1 2 3 4 5 6 7 8 9 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 ;SELECT * FROM words WHERE id IN (ID1,ID2,ID3);
参考资料 《MySQL实战45讲》