Planet MySQL :: Planet MySQL - Archives - なぜMySQLのサブクエリは遅いのか。

よくMySQLはサブクエリが弱いと言われるが、これは本当だろうか？半分は本当で半分は嘘である。MySQLのサブクエリだってなんでもかんでも遅いわけではない。落とし穴をしっかり避け、使いどころを間違えなければサブクエリも高速に実行できるのである。今日はMySQLがどんな風にサブクエリを実行し、どのような場合に遅いのかということについて説明しよう。

EXPLAINで実行計画を調べた際に、select_typeにはクエリの種類が表示されるのだが、代表的なサブクエリには次の3つのパターンがある。

SUBQUERY
DEPENDENT SUBQUERY
DERIVED

結論から言おう。遅いのは2番目、DEPENDENT SUBQUERYである。DEPENDENT SUBQUERYとはいわゆる相関サブクエリに相当するもので、サブクエリにおいて外部クエリのカラムを参照しているサブクエリのことである。そして、MySQLのオプティマイザはたびたび相関関係のないもの、つまり本来はSUBQUERYと分類されるべきものをDEPENDENT SUBQUERYであると判断してしまう。そのため、多くの場合においてサブクエリが遅くなってしまうのである。

MySQLにおいてDEPENDENT SUBQUERYが何故遅いか？それはクエリの評価方法にある。

現時点でのMySQL（バージョン5.1）では、サブクエリはまず外部クエリの条件から評価される。そして、外部クエリの条件に合致する行が見つかると、その行がサブクエリの条件に合致するかどうかが評価されるわけである。即ち、サブクエリにおいてフェッチしなければいけない行数が平均N行、外部クエリでフェッチされる行数がM行のとき、サブクエリにおいてM×N行の評価が行われることになる。これは膨大な計算量である。

以下に具体例を挙げよう。


mysql> EXPLAIN SELECT * FROM Country WHERE Continent = 'Asia' AND Code IN
    -> (SELECT CountryCode FROM City WHERE Population > Country.Population / 2);
+----+--------------------+---------+------+---------------+------+---------+------+------+-------------+
| id | select_type        | table   | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+--------------------+---------+------+---------------+------+---------+------+------+-------------+
|  1 | PRIMARY            | Country | ALL  | NULL          | NULL | NULL    | NULL |  239 | Using where |
|  2 | DEPENDENT SUBQUERY | City    | ALL  | NULL          | NULL | NULL    | NULL | 4079 | Using where |
+----+--------------------+---------+------+---------------+------+---------+------+------+-------------+
2 rows in set (0.00 sec)

ここで利用しているテーブルは、MySQL公式のサンプルデータベースであるworldデータベースのCountryおよびCityテーブルである。このクエリは「人口が特定の都市に半分以上が密集しているアジアの国」を探し出す。この実行計画が示すのは、

まず外部クエリが評価され、CountryテーブルからContinent = 'Asia'にマッチする行がフェッチされる。
Countryテーブルからフェッチされた各行に対してサブクエリ(SELECT CountryCode FROM City...)が評価され、人口が国全体の半数以上密集している都市が存在するかどうかを調べる。

CountryテーブルにはContinent = 'Asia'にマッチする行が51行あるので、Cityテーブルは51×4079=208,029回の評価が行われることになる。ちなみに、このクエリの実行には1秒程度かかってしまう。


mysql> SELECT * FROM Country WHERE Continent = 'Asia' AND Coode IN
    -> (SELECT CountryCode FROM City WHERE Population > Country.Population / 2);
+------+-----------+-----------+----------------+-------------+-----------+------------+----------------+----------+----------+---------------------------------------+----------------------------------------+----------------------------+---------+-------+
| Code | Name      | Continent | Region         | SurfaceArea | IndepYear | Population | LifeExpectancy | GNP      | GNPOld   | LocalName                             | GovernmentForm                         | HeadOfState                | Capital | Code2 |
+------+-----------+-----------+----------------+-------------+-----------+------------+----------------+----------+----------+---------------------------------------+----------------------------------------+----------------------------+---------+-------+
| MAC  | Macao     | Asia      | Eastern Asia   |       18.00 |      NULL |     473000 |           81.6 |  5749.00 |  5940.00 | Macau/Aomen                           | Special Administrative Region of China | Jiang Zemin                |    2454 | MO    |
| QAT  | Qatar     | Asia      | Middle East    |    11000.00 |      1971 |     599000 |           72.4 |  9472.00 |  8920.00 | Qatar                                 | Monarchy                               | Hamad ibn Khalifa al-Thani |    2973 | QA    |
| SGP  | Singapore | Asia      | Southeast Asia |      618.00 |      1965 |    3567000 |           80.1 | 86503.00 | 96318.00 | Singapore/Singapura/Xinjiapo/Singapur | Republic                               | Sellapan Rama Nathan       |    3208 | SG    |
+------+-----------+-----------+----------------+-------------+-----------+------------+----------------+----------+----------+---------------------------------------+----------------------------------------+----------------------------+---------+-------+
3 rows in set (1.08 sec)

このようなDEPENDENT SUBQUERYが常に遅いかというと、そういうわけでもない。サブクエリが評価される際にインデックスを使用することが出来ればこのサブクエリの性能は改善される。次のように。


mysql> ALTER TABLE City ADD INDEX (CountryCode);
Query OK, 4079 rows affected (0.30 sec)
Records: 4079  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM Country WHERE Continent = 'Asia' AND Coode IN
    -> (SELECT CountryCode FROM City WHERE Population > Country.Population / 2);
+------+-----------+-----------+----------------+-------------+-----------+------------+----------------+----------+----------+---------------------------------------+----------------------------------------+----------------------------+---------+-------+
| Code | Name      | Continent | Region         | SurfaceArea | IndepYear | Population | LifeExpectancy | GNP      | GNPOld   | LocalName                             | GovernmentForm                         | HeadOfState                | Capital | Code2 |
+------+-----------+-----------+----------------+-------------+-----------+------------+----------------+----------+----------+---------------------------------------+----------------------------------------+----------------------------+---------+-------+
| MAC  | Macao     | Asia      | Eastern Asia   |       18.00 |      NULL |     473000 |           81.6 |  5749.00 |  5940.00 | Macau/Aomen                           | Special Administrative Region of China | Jiang Zemin                |    2454 | MO    |
| QAT  | Qatar     | Asia      | Middle East    |    11000.00 |      1971 |     599000 |           72.4 |  9472.00 |  8920.00 | Qatar                                 | Monarchy                               | Hamad ibn Khalifa al-Thani |    2973 | QA    |
| SGP  | Singapore | Asia      | Southeast Asia |      618.00 |      1965 |    3567000 |           80.1 | 86503.00 | 96318.00 | Singapore/Singapura/Xinjiapo/Singapur | Republic                               | Sellapan Rama Nathan       |    3208 | SG    |
+------+-----------+-----------+----------------+-------------+-----------+------------+----------------+----------+----------+---------------------------------------+----------------------------------------+----------------------------+---------+-------+
3 rows in set (0.02 sec)

インデックスが使われている様子は、EXPLAINでも見て取れる。


mysql> EXPLAIN SELECT * FROM Country WHERE Continent = 'Asia' AND Coode IN
    -> (SELECT CountryCode FROM City WHERE Population > Country.Population / 2);
+----+--------------------+---------+------+---------------+-------------+---------+--------------------+------+-------------+
| id | select_type        | table   | type | possible_keys | key         | key_len | ref                | rows | Extra       |
+----+--------------------+---------+------+---------------+-------------+---------+--------------------+------+-------------+
|  1 | PRIMARY            | Country | ALL  | NULL          | NULL        | NULL    | NULL               |  239 | Using where |
|  2 | DEPENDENT SUBQUERY | City    | ref  | CountryCode   | CountryCode | 3       | world.Country.Code |   18 | Using where |
+----+--------------------+---------+------+---------------+-------------+---------+--------------------+------+-------------+
2 rows in set (0.01 sec)

なぜインデックスをつけるのがCountryCodeカラムなの？と思われるかも知れない。それ以前に、そもそもこのサブクエリには相関関係などないように見える。なぜ相関関係がないのにDEPENDENT SUBQUERYになるのだろうか？それは、MySQLがこのクエリを次のように書き換えて実行するからだ。


mysql> SELECT * FROM Country WHERE Continent = 'Asia' AND EXISTS
    -> (SELECT 1 FROM City WHERE Population > Country.Population / 2 AND CountryCode = Country.Code);

MySQLは内部的にINを直接処理することができないので、EXISTSに変換することでSQL的には相関のないサブクエリも相関サブクエリになってしまうのである。これがまさにMySQLのサブクエリが遅い！と言われている原因だろう。

この例では外部クエリのWHERE句の条件にマッチする行数が51行しかないので高速化が可能だが、マッチする行数が多い場合、たとえば外部クエリのWHERE句にサブクエリ以外の検索条件がない場合にはテーブルスキャンが発生してしまうことになり、外部クエリで用いられているテーブルが大きい場合には時間が掛かってしまうのである。従って、サブクエリが遅い！！と感じたときにはまず意図せずDEPENDENT SUBQUERYとなっていないかどうか、外部クエリからフェッチされる行数が膨大でないかどうか、サブクエリでインデックスが利用されているかどうかをチェックすると良い。サブクエリでインデックスをつけるべきカラムは、サブクエリが結果を返すカラム、上記の例で言えばCountryCodeである。さらに、サブクエリ内のWHERE句で指定されているカラムであるPopulationと複合インデックス(CountryCode,Population)を作成すればこのクエリはもっと高速になるだろう。

冒頭で挙げた3つのパターンのうち、DEPENDENT SUBQUERY以外のサブクエリはとても高速である。EXPLAINでSUBQUERYと表示されるパターンについて見てみよう。


mysql> EXPLAIN SELECT * FROM Country WHERE Population > ANY (SELECT Population FROM City);
+----+-------------+---------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table   | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+---------+------+---------------+------+---------+------+------+-------------+
|  1 | PRIMARY     | Country | ALL  | NULL          | NULL | NULL    | NULL |  239 | Using where |
|  2 | SUBQUERY    | City    | ALL  | NULL          | NULL | NULL    | NULL | 4079 |             |
+----+-------------+---------+------+---------------+------+---------+------+------+-------------+
2 rows in set (0.00 sec)

この例では敢えてインデックスが利用されないようなクエリを選んでいる。それでもこのクエリはとても速い。（実行時間は0.01秒とか）なぜならSUBQUERYの部分は一度だけしか評価されないからである。ホントか？と思う人はFLUSH STATUSをしてから上記のクエリを実行し、SHOW STATUS LIKE 'Handler%'でストレージエンジンへのアクセス回数を見てみよう。

ちなみに、このクエリをMySQLは内部的に次のように書き換えて実行する。


mysql> SELECT * FROM Country WHERE Population > (SELECT MAX(Population) FROM City);

どの行（ANY）より大きいということは最大値（MAX）より大きいということになるので、上記のように書き換えても結果は同じになるというわけである。もちろんこのクエリではインデックスがあればさらに高速になる。インデックスをつけるべきカラムはもちろんCity.Populationである。その場合、EXPLAINの表示は次のようになる。


mysql> EXPLAIN SELECT * FROM Country WHERE Population < ANY (SELECT Population FROM City);
+----+-------------+---------+------+---------------+------+---------+------+------+------------------------------+
| id | select_type | table   | type | possible_keys | key  | key_len | ref  | rows | Extra                        |
+----+-------------+---------+------+---------------+------+---------+------+------+------------------------------+
|  1 | PRIMARY     | Country | ALL  | NULL          | NULL | NULL    | NULL |  239 | Using where                  | 
|  2 | SUBQUERY    | NULL    | NULL | NULL          | NULL | NULL    | NULL | NULL | Select tables optimized away | 
+----+-------------+---------+------+---------------+------+---------+------+------+------------------------------+
2 rows in set (0.00 sec)

Extraフィールドに面白い表示がされている。Select tables optimized awayは、テーブルがMyISAMである場合にMAX()/MIN()によってサブクエリの最適化が行われた事を意味するメッセージである。これが現れたらサブクエリは最強に最適化されまくってるので、これ以上手の入れようがないということである。（外部クエリは最適化の余地があるかも知れないが。）

さて、最後に見るのはDERIVEDである。DERIVEDはSQL標準では「Subquery in the FROM clause」と呼ばれる。そのままやんけ！と叫びたくなる呼び名であるが、ここは気にせず話を進めよう。DERIVEDが利用されるのは例えば次のようなクエリである。


mysql> EXPLAIN SELECT AVG(p) FROM (SELECT SUM(Population) p FROM Country GROUP BY Continent) CountryPop;
+----+-------------+------------+------+---------------+------+---------+------+------+---------------------------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows | Extra                           |
+----+-------------+------------+------+---------------+------+---------+------+------+---------------------------------+
|  1 | PRIMARY     |  | ALL  | NULL          | NULL | NULL    | NULL |    7 |                                 |
|  2 | DERIVED     | Country    | ALL  | NULL          | NULL | NULL    | NULL |  239 | Using temporary; Using filesort |
+----+-------------+------------+------+---------------+------+---------+------+------+---------------------------------+
2 rows in set (0.01 sec)

id=1の項目では、テーブル名が<derived2>となっているが、id=2のテーブルからDerive（由来）するものであるということを示す。DERIVEDでは、サブクエリは前もって実行されてその結果がテンポラリテーブルに格納される。外部クエリはテンポラリテーブルを使ってクエリを実行することになる。DERIVEDで注意しないといけないのは、テンポラリテーブルのサイズが大きくなってしまうような場合である。MySQLのテンポラリテーブルは最初MEMORYストレージエンジンを利用して作成されるが、テーブルのサイズがmax_heap_table_sizeまたはtmp_table_sizeを超えてしまうとMyISAMに変換される。DERIVEDを利用する場合には、テンポラリテーブルがメモリ内に収まるようにするというのが一つの鍵である。もしテンポラリテーブルが大きくなってしまう場合は、max_heap_table_sizeおよびtmp_table_sizeを増やすといいだろう。

どうにもこうにもメモリに収まりきらないぐらい大きなテンポラリテーブルが必要な場合には、BIG_TABLESシステム変数を使うと良い。テンポラリテーブルが大きくなってしまった場合、MEMORYからMyISAMへの変換作業自体に時間が掛かってしまうことが問題になる場合がある。そんな時は最初からMyISAMを使えば良い。SET BIG_TABLES=1を設定すると、テンポラリテーブルは最初からMyISAMを利用して作成される。僅かではあるが無駄な変換が行われなくなるので効率化が期待出来る。

まとめ。

というわけでMySQLによるサブクエリの処理について見てきたが、きちんと気をつけて使えばサブクエリも高速に実行される。もちろんJOINに書き換えた方が速いのは言うまでもないが、SQL文のメンテナンスし易さなどを考えるとサブクエリで処理を書きたい！という人も居るのではないだろうか。そんな方は次の事に気をつけてサブクエリを使って頂きたい。

サブクエリの種類
外部クエリとサブクエリの評価の順序
外部クエリにおいてフェッチされる行数
サブクエリで利用されるインデックス
テンポラリテーブルのサイズ

実はMySQLのEXPLAINが表示するサブクエリにはもう一つ種類がある。それはUNCACHEABLE SUBQUERYというもので、サブクエリ内でRAND()などが利用されている時に表示される。UNCACHEABLE SUBQUERYはDEPENDENT SUBQUERYよりも重い。サブクエリ内でRAND()などを利用しないように心がけよう。もしUNCACHEABLE SUBQUERYを見かけたらクエリを書き換えるべし。

MySQL 6.0では、サブクエリの最適化が加わる予定である。相関のないIN (SELECT...)がDEPENDENT SUBQUERYに書き換えられるということがなくなるようにするMaterialization最適化、DEPENDENT SUBQUERYの実行速度を速くするsemi-join最適化手法や、DERIVEDにおいてテンポラリテーブルを用いる必要がないFROM Flattening最適化手法が盛り込まれる予定である。従ってMySQL 6.0では「MySQLのサブクエリは遅い！」と言われることはなくなるだろう。もうすぐリリースされる6.0.10αではFROM Flattening以外の最適化が使えるので、リリースされた暁にはブログで紹介したいと思う。

MySQL Links