Help us understand the problem. What is going on with this article?

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

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

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

参考

iri
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした