🎉

「SQLパフォーマンス詳解」を読んだのでまとめ

2023/02/02に公開

SQL

tech

DB のパフォーマンスを考える機会が増えてきたので、 SQL の勉強を始めました。

開発者のための SQL パフォーマンスの全てというサイトがわかりやすく、紙の本 SQL パフォーマンス詳解を読んだので忘れないうちにまとめます。

本の目次に沿ってまとめていきます。

インデックスの内部構造

この本で説明されているのは B ツリー
インデックスはメモリ上の物理データとは別の論理的な順序データ
インデックスは以下の構造をイメージできていれば良さそう

SQL のインデックスとそのチューニングについてのオンラインブックより
インデックスを使った検索手順
1. ルートノードからリーフノードまで降りていくツリー走査(左から右)
2. リーフノード間の検索(上から下)
- 図でいうと 46 を検索するときリーフノードの 1 つ目と 2 つ目にあるのでリーフノード間を検索する必要がある
1. 物理データから実データを読み出す(論理的な順序データから実データ取得)
- インデックスは論理的なデータなのでメモリ上の物理データが必要
遅いインデックスの発生理由
- 上記 2 で複数データがある場合はリーフノードをたくさん見ないといけないので時間がかかる
- 上記 3 で 2 で複数データの実データを取りに行く場合、実データは分散してるので取得に時間がかかる
基本的な検索方法
- INDEX UNIQUE SCAN
  - ツリー走査(1)のみを行う
  - ユニーク制約により検索結果が１つしかないことが保証されいている
  - 上記検索手順の 2. をする必要がないので早い
- INDEX RANGE SCAN
  - ツリー走査とリーフノード間の検索を行う(1,2)
  - 検索結果が複数存在する可能性があるときの検索
- TABLE ACCESS BY INDEX ROWID
  - INDEX SCAN の結果から実データを読み出す(3)
- TABLE ACCESS FULL
  - インデックスを使わずにテーブル全体を検索する

where 句

Primary key で検索するときは一意であることが保証されいているので INDEX UNIQUE SCAN になる
複合インデックス
- 姓と名であいうえお順で並んでると考えると理解しやすい
- 名で検索をしても姓が先に並んでるので検索のインデックスとしては使えない
  - 前に来る姓での検索時は使える
  - つまり、検索でよく使いそうなものを前にしてインデックスを張ると良さそう
インデックスはたくさん張ると insert や delete、update 時に更新が必要になりパフォーマンスに影響する
- インデックスの数が少ないほど、 insert や delete、update のパフォーマンスは上がる
オプティマイザが使う統計情報
- これを元にコスト計算をして、最適な実行計画を立てている
- データが削除されるなどしたときは正しい統計情報が使えず、デフォルトで持っている値を使う
  - そのため、コスト計算が実データと合わず、不適切な実行計画を建てる場合がある
INDEX RANGE SCAN でたくさんデータが出てきた場合、実データ取得のコストが高くなる
- 遅いインデックスの発生理由のところで出てきた話(3 のところ)
- 数が数百などになってくるとインデックスを使って効率よく絞り込んでもデータ取得で時間がかかる場合がある
SQL での関数使用の注意点
- WHERE で比較するときの左側には使わない
  - 例) WHERE UPPER(last_name) = UPPRE('winand')
- オプティマイザは左辺に関数があると自分の知らないものとして扱うのでインデックスを使ったりできなくなる
- どうしても必要な場合は 関数インデックス を張る
  - DB によって関数インデックスを張れないものもあるので確認が必要
  - MySQL と SQL Server は機能がない
    - カラムとして計算した結果を定義して、そこにインデックスを張る、計算列というものをサポートしているので、それを使うことができる
  - 関数インデックスを使う場合、現在時刻のような不確定要素(実行するたびに変わるもの)は使えない
無駄なインデックスは張らない
- insert や delete、update のたびにすべてのインデックスを更新しなければならないのでパフォーマンスに影響する
バインドパラメータ
- WHERE とかで見る ? @name :name みたいなやつ
- SQL インジェクションを防げるのでセキュリティ面でよい
- また実行計画をキャッシュするのでパフォーマンスも良くなる
  - 副作用もあって、統計情報として同じようにデータが分布している場合は有効だが、偏りがあるとパフォーマンスに影響を与える
- バインドパラメータを使わないと毎回実行計画を計算する
  - 基本はバインドパラメータ
  - 結果に影響が出そうなものは直接指定する
範囲検索
- INDEX RANGE SCAN においてパフォーマンスへの影響が最も大きいのがリーフノード走査
- インデックスをスキャンする範囲をできるだけ小さくする
- 範囲検索を想定したインデックスを張る場合、どこから始まってどこで終わるのかを考えることが大事
- 一つのカラムに対しての範囲検索は分かりやすい
- 複数カラムに対して検索する場合
  - サイト内の大なり、小なり、BETWEEN を読むのが一番分かりやすい
以下の SQL だと date_of_birth と subsidiary_id を検索してる
- この場合、どちらを先にして複合インデックスを作るかによってパフォーマンスが変わってくる
```
SELECT first_name, last_name, date_of_birth
  FROM employees
 WHERE date_of_birth >= TO_DATE(?, 'YYYY-MM-DD')
   AND date_of_birth <= TO_DATE(?, 'YYYY-MM-DD')
   AND subsidiary_id  = ?
```
- date_of_birth が先の場合
  - date_of_birth の範囲でツリー走査して、そこからリーフノード走査でデータを見ながら subsidiary_id を探している
  - date_of_birth の範囲で検索したリーフノードを見ると subsidiary_id は順番に並んでない
  - ツリー走査の時点では subsidiary_id を全く見ていない
    
    SQL のインデックスとそのチューニングについてのオンラインブックより
- subsidiary_id が先の場合
  - subsidiary_id でツリー走査し、そのツリー走査の中で date_of_birth も見ている
  - subsidiary_id は等号での検索なので値が決まれば date_of_birth は順番に並んでいる

SQL のインデックスとそのチューニングについてのオンラインブックより

この違いは選択性が影響してくる
- 選択性が高い: より絞り込んで検索できている、その条件による検索結果が少ない状態、低い場合はその逆
- 上の例でも date_of_birth の選択性が高ければパフォーマンスの違いは無視できる可能性がある
- 選択性が高いものを先に持ってくると良いときはフィルタ述語を使うとき
ここで大事なのは、インデックスは等価性を確認して、それから範囲を検索するために使われるということ
アクセス述語
- ツリー走査時に使われる、インデックスをスキャンする範囲を定義
フィルタ熟語
- リーフノード走査時に使われる
LIKE フィルタ
- ワイルドカード(%)の前がアクセス述語に使われる
- ワイルドカード(%)の後ろがフィルタ述語に使われる
- ワイルドカード(%)から始まる検索の場合はテーブルのフルスキャンになるので使うのはできるだけやめる
- バインドパラメータとして LIKE の検索条件が与えられた場合、実行計画を立てるときは最初にワイルドカードはないと仮定する
  - PostgreSQL は最初にワイルドカードが存在すると仮定する
- 全文検索( %xxx% みたいなやつ)の場合、上記が悪い影響を与える可能性がある
  - WHERE text_column LIKE '%' || ? || '%' とすることでこれを回避することができる
複合インデックス
- 複数列の検索時、各カラムに一つずつインデックスを張るのと、複数カラムをまとめてインデックスを張るの、どっちがいい？
  - 複数列まとめた方が高速
部分インデックス(フィルター選択されたインデックス)
- 今までのインデックスは列に対するインデックスで、これは行に対するインデックス
- インデックス作成条件に WHERE を入れて事前に絞り込んでおくことができる
- 以下の例は messages テーブルの未処理(processed = 'N')のみに対して receiver カラムのインデックスを作成している
  - インデックスサイズも少なくでき、パフォーマンスが上がる

CREATE INDEX messages_todo
          ON messages (receiver)
       WHERE processed = 'N'

処理しにくい条件: 正しいインデックスの使用を妨げる WHERE 句
- 日付型
  - 範囲検索のときは期間を明確にして検索する
  - 文字列として検索すると正しいインデックスが使われない
    - その場合は検索文字列の方を日付型に変換する
  - 日付に LIKE 検索をすると文字列比較になってインデックスは使われない
- 数値文字列
  - テキスト列に保存されている数値のこと
  - 文字列になっているので WHERE numeric_string = 42 みたいな数値と比較してしまうとインデックスを使えなくなってしまう
  - 数値文字列は混乱の元なので、ちゃんと数値型を使う

パフォーマンスとスケーラビリティ

データ量に対するスケーラビリティ
- データ量はクエリのスピードに影響を与える
  - その影響をインデックスをうまく使えば小さくも大きくもできる

SQL のインデックスとそのチューニングについてのオンラインブックより

遅いインデックス問題
- インデックス走査を遅くする 2 つの原因
  - テーブルアクセス
  - 広い範囲のインデックススキャン
システム負荷増加によるパフォーマンスへの影響
- 同時に走るクエリが増えればパフォーマンスに影響が出る

SQL のインデックスとそのチューニングについてのオンラインブックより

データ量、システム負荷、どちらが増えても正しくインデックスを張って、それを使っていればパフォーマンスへの影響を小さくできる
NoSQL はパフォーマンス問題をスケールアウトで解決できるとしている
- これは書き込み処理に対して結果整合性モデルを使っているから
  - 複数ノード間で不整合が起きた場合、矛盾を防ぐのではなく、それをうまく扱うことで対処している
  - つまり、すべてのノードで整合性が取れているというわけではなく、うまく扱った結果同じデータを持っているという状態
- Relational DB は厳密な整合性モデルを使っているから遅くなる
ディスクシークによるレイテンシ悪化
- HDD の場合、データを読み込むための時間が長い
  - 少量であれば影響は少ないが、データ量が増えるとパフォーマンスが悪化する
- キャッシュを使うことで改善される
- SSD を使うことによってもかなり速くなる

結合処理

複数テーブルの結合処理
- テーブルは 2 つずつしか結合できない
- 3 つ以上のテーブルの結合は 2 つを結合して中間テーブルを作ってから 3 つ目を結合する処理をしている
  - 中間テーブルは保存されているわけではなく、メモリ節約のためパイプライン化されてすぐに次の処理に渡る
- 結合の順番はオプティマイザがすべての組み合わせを評価して最適なものを使う
  - バインドパラメータを使っていれば実行計画をキャッシュできるので影響を小さくできる
N + 1
- 入れ子のループ処理
  - DB へのアクセスが増えることでネットワークのレイテンシが増えて遅くなる
データ転送量と DB とのやり取り回数
- レスポンスタイムに関して、データ転送量より DB とのやり取り回数の方がパフォーマンスへの影響は大きい
ハッシュ結合
- RDB におけるテーブル結合(JOIN)を行うアルゴリズムの一つ
- 一方の結合対象の列の値からハッシュテーブルを作り、もう一方のテーブルの列の値で探索する方法
- ハッシュ結合のパフォーマンス改善をしたい場合、where 句の熟語に独立したインデックスを張る必要がある
- ハッシュテーブルの目的は結合するテーブルへのアクセス回数を減らすため
  - 一時的なインメモリ構造として動く
- ハッシュテーブルを使う結合ではオプティマイザはサイズが小さいテーブルを自動的に使う
- 結合述語にインデックスを作成しても、ハッシュ結合のパフォーマンスは良くならない
  - WHERE 句が使われていればそこへのインデックスは使える
    - 2 つのテーブルのうち、片方しか WHERE 句で使われていない場合、その WHERE 句で使われているカラムへのインデックスは使える
    - もう一方のテーブルはフルスキャンになる
- ハッシュテーブル自体を小さくする方法として、SELECT で選択するカラムを絞り込むというのがある
  - 必要なカラムのみにすることでハッシュテーブルのサイズを小さくできる

データのクラスタリング

データクラスタ
- 少ない I/O で処理できるよう連続的にアクセスされるデータを近くに保存する
クラスタ化係数
- インデックスの 2 つの連続したエントリが同じテーブルブロックにある可能性を示す間接的な指標
- オプティマイザは TABLE ACCESS BY INDEX ROWID 処理のコスト計算の際にこれを考慮に入れる
- WEHER 句で使われる述語に合わせてインデックスを作成することでデータをクラスタ化し、この係数を高くできる
- ただし、これ目的でインデックスを作るべきではない
  - あくまで今あるインデックスの拡張で検討する
カバリングインデックス
- インデックスの働きによりテーブルアクセスしなくてもよくなる
- select する列でインデックスを作っているとテーブルアクセスがいらなくなる
インデックスのみのスキャン
- 桁違いにパフォーマンスを改善してくれる
- クラスタ化係数が大きかったり、選択行数が少ない場合はそうでもない
- これのためにインデックスを作成するのは結構攻めたインデックス戦略
- なので基本は WHERE 句を優先し、select 句を考えずにインデックスを作成し、それでも必要なら作るって感じ
ヒープテーブル
- クラスタ化インデックスが作成されていないテーブルのこと
- インデックスによって順序付けされていないテーブル
- ヒープテーブルの場合、インデックスは直接ヒープテーブルのポインタを持つので直接データにアクセスできる
  
  SQL のインデックスとそのチューニングについてのオンラインブックより
クラスタ化インデックス
- 指定したカラム(複合インデックスの場合は複数)で順序付けられたテーブル
- 利点は 2 つ
  - ヒープ構造の分の容量が節約できる
  - クラスタ化インデックスへのすべてのアクセスが自動的にインデックスのみのスキャンになる
- 2 つ以上のインデックスを作ろうとすると不利な点が出てくる
  - セカンダリインデックスはクラスタ化インデックスの論理キー(クラスタリングキー)を持ち、セカンダリインデックスを検索したあと、そのクラスタリングキーを使ってクラスタ化インデックスを検索する必要がある
    
    SQL のインデックスとそのチューニングについてのオンラインブックより
  - クラスタ化インデックスを持つとデータの行事帯がインデックスになるため、並び替えが起こるため、ここへのポインタを持てなくなる

ソートとグルーピング

ソートはリソースを非常に消費する
- ソートの結果を一時的に DB がバッファしておかなくてはいけないから
インデックスを使った order by
- インデックスがすでに並び替えられているのでソートする必要がない
- 入力されたデータをすべて処理する前に最初の結果を返し、処理をパイプライン化できる
- where 句で使われるものと同じインデックスが order by 句もサポートしている必要がある
- 例) sale_date と product_id のインデックスを使った order by
  - sale_date が 1 日単位のデータのため、where 句で 1 日単位に絞ってしれば product_id でソートされた結果があるので処理をパイプライン化できる
  - これが 2 日以上の範囲になると product_id の順では並んでいないためソート処理が発生し、パイプライン化した処理ができなくなる
  - これを確認するには、order by 句を完全に含むインデックスを作成して使ってみるといい
    
    SQL のインデックスとそのチューニングについてのオンラインブックより
複合インデックスでは、定義に使ったカラムに対してすべて ASC、DESC を使っていれば逆順でもインデックスを使った order by を使える
- 双方向連結リストになっているのはこれのため
- これが ASC と DESC が入り混じってくると使えなくなる
  - 同じ場合
    - 逆順をたどればいいのでインデックスが使える
      
      SQL のインデックスとそのチューニングについてのオンラインブックより
  - 入り混じっている場合(sale_date: ASC, product_id: DESC)
    - 頭にあるように日毎にインデックスをジャンプして見ないといけないのでインデックスを使えない
      
      SQL のインデックスとそのチューニングについてのオンラインブックより
    - この場合は order の順序に合わせたインデックスを張ればいい
- クラスタ化インデックスがある場合のセカンダリインデックスは例外
  - セカンダリインデックスは順序の指定があるかどうかに関わらず、インデックスにクラスラリングキーを含める
  - そのため、クラスタリングキーを逆順に並び替えるとき、他の列もすべて逆順に並び替えるしかない
インデックスを使った group by
- DB には 2 つの group by アルゴリズムがある
  - ハッシュアルゴリズム
    - 入力されたレコードを一時的にハッシュテーブル上でまとめ上げる
    - すべてのレコードが処理されたらハッシュテーブルが結果として返される
  - ソート・グループアルゴリズム
    - 入力されたレコードをグループキーでソートすることで各グループを順番に処理できるようにする
    - その後、それらを DB がまとめる
  - 一般的にはどちらも中間結果をマテリアライズする必要があり、パイプライン的に処理されない
  - しかし、ソート・グループアルゴリズムの場合はソート処理が必要なく、インデックスを使えるのでパイプライン化された group by が可能となる
- 例) 先ほどの sale_date と product_id
  - 1 日の範囲内で group by として product_id を指定した場合、インデックスが順番に並んでいるのでソートする必要がないのでインデックスが使えてパイプライン化した group by が使える

部分結果

ページングのような並び替えて最初の 10 件を取りたいといった場合にパイプライン化した order by は有効
- 必要な全レコードを読み込むことなく、必要な件数を取得した時点で結果を出力できる
- オプティマイザが実行計画を準備している時点で最初の 10 件だけ必要みたいな条件は考慮されなかったが、少しずつ考慮されるようになっている
  - MySQL の LIMIT とか SQL Server の TOP みたいなものがそれをオプティマイザに知らせるものになっている
- パイプライン化された order by が使える場合は必要な行数だけとってあとの行は読み込まない
- インデックスが最適化されていない場合、DB はテーブル全体を読み込み並び替えを行う必要があり、テーブルの最後の行を読み込んだあとにしか結果が出力されない
パイプライン化された最初の N 件のみを選択するクエリの優位点
- パフォーマンス向上
- スケーラビリティの改善
  - パイプライン化されていない場合、テーブルサイズに比例して応答時間は長くなる
  - パイプライン化した場合、選択する行数のみに比例する
    - テーブルサイズに関係なく常に一定
      
      SQL のインデックスとそのチューニングについてのオンラインブックより
ページング処理
- 2 ページ目以降を取り出す 2 つの方法
  - オフセット法: 先頭から行に番号をつけて必要なページよりも前の番号のレコードをフィルタする
    - offset を指定するだけなのでかんたんに実装できる
    - ただし、深いページになると、そのページまで行数を数えないといけないのでパフォーマンスが悪くなる
      
      SQL のインデックスとそのチューニングについてのオンラインブックより
    - 2 つの欠点がある
      - 新しいレコードが追加された場合、ページの結果がずれる
      - 深いページになるほど応答時間が遅くなる
  - シーク法: 全ページの最後のエントリを検索し、それ移行の必要な行を読み出す
    - ページ区切りの前ページの値を使うのでオフセット法の問題を回避できる
    - 各ページの最後のエントリの一つあとに来るべき値を検索する
      - そのため、すでに表示した値は選択されない
    - ただし、並び替えの順序は確定的である必要がある
      - sale_date の例だと、1 日に 1 件の売上となっている場合は問題ない
        
        sale_date を指定するとデータも一つに決まる
        
        これが 2 件以上持つとなると、データが一つに決まらないため並び替えがうまく行かない
      - 確定的でない場合
        
        インデックスで他の列を使っていて、それによって確定的になるならそれを使う
        
        それ以外の場合は一意な列をインデックスに追加する
        
        sale_date の例だとプライマリキーを入れると一意に決まる
      - 複数列で確定的になる場合は where で複数指定してやる
    - SQL はこんな感じになる
      SELECT * FROM ( SELECT * FROM sales WHERE sale_date <= ? AND NOT (sale_date = ? AND sale_id >= ?) ORDER BY sale_date DESC, sale_id DESC ) WHERE rownum <= 10
    - SQL の最初の部分はアクセス述語として使われている(sale_date <= ?)
      - sale_date <= ? は日付で必要な条件を指定しているだけで、これだと確定的ではないので 2 つ目が必要
    - 2 つ目の部分はフィルタ述語として使われている(NOT (sale_date = ? AND sale_id >= ?))
      - sale_id を指定して確定的にし、表示済みのレコードを削除している
        
        SQL のインデックスとそのチューニングについてのオンラインブックより
    - 欠点は扱いが難しいこと、任意のページを取り出せないこと、
- オフセット法とシーク法のスケーラビリティ
  
  SQL のインデックスとそのチューニングについてのオンラインブックより

データの変更

insert, delete, update のパフォーマンスに対してインデックスはネガティブな影響を与える
- データに変更を加えるたびにインデックスを最適に保つ必要があるため
挿入
- インデックスの数がパフォーマンスに影響する
  - インデックスの数は insert の実行コストの定数になる
  - インデックスの順序とツリーバランスを保つために重い処理になる
  - 特定リーフノードに属する必要があるため、インデックスをたどっていく必要も出てくる
    - リーフノードが見つかっても、そのノードに十分な空き容量がなければリーフノードを分割する
    - それによってブランチノードからの参照も増え、今後はブランチノードの空き容量がなければさらに上のブランチノードの分割が必要になったりする
    - さらに層を増やしてツリーの階層を深くするなどの処理が走る可能性もある
- where 句を持たないのでインデックスの恩恵を受けられない唯一の処理
- インデックスの数による挿入パフォーマンスの変化
  
  SQL のインデックスとそのチューニングについてのオンラインブックより
削除
- where 句があるのでインデックスの恩恵にあずかることができる
- インデックスからの参照も削除する
- インデックスの数による削除パフォーマンスの変化
  
  SQL のインデックスとそのチューニングについてのオンラインブックより
更新
- データ更新があった場合、インデックスを修正する必要がある
- データを削除し、正しい場所に新しいデータを作る
  - delete 文と insert 分を同時に実行したものと同じ処理時間
- 更新される列が含まれたインデックスのみが更新される
- インデックスと列数による更新のパフォーマンス変化
  
  SQL のインデックスとそのチューニングについてのオンラインブックより
- パフォーマンス最適化には更新する行のみを update する必要がある
  - ただ ORM を使っている場合は難しい

GitHubで編集を提案

目次

インデックスの内部構造

where 句

パフォーマンスとスケーラビリティ

結合処理

データのクラスタリング

ソートとグルーピング

部分結果

データの変更

Discussion