MySQL

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


概要

レコード数が少ない間はそれほど問題になりませんが、

レコード数が多いテーブルからランダムで取得する際、処理速度が遅くなる場合があります。

いくつか手法に関して調べてみました(ほぼ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を用いた検索になるよう落とし込むと良さそうです。

それぞれの手法には長所・短所がありますが、

判断のために以下のような要望・状況を確認します。


  • 対象テーブルの規模感は?

  • 対象テーブルは欠番が存在するのか?

  • 取得件数は?

  • 多少偏りが生じても許容できるのか?

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


参考