クラスタインデックス
InnoDB はクラスタインデックスという構造となっており、データがインデックスのリーフノード上に格納されている。クラスタインデックスのキーとしては、通常は主キーもしくは一番始めの NULL を含まないユニークキーとなるが、それらが存在しない場合は暗黙的な 48 ビットの ROWID が主キーとして用いられるようになっている。なお、この ROWID はサーバ内でグローバルなカウンターから値が取得される。
クラスタインデックスの模式図を以下に示す。
上の図は高さが 3 の B+ ツリーとなる。同じサイズのページ単位でデータが管理されており、根ノードから順にページをたどることで目的のデータへ行き当たる。末端のノードはリーフノードと呼ばれ、インデックスを検索した際に最終的に行き着く先となる。それ以外のノードはノンリーフノードと呼ばれる。
クラスタインデックスではデータがリーフノードのエントリ内に格納されており、インデックスを検索すればすぐに行データにたどり着けるようになっている。別途データが格納されている別の領域へアクセスする必要なく、主キーによる検索は効率が良い。またノード内の書くエントリは双方向リンクリストになっていて、ページ内の検索はリストをたどって行われる。InnoDB ではページ内でデータをソートしておらず、空きがあったら使うようになっているため、ページ内部では順番に並んでいないためである。
クラスタインデックスの利点は主キーの検索効率の良さとなる。リーフノードまで到達すれば、さらに追加でデータ領域にアクセスする必要はない。また、データは全て主キーの順に行スキャンをするのが得意となる。欠点としてはセカンダリインデックスを用いた場合で、セカンダリインデックスを使った検索の処理は、まずセカンダリインデックスから主キーの値が取得され、その後主キーからデータが取得されるという流れとなり、インデックスの検索が 2 回発生するため、独立したデータ領域に行データが格納されているときよりも効率が悪い。そのため、InnoDB ではカヴァリングインデックスにすることで、検索速度が改善するという傾向が見られる。
カヴァリングインデックスとは、セカンダリインデックスのリーフにアクセスするだけでクエリが解決できる (目的のデータが取得できる) ようなケースのことである (決して InnoDB の機能とかではない) 。
以下のようなテーブルを考える。
mysql> CREATE TABLE foo (id INT PRIMARY KEY AUTO_INCREMENT, type INT, price INT, data1 INT, data2 INT, data3 INT);
Query OK, 0 rows affected (0.02 sec)
mysql> INSERT INTO foo (type, price) VALUES (1, 100);
Query OK, 1 row affected (0.00 sec)
mysql> INSERT INTO foo (type, price) VALUES (2, 200);
Query OK, 1 row affected (0.00 sec)
mysql> INSERT INTO foo (type, price) VALUES (3, 300);
Query OK, 1 row affected (0.01 sec)
mysql> INSERT INTO foo (type, price) VALUES (4, 400);
Query OK, 1 row affected (0.00 sec)
mysql> INSERT INTO foo (type, price) VALUES (5, 500);
Query OK, 1 row affected (0.01 sec)
mysql> INSERT INTO foo (type, price) SELECT type, price FROM foo;
Query OK, 5 rows affected (0.00 sec)
Records: 5 Duplicates: 0 Warnings: 0
mysql> INSERT INTO foo (type, price) SELECT type, price FROM foo;
Query OK, 10 rows affected (0.00 sec)
Records: 10 Duplicates: 0 Warnings: 0
...
mysql> INSERT INTO foo (type, price) SELECT type, price FROM foo;
Query OK, 2621440 rows affected (12.89 sec)
Records: 2621440 Duplicates: 0 Warnings: 0
mysql> SELECT COUNT(*) FROM foo;
+----------+
| COUNT(*) |
+----------+
| 5242880 |
+----------+
1 row in set (1.37 sec) ここで、インデックスを使わず type ごとの price の合計を出してみる。
mysql> SELECT type, SUM(price) FROM foo GROUP BY type;
+------+------------+
| type | SUM(price) |
+------+------------+
| 1 | 104857600 |
| 2 | 209715200 |
| 3 | 314572800 |
| 4 | 419430400 |
| 5 | 524288000 |
+------+------------+
5 rows in set (3.32 sec) ここで、type のインデックスを作成して、同一のクエリを叩いてみる。
mysql> ALTER TABLE foo ADD INDEX (type);
Query OK, 0 rows affected (12.58 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> SELECT type, SUM(price) FROM foo GROUP BY type;
+------+------------+
| type | SUM(price) |
+------+------------+
| 1 | 104857600 |
| 2 | 209715200 |
| 3 | 314572800 |
| 4 | 419430400 |
| 5 | 524288000 |
+------+------------+
5 rows in set (3 min 29.51 sec) むしろ遅くなった。
mysql> EXPLAIN SELECT type, SUM(price) FROM foo GROUP BY type;
+----+-------------+-------+------------+-------+---------------+------+---------+------+---------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+------+---------+------+---------+----------+-------+
| 1 | SIMPLE | foo | NULL | index | type | type | 5 | NULL | 5232592 | 100.00 | NULL |
+----+-------------+-------+------------+-------+---------------+------+---------+------+---------+----------+-------+
1 row in set, 1 warning (0.00 sec) これはセカンダリインデックスの type が用いられ、type のリーフに price が含まれないが故に、type のリーフから主キーを取得 -> クラスターインデックスのリーフから price を取得しようとしたことにより、Disk I/O が激しくなったことにより発生している。
今欲しいのは type 及び price なので、インデックスを追加してあげれば良い。
mysql> ALTER TABLE foo ADD INDEX (type, price);
Query OK, 0 rows affected (19.92 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> SELECT type, SUM(price) FROM foo GROUP BY type;
+------+------------+
| type | SUM(price) |
+------+------------+
| 1 | 104857600 |
| 2 | 209715200 |
| 3 | 314572800 |
| 4 | 419430400 |
| 5 | 524288000 |
+------+------------+
5 rows in set (1.45 sec) セカンダリインデックスのリーフに price が含まれるようになったため、クラスターインデックスのリーフにアクセスする必要がなくなり、クエリが劇的に高速化していることがわかる。