MySQL 的 ORDER BY RAND() 的替代方案

在 XDite 這篇 [Rails] The Better Way To Do Random 所提到 Jan Kneschke 的「ORDER BY RAND()」這篇文章裡為了找到 ORDER BY RAND() 的替代方案，花了不少功夫解釋。

(PS：我跟 XDite 同屬 PIXNET 的一員，其中本篇文章所提到的 VeryXD 主機目前也放在 PIXNET 的機房裡)

最原始的想法是：

SELECT MAX(id) FROM table;
### 在 application 取一個 1 到 id 中間的值
SELECT * FROM table WHERE id = ...;

但這篇文章要探討的是如何在 MySQL 裡全部做完，所以重點放在如何在 MySQL 裡取得 randid。

首先是透過 RAND() 幫忙：

SELECT RAND() * MAX(id) FROM random;

然後發現有小數點，所以用 CEIL() 變成：

SELECT CEIL(RAND() * MAX(id)) FROM random;

但這個 SQL query 效率不太好：如果有 1M rows，就會跑了 1M 次。所以利用 subquery 改寫成：

SELECT CEIL(RAND() * (SELECT MAX(id) FROM random));

用 EXPLAIN 檢查看起來不錯，所以包成 subquery 拉出隨機選出的 row：

SELECT name FROM random WHERE id = (SELECT CEIL(RAND() * (SELECT MAX(id) FROM random)));

結果發現速度不佳，用 EXPLAIN 檢查發現是因為 subquery optimization 被取消。所以改用其他的方法，像是利用 temporily table 與 JOIN：

SELECT name FROM random JOIN (SELECT CEIL(RAND() * (SELECT MAX(id) FROM random)) AS id) AS r2 USING(id);

速度沒什麼問題，用 EXPLAIN 檢查看起來也都 ok 了，所以我們要處理 id 不連續的情況，也就是有「洞」的狀態，所以取比這個 randid 大的第一個 row：

SELECT name FROM random AS r1 JOIN (SELECT (RAND() * (SELECT MAX(id) FROM random)) AS id) AS r2 WHERE r1.id >= r2.id ORDER BY r1.id ASC LIMIT 1;

至於更後面為了要做到在 non-uniform distribution 下的 ORDER BY RAND() 效果所花的功夫太大 (像是透過 trigger 產生某個 uniform 欄位，然後就可以用那個欄位用上面的方法處理)，一般人應該用不到。需要的人就麻煩自己去看了 :p