【実務・中級編】 GiSTインデックスの概念 – PostgreSQL

お疲れ様です！データベースのパフォーマンスチューニング、日々の業務で頭を悩ませるポイントの一つですよね。

RDBMS、特にPostgreSQLでインデックスを考えるとき、まず頭に浮かぶのはB-treeじゃないでしょうか？等価検索や範囲検索にめっぽう強くて、たいていのケースで活躍してくれる頼れる存在。まさにエースですよね。

でも、ちょっと待ってください。地図情報とか、予約システムの時間帯検索とか、B-treeだけではどうにも遅い…なんて経験、ありませんか？そんな「B-treeの守備範囲外」の球を、鮮やかにキャッチしてくれるのが、今回ご紹介するGiSTインデックスなんです。

今日は、このちょっと特殊だけど、知ってるとマジで世界が変わるかもしれないGiSTインデックスについて、先輩エンジニアの僕が実践的な使い方から、その仕組み、B-treeとの違いまで、みっちり解説していきますね！

—

GiSTって、そもそも何者？B-treeとの決定的な違い

まず、「GiST（Generalized Search Tree）」という名前を聞いて、「汎用検索木」って訳されても、ピンとこない人もいるかもしれません。大丈夫、僕も最初はそうでした。

B-treeは「順序」に基づくインデックスです。数字の大小、文字列の辞書順といった明確な順序関係があるデータに対して、非常に効率的に動作します。例えば、「100より大きい値」とか「’Apple’から’Banana’までの文字列」といった検索ですね。

じゃあ、GiSTは何が違うのか？簡単に言うと、GiSTは「空間的な関係」や「重なり・包含関係」に強いインデックスなんです。

B-treeは「この値とあの値、どっちが大きい？」という質問に答えるのが得意。
一方、GiSTは「この領域とあの領域、重なってる？」とか「この点が、あの領域の中にある？」という質問に答えるのが得意、と考えるとイメージしやすいかもしれません。

この「順序」ではなく「関係性」に注目する点が、GiSTをB-treeと一線を画す存在にしています。

GiSTが本領を発揮するデータ型と演算子

GiSTが特に有効なのは、B-treeでは効率的なインデックスが貼れないような、「非順序データ」や「複雑なデータ構造」です。具体的には、PostgreSQLだとこんなデータ型や演算子で大活躍します。

• 幾何データ型: `point` (点), `box` (矩形), `path` (パス), `polygon` (ポリゴン), `circle` (円)
• 演算子の例:
• `&&` (重なりがあるか)
• `@>` (左が右を含むか)
• `<@` (左が右に含まれるか)
• `~=` (同じか)
• 範囲型: `int4range`, `int8range`, `numrange`, `tsrange`, `tstzrange`, `daterange`
• 演算子の例:
• `&&` (重なりがあるか)
• `@>` (左が右を含むか)
• `<@` (左が右に含まれるか)
• `-|-` (隣接しているか)
• `+` (結合)
• 全文検索 (tsvector, tsquery): 実はGiSTも利用可能です（通常はGINが使われることが多いですが）。
• IPアドレス (inet, cidr): `inet` や `cidr` 型の包含検索などにも使えます。

どうです？これらって、B-treeでインデックスを貼っても、なかなか効きにくいクエリが多いですよね。例えば、地図上で「この四角いエリアに重なる全ての店舗を検索したい」なんて場合、B-treeだと全件スキャンに近くなってしまうことも…。

そんなときにGiSTの出番なんです！

実際に使ってみよう！GiSTインデックスの威力を体験

言葉だけだと分かりにくいので、実際にコードを動かしてその効果を体験してみましょう。今回は「幾何データ」と「範囲型データ」の2つの例で見ていきます。

例1: 幾何データ（地図上のエリア検索）

ECサイトの商品配送エリアの管理や、位置情報サービスで「現在地から半径Xkm以内」の店舗を探す、なんてのはよくある要件ですよね。ここでは、店舗情報とその位置情報を管理するテーブルを考えます。

— テーブル作成
CREATE TABLE stores (
id SERIAL PRIMARY KEY,
name VARCHAR(255) NOT NULL,
location POINT NOT NULL, — 店舗の座標 (点)
delivery_area BOX NOT NULL — 配送可能エリア (矩形)
);

— ダミーデータの挿入 (適当な店舗とエリア)
INSERT INTO stores (name, location, delivery_area) VALUES
(‘新宿店’, POINT(139.70, 35.69), BOX(POINT(139.68, 35.68), POINT(139.72, 35.70))),
(‘渋谷店’, POINT(139.70, 35.66), BOX(POINT(139.69, 35.65), POINT(139.71, 35.67))),
(‘池袋店’, POINT(139.71, 35.73), BOX(POINT(139.70, 35.72), POINT(139.72, 35.74))),
(‘横浜店’, POINT(139.64, 35.45), BOX(POINT(139.63, 35.44), POINT(139.65, 35.46))),
(‘大阪梅田店’, POINT(135.50, 34.70), BOX(POINT(135.49, 34.69), POINT(135.51, 34.71))),
(‘福岡天神店’, POINT(130.39, 33.59), BOX(POINT(130.38, 33.58), POINT(130.40, 33.60)));

— 大量のダミーデータを追加 (動作確認のため)
INSERT INTO stores (name, location, delivery_area)
SELECT
‘店舗_’ || generate_series,
POINT(130.0 + random() 10, 30.0 + random() 10),
BOX(POINT(130.0 + random() 10 – 0.1, 30.0 + random() 10 – 0.1),
POINT(130.0 + random() 10 + 0.1, 30.0 + random() 10 + 0.1))
FROM generate_series(7, 100000);

GiSTインデックスなしで検索してみる

例えば、「東京タワーのあたり（緯度経度: 139.74, 35.66）が含まれる配送エリアを持つ店舗」を探すクエリを考えてみましょう。

EXPLAIN ANALYZE
SELECT name
FROM stores
WHERE delivery_area @> POINT(139.74, 35.66);

結果は、きっとこんな感じになるはずです。

QUERY PLAN
————————————————————————————–
Seq Scan on stores (cost=0.00..3434.00 rows=33333 width=32) (actual time=0.012..14.322 rows=1 loops=1)
Filter: (delivery_area @> ‘(139.74,35.66)’::point)
Rows Removed by Filter: 99999
Planning Time: 0.081 ms
Execution Time: 14.354 ms
(5 rows)

`Seq Scan` (シーケンシャルスキャン) …つまり全件スキャンですね。データ量が増えれば増えるほど、このクエリは遅くなります。これは困りますよね。

GiSTインデックスを作成して検索してみる

では、`delivery_area` カラムにGiSTインデックスを作成してみましょう。

CREATE INDEX idx_stores_delivery_area_gist ON stores USING GIST (delivery_area);

そして、もう一度同じクエリを実行してみます。

EXPLAIN ANALYZE
SELECT name
FROM stores
WHERE delivery_area @> POINT(139.74, 35.66);

どうでしょう？劇的に速くなっているはずです！

QUERY PLAN
——————————————————————————————————
Index Scan using idx_stores_delivery_area_gist on stores (cost=0.29..8.30 rows=1 width=32) (actual time=0.038..0.040 rows=1 loops=1)
Index Cond: (delivery_area @> ‘(139.74,35.66)’::point)
Planning Time: 0.121 ms
Execution Time: 0.063 ms
(4 rows)

`Index Scan` (インデックススキャン) に変わり、実行時間がミリ秒単位にまで縮まりました。これがGiSTの力です！

例2: 範囲型データ（会議室の予約システム）

次に、会議室の予約システムのような、時間帯の重複をチェックするケースを考えてみましょう。

— テーブル作成
CREATE TABLE bookings (
id SERIAL PRIMARY KEY,
room_id INT NOT NULL,
booking_time TSRANGE NOT NULL — 予約時間帯 (タイムスタンプ範囲)
);

— ダミーデータの挿入
INSERT INTO bookings (room_id, booking_time) VALUES
(101, ‘[2023-10-26 09:00:00, 2023-10-26 10:00:00)’),
(102, ‘[2023-10-26 09:30:00, 2023-10-26 10:30:00)’),
(101, ‘[2023-10-26 11:00:00, 2023-10-26 12:00:00)’),
(103, ‘[2023-10-26 14:00:00, 2023-10-26 15:00:00)’),
(101, ‘[2023-10-27 10:00:00, 2023-10-27 11:00:00)’);

— 大量のダミーデータを追加
INSERT INTO bookings (room_id, booking_time)
SELECT
(random() 50)::INT + 100, — 100～150の部屋ID
TSRANGE(
‘2023-01-01 00:00:00’::TIMESTAMP + (random() 365 24 60 60)::INTERVAL,
‘2023-01-01 00:00:00’::TIMESTAMP + (random() 365 24 60 60)::INTERVAL + INTERVAL ‘1 hour’
)
FROM generate_series(6, 100000);

GiSTインデックスなしで検索してみる

「会議室101が、指定した時間帯（例: 2023-10-26 09:45～10:45）に利用可能か（つまり、既存の予約と重ならないか）」をチェックするクエリです。

EXPLAIN ANALYZE
SELECT id, booking_time
FROM bookings
WHERE room_id = 101
AND booking_time && TSRANGE(‘2023-10-26 09:45:00’::TIMESTAMP, ‘2023-10-26 10:45:00’::TIMESTAMP);

ここでも、GiSTインデックスがなければ `Seq Scan` になるか、`room_id` にB-treeがあっても、`booking_time` の重なり検索は効率が悪いです。

QUERY PLAN
——————————————————————————————————
Seq Scan on bookings (cost=0.00..3684.00 rows=33333 width=16) (actual time=0.013..16.123 rows=1 loops=1)
Filter: ((room_id = 101) AND (booking_time && ‘[2023-10-26 09:45:00,2023-10-26 10:45:00)’::tsrange))
Rows Removed by Filter: 99999
Planning Time: 0.100 ms
Execution Time: 16.145 ms
(5 rows)

GiSTインデックスを作成して検索してみる

`room_id` と `booking_time` の両方で効率的な検索を行いたいので、複合インデックスを貼ってみましょう。もちろん `USING GIST` です。

CREATE INDEX idx_bookings_room_time_gist ON bookings USING GIST (room_id, booking_time);

そして、もう一度クエリを実行します。

EXPLAIN ANALYZE
SELECT id, booking_time
FROM bookings
WHERE room_id = 101
AND booking_time && TSRANGE(‘2023-10-26 09:45:00’::TIMESTAMP, ‘2023-10-26 10:45:00’::TIMESTAMP);

今度は `Index Scan` に変わり、高速化されているはずです。

QUERY PLAN
————————————————————————————————————
Index Scan using idx_bookings_room_time_gist on bookings (cost=0.29..8.30 rows=1 width=16) (actual time=0.035..0.037 rows=1 loops=1)
Index Cond: ((room_id = 101) AND (booking_time && ‘[2023-10-26 09:45:00,2023-10-26 10:45:00)’::tsrange))
Planning Time: 0.130 ms
Execution Time: 0.059 ms
(4 rows)

どうです？この差は、実務でパフォーマンス問題に直面したときに、まさに「救世主」となりえますよね。

GiSTの仕組み、もう一歩踏み込む

さて、GiSTがなぜこんなに強力なのか、その仕組みをもう少しだけ深掘りしてみましょう。

B-treeが各ノードに「キーの範囲」を持つことで順序を保つのに対し、GiSTは各ノードに「最小境界領域 (Minimum Bounding Region: MBR)」という概念を持っています。幾何データなら「最小境界矩形（Minimum Bounding Rectangle）」、範囲型なら「最小境界範囲」といった具合です。

例えば、地図のインデックスであれば、親ノードは子ノードが持つ全ての幾何オブジェクトを包含する「より大きな矩形」を保持します。クエリが来たとき、GiSTはまずルートノードから、検索条件（例えば、「この点を含む矩形」）と重なるMBRを持つ子ノードを探していきます。

ここがB-treeとの大きな違いなんですが、GiSTは一つのクエリに対して、複数の子ノードのMBRが重なる可能性があるため、複数のパスをたどることがあります。 B-treeのように必ず一つのパスに絞り込まれるわけではありません。

そして、GiSTインデックスは「損失がある (Lossy)」と言われることがあります。これは、MBRはあくまで「境界領域」であり、そのMBRの中に存在しても、実際のオブジェクトが検索条件に合致しない（重ならない）ケースがあるためです。

例えば、親子ノードのMBRが重なっていても、実際に子ノードの持っているオブジェクトは重なっていない、といったケースです。そのため、GiSTインデックスを使った検索では、インデックスが絞り込んだ結果に対して、最終的に「Recheck Cond」として元のテーブルのデータを使って正確なフィルタリングを行う必要があります。

しかし、これはデメリットというよりも、GiSTが様々なデータ型や演算子に対応できる「汎用性」を実現するためのトレードオフなんです。大まかに絞り込んでから正確なチェックを行うことで、非常に効率的な検索を実現しています。

実践的なアドバイスと注意点

GiSTインデックス、素晴らしいですよね！でも、銀の弾丸じゃないんで、いくつか注意点とアドバイスがあります。

1. インデックスのサイズと更新コスト:
GiSTインデックスはB-treeに比べて、インデックス自体のサイズが大きくなる傾向があります。また、更新（INSERT, UPDATE, DELETE）の際も、複数のパスを更新する可能性があるため、B-treeよりもコストが高くなることがあります。ライトヘビーなシステムでは注意が必要です。

2. 適材適所が重要:
B-treeで効率的に検索できるような「等価検索」や「順序に基づく範囲検索」にGiSTを使う必要はありません。GiSTはあくまで、B-treeが苦手とする「空間的な重なり・包含関係」や「非順序データ」のためのインデックスです。

3. 対応する演算子を確認する:
GiSTインデックスは、特定のデータ型とそれに対応する演算子の組み合わせで初めて効果を発揮します。`@>`, `&&` など、GiSTがサポートする演算子をクエリで使うようにしましょう。そうでないと、インデックスが使われずシーケンシャルスキャンになってしまいます。

4. `VACUUM` の重要性:
これもGiSTに限った話ではないですが、PostgreSQLではインデックスを含め、テーブルの更新履歴が残ります。特にGiSTのような複雑な構造を持つインデックスでは、定期的な `VACUUM` や `ANALYZE` がパフォーマンス維持のために非常に重要になります。

まとめ

GiSTインデックスは、PostgreSQLの強力な拡張性を示す典型的な例です。幾何データや範囲型データなど、B-treeでは効率的なインデックスが貼りにくいデータに対して、劇的なパフォーマンス改善をもたらしてくれます。

• 「順序」ではなく「関係性（重なり・包含）」で検索したいデータ
• 幾何データ型 (`point`, `box`, `polygon` など)
• 範囲型 (`tsrange`, `daterange` など)

これらの条件に合致するケースでパフォーマンスに悩んだら、ぜひGiSTインデックスの導入を検討してみてください。きっと、皆さんのプロジェクトのボトルネックを解消してくれるはずです。

データベースのインデックスは奥が深いですが、適切なインデックスを選ぶ知識は、パフォーマンスチューニングの強力な武器になります。今回のGiSTの知識が、皆さんの日々の業務に役立てば嬉しいです！

それでは、また次の記事で！