MySQLのorder by rand()

インデックスをかけてるテーブルでも、結局ランダムなので全件捜査してから値を返す。プライマリーキーに対して rand() する場合でも O(1) ではないのですよね。なんか回避する方法があったりするのかな。

自分は良くorder by rand()を使ってます。
んで、id:naoya氏も懸念してるようにテーブルサイズが増大した時の動作とかその辺がorder by rand()だときついです。
追記
下記の方法はidに欠番があったりすると使い物になりません。
idに欠番がなく、idに数値を使ってる場合のみ有効です。悪しからず。
なので自分の場合は

set @id = floor(rand()*n)+1;
select id from entry where id = @id;

ってな感じでやってます。
純粋にorder by rand()を使うより体感的にかなり高速だと思うけどどれくらい早くなるかは分かりません。
もっと良い方法があれば知りたい所。

ちなみに上のSQL文は下と同様の動作をします。

select id from entry order by rand() limit 1;

PS:

set @id = floor(rand()*n)+1;

上の「n」は対象のテーブルの行数です。
こうする事によりテーブル全体をorder byする事を防いでます。

追記
にぽたん氏のコメントにあるように

ORDER BY RAND() LIMIT 1 な場合のもっと早い方法。ただ、id に DELETE によって欠番があると使えなかったりする罠

idに欠番があると使えないっす。
て事でこれをidの欠番があっても高速で取り出せる方法を知りたい所。