備忘録
「USE THE INDEX, LUKE!」を読みながら学習したときの自分用のメモ。
インデックスの内部構造
独自のディスク領域を必要として、テーブルのデータを保持することでクエリの実行を早くする。予め決められた順番に並べることで、要素がどこにあるのかがすぐにわかるため素早く簡単にデータを探し出せる。
元々あるデータの前後にデータを追加しようとしたとき、インデックスの順番を保つためには、大量のデータを動かす必要が出てしまう。そこで、データベースでは双方向連結リストと検索木という２つのデータ構造で対処している。
インデックスの最も重要な目的は、インデックスを貼ったデータに対して順序を付けてアクセスできるようにすること。
インデックスリーフノード
メモリ上の物理データの並び順とは独立して論理的な順序付けを作る。
ノードは前後のノードを参照する仕組みで、必要なときにポインタを変更すればデータの挿入が可能。
- リーフノードはデータベースブロック/ページと呼ばれる
- 全てのインデックスブロックは同じサイズ
- 各ブロックはスペースを可能な限り使ってインデックスのエントリを詰めれるだけ詰め込む
- リーフノード内の順序と、双方向連結リストで繋がれたリーフノードの順序の２レベルで管理
検索木（Bツリー）
リーフノードのディスク上の保存場所はインデックスに従わない。そこで素早くデータにアクセスする方法として検索木を採用。
- 「ルートノード」「ブランチノード」「リーフノード」と多段のデータ構造
- ルートノードは１つで、ルートノードは１階層下への参照を持ち、１段下のブランチノードは更に１段下のリーフノードへの参照を持つ
- この方法でレイヤを作ると、ルートからリーフまでの深さがどこでも同じになる
- 深さが等しいからバランス検索木と呼ばれる
バランス検索木によってデータベースはリーフノードを高速に検索することができる。
数百万レコードのインデックスのツリーの深さも4あるいは５になるとのこと。
インデックスが遅くなる
検索木でリーフノードを辿るが、一致するエントリがまだあるかを確認するためにリーフノードが連結しているリーフノードも読み込む必要がある。これによりインデックスを使っても検索が遅い場合がある。
また、リーフノードのエントリに対応するテーブルデータにアクセスすることも検索が遅くなる原因。
プライマリーキー
- 一意であればテーブルアクセスは一回しか発生しないため高速
- pkは一意である必要はない→遅延制約のためなど
プライマリーキーとインデックス
プライマリーキー：データを一意に確定させるもの
インデックス：検索を高速化させるもの
わかりやすかった記事
複合インデックス
- 複数の列にまたがる１つのインデックス
- 複合インデックスの列順番はパフォーマンスに大きく影響
- 任意の１列だけ使うことはできない（ツリーの構造上、２列目だけの検索では効かない）
- 3列の場合、「1番目のみ」「１番目と２番目」「全て」で検索するときにインデックス使用可
- インデックスを減らすとストレージ領域の節約＆メンテナンスのためのオーバーヘッド減少でパフォーマンス向上
フルテーブルスキャン
- テーブルの大部分を読み出す場合には最も効率的
- インデックス検索のオーバーヘッドが必要ない
- インデックスの検索で複数行が得られる場合はROWIDから１行ずつDBから読み出す
- インデックスを使えば効率良くなるとは限らない
関数インデックス
- 関数を適応してからその結果をインデックスに入れる
- 関数呼び出しの結果が一意に決まる確定的な関数のみインデックス作成可能
インデックスの作りすぎ
- インデックスは継続的なメンテナンスが必要
- insertやupdate、deleteが実行されるたびにインデックス更新が発生する
- アプリケーション全体が一貫して同インデックスを使えるように整備
パラメータ化クエリ
- バインドパラメータはプレースホルダを使いDBにデータを渡す方法
- バインドパラメータはSQLインジェクションを防ぐメリットとパフォーマンス向上
- 実行計画をキャッシュするDBでは同じ文に対する実行計画は再利用
- プレースホルダを利用すると値が異なっても同じ文として再利用可能
インデックススキャンの黄金則
- インデックスをスキャンする範囲をできる限り小さく保つ
- アクセス述語：インデックスをスキャンする範囲
- フィルタ述語：リーフノード走査時のみに適用
LIKEフィルタ
- インデックスツリー走査ではLIKEが有効なのは最初のワイルドカードの前まで
- 上記の最初のワイルドカードの前までがアクセス述語になる
別々の列のインデックスを複数使う
- 各インデックスをスキャンして結果をまとめる
- それぞれのインデックスツリーを辿る必要があり負荷を要求
- 中間結果をまとめるために多くのメモリとCPUリソースを要求
- インデックスは２つ使うより１つだけ使うほうが高速
nullに対するインデックス
- OracleでNULLにインデックスを作成したいなら、NULLにならない列をインデックスに追加
正しいインデックス使用を妨げるwhere句など
- 日付（DATE）を比較するときは明確な範囲条件を使う
- DBは必ず一意な結果となる文字列から数値へ変換する（42→042, 0042等逆は定まらない）
- 数値を保存するときは数値型を使用
- 数値文字列は暗黙的な型変換によりパフォーマンスの問題を引き起こす（インデックス効かないなど）
- 数値文字列は不正な数字で変換エラーが発生するリスク
処理しにくい条件
- 範囲検索で複数列を連結する場合は代表的な列に対して条件を付け加えてフィルタする
数式
- 数式を用いたwhere句ではインデックスは効かない
- 数式内のテーブルへの参照を左辺や右辺のみにして、それに対してインデックスを作って回避は可能
スケーラビリティ
- スケーラビリティはパフォーマンスがデータ量のような要素に依存することを示す
- クエリの応答時間は多くの要因に依存するが、データ量もその１つ
- インデックスサイズが同じでもインデックスの定義次第では処理速度はかなり変わる
- データ数が少ない場合はほぼ同じパフォーマンスでも、データ量が増えると影響大
- 特にフィルタ述語として動作するようなインデックスは注意
- データ量が一定でもアクセス量によってパフォーマンスが低下する可能性
入れ子ループ
- レスポンスタイムにはデータ転送量よりもDBとのやり取り回数の方が影響大
- 入れ子ループ結合とハッシュ結合ではチューニングのアプローチが異なる
- ハッシュ結合のチューニングはwhere句の述語に独立したインデックスを作成
- ハッシュテーブルを使う場合、オプティマイザは小さい方を自動的に使う
- ハッシュテーブル全体がメモリに収まらなければ最適な結合は不可。テーブルサイズは小さいほどパフォーマンス高
- 例えばハッシュテーブルに乗せる必要のないデータはフィルタを追加して除く
- ハッシュテーブルはの大きさはメモリ使用量なので行ではなく、列を減らすことも有効
クラスタ
- DBパフォーマンス改善のクラスタは、データクラスタとコンピュータクラスタがある
- SQLデータベースでは行でデータクラスタ化
- インデックスも近い値を行のクラスタとして構成している
- インデックスの強力なポイントは、Bツリーの走査とクラスタ化
- テーブルアクセスが発生する場合、アクセスされる行の物理的な分散具合（クラスタ状況）に左右される
インデックスとクラスタ
- 実行ステップの初期段階でデータ量をへらすために、フィルタ述語を使うべき
- クラスタ化係数はインデックスの２つの連続したエントリが同じテーブルブロックにある可能性を示す
- オプティマイザはテーブルアクセス時のコスト計算にクラスタ化係数を考慮
カバリングインデックス
- インデックスのみのスキャンはwhere句の評価のためにテーブルへのアクセスが必要ない
- インデックス自体に目当ての列があるならテーブルへのアクセスは不要
- インデックスのみのスキャンの優位性はアクセスされる行数とクラスタ化係数で決まる
- カバリングインデックスを狙うのではなく、where句を優先し必要があればselect句にも拡張
- クエリが返す行数ではなく行を取得するためにDBに何行アクセスするかがパフォーマンスに影響
クラスタ化インデックスとセカンダリインデックス
- InnoDBではクラスタインデックス構造で全てのデータは主キーのリーフノードに格納（全てインデックス）
- InnoDBではテーブルスキャンは主キーのインデックススキャンと同義
- クラスタ化インデックスはページ番号でセカンダリインデックスは索引
- セカンダリインデックスに必要な情報が揃っていればクラスタ化インデックスを辿る必要がなく高速
- セカンダリインデックスのみで完結する場合をカバリングインデックスと呼ぶ
最初のN件のみを選択するクエリ
- 最初のN件のみを選択するクエリは応答時間はテーブルサイズに依存せず、件数にのみ依存
- order byに適したインデックスがない場合はテーブル全体をスキャンしないと達成できない
途中のある部分のみを取得するクエリ
- オフセット法は、途中にデータが挿入されるとズレる、また先のページになるにつれ応答時間が長くなる
データの変更
- insert時は新エントリをテーブルの全てのインデックスに追加するため、インデックス数により実行コストが増加
- インデックスは順序と木のバランスを保つ必要があり、エントリ追加はより重い処理になる（インデックスのメンテナンスはinsertで最も重い処理）
- 巨大なデータロードを行う時は一時的にインデックスを削除することは非常に有効
- updateでは変更される列が含まれるインデックスだけが更新される
参考にした記事