Smarticen Notes

正确显示随机消息

7 min read

从一个单词表中随机选出三个单词。如何保证这个逻辑不会随着表的增大而越来越慢。

首先建表并插入初始化数据

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

内存临时表

首先最简单的方法就是使用order by rand()来实现这个逻辑：

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

随机查询取前3条记录。

使用explain分析这条语句： 其中Extra字段中的Using templorary表示需要使用临时表，Using filesort表示需要执行排序操作。所以这条语句的执行需要使用临时表并且需要在临时表上排序。

对于临时内存表中的排序来说，会选择order by如何工作中那种排序算法呢？对于innodb表来说，会优先使用全字段排序，这样可以减少磁盘访问。但是临时表就在内存当中，回表就是直接访问内存，不会导致多访问磁盘，所以会优先考虑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.

内存临时表其实可以看做是一个数组，sort_buffer中的位置信息就是数组的索引，通过索引能够迅速在内存中找到对应的记录，所以才选择存储位置信息的。

order by rand()使用了内存临时表，内存临时表排序的时候使用了rowid排序方法。

磁盘临时表

tmp_table_size这个配置限制了内存临时表的大小，默认值是16M。如果临时表的大小超过了tmp_table_size，那么内存临时表就会转为磁盘临时表。

磁盘临时表使用的引擎默认是InnoDB，是由参数internal_tmp_disk_storage_engine控制的。当使用磁盘临时表的时候，对应的就是一个没有显式索引的 InnoDB 表的排序过程。

这里的排序使用的是优先队列排序算法，只需要维护一个只有三个记录的最大堆，然后扫描一边结束就可以了获得对应的值了，不需要使用外部文件进行外部排序。 不过如果limit后的值比较大，就算维护一个堆也超过了sort_buffer_size大小，那么还是会使用归并排序算法。

总是不管是那种临时表，order by rand()这种写法都会让计算过程非常复杂，需要大量的扫描行数，排序过程的资源消耗也很大。

随机排序方法

先只取一个word值

  1. 取得这个表上主键id的最大值M和最小值N。
  2. 用随机函数生成一个最大值到最小值之间的树X=(M-N) * rand() + N;
  3. 取不小于X的第一个ID的行。

前两步不需要扫描索引直接可以获得，第三步可以利用索引快速定位。但是关键在于这种方法本身不能满足随机要求，因为ID中间可能有空洞，因此选择不同行的概率不一样，不是真正的随机。

例如4个id为1、2、40000、40001，那么几乎完全没有随机的意义了。所以为了得到严格随机的结果，可以使用下面的流程：

  1. 取得整个表的行数，记为C。
  2. 取得Y=floor(C*rand())。floor就是取整数部分
  3. 再用limit Y, 1取得一行。

这里就是按照顺序一个一个读出来，丢掉前Y个，然后把下一个记录作为返回结果。总共需要扫描C+Y+1行。

比起order by rand()，不需要创建临时表，也不需要对临时表进行排序，所以代价要小得多。

现在按照这个思路，就是将这个算法连续执行三次，获得对应的三个值即可

  1. 取得整个表的行数，记为C。
  2. 根据相同的随机方法得到Y1,Y2，Y3.
  3. 再执行三个limit Y,1语句得到三行数据。

Graph View