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

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

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

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

下面是表初始化的 SQL:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)

1
2
3
4
5
6
7
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
hoxis wechat
一个脱离了高级趣味的程序员,关注回复1024有惊喜~
赞赏一杯咖啡
0%