はじめに
こんにちは、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のデータがある場合は以下のような構造をとります。
一番上の階層にあるものはルートノード、一番下の階層にあるものはリーフノードと呼ばれ、各ノードに対して小さいものは左側に、大きいものは右側になるように配置されます。
データが追加された時にどのようにデータが整理されるのか、以下のサイトでシミュレーションすることができます。
B+Tree
B-Treeをさらに拡張したものに B+Treeというものがあります。
こちらも以下のサイトからシミュレーションできます。
B-Tree との大きな違いとして、リーフノードに全てのデータがあり、リーフノード間でのリンクも存在しています。
このリーフノード間のリンクは範囲検索時に使用され、より高速化に処理できるようになっています。
DBでのインデックス作成時には、インデックスに指定したカラムのデータが図のような構造でリーフノードに保持されます。
(※以降、このファイルを便宜上「インデックスファイル」と呼ぶことにします)
インデックスファイルでは インデックス作成時に指定したカラムのデータは保持していますが、DB レコードの全てのデータを保持しているわけではありません。
そのため、リーフノード到達後に別途「DB レコードを保存しているファイル」を参照しに行く必要があります。(※以降、このファイルを便宜上「レコードファイル」と呼ぶことにします)
そのため、インデックスを使用した検索を行う場合は基本的には「インデックスファイル → レコードファイル」の順番に参照してレコードのデータを取得します。
※ インデックスによって検索は高速化されますが、データ挿入時(INSERT時)にはこのインデックスファイルの更新が必要になるため、INSERT のオーバーヘッドが増加してパフォーマンス低下の原因になる可能性があります。
検索の指標
検索する際の重要な指標としてカーディナリティというものがあります。
カーディナリティとは「同一カラムに含まれる値の種類の数」を表す指標で、「条件として指定した場合、全体に対してどれくらい絞り込めるか」に繋がるものです。
カーディナリティが高いカラム、低いカラムの例としては以下のようなイメージです。
| カーディナリティ | カラム | 特徴 |
|---|---|---|
| 高 | ユーザー ID | 一意に絞り込める |
| ↑ | メールアドレス | 一意に絞り込める |
| 電話番号 | 一意に絞り込める | |
| 氏名 | 同姓同名がいる可能性があるがほぼ一意に絞り込める | |
| ↓ | 都道府県 | 47 種類で分類されるのであまり絞り込めない |
| 低 | 性別 | 2 種類でしか分類できずほぼ絞り込めない |
カーディナリティが低いカラムより高いカラムで検索した場合にヒット件数が少なくなるのでパフォーマンスが良くなります。
インデックスの貼り方とパフォーマンス計測例
検証環境
- Windows 10 (WSL2)
- Docker Image: postgresql:15
- PostgreSQL: 15.10
- SQL クライアント: A5:SQL Mk-2
検証
基本的な仕組みがわかったところで、 3種類のインデックスを使用するパターンについてパフォーマンスを比較してみましょう。
- 単一カラムのインデックス
- 複合インデックス
- カバリングインデックス
データ投入
例としてPostgreSQLで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;
インデックスを何も貼っていない状態での検索結果は以下のようになりました。
実行計画
QUERY PLAN
Seq Scan on users (cost=0.00..27293.00 rows=86152 width=22)
Filter: ((age <= 50) AND ((status)::text = 'active'::text))
Seq Scan となっており、インデックスが使用されずに全検索されていることが分かります。
この結果とそれぞれインデックスを貼った結果を比較していきます。(それぞれの計測時にプライマリインデックス以外のインデックスは削除してあります)
単一カラムのインデックス(status)
WHERE句にstatusとageがあるので、statusにインデックスを貼ります。
インデックス作成
CREATE INDEX idx_status ON users (status);
インデックス確認
SELECT
*
FROM
pg_indexes
where
tablename = 'users';
検索
インデックスを作成していない時と比較すると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 <= 50)
-> Bitmap Index Scan on idx_status (cost=0.00..1798.92 rows=164600 width=0)
Index Cond: ((status)::text = 'active'::text)
Bitmap Index Scan on idx_status となっており、インデックスが使用されていることが分かりますね。
※ 作成したインデックスの種類は DB側で良しなに判断されますが、今回はBitmap Indexが作成されました。
複合インデックス(status, age)
インデックス作成
次に WHERE 句の 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 <= 50))
-> 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))
複合インデックスを使用することによって status のみにインデックスを貼った時よりもさらに高速になりました。
カバリングインデックス
インデックスファイルでは、指定したカラムのデータをインデックスファイルに保持していることを説明しました。
これを元に考えると、SELECT 句など SQL に必要なカラムを全てインデックスファイルに保持している場合は、レコードファイルを参照しに行く必要がなくなります。
今回は username, age, status を SELECT しているので、これを包括(cover)するインデックスを作成します。
インデックス作成
CREATE INDEX idx_status_age_username ON users(status, age, username);
検索
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))
インデックスファイルのみでデータ取得が完結し、レコードファイルを参照する必要がなくなったので、Index Only Scanとなりパフォーマンスが良くなっています。
このように SQL で使用するカラム数が少ない場合などはカバリングインデックスを使用することによってさらに高速化することもできます。
まとめ
インデックスと一言で表現しても様々な種類のインデックスがあります。
システムによってクエリは違ったり、データの少ないシステム運用初期の段階と、データが増えたシステム運用中期から長期など、システムのフェイズによってもインデックスの効果は全く違うものになるので、どんなふうにインデックスを貼れば良いのかを一概に言うのは難しいです。
インデックスの構造や仕組みを理解しておくと、どのようなインデックスを貼ると良さそうなのか(適切なインデックスが使用されているか)を評価することができるようになると思います。
パフォーマンスを計測しつつ、最適な解を見つけていきましょう！！
参考資料
- PostgreSQL 8.1.9 文書
https://www.postgresql.jp/document/pg810doc/html/index.html - 探索アルゴリズムとは？基本から応用まで分かりやすく解説します！
https://products.sint.co.jp/topsic/blog/search-algorithm
Discussion