【SQL】INを使うよりEXISTSを使った方が速いって本当なのか

## はじめに
SQLにおいて`IN`を使うよりも`EXISTS`を使った方が速いと聞いたことがあり、なぜそう言えるのか。実際はどうなの？と疑問に思ったため、調べてまとめてみました。


## 注意
MariaDBでのみ確認しています。
すべてのDBにおいて書かれていることが正しいとは限りませんので、注意してください。

## なぜそう言われているのか
`IN`を使った場合、`EXISTS`を使った場合、それぞれどのような挙動になるのかをまとめてみます。

### INを使った場合

```sql
-- 一度でも商品を買ったことがあるユーザを抽出する
select * from users u
where u.id in (select p.user_id from purchases p);
```

#### 挙動
- サブクエリの結果を一時テーブルに保存する
- 外側のテーブル（users）一行ごとに一時テーブルに対してフルスキャンする

### EXISTSを使った場合

```sql
-- 一度でも商品を買ったことがあるユーザを抽出する
select * from users u
where exists (select 1 from purchases p where p.user_id = u.id);
```

#### 挙動
- 外側のテーブル（users）一行ごとに、相関サブクエリになっている部分のクエリが走る
- `purchases.user_id`にインデックスがあれば、インデックスを使って捜査する
- 一件でも見つければその時点で処理終了

つまり、`EXISTS`の方が
- **インデックスを使える**
- **一件でも見つければ検索を打ち切る**

という性質があるため、高速になるケースが多いです。

## 本当なのか実際に試す
理由はわかりましたが、実際はどうなのか。
以下の状況下で試すことにします。

### 確認した環境

#### DB
```
MariaDB [mydb]> select version();
+------------------------+
| version()              |
+------------------------+
| 11.4.2-MariaDB-ubu2404 |
+------------------------+
1 row in set (0.006 sec)
```

#### ER図およびDDL

```mermaid
erDiagram
  users ||--o{ purchases: ""

  users {
    int id PK
    varchar(50) name "ユーザー名"
  }

  purchases {
    int id PK
    int user_id FK
    int product_id "今回は商品マスタ省略"
  }
```

```sql
-- ユーザテーブル定義
create table if not exists users(
    id int not null auto_increment,
    name varchar(50) not null,
    primary key (id)
);

-- 購入テーブル定義
-- ユーザが購入したものを記録する
create table if not exists purchases(
    id int not null auto_increment,
    user_id int not null,
    product_id int not null,
    primary key (id),
    foreign key fk_user_id(user_id) references users(id)
);
```

#### データの数
ユーザ1000人に対して、購入データが100万件あると想定。

```
select count(*) from users;
+----------+
| count(*) |
+----------+
|     1000 |
+----------+
```

```
select count(*) from purchases;
+----------+
| count(*) |
+----------+
|  1000000 |
+----------+
```

#### データの偏り具合

以下のようなデータになっている状態で確認します。

- 900人(users)
購入データ(purchases)一人当たり大体1000〜1200程度
- 100人(users)
購入データ(purchases)なし

### INを使った場合

```sql
select * from users u 
where u.id in (select p.user_id from purchases p);
```

```
...
| 896 | name_896 |
| 897 | name_897 |
| 898 | name_898 |
| 899 | name_899 |
| 900 | name_900 |
+-----+----------+
900 rows in set (0.011 sec)
```

### EXISTSを使った場合

```sql
select * from users u 
where exists (select 1 from purchases p where p.user_id = u.id);
```

```
| 896 | name_896 |
| 897 | name_897 |
| 898 | name_898 |
| 899 | name_899 |
| 900 | name_900 |
+-----+----------+
900 rows in set (0.007 sec)
```

`IN`を使った場合：0.011 sec
`EXISTS`を使った場合：0.007 sec

ほぼ大差ないことがわかります。
`EXISTS`の方が速いはずですが、なぜこのようなことになるのでしょうか？

## 実行計画を見てみる
実際どのようにテーブルにアクセスしているのか実行計画を見てみます。

### INを使った場合

```
+------+-------------+-------+------+---------------+------------+---------+-----------+------+----------------------------+
| id   | select_type | table | type | possible_keys | key        | key_len | ref       | rows | Extra                      |
+------+-------------+-------+------+---------------+------------+---------+-----------+------+----------------------------+
|    1 | PRIMARY     | u     | ALL  | PRIMARY       | NULL       | NULL    | NULL      | 1000 |                            |
|    1 | PRIMARY     | p     | ref  | fk_user_id    | fk_user_id | 4       | mydb.u.id | 1109 | Using index; FirstMatch(u) |
+------+-------------+-------+------+---------------+------------+---------+-----------+------+----------------------------+
```

### EXISTSを使った場合

```
+------+-------------+-------+------+---------------+------------+---------+-----------+------+----------------------------+
| id   | select_type | table | type | possible_keys | key        | key_len | ref       | rows | Extra                      |
+------+-------------+-------+------+---------------+------------+---------+-----------+------+----------------------------+
|    1 | PRIMARY     | u     | ALL  | PRIMARY       | NULL       | NULL    | NULL      | 1000 |                            |
|    1 | PRIMARY     | p     | ref  | fk_user_id    | fk_user_id | 4       | mydb.u.id | 1109 | Using index; FirstMatch(u) |
+------+-------------+-------+------+---------------+------------+---------+-----------+------+----------------------------+
```

`IN`を使っても`EXISTS`を使っても**実行計画は全く同じ**であることがわかりました。
つまり、どちらを使っても速度に違いはないことになります。

## 最適化後のクエリを確認する
DBはクエリを最適化して実行するため、実際に自分が投げたクエリとは違うクエリになっていることがあります。
そのため、最適化した後のクエリがどうなっているのか確認してみます。
MariaDBでは`explain extended`した後に`show warnings`を使うことで、最適化された後のクエリを確認可能です。

```
MariaDB [mydb]> explain extended select * from users u where u.id in (select p.user_id from purchases p);
...

MariaDB [mydb]> show warnings\G
*************************** 1. row ***************************
  Level: Note
   Code: 1003
Message: select `mydb`.`u`.`id` AS `id`,`mydb`.`u`.`name` AS `name` from `mydb`.`users` `u` semi join (`mydb`.`purchases` `p`) where `mydb`.`p`.`user_id` = `mydb`.`u`.`id`
```

```
-- Message部分を整形
select 
  `mydb`.`u`.`id` AS `id`,
  `mydb`.`u`.`name` AS `name` 
from 
  `mydb`.`users` `u` 
semi join 
  (`mydb`.`purchases` `p`) 
where 
  `mydb`.`p`.`user_id` = `mydb`.`u`.`id`
```

`semi join`に最適化されていることがわかりました。

### Semi Joinとは

半結合や準結合と呼ばれるもので、以下のような特徴があります。

- 1:Nのテーブルで内部結合や外部結合した場合、基本的にはN行すべてをスキャンする必要があるが、Semi Joinでは1行見つけた時点で残りの検索を打ち切る
- メインのクエリとサブクエリの結合順を変更できる
- 実際にSQL構文にはないので、普段のSQLでは使えない。DBの内部でのみ使用可能

## 最適化しない状態で試す
これでは実際にどちらが速いのかわからないため、最適化しないようにしてみます。
MariaDBでは`optimizer_switch`という変数があり、これを使うことでさまざまな最適化を制御できます。

https://mariadb.com/kb/en/optimizer-switch/

最適化オプションは色々あるのですが、おそらくこのあたりであろう最適化オプションをOFFにして、再度、実行計画を見てみます。
```sql
-- おそらくこのあたりであろう最適化をOFFにしてみた
SET optimizer_switch='semijoin=off,in_to_exists=off,exists_to_in=off';
```


### INの場合

```
MariaDB [mydb]> explain extended select * from users u where u.id in (select p.user_id from purchases p);
+------+--------------+-------+-------+---------------+------------+---------+------+--------+----------+-------------+
| id   | select_type  | table | type  | possible_keys | key        | key_len | ref  | rows   | filtered | Extra       |
+------+--------------+-------+-------+---------------+------------+---------+------+--------+----------+-------------+
|    1 | PRIMARY      | u     | ALL   | NULL          | NULL       | NULL    | NULL | 1000   |   100.00 | Using where |
|    2 | MATERIALIZED | p     | index | NULL          | fk_user_id | 4       | NULL | 998490 |   100.00 | Using index |
+------+--------------+-------+-------+---------------+------------+---------+------+--------+----------+-------------+
```

typeが`index` に変わり、`purchases`テーブルのインデックスをフルスキャンしていることがわかります。
インデックスとはいえ全件スキャンしているため遅そうです。

### EXISTSの場合

```
MariaDB [mydb]> explain extended select * from users u where exists (select 1 from purchases p where p.user_id = u.id);
+------+--------------------+-------+----------------+---------------+------------+---------+------+------+----------+-------------+
| id   | select_type        | table | type           | possible_keys | key        | key_len | ref  | rows | filtered | Extra       |
+------+--------------------+-------+----------------+---------------+------------+---------+------+------+----------+-------------+
|    1 | PRIMARY            | u     | ALL            | NULL          | NULL       | NULL    | NULL | 1000 |   100.00 | Using where |
|    2 | DEPENDENT SUBQUERY | p     | index_subquery | fk_user_id    | fk_user_id | 4       | func | 1109 |   100.00 | Using index |
+------+--------------------+-------+----------------+---------------+------------+---------+------+------+----------+-------------+
2 rows in set, 2 warnings (0.009 sec)
```

typeが`index_subquery`になっており、相関サブクエリに対してインデックスが効いていることがわかります。
その結果、rowsの値もINの実行計画よりも遥かに小さくなり速そうです。

実際に計測してみます。

### 実行結果

#### INの場合
```
...
| 896 | name_896 |
| 897 | name_897 |
| 898 | name_898 |
| 899 | name_899 |
| 900 | name_900 |
+-----+----------+
900 rows in set (0.576 sec)
```

#### EXISTSの場合
```
...
| 896 | name_896 |
| 897 | name_897 |
| 898 | name_898 |
| 899 | name_899 |
| 900 | name_900 |
+-----+----------+
900 rows in set (0.011 sec)
```

`IN`を使った場合：0.576 sec
`EXISTS`を使った場合：0.011 sec

50倍くらいの差が出て、明らかに`EXISTS`の方が高速であることがわかりました。

## まとめ

`IN`を使うよりも`EXISTS`を使った方が以下の理由で速いです。
- `IN`の場合はフルスキャンすることになる
- `EXISTS`の場合はインデックスが効くため、サブクエリに対してフルスキャンする必要がない

ただし、インデックスが効けばなので、インデックスがない場合は高速化しないため注意が必要です。

また、MariaDBに関して言えば、Semi Join（準結合）による最適化が行われれば、INを使ってもEXISTSを使ってもどちらも同じクエリに最適化されるため高速です。
可読性としてはINの方が勝ることが多いため、最適化が効くならINで書いた方がメリットがあると思います。

今回は`IN`を使うより`EXISTS`を使った方が速いって本当なのかというテーマで調査してみました。

それではまた。
TomoProg

# 参考資料

- 達人に学ぶSQL徹底指南書 第2版 11章 SQLを速くするぞ

https://www.shoeisha.co.jp/book/detail/9784798157825

- MariaDBのoptimizer_switch一覧

https://mariadb.com/kb/en/optimizer-switch/

- Semi Joinに関する資料

https://tech.bm-sms.co.jp/entry/2022/12/13/120000