SQL使ってテーブルからランダムにN件引っ張りたい場合

結論先に書くと、根が深い問題なので一般化すると難しいです。が、規模が小さくて(数万件程度まで)primary keyが1つだけの場合は、

select * from rinchan_images where id in (select id from rinchan_images order by rand() limit N)
な感じで。MySQLが「ERROR 1235 (42000): This version of MySQL doesn't yet support 'LIMIT & IN/ALL/ANY/SOME subquery'」とかたれた場合は
select * from rinchan_images where id in (select id from (select id from rinchan_images order by rand() limit N) as hoge)
な感じで。( thanks to LIMIT付きのサブクエリでWHERE INしたい時のメモ)

みなさん、たくさんのリンちゃんの画像の中からランダムに20個引っ張ってきて眺めたいなんてこと、よくありますよね。あまりにありふれたシチュエーションなのでググればSQLのサンプルもすぐに見つかるかと思いきや、そうでもなかった。というわけで、世の中がリン廃で統一されるのはもう少し先のようです。・・・なことが言いたいんじゃなくて・・・

MySQLの場合、比較的すぐに「order by rand() を使え」てのが見つかります。が、それ以上に、ググった結果の上位に「order by rand() は使うな」というのも見えてきます。使うなっていうのの例だと、こことかこことか。結構ややこしい話なので順番に見えていきましょう。

まず、MySQLは「order by rand()」という機能をこういう目的のために提供してます。が、その内部実装はどうも、keyをテンポラリテーブルに並べてで乱数振って出てきた値を使ってkeyを並び替えてその結果を引っ張ってくる、ということのようです。

mysql> explain select id from rinchan_images order by rand() limit 1;
+----+-------------+-------+-------+---------------+---------+---------+------+------+----------------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+---------+---------+------+------+----------------------------------------------+
| 1 | SIMPLE | twit | index | NULL | PRIMARY | 8 | NULL | 4213 | Using index; Using temporary; Using filesort |
+----+-------------+-------+-------+---------------+---------+---------+------+------+----------------------------------------------+
というわけで、この方針で行くなら、order by rand() で selectされるのは極力primary key のみにしておき、primary key以外のカラムもほしい場合はサブクエリとか使ってクエリを分けるべきとなります。というわけで、最初に示したような例になります。

でもちょっと待って、リンちゃんの画像なんて10万個や100万個くらいあるのが普通なので、primary keyを全部集めてテンポラリで並べ替えなんてオンメモリでできないです。・・・いや100万個ならメモリに乗るけど。でもやっぱりテンポラリテーブル作って並び替えるには負荷が高い。手元テストだと、10万件で0.9秒、100万件で9秒のオーダです。@Atom N270 (1.60GHz Sinle(with HT)), DDR2-533 2GB。というわけで、件数多いとやっぱりつらいです。

回避策は、MySQLのマニュアルのコメントからリンクされてるページになり、要するにselectの外で別途乱数振れということですね。さらりと書いてくれてますがこれも結構やっかいなんです。ここから長いですがauto_incrementで連番が一切空いていないという仮定で話が少し続きます。

連番かつ空きがない場合は、0以上max(id)未満の値を引っ張ってきてそれに合致する行を1つだけselectすればいいわけです。無理矢理1つのSQLにするとこんな感じ。

select * from (select ri2.* from rinchan_images as ri2, (select max(id) as maxid from rinchan_images) as maxid, (select rand() as rnd) as rnd where ri2.id >= maxid.maxid*rnd.rnd and ri2.id < 1+(maxid.maxid)*rnd.rnd limit 1) as ri1;
1件じゃなくてN件なら「+1」を「+N」にすればいい・・・かと思いきやそれだと「ランダムに選んだ位置から連続してN個」になるのでNG。じゃこのSQLをN回実行すればいいかというとrand()とはいえ同じ値を引いてしまう可能性もあるのでやっぱりダメ、N/(count) くらいの確率で同じ値を引いてきてしまうのを覚悟しないといけない。まぁ異なるN個が出るまで何度も繰り返せばいいという手もあるけど。

その辺も考慮して1つのSQLにするとこんな感じ。

select * from (select ri2.* from rinchan_images as ri2, (select max(id) as maxid from rinchan_images) as maxid, (select count(*) as cnt from rinchan_images) as cnt where 4*N > cnt.cnt*rand() limit N) as ri1;
「4*N」ていうのが小細工で、いくらrand()が一様分布に従うことがわかっているからと言ってN回の試行でキレイに1/Nに一様分布するとは限らないので多めに取ってきてlimit Nしてます。ここでは適当に「4倍」しましたが、何倍にしないといけないかは実は結構小難しい話です。

何倍必要かは、一様分布に対するカイ二乗分布を考えないとダメな話となります。N個の等間隔の分割は例としてよく載ってるけど、今は N/count と (count-N)/count との2分割でのカイ二乗分布なのであんま例が載ってなくて私もよくわからない・・・たぶん自由度1でいいはずなんだけど・・・とりあえず手元でシミュレーションした結果こんな感じになりました。シミュレーションに使ったC#のソース

  • N=1 の場合、+4で99%, +6で99.9%, +8で99.99%
  • N=2 の場合、+6で99%, +9で99.9%, +11で99.99%
  • N=3 の場合、+8で99%, +11で99.9%, +14で99.99%
  • N=4 の場合、+10で99%, +12で99.9%, +15で99.99%
  • N=5 の場合、+11で99%, +14で99.9%, +17で99.99%
  • N=6 の場合、+13で99%, +16で99.9%, +19で99.99%
  • N=7 の場合、+14で99%, +18で99.9%, +21で99.99%
  • N=8 の場合、+15で99%, +19で99.9%, +21で99.99%
  • N=9 の場合、+17で99%, +21で99.9%, +24で99.99%
  • N=10 の場合、+18で99%, +22で99.9%, +26で99.99%
というわけで、+12か*3のうちの大きい方を選んどけばとりあえずOKっぽいです。とはいえ、しょせん乱数振ってるだけなので、例えたくさんめに取ってもものすごく低い確率で足りないことが起こりうることになります。auto_incrementで連番が空いていない前提でもこれです、ああ怖い。

連番が空いている場合、空き具合にもよりますがほとんど空いていないような場合は「えいや」で連番っぽく扱えばいいでしょう。ごくまれに出やすいヤツがいる程度で、実際にはほぼ誤差範囲でしょう。連番が結構空いている場合は、もはや一様分布を仮定できないので、ランダム値でselectするというやり方が崩壊して、より一般的なやり方に帰着せざるを得なくなります。

より一般的なやり方は「select * .... order by (primary key) limit N offset n」を使うやり方です。あらかじめ「select count(id) from rinchan_images」でcountを求めといた上で、0以上count未満の乱数nを発生させて、N個を引っ張ってきます。このままだと連番N個なので回避するにはN=1で必要な回数分だけたたくしかなさそう。・・・私の力では1つのsqlで書くことはできなかった・・・

ただこの「limit N offset n」というのも、nがテーブル内の個数に近いくらい非常に大きいとスケールしないやっかいな構文です。2カラムしかないテーブルだとこのまま「limit N offset n」とたたいた方が早かったですが、カラム数によっては先の例のように先にidだけをselectしといてそれを使ったサブクエリでid以外のカラムを引っ張ってきた方がいいかもしれません。

とまぁ大まかにこんな感じです。要するに一般化すると実質ムリです。auto_incrementでなかっただけでもこうなり、primary keyが複数行の場合とかもう考えたくもないですね・・・と思ったけどprimary keyが複数行の場合は単純に並べればいいだけか。MySQLってサブクエリに複数行書けたっけ?手元のMySQL5.1で試したらいけたっぽい。ということで、primary keyが複数行の場合はSQLに書き下すのがめんどいだけで、実質問題なさそうですね。

根本的にこの問題を解決したい場合は、そういうことができるようにデータ構造をあらかじめ準備しておくしかないです。つまり、SQLに頼らないレベルで、かつ乱数を使ってランダムに行を引っ張ってこれるように、事前に設計しておかなければなりません。

なんでこの話こんなにややこしいかというと結局、理論的なRDBMSがそもそも「順番」を扱えないからです。そもそもRDBMSが扱えるのは集合に対する選択・射影・結合で、それ以外のは各種エンジンが勝手に実装しているに過ぎず、たとえばorder byなんかは結果を一度出力してからそれを並び替えているだけですね。順番なんてのは並び替えられた後にしか存在しない概念です。というわけで、小難しくRDBMSだ正規化だとか考えるくらいなら、auto_increment使っといた方がいろいろ小細工がききやすい・・・ように感じられる今日この頃です。

・・・あれ、ところでぼくのリンちゃん画像(ランダム20件)は?

続: SQL使ってテーブルからランダムにN件引っ張りたい場合に続くようだ。

このブログ記事について

このページは、らるるが2013年8月13日 06:55に書いたブログ記事です。

ひとつ前のブログ記事は「画像系の短縮URLの雑記」です。

次のブログ記事は「フルスタックエンジニア」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ

ウェブページ

Powered by Movable Type 7.5.0