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

這篇 所提到 的「」這篇文章裡為了找到 ORDER BY RAND() 的替代方案,花了不少功夫解釋。

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

最原始的想法是:

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

但這篇文章要探討的是如何在 裡全部做完,所以重點放在如何在 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

MySQL 調整

昨天晚上幫「測試」,發現速度卡在 的 CPU bound,先用 丟在背景跑,再用 抓幾個比較明顯的 slow query,補了幾刀 INDEX 後,速度快了不少,不過還是不太滿意。

印象中 MySQL 除了可以紀錄 slow query 外,還可以紀錄沒用到 INDEX 的 SQL query,花了不少時間才找到。這些指令是可以線上改,不需要重開 (如果你堅持要改設定檔重開也 ok),不過請不要在 production 的機器上開,以免 SQL query 寫的很爛,產生大量的 log:

mysql> SET GLOBAL log_queries_not_using_indexes = 1;
Query OK, 0 rows affected (0.00 sec)
mysql> SET GLOBAL slow_query_log = 1;
Query OK, 0 rows affected (0.00 sec)

參考:

PS:這只是告訴你問題在哪裡,而非解決的方法。要知道為什麼會慢,你需要讀不少資料,像是 這類的書籍,以及網路上 MySQL 資料庫長輩們的討論。

Update:翻到 這篇,可以檢查過度 index 時造成效能降低的問題 :p

交大斷網

北區凌晨 00:00 ~ 06:00 斷電,結果斷電後國內是通的,但國際電路卻不通... (印象中這些 router 都是放在一起的,不知道哪裡出問題) 看了一些 server,發現有些 server 有開起來,但有很多 server 沒有開起來,DNS 只有 140.113.6.2 起來,另外兩台 (140.113.1.1 與 140.113.250.135) 都沒起來。另外,Group.NCTU.edu.tw 沒開起來,也許等早上再看看情況吧。

印象中很久沒斷這麼久... (尤其是 DNS,通常不會擺爛到早上再處理)

關於趨勢科技的 Prior Art

要推翻專利 (使得專利無效) 可以用 () 證明在該項專利申請前,專利的內容就已經為人所知。

在 1995/09/26 申請了一項專利 (),描述在 SMTP Gateway 以及 FTP Gateway 上掃描病毒。在今年年初的時候控告 在產品裡使用的 侵犯了該項專利。

由於 都使用了類似的技術,趨勢控告 Barracuda 這件事情在國外的開源社群中有很大的反彈聲浪,畢竟沒人能保證下一個被告的不是 SpamAssassin/amavisd-new。

剛剛在 上看到有個人說他以前在的公司 (在瑞典) 早在 1995 一月就已經推出過類似的產品,有大約上萬的客戶安裝過這向產品,並且打算以此提出 Prior art 推翻 Patent 5623600:

令人振奮的好消息啊...