SQLアンチパターン読書会 「ランダムセレクション」に参加しました

2014/2/27(木) SQLアンチパターン読書会 「ランダムセレクション」に参加してきました。

DoorKeeper
http://sqlap.doorkeeper.jp/events/9180

以下の書籍をターゲットとした読書会なのです。

SQLアンチパターン (2013/01/26) Bill Karwin 商品詳細を見る

場所はいつもの湯島、株式会社アルティネットさんです。
いつも会場提供ありがとうございます。

参加者は9人かな。
この日は @yokatsuki さんからどらやきの差し入れが！美味しかった～

今回は15章「ランダムセレクション」が対象範囲でした。

---

■15章「ランダムセレクション」の説明
今回は主催の @natsu_nanana さんがスライドを作成して紹介してくださいました。

SQLアンチパターン読書会 15章 ランダムセレクション 説明資料 from Nao Yamamoto

図を上手く使ってわかりやすく纏めた資料です。
15.5.4節のオフセットについて質問して、疑問も解決できました。

---

■ディスカッション
今回もディスカッションしたいネタをみんなで付箋に書き出しました。


以下、ディスカッション時の個人メモ。
---

■15.5.4節「オフセットを用いてランダムに行を選択する」
・OFFSET句は、ヒット件数のうち何番目を取ってくるかを指定するので、この方法は欠番があっても正しく動作する。
・Oracle Database 12cからfetch構文（FETCH FIRST n ROWS ONLY）が使えるようになった。
　- Oracle Database 12cリリース1 (12.1)の新機能： 問合せの行制限と行オフセットのネイティブSQLでのサポート
　- Oracle Database SQL言語リファレンス 12cリリース1 (12.1) 「row_limiting_clause： 行制限の例」
・SQL Serverだと、TOP句とPERCENT句を使用することで、結果セットの件数をパーセンテージで制限できる。


■ランダム性
・人間が感じるランダム性とSQLのランダム性は違う。
・WEB+DB PRESSの増井さんの記事　「10000件くらいだと均等に感じるが、100件くらいだと偏りがあるよね」
・@t_wada さんの知り合いの @kagamihoge さんが、ランダム性に関する記事を書いている。
　- kagamihogeの日記 「OracleのSAMPLE句によるランダムセレクションのばらつきを調べる」
　　→ 後半の行にいけばいくほど出現頻度が下がっていく、とのと興味深い調査結果が示されている。
　- kagamihogeの日記 「Oracleのdbms_random.valueで1とmaxの間によるランダムセレクションのばらつきを調べる」
　　→　DBMS_RANDOMパッケージのVALUEファンクションを使うと均等な結果が得られた、との調査結果。
・そもそもランダムって何？
　→　乱数であることの証明は数学的にできないらしい。乱数を定義するとそこで自己矛盾が起きてしまう。
　→　そのため乱数は正式には「疑似乱数」と言う。
・きしださんが「きしだのはてな」というブログで乱数について書いている。
　http://d.hatena.ne.jp/nowokay/20081110/1226302607
　- Javaには「java.util.Random」と「java.security.SecureRandom」という2種類のクラスがある。
　- 前者は偏りがあり、後者はちゃんとばらつく結果が得られた。
　- 統計用などでまともに乱数を使うには Mersenne Twister を使いましょう。


■15.2節「ORDER BY RAND()」
・この構文の意味が分からない、こんなんできたんだ初めて知ったわ、というご意見がチラホラ。私も！
・すべての行に対して乱数を振って、その乱数値を基準にソートする動作になるっぽい？
　→　すべての行に対して乱数が振られ、当然ソート時にインデックスも効かないので性能は極端に悪い。
　（参考） esehara / gist:5925390 「ORDER BY RAND() 使うな」
・「SQL ランダム」でググるとたくさんヒットする。これは発見だった。みんな悩んでるんだな…
・「ORDER BY RAND()の性能が悪いのはSELECT句に*を指定しているためで、*ではなくカラムを指定すると速くなる」という見解がよく見られる。
　→　それは単純にカラム数の違いからくる話である。*がランダムソートが遅い直接の原因ではない。
・伊藤直也氏もブログで order by rand()について言及していた。
　- naoyaのはてなダイアリー： MySQL の order by rand()
　- ブログのコメント欄にある「order by rand()を使ったらいいんじゃないか会議」とは・・・
・"ORDER BY RAND()"のGoogleのヒット優先度を下げたい！
・このパターンを見たら「SQLアンチパターンを読め！」と言いたい。
・SQL Serverにはランダムにデータを抽出したい場合のために NEWID() という組み込み関数が用意されている。
　→　固定長の重複しないUUID（Universally Unique Identifier）が割り振られる。
・闇が深いよね・・・
・Order By Randなんて、フツーは思いつかないよね・・・


■15.5節　解決策
・乱数生成の解決策には、厳密さと速さのバランスがある。
・例えば40件から1件を選ぶくらいじゃ、厳密さはあまり要求されない。
・それに対して金銭が絡むシステムなどは、説明責任があるのでアルゴリズムを開示しないといけない。
・15.5.2節で欠番がある場合の解決策が紹介されているが、「欠番がある ＝ 物理削除している」ということ。
・これがもし論理削除でやっていたら、更に闇になるｗ
・ちなみに「論理削除」はアンチパターンとして書籍に入れたかった・・・
・欠番だったらもう一度リトライ検索する、というロジックもコンテキストによっては解決策になる。
　→　欠番が多いとリトライ検索が多くなるので使えないが、欠番が十分少ないなら実用できる。
・ランダムに40個の数値を取ってくる要件には、この本の解決案が使えないやつがある。
　→　一本釣り系やLimit Offsetは使えなかったりする。


■乱数の生成
・確率に重みを付けたい場合、人間が感じるランダムは複雑なロジックになることが多いので、SQLではなくプログラミング側で実現したほうが良い。
・15.5.3節のようにSQLを2回投げる場合は、トランザクションに注意する必要がある。
　→　ロックをかけるか、同時アクセスが万が一あった場合はしゃあないと諦めるか、などの戦略は、トランザクション分離レベルとか業務要件とかを考慮して決める必要がある。
・オンラインゲームのガチャを実現するには、先に抽選の当選リストを作ってしまう方法もある。
・乱数生成をDB側に寄せる場合は以下が考えられる。
　- APサーバが貧弱な場合。（一般に、DBサーバはCPUもメモリもAPサーバより潤沢）
　- DBからランダム値を取ってこないといけないアプリがたくさんある場合。
　- 件数が多い場合。
　- DBでなんでもやろうとしている会社の場合。
　- アーキテクチャがC/Sの場合。（クラサバ時代はこの発想が多かったかもしれない）
・DBの方がアプリより寿命が長いので、使用するロジックは寿命の長いDB側に寄せておきたいという考えもある。

---

★感想：
ランダムセレクションなんてやる奴ホントおるんか・・・？
な～んて最初は思ってたんですが、この日のディスカッションで思いのほか多くの人が悩んでいるのだなぁ、と驚きました。
いろいろ闇が深いようで・・・
あと、LIMITやFETCHやら、ベンダ依存も多いですね。
このへんは、どのDBMSを使っているかで解決策も分かれそうです。
とりあえず、乱数が必要になったらSQLアンチパターンを読み返すようにしよう。

参加者のみなさま、ありがとうございました～

---

■おまけ：過去の「SQLアンチパターン読書会」ブログ

1章：SQLアンチパターン読書会 「ジェイウォーク」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-65.html

2章：SQLアンチパターン読書会 「ナイーブツリー」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-70.html

3章：SQLアンチパターン読書会 「IDリクワイアド」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-73.html

3章：SQLアンチパターン読書会 「続・IDリクワイアド」 に参加しました
　http://makopi23.blog.fc2.com/blog-entry-77.html

4章；SQLアンチパターン読書会 「キーレスエントリー」 に参加しました
　http://makopi23.blog.fc2.com/blog-entry-84.html

5章：SQLアンチパターン読書会 「EAV(エンティティ・アトリビュート・バリュー)」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-90.html

6章：SQLアンチパターン読書会 「ポリモーフィック関連」 に参加しました
　http://makopi23.blog.fc2.com/blog-entry-94.html

7章：SQLアンチパターン読書会 「マルチカラムアトリビュート」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-97.html

8章：SQLアンチパターン読書会 「メタデータトリブル」 に参加しました
　http://makopi23.blog.fc2.com/blog-entry-105.html

9章：SQLアンチパターン読書会 「ラウンディングエラー」 に参加しました
　http://makopi23.blog.fc2.com/blog-entry-109.html

10章：SQLアンチパターン読書会 「サーティーワンフレーバー」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-115.html

11章：SQLアンチパターン読書会 「ファントムファイル」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-118.html

12章：SQLアンチパターン読書会 「インデックスショットガン」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-121.html

13章：SQLアンチパターン読書会 「フィア・オブ・ジ・アンノウン」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-128.html

14章：SQLアンチパターン読書会 「アンビギュアスグループ」に参加しました
　http://makopi23.blog.fc2.com/blog-entry-130.html