【図解】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)というカラム順の複合インデックスにおける、検索条件とレコードの絞り込み範囲の対応は以下の通りです。

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

列順を決める原則 — 「最も選択性の高い列を先頭に」は誤り

複合インデックスの列順については、「最も選択性の高い列（カーディナリティが高い列）を先頭にする」という指針がよく知られていますが、これは正しくありません（Use The Index, Luke! - 複合インデックス）。

正しい指針は「アプリケーションのWHERE句で利用される組み合わせを最大限カバーできる列順にする」です。具体的には以下の優先順位で列順を決めます。

1. 単独で検索条件に利用される頻度が高い列を先頭にする — 先頭列がWHEREに含まれない検索ではインデックスが利用されないため、最も多くのクエリがインデックスを使えるようにする
2. 等価条件（=）で使われる列を、範囲条件（<, >, BETWEEN, LIKE 'A%'）で使われる列より前に置く — B-treeでは範囲条件の列以降は走査対象が広がりインデックスとして機能しなくなるため
3. 同条件内ならカーディナリティの高い列を先に置く — 上記の制約を満たした上での最適化として有効

カーディナリティ単独で列順を決めると、「先頭列がWHEREに含まれないためインデックスがそもそも使われない」という状況が発生します。インデックスは『使われてナンボ』であり、選択性の最適化はその次の問題です。

アクセス述語とフィルタ述語

複合インデックスの動作を正確に理解するには、検索条件をアクセス述語（access predicate）とフィルタ述語（filter predicate）に区別する必要があります。

• アクセス述語: B-treeを走査する範囲を決める条件。インデックスを「絞り込み」に使う
• フィルタ述語: 走査範囲は変えないが、走査中に行を捨てるかを判定する条件

たとえば(last_name, first_name)というインデックスに対してWHERE last_name = 'Abbott' AND first_name LIKE 'A%'を実行した場合、両方ともアクセス述語として機能します。

一方、WHERE last_name = 'Abbott' AND age = 30の場合、last_name = 'Abbott'はアクセス述語ですが、age = 30はフィルタ述語です（インデックスに含まれていないため、テーブルを参照して行ごとに判定する）。

範囲条件の列以降は、すべてフィルタ述語に変わります。たとえば(a, b, c)というインデックスに対してWHERE a = 1 AND b > 10 AND c = 5を実行すると、アクセス述語はa = 1 AND b > 10までで、c = 5はフィルタ述語になります。b > 10を満たすすべての枝に対してc = 5を判定する必要があるため、cの絞り込みはインデックスでは効きません。

PostgreSQLではEXPLAIN (ANALYZE, BUFFERS)のIndex Cond:がアクセス述語、Filter:がフィルタ述語に対応します。MySQL 8.0以降はEXPLAIN FORMAT=TREEでアクセス述語と類似情報が確認できます。詳細はUse The Index, Luke! - 大なり、小なり、BETWEENを参照してください。

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

インデックスの構造はカラムがソートされた状態であるため、ソートに関する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	否

補足: MySQL 8.0以降は降順インデックスがサポートされている

MySQL 8.0未満では、インデックスの内部構造が常に昇順であり、ASCとDESCを混在させたORDER BYではインデックスが利用できませんでした（filesortが走る）。

MySQL 8.0以降は降順インデックス（descending index）がサポートされ、列ごとに昇順・降順を指定して作成できるようになりました（MySQL 8.0 リファレンス - 降順インデックス）。

-- MySQL 8.0以降
CREATE INDEX idx_users_mixed ON users(last_name DESC, first_name ASC);

このインデックスがあれば、ORDER BY last_name DESC, first_name 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;

*************************<strong> 1. row </strong>*************************
           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;

*************************<strong> 1. row </strong>*************************
           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)やってます。フォローしてもらえるとうれしいです！

参考

• 達人に学ぶDB設計 徹底指南書
• SQL実践入門
• エキスパートのためのMySQL【運用+管理】トラブルシューティングガイド
• MySQLでクエリチューニングことはじめ
• インデックスとは
• 大なり、小なり、BETWEEN
• 3.3.2　単一列インデクスと複数列インデクスの使い分け
• 複合インデックス
• SQLアンチパターンとBtreeインデックスの関連性
• 単一列インデクスと複数列インデクスの使い分け