ジュニアバックエンド開発者にデータベースのインデックスを教える

データベースインデックスの理解：実践ガイド

インデックスとは

データベースインデックスは、データベースがテーブルと並行して維持する別のデータ構造です。これは、1つ以上の列の値をソートされ、検索可能な形式で格納し、実際の行へのポインタを保持します。テーブル自体がデータを格納し、インデックスは行をより速く見つけるのを助けることだけを目的とした追加の構造です。

ここで1つのアナロジーを紹介します。これはあなたが知る必要がある唯一のアナロジーです。インデックスは、教科書の巻末にある索引のようなものです。「トランザクション」という言葉が出てくるすべてのページを知りたい場合、本をページごとに読むのではなく、アルファベット順にソートされた索引で「トランザクション」を検索し、ページ番号の短いリストを取得して、それらに直接ジャンプします。その索引がなければ、すべてのページをスキャンするしかありません。データベースもまったく同じ選択肢に直面します。インデックスを使用して一致する行にジャンプするか、テーブル全体をスキャンするかです。

アナロジーなしの実際の動作を見てみましょう。SELECT * FROM orders WHERE customer_id = 42 のようなクエリを実行すると、データベースには2つの基本的な戦略があります。フルテーブルスキャンは、すべての行を読み取り、条件をチェックします。これはテーブルのサイズに比例した時間を要します。インデックスルックアップは、代わりにソートされたインデックス構造で customer_id = 42 を検索し、一致するエントリをすばやく見つけ、格納されたポインタをたどってそれらの行だけを取得します。少数の行しか一致しない大きなテーブルの場合、インデックスパスは数千倍安くなる可能性があります。

Bツリーインデックスの仕組み（概要）

最も一般的なインデックスタイプはBツリーです。これは、キーがソート順に保持されるバランスの取れたツリー構造です。ルートノードはキー空間を範囲に分割し、各子ノードはさらに細分化し、最下位レベル（リーフ）にはテーブル行へのポインタを含む実際のインデックス値が含まれます。ツリーはバランスが取れており、各ノードは多くのキーを保持しているため、何億もの行を持つテーブルでも、特定の値を検索するには通常3〜5回のノード読み取りしか必要ありません。

Bツリーは値をソート順に保持するため、完全一致以上のものをサポートします。範囲条件（WHERE created_at >= '2024-01-01'）、文字列のプレフィックス一致（WHERE email LIKE 'anna%'）を効率的に処理し、行を既にソートされた状態で返すことができるため、データベースは一致するORDER BY句の別のソートステップをスキップできます。

インデックスにコストがかかる理由

インデックスは無料ではなく、これがあなたが理解しなければならないトレードオフです。

書き込みが遅くなります。すべてのINSERTは、テーブルのすべてのインデックスにエントリを追加する必要があります。すべてのDELETEはエントリを削除する必要があります。インデックス列を変更するすべてのUPDATEは、対応するインデックスエントリを更新する必要があります。6つのインデックスを持つテーブルは、論理的な行の挿入ごとに最大7回の書き込みを行います。書き込み負荷の高いテーブルでは、不注意なインデックス設定はスループットを測定可能に低下させます。

ストレージが増加します。各インデックスは、インデックス付けされた列の値の完全なコピーに加えて、ポインタとツリー構造です。大きなテーブルのインデックスは、テーブル自体のサイズに匹敵するか、それを超えることがあり、バックアップやメモリキャッシュにも影響します。

したがって、基本原則は次のとおりです。インデックスは、読み取り速度のために書き込みコストとストレージを交換します。読み取りが明らかにメリットのある場所に追加し、どこにでも追加するわけではありません。

選択性：値の決定における重要な概念

選択性は、条件が行をどれだけ絞り込むかを表します。選択性の高い列は、行数に対して多くの異なる値を持っています。メールアドレスや注文IDは選択性が高いです。これらをフィルタリングすると、数百万行のうち1行または数行が返され、インデックスが輝きます。ステータスが3つの値（「保留中」、「発送済み」、「キャンセル済み」）を持つ列や、ブール値のis_activeフラグは選択性が低いです。フィルタリングすると、テーブルの40％が一致する可能性があります。

なぜこれが重要なのでしょうか？条件がテーブルの大部分に一致する場合、数百万行のインデックスとテーブルの間を行き来するのは、テーブルを順番にスキャンするよりも遅くなることがよくあります。クエリオプティマイザはこれを認識しており、推定一致率が高すぎるとインデックスを無視します。大まかな直感として、インデックスを使用した典型的なクエリが数パーセント以上の行を返す場合、インデックスはまったく使用されず、純粋なオーバーヘッドになります。

複合インデックスと左側プレフィックスルール

インデックスは、特定の順序で複数の列をカバーできます。たとえば：

CREATE INDEX idx_orders_customer_date ON orders (customer_id, created_at);

これは、顧客IDで最初にソートし、次に各顧客内で作成日時でソートするエントリのように考えてください。電話帳が姓でソートされ、次に名でソートされるようなものです。

左側プレフィックスのアイデアは、そのソート順から直接導き出されます。このインデックスは、以下を効率的に処理できます。

• WHERE customer_id = 42
• WHERE customer_id = 42 AND created_at >= '2024-01-01'

しかし、WHERE created_at >= '2024-01-01' だけでは効率的に処理できません。なぜなら、特定の日付範囲のエントリはすべての顧客に散らばっているからです。姓でソートされた電話帳を使用して「アンナ」という名前のすべての人を見つけることはできません。インデックスは、条件が列リストのプレフィックス（左端の列から始まる）を制約する場合にのみ使用できます。これは、(customer_id, created_at) と (created_at, customer_id) が異なるインデックスであり、異なるクエリを処理することを意味します。列の順序は、最も重要なクエリパターンに従う必要があります。一般的な経験則：等価条件の列を最初に置き、次に範囲またはソート列を置きます。

インデックスが役に立たない場合

• 低い選択性：テーブルの90％が行アクティブである場合にWHERE is_active = true でフィルタリングします。オプティマイザは代わりにスキャンします。
• 列に関数または式を使用：WHERE LOWER(email) = 'x@y.com' は、インデックスが生の値ではなく変換された値を格納するため、email の通常のインデックスを使用できません。（一部のデータベースは式インデックスをサポートしていますが、通常のインデックスは使用されません。）
• 先頭ワイルドカード：WHERE name LIKE '%son' はBツリーを使用できません。ソート順はプレフィックスがわかっている場合にのみ役立ちます。
• 複合インデックスの左端の列をスキップすること（上記参照）。
• 小さなテーブル：数百行の場合、スキャンは既に高速です。インデックスはメリットなしに書き込みコストを追加します。
• インデックス付けされた列の型の一致しないものや暗黙的なキャストも、インデックスの使用を妨げる可能性があります。

2つの小さな例

有用なインデックス。アプリケーションが常に以下を実行していると仮定します。

SELECT id, total, created_at
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;

このインデックスが最適です。

CREATE INDEX idx_orders_customer_date ON orders (customer_id, created_at);

データベースは顧客42のエントリにジャンプし、それらは既に作成日時でソートされており、最新の20件を読み取って停止します。テーブルのサイズに関係なく高速であり、左側プレフィックスのおかげで顧客IDによる通常のルックアップも処理できます。

問題のあるインデックス。代わりに以下を作成したと仮定します。

CREATE INDEX idx_orders_status ON orders (status);

ここで、ステータスには3つの可能な値があり、ほとんどの行は「発送済み」です。SELECT * FROM orders WHERE status = 'shipped' のようなクエリはテーブルの大部分に一致するため、オプティマイザはそれでもテーブルスキャンを実行します。インデックスはほとんどまたはまったく使用されませんが、すべての挿入とすべてのステータス更新はそれを維持するためにコストを支払います。これは純粋な損失です。（知っておくべき例外：低カーディナリティの列へのインデックスは、1つの値がまれで頻繁にクエリされる場合、たとえば少数の「保留中」の注文の場合に役立ちますが、上記の一般的なバージョンはよくある間違いです。）

インデックス追加前の実践チェックリスト

1. まず実際の遅いクエリを特定します。推測でインデックスを付けないでください。実際のクエリパターンを確認し、EXPLAINを使用して現在のプランを確認します。
2. 選択性を確認します。このインデックスを使用する典型的なクエリは、テーブルのごく一部を返しますか？そうでない場合は、再検討してください。
3. マルチカラムフィルタリングとソートの場合、いくつかの単一カラムインデックスよりも、適切なカラム順序（等価条件の列を先に、次に範囲/ソート列）を持つ1つの複合インデックスを設計します。
4. 左側プレフィックスルールを確認します。最も一般的なクエリは、インデックスの最初の列を制約しますか？
5. クエリがインデックス付き列の関数、先頭ワイルドカード、または型キャストでインデックスを無効にしていないことを確認します。
6. 書き込みトラフィックを考慮します。書き込み負荷の高いテーブルでは、追加のインデックスごとに実際のコストがかかります。互いに重複しているか、または他のインデックスのプレフィックスであるインデックスを削除します。
7. 新しいインデックスを作成する前に、既存のインデックスが既にクエリをカバーしているかどうかを確認します。
8. インデックスを作成した後、EXPLAINを使用してオプティマイザが実際にそれを使用していることを確認し、クエリ時間を前後で測定します。
9. 定期的に未使用のインデックスを見直し、削除します。それらは永遠に書き込みとストレージのコストを発生させます。

維持すべき中核的なメンタルモデル：インデックスは、特定の選択的な読み取りを安価にするために、すべての書き込みでコストを支払うソート済みルックアップ構造です。それがサービスを提供するクエリを名前で呼び、それが役立つことを示せる場合にのみ追加します。

データベースインデックスについてお話ししましょう。あなたはSQLクエリを書いてきたと思いますが、それはおそらく数百万行もあるテーブルでは、開発マシン上ではうまく動作するでしょう。しかし、テーブルが数百万行に成長すると、それらのクエリの一部は信じられないほど遅くなる可能性があります。インデックスは、この問題を解決するために私たちが使用する最も一般的なツールです。

データベースインデックスとは何か？例え話

インデックスを教科書の巻末にある索引と考えてください。「B-tree」という言葉が出てくるすべてのページを見つけたい場合、本を最初から最後まで通して読む必要はありません。代わりに、索引にアクセスし、「B-tree」のエントリを見つけ、ページ番号のソートされたリスト（例：112、254、256）を確認します。これははるかに高速です。

データベースインデックスも同様に機能します。これはデータベースが維持する別のデータ構造です。テーブル内の1つ以上の列のデータのコピーをソートされた順序で保持し、テーブル内の元の行へのポインタも保持します。その列のデータをクエリする場合、データベースはこのソートされたインデックスを使用して、テーブル全体を1行ずつスキャンする（「フルテーブルスキャン」）のではなく、必要な行へのポインタをすばやく見つけることができます。

仕組み：B-tree

ほとんどのリレーショナルデータベースは、標準インデックスにB-treeを使用しています。コンピュータサイエンスの詳細を知る必要はありませんが、大まかに言うと、B-treeは自己平衡型のツリー構造です。分岐する階層を想像してください。値を検索するために、データベースはルートノードから開始し、分岐をたどります。各ステップで検索範囲が劇的に狭まります。これにより、データベースは非常に少ないステップで巨大なデータセット内の任意の値を検索できるため、フルテーブルスキャン（線形時間計算量、O(n)）と比較して、検索は信じられないほど効率的になります（対数時間計算量、O(log n)）。

トレードオフ：書き込み速度とストレージ

インデックスは無料ではありません。主なコストは2つあります。

1. **ストレージ：**インデックスはディスクに保存される物理的なデータ構造です。テーブルのデータを複製するため、追加のストレージ容量を消費します。
2. **書き込み速度の低下：**これは最も重要なトレードオフです。行をINSERT、UPDATE、またはDELETEする場合、データベースはテーブルを変更するだけではありません。同期を保ち、ソートされた状態を維持するために、影響を受ける列を含むすべてのインデックスを更新する必要があります。テーブルに5つのインデックスがある場合、1つのINSERTステートメントは実際には6回の書き込みになります。テーブル用が1回、各インデックス用が1回です。これは書き込み負荷の高いアプリケーションの速度を大幅に低下させる可能性があります。

実用的なインデックス作成の重要概念

1. 選択性
選択性とは、列内のユニークな値の数が総行数に対してどれだけ多いかを示すものです。

• 高い選択性： user_idやemail_addressのように、ほとんどの値がユニークな列。これらの列のインデックスは非常に効果的です。なぜなら、検索をすぐに1行または数行に絞り込むことができるからです。
• 低い選択性： ブール値のis_activeフラグ（true/false）やstatus列（'pending'、'active'、'inactive'）のように、ユニークな値が非常に少ない列。選択性の低い列のインデックスは、しばしば役に立ちません。すべてのアクティブユーザーを検索する場合、それはテーブルの80％になる可能性があります。データベースがインデックスとテーブルデータを何度も行き来するよりも、テーブル全体を読み取る方が効率的です。

2. 複合インデックスと最左プレフィックスルール
複合インデックスは、2つ以上の列に対するインデックスです。例：CREATE INDEX idx_name ON users (last_name, first_name);。

列の順序は非常に重要です。これが最左プレフィックスルールです。(A, B, C)に対するインデックスは、データベースが次のクエリを高速化するために使用できます。

• Aでフィルタリングするクエリ
• AとBでフィルタリングするクエリ
• A、B、およびCでフィルタリングするクエリ

しかし、B、C、またはBとCのみでフィルタリングするクエリには使用できません。データベースは検索を開始するために、インデックス定義の最初の列が必要です。

SQL例

数百万行を持つproductsテーブルがあると仮定します。

良いインデックスの例：
多くのユーザーがユニークな製品コードで製品を検索しています。

-- クエリ
SELECT name, price FROM products WHERE product_code = 'ABC-12345';

-- 解決策：高い選択性を持つ列へのインデックス
CREATE INDEX idx_products_product_code ON products (product_code);

このインデックスは非常に効果的です。なぜなら、product_codeはユニーク（高い選択性）であり、インデックスによりデータベースはほぼ瞬時に正確な製品行を見つけることができるからです。

あまり役に立たないインデックスの例：
現在販売中のすべての製品を見つけたいとします。

-- クエリ
SELECT * FROM products WHERE is_available = TRUE;

-- 問題のあるインデックス
CREATE INDEX idx_products_is_available ON products (is_available);

このインデックスはあまり役に立ちません。is_available列は選択性が低い（trueとfalseの2つの値しかない）です。製品の90％が利用可能な場合、データベースはこのインデックスを無視し、フルテーブルスキャンを実行する可能性が高いです。なぜなら、それがより効率的だからです。

チェックリスト：インデックスを追加するタイミング

インデックスを追加する前に、これらの質問を自問してください。

1. テーブルは大きいですか？（小さいテーブルへのインデックスはほとんどまたは全くメリットがありません）。
2. 特定のクエリが遅いですか？（インデックスを無計画に追加しないでください。既知のパフォーマンス問題を解決するために追加してください）。
3. WHERE句でこの列を頻繁にフィルタリングしていますか、またはJOINで使用していますか？（これらはインデックス作成の主な候補です）。
4. その列は高い選択性を持っていますか？（インデックスはチェックする行数を大幅に絞り込むでしょうか？）。
5. 複合インデックスの場合、クエリはインデックスの最左列を使用していますか？
6. これは読み取り負荷の高いテーブルですか？（テーブルの書き込みが非常に頻繁で読み取りが少ない場合、インデックスを維持するコストが読み取りのメリットを上回る可能性があります）。