業務で主に Ruby On Rails での開発を行っていますが、そこで得た知見や、失敗への対応などについて記します。
# 環境
Ruby 2.6.6
Rails 5.2.4.3
Postgres 10.10
状況と現状
状況と要件は以下の通りです。
- あるDBテーブル(ここでは
Item)に、数十万件のレコードがある - そのうちの 10件をランダムに選びたい
単純な実装としては「SQL の RANDOM() でソートして最初の 10件を取り出す」になります。
# Rails の ActiveRecord を利用
Item.order(Arel.sql('RANDOM()')).limit(10)
これを試しに実行すると、以下のように 1000ms ほどの時間がかかります。
Item Load (1029.2ms) SELECT "items".* FROM "items" ORDER BY RANDOM() LIMIT 10;
これは、この処理が以下のように動作しているからです。
- 全てのレコードをランダムに並び替えてしまっている
- そのうち上位10件だけを取得している(11件目以降の並び替えは無駄になってしまう)
これをもっと効率よくしたい場合は、どうするのが良いでしょうか。
対応案の候補
このような状況については、書籍「 SQLアンチパターン 」の第15章の「ランダムセレクション」という項目で、幾つかの解決策が示されています。
ただ、書籍でのこの部分の記述はおもに「1レコードを取り出す」ことを主目的に書かれているので、今回のように「複数行取得」「レコード数が多い」の場合には、幾つかの検討が必要に感じました。
以下、書籍に載っている 5つの解決策と、今回の場合との比較を書きますが、詳しくは書籍を参照ください。
| # | 書籍での解決策 | 今回のように「複数行取得」「レコード数が多い」の場合 |
|---|---|---|
| 1 | 1と最大値の間のランダムなキー値を選択する | 欠番が無い場合に利用可能(下の 対応案A) |
| 2 | 欠番の穴の後にあるキー値を選択する | 複数行取得の場合は難しい |
| 3 | すべてのキー値のリストを受けとり、ランダムに 1つを選択する | レコード数が多すぎる場合は難しい |
| 4 | オフセットを用いてランダムに行を選択する | 複数行取得の場合は難しい |
| 5 | ベンダー依存の解決策 |
TABLESAMPLEが使える可能性が有る(後述の 対応案B) |
なお、この記事の末尾には、これらのいずれでもない「あらかじめレコードを絞ってからランダムに選ぶ」方法についても記します(対応案C)。
(対応案A) あらかじめアプリケーション側でランダムに対象の id を選ぶ
最も簡単なのは「レコードの id には欠番が無い」という場合で、その場合は単純に「idの中から10個選ぶ」ことが出来ます
# 最初の呼び出しに 100ms ほどかかり、次回以降は 1ms ほどになるが、
# アプリケーション側でキャッシュしておくのが良い
maximum_id = Item.maximum(:id)
# rand(limit) は 0..(limit - 1) が選ばれるので、 1..limit になるように succ する
Item.where(id: 10.times.map { rand(maximum_id).succ })
つまり「アプリケーション側で idだけをランダムに選ぶ」ことになりますが、並び替えが不要な分、十分な速さが得られます。
この対応案の利点
- 処理速度が非常に速くなる(レコード取り出し部分に限ると、1000ms が 10ms になるので、約100倍の効率化)
- 真にランダムに選ばれる(選ばれた結果の制約が無い)
- レコードの「関連づけ」が複雑でも問題が生じない
- レコードの数が多くなっても抽出速度に影響しない
この対応案の欠点
- idは欠番が無いことが必須になる(が、その場合の取り得る策については後述)
- 条件付けで半分以下に対象レコードを絞っている場合には難しい(省く手間が多くなる)
- もし「ランダムに同じidを引き当ててしまった」場合は、その分の抽出件数が減る
この対応案のさらなる検討
- 「欠番が無いことが必須」という制約は、もし要件を「稀に10件未満になっても構わない」と緩和出来れば、欠番が有ったままでもこの方法で対応出来る。
ただしその場合、全体に対する欠番の比率を元に「最悪の場合だと何件しか選ばれないことが生じるのか」の割合をあらかじめ見積もる方が良い。 - またさらに「欠番を含む」あるいは「同じidを引き当ててしまう」ことを見越して、「あらかじめ数件多い目に取得して、そのうち必要分だけをさらに絞る」という方法も考えられます。
ほとんどの場合に数件の無駄な取得が増えるのと、絞る時にランダムにすることでの時間がかかることになるが、「なるべく指定件数分を選びたい」場合にはこの方法が採れます。
よって、この対応案の結論としては「 欠番が無い状態であれば、取得は最速になる 」になります。
(対応案B) SQL の TABLESAMPLE 句を使用する
TABLESAMPLE については以下などで紹介/説明されています。
- データベースのランダム読み出しは要注意(翻訳)|TechRacho(テックラッチョ)〜エンジニアの「?」を「!」に〜|BPS株式会社
- PostgreSQL 9.5のTABLESAMPLE句 - Qiita
- PostgreSQL 10.5文書 SQLコマンド SELECT
TABLESAMPLE 句は引数として「サンプリングする割合を0から100までのパーセント」を指定出来るので、ここでは最低限の 1 を指定してから、そこから 10件選ぶ、という形になります。
Item.unscoped.from('items TABLESAMPLE BERNOULLI(1)').order(Arel.sql('RANDOM()')).limit(10)
結果は以下の通りです
Item Load (140.1ms) SELECT "items".* FROM items TABLESAMPLE BERNOULLI(1) ORDER BY RANDOM() LIMIT
ただこの方法は、レコードの「関連づけ」が複雑で、includes を多様している場合に FROM句が上手く設定出来ない状況が起こるようです。
(それぞれの「関連づけ」の設定に依存するので、ご自身の環境でお確かめください)
この対応案の利点
- 処理速度が相応に速くなる(1000ms が 140ms になるので、約7倍の効率化)
- 真にランダムに選ばれる(選ばれた結果の制約が無い)
- idに欠番があっても構わない
- 条件付けで半分以下に対象レコードを絞っている場合でも構わない
- 少なくとも抽出件数の 100倍以上のレコードがあれば、抽出件数が減ってしまう恐れが無い
この対応案の欠点
- 「関連づけ」が複雑な場合に対応しきれない可能性が有る
- 1/100までしか絞り込めないので、レコード数が多い場合にリニアに時間が増える
この対応案のさらなる検討
-
TABLESAMPLEには例示したBERNOULLI以外にもSYSTEMの指定が可能で、これは「ブロックレベルのサンプリング」を行うので、サンプリング結果が偏ることになりますが、レコード数が十分に有る場合は、その中からさらに10件を抽出することで、ある程度のランダム性を確保出来ます。
こちらの方が原理的には「速く動作する」はずですが、手元で試した限りではBERNOULLIとさほど相違はありませんでした。
レコード数が多過ぎで、1/100に絞った後の並び替えの方が重い処理になっているからだと推測されます
よって、この対応案の結論としては「 欠番がある状態で、かつ、常に真にランダムに選ぶ場合に良い 」になります。
(対応案C) あらかじめ id 単位で候補を絞る
「10件をランダムに」の要件をやや緩和して、「ある程度の偏りは構わない」場合、あらかじめ id 単位で候補を絞る方法が有ります。
これはまず、以下のような「IDの末尾8ビット分」のインデックスを新たに追加します。
create_table :items do |table|
# 255 は 16進数で `0xFF` で、末尾 8ビット分を示す。 `&` よってビットマスクを取っている
# 関数でのインデックスを付与する場合は、二重の括弧が必要
table.index '((id & 255))', name: :index_items_on_remaining_id
end
そして、呼び出し時に「あらかじめ対象をランダムに 1/256に絞る」ようにします
Item.where('(id & 255) = ?', rand(256)).order(Arel.sql('RANDOM()')).limit(10)
結果は以下の通りです
Item Load (23.8ms) SELECT "items".* FROM "items" WHERE ((id & 255) = 133) ORDER BY RANDOM() LIMIT 10;
この場合、以下のように動作をしていることになります。
- まず、レコード全体から「IDを256で割った数の余りが、指定されたランダム値」のものだけを選ぶ
- そのレコードをランダムに並び替え、上位10件を取得する
この対応の利点
- 処理速度がかなり速くなる(1000ms が 25ms になるので、約40倍の効率化)
- 「関連づけ」が複雑な場合にも対応出来る
- idに欠番があっても構わない
- レコード数が多い場合にもインデックスを変えれば対応可能(後述)
- 条件付けで半分以下に対象レコードを絞っている場合でも構わない
- その値が選ばれても最低限、必要な数が得られるようになっていれば、抽出件数が減ってしまう恐れが無い
この対応案の欠点
- 真のランダムでは無く、一度に選ばれるレコードの
idが規定されてしまっている(idを定数で割った数に限られる)
この対応案のさらなる検討
- レコード数が多い場合は、「下位8ビットでマスク」としているのを、たとえば「12ビットでマスク」としたりすることで調整可能になる。
よって、この対応案の結論としては「 欠番がある状態で、かつ、常に真にランダムではなくても構わない場合に良い 」になります。
まとめ
これまでの案を比較すると、以下のようになりますが、
あくまでそれぞれの環境やDBテーブルの構成や件数に依存します。
| # | 各方法案 | 効率 | 欠番への対応 | ランダム性 | 複雑な関連づけ | レコード数の多さ | 対象が半分以下 | 抽出件数確保 |
|---|---|---|---|---|---|---|---|---|
| A | IDをランダムに | ◎ | ×※ | ◎ | ○ | ◎ | × | △ |
| B | TABLESAMPLEを利用 | △ | ○ | ◎ | △ | × | ○ | ○ |
| C | IDをあらかじめ絞る | ○ | ○ | △ | ○ | ○ | ○ | ○ |
-
※当該の方法案の「さらなる検討」に書きましたように、対処する方法は幾つか考えられます
それぞれの環境や構成、レコード件数毎に最適な方法を見つけるのが良いと思われます。