PostgreSQL ノート — INDEX 編

データベースにおいて、クエリ効率を向上させるため、データ量が多いときにはインデックスを作成することでデータベースの検索効率を高速化できる。本記事では PostgreSQL の index について探求する。大半の状況では、直接 CREATE INDEX 構文を使用するだけで一般的な開発シナリオに対応できるが、PostgreSQL では実は多くの異なる index type が提供されている。

前書き

最近、僕個人の小さなプロジェクトで全文検索や位置情報検索などの機能を実装したくなり、PostgreSQL が非常に便利であることに気づいた。全文検索があり、強力な GIS サポート（PostGIS との組み合わせ）があり、トリガー関数、使い勝手の良いウィンドウ関数、hstore などが揃っている。そのため、機能を実装しつつ記録を残しておくことにした。ただ、所詮は自己満足のプロジェクトなので、データ量が小さすぎてインデックスを貼るのすら少し滑稽に思えるほどであり、ここでは厳密なベンチマークは行っていない。

目次

• 索引の基本原理
• PostgreSQL におけるインデックスの作成方法
• インデックス使用時の注意事項
• INDEX のメンテナンス方法
• PostgreSQL における index types
  • B Tree
  • GIN
  • GiST
  • BRIN
  • Bloom

索引の基本原理

データベースにおいて最も重要なのはデータの検索であり、データがストレージに保存されている場合、I/O のパフォーマンス問題をどう処理するかを考慮しなければならない。外部ストレージはハードウェア自体の制限から、メモリから直接読み取るよりもはるかに多くの時間を消費する。データベースにおいて、テーブルにインデックスを作成していない場合、データの検索には sequential scans が使用される。データ量が少ないときは顕著なパフォーマンスの差はなく、インデックスを作成するよりも速いことすらあるが、データ量が大きくなるにつれて、sequential scans は読み取りが極端に遅くなる問題を引き起こす可能性が高い。

索引はどのように sequential scans の遅延問題を解決するのか

ディスク上に追加でインデックス用のテーブルを作成することで、インデックスを目次として利用できる。データベースがクエリを実行する際、指定されたインデックスを参照して該当するインデックスを探し出す。そして、インデックスから実データへのポインタを通じて、ディスク上の物理アドレスへとアクセスする。

B Tree

B Tree は、ディスク向けに最適化された平衡木（Balanced Tree）だ。一般的な二分木とは異なり、B Tree は多くの分岐を持つことができ、木の深さを効果的に減らすことができる。B Tree の原理を説明するにはかなりの分量が必要になるため、ここでは説明を省略する。

PostgreSQL におけるインデックス

インデックスの作成

PostgreSQL では SQL 構文を使ってインデックスを作成できる。

CREATE INDEX index_name ON table_name (column_name) USING method;

PostgreSQL では、アルゴリズムを特に指定しない場合、デフォルトで B-Tree を使用してインデックスが作成される。特定のカラムに対してインデックスを作成することも、複数のカラムに対して一度にインデックスを作成することも可能だ。

CREATE INDEX index_name ON table_name (col1, col2);

"Index Scan using index_subscribers_on_email on subscribers  (cost=0.28..8.29 rows=1 width=76)"
"  Index Cond: ((email)::text = 'xxx@yahoo.co.jp'::text)"

"Seq Scan on subscribers  (cost=0.00..37.38 rows=1 width=76)"
"  Filter: ((email)::text = 'xxx@gamil.co.jp'::text)"

EXPLAIN を使用してクエリのパフォーマンスを観察できる。B-Tree の手法によってクエリ時間を短縮できたことがわかる。

注意：

• CREATE INDEX でインデックスを作成するとテーブル全体がロックされ、データ量が多い場合はかなりの時間を要することがある。
• インデックス作成時に CREATE INDEX CONCURRENTLY を追加することで、テーブルがロックされないようにできる。ただし、インデックスの整合性を確保するため、CONCURRENTLY はインデックス作成により多くの時間がかかる。

When this option is used, PostgreSQL will build the index without taking any locks that prevent concurrent inserts, updates, or deletes on the table; whereas a standard index build locks out writes (but not reads) on the table until it’s done. There are several caveats to be aware of when using this option — see Building Indexes Concurrently.

source

適切なインデックス

データベースがインデックスを使用するタイミングを説明するために、まずは2件しかデータがないテーブルにインデックスを貼ってみる。

CREATE INDEX index_users_on_email ON users (email);
EXPLAIN SELECT email FROM users WHERE email = 'xxx@gmail.com';

"Seq Scan on users  (cost=0.00..1.02 rows=1 width=32)"
"  Filter: ((email)::text = 'xxx@gmail.com'::text)"

データ量が少ないデータに対しては、インデックスを作成したとしても、データベースは依然として sequential scan で検索を行う。

これは、ランダム I/O のコストがシーケンシャル検索のコストよりも高いためだ。したがって、データ量が少ない場合、インデックスを作成してもクエリのパフォーマンスは向上せず、むしろディスクスペースの無駄になってしまう。

index size

1300件余りのデータを持つテーブルに対して index を作成する。

CREATE INDEX index_subscribers_on_email on subscribers (email);
SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size;//80K

pg_relation_size を使って関連するリレーションのサイズを取得する。

• インデックスの削除：DROP INDEX IF EXISTS index_name。

インデックスの整合性を保つため、インデックス作成時に PostgreSQL はテーブル全体に排他ロック（exclusive lock）をかけ、インデックス作成完了後に解放する。そのため、頻繁に参照・更新されるテーブルではサービス中断を引き起こす可能性が高く、件数が膨大なデータの場合、インデックスの作成には数分から数十分かかることもある。

インデックスのメンテナンス

https://wiki.postgresql.org/wiki/Index_Maintenance

まずデータベースからいくつかのデータを削除してみる。データベースにとって、デフォルトの削除処理はディスクから実際に領域を解放するわけではなく、「削除済み」のようなフラグを立てるだけだ。インデックスにとっても、データを削除してもインデックスのサイズは減少しない。

DELETE FROM subscribers WHERE id >1350;
SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size; // 80K

このとき、REINDEX を使用してインデックスを再構築できる。REINDEX INDEX index_name

REINDEX INDEX index_subscibers_on_email;
SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size; // 72K

インデックスを再構築すると不要なインデックスが削除され、インデックスのサイズが減少する。

上記からわかるように、挿入や削除が頻繁に行われるテーブルでは、定期的なインデックスの再構築によってインデックスのサイズを削減できる。大量のデータを削除する必要がある場合も、ディスク容量の無駄を防ぐために、可能な限りインデックスを再構築してインデックスサイズを維持するのがよい。

ただし、REINDEX もテーブルロックを引き起こす。サービスのメンテナンスや一時停止が許されない場合は、CREATE INDEX CONCURRENTLY で新しいインデックスを作成し、その後古いインデックスを削除して新しいインデックスの名前を変更するという方法を取ることもできる。これは REINDEX よりも時間がかかり、手間も少し増えるが、テーブルがロックされないことを保証できる。

特定のデータに対するインデックス

特定の条件を満たすデータのみを頻繁にクエリする場合がある。そのようなときは、すべてのデータにインデックスを貼る必要はない。CREATE INDEX index_name ON table_name WHERE ... を使用することで、必要なデータにのみインデックスを作成できる。

インデックスのソート順

インデックス作成時にソート順を特に指定しない場合、デフォルトでは ASC（昇順）でインデックスが作成される。しかし、ランキングや記事の公開日時など、DESC（降順）でソートすることが多いユースケースでは、DESC でインデックスを作成したほうが効率的だ。

CREATE INDEX index_articles_on_published_date ON articles (published_date DESC);

インデックスの再構築

B-Tree インデックスは、インデックスページが完全に空になったときにのみ再利用されるため、データベース内で特定の値を削除してもインデックスのサイズは減らない。元のデータが1400件で、そこから50件削除しても、インデックスサイズに変化はない。

DELETE FROM subscribers WHERE id > 1350;

SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size; // 80K

インデックスを再構築する：

REINDEX INDEX index_subscibers_on_email;
SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size;
72K

利用されていないインデックスを削除してディスク領域を解放し、不要なインデックスがディスク全体を占有するのを防ぐ。ただし注意すべき点として、REINDEX もテーブルロックを引き起こす。サービスの停止メンテナンスが許されない状況であれば、直接新しいインデックスを作成し、元のインデックスを削除した上で新しいインデックスをリネームすることを検討するとよい。

PostgreSQL における index type

注意：以下の内容はまだベンチマークを行っていない

ここまで PostgreSQL のインデックスとその使い方を紹介してきたが、続いて PostgreSQL でよく使われる index type を紹介する。インデックス作成時に使用する方法を特に指定しない場合、PostgreSQL は B Tree を使用してインデックスを作成する。

Btree

B Tree は以下のクエリ操作をサポートしている：

• <
• <=
• =
• >=
• >

GIN(Generalized Inverted Index)

GIN is designed for handling cases where the items to be indexed are composite values, and the queries to be handled by the index need to search for element values that appear within the composite items.

GIN は全文検索や Array のようなデータ型に用いられる。文字通りの転置インデックス（Inverted Index）であり、Value をインデックス値として扱い、それが出現するインデックスを探し出す。

例えば：

this is cat
this is an apple.
cat meows.
// build inverted index
"this": {(0, 0), (1,0)}
"is": {(0,1), (1,1)}
"an": {(1,2)}
"apple: {(1,3)}
"cat": {(0,2), (2,0)}
"meows": {(2,1)}

上記のインデックス表により、もし cat というキーワードを検索したい場合、キーが cat である値から対応するインデックスを見つけることができる。cat は1つ目の文の2番目の単語、および3つ目の文の1番目の単語に出現していることがわかる。

適用シーン：

• 全文検索
• 配列

PostgreSQL での GIN の使用法：

CREATE INDEX index_on_document on sentences using gin(document);

GiST(Generalized Search Tree)

GiST はむしろ汎用的なインターフェースと言える。GiST を使用して独自のインデックス実装（B-Tree、R-Tree など）を定義できる。一般的にはあまり直接使われることはない。しかし、空間構造データのように、包含、隣接、交差といった検索の高速化は B-Tree では難しい場合がある。そのため、PostGIS などでは GiST を使用して空間構造クエリに対して効率的なインデックスを作成している。

適用シーン：

• 独自のインデックスインターフェースの実装
• 空間構造
• B-Tree ではユースケースに適合しにくいデータ構造

BRIN(Block Range Indexes)

行ごとにインデックスを作成する B-Tree とは異なり、BRIN はある範囲（ブロックレンジ）に対してインデックスを作成する。パフォーマンス面では依然として B-Tree に軍配が上がるが、サイズは B-Tree よりもはるかに小さい。

ログファイルや特定範囲の取引注文、請求データなど、データが範囲クエリで頻繁に検索される場合、これらのデータ量は通常非常に膨大であり、B-Tree でインデックスを作成するとディスクスペースを大きく消費してしまう可能性がある。しかし、これらのデータでは完全一致検索を行うことは比較的少なく、範囲検索などによってバッチ処理することが多い。このような場合に BRIN を使用すると、ディスク領域を大幅に節約しつつ、十分なパフォーマンスを得ることができる。

適用シーン：

• ログファイルの分析
• 取引注文の分析
• データ量が大きく、範囲検索を頻繁に行うケース

Bloom

Bloom Filter は、ハッシュテーブルの空間および検索時間の課題を解決するために考案された。アルゴリズム自体の原理により、ある要素が集合内に存在するかどうかを非常に高速に判定できるが、偽陽性（false positive）が発生する可能性があるため、PostgreSQL 内では再チェックが必要となる。

CREATE INDEX bloom_index_event ON events USING bloom (startTime, endTime, name, gifts)
 WITH (length=80, startTime=2, endTime=2, name=4, gifts=2);

length は各シグネチャの長さであり、デフォルトは 80、最大値は 4096。その後のパラメータは、対応するカラム名が何ビットにマッピングされるかを指定するもので、最小は 2、最大は 4096 である。

適用シーン：

• 複数カラムに対する完全一致検索 SELECT * FROM events WHERE startTime=20171111 and endTime=20171231 and name=christmas and gifts="gift_special"。Bloom Filter を利用することで、集合内に存在しない結果を素早く除外できる。

まとめ

一般的に、B-Tree だけでほとんどのユースケースに対応できる。しかし、PostgreSQL には豊富なインデックスタイプが用意されており、データをより容易に検索・インデックス化できるようになり、開発者により高い柔軟性をもたらしてくれる。これが僕が PostgreSQL を非常に気に入っている大きな理由の一つだ。

1. PostgreSQL にはいくつかのインデックスアルゴリズムが用意されており、それぞれに適したユースケースがある。
2. CREATE INDEX を使用するとテーブル全体がロックされるため、大量のデータにインデックスを作成する際には影響が出る可能性が高い。CREATE INDEX CONCURRENTLY で解決できるが、インデックスの作成にはより多くの時間がかかる。
3. データの更新や削除が頻繁に行われると、余分な index が発生する。ディスク領域の使用量を抑えるため、可能な限り定期的に REINDEX でインデックスを再構築するとよい。同時に REINDEX はテーブルロックを引き起こす点に注意が必要だ。テーブルロックを避けるには、新規にインデックスを作成してから元のインデックスを削除・リネームする方法がある。
4. CREATE UNIQUE INDEX により、ユニーク制約を用いて値の一意性を保証できる。
5. INDEX は WHERE 条件を付与することで、特定のユースケースに特化し、特定のカラムに対してのみインデックスを作成できる。
6. INDEX はソート順（デフォルトは ASC）を指定でき、特定のユースケース（記事の公開日時など）に合わせることができる。
7. インデックスは銀の弾丸ではない。少量のデータではインデックスを貼っても依然として seq scan が使われることが確認できる。これはランダム I/O のコストが seq scan よりもはるかに高いためだ。そのため、固定かつ件数が多くないデータ（例：都道府県、郵便番号など）に対しては、インデックスを作成しても検索時間は改善されず、かえって不要なディスクスペースを占有してしまうことになる。