MySQL: データ構造とアルゴリズムの原則

[[190898]]

この記事では、MySQL データベースを研究対象として取り上げ、データベース インデックスに関連するいくつかのトピックについて説明します。 MySQL は多くのストレージ エンジンをサポートしており、さまざまなストレージ エンジンがインデックスに対して異なるサポートを提供していることに特に注意することが重要です。そのため、MySQL データベースは、BTree インデックス、ハッシュ インデックス、フルテキスト インデックスなど、複数のインデックス タイプをサポートしています。混乱を避けるため、この記事では BTree インデックスのみに焦点を当てます。これは、MySQL を使用するときに扱う主なインデックスだからです。ハッシュ インデックスとフルテキスト インデックスについては、この記事では説明しません。

記事の主な内容は3つの部分に分かれています。

最初の部分では、主にデータ構造とアルゴリズム理論の観点から、MySQL データベース インデックスの数学的基礎について説明します。

パート 2 では、クラスター化インデックス、非クラスター化インデックス、カバーリング インデックスなどのトピックと、MySQL データベースの MyISAM および InnoDB データ ストレージ エンジンのインデックス アーキテクチャ実装の組み合わせについて説明します。

パート 3 では、上記の理論的基礎に基づいて、MySQL でインデックスを高パフォーマンスで使用する戦略について説明します。

データ構造とアルゴリズムの基礎

インデックスの性質

MySQL のインデックスの公式定義は次のとおりです: インデックスは、MySQL がデータを効率的に取得するのに役立つデータ構造です。文の主幹を抽出することで、インデックスの本質、つまりインデックスがデータ構造であることがわかります。

データベースクエリはデータベースの最も重要な機能の 1 つであることは周知の事実です。私たちは皆、できるだけ早くデータをクエリすることを望んでいるので、データベース システムの設計者はクエリ アルゴリズムの観点からそれを最適化します。最も基本的なクエリ アルゴリズムは、もちろんシーケンシャル検索 (線形検索) です。複雑度が O(n) のこのアルゴリズムは、データ量が多い場合には明らかに不向きです。幸いなことに、コンピューター サイエンスの発展により、バイナリ検索 (二分探索)、バイナリ ツリー検索 (二分木探索) など、より優れた検索アルゴリズムが数多く提供されています。少し分析してみると、それぞれの検索アルゴリズムは特定のデータ構造にしか適用できないことがわかります。たとえば、バイナリ検索では、取得したデータが順序どおりになっていることが必要で、バイナリツリー検索はバイナリ検索ツリーにしか適用できません。ただし、データ自体の編成構造は、さまざまなデータ構造を完全に満たすことはできません (たとえば、2 つの列を同時に順序どおりに編成することは理論上不可能です)。そのため、データベース システムは、データに加えて、特定の検索アルゴリズムを満たすデータ構造も保持しています。これらのデータ構造は、何らかの方法でデータを参照 (ポイント) するため、これらのデータ構造に対して高度な検索アルゴリズムを実装できます。このデータ構造はインデックスです。

例を見てみましょう:

図1

図 1 は、可能なインデックス作成アプローチを示しています。左側は 2 つの列と 7 つのレコードを持つデータ テーブルです。左端はデータ レコードの物理アドレスです (論理的に隣接するレコードが必ずしもディスク上で物理的に隣接するとは限らないことに注意してください)。 Col2 の検索を高速化するために、右に示すようにバイナリ検索ツリーを維持できます。各ノードには、インデックス キー値と、対応するデータ レコードの物理アドレスへのポインターが含まれています。このようにして、バイナリ検索を使用して、O(log2n) の複雑さ内で対応するデータを取得できます。

これは本物のインデックスですが、実際のデータベース システムでは、後述する理由により、バイナリ検索ツリーやその進化形である赤黒ツリーが使用されることはほとんどありません。

B ツリーと B+ ツリー

現在、ほとんどのデータベース システムとファイル システムでは、インデックス構造として B-Tree またはその派生形である B+Tree を使用しています。この記事の次のセクションでは、メモリの原理とコンピュータ アクセスの原理を組み合わせて、B-Tree と B+Tree がインデックス作成に広く使用されている理由について説明します。このセクションでは、まずデータ構造の観点からのみ説明します。

Bツリー

B-Tree を説明するには、まずデータ レコードをタプル [key, data] として定義します。ここで、key はレコードのキー値です。データ レコードが異なれば、キーも異なります。データは、キーを除いたデータ レコードのデータです。 B-Tree は次の条件を満たすデータ構造です。

1. d は 1 より大きい正の整数で、B ツリーの次数と呼ばれます。

2. h は正の整数で、B ツリーの高さと呼ばれます。

3. 各非リーフノードは n-1 個のキーと n 個のポインターで構成されます (d<=n<=2d)。

4. 各リーフ ノードには、少なくとも 1 つのキーと 2 つのポインターが含まれ、最大で 2d-1 個のキーと 2d ポインターが含まれます。リーフ ノードのポインターはすべて null です。

5. すべてのリーフノードの深さは同じで、ツリーの高さ h に等しくなります。

6. キーとポインタは分離されており、ノードの両端にポインタが存在します。

7. ノード内のキーは、左から右へ非減少順に並べられます。

8. すべてのノードはツリー構造を形成します。

9. 各ポインタは null であるか、別のノードを指しています。

10. ポインタがノード node の左端にあり、null でない場合、それが指すノードのすべてのキーは v(key1) より小さくなります。ここで、v(key1) はノードの最初のキーの値です。

11. ポインタがノード node の右端にあり、null でない場合、それが指すノードのすべてのキーは v(keym) よりも大きくなります。ここで、v(keym) はノードの最後のキーの値です。

12. ノードへのポインタの左隣のキーと右隣のキーがそれぞれkeyiとkeyi+1であり、それらがnullでない場合、それが指すノードのすべてのキーはv(keyi+1)より小さく、v(keyi)より大きくなります。

図 2 は、d = 2 の B ツリーの概略図です。

図2

B ツリーの特性により、B ツリーでキーによってデータを取得するアルゴリズムは非常に直感的です。まず、ルート ノードからバイナリ検索を実行します。キーが見つかった場合は、対応するノードのデータが返されます。それ以外の場合は、対応する間隔のポインターが指すノードが、ノードが見つかるか、ヌル ポインターが見つかるまで再帰的に検索されます。前者は成功した検索であり、後者は失敗した検索です。 B-Tree 上の検索アルゴリズムの疑似コードは次のとおりです。

 BTree_Search(ノード、キー)
 {
 if(node ​​== null ) はnullを返します。
 foreach(ノード.キー)
 {
 if( node.key [i] == key ) はnode.data[i]を返します。
 if( node.key [i] > key ) return BTree_Search(point[i]->node);
 }
 BTree_Search(point[i+1]->node)を返します。
 }
データ = BTree_Search(ルート、my_key);

B ツリーには一連の興味深い特性があります。たとえば、次数 d の B ツリーが N 個のキーをインデックスする場合、そのツリーの高さ h の上限は logd((N+1)/2) です。キーのノード数を検索する漸近的な複雑さは O(logdN) です。この点から、B-Tree は非常に効率的なインデックス データ構造であることがわかります。

さらに、新しいデータ レコードを挿入したり削除したりすると、B ツリーの特性が破壊されるため、挿入や削除時に B ツリーの特性を維持するために、ツリーを分割、結合、転送するなどの操作を行う必要があります。この記事では、B ツリーのこれらの内容について完全に説明するつもりはありません。B ツリーの数学的特性や挿入および削除アルゴリズムを詳細に説明した資料がすでにたくさんあるためです。興味のある方は、この記事の最後にある参考資料を読んでください。

B+ツリー

B ツリーには多くのバリエーションがありますが、最も一般的なのは B+ ツリーです。たとえば、MySQL では通常、インデックス構造を実装するために B+ ツリーを使用します。

B-Tree と比較すると、B+Tree には次の違いがあります。

1. 各ノードのポインタの上限は 2d+1 ではなく 2d です。

2. 内部ノードはデータを保存せず、キーのみを保存します。リーフノードはポインタを保存しません。

図 3 は単純な B+ツリー図です。

図3

すべてのノードが同じドメインを持つわけではないため、B+ ツリーのリーフ ノードと内部ノードは通常、サイズが異なります。これは B-Tree とは異なります。B-Tree では、異なるノードに格納されるキーとポインターの数が一致しない場合があります。ただし、各ノードのドメインと上限は一致しているため、実装では B-Tree が各ノードに同じ量のスペースを適用することがよくあります。

一般的に言えば、B+Tree は B-Tree よりも外部ストレージ インデックス構造の実装に適しています。具体的な理由は、外部ストレージとコンピュータ アクセスの原理に関連しており、これについては後述します。

シーケンシャル アクセス ポインターを使用した B+ ツリー

データベース システムやファイル システムで一般的に使用される B+Tree 構造は、従来の B+Tree に基づいて最適化され、順次アクセス ポインターが追加されています。

図4

図 4 に示すように、B+ ツリーの各リーフ ノードに隣接するリーフ ノードへのポインタを追加することで、順次アクセス ポインタを持つ B+ ツリーが形成されます。この最適化の目的は、区間アクセスのパフォーマンスを向上させることです。たとえば、図 4 では、キーが 18 から 49 までのすべてのデータ レコードをクエリする場合、18 を見つけた後は、ノードとポインターをトラバースするだけで、すべてのデータ ノードに一度にアクセスできるため、区間クエリの効率が大幅に向上します。

このセクションでは、B ツリーと B+ ツリーについて簡単に説明します。次のセクションでは、メモリ アクセスの原則を組み合わせて、データベース システムでインデックスを実装するためのデータ構造として現在 B+ ツリーが推奨されている理由を説明します。

B-Tree (B+Tree) を使用する理由

前述のように、赤黒木などのデータ構造を使用してインデックスを実装することもできますが、ファイル システムとデータベース システムでは、インデックス構造として B-/+ ツリーが一般的に使用されます。このセクションでは、インデックスとしての B-/+ ツリーの理論的根拠を、コンピュータ構成の原則に関する関連知識と組み合わせて説明します。

一般的に、インデックス自体も非常に大きく、すべてをメモリに格納することは不可能であるため、インデックスはインデックス ファイルの形式でディスク上に保存されることがよくあります。この場合、インデックス検索処理中にディスク I/O 消費が発生します。メモリ アクセスと比較すると、I/O アクセスの消費量は数桁大きくなります。したがって、インデックスとしてのデータ構造の品質を評価するための最も重要な指標は、検索処理中のディスク I/O 操作数の漸近的複雑さです。つまり、検索プロセス中のディスク I/O アクセスの数を最小限に抑えるようにインデックスの構造を構成する必要があります。以下では、まずメモリとディスク アクセスの原理を紹介し、次にこれらの原理を組み合わせてインデックスとしての B-/+ ツリーの効率を分析します。

メインメモリアクセスの原理

現在、コンピューターで使用されているメインメモリは、基本的にランダム読み取り書き込みメモリ (RAM) です。現代の RAM の構造とアクセス原理は比較的複雑です。ここでは、この記事では具体的な違いを無視し、非常に単純なアクセス モデルを抽象化して、RAM の動作原理を説明します。

図5

抽象的な観点から見ると、メイン メモリは、それぞれが固定サイズのデータ​​を格納する一連のストレージ ユニットで構成されるマトリックスです。各ストレージ ユニットには固有のアドレスがあります。現代のメイン メモリのアドレス指定ルールは比較的複雑です。ここでは、これを 2 次元アドレスに簡略化します。つまり、ストレージ ユニットは、行アドレスと列アドレスを通じて一意に特定できます。図 5 は 4 x 4 メイン メモリ モデルを示しています。

メインメモリのアクセスプロセスは次のとおりです。

システムがメイン メモリを読み取る必要がある場合、アドレス信号がアドレス バスに配置され、メイン メモリにアップロードされます。メイン メモリは、アドレス信号を読み取った後、信号を解析して指定されたストレージ ユニットを見つけ、このストレージ ユニットのデータをデータ バスに配置して、他のコンポーネントが読み取れるようにします。

メイン メモリへの書き込みプロセスも同様です。システムは、ユニット アドレスと書き込むデータをそれぞれアドレス バスとデータ バスに配置します。メイン メモリは 2 つのバスの内容を読み取り、対応する書き込み操作を実行します。

ここで、メイン メモリへのアクセス時間はアクセス回数にのみ比例関係にあることがわかります。これは、機械的な操作がなく、2 回アクセスするデータ間の「距離」が時間に影響を与えないためです。たとえば、最初に A0 にアクセスしてから A1 にアクセスした場合の所要時間は、最初に A0 にアクセスしてから D3 にアクセスした場合の所要時間と同じです。

ディスクアクセスの原理

前述のように、インデックスは通常、ファイルの形式でディスクに保存され、インデックスの取得にはディスク I/O 操作が必要になります。メインメモリとは異なり、ディスク I/O には機械的な動きが伴うため、ディスク I/O にかかる時間は膨大になります。

図６はディスクの全体構造を示す概略図である。

図6

ディスクは同じサイズで同軸の円形プラッタで構成されており、ディスクは回転できます (個々のディスクは同期して回転する必要があります)。ディスクの片側にはヘッド ブラケットがあり、ヘッドのグループを固定します。各ヘッドはディスクの内容にアクセスする役割を担います。磁気ヘッドは回転できませんが、ディスクの半径に沿って移動できます (実際には接線方向の移動)。各磁気ヘッドは同時に同軸である必要があります。つまり、真上から見下ろすと、すべての磁気ヘッドが常に重なり合っています (ただし、現在ではこの制限を受けないマルチヘッド独立技術があります)。

図７はディスク構造の概略図である。

図7

ディスクは一連の同心円に分割され、円の中心がディスクの中心になります。各同心円はトラックと呼ばれ、同じ半径のすべてのトラックが円筒を形成します。トラックは放射状の線に沿って小さなセグメントに分割されます。各セグメントはセクターと呼ばれます。各セクターはディスクの最小のストレージ単位です。簡単にするために、ディスクにはプラッタとヘッドが 1 つずつあると仮定します。

ディスクからデータを読み取る必要がある場合、システムはデータの論理アドレスをディスクに送信します。ディスクの制御回路は、アドレス指定ロジックに従って論理アドレスを物理アドレスに変換し、読み取るデータがどのトラックとセクターにあるかを判断します。このセクターのデータを読み取るには、ヘッドをこのセクターの上に配置する必要があります。これを実現するには、ヘッドを移動して対応するトラックに合わせる必要があります。このプロセスはシークと呼ばれ、かかる時間はシーク時間と呼ばれます。次に、ディスクが回転して、ヘッドの下のターゲットセクターを回転させます。このプロセスにかかる時間は回転時間と呼ばれます。

局所性原理とディスクの事前読み取り

ストレージメディアの特性上、ディスクアクセス自体はメインメモリよりはるかに遅くなります。機械的な動作消費に加え、ディスクアクセス速度はメインメモリの数百分の一になることがよくあります。したがって、効率を向上させるには、ディスクI/Oを最小限に抑える必要があります。この目標を達成するために、ディスクは厳密にオンデマンドで読み取られるのではなく、毎回事前に読み取られることがよくあります。必要なのが 1 バイトだけの場合でも、ディスクはこの位置から開始し、一定の長さのデータを順番に逆方向にメモリに読み込みます。この理論的根拠は、コンピュータ サイエンスにおける有名な局所性原理です。

あるデータが使用されると、通常は近くのデータもすぐに使用されます。

プログラム実行中に必要なデータは通常集中しています。

ディスクの順次読み取りは非常に効率的であるため (シーク時間は必要なく、回転時間もわずかしか必要ありません)、事前読み取りによって局所性を持つプログラムの I/O 効率を向上させることができます。

事前読み取りの長さは、通常、ページの整数倍になります。ページは、コンピュータ管理メモリの論理ブロックです。ハードウェアとオペレーティング システムは、多くの場合、メイン メモリとディスク ストレージ領域を同じサイズの連続ブロックに分割します。各ストレージ ブロックはページと呼ばれます (多くのオペレーティング システムでは、ページ サイズは通常 4k です)。メイン メモリとディスクは、ページ単位でデータを交換します。プログラムが読み取ろうとするデータがメインメモリにない場合、ページフォールト例外が発生します。このとき、システムはディスクに読み取り信号を送信します。ディスクはデータの開始位置を見つけ、1つまたは複数のページを連続的に読み取り、メモリにロードします。その後、例外が返され、プログラムは引き続き実行されます。

B-/+ツリーインデックスのパフォーマンス分析

これで、ようやく B-/+ ツリー インデックスのパフォーマンスを分析できるようになりました。

前述のように、インデックス構造の品質を評価するには、通常、ディスク I/O の数が使用されます。まず、B ツリー分析から始めましょう。B ツリーの定義によれば、検索には最大 h 個のノードにアクセスする必要があります。データベース システムの設計者は、ディスクの事前読み取り原理を巧みに利用して、ノードのサイズをページと同じサイズに設定し、各ノードを 1 回の I/O だけで完全にロードできるようにしました。この目標を達成するためには、B-Tree の実際の実装で次の技術が必要です。

新しいノードが作成されるたびに、ページのスペースが直接要求されます。これにより、ノードが物理的にページに格納されることが保証されます。さらに、コンピューターのストレージ割り当てはページ単位で行われるため、ノードに必要な I/O は 1 つだけです。

B ツリーでの検索には最大で h-1 回の I/O が必要であり (ルート ノードは常にメモリ内に存在します)、漸近的な複雑度は O(h)=O(logdN) です。一般的な実際のアプリケーションでは、出次数 d は非常に大きな数値であり、通常は 100 を超えるため、h は非常に小さくなります (通常は 3 以下)。

まとめると、インデックス構造として B-Tree を使用することは非常に効率的です。

赤黒木構造の場合、h は明らかにはるかに深くなります。論理的に近いノード (親と子) は物理的に離れている場合があり、局所性を活用できないため、赤黒木の漸近的 I/O 複雑度も O(h) となり、その効率は明らかに B ツリーよりもはるかに悪くなります。

前述のように、B+Tree は外部メモリのインデックス作成に適していますが、その理由は内部ノードの出次数 d に関係しています。上記の分析から、d が大きいほどインデックスのパフォーマンスが向上し、出力次数の上限はノード内のキーとデータのサイズに依存することがわかります。

dmax = floor(ページサイズ / (キーサイズ + データサイズ + ポイントサイズ)) (ページサイズ – dmax >= ポイントサイズ)

または

dmax = floor(ページサイズ / (キーサイズ + データサイズ + ポイントサイズ)) – 1 (ページサイズ – dmax < ポイントサイズ)

切り捨てとは切り捨てを意味します。データ フィールドは B+ ツリーのノードから削除されるため、出力次数が大きくなり、パフォーマンスが向上します。

この章では、理論的な観点から、インデックスに関連するデータ構造とアルゴリズムの問​​題について論じます。次の章では、MySQL で B+Tree がインデックスとしてどのように実装されるかについて説明します。同時に、MyISAM と InnDB ストレージ エンジンを組み合わせて、非クラスター化インデックスとクラスター化インデックスという 2 つの異なるインデックス実装形式を紹介します。

MySQL インデックスの実装

MySQL では、インデックスはストレージ エンジン レベルの概念です。ストレージ エンジンによって、インデックスの実装方法は異なります。この記事では、主に MyISAM および InnoDB ストレージ エンジンのインデックス実装方法について説明します。

MyISAM インデックスの実装

MyISAM エンジンはインデックス構造として B+Tree を使用し、リーフ ノードのデータ フィールドにデータ レコードのアドレスを格納します。次の図は、MyISAM インデックスの概略図です。

図8

ここでは、テーブルに合計 3 つの列があると仮定します。Col1 が主キーであると仮定すると、図 8 は MyISAM テーブルのプライマリ インデックス (主キー) の図になります。 MyISAM インデックス ファイルには、データ レコードのアドレスのみが保存されていることがわかります。 MyISAM では、プライマリ インデックスとセカンダリ インデックス (セカンダリ キー) の間に構造上の違いはありませんが、プライマリ インデックスではキーが一意である必要があるのに対し、セカンダリ インデックス キーは繰り返すことができます。 Col2 にセカンダリ インデックスを作成すると、このインデックスの構造は次のようになります。

図9

これも B+ ツリーであり、データ フィールドにはデータ レコードのアドレスが格納されます。したがって、MyISAM のインデックス検索アルゴリズムは、まず B+Tree 検索アルゴリズムに従ってインデックスを検索します。指定されたキーが存在する場合は、そのデータ フィールドの値が取り出され、次にデータ フィールドの値をアドレスとして使用して対応するデータ レコードが読み取られます。

MyISAM インデックス方式は「非クラスター化」とも呼ばれ、InnoDB のクラスター化インデックスと区別するためにこのように呼ばれています。

InnoDB インデックスの実装

InnoDB もインデックス構造として B+Tree を使用しますが、その具体的な実装は MyISAM とはまったく異なります。

最初の大きな違いは、InnoDB のデータ ファイル自体がインデックス ファイルであることです。上記から、MyISAM インデックス ファイルとデータ ファイルは別々であり、インデックス ファイルにはデータ レコードのアドレスのみが保存されることがわかります。 InnoDB では、テーブル データ ファイル自体が B+ ツリーとして編成されたインデックス構造であり、このツリーのリーフ ノード データ フィールドに完全なデータ レコードが格納されます。このインデックスのキーはデータ テーブルの主キーであるため、InnoDB テーブル データ ファイル自体が主インデックスになります。

図10

図 10 は、InnoDB プライマリ インデックス (データ ファイルでもある) の概略図です。リーフ ノードには完全なデータ レコードが含まれていることがわかります。このタイプのインデックスはクラスター化インデックスと呼ばれます。 InnoDB のデータ ファイル自体は主キーによってクラスター化されているため、InnoDB ではテーブルに主キーが必要です (MyISAM には主キーがない場合があります)。明示的に指定されていない場合、MySQL システムはデータ レコードを一意に識別できる列を主キーとして自動的に選択します。そのような列が存在しない場合、MySQL は InnoDB テーブルの暗黙的なフィールドを主キーとして自動的に生成します。このフィールドは 6 バイト長で、長整数型です。

MyISAM インデックスとの 2 番目の違いは、InnoDB 補助インデックス データ フィールドに、アドレスではなく、対応するレコードの主キーの値が格納されることです。つまり、InnoDB のすべてのセカンダリ インデックスは、データ フィールドとしてプライマリ キーを参照します。たとえば、図 11 は Col3 に定義された補助インデックスを示しています。

図11

ここでは、英語文字の ASCII コードを比較基準として使用します。クラスター化インデックスの実装により、主キーによる検索は非常に効率的になりますが、補助インデックス検索には 2 つのインデックス検索が必要です。最初に補助インデックスを検索して主キーを取得し、次に主キーを使用して主インデックスからレコードを取得します。

さまざまなストレージ エンジンのインデックス実装方法を理解することは、インデックスを正しく使用して最適化するのに非常に役立ちます。たとえば、InnoDB のインデックス実装を理解すれば、長すぎるフィールドを主キーとして使用することが推奨されない理由を簡単に理解できます。これは、すべてのセカンダリ インデックスがプライマリ インデックスを参照し、プライマリ インデックスが長すぎるとセカンダリ インデックスが大きくなりすぎるためです。別の例として、InnoDB データ ファイル自体が B+Tree であるため、InnoDB の主キーとして非単調フィールドを使用することはお勧めできません。非単調な主キーでは、B+Tree の特性を維持するために、新しいレコードを挿入するときにデータ ファイルが頻繁に分割および調整されるため、非常に非効率的です。自動増分フィールドを主キーとして使用するのは良い選択です。

次の章では、これらのインデックス関連の最適化戦略について詳しく説明します。

インデックスの使用戦略と最適化

MySQL の最適化は、主にスキームの最適化とクエリの最適化に分けられます。この章で説明する高性能インデックス戦略は、主に構造最適化のカテゴリに分類されます。この章の内容は、すべて上記の理論的基礎に基づいています。実際、インデックスの背後にあるメカニズムを理解すれば、高パフォーマンス戦略を選択することは純粋な推論となり、これらの戦略の背後にあるロジックを理解できるようになります。

サンプルデータベース

インデックス戦略について説明するには、例として比較的大量のデータを持つデータベースが必要です。この記事では、MySQL の公式ドキュメントで提供されているサンプル データベースの 1 つである employees を使用します。このデータベースには、中程度のリレーショナル複雑性と大量のデータが含まれています。次の図はこのデータベースの ER 関係図です (MySQL 公式マニュアルより引用)。

図12

最左接頭辞原理と関連する最適化

インデックスを効率的に使用するための最初の条件は、どのようなクエリがインデックスを使用するかを知ることです。この問題は、B+ ツリーの「最左プレフィックス原則」に関連しています。次の例は、最左プレフィックス原則を示しています。

ここではまず、ジョイントインデックスの概念について説明します。上記では、インデックスが単一の列のみを参照することを前提としています。実際、MySQL のインデックスは、特定の順序で複数の列を参照できます。このようなインデックスは、ジョイント インデックスと呼ばれます。一般的に、ジョイント インデックスは、各要素がデータ テーブルの列である順序付きタプル <a1、a2、…、an> です。実際、インデックスを厳密に定義するにはリレーショナル代数が必要ですが、ここではリレーショナル代数についてあまり議論したくありません。それは非常に退屈なことなので、ここでは厳密な定義は行いません。さらに、単一列インデックスは、結合されたインデックス要素の数が 1 である特殊なケースとして見ることができます。

employees.titles テーブルを例に、まずこのテーブルにどのようなインデックスがあるのか​​確認してみましょう。

結果から、titles テーブルのプライマリ インデックスは <emp_no、title、from_date> であり、セカンダリ インデックス <emp_no> があることがわかります。複数のインデックスによって物事が複雑になるのを避けるために (MySQL の SQL オプティマイザは複数のインデックスがあると動作が複雑になります)、ここで補助インデックスを削除します。

ALTER TABLE employees.titles で DROP INDEX emp_no を変更します。

この方法では、PRIMARY インデックスの動作の分析に集中できます。

ケース 1: 列全体の一致。

明らかに、インデックス内のすべての列に対して完全一致が実行される場合にインデックスを使用できます (ここで完全一致とは、「=」または「IN」の一致を指します)。ここで注意すべき点は、理論上はインデックスは順序に敏感ですが、MySQL クエリ オプティマイザは適切なインデックスを使用するために where 句の条件の順序を自動的に調整するため、たとえば where 句の条件の順序を逆にするということです。

効果は同じです。

ケース 2: 左端のプレフィックスが一致します。

クエリ条件が、<emp_no> や <emp_no, title> など、インデックスの左側にある 1 つ以上の連続する列と完全に一致する場合、その条件の一部、つまり条件の左端のプレフィックスのみを使用できます。分析結果から、上記のクエリは PRIMARY インデックスを使用していますが、key_len は 4 であり、インデックスの最初の列のプレフィックスのみが使用されていることがわかります。

ケース 3: クエリ条件ではインデックス内の列の完全一致が使用されますが、中間条件の 1 つが指定されていません。

この場合のインデックスの使用方法は、ケース 2 と同じです。title が指定されていないため、クエリではインデックスの最初の列のみが使用されます。次の from_date もインデックスにありますが、title が存在しないため、左のプレフィックスに接続できません。したがって、結果をスキャンして from_date でフィルタリングする必要があります (ここでは、emp_no が一意であるため、スキャンはありません)。 from_date でも where フィルターの代わりにインデックスを使用するようにしたい場合は、補助インデックス <emp_no, from_date> を追加できます。上記のクエリではこのインデックスが使用されます。さらに、「分離列」と呼ばれる最適化方法を使用して、emp_no と from_date の間の「穴」を埋めることもできます。

まず、タイトルのさまざまな値を見てみましょう。

種類は7種類のみです。 「ピット」となる列の値が比較的少ない場合は、「IN」を使用して「ピット」を埋め、左端のプレフィックスを形成することを検討できます。

今回は key_len が 59 で、インデックスが完全に使用されていることを示しています。ただし、type と rows から、IN は実際には 7 つのキーをチェックする範囲クエリを実行していることがわかります。 2 つのクエリのパフォーマンス比較を見てみましょう。

「穴を埋める」ことでパフォーマンスが少し向上しました。 emp_no でフィルタリングした後に大量のデータが残っている場合は、後者のパフォーマンス上の利点がより明らかになります。もちろん、タイトルの値が多数ある場合は、ピット充填を使用するのは適切ではなく、補助インデックスを作成する必要があります。

ケース 4: クエリ条件でインデックスの最初の列が指定されていません。

これは左端のプレフィックスではないため、このようなクエリではインデックスが使用されないのは明らかです。

ケース 5: 列のプレフィックス文字列を一致させます。

この時点ではインデックスは使用できますが、ワイルドカードが最後にのみ出現しない場合は使用できません。 (元のテキストは正しくありません。ワイルドカード % が先頭に現れない場合はインデックスを使用できますが、特定の状況に応じてプレフィックスの 1 つだけが使用される場合があります)

ケース 6: 範囲クエリ。

範囲列ではインデックスを使用できます (左端のプレフィックスである必要があります) が、範囲列に続く列ではインデックスを使用できません。同時に、インデックスは最大 1 つの範囲列に対して使用されるため、クエリ条件に 2 つの範囲列がある場合、インデックスを完全に使用することはできません。

インデックスは 2 番目の範囲インデックスでは何もできないことがわかります。ここで、MySQL に関する興味深い点があります。つまり、explain のみを使用すると、範囲インデックスと複数値の一致を区別できない可能性があります。これは、両方とも範囲として表示されるためです。同時に、「between」を使用することは、範囲クエリであることを意味するわけではありません。たとえば、次のクエリは次のようになります。

2 つの範囲クエリが使用されているように見えますが、emp_no に作用する「BETWEEN」は実際には「IN」と同等であり、emp_no は実際には複数値の完全一致であることを意味します。このクエリではインデックスの 3 つの列すべてが使用されていることがわかります。したがって、MySQL では複数値のマッチングと範囲のマッチングを慎重に区別する必要があります。そうしないと、MySQL の動作について混乱することになります。

ケース 7: クエリ条件に関数または式が含まれています。

残念ながら、クエリ条件に関数または式が含まれている場合、MySQL はこの列のインデックスを使用しません (ただし、数学的な意味では一部は使用できます)。例えば：

このクエリはケース 5 と同じ機能を持ちますが、left 関数を使用すると title 列にインデックスを適用できなくなります。一方、ケース 5 では LIKE を使用するとこれが可能です。別の例:

明らかに、このクエリは、emp_no が 10001 である関数をクエリすることと同じですが、クエリ条件が式であるため、MySQL ではそのインデックスを使用できません。 MySQL は定数式を自動的に最適化できるほど賢くないようです。したがって、クエリ ステートメントを記述するときは、クエリ内で式を避けるようにしてください。代わりに、代数演算を手動で実行し、式のないクエリ ステートメントに変換します。

インデックスの選択性とプレフィックスインデックス

インデックスはクエリを高速化できるため、クエリ ステートメントで必要な場合は常にインデックスを作成する必要がありますか? 答えは「いいえ」です。インデックスはクエリを高速化しますが、コストもかかります。インデックス ファイル自体がストレージ スペースを消費し、インデックスによってレコードの挿入、削除、変更の負荷が増加します。さらに、MySQL は実行時にインデックスを維持するためにリソースも消費するため、インデックスが多いほど効果的です。一般的に、次の 2 つの状況ではインデックスを作成することは推奨されません。

最初のケースは、テーブルに比較的少ないレコードがある場合です。たとえば、1,000 から 2,000 のレコード、あるいは数百のレコードしかないテーブルなどです。インデックスを作成する必要はなく、クエリでテーブル全体をスキャンするだけで済みます。レコード数がどのくらい多いと判断されるかについては、人それぞれ意見があります。私の個人的な経験では、2000 を境界線としています。レコード数が 2000 を超えない場合は、インデックスを作成しないことを検討できます。レコード数が 2000 を超える場合は、適宜インデックスを作成することを検討できます。

インデックスの作成が推奨されないもう 1 つの状況は、インデックスの選択性が低い場合です。いわゆるインデックス選択性は、一意のインデックス値（カーディナリティとも呼ばれる）とテーブルレコードの数（#T）の比率を指します。

インデックスの選択性 = カーディナリティ / #T

明らかに、選択性の範囲は (0, 1] です。選択性が高いほど、インデックスの価値は高くなります。これは、B+Tree の性質によって決まります。たとえば、上で使用した employees.titles テーブルで、title フィールドが個別に頻繁にクエリされる場合、インデックスを作成する必要があるかどうか。その選択性を見てみましょう。

タイトルの選択性は 0.0001 未満 (正確な値は 0.00001579) なので、タイトル用に別のインデックスを作成する必要はありません。

プレフィックス インデックスと呼ばれるインデックス選択性に関連するインデックス最適化戦略があります。プレフィックス インデックスでは、列全体ではなく列のプレフィックスをインデックス キーとして使用します。プレフィックスの長さが適切であれば、プレフィックス インデックスの選択性をフルカラム インデックスの選択性に近づけることができます。同時に、インデックス キーが短くなるため、インデックス ファイルのサイズとメンテナンスのオーバーヘッドが削減されます。以下では、employees.employees テーブルを例として、プレフィックス インデックスの選択と使用について説明します。

図 12 から、employees テーブルにはインデックス <emp_no> が 1 つしかないことがわかります。そのため、名前で人物を検索する場合は、テーブル全体をスキャンすることしかできません。

従業員を名前で頻繁に検索する場合、これは明らかに非効率なので、インデックスの構築を検討できます。 2 つのオプションがあり、<first_name> または <first_name, last_name> を作成し、2 つのインデックスの選択性を確認します。

<first_name> は明らかに選択性が低すぎますが、<first_name, last_name> は非常に選択性があります。ただし、first_name と last_name の合計の長さは 30 です。長さと選択性のバランスをとる方法はありますか? first_name と last_name の最初の数文字を使用して、<first_name, left(last_name, 3)> などのインデックスを作成し、その選択性を確認することを検討できます。

選択性は悪くありませんが、まだ 0.9313 には少し遠いので、last_name プレフィックスを 4 に増やします。

この時点で、選択性はすでに理想的であり、このインデックスの長さはわずか 18 で、<first_name, last_name> のほぼ半分の長さです。このプレフィックス インデックスを作成しましょう。

 ALTER TABLE従業員.従業員
インデックス`first_name_last_name4` (first_name, last_name(4))を追加します。

ここで、名前でクエリを再度実行し、結果をインデックス作成前の結果と比較します。

パフォーマンスは大幅に向上し、クエリ速度は 120 倍以上向上しました。

プレフィックス インデックスは、インデックス サイズとクエリ速度の両方を考慮しますが、ORDER BY 操作や GROUP BY 操作には使用できず、カバーリング インデックスにも使用できないという欠点があります (つまり、インデックス自体にクエリに必要なすべてのデータが含まれている場合、データ ファイル自体にはアクセスされなくなります)。

InnoDB 主キーの選択と挿入の最適化

InnoDB ストレージ エンジンを使用する場合は、特別な必要がない限り、常に業務に関係のない自動インクリメント フィールドを主キーとして使用します。

主キーの選択の問題について議論している投稿やブログをよく見かけます。ビジネスに関係のない自動増分主キーの使用を提案する人もいれば、それは不要で、学生 ID や ID 番号などの一意のフィールドを主キーとして使用できると考える人もいます。どの議論が支持されるかに関係なく、議論のほとんどはビジネスレベルです。データベース インデックスの最適化の観点から見ると、自動増分主キーなしで InnoDB エンジンを使用することは、間違いなく悪い考えです。

InnoDB のインデックス実装については上で説明しました。InnoDB はクラスター化インデックスを使用し、データ レコード自体はプライマリ インデックス (B+ ツリー) のリーフ ノードに格納されます。これには、同じリーフ ノード (メモリ ページまたはディスク ページのサイズ) 内の各データ レコードが主キーの順序で格納される必要があります。したがって、新しいレコードが挿入されるたびに、MySQL はそれを適切なノードに挿入し、主キーに従って配置します。ページが負荷係数 (InnoDB のデフォルトは 15/16) に達すると、新しいページ (ノード) が開かれます。

テーブルが自動増分主キーを使用している場合、新しいレコードが挿入されるたびに、そのレコードは現在のインデックス ノードの後続の位置に順番に追加されます。ページがいっぱいになると、新しいページが自動的に開かれます。次の図に示すように:

図13

これにより、ほぼ順番に入力されるコンパクトなインデックス構造が生成されます。挿入が行われるたびに既存のデータを移動する必要がないため、効率が非常に高く、インデックスの維持に多くのオーバーヘッドが追加されることはありません。

自動増分されない主キー (ID 番号や学生 ID 番号など) が使用されている場合、主キーの値は挿入されるたびにほぼランダムになるため、新しいレコードはそれぞれ既存のインデックス ページの中央のどこかに挿入されます。

図14

このとき、MySQL は新しいレコードを適切な位置に挿入するためにデータを移動する必要があります。ターゲット ページはディスクに書き戻され、キャッシュからクリアされている場合もあります。このとき、ディスクから読み戻す必要があるため、オーバーヘッドが大きく増加します。同時に、頻繁な移動とページング操作により大量の断片化が発生し、インデックス構造が十分にコンパクトではなくなります。その後、OPTIMIZE TABLE を使用してテーブルを再構築し、充填ページを最適化する必要があります。

したがって、可能な限り、InnoDB の主キーとして自動インクリメント フィールドを使用するようにしてください。

追記

実際、データベースのインデックス チューニングは理論だけに頼ることができない技術的な作業です。実際の状況は常に変化しており、MySQL 自体にもクエリ最適化戦略やさまざまなエンジンの実装の違いなど、非常に複雑なメカニズムがあるため、状況はさらに複雑になります。しかし同時に、これらの理論はインデックス チューニングの基礎でもあります。理論を理解することによってのみ、チューニング戦略について合理的な推論を行い、その背後にあるメカニズムを理解し、その後、実際の継続的な実験と調査と組み合わせて、MySQL インデックスの効率的な使用という目標を真に達成することができます。

さらに、MySQL インデックスとその最適化は非常に広範囲にわたるため、この記事ではその一部についてのみ説明します。たとえば、この記事では、インデックスの最適化や、ソート（ORDER BY）に関連するカバーリングインデックスなどのトピックは取り上げていません。また、この記事では、B-Treeインデックスに加えて、さまざまなエンジンに基づくMySQLでサポートされているハッシュインデックス、フルテキストインデックスなども取り上げていません。