假设有一个单词表，如何从中随机选择 3 个出来？

参考：https://time.geekbang.org/column/article/73795

假设有一个单词表，如何从中随机选择 3 个出来？

下面是表初始化的 SQL：

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

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

用 explain 对其进行解析：

Extra 字段显示 Using temporary，表示使用临时表。Using filesort，表示需要执行排序操作。

语句执行流程：

1、创建临时表，有两个字段，分别是 double 类型，记为 R，和 varchar(64) 类型的 W 字段，这个表没有索引；

2、从 words 表中，按主键顺序取出所有的 word 值，对于每一个值，调用 rand() 函数，生成一个随机数

3、将随机数和 word 值，分别存入临时表的 R、W 字段。这时，扫描表行数为 10000；

4、对临时表中的数据进行排序；初始化 sort_buffer；

5、从临时表中依次取出 R 值和位置信息，存放到 sort_buffer 中，此时要做全表扫描，行数为 10000；

6、在 sort_buffer 中根据 R 值排序，这时不涉及扫描表操作；

7、排序完成，取出前三个位置信息，依次到内存临时表中取出 word 值，返回给客户端；

随机排序完整流程图 1

一个表是用什么标记一行数据的？

有主键的 InnoDB 表：主键 ID
没有主键的 InnoDB 表：系统生成一个 rowid
Memory 引擎的临时表：数组的下标

磁盘临时表

其实，并不是所有的临时表都会采用内存表。

tmp_table_size 这个配置限制了内存临时表的大小，默认值是 16M。

如果临时表大小超过了 tmp_table_size，那么内存临时表就会转成磁盘临时表。

磁盘临时表使用的是 InnoDB 引擎，该设置是通过参数 internal_tmp_disk_storage_engine 设置的。

磁盘临时表中使用的优先队列排序算法，而不是归并排序。

执行流程如下：

1、对 10000 个准备排序的 (R, rowid)，先取前三行，构造一个堆；

2、取下一行数据，跟堆中最大的 R 比较，如果小于 R，就把 (R, row) 从堆中摘除，换成新取的数据；

3、重复上述步骤，直到 10000 个数据完成比较。

流程结束后，构造的堆里面就是 10000 行中 R 值最小的三行。

然后依次把它们的 rowid 取出，去临时表拿出对应的 word 字段。

如果，要维护的堆大小超过 sort_buffer_size 的大小，就只能使用归并排序算法了。

无论哪种算法，order by rand() 的计算过程都很复杂，需要扫描很多行数，资源消耗也很多。

随机排序

如果只需要取一个随机 word 值？

很简单，只需要从主键最大值和最小值之间，生成一个随机数 X，然后取不小于 X 的第一个 ID 的行即可。

这样就不需要进行全表扫描，但是若 id 存在空洞，就会出现问题。

比如，有 4 个 id：1、2、40000、40001？这个算法基本上就是个 bug 了。

所以，用值随机不可取。

随机算法 2：

1、取表的行数 C；

2、从行数中随机出一个数，然后取整，记为 Y；

3、再用 limit Y,1 取得一行。

这样就是以行数来进行随机了。

随机算法 3：

如何取出 3 个值呢？

1、取得表行数：C；

2、根据相同的随机算法得到 Y1、Y2、Y3；

3、再执行 limit Y,1 得到三行数据；

总扫描行数是 C+(Y1+1)+(Y2+1)+(Y3+1)

mysql> 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；

生命在于折腾

MySQL实战 | 17 如何随机显示数据？

顺序排序

内存临时表

磁盘临时表

随机排序