TL;DR

MySQL8.0.17から Anti-Join 最適化が導入され、NOT EXISTS や NOT IN クエリのパフォーマンスが向上
Anti-Joinは、駆動表の行に対して内部表で一致する行が存在しない場合にのみ結果を返す
Semijoin（準結合）の逆バージョンとして理解でき、効率的な「存在しないデータ」の取得が可能
MySQLのコストベースオプティマイザは、以下2つの戦略を自動選択する
- First Match戦略: 条件に一致する最初の行が見つかると検索を終了し、メモリ効率が良い
- Materialization戦略: 内部表を一時テーブル化して、複雑な条件や大規模データに対応

前提

MySQL version

Server version:         8.0.28 MySQL Community Server - GPL

DBに Sakila Sample Database を利用

Sakila Sample DatabaseはMySQL開発チームが提供しているMySQLの機能を検証したりするためのサンプルデータベースです。

こちらのGitHubレポジトリからダウンロードすればMySQL以外のRDBMSへのデータ取り込みも可能です。

本記事では、Sakila Sample Databaseから以下2つのテーブルを利用します。

customer.sql(顧客テーブル)

CREATE TABLE `customer` (
  `customer_id` smallint unsigned NOT NULL AUTO_INCREMENT,
  `store_id` tinyint unsigned NOT NULL,
  `first_name` varchar(45) NOT NULL,
  `last_name` varchar(45) NOT NULL,
  `email` varchar(50) DEFAULT NULL,
  `address_id` smallint unsigned NOT NULL,
  `active` tinyint(1) NOT NULL DEFAULT '1',
  `create_date` datetime NOT NULL,
  `last_update` timestamp NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`customer_id`),
  KEY `idx_fk_store_id` (`store_id`),
  KEY `idx_fk_address_id` (`address_id`),
  KEY `idx_last_name` (`last_name`),
  CONSTRAINT `fk_customer_address` FOREIGN KEY (`address_id`) REFERENCES `address` (`address_id`) ON DELETE RESTRICT ON UPDATE CASCADE,
  CONSTRAINT `fk_customer_store` FOREIGN KEY (`store_id`) REFERENCES `store` (`store_id`) ON DELETE RESTRICT ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=600 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci

rental.sql(顧客によるレンタル履歴テーブル)

CREATE TABLE `rental` (
  `rental_id` int NOT NULL AUTO_INCREMENT,
  `rental_date` datetime NOT NULL,
  `inventory_id` mediumint unsigned NOT NULL,
  `customer_id` smallint unsigned NOT NULL,
  `return_date` datetime DEFAULT NULL,
  `staff_id` tinyint unsigned NOT NULL,
  `last_update` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`rental_id`),
  UNIQUE KEY `rental_date` (`rental_date`,`inventory_id`,`customer_id`),
  KEY `idx_fk_inventory_id` (`inventory_id`),
  KEY `idx_fk_customer_id` (`customer_id`),
  KEY `idx_fk_staff_id` (`staff_id`),
  CONSTRAINT `fk_rental_customer` FOREIGN KEY (`customer_id`) REFERENCES `customer` (`customer_id`) ON DELETE RESTRICT ON UPDATE CASCADE,
  CONSTRAINT `fk_rental_inventory` FOREIGN KEY (`inventory_id`) REFERENCES `inventory` (`inventory_id`) ON DELETE RESTRICT ON UPDATE CASCADE,
  CONSTRAINT `fk_rental_staff` FOREIGN KEY (`staff_id`) REFERENCES `staff` (`staff_id`) ON DELETE RESTRICT ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=16050 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci

本文

Anti-Joinとは？

Anti-Joinは、結合操作の一種でJoinでの左側テーブル(駆動表)において右側テーブル(内部表)に一致する行が存在しないレコードのみを抽出するJoin操作の最適化の1つになります。

NOT EXISTSやNOT IN演算を利用するクエリにてこれまでサブクエリを利用していた実行計画がAnti-Joinを利用することで置き換わっています。(後述)

Anti-Join最適化はMySQL8.0.17から導入されています。対応するMySQL公式ブログとドキュメントはそれぞれ以下です。

公式ブログ: Antijoin in MySQL 8
公式ドキュメント: Changes in MySQL 8.0.17 (2019-07-22, General Availability)

Semijoin（準結合）との関係

動作としてAnti-JoinはSemijoinの派生機能でありそれぞれ以下の特徴があります。

Semijoin（準結合）: 駆動表の行に対して、内部表で条件に一致する行が存在するかどうかを確認する
- → 条件に一致する場合、その行が結果として返される
Anti-Join（反結合）: Semijoinの逆で、条件に一致する行が存在しない場合に駆動表の行を返す

Anti-Joinにおける2つの戦略: First Match と Materialization

First Match戦略とMaterialization戦略とは？

Anti-Join最適化において、オプティマイザは2つの戦略から最適なものを自動選択します。

First Match戦略

内容と特徴
- 駆動表の各行に対して内部表を1行ずつ検索する
- 条件に一致する行が1つでも見つかった時点でその検索を終了し、次の駆動表の行に移る
- 余計なデータを処理しないため、メモリ使用量が少なく、インデックスが利用可能な場合に効率的
- 条件一致時にすぐに処理を終了するため、短時間で検索を終えられる
- メモリや一時テーブルを使わないためリソース消費が少ない

Materialization戦略

内容と特徴
- 最初に内部表をスキャンして条件を満たすデータを抽出し、一時テーブル（Materialized Table）を作成する
- その後、駆動表の各行をこの一時テーブルに対して効率的に検索
- 内部表のスキャンが1回で済み、その後は一時テーブルに対して効率的に検索を行える
- 複雑な条件や内部表が大規模な場合に効果を発揮する
- 一時テーブルの作成にはメモリやディスク領域が必要で、初期コストが高くなることがある

First Match と Materialization 戦略のクエリ比較

First Match

First Match戦略が選択されるクエリの例

SELECT c.*
FROM customer c
WHERE NOT EXISTS (
    SELECT 1
    FROM rental r
    WHERE c.customer_id = r.customer_id -- インデックスが使われる条件
);

First Match戦略が選択されるクエリの実行計画

+----+-------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+--------------------------------------+
| id | select_type | table | partitions | type | possible_keys      | key                | key_len | ref                  | rows | filtered | Extra                                |
+----+-------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+--------------------------------------+
|  1 | SIMPLE      | c     | NULL       | ALL  | NULL               | NULL               | NULL    | NULL                 |  599 |   100.00 | NULL                                 |
|  1 | SIMPLE      | r     | NULL       | ref  | idx_fk_customer_id | idx_fk_customer_id | 2       | sakila.c.customer_id |   26 |   100.00 | Using where; Not exists; Using index |
+----+-------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+--------------------------------------+

First Match戦略が選択されるクエリのformat=tree(analyze)の実行計画

| -> Nested loop antijoin  (cost=1814.52 rows=16008) (actual time=5.245..5.245 rows=0 loops=1)
    -> Table scan on c  (cost=61.15 rows=599) (actual time=0.181..0.758 rows=599 loops=1)
    -> Covering index lookup on r using idx_fk_customer_id (customer_id=c.customer_id)  (cost=6.93 rows=27) (actual time=0.007..0.007 rows=1 loops=599)
 |

駆動表customerの各行ごとに内部表rentalのインデックスを利用して検索している。

今回のケースではrentalに無いcustomerが無いのでAnti-Joinでは結果的にすべての行を見に行っている。

Materialization

Materialization戦略が選択されるクエリの例

SELECT c.*
FROM customer c
WHERE NOT EXISTS (
    SELECT 1
    FROM rental r
    WHERE c.last_update = r.last_update -- インデックスが使われない条件
);

Materialization戦略が選択されるクエリの実行計画

+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+----------------------+-------+----------+-------------------------+
| id | select_type  | table       | partitions | type   | possible_keys       | key                 | key_len | ref                  | rows  | filtered | Extra                   |
+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+----------------------+-------+----------+-------------------------+
|  1 | SIMPLE       | c           | NULL       | ALL    | NULL                | NULL                | NULL    | NULL                 |   599 |   100.00 | NULL                    |
|  1 | SIMPLE       | <subquery2> | NULL       | eq_ref | <auto_distinct_key> | <auto_distinct_key> | 5       | sakila.c.last_update |     1 |   100.00 | Using where; Not exists |
|  2 | MATERIALIZED | r           | NULL       | ALL    | NULL                | NULL                | NULL    | NULL                 | 16008 |   100.00 | NULL                    |
+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+----------------------+-------+----------+-------------------------+

Materialization戦略が選択されるクエリのformat=tree(analyze)の実行計画

| -> Nested loop antijoin  (cost=959000.25 rows=9588792) (actual time=30.928..31.811 rows=599 loops=1)
    -> Table scan on c  (cost=61.15 rows=599) (actual time=0.161..0.598 rows=599 loops=1)
    -> Single-row index lookup on <subquery2> using <auto_distinct_key> (last_update=c.last_update)  (actual time=0.000..0.000 rows=0 loops=599)
        -> Materialize with deduplication  (cost=3225.85..3225.85 rows=16008) (actual time=31.025..31.025 rows=2 loops=1)
            -> Filter: (r.last_update is not null)  (cost=1625.05 rows=16008) (actual time=0.030..7.901 rows=16044 loops=1)
                -> Table scan on r  (cost=1625.05 rows=16008) (actual time=0.028..5.907 rows=16044 loops=1)
 |

内部表rentalを条件に基づいて一時テーブル化し、重複を排除している（with deduplication）。

その後、駆動表customerの各行を一時テーブルに対して検索している。

従来のサブクエリ利用の問題点

MySQLでは、NOT EXISTS や NOT IN クエリはしばしばサブクエリの評価に依存していました。しかし、サブクエリは駆動表の行ごとに再評価されるため、効率が悪くなる場合があります。

ヒント句を用いてAnti-Join最適化を無効化しサブクエリで実行してみる

ヒント句を用いてAnti-Join最適化を無効化したクエリ

SELECT c.*
FROM customer c
WHERE NOT EXISTS (
    SELECT /*+ NO_SEMIJOIN() */ 1 -- Anti-Join(Semijoin)を無効化するヒント句
    FROM rental r
    WHERE c.customer_id = r.customer_id
);

ヒント句を用いてAnti-Join最適化を無効化したクエリの実行計画

+----+--------------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+-------------+
| id | select_type        | table | partitions | type | possible_keys      | key                | key_len | ref                  | rows | filtered | Extra       |
+----+--------------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+-------------+
|  1 | PRIMARY            | c     | NULL       | ALL  | NULL               | NULL               | NULL    | NULL                 |  599 |   100.00 | Using where |
|  2 | DEPENDENT SUBQUERY | r     | NULL       | ref  | idx_fk_customer_id | idx_fk_customer_id | 2       | sakila.c.customer_id |   26 |   100.00 | Using index |
+----+--------------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+-------------+

ヒント句を用いてAnti-Join最適化を無効化したクエリのformat=tree(analyze)の実行計画

| -> Filter: exists(select #2) is false  (cost=61.15 rows=599) (actual time=6.250..6.250 rows=0 loops=1)
    -> Table scan on c  (cost=61.15 rows=599) (actual time=0.286..0.816 rows=599 loops=1)
    -> Select #2 (subquery in condition; dependent)
        -> Limit: 1 row(s)  (cost=2.93 rows=1) (actual time=0.008..0.008 rows=1 loops=599)
            -> Covering index lookup on r using idx_fk_customer_id (customer_id=c.customer_id)  (cost=2.93 rows=27) (actual time=0.008..0.008 rows=1 loops=599)
 |

サブクエリの動作概要
- 駆動表の各行ごとに内部表のrentalを評価する
- サブクエリの評価が繰り返されるため、駆動表の行数が多い場合、コストが高くなる

LEFT JOIN WHERE IS NULL のクエリの場合

以下のクエリもこれまでのクエリと等価の「rentalテーブルに該当する行が存在しないcustomerテーブルの行を取得する」ものです。

LEFT JOIN は、駆動表と内部表のすべての一致するデータを生成します。

その後、WHERE IS NULL で不要なデータをフィルタリングしますが、この処理は後段で行われるため基本的に非効率になります。

LEFT JOIN WHERE IS NULL のクエリ

SELECT c.*
FROM customer c
LEFT JOIN rental r ON c.customer_id = r.customer_id
WHERE r.customer_id IS NULL;

LEFT JOIN WHERE IS NULL のクエリの実行計画

+----+-------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+--------------------------------------+
| id | select_type | table | partitions | type | possible_keys      | key                | key_len | ref                  | rows | filtered | Extra                                |
+----+-------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+--------------------------------------+
|  1 | SIMPLE      | c     | NULL       | ALL  | NULL               | NULL               | NULL    | NULL                 |  599 |   100.00 | NULL                                 |
|  1 | SIMPLE      | r     | NULL       | ref  | idx_fk_customer_id | idx_fk_customer_id | 2       | sakila.c.customer_id |   26 |   100.00 | Using where; Not exists; Using index |
+----+-------------+-------+------------+------+--------------------+--------------------+---------+----------------------+------+----------+--------------------------------------+

LEFT JOIN WHERE IS NULL のクエリのformat=tree(analyze)の実行計画

| -> Filter: (r.customer_id is null)  (cost=1814.52 rows=16008) (actual time=4.908..4.908 rows=0 loops=1)
    -> Nested loop antijoin  (cost=1814.52 rows=16008) (actual time=4.904..4.904 rows=0 loops=1)
        -> Table scan on c  (cost=61.15 rows=599) (actual time=0.226..0.811 rows=599 loops=1)
        -> Covering index lookup on r using idx_fk_customer_id (customer_id=c.customer_id)  (cost=0.26 rows=27) (actual time=0.007..0.007 rows=1 loops=599)
 |

上記のformat=treeの実行計画にて、このクエリでもNested loop antijoinを利用していることがわかります。これはMySQL8.17以降ではLEFT JOIN WHERE IS NULLのクエリもオプティマイザが自動で判断しているためのようです。

参考

https://dev.mysql.com/doc/refman/8.0/en/semijoins.html