GIN 逆引きインデックスと配列・JSONB の検索

GIN が解く問題

B+Tree インデックスは「キー1つ → 行1つ(または連続範囲)」を引くのが得意です。しかし扱いたい値が 1行に複数含まれる複合型 になると、この前提が崩れます。たとえば tags text[] 列で「'db' を含む行をすべて出せ」、tsvector 列で「データベース という語を含む文書」、jsonb 列で「{"role":"admin"} を含むドキュメント」——いずれも「1つの行が複数の検索可能な要素を持ち、検索側はその要素のどれか1つにマッチさせたい」形をしています。

GIN(Generalized Inverted Index、汎用逆引き索引) は、まさにこの形のために作られた PostgreSQL の索引です。名前のとおり 全文検索 で使う 転置インデックス(inverted index) を一般化したもので、対象を全文だけに限らず、配列・JSONB・範囲型・trigram など「要素へ分解できる任意の複合値」へ拡張しています。

値を要素キーへ展開する

GIN の核心は 1つの列値を複数のキーへ分解(展開)してから索引化する 点にあります。B+Tree が「値そのもの」をキーにするのに対し、GIN は型ごとに定義された 抽出関数(extractValue) を使い、値を要素の集合へ割り開きます。

この展開によって、検索の問いが「行が値Xに等しいか」ではなく 「行が要素キーKを含むか」 に変わります。tags @> ARRAY['db'](db を含む)も、全文の @@ to_tsquery('データベース') も、内部では「キー db / キー データベース を持つ行はどれか」という同一の問いに帰着します。1つの抽象構造で多様な「含む」検索を捌けるのが GIN の汎用性です。

posting list と posting tree

展開した各要素キーに対して、GIN は そのキーを含む行の位置一覧 を持ちます。行の位置は TID(ヒープ上のタプル識別子、ページ番号+オフセット) で表され、この一覧を posting list(ポスティングリスト) と呼びます。構造を図式化すると次のようになります。

エントリツリー(キーの B+Tree)
  キー "db"     -> [TID2, TID5, TID9, ...]   ← posting list
  キー "sql"    -> [TID5, TID7]
  キー "index"  -> posting tree(別の B+Tree)  ← TID が多すぎる場合

キーそのものは エントリツリー と呼ばれる B+Tree で管理され、ここはキーで二分探索できます。各キーにぶら下がる TID 一覧の扱いが、件数で2段階に分かれます。

• TID が少なければ、エントリと同じページ内に posting list として圧縮格納する。TID は昇順ソートされ、差分(delta)を可変長で符号化するため非常にコンパクトです。
• TID が膨大なら(人気タグなど)、一覧が1ページに収まらないので posting tree という独立した B+Tree に逃がす。キーは TID そのもので、巨大な行集合を効率よく走査・マージできます。

検索の実体は posting list 同士の集合演算 です。tags @> ARRAY['db','sql'](両方を含む)なら、キー db と sql の TID 一覧を取り出し 共通部分(AND) を取ります。どちらも TID 昇順なので、2つのリストを先頭から並走させる マージ交差 で線形時間に処理でき、ランダムアクセスを伴いません。これが「複数要素のAND/OR検索」を GIN が高速にこなせる理由です。

なぜ挿入が重いのか

GIN の弱点は 更新コスト です。1行を挿入すると、その行が展開する すべての要素キー について posting list を更新する必要があります。tags に20個のタグがあれば、エントリツリーを20回たどって20本の posting list へ TID を挿し込みます。しかも posting list は昇順ソートを保つため、末尾追記では済まず、途中への割り込みが起きがちです。1行あたりの索引更新が、B+Tree の比でなく重くなります。

さらに、要素キーは多数の行で共有されます。人気のキーの posting list は頻繁に書き換えられ、競合とページ書き換えの温床になります。素朴に毎回本体を更新すると、書き込みワークロードで GIN は急速に遅くなります。

pending list による挿入の償却

この更新コストを抑えるのが pending list(ペンディングリスト) と、それを使った bulk insert(一括挿入) の最適化です(PostgreSQL では fastupdate として既定で有効)。

挿入時、GIN は新しい行のエントリを すぐには本体のエントリツリーへ反映しません。代わりに、未整理のエントリを pending list という追記専用の領域(連結ページ)へ順次書き足す だけにします。pending list は単なる追記なので、1行あたりの挿入が 本体ツリーの構造更新を伴わない軽い操作 で済みます。多数行の挿入が来ても、まずはここへ溜め込みます。

溜まったエントリは、次のいずれかの契機で まとめて本体へ反映(フラッシュ) されます。

1. pending list のサイズが gin_pending_list_limit(既定4MB)を超えたとき。
2. その GIN への VACUUM が走ったとき。
3. 明示的に gin_clean_pending_list() を呼んだとき。

フラッシュでは、溜まった大量のエントリを キーごとにグループ化してソートし、同じ posting list への挿入を一括で適用 します。1本の posting list を何度も開いて1件ずつ挿すのではなく、対象キーの TID をまとめて1回でマージするため、本体ツリーの更新回数が劇的に減ります。これが「個々の挿入コストを多数の挿入にわたって償却(amortize) する」一括挿入の効果です。インデックス構築(CREATE INDEX)時も同様に、全行を一度ソートしてからキーごとに posting list を組み立てる方式で、1件ずつ挿すより桁違いに速く作れます。

GIN と GiST の使い分け

同じ「含む」系の検索を扱える索引に GiST もありますが、性質が異なります。

おおまかには 「検索が多く更新が少ない」なら GIN、「更新が多い/幾何や範囲を扱う」なら GiST が定石です。配列・JSONB・全文のように「1行が多くの要素を持ち、含む検索を高速にしたい」典型ケースでは GIN が第一候補になります。

JSONB での実際

JSONB に GIN を張ると、ドキュメント DB 的な「このキーと値を含む文書」検索が索引で効くようになります。演算子クラスの選択が重要です。

-- 既定の jsonb_ops: 全パスと値をキー化。@>, ?, ?|, ?& を支援。索引は大きめ
CREATE INDEX ON docs USING gin (data);

-- jsonb_path_ops: 「パス＋値」をハッシュ符号化。@> 専用だが索引が小さく高速
CREATE INDEX ON docs USING gin (data jsonb_path_ops);

SELECT * FROM docs WHERE data @> '{"role":"admin"}';

jsonb_ops はキーの存在演算子(? など)も含め幅広く支援する代わりに、JSON の各パスと値を個別キーへ展開するため索引が肥大します。jsonb_path_ops は「ルートからのパスと値」をまとめて1つのハッシュキーにするので、扱える演算子は包含(@>)に絞られる代わりに 索引が小さく、包含検索が速い のが利点です。アプリが包含検索しかしないなら、後者を選ぶのが定石です。

まとめ

GIN は「1行=1キー」を前提とする B+Tree(B+Tree の内部構造)では扱えない、複合値の包含検索 を一手に引き受ける逆引き索引です。値を要素キーへ展開し、各キーに posting list(多すぎれば posting tree) で行 TID を束ね、検索を TID 集合のマージ演算 へ落とし込みます。代償である重い更新は pending list への追記と一括フラッシュ で償却し、書き込みと読み取りのトレードオフを設定で調整できます。配列・全文・JSONB の「含む」を速くしたいとき、その内側で動いているのがこの構造です。インデックスが物理行をどう指すかという観点は クラスタ化インデックスと非クラスタ化インデックスの内部差 も併せて押さえると、TID を介した逆引きの位置づけがより鮮明になります。