ORDER BY RAND(); が遅い

Question

質問

タイトルの通りなのですが、
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_timeはaccountsテーブルにデータが挿入された日時

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

Answer 1

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

その1

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

その2

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

その3

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

その4

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

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

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

案１）抽出条件にヒットする２０～１００件を（ORDER BY creation_time 等のINDEXに存在する項目で）先に取得し、
その結果に対してRAND()を発生させて、１０件取得する。

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

案２）案１において、update_time項目を追加し、その項目をソート項目とする。
（毎回同じ１００件の中からランダムに選ぶのを防げる）

Answer 2

英語サイトで申し訳ないですが、
こちらの「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に対して複合インデックスを定義すると尚良さそう。

Comments

[aglkjggg]

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

試した結果、3.281秒となりました。
※del_flg, create_time, nameに複合インデックスを付けた状態です。

サブクエリの所はMariaDBだと整数値（このクエリの場合は必ず０）になってしまい、
RAND() との比較が期待する形でできていなかったので、
CAST(10 / COUNT(*) * 10 AS DOUBLE)と書き直しました。
また、ORDER BY RAND()が無くともランダムに取得することが出来ていました。

[Panzer_vor]

> aglkjgggさん
おっと、MariaDBの方は型厳密になってるんですね^^;

それなら今のCASTのやり方でもいいですが、被除算部分のCASTのみでいけるかと思います。
(CAST(10 AS DOUBLE) / COUNT(＊) ＊10)

3秒以上かかりますか、それだと厳しいですね。

ORDER BY句がある理由は、
多分ランダムに取ったものを更に入れ替えるために付けられてるんだと思います。

ちなみに現時点での実行計画って掲示可能ですか？
他の方のアプローチで解決できるかもですが念のため。

[aglkjggg]

すみません、お手数をおかけします。
以下のリンクに実行計画を貼り付けさせていただきました。

※creation_time_del_flg_name は
INDEX `creation_time_del_flg_name` (creation_time, del_flg, name)
の事です。

https://gist.github.com/anonymous/d7a5b438f534dc3d698692316877bdb0

[Panzer_vor]

> aglkjgggさん
実行計画の掲示ありがとうございます。
インデックスは想定通り使われてそうですね・・・^^;

サブクエリが遅いのかメインが遅いのか切り分けたいので、
サブクエリ部分を一度定数に置き換えてもらっても構わないでしょうか？

サブクエリで取得される計算結果の値をRANDと比較するよう変更したら速度に変化は出ますかね？

[Panzer_vor]

> aglkjgggさん
すいません、後1点。
速度が変化するかはさておき日付条件の箇所の文字列は比較対象のカラムのデータ型にキャストした方が良いです。

理由としては以下です。
１.DB側の暗黙変換頼りになり意図しないキャストがされるリスクがある
２.変換時に仮にカラム側のデータがキャストされるとインデックスが効かなくなる可能性が高い

[aglkjggg]

定数に置き換えて実行すると目標値である0.5秒台以下（0.3秒）になりました。

また、クエリキャッシュがある為、
サブクエリの1回目は3秒ほどかかりますが、
2回目以降は0.01秒台となっていました。

テーブルに変更が一切かからないテスト環境で行っている為、
サブクエリで得られる結果の値は常に一定です。
一定である為、キャッシュが効いて定数にした時と同じように0.5秒台以下で結果が得られてもいい気がするのですが・・・非常に謎です。。。

[Panzer_vor]

> aglkjgggさん
定数で早いということはサブクエリがボトルネックなのは間違いないですね^^;

実行計画でSUBQUERYと評価されてたので、
もしかしたら1レコードごとに馬鹿正直にサブクエリを評価しているかもしれません。

サブクエリをFROM句に移して、
INNER JOINのフィルタリング条件へ変更してみた場合は速度に変化はありそうでしょうか？

[aglkjggg]

実行計画に変化はありましたが、結果取得までの時間は変化ありませんでした。
select_typeはSUBQUERYからPRIMARYに変化しました。
WHERE RAND() < '2016/10/29 00:00'
を消すと0.01秒台になりました。

色々一緒に考えていただいた所申し訳ありませんが、
やはりRAND()が重すぎる為、
RAND()を利用しなくていいように別の方法を探るしかなさそうです…。
アプリケーション側、DBの再設計を視野にいれることにします。

[Panzer_vor]

> 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回クエリ発行しても少し高速化は出来そうな気はします。

[aglkjggg]

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

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

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

[Panzer_vor]

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

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

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

Answer 3

del_flgとcreation_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 に丸められることはなかったからです。

ご参考までに。

Comments

[aglkjggg]

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

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

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

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

[KiyoshiMotoki]

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

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

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

Answer 4

「その3」を改変して、

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

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

Comments

[aglkjggg]

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

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

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

Answer 5

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

Comments

[aglkjggg]

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

実際に試したところ、
1のクエリで、11.469秒 → 4.734秒
2のクエリで、28.422秒 → 4.813秒
まで短くなりました。

インデックスの順番も色々変えてみましたが、
あまり関係がありませんでした。

悪くても0.5秒ぐらいで取得したいのですが、
難しそうですね・・・。

[Panzer_vor]

横槍失礼します。

データベース、SQLのみでの解決だと、
Orlofskyさんもおっしゃる通りインデックスを定義する、
というのが一番効果的なのは間違いないと思います。
(登録・更新が多いテーブルだとインデックス更新負荷を考えないといけないですが・・・)

もう既に試しているかも分かりませんが、
カバーリングインデックスを定義してみても少し改善できないでしょうか？

Orlofskyさんの提示されているインデックスをちと改修して、
INDEX "hoge" (creation_time, del_flg, id, name)
とSELECT句で取得するnameも含んだインデックスを定義する方法です。

理論上ではインデックスのみの走査で検索結果を取得できも少しコストを下げることができるかもしれません。
(インデックス検索後の物理的に格納された情報とのマッピング負荷がなくなる)

ただし、これも絶対ではないのでうまくいく保証はないです。

後ここからは別件ですが、
インデックスの定義が多くなりすぎてるようにも感じられるので、
本当に必要なインデックスを絞ることで、
DBMS側の実行プランの選択肢誤りや、
データ登録時の更新負荷を抑えることは出来ると思います。

[Panzer_vor]

書き忘れたので補足ですが、
インデックスの検討で重要な観点は代表的なもので以下となるので参考までに。

１．抽出条件として同時に指定される項目は複合インデックス作成候補
２．１．を発展させSELECT句で指定するカラムがごく少数の場合はカバーリングインデックス作成候補(インデックス走査のみで完結させるためのテクニック)
　→ http://use-the-index-luke.com/ja/sql/clustering/index-only-scan-covering-index

３．定義する上でのカラムの順序を検討する。一番絞り込めるものを先頭とすると検索効率が良い。

４．複合インデックスの場合一番左に定義したカラムが検索条件にない時点で間違いなく効かなくなるので注意

ご参考までに。。。

[aglkjggg]

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

カバーリングインデックスという方法初めて知りました。
「一番絞り込めるものを先頭とすると検索効率が良い。」というのも初耳でした。
インデックスの順序が関係あるのは、なんとなくでしか分かっておらず、
今まで避けてきたのですが、B-Tree関係の話も勉強したほうがいいと再確認しました＞＜；

[Panzer_vor]

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

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

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

[Orlofsky]

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

[Panzer_vor]

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

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

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