【図解】B-treeを理解し、複合インデックスの順番を正しく作る

データベース

複合インデックス（結合インデックス）とは複数のカラムを組み合わせたインデックスのことをいいます。
検索やソート条件で一緒に利用されるカラムに対して複合インデックスを作成することでクエリの高速化が期待できます。

複合インデックスを正しく作成するにはB-treeインデックスの理解が必須です。
今回は複合インデックスを正しく作成するために必要な基礎知識について紹介します。

複合インデックスには順序がある

ユーザーテーブルに存在するlast_name, first_name, ageのカラムに対して複合インデックスを作成する場合を考えてみます。

(last_name, first_name, age)の順で複合インデックスを作成した場合、インデックスの構造は以下のようになります。

(age, last_name, first_name)の順の場合は以下のようになります。

複合インデックスの構造は先頭のカラムから順にソートされた状態になっています。
ですので、同じカラムの組み合わせでも順番によって作成されるインデックスの構造は異なります。

検索条件と複合インデックスの利用可否について

複合インデックスのカラム順には意味があるため、検索条件の組み合わせによっては複合インデックスが利用されません。
(last_name, first_name, age)というカラム順の複合インデックスの場合、検索条件とインデックス利用可否の対応は以下の通りです。

検索条件 インデックスの利用可否
last_name 可
first_name 否
age 否
last_name, first_name 可
last_name, age 否
first_name, age 否

上記の理由は複合インデックスの構造をイメージするとわかりやすいです。

たとえばWHERE last_name = 'Auer'が検索条件の場合、複合インデックスを利用して以下の部分の絞り込みができます。

一方、WHERE first_name = 'Aaron'が検索条件の場合、複合インデックスをたどってうまく範囲が絞り込めません。

複合インデックスを作成する際は単独で検索条件に利用されるカラムを先頭にするとよいです。

複合インデックスによる絞り込みの範囲について

(last_name, first_name, age)というカラム順の複合インデックスにおける、検索条件とレコードの絞り込み範囲の対応は以下の通りです。

上記の結果からわかる通り、先頭のカラムで走査対象を絞り込むほど最終的な検索範囲を狭められます。

ですので、選択性に優れているカラムを複合インデックスの先頭にすると良いです。
具体的には、等価条件で利用されたりカーディナリティが高かったりするカラムを複合インデックスの先頭にすると良いです。

ソートの向きと複合インデックスの利用可否について

インデックスの構造はカラムがソートされた状態であるため、ソートに関するSQLもインデックスを利用して高速化できます。
ただし、ソートの向きによっては複合インデックスが利用されないため注意が必要です。

(last_name, first_name, age)というカラム順の複合インデックスの場合、ソートの向きとインデックス利用可否の対応は以下の通りです。

ORDER BY句 インデックスの利用可否
last_name ASC, first_name ASC, age ASC 可
last_name DESC, first_name DESC, age DESC 可
last_name DESC, first_name ASC, age ASC 否
last_name ASC, first_name ASC 可
last_name ASC, first_name ASC, age ASC, create_ad ASC 否

検索とソートを組み合わせたSQLと複合インデックス利用可否について

WHEREとORDERを組み合わせたSQLでも複合インデックスの利用は可能です。
(last_name, first_name, age)というカラム順の複合インデックスの場合、SQLとインデックス利用可否の対応は以下の通りです。

検索とソートのパターン インデックスの利用可否
WHERE last_name = ‘Abbott’ ORDER BY first_name, age 可
WHERE last_name like ‘A%’ ORDER BY first_name, age 可
WHERE last_name = ‘Abbott’ ORDER BY first_name 可
WHERE first_name = ‘Aaron’ ORDER BY last_name 否
WHERE first_name = ‘Aaron’ ORDER BY last_name limit 1 可(注)

以上の結果からわかるように、WHEREとORDERを組み合わせたSQLで有効に働く複合インデックスを作成する場合は『WHEREで利用されているカラム』『ORDERで利用されているカラム』の順にするとよいです。

『可（注）』のパターンに関する補足説明

WHERE first_name = 'Aaron' ORDER BY last_name limit 1では複合インデックスこそ使われますが、EXPLAINのtypeがindexであることからわかる通り、フルインデックススキャンです。
フルインデックススキャンはインデックス全体をスキャンする必要のある遅い処理ですので、改善の余地があるクエリです。

> EXPLAIN SELECT * FROM users WHERE first_name = 'Aaron' ORDER BY last_name ASC LIMIT 1\G;

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: users
   partitions: NULL
         type: index
possible_keys: NULL
          key: index_users_on_last_name_and_first_name_and_age
      key_len: 521
          ref: NULL
         rows: 1
     filtered: 10.00
        Extra: Using where
1 row in set, 1 warning (0.00 sec)

また、仮に複合インデックス以外にfirst_nameのインデックスが作成されていた場合、(last_name, first_name, age)の複合インデックスよりもfirst_nameのインデックスが優先して使われます。

> CREATE INDEX index_users_on_first_name ON users(first_name);

> EXPLAIN SELECT * FROM users WHERE first_name = 'Aaron' ORDER BY last_name ASC LIMIT 1\G;

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: users
   partitions: NULL
         type: ref
possible_keys: index_users_on_first_name
          key: index_users_on_first_name
      key_len: 258
          ref: const
         rows: 427
     filtered: 100.00
        Extra: Using index condition; Using filesort
1 row in set, 1 warning (0.00 sec)

EXPLAINの読み方の詳細解説はMySQLのEXPLAINの読み方とチューニング時のチェックポイントを参考にしてください。

まとめ

複合インデックス作成時のポイント
  • 単独で検索条件に利用されるカラムを先頭にする
  • 選択性に優れているカラムから順に指定する
  • 検索とソートが関係する複合インデックスは『検索のカラム、ソートのカラム』の順にする

Twitter(@nishina555)やってます。フォローしてもらえるとうれしいです！

参考

RECOMMEND