奇葛格的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次。