質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.34%

  • MariaDB

    407questions

    MariaDBは、MySQL派生のオープンソースなリレーショナルデータベースシステムです。 また、MySQLとほぼ同じデータベースエンジンに対応しています。

ORDER BY RAND(); が遅い

受付中

回答 5

投稿 編集

  • 評価
  • クリップ 4
  • VIEW 2,447

aglkjggg

score 740

 質問

タイトルの通りなのですが、
MariaDBにおいてORDER BY RAND()が非常に遅いため改善を試みましたが、
上手くいかなかった為、
「どうすれば結果取得までの時間を短縮し、CPU使用率を低くできるか」を質問させてください。

 やりたいこと

accountsテーブルからランダムに10個nameを取得したい。

条件

  • del_flgが0のみ取得。
  • creation_timeが毎日AM 00:00より前のものを取得

※クエリは多くて1秒間に10回程度実行される場合があります。

 試したこと

 その1

処理時間 11.469秒
非常に重い。
DBサーバのCPU使用率が跳ね上がるため利用できない。

SELECT
  name
FROM
  accounts
WHERE
  del_flg = 0 AND
  creation_time < '2016/10/29 00:00'
ORDER BY
  RAND()
LIMIT 10;
 その2

こちらを参考にしてSQLを変更しました。
処理時間 28.422秒
悪化しました。

SELECT
  name
FROM
  accounts AS tbl,
  (
    SELECT
      id
    FROM
      accounts
    WHERE
      del_flg = 0 AND
      creation_time < '2016/10/29 00:00'
    ORDER BY
      RAND()
    LIMIT 10
  ) AS tmp_tbl
WHERE
  tbl.id = tmp_tbl.id;
 その3

こちらを参考にしました。
処理時間 0.015秒
INNER JOIN ON id >= idと書かれている項目のものを利用してSQLを作りました。
しかし、user_idがほぼ乱数に近い飛び飛びな値(700,000,000~999,999,999でランダム)の為、
SELECT CEIL(RAND() * (SELECT MAX(`user_id`) FROM `accounts`))
で得られる結果は700,000,000以上になることはほぼ無く、
ランダム性能が悪く使い物になりませんでした。
何十回実行しても連続で結果が同じ場合がありました。

SQLは省略します。

 その4

WHEREの条件がマズいので、場合によっては10件以下が取得される場合があります。
10件以下を取得してしまう可能性があるので使えませんが、自分が色々試した中で最速でした。
処理時間 1.328秒

SELECT
  name
FROM
  accounts,
  (SELECT id FROM accounts ORDER BY RAND() LIMIT 10) AS tmp_tbl
WHERE
  accounts.creation_time < '2016/10/29 00:00' AND
  accounts.del_flg = 0 AND
  accounts.id = tmp_tbl.id;

 対象テーブル

  • データ数300万件(随時増えています)
  • user_idは値が飛び飛び(700,000,000~999,999,999でランダム)
  • nameはユーザー名
  • del_flgは0が削除されていない。1が削除済み。
  • creation_timeaccountsテーブルにデータが挿入された日時
CREATE TABLE `accounts` (
  `user_id` INT(11) NOT NULL,
  `name` VARCHAR(36) NOT NULL,
  `del_flg` TINYINT(1) NOT NULL DEFAULT '0',
  `creation_time` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`user_id`),
  INDEX `name` (`name`),
  INDEX `del_flg` (`del_flg`),
  INDEX `creation_time` (`creation_time`)
)
COLLATE='utf8_general_ci'
ENGINE=InnoDB;

 DBサーバ

  • CentOS 7.2.1511
  • MariaDB Version 15.1
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

0

creation_time, del_flg, id で一つのインデックスを作って今までのSQLと比べてみては?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/10/30 11:37 編集

    > aglkjgggさん
    本質を知るという意味ではBtreeのB+ treeの勉強すると良さ気ですが、そこまで身構える必要もないかなとも思います。
    当方も学問的な所は割とさっぱりですし(

    要は検索時にどういったパターンの検索・取得が多いのか、これが分かってくれば適切なインデックスの張り方が見えてきます。
    (後おまけにGROUP BYやORDER BYさらる項目にも着目すると良さ気。SQLはソート処理が意外に負荷が高かったりするのでインデックスを使わせてソートをスキップという芸当も場合によっては可能です。)

    一番絞り込めるものを先頭にというのも、
    その条件がほとんどの場合は1番の検索条件に入ってくる可能性が高い、という意味で上げせてもらってます。

    キャンセル

  • 2016/10/31 10:35

    しばらくアクセスしない内に議論が進んでいますね。わたしにも参考になります。わたしは普段億単位のデータを扱うことが少なくないので、300万件程度の少ないデータでのレスポンスとしてはかなり遅いなぁ、って印象があります。必要なレスポンスに見合うハードウェアを用意することも考えられてはどうでしょうか?
    SELECTには影響は少ないですが、需要の少ないインデックスは削除することでINSERT, UPDATE, DELETE の負担が減るので全体のパフォーマンスの改善が期待できます。
    以前、Oracleでパフォーマンス・チューニングを依頼されたお客様でボトルネックになっているテーブルでインデックスが20個以上設定されていて開いた口が塞がらなかったことも。

    キャンセル

  • 2016/11/02 21:52

    > Orlofskyさん
    俗に言うインデックスショットガンってやつですね。

    インデックスはあればあるほど良いわけでは当然ないので、
    以下に少数のインデックスで、多くのクエリの検索パターンを高速化(アスセスパスを網羅)させることができるか。

    そこが設計者の腕の見せ所なんでしょうね・・・

    キャンセル

0

「その3」を改変して、

SELECT CEIL((SELECT MIN(`user_id`)) + RAND() * (SELECT MAX(`user_id`) - MINB(`user_id`) FROM `accounts`))

のようにしてみてはどうでしょうか(値のつまり具合で、均等にならないことは間違いないですが、MIN以下を拾うというのは避けられます)。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/10/30 06:49 編集

    ご回答ありがとうございます。

    書いていただいたSQLを参考にしたところ、
    「INが正しく取れてないため全く同じ結果を取得してしまっていた問題」を回避けることができました。

    ただ、やはり ランダム性の心配や
    ORDER BYで指定した並びでの結果取得となるので
    (指定しなければuser_id(プライマリキー)の昇順)
    他に手がない場合に利用させていただきます。

    キャンセル

0

del_flgcreation_timeに複合インデックスが張ってあるという前提で、
以下のようなクエリではいかがでしょうか?

SELECT @rate := ((10 * 1.00000000000) * 2) / COUNT(*) # 余裕を持たせるため、2倍のレートを設定する
FROM accounts
WHERE del_flg = 0
  AND creation_time < CURDATE();

SELECT * FROM (
  SELECT name
  FROM accounts
  WHERE del_flg = 0
    AND creation_time < CURDATE()
    AND RAND() <= @rate
) AS tmp
ORDER BY RAND()
LIMIT 10;


このクエリが何をしているかというと、

  • まず、1つ目のSQL文で@rate * "条件"を満たすレコードの件数 = 20を満たす数値@rateを求め(※)、
  • 2つ目のSQL文のサブクエリ内で、
    "条件"を満たすレコードをRAND() <= @rateによって約20件に絞り込み、
  • それを2つ目のSQL文のサブクエリの外側でランダムに並べ替え、さらに10件に絞り込む

というわけです。
※ @rateユーザー定義変数というものです。

@rateはリアルタイムに求める必要はない上に正確な数値である必要もないので、
例えば日次のバッチ処理で計算した値を別のテーブルに格納しておくなどすれば、さらに速度の改善が見込めます。

ただし、この方法には以下の欠点があります。

  • 確実に10件、取得できるとは限らない。
    -> 取得した行数をチェックし、10件に満たなければ 2つ目のSQL文をもう一度実行する、などで対処してください。
    もっとも、"条件"を満たすレコードの件数が十分に多ければ、滅多に起きることはないと思いますが。
  • "条件"を満たすレコードの件数が極端に多くなると@rateが 0 に丸められてしまい、
    10件に満たない件数しか取得できない可能性が高くなる。
    -> プライマリーキーであるuser_idの型が INT(11) である限りは、問題ないはずです。
    MariaDBの符号付き INT型の最大値は 2147483647 で、私の手元の環境(MySQL5.7)で確認した限りでは
    (10 * 1.00000000000) * 2 / 2147483647 = 0.000000009313226
    となり、0 に丸められることはなかったからです。

ご参考までに。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/10/30 07:52

    ご回答ありがとうございます。

    計算済みの@rateを別テーブルに保存した状態で、
    del_flgとcreation_timeに複合インデックスをつけた状態で試した結果、
    3.125秒となりました。

    また、本筋とは少しズレますが、
    CAST(x AS double)などを使わなくても、
    1.00000000・・・などとすれば有効桁数を任意のものに指定できるのですね。

    解説付きで非常に勉強なりました。

    キャンセル

  • 2016/10/30 15:41

    返信ありがとうございます。

    3秒かかってしまいましたか…

    何か他の良い方法を思いつきましたら、回答に追記させていただきますね。

    キャンセル

0

英語サイトで申し訳ないですが、
こちらの「Order By Rand() Alternative Method」の項のSQLはどうでしょうか。

要件を満たす速度になるかは分かりませんが、
普通のORDER BY RAND()よりは速く動作するかも?

SELECT
    name
FROM
    accounts
WHERE
    del_flg = 0
AND creation_time < '2016/10/29 00:00'
AND RAND() < (SELECT (10 / COUNT(*)) * 10) FROM accounts WHERE del_flg = 0 AND creation_time < '2016/10/29 00:00') 
ORDER BY
    RAND()
LIMIT
    10

これプラスαでdel_flg、create_time、nameに対して複合インデックスを定義すると尚良さそう。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/11/02 20:22

    > aglkjgggさん
    当方の想定してた実行計画と違う結果が返ってきてますね。
    DERIVEDになるかなと想定してたんですが・・・^^;

    SELECT 〜
    FROM accounts
    INNER JOIN (SELECT (10 / COUNT(*)) * 10) AS rate FROM accounts WHERE del_flg = 0 AND creation_time < '2016/10/29 00:00') tmp
    ON RAND() < tmp.rate

    みたいな感じでダメだったっことですよね?

    ともあれRANDによるソートはどうしても重いのは間違いないので、
    例えば取得開始位置はランダムだけど、
    そこから連続した10個のアカウント名が取れても問題ないとかであれば、
    アプリ側で2回クエリ発行しても少し高速化は出来そうな気はします。

    キャンセル

  • 2016/11/02 20:32

    すみません。言葉足らずでした。
    実行計画では3行表示されていました。
    PRIMARY, PARIMARY, DERIVEDでした。
    https://gist.github.com/anonymous/5f67d3f22a37a693c858204f1752ff2c

    書いていただいたクエリと同じものを実行しています。

    クエリだけではどうしようもなさそうなので、
    じっくり他の方法を探りたいと思います。。。

    キャンセル

  • 2016/11/02 21:47

    > aglkjgggさん
    なるほど、了解です。

    プログラム側でレコード数から比率を取得するクエリと、
    比率からランダムに取得するクエリを2本キックする方が早いかもしれないですね。

    1発目は時間かかりそうですが、2発目以降はプリペアドステートメントか何かで実行計画自体をキャッシュさせるなりして高速化出来るかもですし・・・

    キャンセル

0

もう解決されてるかもしれませんが、回答しておきます。

その1

⇒RAND()で時間がかかっているのは、
creation_time < '2016/10/29 00:00'
でヒットする件数分(10万件分くらい?)の
RAND()を発生させて、ソートしているため、
CPUも非常に時間がかかります。

その2

⇒その1の時間で抽出した10件に対して、
tbl.id = tmp_tbl.id;
で抽出しています。
実際の動作は、
tbl.id = Xの結果を
UNION ALLで10回繰り返しているので、
SQLの解析時間もあり、その1より使い物にならない状態になっています。

その3

⇒SQLが省略されているので、省略

その4

⇒RAND()の発生回数を減らす対策の考え方として良いと思います。
もう一息!という感じですね。
他のSQLの結果から察すると、
accounts.id = tmp_tbl.id
にも時間(主にSQL解析時間と予想)がかかってそうです。

どうすれば結果取得までの時間を短縮し、CPU使用率を低くできるか
悪くても0.5秒ぐらいで取得したい

⇒以下のような考え方でCPU使用率を低く、0.5秒くらいで取得できると思います。

案1)抽出条件にヒットする20~100件を(ORDER BY creation_time 等のINDEXに存在する項目で)先に取得し、
その結果に対してRAND()を発生させて、10件取得する。

⇒INDEX破損がなければ、予想としては0.3秒程度です。

案2)案1において、update_time項目を追加し、その項目をソート項目とする。
(毎回同じ100件の中からランダムに選ぶのを防げる)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • MariaDB

    407questions

    MariaDBは、MySQL派生のオープンソースなリレーショナルデータベースシステムです。 また、MySQLとほぼ同じデータベースエンジンに対応しています。