乐胖代购免代理版

こんにちは、サービス開発部の荒引 (@a_bicky) です。

突然ですが、RDBMS の既存のテーブルを見てみたら「何でこんなにインデックスだらけなの？」みたいな経験はありませんか？不要なインデックスは容量を圧迫したり、挿入が遅くなったりと良いことがありません。

そんなわけで、今回はレコードを検索するために必要なインデックスの基礎知識と、よく見かける不適切なインデックスについて解説します。クックパッドでは Rails のデータベースとして主に MySQL 5.6、MySQL のストレージエンジンとして主に InnoDB を使っているので、MySQL 5.6 の InnoDB について解説します。

InnoDB のインデックスに関する基礎知識

インデックスの構造 (B+ 木)

InnoDB では B+ 木が使われています。B+ 木は次のような特徴を持った木構造です。

次数を b とすると、各内部ノード（葉ノード以外のノード）は最大 b - 1 個のキーと最大 b 個の子ノードを持つ*1
内部ノードは値を持たない
葉ノードの各キーは値（または値へのポインタ）を持つ
葉ノードは次の葉ノードへのポインタを持つ
$O(\log_bn)$ で検索できる

次の図は次数 3 の例です。

f:id:a_bicky:20170417093420p:plain:w552

例えば、key が 4 の value を取り出すには次のように木を辿れば良いです。

f:id:a_bicky:20170417093427p:plain:w440

key が 2 〜 9 の value を全て取り出すには次のように木を辿ることができます。葉ノード間が繋がっていることによって範囲検索を効率的に行うことができます。

f:id:a_bicky:20170417093430p:plain:w440

InnoDB の B+ 木では、インデックスに使われているカラムの値と主キーの値が value に格納されています。

ここで (c1, c2) のような複合インデックスを考えてみます。イメージとしては次のような構造になります。例えば、key の上位 4 bytes を c1 に割り当て、下位 4 bytes を c2 に割り当てるイメージです。

f:id:a_bicky:20170418083840p:plain:w440

図からわかるように、c2 = 2 に対応するインデックスレコードを探そうとしても、c1, c2 の順番で並んでいるので、木を辿ることで探すことはできません。c1 = 4 AND c2 = 2 のように c1 の条件が指定されることで木を辿ることができるようになります。

また、c1 >= 2 AND c2 <= 4 のような条件の場合、c1 >= 2 の条件を満たすインデックスレコードは木を辿ることで探せますが、それらのインデックスレコードを更に c2 <= 4 の条件で絞り込むために木を利用することはできません。具体的には、図の例だと [7,5] が条件を満たさないインデックスレコードですが、その隣の [9,3] が条件を満たすかどうかはわからないですよね。結局のところ、c1 >= 2 のインデックスレコード全てを走査しないといけません。

よって、インデックスレコードの走査の数を減らす観点では c1 = 2 AND c2 <= 4 のように c1 の条件が等価比較になる場合に限って、複合インデックスとしての意味を持つことになります。*2

このことについては MySQL のドキュメントの 8.2.1.2 Range Optimization にも次のように言及されています。

The optimizer attempts to use additional key parts to determine the interval as long as the comparison operator is =, <=>, or IS NULL. If the operator is >, <, >=, <=, !=, <>, BETWEEN, or LIKE, the optimizer uses it but considers no more key parts.

InnoDB における B+ 木の実装について知りたい方は次の記事と言及されている関連記事を読むとかなり理解が深まると思います。

B+Tree index structures in InnoDB – Jeremy Cole

クラスタ化インデックスとセカンダリインデックス

InnoDB の主キーはクラスタ化インデックス (clustered indexes) になっており、B+ 木の葉ノードにレコードの全データが格納されています。特定のカラムに張るインデックスはセカンダリインデックスと呼ばれ、セカンダリインデックスの葉ノードには主キーが必ず含まれています。

セカンダリインデックスを使った検索は、まずセカンダリインデックスの B+ 木を辿って主キーを取得し、次にクラスタ化インデックスの B+ 木を辿ってレコードを取得することになります。

f:id:a_bicky:20170417093437p:plain:w440

セカンダリインデックスに必要な情報が全て格納されていれば、クラスタ化インデックスを辿る手順をスキップすることができるので高速です。このようにレコードを取得する際にセカンダリインデックスで完結する場合のことをカバリングインデックスと呼びます。

MySQL がレコードを取得する大まかな手順

MySQL がレコードを取得する際の主要な登場人物として、executor*3 と storage engine (e.g. InnoDB) がいます。

storage engine が InnoDB の場合は次のようにレコードを取得します。

executor が storage engine にレコードを要求する
storage engine (InnoDB) はセカンダリインデックスの木を辿ることで、取得すべきレコードのインデックスに含まれているカラム値と主キーの値を得る
- インデックスが使えない場合はクラスタ化インデックスに含まれている全レコード情報を executor に返す
storage engine は 2 で得たデータのうち、インデックスに含まれているカラム値の情報を使って取得すべきレコードをフィルタリングする (Using index condition)
- インデックスに含まれている情報が使えない場合はスキップ
storage engine は 3 で得たデータの主キー情報を使ってクラスタ化インデックスからレコードを取得する
- SELECT で指定されているカラムや WHERE で指定されているカラムの情報が全てインデックスに含まれている場合はスキップ (Using index)
storage engine は取得したレコード情報を executor に返す
executor は storage engine がフィルタリングできなかったレコードをフィルタリングする (Using where)
- storage engine 側で全てフィルタリングされている場合はスキップ

「雑なMySQLパフォーマンスチューニング」はこの辺の内容をわかりやすく説明しているので、ピンとこなければ読むことをお勧めします。

以上の説明で、Explain で extra に Using index, Using index condition, Using where が出る場合にどのような処理が行われているかイメージが付くと思います。 Using index condition が出る場合は ICP (Index Condition Pushdown) 最適化と呼ばれ、MySQL 5.6 から導入されました。これによって、クラスタ化インデックスから取得するレコードが減るのでその分高速になります。c1 >= 2 AND c2 <= 4 のような条件のために (c1, c2) の複合インデックスを張っても意味がないと前述しましたが、ICP の恩恵を受けてパフォーマンスが改善する場合もあります。

インデックスを張る上でのポイント

インデックスを張る上では次のような内容がポイントになると思います。

インデックスで絞り込めるレコード数が大きいか？（選択性が高いか？）
- WHERE c1 = 1 AND c2 = 2 AND c3 = 3 AND c4 = 4 みたいな条件があるからといって、(c1, c2, c3, c4) の複合インデックスが必要とは限らない
- c1 で十分絞りこめるのに他のカラムもインデックスに含めるとインデックスが肥大化する
複合インデックスを張る場合
- 絞り込めるレコード数の大きいカラムを先にしているか？
- 等価比較するカラムが先になっているか？
カバリングインデックスの恩恵を十分に受けられるか？
ICP の恩恵を十分に受けられるか？
ソートに使うか？*4

不適切なインデックスの例

これまでに説明した内容がわかっていると、以下に挙げる内容が不適切なインデックスだとわかるはずです。

インデックスの最初のカラムに範囲指定をする複合インデックス
選択性の悪いインデックス
他のインデックスで代替できるインデックス

具体例を挙げるために、次のようなテーブルを扱うことにします。商品情報を管理するテーブルで、現在以降に掲載される商品の情報が日々追加されていく想定です。

CREATE TABLE `products` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `shop_id` int(10) unsigned NOT NULL,  -- 商品を掲載している店舗の ID
  `name` varchar(255) NOT NULL,         -- 商品名
  `price` int(10) unsigned NOT NULL,    -- 商品の価格
  `starts_at` datetime NOT NULL,        -- 商品の掲載開始日時
  `ends_at` datetime NOT NULL,          -- 商品の掲載終了日時
  PRIMARY KEY (`id`)
) ENGINE=InnoDB

それでは具体例を見ていきます。

インデックスの最初のカラムに範囲指定をする複合インデックス

次のインデックスが定義されているとします。

ALTER TABLE products ADD INDEX ix_ends_at_starts_at (ends_at, starts_at);

これは、次のようなクエリに対処するために定義されたインデックスですが、ends_at 単一のインデックスを張るのとあまり変わりません。*5

-- 現在掲載されている商品を抽出する
SELECT * FROM products WHERE starts_at <= NOW() AND ends_at >= NOW();

この理由は次のような B+ 木をイメージするとわかりやすいです。この木は (c1, c2) に対して構築された B+ 木ですが、c1 >= 2 AND c2 <= 5 のような条件でレコードを引こうと思った場合にインデックスレコードを走査する数が減りません。例えば、[2,8] のインデックスレコードが c2 の条件を満たしませんが、その隣の [3,1] が c2 の条件を満たすかどうかは木の構造から判断できず、c1 >= 2 のインデックスレコードを全て走査することになります。

f:id:a_bicky:20170418084900p:plain:w440

MySQL 5.6 では前述した ICP 最適化という仕組みがあるので、starts_at >= NOW() での絞り込みで劇的にレコードが減るようであれば、ICP の恩恵を受けられるかもしれません。

ICP の効果は session status の Handler_read_next の値がどれだけ変わるかを見てみるのが良いでしょう。この値が少ないほどインデックスレコードの走査が少ないことを意味します。

-- ICP 有効
FLUSH STATUS;
SET @@optimizer_switch = "index_condition_pushdown=on";
SELECT * FROM products WHERE starts_at <= NOW() AND ends_at >= NOW();
SHOW SESSION STATUS LIKE 'Handler%';

-- ICP 無効
FLUSH STATUS;
SET @@optimizer_switch = "index_condition_pushdown=off";
SELECT * FROM products WHERE starts_at <= NOW() AND ends_at >= NOW();
SHOW SESSION STATUS LIKE 'Handler%';

ICP の効果が低いと判断したら、ix_ends_at_starts_at は削除して単一のインデックスを張りましょう。

ALTER TABLE products DROP INDEX ix_ends_at_starts_at,
  ADD INDEX ix_ends_at (ends_at);

似たような例として、次のようなインデックスを考えます。

ALTER TABLE products ADD INDEX ix_ends_at_shop_id (ends_at, shop_id);

これは、次のようなクエリに対処するために定義されたインデックスですが、同様に ends_at 単一のインデックスを張るのとあまり変わりません。

-- shop_id = 1234 の店舗の現在掲載される商品を抽出する
SELECT * FROM products WHERE shop_id = 1234 AND starts_at <= NOW() AND ends_at >= NOW();

shop_id は等価比較で使う前提なので、(shop_id, ends_at) の順番でインデックスを張ることで複合インデックスとしての恩恵が得られます。

ALTER TABLE products DROP INDEX ix_ends_at_shop_id,
  ADD INDEX ix_shop_id_ends_at (shop_id, ends_at);

選択性の悪いインデックス

次のインデックスが定義されているとします。

ALTER TABLE products ADD INDEX ix_shop_id_starts_at (shop_id, starts_at);

これは、次のようなクエリに対処するために定義されたインデックスですが、選択性の観点で良くありません。

-- shop_id = 1234 の店舗の現在掲載される商品を抽出する
SELECT * FROM products WHERE shop_id = 1234 AND starts_at <= NOW() AND ends_at >= NOW();

ix_shop_id_starts_at の選択性が良いかどうかはテーブルとクエリの特性次第ですが、products テーブルが現在以降に掲載される商品しか追加されず、過去に掲載されていた商品が残り続けるのであれば、starts_at <= NOW() という条件は該当レコードが日々増えていきます。一方で、ends_at >= NOW() は商品の増え方が一定であれば該当レコードの量は一定とみなせます。

よって、(shop_id, ends_at) にインデックスを張るべきです。

ALTER TABLE products DROP INDEX ix_shop_id_starts_at,
  ADD INDEX ix_shop_id_ends_at (shop_id, ends_at);

他のインデックスで代替できるインデックス

次のインデックスが定義されているとします。

ALTER TABLE products ADD INDEX ix_shop_id (shop_id),
  ADD INDEX ix_shop_id_ends_at (shop_id, ends_at);

これは次のような 2 種類のクエリに対処するために定義されたインデックスですが、ix_shop_id は冗長です。

-- shop_id = 1234 の店舗に掲載されたことがある、または掲載される予定の商品を全て抽出する
SELECT * FROM products WHERE shop_id = 1234;
-- shop_id = 1234 の店舗の現在掲載される商品を抽出する
SELECT * FROM products WHERE shop_id = 1234 AND starts_at <= NOW() AND ends_at >= NOW();

shop_id での絞り込みに特化したインデックスとして ix_shop_id を導入したと思われますが、次の 2 つの木を見れば ix_shop_id_ends_at が ix_shop_id の役割を包含していることは一目瞭然です。

f:id:a_bicky:20170417093440p:plain:w440

よって、ix_shop_id は削除すべきです。

ALTER TABLE products DROP INDEX ix_shop_id;

最後に

以上、MySQL (InnoDB) のインデックスについて簡単に解説しました。InnoDB について完璧に理解しようと思うと膨大な知識が必要ですが、よくある単純な用途でインデックスを張るだけであれば、必要とされる知識はほんの少しであることがわかると思います。本エントリーによって、世の中から不適切なインデックスだらけのテーブルが少しでもなくなれば幸いです。

*1:次数の解釈は文献によって異なるので、2017 年 4 月 17 日時点の Wikipedia に合わせています

*2:後述する ICP が効果を発揮する場合はその限りではありません

*3:executor を mysql server と表現している記事を見かけることがありますが、sql_executor.cc に実装されているので executor という表現の方が適切だと思います

*4:本エントリではソートには触れないので、興味のある方は「漢(オトコ)のコンピュータ道: Using filesort」を参照すると良いと思います

*5:Explain の key_len 的には starts_at も使われるように見えるので、ソースコードを読んでその理由を調べようと前々から思ってますが、未だに調査できてません…