「カーディナリティが高いカラム両方がwhereとorder byに入る場合は、どのようなインデックスを張るべきなんだろうか。」に対する答え。MySQLの場合。
まず、前提として、インデックスの仕組み。インデックスは B+Tree になってて、各ノードにindexに使われてるキーの値、リーフには(indexに使われてるキー,プライマリーキー）の値が書き込まれている。プライマリーキーは例外的に、リーフにその行のすべてのデータが書き込まれているクラスタインデックスになっている。
というわけで、例えば SELECT * FROM t WHERE indexed_column > x; みたいなクエリを実行すると、
- インデックスツリーからxより大きい値を探して（B+Tree なのでO(log n)）
- 探してきた分だけ以下の操作を繰り返す
- リーフに書き込まれてるプライマリーキーの値を読んで
- プライマリキーインデックスを辿って(おなじくO(log n))、リーフに書き込まれているデータを返す
という動きをする。
ここで、 SELECT * FROM t WHERE where_column > x ORDER BY order_column LIMIT n;のようなクエリを考える。
where_columnにインデックスがある場合、
- インデックスツリーからxより大きい値を探して（B+Tree なのでO(log n)）
- 探してきた分だけ以下の操作を繰り返す
- リーフに書き込まれてるプライマリーキーの値を読んで
- プライマリキーインデックスからさっきの値を探して(おなじくO(log n))、リーフに書き込まれているデータを持ってくる
- order_columnの値でソートする
- ソート結果を頭からn件返す
という動きになる。
order_columnにインデックスがある場合、
- 以下の操作を、インデックスツリーの先頭リーフから、データがn件見つかるまで繰り返す
- リーフに書き込まれてるプライマリーキーを読む
- プライマリーキーのインデックスツリーからデータを持ってくる
- WHERE条件をチェック
- 条件を満たしていればその行を返すものとして保存
- 見つかったデータを返す
前者の場合、WHEREに指定された条件と一致する行に対するIOは必ず発生し一度メモリに読み込まれる一方で、指定されていない条件と一致しない行に対して一切のIOが発生しない。
後者の場合、WHEREに指定された条件に一致しない行に対してもIOが発生するが、条件に一致する行をすべて読み込む必要がない（n件そろった時点でIOを打ち切ることができる）
このため、LIMITの値が十分に小さく、なおかつWHERE条件に一致するレコードの量が十分に大きい場合はORDER BYを狙ったインデックスを張ったほうがよい。LIMITを併用したいシーンである以上、この条件を満たすことのほうが多いであろう。
注意すべき点として、OFFSETに大きい値を指定された場合は、WHERE条件を満たすレコードをOFFSETの値 + LIMITの値分探さないと探索を打ちきれないので、この場合はかなり重いクエリになってしまう。このへんがよく言われる「ページャの闇」ってやつで、ページャの闇を避けるためにはWHEREとORDERに同じキーを指定するとかredisとか使うとかそういう工夫や仕様調整が必要となってくる。