複合インデックスはなぜ順番が大切なのか

Daily Blogging53日目

以前インデックスのアンチパターンの中で複合インデックスについて軽く触れた

また、クエリの条件式で使用する際は、複合インデックスの順番通りに記述しないと複合インデックスが採用されないので注意が必要。

なぜ複合インデックスの順番通りでないとダメなのか
このことについてちゃんと言語化して説明できなかったので改めて理由を調査した

インデックスはB-treeの構造で保存される

インデックスはインデックスファイルに、B-treeの構造で格納される。
例えばこういうテーブルがあったとして

id	カラムA
1	10
2	20
3	15
4	25
5	30

カラムAに対するインデックスを作成すると、インデックスファイルにはこんな感じのデータ構造で格納される。

      [20]  
      /    \  
  [10, 15]  [25, 30]

このとき、Aの値の昇順で格納されるよ
→昇順にすることで検索効率が上がる

複合インデックスの場合

id	カラムA	カラムB
1	10	5
2	10	3
3	15	4
4	20	1
5	20	2
6	20	3
7	25	1

上記のテーブルに対して、複合インデックス(カラムA, カラムB)を作成した場合、
インデックスファイルはこうなる

                  [ (15, 4) ]  
       　　　　　　　/       \  
 [ (10, 3), (10, 5) ]   [ (20, 1), (20, 2), (20, 3), (25, 1) ]

まずカラムAの値の昇順でソートされた後に、カラムBの値でソートする

インデックスは結果的に採用されないだけ

上記のデータに対して

SELECT * FROM users WHERE B = 3;

を実行した場合、
B = 3のデータが散らばっているため効率的に検索ができない
結局最初から順番にひとつひとつ確認しないと該当するデータに辿り着かないので、場合によってはフルスキャンの方が効率が高くなる可能性がある。
つまり、複合インデックスは使えないんじゃなくて、使ってもしょうがないので結果的に採用されないということ

目次で考えよう

本の目次で考えてみよう

先ほどの複合インデックス(カラムA,カラムB)を目次に例えてみる
A：章
B：節

例えば、「第２章の節を全部探そう」という場合、すぐに見つかりますね
目次のどこら辺に第２章についての記載があるかパッとわかります。

「第２章の第２節を探したい」という場合も目次のどの辺に書いているかすぐにわかります。

しかし、「第２節を探したい」という場合、目次の全てに目を通さないと全ての第２節を見つけることはできないです
→検索効率が悪い

わかりにくいか...?

複合インデックスが採用されるケース

使えるのは下記の２パターンの時

• カラムA,カラムBの順で指定した条件で絞る

SELECT * FROM users WHERE カラムA = 10 AND カラムB = 3;

• Aの値で条件を絞る

SELECT * FROM users WHERE A = 10