2013年3月30日土曜日

◆インデックスの構造と内部動作1

データベースの内部構造
データベースの内部構造

インデックスを理解するには、データベースの内部構造を理解しておくことが重要です。まずは、データベースの内部構造から理解していきましょう。
データベースは、次のように「データ ファイル」(.mdf)と「トランザクション ログ ファイル」(.ldf)の 2種類で構成されます。データ ファイルには、テーブルやデータ、インデックス、ビュー、ストアド プロシージャなどが格納されます。

image

ページとヒープ

データ ファイルは、内部的には、「ページ」という 8 KBの大きさで区切られています。ページは、ディスク入出力の単位です。たとえば、テーブルの行サイズが 800バイトであれば、1ページには10行分のデータを格納することができます。実データが格納されているページ全体は「ヒープ」と呼ばれています。
インデックス自体もデータ ファイルへ格納されるので、内部的にはページへ格納されています。したがって、ルート ノードは「ルート ページ」、中間ノードは「中間ページ」、リーフ ノードは「リーフ ページ」とも呼ばれます。

エクステント

データ ファイル内の連続した 8 ページは、「エクステント」と呼ばれ、テーブルやインデックスに割り当てられる領域の単位になります。データが追加されると、エクステントが1つ確保され、その後に追加されるデータが連続した 8 ページに格納されます。これによって、同じオブジェクトのデータが連続した8ページに格納されることが保証されます。テーブル スキャンや後述の Index Scan などの全件検索または範囲検索は、連続したデータにアクセスするので、ページごとではなく、エクステント単位(64KBの大きさ)でまとめて読み込むことでパフォーマンスを向上させています。

非クラスター化インデックスの正確な構造
非クラスター化インデックスの正確な構造

これまでは、インデックスがイメージしやすいようにデータの範囲で説明してきましたが、正確には、インデックス ページにはデータの範囲ではなくデータの値(インデックスを作成した列の値)が格納されます。検索時には、この値と検索条件に指定された値との大小関係によってツリー構造が走査されます。
たとえば、前の Step で作成した、「社員」テーブルの「姓」列に対する非クラスター化インデックスの構造は、次のようになります(データ量が少ない場合は、2階層のインデックスが作成されます)。

image

このインデックスの構造の場合に、「Aoki」さんのデータを検索する場合は、まずルート ページへアクセスして、「Aoki」さんが、「Andou」さんと「Asari」さんの間のデータであることが分かるので、下位ページ(リーフ ページ)の 102 ページへアクセスします。
102 ページ内で「Aoki」さんのデータを探し、見つかったら、その行識別子(1:131:5)から、データ ファイルID が 1(.mdf ファイル)、ページ番号が 131、そのページ内の 5行目に、実際のデータがあることが分かります。
このように、インデックスを利用することで、すべてのデータを検索することなく、わずか数ページを読み取るだけで該当のデータを取得することができます。

Note: SET STATISTICS IO コマンドでクエリが読み取ったページ数を確認
クエリが実際に読み取ったページ数は、SET STATISTICS IO コマンドを利用すると調べることができます。これは、次のように実行します。
SET STATISTICS IO ON
実行後、SELECT ステートメントを実行して、[メッセージ]タブをクリックすると、次のように「論理読み取り数」が表示されて、クエリが読み取ったページ数を確認することができます。
image
このコマンドは、接続が終了するか、、次のように SET STATISTICS IO を OFF に設定するまで有功です。
SET STATISTICS IO OFF
読み取ったページ数

インデックスの階層数の調査: dm_db_index_physical_stats
インデックスの階層数の調査

dm_db_index_physical_stats 動的管理関数は、インデックスの階層数や使用しているページ数を調べることができる大変便利な関数です。構文は次のとおりです。

image

index_level 列で、インデックスの階層番号(リーフが 0、その上位は 1 からの連番)、page_count 列で、使用しているページ数を取得することができます。
第1~第4引数へは、調べたいインデックスのデータベースやテーブル、インデックスを ID で指定し、NULL を指定することも可能です。NULL を指定した場合は「すべて」を意味し、たとえば、テーブル ID に NULL を指定した場合は、すべてのテーブルを対象にすることができます。
個別に ID を指定する場合は、「データベースID」は DB_ID 関数、「テーブルID」は OBJECT_ID 関数から取得することができます。
「インデックスID」は、次のように sys.indexes カタログ ビューから取得することができます。

image

name 列でインデックスの名前、index_id でインデックスID を取得することができます。

スキャンモード

dm_db_index_physical_stats 関数の第5引数のスキャン モードには、「LIMITED」、「SAMPLED」、「DETAILED」の 3つがあります。インデックスの使用ページ数を調べるには、DETAILED モードを指定する必要があります(3つのモードの詳しい違いについては、Step 4 で説明します)。

Let's Try
  1. まずは、sys.indexes カタログ ビューをクエリして、Step 2 で作成した「index_姓」非クラスター化インデックスのインデックスID を調べます。
    image
    image
    index_id 列が「3」となっているので、インデックスID が 3 であることを確認できます。
  2. 次に、dm_db_index_physical_stats 関数を利用して、「index_姓」インデックスの階層数と使用しているページ数を調べます。
    image
    index_level 列には、「1」と「0」が表示され、「0」はリーフ ページ、「1」以上は中間ページより上の階層になり、一番大きい値がルート ページになります。したがって、今回は「1」が一番大きい値なので、これがルート ページになります(インデックスが 2階層で構成されていることが分かります)。

    Note: 隠しコマンドの DBCC IND と DBCC PAGE でインデックスの中身を見る
    インデックスは、dm_db_index_physical_stats 関数で階層数と使用ページ数を調べることができますが、インデックスの中身までは見ることができません。インデックスの中身を見るには、ページの中身を見るための隠しコマンド(ヘルプへ記載されていないコマンド)の「DBCC IND」と「DBCC PAGE」を利用する必要があります。
    DBCC IND コマンドでは、インデックスが使用しているページ番号を取得することができ、たとえば、次のように入力すると、index_姓(インデックスID が 3)の使用しているページ番号を取得することができます。
    DBCC IND(sampleDB, 社員, 3)
    image結果の PagePID 列は、インデックスへ割り当てられているページ番号で、IndexLevel 列は「0」がリーフ ページで、「1」以上は、リーフより上の階層を表します。
    ここで調べたページ番号を DBCC PAGE コマンドの第3引数へ与えることで、そのページの中身を見ることができるようになります。たとえば、次のように入力すると、ページ番号「179」の中身を参照することができます。
    DBCC PAGE(sampleDB, 1, 179, 3)
    image
インデックスを作成しても効果のない列
インデックスを作成しても効果のない列

インデックスを作成すれば、基本的にはパフォーマンスが向上しますが、作成してもパフォーマンスの向上が見込めないケースがあります。代表的なのは次の 2つです。

  • WHERE句の検索条件にほとんど使用されない列
    検索条件にほとんど使用されない列に対してインデックスを作成しても、効果はありません。逆に、作成したことによってパフォーマンスの低下を招く恐れがあります。インデックスを作成すると、インデックスを作成した列のデータを更新した際に、インデックスそのもの(ツリー構造)も更新されるからです。したがって、検索条件にほとんど使用されない列で、かつ更新頻度が過剰な列に対してはインデックスを作成しないことをお勧めします。

    Note: 使用されていないインデックスを探すには?
    動的管理ビューの「dm_db_index_usage_stats」を利用すると、SQL Server の起動後に、1 度も使用されていないインデックス(未使用のインデックス)や、使用回数の少ないインデックスを探すことができます。具体的な利用方法については、本自習書シリーズの「監視ツールの基本操作」で詳しく説明しています。
  • 検索条件に該当するデータが大量にある場合
    インデックスは、大量のデータから 1~ 数百件のデータを取り出すときに最も効果があります。検索条件に該当するデータが大量にある場合には、インデックスの効果が得られません。該当データが多い場合には、RID Lookup で(リーフレベルのポインターを使用して)実際のデータを取得すると、テーブル スキャンよりも効率が悪くなることがあるからです。
    image
    SQL Serverは、インデックスを使用するよりもテーブル スキャンの方が効率が良いと判断した場合には、テーブル スキャンを使用してデータ検索を実行します。
Let's Try: 「性別」列へインデックスを作成した場合の動作
  1. まずは、社員テーブルの「性別」列へインデックスを作成してみましょう。

    CREATE INDEX index_性別 ON 社員(性別)

  2. 次に、グラフィカル実行プランの表示を有効にして、性別が「男性」の社員のみを検索してみましょう。

    SELECT * FROM 社員 WHERE 性別 = '男性'


    image結果は、テーブル スキャンが実行されていることを確認できます。
    このようにデータの種類が少ない場合(性別列は「男性」と「女性」の 2種類)は、検索条件に該当するデータが自ずと多くなるので、インデックスを作成しても利用されません。SQL Server は、インデックスを使用するよりもテーブル スキャンの方が効率が良いと判断したした場合は、テーブル スキャンを使用してデータ検索を実行するのです。
  3. このインデックス「index_性別」は、不要なので削除しておきます。
    DROP INDEX 社員.index_性別
検索条件に該当するデータ件数が多い場合

続いて、「姓」列に対して、検索条件に該当するデータ件数が多い場合に、インデックスが利用されるかどうかを確認してみましょう。

  1. データ件数を多く取得するために、次のように LIKE 演算子を利用して、姓が「A」で始まる社員を検索してみましょう。

    SELECT * FROM 社員 WHERE 姓 LIKE 'A%'


    image結果が表示され、293 件のデータが検索条件に該当し、テーブル スキャンが実行されたことを確認できます。このインデックスは、「姓='Aoki'」という検索条件のときには Index Seek が実行されていました。
    このように、検索条件に該当するデータ件数が多い場合には、インデックスが利用されず、テーブル スキャンが実行されます。

    Note: クエリ オプティマイザーによる最適な実行プランの選択
    データの検索時に、どのインデックスを利用するかや、インデックスを利用しないでテーブル スキャンを実行するかは、SQL Server の「クエリ オプティマイザー」という機能(プログラム)が判断します。クエリ オプティマイザーは、検索条件に該当するデータを取得するために、インデックスよりもテーブル スキャンを利用したほうが「高速」だと判断した場合は、テーブル スキャンを実行します。オプティマイザーは、I/O コスト(ディスク入出力の負荷がどれくらいか)、と CPU コスト(CPU への負荷がどれくらいか)などをもとに判断しています。
インデックスが役立たない例

条件に該当するデータ件数が少ない場合でも、SQL ステートメントの書き方が悪いと、インデックスを利用しない(Index Seek が実行されない)非効率な検索が行われます。これは、次の 3 つのケースです。

  • LIKE 演算子を利用する際に、先頭に %(ワイルド カード文字)を指定している場合
    image
  • 演算子の左辺へ「関数」や「計算式」を記述している場合
    image
  • 列へ設定してある照合順序とは、異なる照合順序を指定している場合
    image
Let's Try: LIKE の先頭に % を指定した場合
  1. まずは、LIKE 演算子で先頭をワイルドカード指定した場合の検索を試してみましょう。ここでは、検索条件に「姓 LIKE '%oki'」と指定して、姓が「oki」で終わる社員を検索してみます。
    image
    image
    グラフィカル実行プランには、Index Scan と RID Lookup が表示され、Index Seek ではないことを確認できます。
    このように、LIKE 演算子の先頭がワイルド カード文字の場合は、Index Seek が実行されません。
Index Scan とは

Index Scan(インデックス スキャン)は、Index Seek のアイコンと非常に似ていますが、内部動作は大きく異なります。Index Scan は、インデックスのツリー構造を利用せずに、リーフ ノードを横方向へ全スキャンして、該当データを探し出す内部動作です。したがって、Index Scan は、Index Seek よりも多くのページにアクセスすることになるので、効率の悪い検索方法です(Index Seek よりも実行時間がかかります)。
image

関数処理をしている場合
  1. ここでは、UPPER 関数を利用して、検索を実行してみましょう。
    image
    結果は、Index Scan と RID Lookup になり、Index Seek が実行されていないことを確認できます(Index Scan によって、リーフページを全スキャンしているので、効率の悪い検索が実行されています)。
クラスター化インデックス
クラスター化インデックス

今までは、「非クラスター化インデックス」について説明してきましたが、ここからは、もう 1つのインデックス「クラスター化インデックス」について説明します。
非クラスター化インデックスとクラスター化インデックスの違いは、非クラスター化インデックスではリーフ レベルへ実際のデータへのポインター(行識別子:RID)が格納されるのに対して、クラスター化インデックスの場合は、リーフ レベルにはポインターではなく実際のデータそのものを格納するところです。
クラスター化インデックスを作成すると、実際のデータが物理的に並べ替えられて、クラスター化インデックスのリーフ ページとなり、ヒープが削除されます。
たとえば、社員テーブルの「姓」列に対してクラスター化インデックスを作成すると、次のようになります。

image
このように、クラスター化インデックスでは、実際のデータがインデックス内へ吸収されるので、非クラスター化インデックスよりも検索のパフォーマンスが向上します。

クラスター化インデックスの作成

クラスター化インデックスを作成するには、CREATE INDEX ステートメントで、次のように CLUSTERED を指定します。

image

クラスター化インデックスを、オブジェクト エクスプローラーから作成する場合は、次のように操作します。
image

image

Let's Try

それでは、クラスター化インデックスを作成してみましょう。

  1. まずは、「姓」列へ作成していた非クラスター化インデックス「index_姓」を削除します。
    image
  2. 次に、「姓」列に対してクラスター化インデックスを作成します。
    image
  3. 次に、sys.indexes カタログ ビューをクエリして、クラスター化インデックスのインデックス ID を確認してみましょう。
    image
    image
    インデックスID(index_id)は、「1」であることを確認できます。このように、クラスター化インデックスのID は、常に 1 になります。
  4. 続いて、dm_db_index_physical_stats 関数を利用して、クラスター化インデックスの階層数と使用しているページ数を確認してみましょう。
    image
    index_level が、「2」、「1」、「0」とあることから、このインデックスが 3階層であることが分かります。index_level の「0」がリーフ ページ、「1」が中間、「2」がルート ページです。また、クラスター化インデックスの場合は、リーフ ページ「0」が実データのページ数なので、実際のデータが「560」ページであることも確認できます。
  5. 次に、「姓」列が「Aoki」さんの社員を検索して、クラスター化インデックスの効果を確認してみましょう。
    image
    image
    実行プランを確認すると、「Clustered Index Seek」というアイコンが表示され、インデックス名「社員.index_姓」を確認することができます。これは、クラスター化インデックスを利用して検索を行ったという内部動作です。また、RID Lookup のアイコンがないところにも注目してください。クラスター化インデックスのリーフページは実際のデータが格納されているので、RID Lookup は必要なく、クラスター化インデックス内の Seek だけでデータを取得することができるのです。
    このように、クラスター化インデックスは、RID Lookup をしなくて済む分、非クラスター化インデックスよりも検索のパフォーマンスが向上します。
  6. 次に、検索条件を「姓 LIKE 'A%'」へ変更して、該当データ件数が多くなるように、データを検索してみましょう(これは、非クラスター化インデックスのときは、テーブル スキャンになった検索です)。
    image
    結果は、293 件の結果が返り、実行プランを確認すると、Clustered Index Seek が表示されて、クラスター化インデックスの Seek のみで検索が完了したことを確認できます。
    クラスター化インデックスでは、リーフ レベルに実際のデータが昇順に並び替えられているので、このような検索(先頭文字を指定した範囲検索)であっても、インデックスを利用して高速にデータを取得することができます。

Clustered Index Scan とテーブル スキャン

次に、クラスター化インデックスを作成した「姓」列以外の列を利用して検索してみましょう。

image

実行プランを確認すると、「Clustered Index Scan」というアイコンが表示されます。このアイコンは、Clustered Index Seek と非常に似ていますが、意味は大きく異なります。
「名」列には、インデックスを作成していないので、テーブル スキャンが実行されるはずですが、Clustered Index Scan と表示されています。このアイコンは、クラスター化インデックスのリーフレベルを横方向へ全件スキャンしたという内部動作です。つまり、実行されていることはテーブル スキャンとほとんど同じです。これは、クラスター化インデックスを作成すると、実際のデータがインデックスに吸収されるので、「テーブル = クラスター化インデックス」となり、テーブル スキャンという概念がなくなるためです。

0 件のコメント:

コメントを投稿