《MySQL实战45讲》——学习笔记17 “随机排序、内存临时表“

本篇主要通过在一个排序场景下，使用到临时表的业务场景示例，介绍在MYSQL排序时用到的内存临时表/磁盘临时表的相关知识；还包括一个特殊的场景，即参与排序的数据超过了sort_buffer_size 但MySQL却未使用临时文件（归并排序算法）的情况，这是因为MySQL5.6版本引入了一个新的排序算法，即：优先队列排序算法（堆排序）；

对于本文引用的业务场景例子——随机排序后取TopN，实际上不适合使用MySQL来解决业务问题，因为会消耗MYSQL宝贵的IO和CPU资源；业界一般是配合缓存，放在服务器内存（JVM）中计算；本文仅仅是刚好用这个例子来方便介绍相关知识点；

业务场景示例

场景说明：某个英语学习App首页有一个随机显示单词的功能，用户每次访问首页的时候，都会随机滚动显示三个单词；为了便于理解，对这个例子进行了简化：从一个单词表中随机选出三个单词；

这个表的建表语句和初始数据的命令如下，表数据初始化后里面有10000条记录：

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

问题：发现随着单词表变大，选单词这个逻辑变得越来越慢，甚至影响到了首页的打开速度；
 

内存临时表

方案：通过MySQL内置函数 rand() ，对每一条记录计算一个random值，对改值排序取前3个记录；

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

虽然这个SQL语句写法很简单，但执行流程却有点复杂，先用explain命令来看看这个语句的执行情况；

Extra字段显示 Using temporary，表示的是需要使用临时表；Using filesort，表示的是需要执行排序操作；分析下来，意思就是：需要对每条记录及random值记入临时表，并且需要在临时表上排序；

根据上篇文章的结论：对于InnoDB表来说，执行全字段排序会减少磁盘访问，因此会被优先选择；当内存不够时，才会使用rowid排序再回表；那么这里，针对的是存入random值的内存表，会使用那种算法呢？

结论是：根据rowid排序；因为对于内存表，回表过程只是简单地根据数据行的位置，直接访问内存得到数据，根本不会导致多访问磁盘；那么优化器就没有了磁盘IO这一层顾虑，因此它会优先考虑的，就是用于排序的行越小越好，所以，MySQL 这时就会选择 rowid 排序；

这条语句的执行流程（同时分析一下语句的扫描行数）：

（1）创建一个临时表；这个临时表使用的是memory引擎（这个引擎类型由配置参数 internal_tmp_disk_storage_engine 控制），表里有两个字段，第一个字段是double类型（random的值），为了后面描述方便，记为字段R，第二个字段是varchar(64)类型（word的值），记为字段W；并且，这个表没有建索引；

（2）从words表中，按主键顺序取出所有的word值；对于每一个word值，调用rand()函数生成一个大于0小于1的随机小数，并把这个随机小数和word分别存入临时表的R和W字段中，到此，扫描行数是10000；

（3）现在临时表有10000行数据了，接下来你要在这个没有索引的内存临时表上，按照字段R排序；初始化sort_buffer；

（4）sort_buffer中有两个字段，一个是double类型（参与排序的random的值），另一个是整型（rowid）；

（5）从内存临时表中一行一行地取出random的值和位置信息rowid，分别存入sort_buffer中的两个字段里；这个过程要对内存临时表做全表扫描，此时扫描行数增加10000，变成了20000；

（6）在sort_buffer中根据R的值进行排序；注意，这个过程没有涉及到表操作，所以不会增加扫描行数；

（7）排序完成后，取出前三个结果的位置信息rowid，依次到内存临时表中取出word值，返回给客户端；这个过程中，访问了表的3行数据，总扫描行数变成了20003；

小结一下：order by rand() 语句使用了内存临时表，而内存临时表排序的时候使用了rowid排序方法；扫描行数 = 初始化内存临时表时扫描原表的行数 + 排序时扫描内存临时表的行数 + 取rowid回内存临时表查数据的行数；

MySQL的表是用什么方法来定位“一行数据”的？——rowid

可以看到，图里有个数据行的位置信息pos，其实就是rowid；实际上它表示的是：每个引擎用来唯一标识数据行的信息；

上篇文章的场景中，主键ID就是排序过程中给的rowid，你可能会有疑问：如果创建的表没有主键，或者把一个表的主键删掉了，rowid如何取值？这种情况下，InnoDB会自己生成一个长度为6字节的rowid来作为主键；

• 对于有主键的InnoDB表来说，这个rowid就是主键ID；
• 对于没有主键的InnoDB表来说，这个rowid就是由系统生成的；
• MEMORY引擎不是索引组织表；在这个例子里面，可以认为它就是一个数组；因此，这个rowid其实就是数组的下标；

磁盘临时表

上篇文章中提到了，当sort_buffer的内存空间不够时，会借助磁盘临时文件，使用外部排序+归并；内存临时表也与之类似，tmp_table_size这个配置限制了内存临时表的大小（默认值是16M），如果临时表大小超过了tmp_table_size，那么内存临时表就会转成磁盘临时表；

下面修改MySQL的配置，让这条语句走磁盘临时表，并通过OPTIMIZER_TRACE查看其执行过程信息：

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

分析：

（1）因为将max_length_for_sort_data设置成16，小于word字段的长度定义，所以sort_mode里面显示的是rowid排序，这个是符合预期的，即参与排序的是随机值R字段和rowid字段组成的行；

（2）number_of_tmp_files的值居然是0，与预期不符；意味着没有用到临时磁盘文件排序，明明tmp_table_size的值是不够的：row_size=14，10000条数据就是140000字节，说明排序占用的空间超过了sort_buffer_size定义的32768字节了，理论上应该用临时文件排序啊？

原因是这里采用是MySQL5.6版本引入的一个新的排序算法，即：优先队列排序算法，而非使用临时文件时采用的归并排序算法；

其实，这个SQL语句只需要取R值最小的3个rowid；但是，如果使用归并排序算法的话，虽然最终也能得到前3个值，但是这个算法结束后，已经将10000行数据都排好序了，也就是说，后面的9997行也是有序的了；但实际上，我们的查询并不需要这些数据是有序的；所以，想一下就明白了，如果使用归并算法，这会浪费了非常多的计算成本；

从10000个值中取R值最小的3个rowid，这本质上是一个topK问题，解决此类问题的经典方案就是堆排序；而优先队列排序算法采用的正是大顶堆排序；

这里我们再看一下上面一篇文章中使用归并排序的SQL查询语句：

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

你可能会问，这里也用到了limit，为什么没用优先队列排序算法呢？

原因是，这条SQL语句是limit 1000，如果使用优先队列算法的话，需要维护的堆的大小就是1000行的(name,rowid)，超过了我设置的sort_buffer_size大小，所以只能使用归并排序算法；

总的来说，SQL语句中使用 order by 排序且使用limit N子句时，如果limit后的数值N不是很大从而可以满足这N条记录能全部放于sort_buffer中，则MySQL会使用优先队列排序算法，否则sort_buffer不够用，就只能使用磁盘临时文件+归并排序算法了；

其他的基于MySQL的随机排序方案

通过上面的分析，不论是使用哪种类型的临时表（内存/磁盘临时表），order by rand() 这种写法都会让计算过程非常复杂，需要大量的扫描行数，因此排序过程的资源消耗也会很大；

不妨换个思路，最初的目的是随机的找到3条记录，而唯一标识记录的就是他的主键ID，因此可以将问题转换成从表中随机计算出3个主键ID的值即可；

方案A：（1）取得这个表的主键id的最大值M和最小值N；（2）用随机函数生成一个最大值到最小值之间的数X=(M-N)*rand()+N；（3）取不小于X的第一个ID的行；依次找3个ID；

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;

这个方法效率很高，因为取max(id)和min(id)都是不需要扫描索引的，而第三步的select也可以用索引快速定位，可以认为就只扫描了3行；但实际上，这个算法本身并不严格满足题目的随机要求，因为ID中间可能有空洞，因此选择不同行的概率不一样，不是真正的随机；

比如表里有4个id，分别是1、2、4、5，如果按照上面的方法，随机值算出来X=1~5的概率是相同的，但是由于ID=3的记录不存在，因此随机值算出的X=3和X=4都对应主键ID=4的这条记录，因此每条记录被选中的概率不等；

方案A问题的关键在于可能存在主键非自然数连续，因此可以使用真实的行数来计算随机值，并且使用limit语句找到第X行记录，方案B如下：（1）取得整个表的行数，并记为C；（2）取得Y = floor( C * rand() )；floor函数在这里的作用，就是取整数部分；（3）再用limit Y,1取得第Y+1行记录；

方案B解决了方案A的概率不均匀问题；MySQL处理limit Y,1的做法就是按顺序一个一个地读出来，丢掉前Y个，然后把下一个记录作为返回结果，因此这一步需要扫描Y+1行；再加上，第一步扫描的C行，总共需要扫描C+Y+1行，执行代价比方案A的代价要高；当然，跟直接order by rand() 比起来，方案B执行代价还是小很多的（无需用到内存临时表和排序）；

这篇文章，其实是借着随机排序的业务场景需求，介绍MySQL对临时表排序的执行过程；如果直接使用order by rand()，这个语句需要Using temporary和Using filesort，查询的执行代价往往是比较大的；所以，在设计的时候你要尽量避开这种写法；

在实际应用的过程中，比较规范的用法就是：尽量将业务逻辑写在业务代码中，让数据库只做“读写数据”的事情；不要尝试让MySQL去解决业务逻辑问题！

下篇文章：《MySQL实战45讲》——学习笔记18 “索引失效、函数/隐式转换“【建议收藏】

本章参考：17 | 如何正确地显示随机消息？-极客时间