MySQLでの高速な重み付きランダム表示
東京都で賢い借金返済方法を教えます！では、MySQLに格納したWikipedia記事をランダムに表示している。速度を気にしないなら、
SELECT * FROM docs ORDER BY RAND() LIMIT 10;
で良いのだけど、レコード数が多いと遅くて使いものにならない。そこで、記事IDを1から始まる連番になるようにDBに格納している。このようにすると、アプリケーション側でDBに格納されている文書IDが全て分かるので、ランダムに文書IDを10個選択して、その文書IDのレコードを表示することで、ランダム表示を実現している。
例えば、IDは10個選択するRubyコードは、
ids = Array.new(10){ rand(num_docs) + 1 }
で、DBに発行するSQLはこんな感じになる。
SELECT * FROM docs where ID in (id1,id2,..,id10) LIMIT 10;
最初はこの方式で満足していたのだが、不満も出てきた。Wikipediaの記事をランダム表示させてしばらく眺めていると、やけにイタリアのコムーネ（市町村）の記事が多い。調べて見たところ、イタリアのコムーネの記事は8102件もあって、結構なボリュームを占めていた。*1
他にも、イタリアのコムーネなどのマイナー記事が頻繁に表示されるのはつまらないので、記事の重要性に応じて表示頻度を変えたくなった。つまり、重要な記事ほど、頻繁に表示されるように変更したくなった。
重要度に応じて出現割合を変えるのは RAND() 関数を使えば簡単だが、前述のように処理速度が遅いため実用的でない。そこで、アプリケーション側でなんとかする方法を考えた。
まず、重要度順に記事をソートして、各記事のソート順位を求める。そして、Wikipedia記事テーブルにRANKカラムを追加し、RANKカラムに求めたソート順位を格納する。つまり、RANKカラムは1からレコード数までの範囲の値をとり、そのカラム値が小さい記事ほど重要度が高いことになる。
後は、アプリケーション側でRANKを10件ランダムに選択して、その値をカラム値とする記事を取得すれば良い。この時、小さいRANKを優先して選択する。このような選択方法は色々とある。
例えば、次のRubyコードの場合、ランク1位の記事は最下位の記事の2.7(=e)倍の確率で選択し、また、記事の選択確率はランクに応じて指数的に減少する。
ranks = Array.new(10) { p = exp(1 - rand()) - exp(0) q = exp(1) - exp(0) (p / q * num_docs).to_i }
選択したrank値を用いてレコードを表示する際はIDの場合と同じで、次のようになる。
SELECT * FROM docs where RANK in (rank1,rank2,..,rank10) LIMIT 10;
まとめる。
- MySQLに格納したデータを高速にランダム表示するには、アプリケーション側でレコードIDなどを指定する。
- 重要度に応じたランク値をDBに格納することで、重み付きランダム表示が可能となる。
