PostgreSQL ノート — インデックス

データベースにおいて、クエリの効率を改善するために、大量のデータがある場合、インデックスを作成することでデータベースのクエリ効率を向上させることができます。本記事では、PostgreSQLのインデックスについて探求します。ほとんどの場合、直接CREATE INDEXの構文を使うことで一般的な開発シナリオに対応可能ですが、PostgreSQLでは様々なインデックスタイプが提供されています。

前書き

最近、自分の小さなプロジェクトで全文検索や位置情報検索などの機能を実装しようとしたところ、Postgresが非常に便利だと感じました。全文検索、強力なGISサポート（PostGISと組み合わせ）、トリガーファンクション、便利なウィンドウ関数、hstoreなどが揃っています。機能を実装する傍ら、少し記録を残すことにしました。ただし、これはあくまで自己満足のプロジェクトなので、データ量が少ない中でのインデックス作成は少し滑稽に感じ、厳密なベンチマークは行っていません。

目次

• インデックスの基本原理
• PostgreSQLでのインデックス作成方法
• インデックス使用時の注意点
• インデックスの維持管理
• PostgreSQLにおけるインデックスタイプ
  • B Tree
  • GIN
  • GiST
  • BRIN
  • Bloom

インデックスの基本原理

データベースで最も重要なのはデータのクエリです。データがハードディスクに保存される際には、I/Oの効率問題を考慮する必要があります。外付けハードディスクはそのハードウェアの制約上、メモリから直接読み取るよりも多くの時間を要します。データベース内でデータテーブルにインデックスが作成されていない場合、sequential scansを使用してデータをクエリします。データ数が少ない場合はあまり明確なパフォーマンス差はありませんが、データが増えるにつれて、sequential scansが遅延を引き起こす可能性が高くなります。

インデックスがsequential scansの遅さを解決する方法

ハードディスク上に追加のインデックステーブルを作成することで、インデックステーブルを目次として利用し、データベースはクエリ時に指定されたインデックステーブルを使って対応するインデックスを検索します。さらに、そのインデックスが実際のデータにリンクし、ハードディスク内の物理アドレスに接続されます。

B Tree

B 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を使用するとインデックスの作成により多くの時間がかかります。

このオプションを使用すると、PostgreSQLは、テーブルに対する同時挿入、更新、削除を妨げるロックを取らずにインデックスを構築します。一方、標準のインデックス構築は、完了するまでテーブルの書き込みをロックします（ただし読み取りはロックしません）。このオプションを使用する際にはいくつかの注意点があります — 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のコストが順次クエリよりも高くなるため、データ量が少ない場合にはインデックスを作成してもクエリ効率は向上せず、逆にハードディスクのスペースを無駄にすることになります。

インデックスサイズ

1300以上のデータに対してインデックスを作成します。

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は全テーブルに対して排他的ロックをかけ、インデックス作成後にのみ解放します。そのため、頻繁に変更が加わるテーブルの場合、サービスが中断される可能性が高く、多くのデータがある場合、インデックス作成に数分から数十分かかることがあります。

インデックスの維持管理

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におけるインデックスタイプ

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

上記でPostgreSQLのインデックスとその使用方法を紹介しましたが、次にPostgreSQLにおける一般的なインデックスタイプを紹介します。インデックスを作成する際に特に使用方法を指定しない場合、PostgreSQLはB Treeを使用してインデックスを作成します。

Btree

B Treeは以下のようなクエリ操作をサポートしています：

• <
• <=
• =

• =

GIN（Generalized Inverted Index）

GINは、インデックスを付ける項目が複合値であり、インデックスによって処理されるクエリが複合項目内に出現する要素値を検索する必要がある場合に対処するために設計されています。

GINは全文検索やArrayのような場合に使用されます。文字通りの意味通りに、倒立インデックスとは、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は実際には汎用インターフェースで、自分自身のインデックスの実装方法（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は各signatureの長さで、デフォルトは80、最大4096です。後続のパラメータは、対応するカラム名がいくつのビットにマッピングされるかを示し、最小は2、最大は4096です。

適用シーン：

• 複数のカラムの正確な検索 SELECT * FROM events WHERE startTime=20171111 and endTime=20171231 and name=christmas and gifts="gift_special"、Bloomフィルターを使用すると、集合内にない結果を迅速に除外できます。

まとめ

一般的に、B-Treeはほとんどの使用シーンを処理できる能力があります。しかし、PostgreSQLには多様なインデックスタイプがあり、データのクエリやインデックスをより簡単にし、開発者に高い柔軟性を提供します。これが私がPostgreSQLを非常に好きな理由の一つです。

1. PostgreSQLにはいくつかのインデックス作成アルゴリズムがあり、それぞれに適した使用シーンがあります。
2. CREATE INDEXを使用する際には全テーブルがロックされ、大量のデータでインデックスを作成する場合には影響を及ぼす可能性があります。CREATE INDEX CONCURRENTLYを使用して解決できますが、インデックス作成にもっと多くの時間がかかります。
3. データが頻繁に更新、削除されると、冗長なインデックスが生じます。可能な限りREINDEXを固定的に使用してインデックスを再構築し、ハードディスクスペースの使用を減らしてください。同時に、REINDEXがテーブルロックを引き起こすことに注意してください。新たにインデックスを作成し、元のインデックス名を削除することでテーブルロックを回避できます。
4. CREATE UNIQUE INDEXを使用することで、値の一意性を保証できます。
5. INDEXはWHERE条件を使用して特定のカラムにインデックスを付け、特定の使用シーンに対応できます。
6. INDEXは順序を付けて（デフォルトはASC）、特定の使用シーンに適合させることができます（発行日など）。
7. インデックスは万能ではなく、小規模データの場合、インデックスを作成しても依然としてseq scanが使用されることがあります。これはランダムI/Oのコストがseq scanよりも高いためです。したがって、固定で数が少ないデータ（例：県、市、郵便番号）にインデックスを作成してもクエリ時間が増加することはなく、逆に不要なハードディスクスペースを占有してしまうことがあります。