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


# 概要

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

# 準備

## テーブル作成

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

```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件登録したダミーのテーブルを作成し、
単純結合を繰り返すことで件数を増やします。

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

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

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

```sql
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;
```

```sql
DROP TABLE `dummy`;
```

# 手法

## ORDER BY RAND()

伝統的な手法です。

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

1 row in set (2.99 sec)
```

```sql
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`

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

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

1 row in set (0.28 sec)
```

```sql
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をランダム生成し、内部結合することでレコードを取得します。

```sql
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)
```

```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\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で条件を変化させたものです。

```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)
```

```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\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で大量のデータを追加してみる](http://d.hatena.ne.jp/yk5656/20140202/1391910335)
* [MySQLで簡単にランダムなテストデータを作成する方法](http://qiita.com/tayasu/items/c5ddfc481d6b7cd8866d)
* [In SQL how do I get the maximum value for an integer?](http://stackoverflow.com/questions/2679064/in-sql-how-do-i-get-the-maximum-value-for-an-integer)
* SQLアンチパターン 15章 ランダムセレクション