Random Selection

Some queries cannot be optimized: take a different approach.

• ランダムに並べ替えて1件取得
• テーブルのレコード数が増えたら遅くなった

Objective: Fetch a Sample Row

• 再現性・決定性の原理原則からは外れる

• が、要求されることは多い

  • 広告等のランダム表示
  • 一部のレコードを監査
  • 空いているオペレーターの誰かに仕事をアサイン
  • テストデータの生成
• 全行取得してアプリケーション側で乱択することはしたくない

Antipattern: Sort Data Randomly

• ORDER BY RAND() LIMIT 1とかやっちゃう

• スケールしない

  • 1行しか使わないのに全行並べ替え
  • 毎回結果が異なるのでキャッシュが効かない
  • インデックス効かないのでテーブルスキャン

  • B+木インデックス効かないのでソート必要

    • ファイルソート
• テスト時の小規模データでは気づかない

How to Recognize the Antipattern

• こんなのが聞こえてきたら、その人は本アンチパターンを踏んでいる

  • 「SQLでは、ランダムな行を返すのはとても遅い」

  • 「アプリケーションのメモリを増やするはどうすればいい？全行取得して1行乱択したい」

    • 超ムダ
    • DBの全データは、アプリケーションでは手に負えない大きさになりがち

  • 「出現頻度が均一じゃない」

    • 主キーに欠番があるケースでChoose Next Higher Key Valueを適用している(後述)

Legitimate Uses of the Antipattern

• データが少ない

• システムのライフタイム通じて増えない

  • 合衆国の州とか

Solution: In No Particular Order…

• ランダム値でソートするアプローチでは最適化できないので考え方を変える

Choose a Random Key Value Between 1 and MAX

• 主キー(連番)が1~N、欠番なしという前提

SELECT b1.*
  FROM Bugs b1
 INNER JOIN (SELECT CEIL(RAND() * (SELECT MAX(bug_id) FROM Bugs)) AS rand_id) b2
    ON b1.bug_id = b2.rand_id

Choose Next Higher Key Value

• 欠番がある場合

SELECT b1.*
  FROM Bugs b1
 INNER JOIN (SELECT CEIL(RAND() * (SELECT MAX(bug_id) FROM Bugs)) AS rand_id) b2
 WHERE b1.big_id >= b2.bug_id
 ORDER BY b1.bug_id
 LIMIT 1;

• 欠番の次を見に行く
• 分布は均一でなくなる

Get a List of All Key Values, Choose One at Random

• PK全取得して、アプリケーション側で乱択する

• メリット

  • 欠番があっても分布均一

• デメリット

  • レコード数によってはメモリを使い果たしてしまう

  • 2クエリ発行しなければならない

    • PK全取得
    • PKでレコード指定

Choose a Random Row Using an Offset

• LIMIT 1 OFFSET {乱数}
• ROW_NUMBER()ウィンドウ関数とWHERE row_num = {乱数}

Proprietary Solutions

• 製品によっては専用の関数が用意されている

  • Microsoft SQL Server 2005

    • TABLESAMPLE (1 ROWS)句

  • Oracle

    • SAMPLE (1)句

英語

• on the lookout for

  • … に目を光らせて