🔍

MySQLでWhere句内でOR演算子を使うと「インデックスが効かなくなる」は本当か

2022/01/15に公開約16,800字

概要

MySQLのクエリのパフォーマンスチューニングで調べると、Where句内でOR演算子を使うと「インデックスが使われず、フルテーブルスキャンになる」という話が結構でてきますが、あまり説明がなく、イマイチよく分からないので調べてまとめてみました。
ここでいうMySQLは、MySQL5.6を指しています。

これを読むと何が分かるようになるのか

MySQL5.6の検索条件でOR演算子を使った際に、フルテーブルスキャンが発生する条件が分かるようになります(多分)。多分と書いたのは、条件を網羅はできていないと思うからです。

注意

この記事を書くにあたって、一次資料(MySQL5.6リファレンスマニュアル)にあたっていますが、随所に著者の考察が含まれています。つまり、事実と異なる可能性があります。

またこの記事では、OR演算子を使った検索で、フルテーブルスキャンが発生するか否かだけに焦点を当てています。そもそものOR演算子を使ったクエリのパフォーマンスには言及しません。もっと効率良いクエリはあると思いますが、この記事の範疇ではありません。

いきなり結論

本当でもあり、間違いでもある。

  1. Where句内のOR演算子で、インデックスが張られていないカラムが検索条件に混ざっている場合にフルテーブルスキャンになる(これは自然)
  2. Where句内のOR演算子で、検索条件に指定してるカラムすべてに個別にインデックスを張っている場合はフルテーブルスキャンにならない(MySQL5.6よりは前はフルテーブルスキャンになったらしいが、MySQL5.6以降ではインデックスマージという最適化が入る。ただし5.6でも全文検索において例外あり。)
  3. 全文検索時のFULLTEXTインデックス(転置インデックス)を使用している場合は、Where句内でOR演算子を使うことでフルテーブルスキャンになる

検証用のテーブルを用意する

検証用にテーブルを用意します。
データを作るのが面倒だったので、今回はIMDb.comが公開している映画やテレビ番組などのデータを貰ってきて movies テーブルに突っ込みました。

movies テーブルのスキーマです。
まだセカンダリインデックスはありません。

CREATE TABLE `movies` (
  `tconst` varchar(10) COLLATE utf8mb4_unicode_ci NOT NULL,
  `title_type` varchar(127) COLLATE utf8mb4_unicode_ci NOT NULL,
  `primary_title` varchar(127) COLLATE utf8mb4_unicode_ci NOT NULL,
  `original_title` varchar(127) COLLATE utf8mb4_unicode_ci NOT NULL,
  `is_adult` tinyint(1) NOT NULL,
  `start_year` int(11) NOT NULL,
  `end_year` int(11) DEFAULT NULL,
  `runtime_minutes` int(11) NOT NULL,
  `genre` varchar(127) COLLATE utf8mb4_unicode_ci NOT NULL,
  PRIMARY KEY (`tconst`),
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci

mysql> SHOW INDEX FROM movies;
+--------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table  | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| movies |          0 | PRIMARY  |            1 | tconst      | A         |     7061415 |     NULL | NULL   |      | BTREE      |         |               |
+--------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

あまり本質的なところではないですが、一応、各カラムの説明です。

tconst title_type primary_title original_title is_adult start_year end_year runtime_minutes genre
動画のタイトルのID movie, short, tvseries, tvepisode, videoとか 販促資料とかで使われるタイトル(原題と異なる場合がある) 原題 大人向けかどうかフラグ 公開年 終了年(シリーズの終わりとか) 動画の長さ(分) ジャンル

レコード数は大体860万件です。

mysql> SELECT COUNT(*) FROM movies;
+----------+
| COUNT(*) |
+----------+
|  8604847 |
+----------+

MySQL5.6のリファレンスマニュアルを参照しながら検証してみる

順番に検証していきます。

結論1: Where句内のOR演算子で、インデックスが張られていないカラムが検索条件に混ざっている場合にフルテーブルスキャンになる

検証に primary_title カラムと original_title カラムの2つを使います。
この検証では、インデックスが張られているカラムと張られていないカラムの2つが必要なので、今回は primary_title カラムだけにインデックスを張ることにします。

mysql> CREATE INDEX idx_primary_title ON movies (primary_title);

mysql> SHOW INDEX FROM movies;
+--------+------------+-------------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table  | Non_unique | Key_name          | Seq_in_index | Column_name   | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------+------------+-------------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| movies |          0 | PRIMARY           |            1 | tconst        | A         |     7061415 |     NULL | NULL   |      | BTREE      |         |               |
| movies |          1 | idx_primary_title |            1 | primary_title | A         |     7061415 |     NULL | NULL   |      | BTREE      |         |               |
+--------+------------+-------------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

検証用のクエリの実行計画を確認します。
インデックスありの primary_title カラムとインデックスなしの original_title をOR演算子の条件として指定します。
typeALL になっているのでフルテーブルスキャンになっている事が分かります。

mysql> EXPLAIN SELECT * FROM movies WHERE primary_title = 'ALF' OR original_title = 'ALF';
+----+-------------+--------+------+-------------------+------+---------+------+---------+-------------+
| id | select_type | table  | type | possible_keys     | key  | key_len | ref  | rows    | Extra       |
+----+-------------+--------+------+-------------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | movies | ALL  | idx_primary_title | NULL | NULL    | NULL | 7061415 | Using where |
+----+-------------+--------+------+-------------------+------+---------+------+---------+-------------+

念の為に、インデックスありのカラムのみがOR演算子の条件に指定された時はフルテーブルスキャンにならないことを確認します。
インデックスありの primary_title だけを使います。
typeref になり、フルテーブルスキャンではなくインデックスを使ってアクセスされていることが分かります。

mysql> EXPLAIN SELECT * FROM movies WHERE primary_title = 'ALF';
+----+-------------+--------+------+-------------------+-------------------+---------+-------+------+-----------------------+
| id | select_type | table  | type | possible_keys     | key               | key_len | ref   | rows | Extra                 |
+----+-------------+--------+------+-------------------+-------------------+---------+-------+------+-----------------------+
|  1 | SIMPLE      | movies | ref  | idx_primary_title | idx_primary_title | 510     | const |    9 | Using index condition |
+----+-------------+--------+------+-------------------+-------------------+---------+-------+------+-----------------------+

ちなみに、インデックスありの同一のカラムを2回指定してもフルテーブルスキャンにはなりません。
この場合、typerange になっていますが、これはインデックスを用いた範囲検索を表しているのでフルテーブルスキャンは発生していません。

mysql> EXPLAIN SELECT * FROM movies WHERE primary_title = 'ALF' OR primary_title = 'Full House';
+----+-------------+--------+-------+-------------------+-------------------+---------+------+------+-----------------------+
| id | select_type | table  | type  | possible_keys     | key               | key_len | ref  | rows | Extra                 |
+----+-------------+--------+-------+-------------------+-------------------+---------+------+------+-----------------------+
|  1 | SIMPLE      | movies | range | idx_primary_title | idx_primary_title | 510     | NULL |   82 | Using index condition |
+----+-------------+--------+-------+-------------------+-------------------+---------+------+------+-----------------------+

ネットで検索すると「OR演算子の右辺はインデックスが効かない」みたいな話がでてきますが、そうではないようです。

インデックスが効かないのは、OR演算子を使った検索条件にインデックスが張られていないカラムが使われているからです。インデックスが張られていないカラムの検索は、フルテーブルスキャンするしか方法がないです。この場合、MySQL(厳密にはInnoDBか?)のオプティマイザは、「どうせフルテーブルスキャンするならインデックス張られているカラムに対してもインデックス使わなくていいじゃん」と言ってインデックスを使うのをやめるのでしょう。これは効率を考えると自然な処理な気がします。

結論2: Where句内のOR演算子で、検索条件に指定してる異なるカラムすべてに個別にインデックスを張っている場合はフルテーブルスキャンにならない

MySQL5.6以降においては、OR演算子を用いた検索条件に指定しているカラムすべてに個別にインデックスが張られている場合は、フルテーブルスキャンにはなりません。

MySQL5.6より前では、1テーブルに対する1クエリについて、1インデックスしか使わない仕様だったようです。そのため、検索条件に使用している異なるカラムすべてに個別にインデックスを張っていたとしても、1つのカラムだけしかインデックスを使えないので、他のカラムはフルテーブルスキャンするしかありません。こうなるとまたオプティマイザは「どうせフルテーブルスキャンするんじゃん...」と言って、すべてのインデックスの使用をやめてしまったのでしょう。これがMySQLでOR演算子を使って検索するとインデックスが効かなくなると言われてきた理由だと思います。

MySQL5.6で、OR演算子を用いた検索条件に指定しているカラムに個別に張られているインデックスを使って得られた結果をマージしてくれる機能が入りました。これをインデックスマージ最適化といいます。つまり、フルテーブルスキャンは発生せず、インデックスを使ったアクセスです。

ここでも結論1で使用した primary_title カラムと original_title カラムの両方を使って検証します。この検証では異なるカラムすべてに個別にインデックスを張る必要があるので、original_title にもインデックスを張ります。

mysql> CREATE INDEX idx_original_title ON movies (original_title);

mysql> SHOW INDEX FROM movies;
+--------+------------+--------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table  | Non_unique | Key_name           | Seq_in_index | Column_name    | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------+------------+--------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| movies |          0 | PRIMARY            |            1 | tconst         | A         |     7061415 |     NULL | NULL   |      | BTREE      |         |               |
| movies |          1 | idx_primary_title  |            1 | primary_title  | A         |     7061415 |     NULL | NULL   |      | BTREE      |         |               |
| movies |          1 | idx_original_title |            1 | original_title | A         |     7061415 |     NULL | NULL   |      | BTREE      |         |               |
+--------+------------+--------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

検証用のクエリの実行計画を見てみます。
typeindex_merge になっていて、インデックスマージの最適化によりインデックスが効いていることが分かります。

mysql> EXPLAIN SELECT * FROM movies WHERE primary_title = 'ALF' OR original_title = 'Full House';
+----+-------------+--------+-------------+--------------------------------------+--------------------------------------+---------+------+------+----------------------------------------------------------------+
| id | select_type | table  | type        | possible_keys                        | key                                  | key_len | ref  | rows | Extra                                                          |
+----+-------------+--------+-------------+--------------------------------------+--------------------------------------+---------+------+------+----------------------------------------------------------------+
|  1 | SIMPLE      | movies | index_merge | idx_primary_title,idx_original_title | idx_primary_title,idx_original_title | 510,510 | NULL |   79 | Using union(idx_primary_title,idx_original_title); Using where |
+----+-------------+--------+-------------+--------------------------------------+--------------------------------------+---------+------+------+----------------------------------------------------------------+

インデックスマージ最適化が使えなかった時代は、UNION 構文を使ってインデックスが効くようように人力で最適化していたようです。そんな話がググると沢山でてきます。

結論3: 全文検索時のFULLTEXTインデックス(転置インデックス)を使用している場合は、Where句内でOR演算子を使うことでフルテーブルスキャンになる

全文検索に用いるFULLTEXTインデックスではインデックスマージ最適化は行われません。つまり、OR演算子を用いて全文検索を行うとフルテーブルスキャンが発生する可能性があります。

インデックスマージは全文インデックスには適用できません。将来の MySQL リリースでこれらを扱うように、それを拡張する予定です
https://dev.mysql.com/doc/refman/5.6/ja/index-merge-optimization.html

ここでも先の検証に使用した primary_titleoriginal_title カラムを使います。
今回は全文検索を行うので、これらのカラムに対してFULLTEXTインデックスを作成します。FULLTEXTインデックスは全文検索で使用する転置インデックスです。インデックスマージ最適化が適用されないことを確認したいので、両方のカラムにFULLTEXTインデックスを作成します。

mysql> CREATE FULLTEXT INDEX ftxt_idx_primary_title ON movies (primary_title);
mysql> CREATE FULLTEXT INDEX ftxt_idx_original_title ON movies (original_title);

mysql> SHOW INDEX FROM movies;
+--------+------------+-------------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table  | Non_unique | Key_name                | Seq_in_index | Column_name    | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------+------------+-------------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| movies |          0 | PRIMARY                 |            1 | tconst         | A         |     8697793 |     NULL | NULL   |      | BTREE      |         |               |
| movies |          1 | idx_primary_title       |            1 | primary_title  | A         |     8697793 |     NULL | NULL   |      | BTREE      |         |               |
| movies |          1 | idx_original_title      |            1 | original_title | A         |     8697793 |     NULL | NULL   |      | BTREE      |         |               |
| movies |          1 | ftxt_idx_primary_title  |            1 | primary_title  | NULL      |     8697793 |     NULL | NULL   |      | FULLTEXT   |         |               |
| movies |          1 | ftxt_idx_original_title |            1 | original_title | NULL      |     8697793 |     NULL | NULL   |      | FULLTEXT   |         |               |
+--------+------------+-------------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

Btreeインデックス(通常のインデックス)とFULLTEXTインデックスを組み合わせたクエリの実行計画を確認します。
typeALL なので、フルテーブルスキャンが発生しています。
インデックスマージの最適化はされていないようです。

mysql> EXPLAIN SELECT * FROM movies WHERE MATCH(primary_title) AGAINST ('+ALF') OR original_title = 'Full House';
+----+-------------+--------+------+--------------------------------------------+------+---------+------+---------+-------------+
| id | select_type | table  | type | possible_keys                              | key  | key_len | ref  | rows    | Extra       |
+----+-------------+--------+------+--------------------------------------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | movies | ALL  | idx_original_title,ftxt_idx_original_title | NULL | NULL    | NULL | 8697793 | Using where |
+----+-------------+--------+------+--------------------------------------------+------+---------+------+---------+-------------+

FULLTEXTインデックス同士を組み合わせたクエリの実行計画を確認します。
フルテーブルスキャンが発生しています。

mysql> EXPLAIN SELECT * FROM movies WHERE MATCH(primary_title) AGAINST ('+ALF') OR MATCH(original_title) AGAINST ('+"Full House"');
+----+-------------+--------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | movies | ALL  | NULL          | NULL | NULL    | NULL | 8697793 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+---------+-------------+

念の為に、OR演算子を使わない場合にFULLTEXTを使った全文検索ができることも確認します。
typefulltext になり、FULLTEXTインデックスが使われ、フルテーブルスキャンが発生していないことが分かります。

mysql> EXPLAIN SELECT * FROM movies WHERE MATCH(primary_title) AGAINST ('+ALF');
+----+-------------+--------+----------+------------------------+------------------------+---------+------+------+-------------+
| id | select_type | table  | type     | possible_keys          | key                    | key_len | ref  | rows | Extra       |
+----+-------------+--------+----------+------------------------+------------------------+---------+------+------+-------------+
|  1 | SIMPLE      | movies | fulltext | ftxt_idx_primary_title | ftxt_idx_primary_title | 0       | NULL |    1 | Using where |
+----+-------------+--------+----------+------------------------+------------------------+---------+------+------+-------------+

ちなみに、異なる2つのカラムではなく、同一のカラムによるOR演算子を使った全文検索ではフルテーブルスキャンになりました。

mysql> EXPLAIN SELECT * FROM movies WHERE MATCH(primary_title) AGAINST ('+ALF') OR MATCH(primary_title) AGAINST ('+"Full House"');
+----+-------------+--------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | movies | ALL  | NULL          | NULL | NULL    | NULL | 8697793 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+---------+-------------+

FULLTEXTインデックスではインデックスマージ最適化が行われないので、MySQL5.6より前と同様に1つのインデックスしか使わない原則が働くのかもしれません。そのため複数のカラムを検索条件に指定した場合、オプティマイザは「どうせフルテーブルスキャンするし...」と言ってハナからインデックスを使うことを放棄するのかもしれません。

まとめ

AND演算子と違い、OR演算子は複数のカラムによる検索条件の結果の和をとるので、効率を考えると複数カラムのインデックスを使用する必要があります。これを実現するのがインデックスマージ最適化ですが、まだ一部のシチュエーションでは使うことができません。パフォーマンス上の理由で、OR演算子で使用することが避けられてきた背景をうまく説明できた気がします。

付録

MySQL5.6リファレンスマニュアル

https://dev.mysql.com/doc/refman/5.6/ja/

検証に使ったMySQLのバージョン

mysql> SELECT VERSION();
+-----------+
| VERSION() |
+-----------+
| 5.6.51    |
+-----------+

検証に使ったデータ
ファイル名: title.basics.tsv.gz
入手先: IMDb Datasets

https://www.imdb.com/interfaces/

Discussion

ログインするとコメントできます