奇葛格的BLOG

http://jack.lifegoo.com/?p=27

RAND() 是MySql的一个内嵌函数，主要用来生成随机数。

RAND()/RAND(N) returns a random floating-point value v between 0 and 1 inclusive (that is, in the range 0 <= v <= 1.0). If an integer argument N is specified, it is used as the seed value, which produces a repeatable sequence of column values.

MySql的文档说”把 ORDER BY RAND()和LIMIT联合使用，那么就可以来随机选择行(ORDER BY RAND() combined with LIMIT is useful for selecting a random sample from a set of rows)”, 例如:

SELECT * FROM random ORDER BY RAND() LIMIT 1

当上述SQL运行时，RAND()必须每次都被解释以便获得新的随机数。同时从explain sql的extra信息我们大致可以推出上面SQL的工作流程:

1. MySql用结果集创建一个temporary table(Using temporary).
2. 给结果集的每一行赋予一个随机有序的索引.
3. 进行排序然后返回结果 (Using filesort).

这个过程对于少量数据(具体见后面的benchmarks report)是可行的，但是对于大数据集是很浪费时间的。换而言之，ORDER BY RAND()对于随机选取的scalibility是很差的。

现在回到问题的最初，前天钱斌在察看MySql服务器性能时发现ORDER BY RAND()这个SQL语句非常慢(数据库表内有近200,000的数据，以后还要增加)，然后他提出自己的一个解决方案 ——- 数据插入前随机排序，选取时顺序读取。这是一个可行的办法，成本是必须修改程序。另一方面我也不愿意放弃MySql提供的RAND()函数。

重新看ORDER BY RAND()的工作流程，可以找出优化的途径(序列号对应上面的工作流程顺序):

1. 结果集能不能缩到最小? 能不能做到和外部数据无关，而是一种常数的关系? 能不能在结果集的选取上就是随机的?
2. 对表结构里面的一些属性做索引。
3. 对结果集按照某个属性来做排序然后返回结果。
4. RAND()不能出现在WHERE后面以保证RAND()是只运行一次的。

按照这些想法，下面就是设计其实现。

1. 首先想到的方案很简单，类似内存访问。table里数据都是从第一条开始读取，其访问偏移量可以做到随机。
   

   SELECT FLOOR(RAND() * COUNT(*)) AS offset FROM random;
   SELECT * FROM random LIMIT offset, 1;

   唯一的问题是，上面是两句独立的SELECT语句，所以可以用存储过程或者MySql函数来实现。

2. 下面的方案主要集中力量在缩小结果方面。假设最简单的一种场景: random table里面有一个bigint型的主键(记作id)，那么选取出一个 id >= FLOOR(max(id) * RAND()) 会怎么样呢?
   

   SELECT * FROM random
   WHERE id >= (SELECT FLOOR(MAX(id) * RAND()) FROM random )
   ORDER BY id ASC LIMIT 1;

   可以分析出来，因为RAND()是在[0, 1]区间，所以结果集数目是在[0, max(id)]之间。这样就说明结果集是不稳定的，换句话说它可能受外部数据的变化而振动。更致命的缺陷是RAND()是在WHERE后面的，这样每选择一行，RAND()都要被解释一次。

3. 尝试改善上述方案的缺陷，我们得到这样的实现:
   

   SELECT *
   FROM random AS r JOIN (SELECT FLOOR(RAND() * SELECT MAX(id) FROM random) AS id ) AS r0
   WHERE r.id >= r0.id
   ORDER BY r.id ASC LIMIT 1;

   第二种方案里面嵌套SELECT我们用INNER JOIN来取代。这种取代使得RAND()只需要解释运行一次。当然它的结果集数目还是停留在[0, max(id)]区间。

最后是benchmarks的一些数据:

第1种解决方案: SELECT * FROM random ORDER BY RAND() LIMIT 1
第2种解决方案: SELECT * FROM random WHERE id >= (SELECT FLOOR(MAX(id) * RAND()) FROM random ) ORDER BY id ASC LIMIT 1;
第3种解决方案: SELECT * FROM random AS r JOIN (SELECT FLOOR(RAND() * SELECT MAX(id) FROM random) AS id ) AS r0 WHERE r.id >= r0.id ORDER BY r.id ASC LIMIT 1;
上述三种方案都分别独立运行100次。