D.Horiyama's output

理論から学ぶデータベース実践入門 ch11 インデックスの設計戦略 (2/2)

RDBSQL勉強メモ

出典: 

リレーショナルモデルとインデックス

  • インデックスは物理的な設計(実装)の一部

  • 本来は論理が先立つ

    1. 欲しいデータは何かが決まる
    2. データを取得するクエリが決まる
    3. クエリの高速化のためにインデックスを設計する

  • 現場では往々にして逆転

    1. インデックスを決め打ちする
    2. いかにインデックスを活用してデータを取得するか考える

インデックスはリレーショナルモデルの一部ではない

  • とはいえ重要でないわけではない
  • リレーショナルモデルとインデックスとの間はミッシングリンク
  • いかに繋ぐかが開発者・DB設計者の腕の見せ所
  • 基本は論理が先

  • 主キー定義してプライマリインデックスを定義するのはアリ

    • DB設計時に候補キーは判明する
  • 直感で「このカラムで検索されることが多くなる」という場合もアリ
  • が、決め打ちインデックスにクエリが縛られることのなきよう
  • インデックスの定義は柔軟に見直せ

正規化とインデックス

  • 正規化は特に実践すべき
  • なぜならば

カラム数が絞られる

  • 逆に、正規化されていないテーブルはカラムが多い

    • 必要なインデックスも増える

  • 正規化されたテーブルには少なくとも1つの候補キーがある(1NFの定義)

    • PKインデックスつけられる

問題児NULL

  • IS NULL検索は非効率

    • NULLはインデックス上で先頭または最後尾にまとまって配置される
    • 連続領域のスキャンにほかならない

  • 3VLなってしまう、排中律が成り立たない

    • 「20歳未満または年齢不明」
    • WHERE age < 20 OR age IS NULL
    • IS NULLが含まれていると台無しに
    • 【補】ORでインデックス効かない製品もある

指令: 最適なインデックスを探せ！

  • 唯一の正解はない

必要なインデックス

  • 作成しすぎNG

    • 更新のオーバヘッド
    • ディスクスペース増大
    • バッファプールのヒット率低下

インデックスのアクセス特性

  • テーブルスキャンを避けるためのインデックス

  • が、テーブルスキャンのほうがシステム全体としてスループット高いことも

    • クエリ実行頻度がきわめて低い

    • テーブルのサイズが非常に小さい

      • 【補】 O(n)とO(logn)

    • 検索結果が非常に多くの行にヒットする

      • カヴァリングインデックスなら高速

      • さもないと低速

        • derefしてランダムアクセスする必要があるため

インデックスが使用される構文

WHERE句

  • 前方一致でなければならないことに注意
  • 等号・不等号混在は特に注意
-- 低効率
-- 複合インデックス(col1, col2)
WHERE col1 > 100 AND col2 = 'abc'

-- 高効率
-- 複合インデックス(col2, col1)
WHERE col2 = 'abc' AND col1 > 100
  • B+木インデックスは前方一致

  • 前者はcol1のインデックスしか効かない

    • col1 > 100

  • 後者はcol2, col1のインデックス両方効く

    • col2 = 'abc' AND col1 > 100

JOIN

  • 駆動表

    • FROM句の指定する表

  • 内部表

    • JOIN句で指定する表
SELECT *
  FROM t1
  JOIN t2 ON t1.col1 = t2.col2
 WHERE t1.col3 = 100
   AND t2.col4 = 'abc';

  • 内部表t2にマルチカラムインデックス(col2,col4)があると、col2単体のインデックスよりもアクセスが効率的になる可能性がある

    • オプティマイザが内部表と駆動表を入れ替えることがある

    • すると、テーブルから行がフェッチされる時点で両条件で絞り込まれる

      • t1.col1 = t2.col2
      • t2.col4 = 'abc'
    • フェッチ後に絞り込むよりも高効率
SELECT *
  FROM t2
  JOIN t1 ON t1.col3 = 100
 WHERE t1.col1 = t2.col2
   AND t2.col4 = 'abc';
  • 【補】↑こういうこと？多分

相関サブクエリ

  • INとかEXISTSとか
  • これもWHEREとおなじこと(略)

ソート

  • 前方一致

    • 順序が一致
    • 抜けがない
    • 最後のカラム以外等価比較

カヴァリングインデックス

  • クエリの実行に必要なカラムがすべてインデックスに含まれている

    • deref・テーブルアクセスがおこらない

  • 功罪

    • 非常に高速

    • インデックスのサイズが大きくなってしまう

      • ディスクスペース増大
      • 更新性能劣化

ORとインデックス

  • インデックスマージ

    • ORで条件が結合されている場合
    • それぞれの条件にインデックスがある必要がある
    • インデックスを使って取得したROWIDがUNIONされる

  • インデックスマージが実装されているかは製品次第

    • 使用不可or精度が低い場合は自前UNION

  • ANDには適用できないの(マルチカラムインデックス必要ない説)

    • 絞り込み効率悪い

最適なインデックスを探すための戦略

インデックス≠候補キー

  • インデックス

    • 制限の高速解決

    • 候補キーに限らない(セカンダリインデックス)

      • 同じ値が並び、範囲検索になる

  • カヴァリングインデックス

    • さらに射影の高速解決

カラムの並び順

  • カラムの順序のある/なし

    • インデックス: あり(重要)
    • リレーショナルモデル: なし
  • 範囲検索やソートのクエリを記述する場合は、検索条件が前方一致になるようにカラムを配置する
  • パフォーマンスのために、同じカラムの組み合わせで、並び順だけが異なるインデックスを作成することも

カーディナリティ

  • カーディナリティが高いカラムだけ含んだインデックスを作るというテクニック

    • カーディナリティが低いカラムもわざわざ含める価値はない

最適な組み合わせを探す

  • まず可能性を網羅

    • 製品を熟知することが重要

      • どのようなタイプのインデックスが使用できるか

      • 実行計画のどこでインデックスが利用可能になるか

        • 【補】インデックスマージ効く、とか

  • つぎに必要なもののみ残す

    • 判断基準

      • 個々のカラムのカーディナリティ
      • テーブルのサイズ
      • クエリ実行頻度

    • 全体のバランスを取る

      • 1つのクエリの高速化のために更新が遅くなり、システム全体のパフォーマンスが悪化する、等はNG

  • 本質は組み合わせ最適化問題

    • 難問

      • しかも試行錯誤に時間がかかる

難しい作業に立ち向かう

  • 技術力が必要

  • 基本が大事

    • B+ツリーインデックスの働き
    • B+ツリー以外のインデックスの種類
    • インデックス設計の前にしっかりと正規化を行う
    • 論理設計が決まってから物理設計
    • SQLのどのような個所にインデックスが必要か
    • カラムの並び順だけが異なるインデックスがあっても良い
    • 最大公約数的にカーディナリティが高いカラムだけを含んだインデックスを作る
    • 必要なインデックスの組み合わせを網羅する方法

真の最適解にこだわらない

  • さっさと妥協せよ

    • 真の最適値を見つけることは困難

      • 割に合う保証もない
      • 運用している間に最適解が変化することもある

コラム: こんなインデックス設計はゴミ箱行きだ！

  • すべてのカラムにインデックスがある
  • インデックスに含まれているカラムが1つしかない

  • たくさんあるマルチカラムインデックスに同じカラムの組が登場し、常に同じ順序で並んでいる

    • 【補】 順序が異なるならわかる(前方一致のため)

  • 0か1しか値を取らない、フラグのようなカラムのインデックスがある

    • 【補】カーディナリティ低いので、deref・ランダムアクセスぶん性能が劣化するまである