概要
レコード数が少ない間はそれほど問題になりませんが、
レコード数が多いテーブルからランダムで取得する際、処理速度が遅くなる場合があります。
いくつか手法に関して調べてみました（ほぼ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章 ランダムセレクション