unoh.github.com by unoh

komagataです。

Webアプリケーションのパフォーマンスの大半はデータベース、特にインデックスの使われ方にかかっている気がします。

仕事でもMySQLをよく使いますが、MySQLでは１テーブルに付き１インデックスしか使われません。PostgreSQLなどと比べてそのことが気になってMySQLでのパフォーマンスチューニングに全く自信が持てませんでした。

オライリーの実践ハイパフォーマンスMySQLには下記のように書かれています。

実際、UNIONを除き、MySQLでは、１つのクエリを実行するとき、１つのテーブルに付き１つのインデックスしか使用できない。この事実は、繰り返し述べるに値するほど重要である。「MySQLでは、１つのクエリを実行するとき、１つのテーブルにつき１つのインデックスしか使用できないのである。」

また、その制約を考えたクエリの書き方として下記の様に書いてあります。

mysql> EXPLAIN SELECT * FROM Headline
    -> WHERER ExpireTime >= 1012201600 OR Id <= 5000000
    -> ORDER BY ExpireTime ASC LIMIT 10\G
何と、MySQLは完全なテーブルスキャンを実行すべきだと判断してしまった。（中略）このようなクエリを、UNIONを使用して書き換えることができる。そのためには、クエリを２つのクエリに分解し、それぞれのクエリで１つのインデックスを使用する。その後で、結果を結合してソートする。つまり、以下のようなクエリを実行すればよい。
(SELECT * FROM Headline WHERE ExpireTime >= 1081020749
ORDER BY ExpireTime ASC LIMIT 10)
 
UNION
 
(SELECT * FROM Headline WHERE Id <= 50000
ORDER BY ExpireTime ASC LIMIT 10)
 
ORDER BY ExpireTime ASC LIMIT 10

こんな簡単なクエリでわざわざこんなことしなくちゃいけないのかよと思いました・・・。しかし本書はMySQL 4.0.14をベースにかかれていています。MySQLユーザー的には常識なのかもしれませんがMySQL 5.0からはインデックス結合という機能があるそうです。１テーブル１インデックス問題（勝手にそう呼んでいる）が解決するかもしれないと思って調べてみました。インデックス結合とはその名の通り複数のインデックスを結合して結果を返してくれるそうです。EXPLAINのtypeフィールドではindex_mergeというメソッド名で表されます。マニュアルに拠ればインデックス結合には3つのアルゴリズムがありそれぞれEXPLAINのExrtaフィールドで確認できます。（Using～というやつ）そしてそれぞれのアルゴリズムは下記のような時に選ばれるそうです。

共通集合アルゴリズム --- Using intersect(...)
WHERE節で異なるインデックスをANDでつないだ時。
ユニオンアクセスアルゴリズム --- Using union(...)
WHERE節で異なるインデックスをORでつないだ時。
ソートユニオンアクセスアルゴリズム --- Using sort_union(...)
WHERE節で異なるインデックスをORでつないだ時でソートが必要な時。（前述のUNIONしなければならない例はこれに該当するんじゃないでしょうか）

結合方法自体OPTIMIZERが選択するので必ず使われるわけではありません。実際の効果の程を試してみました。試した環境： Debian etch MySQL 4.1.22, MySQL 5.0.32 テーブル：

CREATE TABLE `employees` (
  `id` int(11) NOT NULL auto_increment,
  `name` varchar(32) default NULL,
  `age` int(11) default NULL,
  PRIMARY KEY  (`id`),
  KEY `index_name` (`name`),
  KEY `index_age` (`age`)
)

テストデータ（ランダムなデータ10万件)：

#!/usr/bin/env ruby
 
100000.times do |i|
  puts "INSERT INTO employees (name, age) VALUES ('name_#{rand(100)}', #{rand(100)});"
end

テストデータを投入し、ANALYZE TABLEした後のインデックスは下記の通りです。

mysql> SHOW INDEX FROM employees\G
*************************** 1. row ***************************
       Table: employees
  Non_unique: 0
    Key_name: PRIMARY
Seq_in_index: 1
 Column_name: id
   Collation: A
 Cardinality: 160673
    Sub_part: NULL
      Packed: NULL
        Null:
  Index_type: BTREE
     Comment:
*************************** 2. row ***************************
       Table: employees
  Non_unique: 1
    Key_name: index_name
Seq_in_index: 1
 Column_name: name
   Collation: A
 Cardinality: 53557
    Sub_part: NULL
      Packed: NULL
        Null: YES
  Index_type: BTREE
     Comment:
*************************** 3. row ***************************
       Table: employees
  Non_unique: 1
    Key_name: index_age
Seq_in_index: 1
 Column_name: age
   Collation: A
 Cardinality: 99
    Sub_part: NULL
      Packed: NULL
        Null: YES
  Index_type: BTREE
     Comment:
3 rows in set (0.00 sec)

この条件でMySQL 4.1.22, 5.0.32それぞれで上記のアルゴリズムが使われた場合（5.0.32）と使われない場合（4.1.22）でEXPLAIN結果と速度を計りました。

・共通集合アルゴリズム

MySQL 4.1.22の場合：

mysql> EXPLAIN SELECT * FROM employees WHERE name = "name_1" AND age = 1\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: employees
         type: ref
possible_keys: index_name,index_age
          key: index_name
      key_len: 33
          ref: const
         rows: 571
        Extra: Using where
1 row in set (0.00 sec)

普通にインデックスが一つだけ使われました。

MySQL 5.0.32の場合：

mysql> EXPLAIN SELECT * FROM employees WHERE `name` = 'name_1' AND `age` = 1\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: employees
         type: index_merge
possible_keys: index_name,index_age
          key: index_age,index_name
      key_len: 5,99
          ref: NULL
         rows: 5
        Extra: Using intersect(index_age,index_name); Using where
1 row in set (0.01 sec)

typeにindex_merge、ExtraにUsing intersect(index_age,index_name)と出ました。共通集合アルゴリズムを使って別々のインデックスがマージされて使われているようです。

実際の速度：

mysql> SELECT SQL_NO_CACHE * FROM employees WHERE `name` = 'name_1' AND `age` = 1;

インデックス結合無し（MySQL 4.1.22）：0.01 sec
インデックス結合有り（MySQL 5.0.32）：0.01 sec

・ユニオンアクセスアルゴリズム

MySQL 4.1.22の場合：

mysql> EXPLAIN SELECT SQL_NO_CACHE * FROM employees WHERE `name` = 'name_1' OR `age` = 1\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: employees
         type: ALL
possible_keys: index_name,index_age
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 100000
        Extra: Using where
1 row in set (0.01 sec)

対象レコードが多いのでALLになりました。

MySQL 5.0.32の場合：

mysql> EXPLAIN SELECT SQL_NO_CACHE * FROM employees WHERE `name` = 'name_1' OR `age` = 1\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: employees
         type: index_merge
possible_keys: index_name,index_age
          key: index_name,index_age
      key_len: 99,5
          ref: NULL
         rows: 2749
        Extra: Using union(index_name,index_age); Using where
1 row in set (0.00 sec)

typeにindex_merge、ExtraにUsing union(index_name,index_age)と出ました。ユニオンアクセスアルゴリズムを使って別々のインデックスがマージされて使われているようです。

実際の速度：

mysql> SELECT SQL_NO_CACHE * FROM employees WHERE `name` = 'name_1' OR `age` = 1;

インデックス結合無し（MySQL 4.1.22）：0.13 sec
インデックス結合有り（MySQL 5.0.32）：0.02 sec

・ソートユニオンアクセスアルゴリズム

MySQL 4.1.22の場合：

mysql> EXPLAIN SELECT SQL_NO_CACHE * FROM employees WHERE `name` = 'name_1' AND `age` < 5\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: employees
         type: ref
possible_keys: index_name,index_age
          key: index_name
      key_len: 33
          ref: const
         rows: 571
        Extra: Using where
1 row in set (0.01 sec)

普通にインデックスが一つだけ使われました。

MySQL 5.0.32の場合：

mysql> EXPLAIN SELECT SQL_NO_CACHE * FROM employees WHERE `name` = 'name_1' OR `age` < 5\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: employees
         type: index_merge
possible_keys: index_name,index_age
          key: index_name,index_age
      key_len: 99,5
          ref: NULL
         rows: 11537
        Extra: Using sort_union(index_name,index_age); Using where
1 row in set (0.00 sec)

typeにindex_merge、ExtraにUsing sort_union(index_name,index_age)と出ました。ソートユニオンアクセスアルゴリズムを使って別々のインデックスがマージされて使われているようです。

実際の速度：

mysql> EXPLAIN SELECT SQL_NO_CACHE * FROM employees WHERE `name` = 'name_1' OR `age` < 5;

インデックス結合無し（MySQL 4.1.22）：0.15 sec
インデックス結合有り（MySQL 5.0.32）：0.07 sec

大抵の場面で複数のインデックスを結合してクエリが速くなることがわかりました。これらの条件はとりたてて特殊なものではないので速くなる場面は多そうです。MySQL 5.0以上に乗り換えた再に無自覚に効果が出ているかもしれませんが、MySQL 4.1系以前とは違ってこのインデックス結合を意識したインデックス設計は大事だと思います。

個人的にこの１テーブル１インデックス問題はずっと気になっていて、他のRDBに乗り換えようかな、などと考えていたんですが、このインデックス結合をみてMySQLで頑張ってみようという気になりました。

※追記
「複合インデックスと名前が紛らわしい」、「例題が悪い」との指摘を受けました。確かにその通りだと思いました。それとPostgreSQLのEXPLAINで出てくる様なMerge自体のコストも気になるところです。追って調べていきたいと思います。