勉強日記

チラ裏

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

RDB SQL 勉強メモ 閃乱カグラ

gihyo.jp

まとめ

  • 元になるDBの論理設計がしっかりしていることが重要
    • 1つのテーブルに膨大なカラムが含まれる、という事態を避ける
    • さもないと作成可能なインデックスの組み合わせは膨大な数になる
      • 難しいインデックス設計がさらに困難に

インデックスの働き

  • 索引
  • 本の索引は結局索引をフルスキャンする必要がある
  • RDBの索引はもう少しスマート

RDBのインデックス

  • 例えばB+ツリーインデックス
  • ルートノードからリーフノードへ至る1本のパスだけを検索すれば済む
    • 平衡木ならO(log(n))

インデックスの左端と範囲検索

  • B+ツリーインデックスは、等価比較および範囲検索に利用できる
    • <, >, <=, >=
    • BETWEEN
    • LIKE前方一致
  • マルチカラムインデックスの場合もLIKE前方一致と同様
    • 指定順がインデックス定義順であること
    • 抜けがないこと

セカンダリインデックスの更新

  • 主キー
    • めったに書き換えられることはない
  • セカンダリインデックス
    • 更新ありまくり
  • インデックス更新コストは高い
    • 削除・挿入と等価
    • 安易につけてはいけない

インデックスの種類

  • B+ツリー以外にも種類あり
    • RDB製品次第
    • 要件次第で必要になる

ハッシュインデックス

  • 検索速度が非常に速い
  • 等価比較のみ。範囲検索には利用できない
    • 主キーは等価比較だけでよい場合が多い

全文検索インデックス

  • 後方一致や中間一致を扱う
  • 転値インデックス
rowid text
1 Relational Model
2 Model View Controller
3 Materialized View
word rowid
Controller 2
Materialized 3
Model 1
Model 2
Relational 1
View 1
View 2
  • 行に含まれる単語あるいは部分文字列から行へのポインタが格納されている
  • わかち書きがない言語(e.g.日本語)ではどうする？

形態素解析

  • 辞書を用いて文章の文法を解析、単語を抽出
  • メリット
    • 無駄が少ない
  • デメリット

Nグラム

  • N文字ずつの部分文字列に分割
  • 「外国人参政権」のバイグラム
    • 外国
    • 国人
    • 人参
    • 参政
    • 政権
  • メリット
    • 網羅的
  • デメリット
    • 検索ノイズが多い
      • 上記の例の「人参」など
    • インデックスのサイズ大きい

Rツリーインデックス

  • 地図上の地点を検索するのに用いる
  • Spacial Indexとも
  • 最小外接矩形(MBR: Minimum Bounding Rectangle)を用いてインデックスを構築
  • MBRをMBRで再帰的にくるむ
    • 子は適切な個数
    • なるべくオーバーラップしないよう
  • MBRのツリーができあがる

関数インデックス

  • WHERE year(date_col) = 2013とかにもインデックス適用できるやつ
  • 関数適用後の値に対してB+ツリーインデックスを作成

ビットマップインデックス

  • オンライン分析処理(OLAP: OnLine Analytical Processing)などで用いられる
  • カラムごとに複数のビットマップが作成される
name grade
飛鳥 2
葛城 3
斑鳩 3
柳生 1
雲雀 1
value bitmap
1 00011
2 10000
3 01100
  • メリット
    • インデックスのサイズが小さい
      • スキャン高速
  • デメリット
    • ビットマップの更新に時間がかかる
      • オンライントランザクション処理(OLTP: Online Transaction Processing)には不向き
      • カラムがとりうる値のバリエーションが多い場合、期待したパフォーマンスが出ない
        • 必要なビットマップ数が増えてしまうため

コラム: クラスタインデックス

  • テーブルそのものがインデックスでできている
    • 索引構成表(IOT: Index Organized Table)とも
    • InnoDBストレージエンジンではクラスタインデックス強制
  • 主キーのリーフノードに他のカラムの値も一緒に格納
    • 主キー検索は速い
    • セカンダリインデックス検索はオーバヘッドあり
      • ツリーを辿らなければならない

パーティショニング

  • 水平パーティショニングのことを指す

パーティショニング

パーティショニングが適しているケース

  • 刈り込みが有向なクエリの実行頻度が高い場合
  • カーディナリティが低い場合
    • インデックスの効率がよくない
  • アクセスの局所性がある場合
    • 「直近の月のみ検索対象」とか

パーティショニングと一意性制約

ローカルインデックス

  • パーティションごとに作成されるインデックス
    • テーブル全体としては一意性を保証しない
  • 多くの製品でローカルインデックスに課せられる制限
    • 主キーやユニークインデックスには必ずパーティションキーを含めなければならない
    • 元々ユニークインデックスを構成していたカラムの組が一意性を保証できなくなる可能性がある

パーティションキー追加前

hoge(PK) fuga(PK) year
1 1 2010
1 2 2010
2 1 2011
2 2 2011

パーティションキー追加後

hoge(PK) fuga(PK) year(PK)
1 1 2010
1 2 2010
2 1 2011
2 2 2011
1 1 2011
  • {hoge,fuga}が一意性を失う例
    • 重複データを登録できてしまうように
  • パーティショニングにより一意性を保証できなくなるくらいならパーティショニングすべきでない

グローバルインデックス

  • 個々のパーティションではなく、テーブル全体を対象としたインデックス
  • 一意性制約が損なわれる心配がない
  • 反面、そのインデックスを使用する場合、パーティションの刈り込みができない
    • パーティショニングの旨味を損なう

パーティショニングについてよくある誤解

  • 「パーティショニングすればそれだけでアクセスが高速化する」
  • 基本的に刈り込みが効かなければ意味がない
  • むしろ遅くなるケースも
    • 刈り込みがない & ローカルインデックス
    • パーティションの数だけインデックス検索が発生する