概要

レコード数が少ない間はそれほど問題になりませんが、
レコード数が多いテーブルからランダムで取得する際、処理速度が遅くなる場合があります。
いくつか手法に関して調べてみました（ほぼSQLアンチパターンの受け売りですが…）。

準備

テーブル作成

ローカル環境で以下のようなテーブルを作り、複数の手法を試します。

CREATE TABLE `sandbox` (
    `id` INT UNSIGNED NOT NULL AUTO_INCREMENT,
    `param` INT NOT NULL,
    `content` VARCHAR(255) NOT NULL,
    `created_at` DATETIME NOT NULL,
    PRIMARY KEY (`id`)
);

レコード投入

レコード数の多いテーブルとするため、100万レコードを投入します。
レコードを10件登録したダミーのテーブルを作成し、
単純結合を繰り返すことで件数を増やします。

CREATE TABLE `dummy` (
    `id` INT UNSIGNED NOT NULL AUTO_INCREMENT,
    PRIMARY KEY(`id`)
);

INSERT INTO `dummy`
VALUES (), (), (), (), (), (), (), (), (), ();

10件のレコードを持つテーブルを6つ単純結合することで10^6（100万）件になります。
dummy テーブルは件数を稼ぐためだけに利用しており、
挿入するレコード内容は別途ランダムに設定しています。

INSERT INTO `sandbox` (`param`, `content`, `created_at`)
SELECT
    ROUND(RAND() * 100), /* 0 〜 100 */
    CONV(ROUND(RAND() * ~0), 10, 36), /* 0 〜 UNSIGNED BIGINT最大値 を36進数(0-9A-Z)に変換 */
    DATE_ADD(NOW(), INTERVAL 365 * RAND() DAY) /* 現在日時 〜 1年後 */
FROM `dummy` d1, `dummy` d2, `dummy` d3, `dummy` d4, `dummy` d5, `dummy` d6;

DROP TABLE `dummy`;

手法

ORDER BY RAND()

伝統的な手法です。

SELECT * FROM `sandbox` ORDER BY RAND() LIMIT 1;

1 row in set (2.99 sec)

EXPLAIN SELECT * FROM `sandbox` ORDER BY RAND() LIMIT 1\G

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: sandbox
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 996950
        Extra: Using temporary; Using filesort

簡潔な実装
欠番があっても取得できる
複数のレコードを取得できる
LIMITで持ってくる関係上、複数取得する場合は組み合わせに偏りが生じる
各レコード毎に RAND() を実行する必要がある
実行毎に変化するIndexを利用できない値でソートしているため、 Using temporary; Using filesort

取り出すカラム数を絞ることで多少速度が改善される様子ですが、
読み込まなければならないレコード数は依然として多いため、他の手法が望ましいかと思います。

SELECT `id` FROM `sandbox` ORDER BY RAND() LIMIT 1;

1 row in set (0.28 sec)

EXPLAIN SELECT `id` FROM `sandbox` ORDER BY RAND() LIMIT 1\G

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: sandbox
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 996950
        Extra: Using index; Using temporary; Using filesort

INNER JOIN ON id = id

取得するIDをランダム生成し、内部結合することでレコードを取得します。

SELECT s.*
FROM `sandbox` AS s
INNER JOIN (
  SELECT CEIL(RAND() * (SELECT MAX(`id`) FROM `sandbox`)) AS `id`
) AS `tmp` ON s.id = tmp.id;

1 row in set (0.00 sec)

EXPLAIN SELECT s.*
FROM `sandbox` AS s
INNER JOIN (
  SELECT CEIL(RAND() * (SELECT MAX(`id`) FROM `sandbox`)) AS `id`
) AS `tmp` ON s.id = tmp.id\G

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: <derived2>
         type: system
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1
        Extra:
*************************** 2. row ***************************
           id: 1
  select_type: PRIMARY
        table: s
         type: const
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: const
         rows: 1
        Extra:
*************************** 3. row ***************************
           id: 2
  select_type: DERIVED
        table: NULL
         type: NULL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: NULL
        Extra: No tables used
*************************** 4. row ***************************
           id: 3
  select_type: SUBQUERY
        table: NULL
         type: NULL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: NULL
        Extra: Select tables optimized away

INDEXを利用した取得
レコード数の増加に強い
欠番のないテーブルであることが前提
取得できるレコードは1件のみ

INNER JOIN ON id >= id

先述のSQLで条件を変化させたものです。

EXPLAIN SELECT s.*
FROM `sandbox` AS s
INNER JOIN (
  SELECT CEIL(RAND() * (SELECT MAX(`id`) FROM `sandbox`)) AS `id`
) AS `tmp` ON s.id >= tmp.id
ORDER BY s.id
LIMIT 1;

1 row in set (0.00 sec)

EXPLAIN SELECT s.*
FROM `sandbox` AS s
INNER JOIN (
  SELECT CEIL(RAND() * (SELECT MAX(`id`) FROM `sandbox`)) AS `id`
) AS `tmp` ON s.id >= tmp.id
ORDER BY s.id
LIMIT 1\G

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: <derived2>
         type: system
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1
        Extra:
*************************** 2. row ***************************
           id: 1
  select_type: PRIMARY
        table: s
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 498475
        Extra: Using where
*************************** 3. row ***************************
           id: 2
  select_type: DERIVED
        table: NULL
         type: NULL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: NULL
        Extra: No tables used
*************************** 4. row ***************************
           id: 3
  select_type: SUBQUERY
        table: NULL
         type: NULL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: NULL
        Extra: Select tables optimized away

欠番があっても取得できる
複数のレコードを取得できる
欠番直後のレコードが取得されやすいという偏りが生じる
LIMITで持ってくる関係上、複数取得する場合は組み合わせに偏りが生じる
WHERE句の関係上、読み込むレコード数が増える

Application

WHERE

対象テーブルのIDリストを取得してアプリ側でランダム処理を行い、
決定したIDで再度取得SQLを投げる、という手法です。

欠番があっても取得できる
複数のレコードを取得できる（WHERE IN）
比較的偏りのない取得ができる
DBに2回リクエストを投げる必要がある
件数が多いとリスト読み込みにコストがかかる

毎回IDのリストを全部引っ張ってくる点が気になりますが、
欠番の対応や偏りの軽減が必要な局面では、一考の価値がありそうです。

OFFSET

対象テーブルの行数を取得し、それを最大値とするランダムなIDを生成して
再度取得SQLを投げる、というものです。

欠番があっても取得できる
複数のレコードを取得できる
DBに2回リクエストを投げる必要がある
LIMITで持ってくる関係上、複数取得する場合は組み合わせに偏りが生じる
OFFSETが増えるほど読み込む件数が増え、コストが増加する

もし欠番がないのであれば、LIMIT OFFSET よりも BETWEEN で
Indexを用いた検索にする方が良さそうです。

まとめ

基本的には、Indexを用いた検索になるよう落とし込むと良さそうです。
それぞれの手法には長所・短所がありますが、
判断のために以下のような要望・状況を確認します。

対象テーブルの規模感は？
対象テーブルは欠番が存在するのか？
取得件数は？
多少偏りが生じても許容できるのか？

これらを踏まえて、最適な手法を採用するのが良さそうです。

参考

MySQLで大量のデータを追加してみる
MySQLで簡単にランダムなテストデータを作成する方法
In SQL how do I get the maximum value for an integer?
SQLアンチパターン 15章ランダムセレクション

MySQLでランダムにレコードを取得する場合の手法

概要

準備