SQLインデックスの説明、Pt。 2

公開: 2022-03-11

SQLインデックスの説明の最初のレッスンでは、並べ替えを使用してデータの取得を高速化する方法を学びました。 行が並べ替えられた後のクエリの実行は高速ですが、並べ替えには、すべての行を少なくとも1回読み取り、それらを移動することが含まれます。 そのため、テーブル全体を順番に読み取るよりも、メソッドの速度が低下し、効率が低下します。

論理的な結論は、特定のテーブルのソートされたコピー（正式にはSQLインデックスと呼ばれ、プレフィックスはIX_ ）を維持する必要があるということのようです。 その場合、最初の記事の検索アルゴリズムが適用可能になり、開始する前にテーブルを並べ替える必要がなくなります。

テーブルのソートされたコピーとしてのインデックス

もう一度Googleスプレッドシートを使用して、そのアイデアの文字通りの実装を見てみましょう。 予約スプレッドシートは、同じデータを含む5枚のシートのコレクションになります。 各シートは、さまざまな列のセットに従って並べ替えられます。

ここでの演習は、以前のSQLインデックスチュートリアルの記事よりも厳密さを低くすることを目的としています。タイマーや行数よりも感覚で行うことができます。 いくつかの演習は非常に似ているように見えますが、今回は次のことを検討しています。

  1. ソートされたプライマリテーブルではなく、個別のインデックスを使用する場合にデータをより効率的に取得する方法
  2. データを変更するときに各インデックスとテーブルの順序を維持する方法

前のチュートリアルは読み取りに焦点を当てていましたが、多くの一般的な実際のデータダイナミクス（ホテルの予約を含む）では、新しいデータの挿入と既存のデータの更新の両方で、書き込みパフォーマンスに対するインデックスの影響を考慮する必要があります。

予備演習：予約をキャンセルする

並べ替えられたテーブル戦略を使用してSQLインデックスのパフォーマンスを把握するには、2020年8月22日からホテル4でクライアント12の予約を削除する必要があります。テーブルを作成し、正しい並べ替えを維持します。

終わり？ テーブルの複数のソートされたコピーを保持するという考えは、見た目ほど良くないことは明らかです。 それでも疑問がある場合は、削除した予約を再挿入するか、既存の予約の日付を変更することもできます。

テーブルのソートされたコピーはより高速な検索を可能にしますが、今学んだように、データの変更は悪夢です。 既存の行を追加、削除、または更新する必要がある場合は常に、テーブルのすべてのコピーを取得し、行や追加または移動する場所を見つけて、最後にデータのブロックを移動する必要があります。

行アドレスを使用したSQLインデックス

このスプレッドシートには、異なるアプローチを使用するインデックスが含まれています。 インデックス行は引き続き特定の基準に従って並べ替えられますが、他のすべての情報をインデックス行に保持するわけではありません。 代わりに、「行アドレス」、つまり予約シートの行のアドレス（テーブル自体を表す）を列Hに保持します。

すべてのRDBMS実装は、オペレーティングシステムレベルの機能を使用して、物理アドレスを使用してディスク上のブロックをすばやく見つけます。 行アドレスは通常、ブロックアドレスとブロック内の行の位置で構成されます。

このインデックスデザインがどのように機能するかを学ぶために、いくつかの演習を行いましょう。

演習1：すべてのクライアントの予約

最初の記事と同様に、次のSQLクエリの実行をシミュレートします。

 SELECT * FROM Reservations WHERE ClientID = 12;

繰り返しますが、2つの合理的なアプローチがあります。 1つ目は、Reservationsテーブルからすべての行を読み取り、条件に一致する行のみをフェッチすることです。

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

2番目のアプローチでは、IX_ClientIDシートからデータを読み取り、条件に一致するアイテムについて、rowAddress値に基づいて予約テーブルの行を検索します。

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

ここで、 Get first row fromという式は、前の記事で見たものと同様のループによって実装されています。

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

行が見つかるまで下にスライドするか、rowAddress列でフィルターを使用することにより、特定のrowAddressを持つ行を見つけることができます。

返される予約がほんの一握りである場合は、インデックスを使用するアプローチの方が適しています。 ただし、返される行が数百、場合によっては数十である場合は、Reservationsテーブルを直接使用するだけの方が高速になる可能性があります。

読み取りの量は、ClientIDの値によって異なります。 最大値の場合はインデックス全体を読み取る必要があり、最小値の場合はインデックスの先頭にあります。 平均値は行数の半分です。

後でその部分に戻り、効率的なソリューションを紹介します。 今のところ、基準に一致する最初の行を見つけたら、その部分に焦点を当てましょう。

演習2：特定の日付から始まる予約の数

タスクは、新しいインデックスデザインを使用して、2020年8月16日のチェックイン数をカウントすることです。

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

カウントに適切なインデックスを使用するアプローチは、関係する行数に関係なく、テーブルスキャンよりも優れています。 その理由は、Reservationsテーブルにアクセスする必要がまったくないためです。必要なすべての情報がインデックス自体にあります。

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

アルゴリズムは基本的に、ソートされたテーブルを使用するものと同じです。 ただし、インデックス行はテーブル行よりもはるかに短いため、RDBMSがディスクから読み取る必要のあるデータブロックは少なくなります。

演習3：犯罪捜査（ホテルと日付範囲を指定したゲストリスト）

2020年8月13日と14日にホテル3に到着したゲストのリストを作成しましょう。

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

予約テーブルからすべての行を読み取るか、使用可能なインデックスの1つを使用できます。 特定の基準に従ってソートされたテーブルを使用して同じ演習を行った後、インデックスIX_HotelID_DateFromが最も効率的であることがわかりました。

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

さらに効率的なインデックスを設計できますか？

報告するゲストのリストに必要な唯一の情報であるClientID値のために、テーブルにアクセスします。 その値をSQLインデックスに含めると、テーブルにアクセスする必要がまったくなくなります。 そのようなインデックス、 IX_HotelID_DateFrom_ClientIDからのみ読み取るリストを作成してみてください。

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

インデックスにクエリの実行に必要なすべての情報が含まれている場合、インデックスはクエリをカバーしていると言います。

演習4：IDの代わりにゲストの名前のリスト

ゲストIDのリストは、犯罪を調査している警察官には役に立ちません。 名前を指定する必要があります。

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

リストを提供するには、 Reservationsテーブルのデータに加えて、このGoogleシートにあるゲスト情報を含むClientsテーブルも必要です。

この演習は前の演習と同様であり、アプローチも同様です。

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

式Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientIDは、テーブルスキャンまたはインデックスを使用して実装できます。 テーブルスキャンを使用する場合、 WhileループのClientIDごとに、平均してClientsテーブルの行の半分を読み取る必要があります。

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

これまで検討してきたインデックスの実装（「フラット」インデックスの実装と呼びましょう）は、あまり役に立ちません。 インデックスから同じ数の行（小さい行ですが）を読み取ってから、 RowAddressを使用してClientsの行にジャンプする必要があります。

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

注：ここで、 PKは「主キー」を指します。これは、シリーズの後半で説明する用語です。

それほど多くの行を読まなくてもこれを達成する方法はありますか？ はい—これはまさにBツリーインデックスの目的です。

バランスツリー（Bツリー）インデックス

Clients_PK_Flatの行を4行のブロックに分割し、ブロックの最後のClientIDの値とブロックの開始アドレス（列IndexRowAddress ）を含むリストを作成しましょう。 結果のデータベースインデックスデータ構造—Clients_PK_2Levelsシートにあります。 新しい構造が、 ClientIDが28のクライアントを見つけるのにどのように役立つかを試してください。アルゴリズムは次のようになります。

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

あなたはおそらく、私たちが別のレベルを追加できることを理解したでしょう。 レベル1は、IX_Clients_PKタブに表示されているように、4つの行で構成されています。 ClientIDが28のゲストの名前を見つけるには、主キー構造から3つのブロック（ノード）のデータ（レベルごとに1つ）を読み取り、最後にアドレス42のClients行にジャンプする必要があります。

このSQLインデックスの構造は、バランスツリーと呼ばれます。 ルートノードから各リーフレベルノードへのパスが同じ長さ、いわゆるBツリーの深さを持つ場合、ツリーはバランスが取れています。 私たちの場合、深さは3です。

スプレッドシートの[IX_Clients_PK]タブに基づくBツリーの例で、上記のアルゴリズムのルックアップパスを示しています。

今後、スプレッドシートにはリーフレベルのエントリしか含まれていませんが、各インデックスはBツリー構造であると見なします。 Bツリーについて知っておくべき最も重要な事実は次のとおりです。

  • Bツリーインデックス構造は、市場に出回っているすべての主要なRDBMSで最も一般的に使用されているインデックスです。
  • バランスの取れたツリーのすべてのレベルは、キー列の値順に並べられています。
  • データはディスクからブロック単位で読み取られます。
  • 1つのBツリーノードには1つ以上のブロックが含まれます。
  • クエリのパフォーマンスに影響を与える最も重要な要素は、ディスクから読み取られるブロックの数です。
  • ルートから始まりリーフレベルで終わる各新しいBツリーレベルのアイテム数は、指数関数的に増加します。

演習5：犯罪捜査、パートII

現在、警察の検査官は、A市のすべてのホテルから、対応するゲストの名前、到着日、ホテル名のリストを探しています。

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

アプローチ1

インデックスIX_DateFrom_HotelID_ClientIDを使用する場合、日付範囲の各行について、Hotelsテーブルにアクセスし、ホテルが都市Aからのものであるかどうかを確認する必要があります。そうである場合は、Clientsテーブルにもアクセスする必要があります。クライアントの名前を読みます。

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

アプローチ2

IX_HotelID_DateFrom_ClientIDを使用すると、より効率的な実行プランが得られます。

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Hotelsテーブルから、都市Aのすべてのホテルを検索します。これらのホテルのIDがわかれば、 IX_HotelID_DateFrom_ClientIDインデックスから後続のアイテムを読み取ることができます。 このように、各ホテルと日付のBツリーリーフレベルの最初の行を見つけた後、A市外のホテルからの予約を読み取ることはありません。

短いHotelsテーブルをIX_HotelID_DateFrom_ClientIDインデックスと組み合わせて活用します。表は左側に表示され、A市にあるホテルに対応する2つのホテルの行が強調表示されています。次に、これらの各ホテルはBツリープロセスを介してクイックルックアップされ、インデックス内のブロックを直接指します。右側には、求められているすべてのデータが連続しています。

ここで、目標に適したデータベースインデックスがある場合、追加の結合によって実際にクエリが高速化されることがわかります。

Bツリー構造と、行が挿入、更新、または削除されるたびに更新される方法については、パーティション化の動機とその影響について説明するときに詳しく説明します。 重要なのは、インデックスを使用するときはいつでも、この操作をすばやく検討できるということです。

SQLのインデックスクエリ：詳細がすべての違いを生む

インデックスとデータベースに関しては、SQL言語レベルで作業すると、実装の詳細がある程度隠されます。 これらの演習は、さまざまなSQLインデックスを使用するときに実行プランがどのように機能するかを理解するのに役立つことを目的としています。 記事を読んだ後、クエリを可能な限り高速かつ効率的にするために利用可能なインデックスとデザインインデックスが与えられた場合の最良の実行プランを推測できることを願っています。

このシリーズの次のパートでは、新しく習得したスキルを使用および拡張して、SQLでのインデックスの使用における最も一般的なベストプラクティスとアンチパターンを調査および理解します。 次のパートで取り上げたいグッドプラクティスとベストプラクティスのリストがありますが、次の記事をあなたのニーズと経験により関連性のあるものにするために、回答を希望する独自の質問を投稿してください。

SQLインデックスの説明の最後の部分では、テーブルとインデックスのパーティション分割、それを使用するための正しい動機と間違った動機、およびクエリのパフォーマンスとデータベースの保守への影響についても学習します。