データベースにインデックスを貼る時に考えること

インデックスの仕組み

インデックスは「データベースの目次」です。書籍の牽引と同じように、特定の情報を素早く見つけるための仕組みです。

インデックスがない場合、データベースはテーブル全体をスキャンする必要があります。100万件のユーザーから特定のメールアドレスを探す場合、最悪のケースでは100万行すべてを確認することになってしまいます。しかし、メールアドレスにインデックスを貼っておけば、データベースはB-treeという木構造を使って、わずか数十回の比較で目的のレコードに到達することができます。

[内部的な仕組み]

B-treeインデックスは、平衡二分探索木を使用しており、データの挿入、削除、検索が効率的に行えます。
フルテーブルスキャンと比較して、大幅にパフォーマンスが向上します。

[トレードオフ]

メリット: SELECTクエリのパフォーマンス向上
デメリット: INSERT、UPDATE、DELETEのパフォーマンス低下、ストレージ消費

インデックスを貼るべき状況

1. WHERE句で頻繁に検索される列

まず、検索がどのように動作するのかを理解することが重要です。データベースがWHERE句でレコードを探す時は、基本的に条件に合うレコードを見つけるまで、テーブルのレコードを1行ずつ確認するという作業をを行います。

例えば、特定のメールアドレスを持つユーザーを探すクエリ User.find_by(email: 'student@example.com') を行った場合、インデックスがないとデータベースは最初のレコードから順番に全てのユーザーのメールアドレスを確認していきます。これがフルテーブルスキャンと呼ばれる状態です。テーブルが小さいうちは問題になりませんが、データが増えるにつれて検索時間は線形に増加していってしまいます。

ここでインデックスが登場です。emailカラムにインデックスを貼ると、データベースはB-treeという特殊なデータ構造を作ります。これは、辞書が五十音順に並んでいるのと同じ原理です。辞書で「さくら」と探す時に、まず真ん中あたりを開いて「た行」だったら前半に戻り、「か行」だったら後半を見るという二分探索をしているはずです。

B-treeインデックスも同じ仕組みで、各ステップで探索範囲が半分になっていくので、フルテーブルスキャンよりも早く目的のレコードに到達することができます。

2. 外部キー

例えば、@user.exam_resultsのようなコードを書いた時、Railsは裏側でSELECT * FROM exam_results WHERE user_Id = ?というSQLを発行します。このuser_idでの検索は、明示的にWHERE句を書いていなくても、関連レコードを取得するたびに発生します。

外部キーにインデックスがない状態で何が起きるかをみていきます。例えば、ユーザーが1000人、各ユーザーが平均100回の試験を受けているシステムがあるとします。exam_resultsテーブルには10万件のレコードがあるとします。

あるユーザーが試験結果一覧ページを表示するために、@user.exam_resultsを呼び出すと、データベースはexam_resultsテーブルをスキャンして、そのユーザーのuser_idを持つレコードを探します。10万件全てを確認して、該当する100件を見つけ出します。1人のユーザーのページを表示するために、10万行をチェックする非効率さがわかります。

これが20人のユーザーが同時にログインして各自で試験結果一覧を取得したら、20個のフルテーブルスキャンが同時に走り、合計200万行のデータを処理することになってしまいます。

この問題を、user_idにインデックスを貼ると解決できます。インデックスがあると、特定のuser_idを持つレコードの場所を瞬時に特定できます。10万行のスキャンをする変わりに、数回でインデックス検索で、目的の100件に到達できます。

複数のテーブルを結合する際、外部キーのインデックスがないと、結合のコストが指数関数的に増加してしまいます。例えば、ユーザーと投稿とコメントを結合するクエリを考えてみます。1000人のユーザー、10万件の投稿、100万件のコメントがある場合、外部キーのインデックスがないと、最悪のケースでは数百億回の比較が必要になります。これは実用的な時間では終わりません。

Railsのadd_referenceマイグレーションがデフォルトでインデックスを作成するのは、この理由からです。外部キーにインデックスがないアプリケーションは、データが増えるにつれて必ず破綻します。

3. ORDER BY句で使われる列

ソート処理は、データベースにとって非常にコストの高い操作になります。例えば、試験結果を新しい順に表示するExamResult.order(taken_at: :desc).limit(20)というクエリで考えてみます。taken_atカラムにインデックスがない場合、データベースは次のような処理を行います。

まず、exam_resultsテーブル全体を読み込みます。10万件全てです。次に、taken_atの値で10万件ソートします。そして最後に、ソートされた結果の先頭20件を返します。つまり、20件だけが必要なのに、10万件全てを処理しているわけです。

ソート処理のコストは、データ量に対して線形以上に増加します。一般的なソートアルゴリズムはO(n log n)の計算量を持ちます。これは、データが10倍になると、処理時間は10倍以上に増えることを意味します。

さらに問題なのは、メモリの問題です。データベースはソートのために、対象となるデータをメモリに読み込もうとします。

taken_atにインデックスを貼ると、状況は一変します。インデックスは既にソート済みのデータ構造だからです。データベースはインデックスの先頭（または末尾）から順番に読むだけで、ソート済みの結果を得られます。10万件のソート処理が不要になり、必要な20件だけを直接取得できるのです。

これは特に、ページネーションと組み合わせると重要になります。ExamResult.order(taken_at: :desc).page(100).per(20) のように、100ページ目を表示する場合を考えてください。インデックスがないと、毎回10万件全体をソートして、その中から1981番目から2000番目のレコードを取り出すことになります。ユーザーがページをめくるたびに、この重い処理が走ります。

インデックスがあれば、データベースは既にソートされたインデックスをスキップして、必要な位置から直接20件を読み取れます。1ページ目でも100ページ目でも、パフォーマンスはほぼ変わりません。

4. JOIN操作で使われる列

ユーザー、コース、受講履歴の3つのテーブルを結合して「各コースを受講しているユーザー数を集計する」クエリを考えます。

SELECT courses.name, COUNT(enrollments.id)
FROM courses
JOIN enrollments ON enrollments.course_id = courses.id
GROUP BY courses.id

enrollments.course_idにインデックスがない場合、データベースは「ネステッドループジョイン」という最も単純なアルゴリズムを使います。これは二重ループのようなもので、外側のループでcoursesテーブルの各行を取り出し、内側のループでenrollmentsテーブル全体をスキャンして、一致するcourse_idを探します。

コースが100個、受講履歴が10万件ある場合、100回のフルテーブルスキャンが実行され、合計で1000万行の比較が行われます。これは1000万回の「このレコードのcourse_idは目的のIDと一致するか？」という判定です。データベースの処理時間は数秒から数十秒に達し、ユーザーは待たされることになります。

course_idにインデックスがあると、データベースはより効率的な「インデックスネステッドループジョイン」や「ハッシュジョイン」を選択できます。インデックスを使えば、各コースに対して、そのcourse_idを持つ受講履歴をインデックス検索で直接見つけられます。1000万回の比較が、数百回のインデックス検索に置き換わるのです。

5. ユニーク制約が必要なカラム

ユニーク制約のインデックスは、検索の高速化だけでなく、データの整合性を保証する役割があります。

メールアドレスのケースを考えてみます。Railsのバリデーションvalidates :email, uniqueness: trueするケースです。しかし、このバリデーションだけでは不十分です。

理由は、Railsのバリデーションは次のような流れで動作するからです。

データベースから既存のレコードを検索
該当するメールアドレスがなければバリデーションはパス
そして、新しいレコードをデータベースに挿入

ここでの問題は、2人のユーザーが同時に同じメールアドレスで登録を試みた場合に、次のような状況が起こり得ます。

ユーザーAの処理 : データベースを検索→該当なし→バリデーションOK
ユーザーBの処理 : データベースを検索→該当なし→バリデーションOK（まだAのレコードがそんざいしないため）
ユーザーAの処理 : レコードをINSERT→成功
ユーザーBの処理 : レコードをINSERT→成功（Aと同じメールアドレスで重複）

これはレースコンディションと呼ばれる問題です。
データベースレベルのユニーク制約は、この問題を根本的に解決します。add_index :users, :email, unique: true を実行すると、データベースは2つのことを行います。

既存のデータをチェックして重複がないことを確認します。もし、重複があれば、インデックス作成は失敗します。これにより、過去のデータにも整合性が保証されます。
今後のINSERT操作やUPDATE操作を六っっ句と原始的な操作で保護します。データベースは内部的に、同じ値を持つ2つのレコードが同時に挿入されることを物理的に不可能にします、ユーザーBがINSERTを試みた時、データベースはユーザーAのINSERTが完全に完了するまで待機し、その後、重複エラーを返します。

DB設計段階でどのようにインデックス戦略を立てるのか

要件定義やユーザーストーリーから把握

例えば、「ユーザーが自分の試験結果一覧を確認できる」という要件があったとします。この要件から、試験結果テーブルからユーザーIDで絞り込みを行う検索が必ず発生します。また、一覧ということは、時系列で並び替える必要があることも想定できます。

データベーススキーマから自動的に決まるインデックス

DB設計段階で、テーブル間の関係性を定義すると思うので、以下のようなインデックスは自動的に決まります。

外部キー
ユニーク制約
ポリモーフィック関連

アクセスパターンのマッピング

DB設計と並行して、主要な画面やAPIエンドポイントをリストアップしておく。そして、各画面が「どのテーブルのどのカラムを使って検索するか」を書き出しておきます。

判断に迷うケースの考え方

アクセス頻度を考える
データ量の予測
リアルタイム性

ドキュメントの整備

インデックスの意図を記録しておく。

複合インデックス

複合インデックスは、複数のカラムを組み合わせて1つのインデックスを作成する手法です。

例えば、電話帳で考えみます。同じ姓の中でさらに五十音順で並んでいます。複合インデックスも同じ構造です。add_index :users, [:last_name, :first_name]というインデックスを作ると、データベースは「姓でソートし、姓が同じ場所は名でソートする」という二段階のソーと順序でデータを整理します。

ここで重要なのは、インデックスの順番です。電話帳が「姓と名」の順序であって、「名と姓」の純情ではないということです。「太郎」という名前の人を探そうとしても、電話帳では効率的に探すことはできません。理由は、「山田太郎」「佐藤太郎」もバラバラの場所にあるからです。

これが複合インデックスの最も重要な原則「左端一致の原則」です。複合インデックスは、左側のカラムから順番にしか利用できません。

左端一致の原則

add_index :exam_results, [:user_id, :taken_at, :score]という3つのカラムを持つ複合インデックスを例に、この原則を詳しく見ていきます。

このインデックスは、データをまずuser_idでソートし、同じuser_idの中でtaken_atでソートし、さらに同じtaken_idの中でscoreでソートした状態で保持していきます。

この構造から、次のようなクエリパターンでインデックスが使われます。まず、user_idだけで検索するクエリは最適化されます。user_idを検索するクエリは複合インデックスの第一階層だけを使用して動作します。

次に、user_idとtaken_atの両方で検索するクエリも最適化されます。まず。user_idで絞り込み、その中でtaken_atで絞り込むという。インデックスの構造に完全に一致した処理ができます。

さらに、三つ全てのカラムを使うクエリも当然最適化されます。

複合インデックスと単一インデックスの違い

user_idのインデックスとtaken_atインデックスを別々に作れば、両方のカラムでの検索に対応できるのでは？という疑問が湧きました。

しかし、個別にインデックスを使う場合、データベースは通常、どちらか一方のインデックスしか使用しません。そのため、ExamResult.where(user_id: 123, taken_at: date)というクエリがあった場合には、user_idのインデックスを使ってuser_idのレコードを見つけ、その結果に対してtaken_atの条件でフィルタリングします。

複合インデックスが効果を発揮するパターン

絞り込みとソートを組み合わせるソートです。

例えば、Post.where(user_id: current_user.id).order(created_at: :desc).limit(20)という、ユーザーの投稿一覧を新しい順に表示する機能があるとします。

user_idにインデックスがある場合、まずuser_idで絞り込み、該当する投稿を取得し、created_atでソートし、上位20件を返します。

しかし、add_index :posts, [:user_id, :created_at]という複合インデックスがあれば、各ユーザーの投稿が既にcreated_atでソートされた状態になります。データベースはインデックスの先頭から順番に20件を直接取得できるため、ソート処理が不要になります。

これは特にページネーションで効果を発揮します。

インデックスにおけるMySQLとPostgreSQLの違い

MySQLは、テーブルのデータ自体が主キーのインデックス順に物理的に並べられている。本棚の本が背番号順に並んでいるイメージ。

PostgreSQLは、すべてのインデックスが平等。図書館の牽引カードが本の物理的棚の位置を直接示しているイメージ。

MySQLでは、主キーの設計が重要になる。主キーは単に一意性を保証するだけでなく、データの物理的な配置を決定するからです。例えば、UUIDのようなランダムな値を主キーとすると、新しいレコードの挿入位置がランダムになり、データの断片化が進んでしまいます。

まとめ

データベースのインデックスを貼る時に考慮することは、「WHERE句で頻繁に検索されるカラムかどうか」「外部キーかどうか」「ユニーク制約が必要なカラムかどうか」「ソートに使われるカラムかどうか」「JOINが行われるカラムかどうか」という点を中心に考えて設計をします。

外部キーとユニークキーはRailsのマイグレーションでも自動的にインデックスが作成されますが、特定のユーザーのデータを取得する時や複数テーブルを結合する際に、外部キーにインデックスがないとパフォーマンスが低下してしまうので、設定するのが重要です。
ユニークキーのインデックスに関しても、レースコンディションによってデータの整合性が破壊されてしまうリスクがあるため、データベースレベルでインデックスを設定しておくことが重要です。

実際に、インデックス戦略を考える時は、要件定義やユーザーストーリーからアクセスパターンを洗い出し、DB設計段階で主要な検索条件やソート条件を把握しておくことが重要です。

また、複合インデックスは絞り込みとソートを組み合わせるケースで特に効果を発揮するので、左端一致の原則を理解した上で設計を行うことが重要です。