データベース索引

索引は条件を候補キーへ絞り、RID から行のヒープページを見つける。RID は住所で、行の値ではない。必要列が索引になければヒープも読む。本レッスンは「索引ページ＋異なるヒープページの読み取り」を全表走査と比べ、前者が少ない場合に冷ページ計数での節約を示す。

ハッシュは等値バケットへ飛び、B+ 木はキー順を保ち、INCLUDE の付加データは射影を直接返せる。同じ表と同じ結果行でも、訪れるページが変わる。

データベース索引の仕組み

既定のクエリは：

SELECT tier
FROM customers
WHERE customer_id = 84;

16 行を一ページ二行、八ヒープページに置く。物理順は customer_id と無関係で、一致行は RID P7:S0、ページ 7 のスロット 0 にある。

全表走査は八ページを読み、各二行を調べる。一行だけ該当しても全て読む。単位は行ではなくページだ。

ハッシュ索引はバケット番号を計算する。複数の key→RID と衝突があるため、完全なキーを比べる。84 は H4 にあり、84 → P7:S0 の後で P7 を読むので二ページ。

B+ 木は根 I0 の分離キーから葉 L3 へ進み、同じ RID で P7 を読むので三ページ。カバリング B+ 木は tier を葉に持ち、I0 と L3 だけで Basic を返せるので二ページとなる。

数値はこの配置のもので、一般的なベンチマークではない。索引と異なるヒープページを分けて数える考え方を示している。

等値、範囲、キー順

ハッシュは正確なキーをバケットに写すが、大小順を保たない。68 から 84 が隣り合うバケットにあるとは限らず、番号範囲を BETWEEN のように使うと行を落とす。

B+ 木の customer_id BETWEEN 68 AND 84 は L2 へ下り、順序付きの兄弟リンクで L3 へ進み、五キーを得る。通常の索引は五 RID から五つの異なるヒープページを読む。根一、葉二、ヒープ五で八読み取り。カバリングなら tier が葉にあり、三索引ページだけで済む。

等値は両構造で扱えるが、範囲にはキー順を扱える経路が必要で、バケット番号の見た目の順序では代用できない。

カバリングとヒープ取得

二次索引は行を特定しても、全必要列を持つとは限らない。RID は論理キー順と物理ヒープを結ぶ。同じ経路で複数 RID が同ページにあれば、一回の取得へまとめて数える。

カバリングはクエリとの関係だ。(customer_id) INCLUDE (tier) は既定を覆うが、email を求めれば同じ葉では足りない。未カバーのプリセットは P7:S0 をたどる。列を増やすと索引が広がり、容量と書き込み費用も増える。

最適化器が索引を使わない理由

選択性の低いプリセットは Basic の十顧客を求め、全八ヒープページに散らばっている。通常 B+ 木は根一、葉三、ヒープ八で 12。単純走査は八だけなので、四索引ページを省く判断が合理的だ。

選択性は該当項目数、クラスタ化は RID が触れる異なるページ数を決める。少数が一ページに集まる場合と、多数が全体に散らばる場合は違う。使える索引でも高価になりうる。

比較パネルは四経路のモデル値を残すが、現在の問いは選択索引が走査を置き換えるべきか。他の値は仮定した代替案で、全索引が同時に存在する意味ではなく、対応する再生で根拠を確認する。低選択性の通常 B+ 木なら答えは否。別途カバリング索引があればヒープを省け、選択肢が変わる。

索引アクセスのステップ

1. SQL の条件と射影を読み、等値か範囲かを確認する。
2. 走査の基準を再生する。P# heap は一つの全ページ読み取り。
3. 選択索引を再生する。ハッシュはバケット、B+ 木は根と必要な葉を読む。
4. 候補を検証する。衝突は完全キー比較、木は順序区間を保つ。
5. 射影を付加データで覆えるか決め、足りなければ RID を集める。
6. ヒープページでまとめ、各異なるページを一度読む。
7. 冷たい論理ページ数を比較し、最安の有効案を示す。

存在しない 85 は候補バケットや葉で不在を確認でき、ヒープを読まない。行を取らないため、失敗検索が成功より安い場合がある。

境界ケース

• 等値キーなしはバケットか葉で証明し、ヒープへ行かない。
• 葉をまたぐ範囲は L2 から L3 へ進み、ハッシュに同じ順序付き経路はない。
• 44、52、68、84 は H4 を共有するが、バケット一致はキー一致ではない。
• 同ページの複数 RID は一論理読み取りを共有する。
• tier を覆っても email は覆わない。
• 低選択性の非カバリング索引は全ヒープに加えて索引も読む。

ページ読み取りの計算量

ヒープページ数 P、索引項目 N、B+ 木分岐数 f、訪問葉 L、一致を含む異なるヒープ H とする。

• 走査は O(P) ヒープ読み取り。
• ハッシュ等値は平均 O(1) バケットと H ヒープ。
• B+ 点検索は O(log_f N) 層と H。
• B+ 範囲は O(log_f N + L + H)。
• 本カバリングモデルは同じ索引探索で、射影が葉にあり H=0。

アクセス規模であり、経過時間ではない。キャッシュ、先読み、機器、並行処理、統計で実費用は変わる。実際の index-only scan も可視性確認でヒープへ行く場合がある。

実計画を読む

推定と実際の該当件数、索引条件と射影、index-only か、ヒープ取得とデータページ数を確認する。競合する走査と、古い統計、配置のばらつき、件数推定の影響も見る。キャッシュ、先読み、ハッシュ索引や INCLUDE の対応、広い索引の容量と書き込み増幅も費用に含める。

これらは冷ページモデルの選択を逆転させうる。経路が何を増やし、どの読み取りを省くかを調べる。

よくある間違い

• 全索引が全クエリを速くすると思う。低選択性の非カバリングでは、ほぼ全表を読む前に追加費用がかかる。
• 番号付きバケットを順序付きキー範囲と考える。
• RID を値と読み、アドレスの先の取得を忘れる。
• クエリを示さず索引をカバリングと呼ぶ。条件と射影に依存する。
• 一致行ごとにヒープを数え、同ページの共有を忘れる。
• 表示値を PostgreSQL や MySQL の固定費用と読む。

モデルの範囲

二層の小 B+ 木、固定バケット、非クラスタ化ヒープで冷論理読み取りを数える。常駐、OS キャッシュ、先読み、可視性、MVCC、ロック、圧縮、オーバーフローバケット、木の高さ変化、統計の不確実さ、書き込み増幅、固有配置は省く。実最適化器は CPU、I/O、キャッシュ、相関、件数を推定する。ここでは同じ行を返すために触れるページだけを分離している。