クラスター化インデックスのストーリー

Oracleを使用してSQL Serverにアップグレードした後は、驚くべきことがたくさんあります。 自動トランザクションに慣れるのは困難です-更新後、commitを入力する必要はありません（これは素晴らしいことですが）が、エラーが発生した場合はrollback（単なる悪夢）を入力することはできません。 ジャーナルがロールバックとローリングトランザクションの両方に使用されるアーキテクチャに慣れるのは困難です。 「作家は読者をブロックし、読者は作家をブロックします」という状況に慣れることは難しく、慣れると習慣を破ることはさらに難しくなります。 そして、難易度のランキングの最後の場所は、クラスター化されたインデックスの優位性によって演じられるわけではありません。 既定では、テーブルの主キーはクラスター化インデックスであるため、ほとんどすべてのテーブルにクラスター化インデックスがあります。



実際、この獣は完全に大胆不敵であり、非常に便利です。 それがなぜ必要なのか、どうやって使うのかを考えてみましょう。

ファイル、ページ、RID

テーブルのデータは物理的にデータベースファイルに保存されます。 データベースファイルは、ページ（ページ）-サーバーの論理ストレージユニットに分割されます。 MS SQL Serverのページのサイズは8キロバイト（8192バイト）である必要があり、そのうち8060バイトはデータ用です。 各行に対して、その物理アドレス、いわゆる行ID（RID）を指定できます。これは、ファイルが配置されているファイル、このファイルのページの順序、ページの場所です。 テーブル全体でページが割り当てられます。1つのページには、1つのテーブルのデータしか存在できません。 さらに、行の読み取り/書き込みが必要な場合、サーバーはページ全体の読み取り/書き込みを行います。これははるかに高速だからです。

Bツリーインデックスはどのように配置されますか？

Bツリーとは、バランスツリー、つまり「バランスツリー」を意味します。 インデックスには、検索のエントリポイントであるルートページが1つだけ含まれています。 ルートページには、キー値と、これらのインデックス値の次のレベルのページへのリンクが含まれています。 インデックスで検索すると、目的の値を超えない最後の値が見つかり、対応するページへの遷移が発生します。 ツリーの最後のリーフレベルには、すべてのキーが一覧表示され、各キーにはテーブルデータへのリンク（ブックマーク）が示されます。 リンクロールの自然な候補はRIDであり、実際にはヒープケースに使用されます。 次の図では、文字Bはテーブル行へのリンクを示しています。







テーブルにエントリを追加するときは、インデックスにも追加する必要があります。 テーブルエントリを参照する新しいインデックスエントリがリーフレベルページに挿入されます。 このページに空き領域がないことが判明する場合があります。 次に：

1. インデックスには、リーフレベルでも新しいページが割り当てられます。
2. 前のページのレコードの半分は新しいものに転送されます（したがって、それらを順番に追加するときに、次の行のページを再度選択しなければならない状況に陥ることはありません）。 新しいページが水平リンクに埋め込まれます。前の次の代わりに、前の新しい次のリンクが設定されます。
3. 新しいページへのリンクが、対応するキーとともに親ページに提供されます。 同時に、親ページがオーバーフローする可能性があります-その後、データ分離のプロセスがより高いレベルで繰り返されます。 オーバーフローが最上部に達すると、ルートページが2つに分割され、新しいルートが表示され、ツリーの高さが1増加します。

インデックスの存在下でテーブルにレコードを追加することは明らかに費用のかかるプロセスになることは明らかです。各ページ分割では、少なくとも4ページ（共有、共有、新しい、親）を更新する必要があります。

同時に、インデックスの存在はデータ検索を劇的に加速します。連続スキャンの代わりに、ツリー内を下るバイナリ検索を実行できます。 また、1レベルのページへの水平リンクが存在するため、インデックスキーの範囲を非常に迅速に通過することができます。 また、選択の主なタスクである単一値の検索と範囲のスキャンにスムーズにアプローチします。

ヒープが小さい

ヒープの形式で編成されたモデルテーブルを考えてみましょう。レコードには特定の順序がありません。

レコードが最初に受信するRIDは、ほとんど常にそれと共に残ります。 まれに、ヒープ内のエントリが別のページに移動されることがあります。これは、更新後、行が占有した場所に収まらなくなったときに発生します。 ただし、この場合、新しい場所へのリンクは同じ場所に残ります。つまり、追加するときに文字列が受信したRIDを知っていれば、文字列は常に見つかります。 したがって、ヒープ上のインデックスの場合、データを参照するための最適な選択肢はRIDです。



テーブルに20万のエントリがあり、各ページに48〜52のエントリが配置されているとします。 テーブルは4000ページを占有すると仮定します。 [City]フィールドの値が「Perm」であるすべてのレコードを検索する必要があるとします。 また、そのうちの3つしかないことも想定していますが、まだわかりません。



サーバーは、4,000ページすべてをスキャンする必要があります。 サーバーが3つすべてのエントリを検出した場合でも、最後まで行かなければなりません。必要なエントリがもうないという保証はありません。 したがって、要求を完了するには、4,000の論理ページ読み取りが必要です。

そして、バイナリ検索で検索できるインデックス、たとえば高さ3のツリーがあるとしますか？ サーバーは、最初のレコードのアドレスを見つけるために、インデックスページを3回読み取る必要があります。 2番目と3番目のレコードのアドレスは、同じページまたは次のいずれかで横に並んでいます。インデックスページはリンクによって水平方向にリンクされています。 つまり、最大4回の読み取り後、サーバーはおそらく3つすべてのレコードのRIDを知っています。 非常に運が悪い場合、3つのエントリはすべて異なるページにあります。 したがって、ページの7回の論理読み取りの後にインデックスが存在する場合、3つのレコードがすべて見つかる可能性があります。 7対4000-印象的。



しかし、レコードが少ない場合はとても良いでしょう。 そして、これが「パーマ」ではなく「モスクワ」であり、必要な記録が3ではなく、2万である場合はどうでしょうか。 これはそれほど多くはなく、レコードの総数の10パーセントにすぎません。 しかし、写真はすぐにそれほどバラ色ではなくなりました。



3回の読み取りの場合、サーバーは最初のレコードを見つけます。 そして、彼は2万RIDを読み取り、ページを2万回読み取って行を取得する必要があります。サーバーは、ページ全体のデータのみを読み取ることを覚えています。 必要なレコードがテーブル全体に散らばっていることが判明する可能性があります。また、2万件の論理読み取りを確保するには、ディスクからほとんどのページを読み取る必要があります。 すべてではないにしても、まだ良い。 4000の論理読み取り値の代わりに、20,000を取得します。



インデックスは、少数の値を見つけるのに非常にうまく機能しますが、大きな範囲を超えるとうまく機能しません。



クエリオプティマイザーはこれをよく認識しています。 したがって、インデックス検索ではインデックス検索の代わりに十分に大きな範囲が得られると予想する場合、テーブル全体のスキャンを選択します。 ちなみに、これはオプティマイザが正しい統計を使用していても間違える可能性のあるまれな場所の1つです。 実際に必要なデータが非常にコンパクトな場合（たとえば、2万回の論理読み取り-ディスクからブロックを60回読み取り、キャッシュ内のブロックを19940回読み取ります）、インデックスを強制的に使用すると、メモリと速度が向上します。

しかし、範囲はどうですか？

問題は、インデックス検索の終了時に、サーバーがデータを受信せず、サーバーが存在するアドレスのみを受信することです。 サーバーはまだこのアドレスに行き、そこからデータを取得する必要があります。 データがパスの終わりにすぐに置かれたら素晴らしいでしょう！

実際、いくつかの嘘。 たとえば、キー値は正確にインデックス内にあります。それらに従う必要はありません。 キー以外のフィールドのみ。 また、キー以外のフィールドもインデックスに配置されるとどうなりますか？ さて、すべてではなく、スキャンリクエストに必要なものだけを考えてみましょう。



そしてその場合、追加の（含まれた）列を持つインデックスがあります 。 通常のインデックスのサイズでは失われます。そのリーフページには、文字列のキーとアドレスだけでなく、データの一部も含まれます。 単一の値の検索では、そのようなインデックスはそれほど悪くなく、範囲のスキャンでははるかに優れています。 インデックスがクエリをカバーしている場合（つまり、クエリにリストされているすべての列が含まれている場合）、クエリを実行するためにテーブルはまったく必要ありません。 ブックマークに頼らずにインデックスから必要なすべてのデータを取得する機能は、大きなメリットをもたらします。



モデルの例に戻りましょう。 クエリに必要な列がインデックスに含まれているとします。 簡単にするために、正確に50のレコード（キー、追加された列、レコードへのリンク）がインデックスのリーフページに分類されると仮定します。 次に、2万件のレコードをスキャンする場合、非カバーインデックスの2万件の論理読み取りではなく、400インデックスページだけを読み取る必要があります。



2000に対して400-差は50倍です。 クエリオプティマイザーが特定の列をインデックスに含めることを提案することを好むのは当然のことです。

それとも、インデックスにすべての列を追加する価値があるのでしょうか？ その後、すべてのリクエストはインデックスでカバーされます。 さらに、リーフではRIDも必要ありません。そのようなインデックスは、データを取得するためにテーブルにアクセスせず、手元にすべてのものがあるためです。 はい、この場合、テーブル自体は不要になりました！



そして、 クラスタ化インデックスの概念に到達しました 。 通常のBツリーのように配置されますが、リーフページのテーブルレコードへのリンクの代わりに、データ自体が配置され、それとは別のテーブルはありません。 テーブルはクラスター化インデックスを持つことはできず、クラスター化インデックスにすることができます 。

クラスタ化インデックスでのキースキャンは、テーブル全体のスキャンよりも優れています。 すべてのレコードの97％をスキャンする必要がある場合でも。

キャッチはどこですか？

最初の-それはどこで明確です。 クラスタ化インデックスはテーブルであり、テーブルは1つしか存在できません。 サーバーにはデータのマスターコピーが必要です。1つのインデックスからのみ、すべてのブックマークを破棄し、データのみを残す準備ができています。 すべてのフィールドが含まれる別のインデックスがある場合、行のアドレスが含まれます。



2つ目の問題があります。 クラスタ化インデックスを使用すると、RIDを行アドレスとして使用できなくなります。 クラスター化インデックスのエントリは並べ替えられます（物理的に-ページ内、論理的に-ページ間に水平リンクがあります）。 レコードを追加したり、キーフィールドを変更すると、レコードは適切な場所に移動します-多くの場合、ページ内ですが、別のページに移動することもできます。 つまり、 クラスター化インデックスのRIDは、レコードを一意に識別しなくなります。 したがって、一意に識別する行のアドレスとして、クラスター化インデックスのキーが使用されます。



つまり、ツリーをたどって非クラスター化インデックスを検索すると、データアドレスではなく、クラスター化インデックスのキーが取得されます。 データ自体を取得するには、クラスター化インデックスツリーも調べる必要があります。



クラスター化されたインデックス上に構築された非クラスター化インデックスによって2万件のレコードの範囲をスキャンすることを想像してください。 ここで、既知のRIDに従ってページの2万回の論理読み取りを実行する必要はありませんが、クラスター化インデックスで2万回の検索を実行する必要があり、各検索には3回またはそれ以上の論理読み取りが必要です。



そして、クラスタ化インデックスのキーが一意でない場合はどうなりますか？ そして、これは起こりません。 サーバーにとって、それは必然的に一意です。 ユーザーが一意でないクラスター化インデックスを作成するように要求した場合、サーバーは各キーに4バイトの整数を割り当てます。これにより、キーの一意性が確保されます。 これはユーザーに対して透過的に行われます。サーバーは数字の正確な値をユーザーに通知するだけでなく、その存在の事実も伝えません。 レコードの明確な識別の可能性のために、キーの一意性が正確に必要です-そのため、クラスター化インデックスのキーは行のアドレスとして機能できます。

それで、するかしないか？

理論に基づいて、クラスター化インデックスを構築するための合理的な手順を説明できます。 テーブルが必要とするすべてのインデックスを書き出し、それらからクラスタリングの候補を選択する必要があります。

クラスター化インデックスを作成する必要はありません。 スキャンがインデックスキーによって想定されていない場合、これはクラスタリングの適切な候補ではありません（ 他のインデックスによるスキャンが想定されている場合、非常に悪い候補ですら）。 クラスタリングの候補を誤って選択すると、パフォーマンスが低下します。これは、他のすべてのインデックスがヒープで実行した場合よりもうまく機能しないためです。



次の選択アルゴリズムが提案されています。

1. 単一の値が検索されるすべてのインデックスを定義します。 そのようなインデックスが一意である場合、クラスタ化する必要があります。 複数の場合-次のステップに進みます。
2. 前の手順のインデックスに、範囲のスキャンに使用されるすべてのインデックスを追加します。 存在しない場合、クラスター化インデックスは不要であり、ヒープ上のいくつかのインデックスはより適切に機能します。 存在する場合は、それぞれをカバーして、このインデックスでスキャンクエリに必要なすべての列を追加する必要があります。 そのようなインデックスが一意である場合、クラスタ化する必要があります。 複数ある場合は、次の手順に進みます。
3. すべてのカバリングインデックスの中で、クラスタリングに最適な選択肢は間違いありません。 これらのインデックスの1つは、以下を考慮してクラスター化する必要があります。
   
   
   • キーの長さ クラスター化インデックスキーは行参照であり、非クラスター化インデックスのリーフレベルに格納されます。 キーの長さが短いほど、ストレージスペースが少なくなり、生産性が向上します。
   • カバレッジの程度。 クラスター化インデックスにはすべてのフィールドが「無料で」含まれており、最大のフィールドセットを持つカバリングインデックスがクラスター化に適しています。
   • 使用頻度。 スパニングインデックスで単一の値を見つけることは可能な限り高速な検索であり、クラスタ化インデックスはあらゆるクエリにまたがっています。

追記。 なぜ彼だけがいるのですか？

この記事を書き始めたとき、テーブルに複数のクラスター化インデックスを含めることができない理由を完全に理解しました。 執筆の途中で、私はこれを理解することをやめ、今は理解していません（それはばかげていますが、それでも説明できます）。 今、私には仮説しかありません。



クラスタ化インデックスには、最初にリーフ頂点のすべてのデータが含まれ、2番目にテーブルデータへの参照が含まれません（外部にテーブルがないため）。 さて、すべてのフィールドを含み、リンクを含まない、いくつかのインデックスをそのように配置することを妨げるのは何ですか？ 知りません 私だけが提供できます。



まず、すべてのフィールドが含まれるインデックスをいくつでも作成できます。 これは、いくつかのクラスター化インデックスが私たちに約束するゲイン全体が比較的小さいことを意味します。追加のインデックスのリーフレベルでは、データへのリンクはありません。つまり、スペースを少し節約します。 また、いくつかのクラスター化インデックスの作成にはどのような問題が伴いますか？

1. クラスター化インデックスキーは、非クラスター化インデックスのリーフに格納されているデータへのリンクです。 複数のクラスター化インデックスが存在する可能性がある場合でも、キーがデータ識別子である「メイン」インデックスを選択する必要があります。
2. 非キー列をクラスター化インデックスに追加する必要がある場合、インデックスを完全に再構築する必要があり、その上の非クラスター化インデックスをまったく変更する必要はありません。 複数のクラスター化インデックスが存在する場合、すべてを再構築する必要があり、その所要時間を事前に判断することは不可能です。
3. エラーに満ちた多くの状況があります。 たとえば、複数のクラスター化インデックスが存在する場合、ユーザーがマスターインデックス（非クラスター化インデックスのデータへのリンクとして機能するキーを持つインデックス）を削除すると、サーバーは新しいマスターインデックスを自動的に選択する必要があります。

ここで、複数のクラスター化インデックスの禁止は、この概念の実装にはコストがかかり、エラー（つまり、信頼性の低下）が伴うという事実に関連しており、利益は比較的少ないという考えに傾いています。 つまり、いくつかのクラスター化インデックスを作成することは技術的には可能ですが、費用がかかり、不便で無駄です。

複数のクラスター化インデックスを作成することを不可能にする考慮事項が表示されない可能性があります。 誰かがこれらの考慮事項を指摘してくれたら本当に感謝しています。



インデックスをクラスタリングしてください。