Scott's world.

MySQL-正确显示随机行数笔记

Word count: 1.7kReading time: 6 min
2020/02/06 Share

MySQL-正确显示随机行数笔记

我们应该经常能遇到需要随机获取表中几行记录的需求,所以今天我们就来讨论这一个需求应该如何优雅地解决。

假设我们建立一个只有两个字段(‘id’,’word’)的表,在表面插入10000行记录,接下来我们需要随机选择三行显示出来,有什么方法,存在什么问题以及如何改进呢?

内存临时表

我们很容易想到使用order by rand()

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

通过explain命令可以知道这条语句需要临时表,并且需要在临时表上排序。

对于InnoDB表来说,执行全字段排序会减少磁盘访问,因此会被优先选择。

对于内存表,回表过程只是简单地根据数据行的位置,直接访问内存得到数据,根本不会导致多访问磁盘

所以,MySQL会选择行数相对少的rowid排序。

  • 执行流程

    1. 创建使用memory引擎的临时表,表里有两个字段,并且这个表没有建立索引
    2. 从需要查询的表中,按主键顺序取出所有的word值,且调用rand()函数生成一个大于0小于1的随机小数存入临时表中,此时扫描行数为10000。
    3. 临时表有10000行数据,按照前面生成的随机数字段排序。
    4. 初始化sort_buffer,字段与临时表相同。
    5. 从内存临时表中取出排序好的随机值和位置信息,分别存入sort_buffer两个字段里。此时扫描行数增加10000。
    6. 在sort_buffer中根据取出的随机值进行排序,此过程没有涉及表操作。
    7. 排序完成后,取出前三个结果的位置信息,依次到内存临时表中取出word值,返回给客户端。此过程扫描行数增加3行。

了解上面提到的位置信息,我们需要知道一个基本概念:MySQL的表是用什么方法来定位“一行数据”的。

如果你创建的表没有主键,或者把一个表的主键删掉了,那么InnoDB会自己生成一个长度为6字节的rowid来作为主键。即rowid表示的是每个引擎用来唯一标识数据行的信息。

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

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

磁盘临时表

并不是所有的临时表都是内存表。

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

磁盘临时表使用的引擎默认是InnoDB,是由参数internal_tmp_disk_storage_engine控制的。

如果复现上面的过程会发现即使数据总行数字节超过了定义的sort_buffer_size定义的字节数,但是并没有用到临时表,这是因为MySQL 5.6版本引入的一个新的排序算法,即:优先队列排序算法

我们只需要取最小的三个rowid,如果用归并排序算法就会将所有记录排序,这个过程会浪费非常多的计算量。

而根据优先队列排序算法,从最大堆或者最小堆取出最小的三个rowid的过程是最快得,所以这个过程并不需要临时文件。

而在其他情况下,我们也要考虑需要维护的堆,堆占用的空间是否大于临时文件。

总之,不论是使用哪种类型的临时表,order by rand()这种写法都会让计算过程非常复杂,需要大量的扫描行数,因此排序过程的资源消耗也会很大。

随机排序方法

  • 随机算法1

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

    这个方法效率高,因为取最大值和最小值是不需要扫描索引,而第三部的select也可以用索引快速定位,可以认为就只扫描了3行。

    但实际上,这个算法本身并不严格满足题目的随机要求,因为ID中间可能有空洞,因此选择不同行的概率不一样,不是真正的随机。

  • 随机算法2

    1
    2
    3
    4
    5
    6
    7
    mysql> select count(*) into @C from t;
    set @Y = floor(@C * rand());
    set @sql = concat("select * from t limit ", @Y, ",1");
    prepare stmt from @sql;
    execute stmt;
    DEALLOCATE prepare stmt;
    #由于limit 后面的参数不能直接跟变量,所以我在上面的代码中使用了prepare+execute的方法。你也可以把拼接SQL语句的方法写在应用程序中,会更简单些。
    1. 取得整个表的行数,并记为C。
    2. 取得 Y = floor(C * rand())。 floor函数在这里的作用,就是取整数部分。
    3. 再用limit Y,1 取得一行。

    根据上述方法,总共需要扫描的行数是C+Y+1行

    并且此算法比order by rand()的代价小很多

    因为随机算法2进行limit获取数据的时候是根据主键排序获取的,主键天然索引排序。获取到第9999条的数据也远比order by rand()方法的组成临时表R字段排序再获取rowid代价小的多。

    而如果要随机取3个word值,总共需要扫描的行数是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;

问题

上面的随机算法3的总扫描行数是 C+(Y1+1)+(Y2+1)+(Y3+1),实际上它还是可以继续优化,来进一步减少扫描行数的。

我的问题是,如果你是这个需求的开发人员,你会怎么做,来减少扫描行数呢?说说你的方案,并说明你的方案需要的扫描行数。

参考

CATALOG
  1. 1. MySQL-正确显示随机行数笔记
    1. 1.1. 内存临时表
    2. 1.2. 磁盘临时表
    3. 1.3. 随机排序方法
    4. 1.4. 问题
      1. 1.4.1. 参考