ORDER BY RAND()

原文地址:http://jan.kneschke.de/projects/mysql/order-by-rand

翻译:ShiningRay

译者序
之前有位朋友提到从MySQL随机取1条记录其实只要SELECT * FROM table ORDER BY RAND() LIMIT 1即可。其实这个语句有很大的性能问题,对于大表的效率是非常低下的。我们可以看一下MySQL对其的解释:

EXPLAIN SELECT *
FROM money_logs
ORDER BY RAND( )
LIMIT 1
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE table ALL NULL NULL NULL NULL 173784 Using temporary; Using filesort

这个SQL语句无法使用任何索引,还必须使用临时表和文件排序,在一个15万条记录的MyISAM表需要花大约0.3秒。已经是相当慢的了。如何优化,请往下看:

第一个例子我们先假设ID是从1开始并且1和ID的最大值之间没有任何空档。

将工作移入应用程序

第一个想法:如果我们可以事先在应用程序中计算出ID,那么就可以简化整个工作。

由于MAX(id) == COUNT(id) 我们只要生成从1到MAX(id)之间一个随机数,并将其传给数据库并取回随机行。

上面第一个SELECT基本上是一个可以被优化掉的空操作。第二个是一个针对常量的eq_ref查询,同样也很快。

将任务放入数据库

不过有必要将其放入应用程序吗?难道我们不能在数据库里完成?

OK,现在我们知道如何生成随机ID了,不过如何获取记录行?

哦,不!不要走这条路。虽然它很直观,但是也是最容易犯的错。理由是:在WHERE子句中的SELECT会针对外部SELECT取出的每一行执行一次。这可能会是0到4091行,看你的运气了。

我们必须用一种方法确保随机ID只被生成一次:

内部的 SELECT 生成了一个常数临时(TEMPORARY)表并且联接(JOIN)只选择了一行。完美。

没有排序、没有应用程序介入,查询的大部分都被优化了。

在数字中加入空档

为了使最终的解决方案通用化,我们必须考虑空档的可能性,如当你删除(DELETE)了记录行。

JOIN现在加入了所有大于等于我们随机数的ID,并且当直接匹配不存在的时候,只选择最临近的记录。不过一旦找到了某一行,我们就立刻停止(LIMIT 1)。同时我们根据索引(ORDER BY id ASC)读取记录。由于我们使用了>=而非=,所以我们可以削去CEIL同时还能获取同样的结果,节省了一点点开销。

平均分布

一旦ID的分布不再是平均的了,那么我们对行的选择也不是完全随机的了。

RAND函数生成诸如9到15之间的ID都会让id 16被选择。

目前还没有针对这个问题的真正的解决方案,不过你的数据是大部分不变的话可以添加一个将行号映射到ID的映射表:

row_id现在则是没有空档的,我们就可以再次运行我们的随机查询了:

1000次查找之后,我们可以看到一个平均分布:

使用触发器维护有空档的表

让我们就用前面的几个表:

一旦我们在r2中改动了某些东西,我们希望r2_equi_dist也被更新。

INSERT很简单,但在DELETE时我们需要更新equi-dist-id来维持id的连续。

UPDATE就非常直观了。我们只要维护一下外键约束:

一次多行

如果你想一次取回多行,你可以:

  • 执行多次查询
  • 写一个存储过程执行查询并将结果存入一个临时表
  • 进行一个UNION

存储过程

存储过程为你提供了通用语言中很有用的一些结构:

  • 循环
  • 控制结构
  • 过程

这个任务中我们只需要一个LOOP:

下面的问题留给读者解决:

  • 使用动态SQL并传入临时表的名字
  • 在表上使用一个UNIQUE索引并捕获UNIQUE键冲突来消除结果集中可能的重复记录。

性能

现在让我们看看性能方面发生了什么变化。我们有三个不同的查询来解决这个问题。

  • Q1. ORDER BY RAND()
  • Q2. RAND() * MAX(ID)
  • Q3. RAND() * MAX(ID) + ORDER BY ID

Q1预期消耗N * log2(N),Q2和Q3接近常数。

下标是评测的结果,针对N行的表(从一千行到一百万行),每个查询执行1000次。

如你所见,普通的ORDER BY RAND()从仅100行的表开始便落后于优化过的查询了。

关于这些查询更详细的分析可以在analyzing-complex-queries查阅.

“ORDER BY RAND()”的4个回复

  1. 感谢好文分享。请问下博主
    我对“在WHERE子句中的SELECT会针对外部SELECT取出的每一行执行一次。这可能会是0到4091行,看你的运气了。”
    这句不太懂,这是怎么个机制?

发表评论

电子邮件地址不会被公开。 必填项已用*标注