インデックスを使うとなぜ早くなるのか？

はじめに

こんにちは、BTMの坂本です！
突然ですが皆さんはインデックスを貼ったことはありますか？
「早くなるらしいからなんとなく貼っておいた」という方や「貼ったことないしよくわかんない」という方もいるのではないでしょうか。
「インデックスをどう貼ればいいのか？」「インデックスを使うとなぜ早くなるのか？」という疑問に対して、その原理とイメージをざっくりと掴んでいきましょう！

インデックスとは？

インデックスとは「索引」という意味で、書籍などでもよく使用されます。辞書から目的の単語を探すのに、最初の文字がどのページから始まるのかわからないと探すのに時間かかりますよね。DBでも同じく、目的の情報を効率よく見つけるために使用されるもので、パフォーマンスを向上させるためにとても重要な機能です。

なぜインデックスを貼ると早くなる？

「インデックスを貼ると早くなる」ということを知っている方は多いと思いますが、「なぜ早くなるのか？」という質問に答えられる人は意外と少ないかもしれません。回答のひとつとして「効率のいい検索アルゴリズムを使用している」というものがあります。

検索アルゴリズム

数学的な詳しい解説は省略しますが、使用する検索アルゴリズムによって目的の情報を取得するまでの計算量が大きく異なります。

例えば全100巻のマンガから13巻を見つける場合について、線形探索と二分探索の2種類のアルゴリズムで比較してみます。

線形探索

線形探索は本棚の端から端まで、1巻、2巻、3巻…13巻と順番に1つずつ探していく方法です。データ量に対して計算量が比例(線形に変化)します。(計算量: O(n)=13回)

通常、インデックスを使用しない場合は探すヒントがないので、このアルゴリズムで検索することになります。

二分探索

二分探索は、全体を半分に分けた場合にどちらに目的のものが入っているかを探していく方法です。1回の検索で対象が半分になっていくため、計算量は小さくなります(計算量: O(log n)=3回)

このように、大量のデータを検索する場合は線形探索よりも二分探索のアルゴリズムを採用したほうが、目的の情報をより早く見つけることができます。

検索アルゴリズムはほかにもいくつかあり、インデックス作成時にはデータの種類などに応じて適切なアルゴリズムが選択されます。

データ構造

二分探索を応用したデータ構造としてB-Tree, B+Treeといったものがあります。

B-Tree

二分探索アルゴリズムを利用したものがB-Tree構造で、1~10のデータがある場合は以下のような構造をとります。

一番上の階層にあるものはルートノード、一番下の階層にあるものはリーフノードと呼ばれ、各ノードに対して小さいものは左側に、大きいものは右側になるように配置されます。

データが追加された時にどのようにデータが整理されるのか、以下のサイトでシミュレーションすることができます。
https://www.cs.usfca.edu/~galles/visualization/BTree.html

B+Tree

B-Treeをさらに拡張したものにB+Treeというものがあります。

こちらも以下のサイトからシミュレーションできます。
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B-Treeとの大きな違いとして、リーフノードに全てのデータがあり、リーフノード間でのリンクも存在しています。このリーフノード間のリンクは範囲検索時に使用され、より高速化に処理できるようになっています。

DBでのインデックス作成時には、インデックスに指定したカラムのデータが図のような構造でリーフノードに保持されます。(以降このファイルを便宜上「インデックスファイル」と呼ぶことにします)

インデックスファイルではインデックス作成時に指定したカラムのデータは保持していますが、DBレコードの全てのデータを保持しているわけではありません。そのため、リーフノード到達後に別途「レコードファイル」を参照しに行く必要があります。

そのため、インデックスを使用した検索を行う場合は基本的には「インデックスファイル → レコードファイル」の順番に参照してレコードのデータを取得します。

※ インデックスによって検索は高速化されますが、データ挿入時(INSERT時)にはこのインデックスファイルの更新が必要になるため、INSERTのオーバーヘッドが増加してパフォーマンス低下の原因になる可能性があります。

検索の指標

検索する際の重要な指標としてカーディナリティというものがあります。

カーディナリティとは「同一カラムに含まれる値の種類の数」を表す指標で、「条件として指定した場合、全体に対してどれくらい絞り込めるか」に繋がるものです。

カーディナリティが高いカラム、低いカラムの例としては以下のようなイメージです。

カーディナリティ	カラム	特徴
高	ユーザーID, メールアドレス, 電話番号	一意に絞り込める
	氏名	同姓同名の可能性があるがほぼ一意
低	都道府県	47種類で分類されるので絞り込みに弱い
	性別	2種類でしか分類できず絞り込みに弱い

カーディナリティが高いカラムで検索した場合にヒット件数が少なくなるのでパフォーマンスが良くなります。

インデックスの貼り方とパフォーマンス計測例

検証環境

• Windows 10 (WSL2)
• Docker Image: postgresql:15
• PostgreSQL: 15.10
• SQL クライアント: A5:SQL Mk-2

検証

3種類のインデックスパターンでパフォーマンスを比較します：

• 単一カラムのインデックス
• 複合インデックス
• カバリングインデックス

データ投入

例としてusersテーブルを作成し、100万件のデータを登録します。

-- usersテーブル作成
CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    username VARCHAR(50),
    email VARCHAR(100),
    age INT,
    status VARCHAR(20),
    created_at TIMESTAMP,
    updated_at TIMESTAMP
);

-- 100万件のテストデータを挿入
INSERT INTO users (username, email, age, status, created_at, updated_at)
SELECT
    'user' || i as username,
    'user' || i || '@example.com' as email,
    18 + (random() * 62)::INT as age,
    CASE (random() * 3)::INT
        WHEN 0 THEN 'active'
        WHEN 1 THEN 'inactive'
        WHEN 2 THEN 'pending'
        ELSE 'suspended'
    END as status,
    CURRENT_DATE - ((random() * 1000)::INT || ' days')::INTERVAL as created_at,
    CURRENT_DATE - ((random() * 500)::INT || ' days')::INTERVAL as updated_at
FROM generate_series(1, 1000000) i;

インデックス無し

検索に使用するSQL:

SELECT
    username,
    status,
    age
FROM
    users
WHERE
    status = 'active'
    AND age <= 50;

結果（Seq Scanで全件検索）:

実行計画:

QUERY PLAN
Seq Scan on users  (cost=0.00..27293.00 rows=86152 width=22)
  Filter: ((age <= 50) AND ((status)::text = 'active'::text))

単一カラムのインデックス(status)

インデックス作成:

CREATE INDEX idx_status ON users (status);

検索結果（約2倍速）:

実行計画:

QUERY PLAN
Bitmap Heap Scan on users  (cost=1820.46..16582.46 rows=86152 width=22)
  Recheck Cond: ((status)::text = 'active'::text)
  Filter: (age   Bitmap Index Scan on idx_status  (cost=0.00..1798.92 rows=164600 width=0)
        Index Cond: ((status)::text = 'active'::text)

複合インデックス(status, age)

インデックス作成:

CREATE INDEX idx_status_age ON users(status, age);

検索結果（さらに高速）:

実行計画:

QUERY PLAN
Bitmap Heap Scan on users  (cost=1206.75..14814.36 rows=87641 width=44)
  Recheck Cond: (((status)::text = 'active'::text) AND (age   Bitmap Index Scan on idx_status_age  (cost=0.00..1184.83 rows=87641 width=0)
        Index Cond: (((status)::text = 'active'::text) AND (age <= 50))

カバリングインデックス

SELECT句のusername, status, ageを全て含むインデックスを作成すると、レコードファイル参照が不要になります。

インデックス作成:

CREATE INDEX idx_status_age_username ON users(status, age, username);

検索結果（Index Only Scan）:

実行計画:

QUERY PLAN
Index Only Scan using idx_status_age_username on users  (cost=0.42..3627.47 rows=86152 width=22)
  Index Cond: ((status = 'active'::text) AND (age <= 50))

まとめ

インデックスには単一・複合・カバリングなど様々な種類があり、システムフェーズやデータ量によって効果が変わります。構造と仕組みを理解し、計測を繰り返して最適なインデックスを貼りましょう！！