UNIQE INDEXと JOIN とORDER BY で無用なソートが発生するケースとその回避方法

mysql

Amazon.co.jp： 実践ハイパフォーマンスMySQLを読んでいたら「クエリチューニング」の章(p. 101)でタイトルにある問題が取りあげられていたので考察。
MySQL のバージョンは「5.0.67」。

サンプルDB

サンプルとして、よくある商品と注文のテーブルを使います。
作るのが手間だったので、本の例と変えています。あと、説明に関係ないカラム*1も省略しています。

> show create table products \G;
*************************** 1. row ***************************
       Table: products
Create Table: CREATE TABLE `products` (
  `id` int(11) NOT NULL auto_increment,
  `name` varchar(40) NOT NULL,
  PRIMARY KEY  (`id`),
  UNIQUE KEY `name` (`name`)
) ENGINE=MyISAM AUTO_INCREMENT=4 DEFAULT CHARSET=utf8


> show create table orders \G;
*************************** 1. row ***************************
       Table: orders
Create Table: CREATE TABLE `orders` (
  `id` int(11) NOT NULL auto_increment,
  `product_id` int(11) NOT NULL,
  `customer_id` int(11) NOT NULL,
  `ordered_on` date NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `product_id` (`product_id`,`ordered_on`)
) ENGINE=MyISAM AUTO_INCREMENT=5 DEFAULT CHARSET=utf8
  • レコード
> select * from products;
+----+----------+
| id | name     |
+----+----------+
|  1 | ipod     | 
|  2 | macbook  | 
|  3 | keyboard | 
+----+----------+

> select * from orders;
+----+------------+-------------+------------+
| id | product_id | customer_id | ordered_on |
+----+------------+-------------+------------+
|  1 |          1 |           1 | 2009-01-01 | 
|  2 |          2 |           1 | 2009-01-01 | 
|  3 |          1 |           2 | 2009-01-13 | 
|  4 |          1 |           3 | 2009-01-12 | 
+----+------------+-------------+------------+

問題のクエリ

> select orders.ordered_on from products left join orders ON products.id = orders.product_id where products.name = 'ipod' order by ordered_on;
+------------+
| ordered_on |
+------------+
| 2009-01-01 | 
| 2009-01-12 | 
| 2009-01-13 | 
+------------+


EXPLAIN かけると、

> explain select products.name, orders.ordered_on from products left join orders ON products.id = orders.product_id where products.name = 'ipod' order by ordered_on;
+----+-------------+----------+-------+---------------+------------+---------+-------+------+---------------------------------+
| id | select_type | table    | type  | possible_keys | key        | key_len | ref   | rows | Extra                           |
+----+-------------+----------+-------+---------------+------------+---------+-------+------+---------------------------------+
|  1 | SIMPLE      | products | const | name          | name       | 122     | const |    1 | Using temporary; Using filesort | 
|  1 | SIMPLE      | orders   | ref   | product_id    | product_id | 4       | const |    2 | Using index                     | 
+----+-------------+----------+-------+---------------+------------+---------+-------+------+---------------------------------+


ここで問題なのが、products テーブルの欄に出ている「Using temporary; Using filesort」。これは本来不要なソートなはず。
その理由は次の通り。

  • products テーブルのname 属性にはユニークキー制約がかかっているので、「name = 'ipod'」 に一致するレコードは一つしかない
  • よって結合する際には「product_id = 1」となるレコードをproducts テーブルから探せばいい
    • この動作に関する説明は、ここが分かりやすい。。要約すると、JOIN を含むこの例のクエリの動作は次のようになる
      • まず「name = 'ipod'」となるレコードをproducts テーブルから探す。前述の通り、この条件にあてはまるレコードは1つ
      • 次に、上の結果のレコードに対してorders テーブルのレコードがフェッチされる。よって、orders テーブルから「product_id = 1」となるレコードが全て探索される
  • 最後にordered_on でソートするが、orders テーブルには(product_id, ordered_on) という複合インデックスがあるので、product_id = 1 となるレコード郡は既にordered_on 順にソートされている
  • よってproducts テーブルのソートや、結合結果のテーブルを改めてソートする必要はない

回避策

この余分はソートは次のようにクエリを分割することで解決できる。

> select @product_id := id from products where name = 'ipod';
+-------------------+
| @product_id := id |
+-------------------+
|                 1 | 
+-------------------+

> select ordered_on from orders where product_id = @product_id order by ordered_on;
+------------+
| ordered_on |
+------------+
| 2009-01-01 | 
| 2009-01-12 | 
| 2009-01-13 | 
+------------+


EXPLAIN を見てみる。

explain select @product_id := id from products where name = 'ipod';
+----+-------------+----------+-------+---------------+------+---------+-------+------+-------+
| id | select_type | table    | type  | possible_keys | key  | key_len | ref   | rows | Extra |
+----+-------------+----------+-------+---------------+------+---------+-------+------+-------+
|  1 | SIMPLE      | products | const | name          | name | 122     | const |    1 |       |
+----+-------------+----------+-------+---------------+------+---------+-------+------+-------+

> explain select ordered_on from orders where product_id = @product_id order by ordered_on;
+----+-------------+--------+------+---------------+------------+---------+-------+------+--------------------------+
| id | select_type | table  | type | possible_keys | key        | key_len | ref   | rows | Extra                    |
+----+-------------+--------+------+---------------+------------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | orders | ref  | product_id    | product_id | 4       | const |    2 | Using where; Using index |
+----+-------------+--------+------+---------------+------------+---------+-------+------+--------------------------+


クエリを分けたので、ソートは発生しない。
一般的にはこのようにクエリを分割した方が、余分なソートを行うより速いと書かれている。(実際に問題に直面した時はベンチをとる必要があるけど)

考察：何故余分なソートが発生するのか

ここからは完全に自分の考えです。

仮説1：最初にテーブルを結合してからwhere やorder が行われる

最初に考えたのはこれです。つまり、ここで説明した通りの動作をせず、次のような手順でクエリが実行される仮説。

  • まず一番最初に結合を行う。つまり、products テーブルの各レコードが orders テーブルの全てのレコードに結合される
  • 次にwhere が適応される
  • 最後に結合されたテーブルに対してorder by が行われる


違う気がする。最初に結合を行うというのは効率が悪すぎる。それに、最初に結合テーブルを作成して、そのテーブルに対してwhere で結果を絞るなら、orders テーブルの方でもインデックスは使えないと思う。でも、ここではインデックスが使われている。
この仮説は違うっぽい。

仮説2：JOIN のフェッチを行う際には結合元テーブルのユニーク制約情報を考慮しない

そもそも今回のクエリでソートが不要なのは、products.name にユニーク制約がかかっているから。

もしユニーク制約がかかっていなかったらソートが必要になる。「name = 'ipod'」となるproducts のレコードが2つあるとすれば、それらは違うid を持つ。orders テーブルのインデックスは、同じproduct_id のレコード郡はordered_on に基づいてソートされていることを保証するが、異るproduct_id のレコード郡の間でordered_on に基づいてソートされている保証はない(当然だけど)。


このことを踏まえて考えてみると、MySQL はJOIN のフェッチを起こなう際には結合元テーブルのユニーク制約情報を考慮しないように思える。仮に考慮していればこのようにソートが不要なことを判断できる。


この解釈でいいのだろうか。order by が含まれるクエリの動作には毎回悩む。MySQL のソースを読めればいいのだけれど…そのあたりはまだ勉強不足(i_i)

*1:products.price とか