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的工作流程:
- MySql用结果集创建一个temporary table(Using temporary).
- 给结果集的每一行赋予一个随机有序的索引.
- 进行排序然后返回结果 (Using filesort).
这个过程对于少量数据(具体见后面的benchmarks report)是可行的,但是对于大数据集是很浪费时间的。换而言之,ORDER BY RAND()对于随机选取的scalibility是很差的。
现在回到问题的最初,前天钱斌在察看MySql服务器性能时发现ORDER BY RAND()这个SQL语句非常慢(数据库表内有近200,000的数据,以后还要增加),然后他提出自己的一个解决方案 ——- 数据插入前随机排序,选取时顺序读取。这是一个可行的办法,成本是必须修改程序。另一方面我也不愿意放弃MySql提供的RAND()函数。
重新看ORDER BY RAND()的工作流程,可以找出优化的途径(序列号对应上面的工作流程顺序):
- 结果集能不能缩到最小? 能不能做到和外部数据无关,而是一种常数的关系? 能不能在结果集的选取上就是随机的?
- 对表结构里面的一些属性做索引。
- 对结果集按照某个属性来做排序然后返回结果。
- RAND()不能出现在WHERE后面以保证RAND()是只运行一次的。
按照这些想法,下面就是设计其实现。
- 首先想到的方案很简单,类似内存访问。table里数据都是从第一条开始读取,其访问偏移量可以做到随机。
SELECT FLOOR(RAND() * COUNT(*)) AS offset FROM random;
SELECT * FROM random LIMIT offset, 1;
唯一的问题是,上面是两句独立的SELECT语句,所以可以用存储过程或者MySql函数来实现。
- 下面的方案主要集中力量在缩小结果方面。假设最简单的一种场景: 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()都要被解释一次。
- 尝试改善上述方案的缺陷,我们得到这样的实现:
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次。
random数据大小 |
第1种解决方案 |
第2种解决方案 |
第3种解决方案 |
100 |
0.08s |
0.08s |
0.02s |
500 |
0.08s |
0.80s |
0.00-0.01s |
1000 |
0.14s |
2.00s |
0.02s |
10000 |
1.53s |
65.02s |
0.00-0.02s |
100000 |
15.83s |
|
0.00-0.02s |