selectivity ごとにインデックスの効きを計測してみた
データベースのインデックスは「クエリ条件にマッチする行が、テーブル全体の何 % を占めるか」によって効きが変わるのかを、PostgreSQL で計測してみました。
計測方法
100 万行の orders テーブルを作り、user_id（0〜10万の整数）と status（4 種類の文字列）にそれぞれインデックスを貼ります。
selectivity が 0.001% 〜 33% になる範囲で 7 種類のクエリを用意し、Seq Scan / Index Scan / Bitmap Scan で切り替えて EXPLAIN ANALYZE で結果を見ます。
それから実行時のばらつきを除去するため、各組み合わせを 5 回ずつ実行して中央値を採用しました。
スキャンの強制切り替えには以下を使います。
SET enable_seqscan = off;
SET enable_indexscan = off;
SET enable_bitmapscan = off;
2 つを off にすれば残りが強制されます。 これがないとプランナが自動で選んでしまうので、意図したスキャンで計測できません。
結果
実行時間の中央値（単位 ms）。
| selectivity | 行数 | Seq Scan | Index Scan | Bitmap Scan |
|---|---|---|---|---|
| 0.001% | 5 | 32.66 | 0.004 | 0.005 |
| 0.01% | 81 | 32.81 | 0.016 | 0.022 |
| 0.1% | 936 | 32.54 | 0.151 | 0.289 |
| 1% | 9,779 | 34.83 | 1.88 | 3.31 |
| 5% | 49,439 | 35.57 | 17.46 | 11.44 |
| 10% | 99,718 | 36.65 | 34.04 | 17.33 |
| 33% | 333,620 | 54.23 | 36.02 | 37.01 |
思っていたこと vs 実測
Seq Scan は 33% でも最遅
selectivity が高ければ Seq Scan が勝つと思っていましたが、33% でも最遅でした。 インメモリだと、Seq Scan の強みであるシーケンシャル I/O が活きにくいのかもしれません。
selectivity 5% 以上では Bitmap Scan が速くなった
1% 以下では Index Scan が速く、5% を超えると Bitmap Scan の方が優位でした。
少量取得だと Bitmap はビットマップ構築のコストが無駄になりがちですが、selectivity が上がると Index Scan は同じヒープページに何度も飛ぶ無駄が出てきます。Bitmap Scan はヒープを物理順に 1 回ずつ読むので、この差が効いてくるのかなと思います。
まとめ
インデックスを貼ればどんなクエリでも速くなるというわけではないようなので、selectivity を見積もった上で、適切なスキャン方式が選ばれているか EXPLAIN で確認することが大事ですね。
今回は単純な SELECT * 1 本で試しましたが、SELECT count(*) や JOIN、複合条件などでも別途検証してみたいです。