インデックスと B-⁠tree

索引が効かないのはどんなときか

索引は、探す列の値の並びをたどれるときにだけ効きます。並びを使えない探し方、選ぶ行が多い問い合わせ、書き込みの多い表では、索引は効かないか、かえって損になります。

先頭の列を使わない検索

2 つの列をまとめた複合索引は、1 つ目の列の順に並び、同じ値の中で 2 つ目の列の順に並びます。電話帳が姓の順、同じ姓の中で名の順に並ぶのと同じです。

MySQL の公式文書は、(col1, col2, col3) の索引で引けるのは、col1、col1 と col2、3 つ全部のように左端から続く組だけだと書いています。PostgreSQL 18 の公式文書は、先頭の列の値の種類がとても少ないときに限り、先頭の値ごとに引き直す「スキップスキャン」を使うことがあると書いています。種類が多ければ、たいていは表を全部読むほうを選びます。

次のコードは、(店, 日) の順に並べた索引で、店 3 だけを探す場合と、日 7 だけを探す場合を比べます。出力は左から、行数、店で引いて読んだ行、日で引くために並びを使わず読んだ行、店ごとに引き直した回数、当たった行の数です。

(10000, 1000, 10000, 10, 10)
(10000, 10, 10000, 1000, 1000)

店が 10 軒なら、店 3 は当たる 1000 行だけを読み、日 7 は店ごとに 10 回引き直せば 10 行が見つかります。店が 1000 軒になると引き直しは 1000 回で、当たる行も 1000 行です。1 万行の中で 1000 回も木を降りるなら、全部を読むのと大きく変わりません。

列に関数をかけた条件も、並びを使えません。PostgreSQL の公式文書は、lower(col1) で比べたいなら lower(col1) そのものに索引を作れば使えると書き、その索引は行を入れるたびに式を計算するので保つ手間が大きいとも書いています。

選ぶ行が多い問い合わせ

選ぶ行が多いと、索引をたどるより表を全部読むほうが速くなります。索引で見つけた行は表のあちこちの頁に散っていて、1 行ごとに別の頁を読むことになるからです。

次のコードは、100 万行、1 頁に 100 行の表で、当たる行の割合を変えて、読む頁の数を比べます。当たる行はどれも別の頁にある、いちばん悪い場合で数えます。最後の 4 行は、1000 行を足すときに書く頁の数で、行を入れる頁 1 枚に、索引ごとの葉の頁 1 枚が足されると数えます。

全件 10000
0.01 100 103 索引
0.1 1000 1003 索引
1 10000 10003 全件
2 20000 20003 全件
10 100000 100003 全件
索引 0 本 1000
索引 1 本 2000
索引 3 本 4000
索引 5 本 6000

表を全部読むと 10000 頁です。当たる行が 0.1% (1000 行) なら索引で 1003 頁と少なく済みますが、1% (1 万行) で 10003 頁になり、全件読みが勝ちます。MySQL の公式文書も、ほとんどの行を読む問い合わせでは、索引をたどるより順に読むほうが速いと書いています。

実際のデータベースは行の置かれ方や統計も見て決めるので、境目は 1% ちょうどではありません。分かるのは、選ぶ行が増えるほど索引の得が消えることです。

書き込みが遅くなる

索引を足すと、行を入れたり直したりするたびに索引も直すので、書き込みが重くなります。上のコードでは、索引が 0 本なら 1000 頁、5 本なら 6000 頁を書きました。

PostgreSQL の公式文書は、索引を作ったら表と合わせ続ける手間がかかるので、ほとんど使われない索引は消すべきだと書いています。