😎

[Rails + MySQL]サブクエリを持つクエリの実行順とサブクエリ最適化

2022/04/28に公開

MySQL

Rails

Ruby

tech

はじめに

こんにちは、M-Yamashitaです。

今回の記事は、サブクエリを持つクエリの実行順と、サブクエリの最適化について公式の説明を交えながら説明する話です。

サブクエリの最適化について何も知らず使った結果、パフォーマンス低下を招いてしまい、原因分析や修正など大変な経験をしました。事前に知っていれば避けられた問題でした。
この問題を少しでも避けてもらいたいと思い、サブクエリを持つクエリの実行順、サブクエリを使用したときにMySQLが選択しうる最適化について記事を書きました。
MySQLについてあまり詳しくないため、間違っている箇所等あれば指摘をお願いします。

なお、本記事ではMySQL 5.7.35を使用した前提となっています。

この記事で伝えたいこと

私が出会ったサブクエリの問題と対策
サブクエリを持つクエリの実行順
サブクエリ最適化の概要と適用条件

背景

以前、Railsにてサブクエリを使ったコードを書いていました。
そのままのコードは載せられないので、以下のようなサンプルコードで説明します。

20210522040855_create_users

class CreateUsers < ActiveRecord::Migration
  def change
    create_table :users do |t|
      t.string :name
      t.string :email

      t.timestamps null: false
    end
  end
end

20210522040952_create_microposts

class CreateMicroposts < ActiveRecord::Migration
  def change
    create_table :microposts do |t|
      t.text :content
      t.references :user, index: true, foreign_key: true

      t.timestamps null: false
    end
  end

micropost.rb

class Micropost < ActiveRecord::Base
  belongs_to :user
end

サブクエリを使った実装コード:

users = User.where(email: 'test@example.com')
microposts = Micropost.where(user: users).where("created_at < ?", "2022-04-20 00:00:00")
microposts.update_all(content: 'xxx')

指定のメールアドレスを持つユーザにて、作成日時が指定日時より前のコンテンツ内容を更新する処理となります。このときusersテーブル、micropostsテーブルにはそれぞれ大量のレコード（100万件）が存在していました。

上記コードを実行すると、実行クエリは以下のようになります。

  SQL (30891.9ms)  UPDATE `microposts` SET `microposts`.`content` = 'xxx' WHERE `microposts`.`user_id` IN (SELECT `users`.`id` FROM `users` WHERE `users`.`email` = 'test@example.com') AND (created_at < '2022-04-20 00:00:00')

実行されたクエリは30秒以上もかかっていますね。サンプルではこのくらいの秒数ですが、実際にはこれ以上の時間がかかり、DBに負荷がかかっていました。

この現象を確認された方から、「このクエリはDBに負荷がかかる」、「サブクエリは重いので使わないほうが良い」といったご指摘をいただきました。
そのため、なぜ負荷がかかるのか、サブクエリを使用したとき何が起きるのかを調べ始めました。

先に背景の問題の結論

背景にあるクエリを最適化した場合、サブクエリ最適化が適用され、EXISTS戦略が選択されるようです。
その結果、外側のクエリで取得したuser_idそれぞれに対し、サブクエリのmicropostsテーブルの検索が行われてしまい、DBの負荷増加につながっていました。

対策として、サブクエリ自体を別に分けてあらかじめ実行しておき、その結果をもとに外側のクエリを実行するようにしました。この他にも対策はあると思いますが、今回はこの方法を選択しました。
改善後のコードと実行されたクエリは以下のとおりです。

user_ids = User.where(email: 'test@example.com').pluck(:id)
microposts = Micropost.where(user: user_ids).where("created_at < ?", "2022-04-20 00:00:00")
microposts.update_all(content: 'xxx')

(1130.4ms)  SELECT `users`.`id` FROM `users` WHERE `users`.`email` = 'test@example.com'
SQL (5.6ms)  UPDATE `microposts` SET `microposts`.`content` = 'xxx' WHERE `microposts`.`user_id` IN (1, 12) AND (created_at < '2022-04-20 00:00:00')

変更前後を見てわかる通り、実行時間が大幅に短縮されました。
なお、IN句にセットされるIDが大量にある場合、テーブルフルスキャンになってしまう可能性があるので、IN句にセットするID一覧を細切れにし、複数回に分けて更新する等必要です。
参考:

サブクエリについて

前提

本記事ではクエリの例を出すために以下の2テーブルを使用しています。

mysql> SHOW columns FROM users;
+------------+--------------+------+-----+---------+----------------+
| Field      | Type         | Null | Key | Default | Extra          |
+------------+--------------+------+-----+---------+----------------+
| id         | int(11)      | NO   | PRI | NULL    | auto_increment |
| name       | varchar(255) | YES  |     | NULL    |                |
| email      | varchar(255) | YES  |     | NULL    |                |
| created_at | datetime     | NO   |     | NULL    |                |
| updated_at | datetime     | NO   |     | NULL    |                |
+------------+--------------+------+-----+---------+----------------+
5 rows in set (0.02 sec)

mysql> SHOW columns FROM microposts;
+------------+----------+------+-----+---------+----------------+
| Field      | Type     | Null | Key | Default | Extra          |
+------------+----------+------+-----+---------+----------------+
| id         | int(11)  | NO   | PRI | NULL    | auto_increment |
| content    | text     | YES  |     | NULL    |                |
| user_id    | int(11)  | YES  | MUL | NULL    |                |
| created_at | datetime | NO   |     | NULL    |                |
| updated_at | datetime | NO   |     | NULL    |                |
+------------+----------+------+-----+---------+----------------+
5 rows in set (0.01 sec)

なお、micropostsテーブルのuser_idはusersテーブルのidを参照しています。

また、上記2テーブルには100万件のサンプルレコードを入れています。
サンプルレコードの中身は以下のとおりです。

mysql> SELECT * FROM users; 
+---------+---------------+-------------------------+---------------------+---------------------+
| id      | name          | email                   | created_at          | updated_at          |
+---------+---------------+-------------------------+---------------------+---------------------+
|       1 | 名前1         | test1@example.com       | 2022-04-23 15:19:07 | 2022-04-23 15:19:07 |
|       2 | 名前2         | test2@example.com       | 2022-04-23 15:19:07 | 2022-04-23 15:19:07 |
|       3 | 名前3         | test3@example.com       | 2022-04-23 15:19:07 | 2022-04-23 15:19:07 |
・・・
mysql> SELECT * FROM microposts;
+---------+----------------+---------+---------------------+---------------------+
| id      | content        | user_id | created_at          | updated_at          |
+---------+----------------+---------+---------------------+---------------------+
|       1 | content1       |       1 | 2022-04-23 15:21:03 | 2022-04-23 15:21:03 |
|       2 | content2       |       2 | 2022-04-23 15:21:03 | 2022-04-23 15:21:03 |
|       3 | content3       |       3 | 2022-04-23 15:21:03 | 2022-04-23 15:21:03 |
・・・

サブクエリを持つときのクエリの実行順

公式ドキュメントから引用します。

MySQL evaluates queries “from outside to inside.” That is, it first obtains the value of the outer expression outer_expr, and then runs the subquery and captures the rows that it produces.

記載のとおり、MySQLでは外側から内側に向けて実行されます。そのため最初に外側のクエリを実行し、次にサブクエリが実行されます。

実際にサブクエリを持つクエリをEXPLAINし、実行順序を確認してみます。

mysql> EXPLAIN SELECT * FROM users WHERE id IN (SELECT user_id FROM microposts);
+----+--------------+-------------+------------+--------+-----------------------------+-----------------------------+---------+-------------------+--------+----------+-------------+
| id | select_type  | table       | partitions | type   | possible_keys               | key                         | key_len | ref               | rows   | filtered | Extra       |
+----+--------------+-------------+------------+--------+-----------------------------+-----------------------------+---------+-------------------+--------+----------+-------------+
|  1 | SIMPLE       | users       | NULL       | ALL    | PRIMARY                     | NULL                        | NULL    | NULL              | 995504 |   100.00 | Using where |
|  1 | SIMPLE       | <subquery2> | NULL       | eq_ref | <auto_key>                  | <auto_key>                  | 5       | sampledb.users.id |      1 |   100.00 | NULL        |
|  2 | MATERIALIZED | microposts  | NULL       | index  | index_microposts_on_user_id | index_microposts_on_user_id | 5       | NULL              | 997646 |   100.00 | Using index |
+----+--------------+-------------+------------+--------+-----------------------------+-----------------------------+---------+-------------------+--------+----------+-------------+
3 rows in set, 1 warning (0.01 sec)

usersテーブルを検索したあとに、micropostsテーブルが検索されていることが分かります。

サブクエリの最適化

クライアント側がサブクエリを使用したとき、MySQLではサブクエリの評価が行われます。
MySQL 5.7では、オプティマイザーはサブクエリの評価を行うために、それぞれ最適化の戦略を持っています。

INやANYを使ったサブクエリの場合
- 準結合（Semijoin）
- 実体化（Materialization）
- EXISTS戦略（EXISTS strategy）
NOT INや<>ALLを使ったサブクエリの場合
- 実体化（Materialization）
- EXISTS戦略（EXISTS strategy）

以降は、それぞれの戦略について説明します。

準結合（Semijoin）

準結合とは

公式ドキュメントから引用します。

SELECT class_num, class_name
FROM class
WHERE class_num IN (SELECT class_num FROM roster);
Here, the optimizer can recognize that the IN clause requires the subquery to return only one instance of each class number from the roster table. In this case, the query can use a semijoin; that is, an operation that returns only one instance of each row in class that is matched by rows in roster.

この説明では、rosterテーブルの行と一致するclassテーブルの各行のインスタンスを1つだけ返すとあります。
また、以下記事では次のように説明されています。

セミジョインとはサブクエリ内のテーブルの重複レコードを取り除き，結合と同じような動きをします。

準結合が使用される条件

準結合が使用されるためには、以下の条件を満たしている必要があります。

システム変数のoptimizer_switchのsemijoinがonになっていること（デフォルトはon）
外側のクエリのWHERE句にIN、もしくはANY句がある
UNIONを使用しない単一のSELECT文である
GROUP BYやHAVING句を持たない
集計関数を持たない
LIMITを使用したORDER BYを持たない
STRAIGHT_JOINがクエリに存在しない
外側、内側のテーブルの合計数が、結合で許可されたテーブルの最大数未満となっている
- MySQLでは、結合で許可されたテーブルの最大数は61となっている
  https://dev.mysql.com/doc/refman/5.7/en/join.html
The maximum number of tables that can be referenced in a single join is 61

準結合使用の確認

mysqlコマンドに--show-warningsをつけてログインします。

 mysql -u root -pxxxxx --show-warnings

EXPLAINを行い、Noteにsemi joinがあれば準結合が使用されています。
実際にEXPLAINをしてみます。

mysql> EXPLAIN SELECT * FROM users WHERE id IN (SELECT user_id FROM microposts);
+----+--------------+-------------+------------+--------+-----------------------------+-----------------------------+---------+-------------------+--------+----------+-------------+
| id | select_type  | table       | partitions | type   | possible_keys               | key                         | key_len | ref               | rows   | filtered | Extra       |
+----+--------------+-------------+------------+--------+-----------------------------+-----------------------------+---------+-------------------+--------+----------+-------------+
|  1 | SIMPLE       | users       | NULL       | ALL    | PRIMARY                     | NULL                        | NULL    | NULL              | 995504 |   100.00 | Using where |
|  1 | SIMPLE       | <subquery2> | NULL       | eq_ref | <auto_key>                  | <auto_key>                  | 5       | sampledb.users.id |      1 |   100.00 | NULL        |
|  2 | MATERIALIZED | microposts  | NULL       | index  | index_microposts_on_user_id | index_microposts_on_user_id | 5       | NULL              | 997646 |   100.00 | Using index |
+----+--------------+-------------+------------+--------+-----------------------------+-----------------------------+---------+-------------------+--------+----------+-------------+
3 rows in set, 1 warning (0.07 sec)

Note (Code 1003): /* select#1 */ select `sampledb`.`users`.`id` AS `id`,`sampledb`.`users`.`name` AS `name`,`sampledb`.`users`.`email` AS `email`,`sampledb`.`users`.`created_at` AS `created_at`,`sampledb`.`users`.`updated_at` AS `updated_at` from `sampledb`.`users` semi join (`sampledb`.`microposts`) where (`<subquery2>`.`user_id` = `sampledb`.`users`.`id`)

Noteにsemi joinがあるため、このクエリは準結合が選択されていることが分かります。

実体化（Materialization）

実体化とは

実体化は、サブクエリの結果を一時テーブルとして生成しメモリに保持することです。
仕組みとしては、クエリの初回実行時にサブクエリを実行した後、メモリ上に一時テーブルを生成し、その一時テーブルにサブクエリの結果を保存します。次回以降、そのサブクエリの結果が必要になったとき、サブクエリを実行せず一時テーブルを参照します。これによりクエリがスピードアップすることとなります。
ただしメモリ上に保持した一時テーブルが大きくなりすぎたときは、ディスクストレージに戻ってしまいます。

実体化が使用される条件

公式では以下のような条件が掲示されています。

For subquery materialization to be used in MySQL, the optimizer_switch system variable materialization flag must be enabled. (See Section 8.9.2, “Switchable Optimizations”.) With the materialization flag enabled, materialization applies to subquery predicates that appear anywhere (in the select list, WHERE, ON, GROUP BY, HAVING, or ORDER BY), for predicates that fall into any of these use cases:

The predicate has this form, when no outer expression oe_i or inner expression ie_i is nullable. N is 1 or larger.
(oe_1, oe_2, ..., oe_N) [NOT] IN (SELECT ie_1, i_2, ..., ie_N ...)
The predicate has this form, when there is a single outer expression oe and inner expression ie. The expressions can be nullable.
oe [NOT] IN (SELECT ie ...)
The predicate is IN or NOT IN and a result of UNKNOWN (NULL) has the same meaning as a result of FALSE.

これをまとめると、以下のようになります。

optimizer_switchのシステム変数のmaterializationがonになっていること（デフォルトはon）
SELECT、WHERE, ON, GROUP BY, HAVING, ORDER BYのどれかに、以下3つのどれかのパターンがある
- 1. クエリが以下のような形になっており、oe_1~oe_Nもしくはie_1~ie_N(1 <= N)がNULLにならないこと。
```
(oe_1, oe_2, ..., oe_N) [NOT] IN (SELECT ie_1, i_2, ..., ie_N ...)
```
- 1. クエリが以下のような1つのoe、ieを持っており、式をNULLにすることができる。
```
oe [NOT] IN (SELECT ie ...)
```
- 1. INやNOT IN句を持っており、UNKNOWN(NULL)の結果がFALSEの結果となっている。

それぞれ具体例で考えてみます。

1つ目: The predicate has this form, when no outer expression oe_i or inner expression ie_i is nullable. N is 1 or larger.

これは文字通りの意味で、以下のようなクエリを指しています。

SELECT * FROM users WHERE (users.id, users.created_at) IN (SELECT user_id, created_at FROM microposts)

このクエリのサブクエリ最適化でどの最適化が選択されているのかを確認します。
準結合が使用されないようにsemijoinフラグをoffにした後、上記クエリをEXPLAINします。

mysql> EXPLAIN SELECT * FROM users WHERE (id, created_at) IN (select user_id, created_at from microposts);
+----+-------------+------------+------------+------+-----------------------------+------+---------+------+--------+----------+-------------+
| id | select_type | table      | partitions | type | possible_keys               | key  | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+------------+------------+------+-----------------------------+------+---------+------+--------+----------+-------------+
|  1 | PRIMARY     | users      | NULL       | ALL  | NULL                        | NULL | NULL    | NULL | 995504 |   100.00 | Using where |
|  2 | SUBQUERY    | microposts | NULL       | ALL  | index_microposts_on_user_id | NULL | NULL    | NULL | 997646 |   100.00 | NULL        |
+----+-------------+------------+------------+------+-----------------------------+------+---------+------+--------+----------+-------------+
2 rows in set, 1 warning (0.02 sec)

Note (Code 1003): /* select#1 */ select `sampledb`.`users`.`id` AS `id`,`sampledb`.`users`.`name` AS `name`,`sampledb`.`users`.`email` AS `email`,`sampledb`.`users`.`created_at` AS `created_at`,`sampledb`.`users`.`updated_at` AS `updated_at` from `sampledb`.`users` where <in_optimizer>((`sampledb`.`users`.`id`,`sampledb`.`users`.`created_at`),(`sampledb`.`users`.`id`,`sampledb`.`users`.`created_at`) in ( <materialize> (/* select#2 */ select `sampledb`.`microposts`.`user_id`,`sampledb`.`microposts`.`created_at` from `sampledb`.`microposts` where 1 ), <primary_index_lookup>(`sampledb`.`users`.`id` in <temporary table> on <auto_key> where ((`sampledb`.`users`.`id` = `materialized-subquery`.`user_id`) and (`sampledb`.`users`.`created_at` = `materialized-subquery`.`created_at`)))))

Noteにmaterialize、materialized-subqueryが含まれており実体化が使用されている事が分かります。（後述の「実体化使用の確認」項目を参照）

2つ目:The predicate has this form, when there is a single outer expression oe and inner expression ie. The expressions can be nullable.

2つ目、3つ目については文章の意味を把握できなかったので、Slackのmysql-casualにて質問したところ、yoku0825さんに教えていただきました。yoku0825さん、ありがとうございます！

2つ目について教えていただいた内容を引用します。

oe または ie がNULLABLEなカラムまたは、NULLアンセーフな演算(たとえばNULL+1はNULL)じゃないかなと思います。

この説明をもとに、私にてNULLアンセーフな演算を持つサブクエリを考えてみました。

SELECT * FROM users WHERE id IN (SELECT user_id FROM microposts WHERE id = NULL + 1);

semijoinフラグをoffにした後、このクエリをEXPLAINしてみます。

mysql> EXPLAIN SELECT * FROM users WHERE id IN (SELECT user_id FROM microposts WHERE id = NULL + 1);
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+--------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra                          |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+--------------------------------+
|  1 | PRIMARY     | users | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 995504 |   100.00 | Using where                    |
|  2 | SUBQUERY    | NULL  | NULL       | NULL | NULL          | NULL | NULL    | NULL |   NULL |     NULL | no matching row in const table |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+--------------------------------+
2 rows in set, 1 warning (0.02 sec)

Note (Code 1003): /* select#1 */ select `sampledb`.`users`.`id` AS `id`,`sampledb`.`users`.`name` AS `name`,`sampledb`.`users`.`email` AS `email`,`sampledb`.`users`.`created_at` AS `created_at`,`sampledb`.`users`.`updated_at` AS `updated_at` from `sampledb`.`users` where <in_optimizer>(`sampledb`.`users`.`id`,`sampledb`.`users`.`id` in ( <materialize> (/* select#2 */ select NULL from `sampledb`.`microposts` where (NULL = (NULL + 1)) ), <primary_index_lookup>(`sampledb`.`users`.`id` in <temporary table> on <auto_key> where ((`sampledb`.`users`.`id` = `materialized-subquery`.`user_id`)))))

Noteにmaterialize、materialized-subqueryが含まれている事が分かるため、実体化が選択されている事が分かります。

3つ目:The predicate is IN or NOT IN and a result of UNKNOWN (NULL) has the same meaning as a result of FALSE.

こちらもyoku0825さんから教えていただいた内容を引用します。

INでNULLとFALSEがすり替わるやつは、例えばこんな感じです。

mysql80 8> SELECT * FROM t;
+------+----------+
| id   | val      |
+------+----------+
|    1 | yoku0825 |
|    2 | yoku0826 |
|    3 | yoku0825 |
|    4 | NULL     |
|    5 | yoku0827 |
|    6 | NULL     |
+------+----------+
6 rows in set (0.00 sec)
mysql80 8> SELECT * FROM t WHERE val = 'yoku0829';  -- 存在しない
Empty set (0.00 sec)
mysql80 8> SELECT NULL IN (NULL);  -- 通常NULL IN NULLはNULLだけれど
+----------------+
| NULL IN (NULL) |
+----------------+
|           NULL |
+----------------+
1 row in set (0.00 sec)
mysql80 8> SELECT NULL IN (SELECT id FROM t WHERE val = 'yoku0829'); -- NULL IN (1行も返さないサブクエリ) はFALSEになる
+---------------------------------------------------+
| NULL IN (SELECT id FROM t WHERE val = 'yoku0829') |
+---------------------------------------------------+
|                                                 0 |
+---------------------------------------------------+
1 row in set (0.00 sec)

実際どこで使うのと言われると謎なんですが、FALSEであるのでNOTでひっくり返すとTRUEになるので、 WHERE NOT(NULLABLEなカラム IN (結果を返さないかも知れないサブクエリ)) とかやると変なことになるかも知れません

教えていただいたクエリを参考に、私の持つテーブルでクエリを作ると

SELECT * FROM users WHERE NULL IN (SELECT id FROM microposts WHERE id > 99999999);

のようになります。

semijoinフラグをoffにして、EXPLAINを行います。

mysql> EXPLAIN SELECT * FROM users WHERE NULL IN (SELECT id FROM microposts WHERE id > 99999999);
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------+
| 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 | Impossible WHERE               |
|  2 | SUBQUERY    | NULL  | NULL       | NULL | NULL          | NULL | NULL    | NULL | NULL |     NULL | no matching row in const table |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+--------------------------------+
2 rows in set, 1 warning (0.01 sec)

Note (Code 1003): /* select#1 */ select `sampledb`.`users`.`id` AS `id`,`sampledb`.`users`.`name` AS `name`,`sampledb`.`users`.`email` AS `email`,`sampledb`.`users`.`created_at` AS `created_at`,`sampledb`.`users`.`updated_at` AS `updated_at` from `sampledb`.`users` where 0

select_typeがSUBQUERYとなりますが、Noteにはmaterialize、materialized-subqueryは表示されないようです。
おそらく、materialize、materialized-subqueryが表示される箇所はサブクエリの式の中になりますが、今回のケースではサブクエリの結果が明らかでありサブクエリが表示されないので、materialize、materialized-subqueryも表示されないと思われます。

実体化使用の確認

mysqlコマンドに--show-warningsをつけてログインします。

 mysql -u root -pxxxxx --show-warnings

準結合が使用されないようにsemijoinフラグをoffにした後、EXPLAINを行い、Noteにmaterialize、materialized-subqueryがあれば実体化が使用されています。
また、実体化を使用しないクエリと比較して、select_typeがDEPENDENT SUBQUERYから SUBQUERYに変わることもあるようです。

mysql> EXPLAIN SELECT * FROM users WHERE id IN (SELECT user_id FROM microposts);
+----+-------------+------------+------------+-------+-----------------------------+-----------------------------+---------+------+--------+----------+-------------+
| id | select_type | table      | partitions | type  | possible_keys               | key                         | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+------------+------------+-------+-----------------------------+-----------------------------+---------+------+--------+----------+-------------+
|  1 | PRIMARY     | users      | NULL       | ALL   | NULL                        | NULL                        | NULL    | NULL | 995504 |   100.00 | Using where |
|  2 | SUBQUERY    | microposts | NULL       | index | index_microposts_on_user_id | index_microposts_on_user_id | 5       | NULL | 997646 |   100.00 | Using index |
+----+-------------+------------+------------+-------+-----------------------------+-----------------------------+---------+------+--------+----------+-------------+
2 rows in set, 1 warning (0.00 sec)

Note (Code 1003): /* select#1 */ select `sampledb`.`users`.`id` AS `id`,`sampledb`.`users`.`name` AS `name`,`sampledb`.`users`.`email` AS `email`,`sampledb`.`users`.`created_at` AS `created_at`,`sampledb`.`users`.`updated_at` AS `updated_at` from `sampledb`.`users` where <in_optimizer>(`sampledb`.`users`.`id`,`sampledb`.`users`.`id` in ( <materialize> (/* select#2 */ select `sampledb`.`microposts`.`user_id` from `sampledb`.`microposts` where 1 ), <primary_index_lookup>(`sampledb`.`users`.`id` in <temporary table> on <auto_key> where ((`sampledb`.`users`.`id` = `materialized-subquery`.`user_id`)))))

EXISTS戦略

EXISTS戦略とは

EXISTS戦略は以下のようなクエリを、EXISTSを持つクエリに書き換える戦略です。
この変換をプッシュダウン戦略とも呼ぶようです。
変換前：

outer_expr IN (SELECT inner_expr FROM ... WHERE subquery_where)

変換後：

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND outer_expr=inner_expr)

また、outer_expr、inner_exprが1個だけでなく複数個あった場合も変換されます。
以下のようにoe_1~oe_Nとie_1~ie_Nの個数が同じだった場合もEXISTS戦略となります。
変換前：

(oe_1, ..., oe_N) IN
  (SELECT ie_1, ..., ie_N FROM ... WHERE subquery_where)

変換後：

EXISTS (SELECT 1 FROM ... WHERE subquery_where
                          AND oe_1 = ie_1
                          AND ...
                          AND oe_N = ie_N)

なお、このEXISTS戦略が選択された場合、検索対象のレコード数には注意を払う必要があります。
というのも、WHERE句にouter_expr=inner_exprがあるため、「外側のクエリのテーブルのレコード数 * サブクエリのテーブルのレコード数」の検索を行ってしまう可能性があります。
（EXISTS句があるため一致するレコードがあれば検索終了となりますが、もしなかった場合すべてのレコードを検索することになります。）

このプッシュダウン戦略が使用されるためには、以下2つを両方見たす必要があります。

outer_expr、inner_exprは両方NULLにならない
サブクエリの結果がFALSE、NULLのどちらになっても、外側のクエリには関係がないこと

もし満たしていなかった場合、最適化がさらに複雑になります。
outer_exprがNULLではなく、inner_exprがNULLだった場合の説明は以下の通りです。

Suppose that outer_expr is known to be a non-NULL value but the subquery does not produce a row such that outer_expr = inner_expr. Then outer_expr IN (SELECT ...) evaluates as follows:
・NULL, if the SELECT produces any row where inner_expr is NULL
・FALSE, if the SELECT produces only non-NULL values or produces nothing
In this situation, the approach of looking for rows with outer_expr = inner_expr is no longer valid. It is necessary to look for such rows, but if none are found, also look for rows where inner_expr is NULL. Roughly speaking, the subquery can be converted to something like this:
EXISTS (SELECT 1 FROM ... WHERE subquery_where AND
       (outer_expr=inner_expr OR inner_expr IS NULL))

EXISTS句に変換した際、サブクエリのWHEREの条件にinner_expr IS NULLの条件も入ってくるということのようです。

なお、outer_exprがNULLになる場合の変換も公式には記載されていますが、そのケースがレアであることから、この記事での記載は省略します。

For multiple-table subqueries, execution of NULL IN (SELECT ...) is particularly slow because the join optimizer does not optimize for the case where the outer expression is NULL. It assumes that subquery evaluations with NULL on the left side are very rare, even if there are statistics that indicate otherwise.

EXISTS戦略が使用される条件

明確に記載がありませんでしたので、おそらく準結合、実体化戦略が選択されなかったときにこのEXISTS戦略が使用されると思われます。

EXISTS戦略使用の確認

mysqlコマンドに--show-warningsをつけてログインします。

 mysql -u root -pxxxxx --show-warnings

semijoinフラグをoffにしてEXPLAINを行った際、NoteにあるクエリにEXISTS句が使用され、WHERE句にinner_expr = outer_exprがあればEXISTS戦略が使用されています。

mysql> EXPLAIN SELECT id FROM users WHERE email IN (SELECT content FROM microposts);
+----+--------------------+------------+------------+------+---------------+------+---------+------+--------+----------+-------------+
| id | select_type        | table      | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra       |
+----+--------------------+------------+------------+------+---------------+------+---------+------+--------+----------+-------------+
|  1 | PRIMARY            | users      | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 995504 |   100.00 | Using where |
|  2 | DEPENDENT SUBQUERY | microposts | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 997646 |    10.00 | Using where |
+----+--------------------+------------+------------+------+---------------+------+---------+------+--------+----------+-------------+
2 rows in set, 1 warning (0.01 sec)

Note (Code 1003): /* select#1 */ select `sampledb`.`users`.`id` AS `id` from `sampledb`.`users` where <in_optimizer>(`sampledb`.`users`.`email`,<exists>(/* select#2 */ select 1 from `sampledb`.`microposts` where (<cache>(`sampledb`.`users`.`email`) = `sampledb`.`microposts`.`content`)))

NoteのクエリにEXISTS句があり、where (<cache>(sampledb.users.email) = sampledb.microposts.content)のようにinner_expr = outer_exprの形になっているため、EXISTS戦略が使われていることが分かります。

おわりに

この記事ではサブクエリの実行順、最適化について説明しました。
何気なく使うサブクエリですが、思わぬ落とし穴もあったりするので、コード修正時にはEXPLAINでの確認も必要ですね。
この記事が誰かのお役に立てれば幸いです。

はじめに

この記事で伝えたいこと

背景

先に背景の問題の結論

サブクエリについて

前提

サブクエリを持つときのクエリの実行順

サブクエリの最適化

準結合（Semijoin）

準結合とは

準結合が使用される条件

準結合使用の確認

実体化（Materialization）

実体化とは

実体化が使用される条件

1つ目: The predicate has this form, when no outer expression oe_i or inner expression ie_i is nullable. N is 1 or larger.

2つ目:The predicate has this form, when there is a single outer expression oe and inner expression ie. The expressions can be nullable.

3つ目:The predicate is IN or NOT IN and a result of UNKNOWN (NULL) has the same meaning as a result of FALSE.

実体化使用の確認

EXISTS戦略

EXISTS戦略とは

EXISTS戦略が使用される条件

EXISTS戦略使用の確認

おわりに

Discussion