SQL Server/SQL Database再入門 第2回 Index SeekとIndex Scan

# クラスター化インデックスと非クラスター化インデックスの構造

本題のIndex SeekとIndex Scanの話に入る前に、以下の公式サイトを元にSQL Serverで基本となるクラスター化インデックスと非クラスター化インデックスについて確認しておきましょう。
[SQL Server のインデックスのアーキテクチャとデザイン ガイド \- SQL Server \| Microsoft Docs](https://docs.microsoft.com/ja-jp/sql/relational-databases/sql-server-index-design-guide?view=sql-server-ver15)

## B-Treeインデックス

図は次のクラスター化インデックスと非クラスター化インデックスの図をみてください。

* ツリー内の各ページをインデックス ノードと呼びます
* 最上位ノードはルート ノードと呼びます
* インデックス内の最下位ノードをリーフ ノードと呼びます
* ルート ノードとリーフ ノードの間にあるノードは中間レベルノードと呼びます
* ルート ノードと中間レベル ノードの各インデックス行には、キー値と、B ツリー内の中間レベル ページかインデックスのリーフ レベルのデータ行のいずれかへのポインターが含まれています

## クラスター化インデックス

* クラスター化インデックスでは、リーフ ノードに基になるテーブルのデータ ページが含まれています。
* 特に指定しないと、主キーがクラスター化インデックスになります。
* クラスター化インデックスがない状態をヒープと呼びますが、この状態だとSQL Serverは断片化を解消できないのでSQL Serverでは事実上クラスター化インデックスは必須です。

![https://docs.microsoft.com/ja-jp/sql/relational-databases/sql-server-index-design-guide?view=sql-server-ver15](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/7a269160-7173-43aa-857d-c081f8060dc3.png)

## 非クラスター化インデックス

* 非クラスター化インデックスでは、リーフ ノードにヒープもしくはクラスター化インデックスのポインターが含まれています。

![https://docs.microsoft.com/ja-jp/sql/relational-databases/sql-server-index-design-guide?view=sql-server-ver15](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/975565fe-3ded-8c90-41d8-6e14509422a3.png)

## インデックスの構造を確認する

確認するためのテーブルを作ってみます。
ちなみにGOで実行回数を指定できるのですが、私は先月まで知りませんでした。

```sql
CREATE TABLE [dbo].[test](
	[id] [bigint] IDENTITY(1,1) NOT NULL PRIMARY KEY,
	[name] [nvarchar](50) NOT NULL,
	[address] [nvarchar](200) NOT NULL,
	[rgdt] [datetime] NOT NULL
)
GO

INSERT INTO test (name, address, rgdt)
VALUES('a000', 'a000', GETDATE())
GO 300000
```

確認してみましょう。

```sql
SELECT
o.name, 
d.index_id,
d.index_depth, 
d.index_level, 
d.index_type_desc, 
d.page_count,
d.record_count, 
d.avg_fragmentation_in_percent
FROM sys.dm_db_index_physical_stats ( DB_ID(), 
                                      OBJECT_ID('[dbo].[test]'), 
           NULL, 
           NULL, 
           'DETAILED') d
JOIN sys.objects o on o.object_id = 
 d.object_id WHERE d.index_type_desc = 'CLUSTERED INDEX'
```
このインデックスの場合は、深さが3で、リーフのページ数は1745、レコード数は30000になっています。
中間ノードのページ数は7で、レコード数は1745ですね。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/2a1a7f20-5c7f-a1dc-1883-8a7748bfd7fd.png)

非クラスター化インデックスの場合も確認してみます。

```sql
CREATE NONCLUSTERED INDEX IDX_test_rgdt ON test (rgdt) INCLUDE (name);
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/a6a9e36c-b2f7-f82b-3d8b-54bd258b6744.png)


# Index SeekとIndex Scan

Index SeekとIndex Scanの違いを図で表すと以下のような感じになります。Index Seekは探索している対象を一つ一つ、ルートからリーフに向かってアクセスし、SCANはリーフを横串でアクセスして対象を探します。
どちらのアクセスになるかはコスト計算をしてオプティマイザが決めてしまうので、今回はヒントで名指しして動きをみてみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/a7930ca2-8e40-4e7f-3a08-0a0907d84bf0.png)

```sql
SET statistics io on

SELECT
*
FROM test WITH(FORCESEEK)
WHERE id IN (906170, 906171)
```

論理読み取りの数が深さと探索している値の数を掛けた値になっていますね。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/18c52cc6-6d2a-db84-0f94-f041ee002ade.png)

```sql
SET statistics io on

SELECT
*
FROM test WITH(FORCESCAN)
WHERE id IN (906170, 906171)
```

論理読み取りの数がクラスター化インデックスのリーフのページ数と同じ値になっています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/eee971dc-26ae-e83c-25b4-2565fb918c04.png)

キーで範囲検索をしてみます。

```sql
SET STATISTICS IO, TIME ON

SELECT
*
FROM test
WHERE id BETWEEN 130 AND 140

SET STATISTICS IO, TIME OFF
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/1af92195-4cdd-fd19-096a-d57d01a8911e.png)


別の範囲でも検索してみます。

```sql
SET STATISTICS IO, TIME ON

SELECT
*
FROM test
WHERE id BETWEEN 20 AND 30

SET STATISTICS IO, TIME OFF
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/46730330-d6a7-29e3-c68c-6c4cc44ef582.png)

どちらの場合も今回はINDEX SEEKになりました。
論理読み取りの数が違うのは130と140の間にData Pageの境界があるからです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/2ddf7b96-0f4b-e2ca-78bd-6773bf3625f3.png)


# レコード数とINDEXの関係

5件だけ入れてみましょう。

```sql
INSERT INTO test (name, address, rgdt)
VALUES('a000', 'a000', GETDATE())
GO 5
```

この時のインデックスは1階層しかありません。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/37f869d8-6626-70a5-4919-c33494dd41db.png)

190行くらい入れると二階層になります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/75a7c696-bdd9-b6ed-9fd4-9ac1d8f2cc79.png)

もう少し細かく中身をみてみます。

```sql
SELECT
i.type_desc AS [index_type],
i.name AS [index],
page_level AS [page_level],
allocated_page_page_id AS [page_id],
page_type_desc,
previous_page_page_id,
next_page_page_id,
p.allocated_page_file_id AS [file_id]
FROM 
sys.indexes i CROSS APPLY
sys.dm_db_database_page_allocations(DB_ID('sample'), i.object_id, i.index_id, NULL, 'DETAILED') p
WHERE i.name LIKE '%test%' AND page_type_desc IS NOT NULL
```

INDEX_PAGEの289が1つ、DATA_PAGEの288と290ができています。
これは、もともとはDATA_PAGEの288だけがあって、ここに収まりきらなくなったので、INDEX_PAGEの289とDATA_PAGEの290ができたのです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/6849965e-6270-db2f-4581-4e6c64f1b4d4.png)

このようにレコード数が増えてDATA_PAGEに収まらなくなると、ページが分割され、DATA_PAGEの親になるINDEXページが作られます。

さらにレコードを追加し続けると以下のように一つのINDEX_PAGEで収まらなくなり、3階層になります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/45e1c338-e850-eb24-864c-9e9fa6e5e754.png)

理屈ではさらに量が増えると4階層になる可能性もあるんだと思いますが見たことがありません。
4階層になる前にパーティションで分割することになって結果として3階層までで収まるのことなるだろうと思います。

# Indexの中身

Data pageが2個、Index pageが1個しかない単純な状態で確認してみます。

```sql
SELECT
i.type_desc AS [index_type],
i.name AS [index],
page_level AS [page_level],
p.extent_page_id,
allocated_page_page_id AS [page_id],
page_type_desc,
previous_page_page_id,
next_page_page_id,
p.allocated_page_file_id AS [file_id]
FROM 
sys.indexes i CROSS APPLY
sys.dm_db_database_page_allocations(DB_ID('sample'), i.object_id, i.index_id, NULL, 'DETAILED') p
WHERE i.name LIKE 'PK__test__3213E83F49FB8D49'
```

ページは一つずつ確保されるわけではなく、Extent単位で確保されます。
1Extent = 8 Pageです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/86176b3d-a65b-c10c-6137-3a3265ba5225.png)

Index Pageの中身を確認します。

```sql
DBCC TRACEON(3604)
DBCC PAGE ('sample', 1, 13489, 3)
DBCC TRACEOFF(3604)
```

Index Pageの中にkeyの～133はData Pageの13488に、134～はData Pageの13490という指定があることが分かります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/88b867e0-5a08-9f43-ea01-f8c2591203d3.png)

今度はData Pageの中身を見てみます。

```sql
DBCC TRACEON(3604)
DBCC PAGE ('sample', 1, 13490, 3)
DBCC TRACEOFF(3604)
```
クラスタ化インデックスなので、テーブルの実体が入っています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/1dcd07a3-e0b9-461f-02c6-9f05261b48ea.png)

非クラスター化インデックスの中身をみてみます。

```sql
SELECT
i.type_desc AS [index_type],
i.name AS [index],
page_level AS [page_level],
p.extent_page_id,
allocated_page_page_id AS [page_id],
page_type_desc,
previous_page_page_id,
next_page_page_id,
p.allocated_page_file_id AS [file_id]
FROM 
sys.indexes i CROSS APPLY
sys.dm_db_database_page_allocations(DB_ID('sample'), i.object_id, i.index_id, NULL, 'DETAILED') p
WHERE i.name LIKE 'idx_test_name'
```
Index Pageが一つだけあるのが分かります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/d3dffd8f-a528-8a81-d072-c1f2ac90899d.png)


中をみてみましょう。

```sql
DBCC TRACEON(3604)
DBCC PAGE ('sample', 1, 3424, 3)
DBCC TRACEOFF(3604)
```

keyごとのPageIdとKeyHashValueというData Page内で対象行を特定する項目が入っています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/47d720a3-279b-bc19-0fb7-f922f14f9dc0.png)


# シリーズ SQL Server/SQL Database再入門

なんとなくならSQL Serverを使えている人のためのSQL Server/SQL DatabaseのTips集です。

1. [Decimal型とMoney型の違い](https://qiita.com/yyukawa/items/c1e23a97d4170edba23f)
1. [Index SeekとIndex Scan](https://qiita.com/yyukawa/items/4cc1cd5e447b5a5d1b48)
1. [クエリ毎の性能指標の確認方法を知る](https://qiita.com/yyukawa/items/c80151bb9db98de491a2)
1. [SQL Databaseでパーティション テーブルとパーティション インデックス](https://qiita.com/yyukawa/items/902a166c2520793b8116#%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-sql-serversql-database%E5%86%8D%E5%85%A5%E9%96%80)
1. [統計とクエリの関係](https://qiita.com/yyukawa/items/f05b8a2b89e955c94299)
1. [結合方法：NESTED LOOP、MERGE、HASH](https://qiita.com/yyukawa/items/706291047576a654f1e1#merge-join-3)