なからなLife

geekに憧れと敬意を抱きながら、SE、ITコンサル、商品企画、事業企画、管理会計、総務・情シス、再び受託でDB屋さんと流浪する人のブログです。

MySQLとRAND関数の挙動の整理 その2

MySQL Advent Calendar 2020 - Qiita の4日目の記事です。
昨日の記事
MySQLとRAND関数の挙動の整理 その1 - なからなLife
の続きです。

よって、前提条件も同じで

での挙動です。

MySQLでテーブルからランダムにn件取り出したい:n=1のとき

test_seqテーブルは「col_id integer」で欠番がない列なので、これを使えば、n=1は「ORDER BY RAND()」ではない方法で1件取り出しが出来ます。

以下のような方法がありますが、NGなヤツがあるので、先にそれも含めて列挙しておきます。
(1)WHERE col_id = FLOOR(RAND() * N : NG
(2)JOIN (SELECT FLOOR(RAND() * N) AS col_id FROM dual) : OK
(3)JOIN (SELECT FLOOR(RAND() * N) AS col_id FROM 実体表) :OKだが遅い
(4)JOIN (SELECT FLOOR(RAND() * N) AS col_id FROM 実体表 LIMIT 1) :OK
(5)ユーザー定義変数を使う:OK、だけど。。。

2020.12.04追記
あとから気づいたのですが、このネタは、みんな大好き「SQLアンチパターン」の「15章 ランダムセレクション」に記載がありました。
しかし、上記5つと丸かぶりするものはなかったので、
(6)「SQLアンチパターン」に記載のある方法
として追加しています。
2020.12.04追記ここまで

では、1つずつ見ていきます。

(1)WHERE col_id = FLOOR(RAND() * N

SELECT * FROM test_seq WHERE col_id = FLOOR(RAND() * 10000000);

するとランダムな1件が取得できる、と期待したいところですが、これも直感に反して全件に対してRAND()を実行し、偶然「col_id = FLOOR(RAND() * 10000000)」が真になったときだけレコードが抽出されます。
結果、0件なこともあるし、複数件ヒットすることもありますので、まったくアテにならないです。


また、「RAND() * N」で、col_idの最大値まで算出されるようにのN値を調整しないと、出てこない値が発生してしまいますね。


前回も、サラっと

RAND関数は、使用するテーブル全件に対して1件ずつ乱数生成処理を行う。

って書いたんですけど、これWHEREにも適用されるんですよね。

WHERE 句内の RAND() は、WHERE が実行されるたびに再評価されます。

ORDER BY ではカラムが複数回評価されるため、ORDER BY 句内では RAND() 値を持つカラムを使用できません。ただし、次のようにランダムな順序で行を取得できます。

mysql> SELECT * FROM tbl_name ORDER BY RAND();

LIMIT と組み合わせて ORDER BY RAND() を使用すれば、行のセットからランダムなサンプルを選択する際に役立ちます。

mysql> SELECT * FROM table1, table2 WHERE a=b AND c<d -> ORDER BY RAND() LIMIT 1000;

https://dev.mysql.com/doc/refman/5.6/ja/mathematical-functions.html#function_rand

公式ドキュメント側にしっかりランダム行取り出しの例とか出してくれてるんですけど、そもそも「どおして、テーブル全行に対して、逐一乱数生成を実行する仕様なの?」については触れられていません。


というわけで、WHERE句でRAND関数を使うケースのサンプルとなるSQLの実行結果、スロークエリログの出力状況、実行計画は以下の通りです。

mysql> SELECT * FROM test_seq WHERE col_id = FLOOR(RAND() * 10000000);
+---------+
| col_id  |
+---------+
|    5864 |
| 6999598 |
+---------+
2 rows in set (2.61 sec)

-- スロークエリログ
# Query_time: 2.611023  Lock_time: 0.000088 Rows_sent: 2  Rows_examined: 16777216

-- 実行計画
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+--------------------------+
| id | select_type | table    | partitions | type  | possible_keys | key     | key_len | ref  | rows     | filtered | Extra                    |
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+--------------------------+
|  1 | SIMPLE      | test_seq | NULL       | index | NULL          | PRIMARY | 4       | NULL | 16333383 |    10.00 | Using where; Using index |
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+--------------------------+||<

と、見事に2件引っかかってしまい、INDEX FULLSCANでRows_examinedが跳ね上がってますね。

(2)JOIN (SELECT FLOOR(RAND() * N) AS col_id FROM dual)

このようにdual表を使ったサブクエリ表とJOINすると良いようです。
というか、Oracle上がりなので「FROM dual」って書いちゃいますけど、「FROM dual」は省略しても大丈夫。

SELECT r.col_id FROM test_seq s JOIN (SELECT FLOOR(RAND() * 1000000) AS col_id FROM dual) r WHERE s.col_id = r.col_id;

もちろん、MySQL 8.0ならWITH句を使用しても大丈夫です。

このようにJOINすると、以下のようになります。

mysql> SELECT r.col_id FROM test_seq s JOIN (SELECT FLOOR(RAND() * 1000000) AS col_id FROM dual) r WHERE s.col_id = r.col_id;
+--------+
| col_id |
+--------+
| 516476 |
+--------+
1 row in set (0.00 sec)


-- スロークエリログ
# Query_time: 0.000406  Lock_time: 0.000179 Rows_sent: 1  Rows_examined: 1

-- 実行計画
+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+----------------+
| id | select_type | table      | partitions | type   | possible_keys | key     | key_len | ref   | rows | filtered | Extra          |
+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+----------------+
|  1 | PRIMARY     | <derived2> | NULL       | system | NULL          | NULL    | NULL    | NULL  |    1 |   100.00 | NULL           |
|  1 | PRIMARY     | s          | NULL       | const  | PRIMARY       | PRIMARY | 4       | const |    1 |   100.00 | Using index    |
|  2 | DERIVED     | NULL       | NULL       | NULL   | NULL          | NULL    | NULL    | NULL  | NULL |     NULL | No tables used |
+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+----------------+

速い!


なぜか、MySQL8.0.22ではRows_examinedが「2」だったけど。。。


なお、dual表はレコード1件だけを持つ仮想表です。SELECT * FROM dualで中身を見ることは出来ないです。*1


(3)JOIN (SELECT FLOOR(RAND() * N) AS col_id FROM dual以外の表)

では、dual表以外の1行のテーブルでサブクエリしたりJOINすればRAND()は1回だけ評価されて結合されるかというと、そうではないです。。。

CREATE TABLE `test_rand` (
  `col_id` int(11) NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`col_id`)
);

INSERT INTO test_rand SELECT 0;

なテーブルに1行だけINSERTして、

SELECT r.col_id FROM test_seq s JOIN (SELECT FLOOR(RAND() * 1000000) AS col_id FROM test_rand) r WHERE s.col_id = r.col_id;

すると、

mysql> SELECT r.col_id FROM test_seq s JOIN (SELECT FLOOR(RAND() * 1000000) AS col_id FROM test_rand) r WHERE s.col_id = r.col_id;
Empty set (2.62 sec)

-- スロークエリログ
# Query_time: 2.623315  Lock_time: 0.000198 Rows_sent: 0  Rows_examined: 16777217

-- 実行計画
+----+-------------+-----------+------------+-------+---------------+---------+---------+------+----------+----------+-----------------------------------------------------------------+
| id | select_type | table     | partitions | type  | possible_keys | key     | key_len | ref  | rows     | filtered | Extra                                                           |
+----+-------------+-----------+------------+-------+---------------+---------+---------+------+----------+----------+-----------------------------------------------------------------+
|  1 | SIMPLE      | test_rand | NULL       | index | NULL          | PRIMARY | 4       | NULL |        1 |   100.00 | Using index                                                     |
|  1 | SIMPLE      | s         | NULL       | index | NULL          | PRIMARY | 4       | NULL | 16333383 |    10.00 | Using where; Using index; Using join buffer (Block Nested Loop) |
+----+-------------+-----------+------------+-------+---------------+---------+---------+------+----------+----------+-----------------------------------------------------------------+

となります。空振りな上に、INDEX FULLSCANで1600万件スキャンですね。。。

RANDの評価回数が、サブクエリの外にいる結合相手に引きずられる、という、なかなか直感的ではない仕様。


なかなかややこしいですね。

(4)JOIN (SELECT FLOOR(RAND() * N) AS col_id FROM 実体表 LIMIT 1)

上記(3)と同じ条件で、サブクエリに「LIMIT 1」をつけると、高速に、1件だけ取れるようになります。

mysql> SELECT r.col_id FROM test_seq s JOIN (SELECT FLOOR(RAND() * 1000000) AS col_id FROM test_rand LIMIT 1) r WHERE s.col_id = r.col_id;
+--------+
| col_id |
+--------+
| 220977 |
+--------+
1 row in set (0.00 sec)

-- スロークエリログ
# Query_time: 0.000510  Lock_time: 0.000250 Rows_sent: 1  Rows_examined: 2

-- 実行計画
+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+
| id | select_type | table      | partitions | type   | possible_keys | key     | key_len | ref   | rows | filtered | Extra       |
+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+
|  1 | PRIMARY     | <derived2> | NULL       | system | NULL          | NULL    | NULL    | NULL  |    1 |   100.00 | NULL        |
|  1 | PRIMARY     | s          | NULL       | const  | PRIMARY       | PRIMARY | 4       | const |    1 |   100.00 | Using index |
|  2 | DERIVED     | test_rand  | NULL       | index  | NULL          | PRIMARY | 4       | NULL  |    1 |   100.00 | Using index |
+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+


でも、n=10が欲しくて、「LIMIT=10」と書いても、このままだと1件しか返ってこないです。
結合対象となる実体表「test_rand」に入っている件数が最大となり、その範囲であれば、欲しい件数をLIMITに指定して取得できるようになります。

こうなると、結合先のテーブルの格納件数そのものは関係ない。。。

なので、極端な話、同じテーブル=1600万件超入っているテーブルを使って

SELECT r.col_id FROM test_seq s JOIN (SELECT FLOOR(RAND() * 1000000) AS col_id FROM test_seq LIMIT 1) r WHERE s.col_id = r.col_id;

と書いても、同様に「Rows_examined: 2」で高速に1件取得できます。


(5)ユーザー定義変数を使う

あと、ユーザー定義変数を使える場合、

SET @rand_value=FLOOR(RAND() * 1000000);
SELECT col_id FROM test_seq WHERE col_id = @rand_value;

とすると、SELECT文の中からはRAND関数自体が排除されて、単純に1つの値を検索条件とする等価検索なクエリになります。

なので当然ですが、

mysql> select COUNT(*) from test_rand;
+----------+
| COUNT(*) |
+----------+
|        1 |
+----------+
1 row in set (0.00 sec)

mysql> SET @rand_value=FLOOR(RAND() * 1000000);
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT col_id FROM test_seq WHERE col_id = @rand_value;
+--------+
| col_id |
+--------+
| 222033 |
+--------+
1 row in set (0.00 sec)

# Query_time: 0.000177  Lock_time: 0.000093 Rows_sent: 1  Rows_examined: 1

+----+-------------+----------+------------+-------+---------------+---------+---------+-------+------+----------+-------------+
| id | select_type | table    | partitions | type  | possible_keys | key     | key_len | ref   | rows | filtered | Extra       |
+----+-------------+----------+------------+-------+---------------+---------+---------+-------+------+----------+-------------+
|  1 | SIMPLE      | test_seq | NULL       | const | PRIMARY       | PRIMARY | 4       | const |    1 |   100.00 | Using index |
+----+-------------+----------+------------+-------+---------------+---------+---------+-------+------+----------+-------------+

になります。

ユーザー定義変数は「用法・用量を守って正しくお使いください」的なやり方だと思っています。
個人的には、使い捨てのSQLならともかくプロダクションで利用するなら、MySQLのユーザー定義変数じゃなくてアプリ実装の言語内でランダム値を生成して利用して欲しいですね。


(6)「SQLアンチパターン」に記載のある方法(2020.12.04追記)

SQLアンチパターンには、5つの解決策が提示されています。

  • 15.5.1. 1と最大値のランダムなキー値を選択する
  • 15.5.2. 欠番の穴の後ろにあるキー値を選択する
  • 15.5.3 すべてのキー値のリストを受け取り、ランダムに1つを選択する
  • 15.5.4. オフセットを用いてランダムに行を選択する
  • 15.5.5. ベンダー依存の解決策

それぞれ、見ていきましょう。

15.5.1. 1と最大値のランダムなキー値を選択する

欠番なしの連番から1件取る時のみ使えるものですが、高速に、ランダムに1件取れますね。さすがです。


今回の試験用のテーブルに書き換えると

SELECT b1.* FROM test_seq AS b1
JOIN (SELECT CEIL(RAND()*(SELECT MAX(col_id) FROM test_seq)) AS col_id) AS b2
ON b1.col_id = b2.col_id
ORDER BY b1.col_id
LIMIT 1;

です。

スロークエリと実行計画はこんな感じでした。

# Query_time: 0.000411  Lock_time: 0.000136 Rows_sent: 1  Rows_examined: 1

+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+------------------------------+
| id | select_type | table      | partitions | type   | possible_keys | key     | key_len | ref   | rows | filtered | Extra                        |
+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+------------------------------+
|  1 | PRIMARY     | <derived2> | NULL       | system | NULL          | NULL    | NULL    | NULL  |    1 |   100.00 | NULL                         |
|  1 | PRIMARY     | b1         | NULL       | const  | PRIMARY       | PRIMARY | 4       | const |    1 |   100.00 | Using index                  |
|  2 | DERIVED     | NULL       | NULL       | NULL   | NULL          | NULL    | NULL    | NULL  | NULL |     NULL | No tables used               |
|  3 | SUBQUERY    | NULL       | NULL       | NULL   | NULL          | NULL    | NULL    | NULL  | NULL |     NULL | Select tables optimized away |
+----+-------------+------------+------------+--------+---------------+---------+---------+-------+------+----------+------------------------------+
15.5.2. 欠番の穴の後ろにあるキー値を選択する

欠番のあるケースに対応させたものです。

「15.5.1. 1と最大値のランダムなキー値を選択する」との違いは、
結合条件のところで
「ON b1.col_id = b2.col_id」

「ON b1.col_id >= b2.col_id」
に変えただけです。

スロークエリと実行計画はこんな感じで、実行計画のid=2が b1テーブルに対するPrimary Keyのrangeスキャンでrowsが跳ね上がっていますが、Rows_examinedは1で処理できています。

# Query_time: 0.000495  Lock_time: 0.000289 Rows_sent: 1  Rows_examined: 1

+----+-------------+------------+------------+--------+---------------+---------+---------+------+---------+----------+------------------------------+
| id | select_type | table      | partitions | type   | possible_keys | key     | key_len | ref  | rows    | filtered | Extra                        |
+----+-------------+------------+------------+--------+---------------+---------+---------+------+---------+----------+------------------------------+
|  1 | PRIMARY     | <derived2> | NULL       | system | NULL          | NULL    | NULL    | NULL |       1 |   100.00 | NULL                         |
|  1 | PRIMARY     | b1         | NULL       | range  | PRIMARY       | PRIMARY | 4       | NULL | 3344480 |   100.00 | Using where; Using index     |
|  2 | DERIVED     | NULL       | NULL       | NULL   | NULL          | NULL    | NULL    | NULL |    NULL |     NULL | No tables used               |
|  3 | SUBQUERY    | NULL       | NULL       | NULL   | NULL          | NULL    | NULL    | NULL |    NULL |     NULL | Select tables optimized away |
+----+-------------+------------+------------+--------+---------------+---------+---------+------+---------+----------+------------------------------+

LIMITを増やすと、ランダムな5件でなく、ランダムで特定した1件から連続する5件、になるのが、「(4)JOIN (SELECT FLOOR(RAND() * N) AS col_id FROM 実体表 LIMIT 1)」と異なるところです。

15.5.3 すべてのキー値のリストを受け取り、ランダムに1つを選択する

1回目のSELECTでフルリストを取り、アプリ側でリスト内の値を1つランダムに取得、そのキー値でSELECTし直す、というロジックをアプリ側で実装する、というものです。

SQL2回投げる必要があるのと、1回目の全件リスト取得でアプリ側のメモリを食うことに気をつけましょう、という注記もあります。
でも1回目にリストを取るようにしているため、欠番ありのケースや、そもそも数値じゃないケースでも対応できます。

これは実行計画もスロークエリも取りません。わかりきっている話なので。

15.5.4. オフセットを用いてランダムに行を選択する

テーブルの行数を用いて0からのオフセット値「x」をランダムで生成し、その値を使った「LIMIT 1 OFFSET x」なSELECT文で行全体を取り直す、という手法です。

今回使っているテストテーブルが1列の連番なのでちょっとわかりにくいですが、以下のように、id_offsetをランダムで生成し、その数だけoffsetしたレコードを1件とるので、1から始まる連番テーブルでは、id_offset+1を持つレコードが返ってきます。

1秒以下で処理できているJOIN方式に比べると、ちょっとだけ遅いです。

mysql> SELECT ROUND(RAND() * (SELECT COUNT(*) FROM test_seq)) AS id_offset;
+-----------+
| id_offset |
+-----------+
|  11827634 |
+-----------+
1 row in set (1.78 sec)

# Query_time: 1.775593  Lock_time: 0.000165 Rows_sent: 1  Rows_examined: 16777216

mysql> explain SELECT ROUND(RAND() * (SELECT COUNT(*) FROM test_seq)) AS id_offset;
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+----------------+
| id | select_type | table    | partitions | type  | possible_keys | key     | key_len | ref  | rows     | filtered | Extra          |
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+----------------+
|  1 | PRIMARY     | NULL     | NULL       | NULL  | NULL          | NULL    | NULL    | NULL |     NULL |     NULL | No tables used |
|  2 | SUBQUERY    | test_seq | NULL       | index | NULL          | PRIMARY | 4       | NULL | 16333383 |   100.00 | Using index    |
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+----------------+
2 rows in set, 1 warning (0.00 sec)

mysql> SELECT * FROM test_seq LIMIT 1 OFFSET 11827634;
+----------+
| col_id   |
+----------+
| 11827635 |
+----------+
1 row in set (1.36 sec)

# Query_time: 1.359631  Lock_time: 0.000086 Rows_sent: 1  Rows_examined: 11827635

mysql> explain SELECT * FROM test_seq LIMIT 1 OFFSET 11827634;
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+-------------+
| id | select_type | table    | partitions | type  | possible_keys | key     | key_len | ref  | rows     | filtered | Extra       |
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+-------------+
|  1 | SIMPLE      | test_seq | NULL       | index | NULL          | PRIMARY | 4       | NULL | 16333383 |   100.00 | Using index |
+----+-------------+----------+------------+-------+---------------+---------+---------+------+----------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

LIMIT OFFSETが使えないけどウインドウ関数が使えるDBの場合は、ウインドウ関数で処理できるようです。MySQLのエントリなので詳しく触れませんので、SQLアンチパターン読んでください。

  • 15.5.5. ベンダー依存の解決策

SQL Serverには「TABLESAMPLE」句、Oracleには「SAMPLE」句があって、ランダムにサンプルレコードを抽出できるそうです。
MySQLのエントリなので(略

まとめ

  • ランダムに1件だけレコードを抽出したいケースでは、欠番のない連番数値列が存在していれば、ORDER BY RAND()ではない方法が使える。
  • 単純に「WHERE カラム = FLOOR(RAND() * N」とすると、テーブルの件数分だけRAND関数が評価され、等価式が偶然「真」になったときだけ値が戻るため、戻り件数が不定で、0件になることもある。
  • サブクエリとJOINを使用する方式では、RAND関数を実行するサブクエリ内では表無指定・dual表を使うか、サブクエリに「LIMIT N」を指定すると正確に高速に処理できる。
  • 2020.12.04追記名著「SQLアンチパターン」の「15章 ランダムセレクション」にも書いてある。

経験上、プロダクションでRAND関数を使うケースが結構少ないなと思う次第。
数値列での検索なら、MySQLのRAND関数は使わずに、アプリ側の実装言語の乱数生成結果で素直なSQLを投げてきて欲しいのが正直なところです。
欠番にあたったらリトライするか、等価検索じゃなくて範囲検索かつLIMITつけるかすれば直近の値が拾えるはずなので。



今回の一連のネタ、応答速度にシビアに影響してくるけど、

にも載ってない模様。

*1:Oracleだとdual表の中身が参照できて、「X」という値の入った1行が返ってきます。