MySQL でレコードのランダム抽出をするには

ORDER BY RAND() で OK。

ただ、全レコードに対してランダムな数値を与えてインデックスなしでソートするのでそれなりのコストがかかる。

この場合の計算量はどうなんだろう。ソートの実装がどうなっているのかは知らないので確かなことは分からないけれど、LIMIT をつけずに全レコードをランダムソートするならば計算量はよくて O(N log N)程度のはず。LIMIT で K 件(K < log N)を抽出する場合は、愚直にやっても O(KN)あればできる。

よって、1件ずつランダム抽出していくような場合は大して問題にならないが、リストとしてまとめてランダムに並んだレコードを取り出したい、というような場合にはあまり効率的でない。

そういった場合には事前にインデックスつきのフィールドに RAND() を書き込んでおいて、取得したいときにそのフィールドで ORDER BY してやったほうがいいはず。