SQLServerのインデックスについての基礎の基礎。

### はじめに

SQL Serverの記事２本目です。

前回、Profilerの使い方をまとめ、パフォーマンスチューニングを行うためのツールの紹介をしました。

https://qiita.com/s_moriyama/items/fc3c7ac27d2dfb21aabd

今回はパフォーマンスチューニングの為の基礎知識であるインデックスについての記事です。

似た記事は既に多くありますが、私がこれからインデックスを知らない人にどうやって教えるかな？って考えた時の構成で記載してみました。

## インデックスはなぜ必要か？

### 辞書で理解するインデックス

わかりやすい例えで「辞書」が良いのかなと思います。
辞書で調べたい単語などを探すとき、どのように探しますか？

例えば、「鮮度」という言葉を調べる場合、索引ページや、小口部分から「せ」で始まるページを探し、次に２文字目が「ん」になっている箇所を探していき、最終的に探したい単語を見つけると思います。

このような段階的に検索範囲を絞り込んでいく仕組みが、データベースにおけるインデックスの考え方とよく似ています。

### なぜ効率的な検索が可能なのか

辞書で素早く目的の言葉を見つけられるのは、すべての言葉が「あ」から「ん」までの順に整理されているからです。この「並び順」という規則があるからこそ、効率的な検索が可能になります。

データベースのインデックスも同様に、データが特定のルールに従って整列されていることが前提となっています。

例えば、1000ページある書籍から「バナナ」という単語を探す場合を考えてみてください。

もしページの内容が順不同であれば、目的の単語を見つけるために1000ページすべてを確認する必要があるため、非常に非効率的です。

一方、辞書のように整列されていれば、必要な範囲だけを確認すれば良いのです。

また、以下のような事象もすべてのページを確認しないと確定できません。

* バナナが書籍内に存在しないこと
* バナナが書籍内に存在すること
    * 1回のみ登場する？
    * 複数回登場する？

インデックスは大量のレコードの中から必要な情報を高速に取得するための技術となります。

データベースの性能がシステム全体の性能に大きく影響するため、パフォーマンスチューニングが必要なのです。

## SQL Serverにおけるデータと索引

### データ ストレージの基本単位「ページ」

SQL Serverでは、データは「ページ」と呼ばれる8KBの単位で管理され、連番が付与されています。

これらのページは、必ずしも論理的な順序で保存されているわけではありません。
たとえば、顧客データを保存する場合：

* 社員ID「001」
    * データがページ1に
* 社員ID「002」
    * データがページ105に
* 社員ID「003」
    * データがページ50に

というように、物理的には順不同で格納されています。

詳細は下記ページを確認いただければと思いますが、ここでは初期状態は順不同で並んでいるので、先ほどの辞書の例でいう、索引がないことを理解頂ければよいです。

https://learn.microsoft.com/ja-jp/sql/relational-databases/pages-and-extents-architecture-guide?view=sql-server-ver16

### データベースにおける索引（インデックス）

社員データベースでの検索パターンを考えてみます。

```mermaid
erDiagram
    Shain {
        int id "社員ID"
        string name "社員名"
        date birth_date "生年月日"
        string gender "性別"
        date hire_date "入社日"
        date leave_date "退職日"
        string email "メールアドレス"
        string phone "電話番号"
    }
```

よくある検索パターン例：

* 社員IDによる検索
    * 「社員ID: 1234の社員情報を表示したい」
* 社員名による検索
    * 「田中さんの連絡先を知りたい」
* 「2024年4月入社の新入社員一覧を出して」
    * 研修対象者の抽出時
* 生年月日による検索
    * 「今月誕生日の社員を探して」

このように、辞書とは異なり、検索パターンは多岐にわたります。

私たちはビジネス要件に従い、適切な索引（インデックス）を複数作成していく必要があります。

## B+Tree

### B+Treeとは

SQL Serverは二分探索木の仕組みでインデックスを構築しており、その中でもB+Treeという構造を使用しています。

```mermaid
graph TD
    R["ルートノード"]
    I1["中間ノード"]
    I2["中間ノード"]
    L1["リーフノード"]
    L2["リーフノード"]
    L3["リーフノード"]
    L4["リーフノード"]
    
    R --> I1
    R --> I2
    
    I1 --> L1
    I1 --> L2
    
    I2 --> L3
    I2 --> L4   
    
    style R fill:#f9f,stroke:#333,stroke-width:2px
    style I1 fill:#bbf,stroke:#333,stroke-width:2px
    style I2 fill:#bbf,stroke:#333,stroke-width:2px
    style L1 fill:#dfd,stroke:#333,stroke-width:2px
    style L2 fill:#dfd,stroke:#333,stroke-width:2px
    style L3 fill:#dfd,stroke:#333,stroke-width:2px
    style L4 fill:#dfd,stroke:#333,stroke-width:2px
```

:::note warn
実際はリーフページ間でも繋がりがあるのですが、ここでは見易さの為、省略しています。
:::


### 基本構造

* ルートノード
    * ツリーの最上位
    * 実際のデータは持たず、索引のみ保持
* 中間ノード
    * データの振り分けを行う
    * 実際のデータは持たず、索引のみ保持
* リーフノード
    * 実際のデータを保持

### メリット

B+Treeの利点は複数ありますが、データが指数関数的に増えても、対数関数的にしか検索回数が増えないところが大きな利点です。

例えば、1ノードに3つのリーフページが入るB+Treeの場合、深さ・データ件数及び、検索回数の関係以下のようになります。

* 深さ1
    * データ数：3件
    * 検索回数：1回
* 深さ2
    * データ数：9件(3^2)
    * 検索回数：2回
* 深さ3
    * データ数：27件(3^3)
    * 検索回数：3回
* 深さ4
    * データ数：81件(3^4)
    * 検索回数：4回
* 深さ5
    * データ数：243件(3^5)
    * 検索回数：5回

また、B+Treeはリーフの深さが同じであるため、どのデータの検索においても、同じ速さで検索を行うことが可能です。

### 例：1~10の値をインデックス

実際に1から10のノードを格納したB+Treeです。

範囲指定の場合でも、起点・終点のリーフノードが分かれば、効率的に検索できます。

```mermaid
graph TB
    subgraph ルートノード
        Root[("4 | 7<br/><i>振り分けポイント</i>")]
        style Root fill:#ff9999,stroke:#333
    end
    
    subgraph 中間ノード
        N1[("2 | 3<br/><i>検索経路</i>")]
        N2[("5 | 6<br/><i>検索経路</i>")]
        N3[("8 | 9<br/><i>検索経路</i>")]
        style N1 fill:#99ff99,stroke:#333
        style N2 fill:#99ff99,stroke:#333
        style N3 fill:#99ff99,stroke:#333
    end
    
    subgraph リーフノード
        direction LR
        L1["1"] -->
        L2["2"] -->
        L3["3"] -->
        L4["4"] -->
        L5["5"] -->
        L6["6"] -->
        L7["7"] -->
        L8["8"] -->
        L9["9"] -->
        L10["10"]
        
        style L1 fill:#9999ff,stroke:#333
        style L2 fill:#9999ff,stroke:#333
        style L3 fill:#9999ff,stroke:#333
        style L4 fill:#9999ff,stroke:#333
        style L5 fill:#9999ff,stroke:#333
        style L6 fill:#9999ff,stroke:#333
        style L7 fill:#9999ff,stroke:#333
        style L8 fill:#9999ff,stroke:#333
        style L9 fill:#9999ff,stroke:#333
        style L10 fill:#9999ff,stroke:#333
    end
    
    Root --> N1
    Root --> N2
    Root --> N3
    
    N1 --> L1
    N1 --> L2
    N1 --> L3
    
    N2 --> L4
    N2 --> L5
    N2 --> L6
    
    N3 --> L7
    N3 --> L8
    N3 --> L9
    N3 --> L10

```

## インデックスの種類

代表的なものだけ紹介しますが、その前にインデックスがない状態で実行計画を確認してみます。

50,000件のデータに対して、IDを指定して検索を行う単純なSQLです。
（実行計画上、パーセンテージが高いところが性能に影響しているところです。）

![スクリーンショット 2024-11-11 4.35.47.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894042/cdcc470a-ae28-da7c-3609-bc625a0cf436.png)

Table Scan（テーブル全走査）にて、50,000件のレコードの読み取りが実施されていることが性能に影響していることがわかります。

![スクリーンショット 2024-11-11 4.37.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894042/86499ec8-1875-3633-f73c-56d1fe494480.png)

### 非クラスター化インデックス (Non-Clustered Index)

内容説明の前に動作確認をします。

下記DDLで、非クラスター化インデックスを作成し、再度実行計画を確認します。

```sql
CREATE NONCLUSTERED INDEX IX_Shain_ID ON Shain(ID);
```

![スクリーンショット 2024-11-11 4.44.13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894042/d8b338bf-c47f-bd04-4935-55a537dd0c37.png)

Table Scanがなくなり、新たにIndex SeekとRID Lookupの２つの動作が出てきました。

#### Index Seek

Table ScanがIndex Seekに変わったのですが、読み取った行数が1になっています。

この動作から、適切にインデックスが適用されていることがわかります。

![スクリーンショット 2024-11-11 4.49.03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894042/665681b8-a4c0-8aee-047c-69062c5a8bbb.png)

パフォーマンスチューニングの基本は、このScanをSeekに変更していくことです。

Table Scanとは別に、Index ScanというScanもありますが、これも同様に低速です。

#### RID Lookup

RID Lookupとは、Select結果を取得するために行なっている操作です。

ここが、非クラスター化インデックスの特徴ですが、指定したインデックス項目を基にB+Treeが作られますが、末端のリーフノードには、RID(Row ID)と呼ぶ、実データの参照先を示すアドレスが格納されています。

このため、インデックスを構成する項目以外の項目を取得する場合は、RIDから実データを取得する必要があり、RID Lookup分のオーバヘッドが発生するのです。

インデックスを構成するidのみを取得するように変更すると、RID Lookupは発生しません。

![スクリーンショット 2024-11-11 4.57.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894042/1172db4c-1d4d-b2f8-dc47-645706b728fa.png)

非クラスター化インデックスにSelectで必要な情報を付与する付加列インデックスというものもありますが、データの二重持ちになるため、データ容量やインデックス再構築時のコストなどの考慮は必要になります。

また非クラスター化インデックスは明示的にインデックスを作成しなくても、ユニークキーを指定することで自動生成されます。

### クラスター化インデックス (Clustered Index)

次にクラスター化インデックスを作成し、動作確認します。

```sql
CREATE CLUSTERED INDEX IX_Shain_ID ON Shain(ID);
```

![スクリーンショット 2024-11-11 5.02.50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894042/24c9d177-2124-0f74-746f-54172caf8933.png)

![スクリーンショット 2024-11-11 5.12.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894042/5b2663ec-b9ec-464c-1edc-ffff8a887732.png)

こちらは、RID Lookupが発生していません。
これはリーフノードに実データが格納されているためです。

クラスター化インデックスはテーブルの実データ（ページ）の並び順を決定する、１つのテーブルで１つだけの作成できるインデックスです。

また、クラスター化インデックス作成後は、RID LookupはKey Lookupという名称に変更されます。

![スクリーンショット 2024-11-11 5.18.52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894042/ba891547-6883-dc21-b256-fd61bdecc778.png)

これはクラスター化インデックス作成により、実データ参照ではなく、クラスター化インデックスからデータを参照するように挙動が変わるためです。

よって、クラスター化インデックスはRID/Key Lookup操作がないため、このインデックスを利用するのが最速になります。

ただし、再構成に時間が掛かるので、注意が必要です。
単純増加のような連番を使うことで、再構築のオーバーヘッドを減らすことができます。

またクラスター化インデックスは明示的にインデックスを作成しなくても、主キー（プライマリキー）を指定することで自動生成されます。

## さいごに

まだまだ記載できることがありそうですが、いったんこの記事ではここまでとします！
文章があまり上手ではなくて、若干心苦しいです。

次の記事で、実際にパフォーマンスチューニングに関する記載を書いていこうと思います。