ランダムセレクション

ランダムな結果を返すソートを使用するとパフォーマンスが低下するというアンチパターン。

目的：サンプル行をフェッチする

大量のデータセットからランダムに結果を抽出したい。
使用する場面として以下のような場面が想定されます、

複数の広告からランダムで数件選択されるニュースの広告
おみくじやくじ引きのような複数の選択肢からランダムに結果を返す場合

アンチパターン：データをランダムにソートする

SQLでランダムな行を取得する方法として一般的な方法として、RAND()を用いてソートを行い、最初の行を取得する方法があげられる。

ランダムソート

SELECT * FROM Users ORDER BY RAND() LIMIT 1;

昇順、降順のソートとの違いについて比較する。
昇順、降順のソートでは値の大きさによって行を並び替え、２回以上同じクエリを発行しても結果は同じとなる。

以下の方法であればインデックスのメリットも得ることができる。

昇順、降順ソート

-- 昇順ソート
SELECT * FROM Users ORDER BY user_id ASC;

-- 降順ソート
SELECT * FROM Users ORDER BY user_id DESC;

ランダムにソートをかける場合は値の大小に関わらず行はランダムにソートされ、順番はソートをかけるごとに変わる。
RAND()ではインデックスのメリットを受けることができない。

インデックスの活用はソートを高速化する手段の１つ。
インデックスを使用できない場合、テーブルスキャンを用いるためパフォーマンスの低下につながる。

稼働期間が長くなった場合など、データが増えるにつれ問題が出てくる場合がある。

アンチパターンを用いても良い場合

データセットが小さい場合。
47都道府県からランダムに１つ選択する場合など、サイズが大きくなく件数が増えていく可能性が低い場合。

解決策：特定の順番に依存しない

ランダムなソートを使用したクエリではテーブルスキャンが発生してインデックスを使えない高コストなソートが行われる。

１と最大値の間のランダムなキーを選択する

解決策1

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

１から主キーの最大値までの間の値をランダムに選択する。

主キーが１から開始されていること
１から最大値までに欠番がないこと
全ての値が使用されていることが確実な場合

欠番の穴の後にあるキー値を選択する

解決策2

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

１から主キーの最大値までの間に欠番があり、かつ乱数によって欠番キーが算出されてしまう場合。

乱数に一致するキー値がない場合でも算出できる
欠番キーの１つ上のキー値が産出される可能性が高い
欠番の行が少ない場合やキー値が均等に選ばれることが重要ではない場合

全てのキー値のリストを受け取り、ランダムに１つ選択する

アプリケーションからデータセットの主キーを全て取得し、ランダムにキー値を選択。
ランダムで取得した主キーで該当の行全体を再度取得する。

解決策3

-- アプリ側から以下のようなクエリでキーリストを取得
SELECT user_id FROM Users;

-- アプリケーション側で上記リストから乱数を取得
-- 言語によって処理方法が変わるため処理は省略

-- リストから取得した乱数で行全体を取得するクエリ
SELECT * FROM Users WHERE user_id = 乱数;

※言語などによって方法が異なるためクエリのみサンプルを記載。

テーブル全体のソートを回避でき、テーブルスキャンの必要がない
各キー値が均等に選択される
データベースから全てのキーを取得するとリストが大きくなりすぎる可能性がある
１回目はリストを取得、２回目は選択したキーで行の取得と２回クエリを実行する必要がある

オフセットを用いてランダムに行を選択する

データセットの行数をカウントし、０と行数までの間の乱数を返す方法。

解決策4

-- アプリ側から以下のようなクエリで乱数を取得
SELECT FLOOR(RAND() * (SELECT COUNT(*) FROM Users));

-- 言語によって処理方法が変わるため処理は省略

-- 取得した乱数で行全体を取得するクエリ
SELECT * FROM Users LIMIT 1 OFFSET 乱数;

※言語などによって方法が異なるためクエリのみサンプルを記載。

キー値が連続していることを前提としない場合
各行が均等に選択される必要がある場合
キーリスト全体を取得する必要がない
複数件の取得だとクエリの発行回数が増加

まとめ

クエリには最適化できないものもあります。最適化できない場合は、別のアプローチを考えましょう。

参考文献

SQLアンチパターン

SQLアンチパターン ランダムセレクション