読者です 読者をやめる 読者になる 読者になる

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

ORDER BY RAND()の代わりを実装する、あるいはMySQLでランダムにデータを取ってくる方法についてのメモ

 こんにちは。相変わらずBookableというサービスをこつこつとやっているのですが、前回に「ORDER BY RAND()を使うと重くなる」という話を書いたところ、知人から「それやめろ」という斧であったり、あるいは他の方面からアドバイスを頂きました(Thanks グニャラくん!)。

 なんでORDER BY RAND()がダメなの?という話は、ちょっと息抜きに翻訳したものがあるのですが、まず問題としてMySQLの乱数を生成するコストが高いという問題がある様子。少なくとも全件に対して乱数を発行するし、そして並び替えも発生してしまうので、とにかく非効率であると。だからその辺はMySQLにまかせるのではなく、それを呼び出すプログラム側にまかせたほうが圧倒的に効率がよくなるようです。

 例えば、RANDでやると、下のように件数が増えるにつれて負荷が膨大になっていきます。

 djangoの場合、元々のOMRにORDER BY RAND()クエリを作るためのものが実装されており、プロトタイプの段階ではそれでもよかったのですが、扱うデータが増えるにつれて、普通に負荷がかかるようになりましたので、すり替えた次第です。その結果、圧倒的にレスポンスはよくなりました。下がmuninのログです。分かりにくいですが、金曜日0:00付近ですね。

 いままでのはなんだったの……という数値まで落ちましたね。

 今回は、その辺について、軽く作業メモをしておきたいと思います。

実装の方針

 実装の方針としては、最初にグニャラさんの記事で解説があったように、個別に乱数が入っていて、かつIndexが貼られているフィールドを作ります。Pythonの場合、randomライブラリのrandom()を呼び出すと、float値の0〜1の間で生成してくれるので、それに対して乱数でアクセスします。

 当然、このフィールドに「直接」アクセスすることはできませんが(そもそもその値があるかどうかがわからない)、元々のORDER BY RAND()の発想を見てみると、どうやらプログラム側で発生させた乱数から見て隣接する値を持つレコードを持ってくるということになるのかな、と思います。つまり、ランダムで 0.3が出てきて、レコードに 0.1, 0.25, 0.31とするなら、それよりも大きい数(この場合なら0.31)を一つだけ取ってこい、といったようなクエリになるかと思います。

 で、上記では一つだけ取り出す場合のことになっていましたが、自分が確認したところだと、1件ずつ取り出してきて、最後にN件(Nは任意の数)にプログラム側で合わせるという実装であるならば、30件取り出すくらいだったら全然マシ、というか実装しろレベルでありました。下に具体的な画面をアップしておきます。参考までに、前回はこちら。

 で、改善した様子。

 クエリで使っている時間が、1000msecから100msecくらいにまで落ちてますね。ただ、この方法、実はデータベース側から見るとそりゃそうだろという話なんだけど、プログラム側から見ると、結構いろいろと奥が深かったりします。

 先に進む前に、ここで自分が理解したのは、とりあえず、このフィールドというのは、そのポジションを決定するものである、という感じで理解しました。

第一に考えること: 隣接する数があるとは限らない

 例えば、 0.1, 0.2, 0.5 というデータがあったとして、プログラム側から「0.6より大きい数字を持つデータを持って来い」と言った場合、当然のことながら隣接する数が無いので、0件となります。なので、まず一つに「本当にちゃんとレコードを取ってこれているの?」というのを、プログラム側で調べる必要があります。で、とれなかったらやりなおせ、ということをやる必要はあります。

第二に考えること: 複数同じレコードが出てくる

 上記とちょっと似ています。同じく 0.1, 0.2, 0.5 というデータがあったとします。例えばここから2件のデータを取ってくる場合、たまたま「0.3、0.4」で、かつ「それ以上のデータを取ってくる」とした場合、「0.5」のデータが重複してしまうことになります。これでもいいという場合はいいんですが、自分の場合だと、同じレコードはできるだけ出したくない、という思いがあったので、このあたりもチェックするようにしました。

他の方法

 とはいえ、この数字は単なるポジションの問題であるといいました。愚直にランダムにしたいのであるならば、1件ずつ取ってくるという方法もありですが、「なんとなくランダムになっていればいい。具体的には順番は一緒でも、取ってくる場所が違えばそれでいい」という場合もあります。

 例えば、0.1, 0.3, 0.6, 0.8というデータがあったとして、ここから任意の2件を取り出したい場合、別に順番は気にしないよ、というのであるならば、任意の場所を指定して、そこからN件取り出すというのは、有効な手段ですし、元々のRANDっぽく、なおかつ重複もしないというシンプルでいい方法だと思います。

 また、これをさらに応用して、N件欲しい場合、N件に、さらに余計な幅を持たせたM件をプラスして、その中からプログラムでランダムに取ってくるという実装もありでしょう。例えば、100件欲しいなら、1000件とってきて、さらにそこから100件に絞り込む、といったようなことです。もし、サーバー側に余力があるのなら、上の方法も、随時1件ずつ取ってくるよりいいでしょう。

 ただ、この方法もちょっと欠点があって、要するに何のデータがあれば、何かのデータもあるという組み合わせが容易に出来てしまいます。予測が出来ちゃうわけですね。そうすると、N件+M件という方法を推し進めてもいいのですが、そうなると全件取得をデータベース側でやるか、プログラム側でやるという風になってしまう。

 それを回避する方法として、定期的にアクセスされないであろう時間帯(例えば午前3時)のときに、乱数を生成しなおすという方法もありますが、当然のことながら、乱数を生成しなおしているときは、莫大なクエリが発行されたりするので、レスポンスが遅くなったりします。少ないデータ数だったらいいのですが、例えば12万件のデータを持っていたりすると、20分ほどはアクセスしずらい状態が生まれます(逆に考えれば20分くらいで済むならそれでいい、という考え方もできます)。

応用

 で、この方法なんですが、ちょっとした応用が効いたりします。例えばプログラムで渡される乱数が0〜1未満の場合は、実数というか、いわゆる小数点より上の数(例えば25.34なら25の部分)に、何らかのデータが埋め込めるというのがあります。愚直に別々にフィールドを持っておいて、さらにランダム用のフィールドで絞り込むという形をとってもいいのですが、だったら埋め込んでしまえというのがあります。

 例えば、はてなブックマークでブックマークされたエントリで、3User以上のものを取り出したいといった場合、3.123みたいな形にすると、3.0 > x > 9.0 みたいな形でランダムに取り出せます。もちろん、二つのインデックスを組み合わせたものを作ってもいいとは思います。

 ただ、この場合だと、普通のrealというかfloat的なフィールドを作ると失敗する可能性があり、DECIMALでfloat + intみたいなフィールドを作ってあげる必要がある可能性があります。DESCIMALは下のようなフィールドですね。

まとめ

 というわけで、ORDER BY RAND()の代わりになるいろいろな方法を紹介しました。自分としては思い付く方法としては以上になりますが、他に参考になるものがあれば教えて頂ければ幸いです。

追記(2013/07/10)

 コメントで頂きました。どうやら『SQLアンチパターン』に、ランダムを扱うための章があるみたいですね。実は手元にあるんですが、詰んだままでした。あとで確認します!ありがとうございます。

SQLアンチパターン

SQLアンチパターン

  • 作者: Bill Karwin,和田卓人(監訳),和田省二(監訳),児島修
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2013/01/26
  • メディア: 大型本
  • 購入: 9人 クリック: 698回
  • この商品を含むブログ (30件) を見る