奇葛格的BLOG

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

RAND() 是MySql的一個(gè)內(nèi)嵌函數(shù)，主要用來(lái)生成隨機(jī)數(shù)。

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的文檔說(shuō)”把 ORDER BY RAND()和LIMIT聯(lián)合使用，那么就可以來(lái)隨機(jī)選擇行(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

當(dāng)上述SQL運(yùn)行時(shí)，RAND()必須每次都被解釋以便獲得新的隨機(jī)數(shù)。同時(shí)從explain sql的extra信息我們大致可以推出上面SQL的工作流程:

1. MySql用結(jié)果集創(chuàng)建一個(gè)temporary table(Using temporary).
2. 給結(jié)果集的每一行賦予一個(gè)隨機(jī)有序的索引.
3. 進(jìn)行排序然后返回結(jié)果 (Using filesort).

這個(gè)過(guò)程對(duì)于少量數(shù)據(jù)(具體見后面的benchmarks report)是可行的，但是對(duì)于大數(shù)據(jù)集是很浪費(fèi)時(shí)間的。換而言之，ORDER BY RAND()對(duì)于隨機(jī)選取的scalibility是很差的。

現(xiàn)在回到問(wèn)題的最初，前天錢斌在察看MySql服務(wù)器性能時(shí)發(fā)現(xiàn)ORDER BY RAND()這個(gè)SQL語(yǔ)句非常慢(數(shù)據(jù)庫(kù)表內(nèi)有近200,000的數(shù)據(jù)，以后還要增加)，然后他提出自己的一個(gè)解決方案 ——- 數(shù)據(jù)插入前隨機(jī)排序，選取時(shí)順序讀取。這是一個(gè)可行的辦法，成本是必須修改程序。另一方面我也不愿意放棄MySql提供的RAND()函數(shù)。

重新看ORDER BY RAND()的工作流程，可以找出優(yōu)化的途徑(序列號(hào)對(duì)應(yīng)上面的工作流程順序):

1. 結(jié)果集能不能縮到最小? 能不能做到和外部數(shù)據(jù)無(wú)關(guān)，而是一種常數(shù)的關(guān)系? 能不能在結(jié)果集的選取上就是隨機(jī)的?
2. 對(duì)表結(jié)構(gòu)里面的一些屬性做索引。
3. 對(duì)結(jié)果集按照某個(gè)屬性來(lái)做排序然后返回結(jié)果。
4. RAND()不能出現(xiàn)在WHERE后面以保證RAND()是只運(yùn)行一次的。

按照這些想法，下面就是設(shè)計(jì)其實(shí)現(xiàn)。

1. 首先想到的方案很簡(jiǎn)單，類似內(nèi)存訪問(wèn)。table里數(shù)據(jù)都是從第一條開始讀取，其訪問(wèn)偏移量可以做到隨機(jī)。
   

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

   唯一的問(wèn)題是，上面是兩句獨(dú)立的SELECT語(yǔ)句，所以可以用存儲(chǔ)過(guò)程或者M(jìn)ySql函數(shù)來(lái)實(shí)現(xiàn)。

2. 下面的方案主要集中力量在縮小結(jié)果方面。假設(shè)最簡(jiǎn)單的一種場(chǎng)景: random table里面有一個(gè)bigint型的主鍵(記作id)，那么選取出一個(gè) id >= FLOOR(max(id) * RAND()) 會(huì)怎么樣呢?
   

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

   可以分析出來(lái)，因?yàn)镽AND()是在[0, 1]區(qū)間，所以結(jié)果集數(shù)目是在[0, max(id)]之間。這樣就說(shuō)明結(jié)果集是不穩(wěn)定的，換句話說(shuō)它可能受外部數(shù)據(jù)的變化而振動(dòng)。更致命的缺陷是RAND()是在WHERE后面的，這樣每選擇一行，RAND()都要被解釋一次。

3. 嘗試改善上述方案的缺陷，我們得到這樣的實(shí)現(xiàn):
   

   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來(lái)取代。這種取代使得RAND()只需要解釋運(yùn)行一次。當(dāng)然它的結(jié)果集數(shù)目還是停留在[0, max(id)]區(qū)間。

最后是benchmarks的一些數(shù)據(jù):

第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;
上述三種方案都分別獨(dú)立運(yùn)行100次。