参考
この記事は、以下の記事を読んで疑問に思ったことを調べた学習記録である。
記事では、Zennのサイト内検索をpg_trgm拡張を使って平均6倍、95パーセンタイルで4.25倍高速化した事例が紹介されている。
なぜ中間一致検索は遅いのか
通常、PostgreSQLでLIKE '%keyword%'のような中間一致検索を実行すると、BTreeインデックスが使えずフルスキャンが発生する。BTreeインデックスは文字列の前方一致には有効だが、中間一致では活用できない構造になっているためである。
データ量が増えると、このフルスキャンが深刻なパフォーマンスボトルネックになる。参考記事では、検索に1秒〜数秒かかる状態だったとのことだ。
n-gramインデックスの仕組み
n-gramインデックスは、文字列をn文字ずつに分割してインデックス化することで、中間一致検索でもインデックスを効かせる仕組みである。
3-gramの例
「PostgreSQL」という文字列を3-gram（トライグラム）で分割すると以下のようになる。
__P, _Po, Pos, ost, stg, tgr, gre, reS, eSQL, QL_, L__
先頭と末尾にはパディング文字（_）が付与される。
検索時の動作
「stgre」というキーワードで検索する場合：
- 検索キーワードを3-gramで分割:
stg,tgr,gre - インデックスからこれらすべてのトライグラムを含む文書を抽出
- 抽出された候補に対してRecheck処理を実行
重要なのは「いずれか」ではなく「すべて」のトライグラムが存在する文書が候補になる点である。もし「いずれか」だと、無関係な文書が大量に候補に含まれてしまう。
Recheck処理が必要な理由
n-gramインデックスでは、インデックスレベルでの検索後に必ずRecheck処理が必要になる。
具体例
以下のような状況を考える。
- 本文: 「小学校校長」
- クエリ: 「小学校長」
3-gramで分割すると：
- 「小学校校長」→
小学校,学校校,校校長 - 「小学校長」→
小学校,学校長
「小学校」が共通しているため、n-gramレベルでは「小学校校長」が候補として抽出される。しかし実際には「小学校長」という文字列は含まれていない。
このようなfalse positive（誤検出）を除外するため、インデックスで絞り込んだ候補に対して、実際に検索キーワードが含まれているかを厳密にチェックする必要がある。これがRecheck処理である。
pg_trgmとpg_bigmの選択
PostgreSQLには2つの主要なn-gram拡張がある。
- pg_trgm: 3-gram方式、PostgreSQL本体にcontribとして付属
- pg_bigm: 2-gram方式、サードパーティ製（NECが開発）
比較表
| 機能 | pg_trgm | pg_bigm |
|---|---|---|
| エコシステム | PostgreSQLコミュニティ | サードパーティ |
| ILIKE対応 | ○ | × |
| 2文字以下の検索 | × | ○ |
| Recheck無効化 | × | ○ |
| インデックスサイズ | 小 | 大（約2倍） |
なぜpg_trgmが選ばれたか
参考記事では、以下の理由でpg_trgmのみを採用している。
- ILIKE対応が必須: 英字の大小文字を区別しない検索を実現
- エコシステムの安定性: PostgreSQLコミュニティによる長期的なメンテナンス
- 2文字以下の対応: トピック検索へのフォールバックで代替可能
pg_bigmでLOWER()を使う方法もあるが、これはカラム全体を小文字化した上でインデックスを作成する必要があり、インデックスサイズがさらに増大する。
GINとGiSTの使い分け
n-gramインデックスの作成時には、インデックスメソッドとしてGIN（Generalized Inverted Index）またはGiST（Generalized Search Tree）を選択できる。
特徴の違い
-
GIN:
- 検索速度が速い
- 構築・更新が遅い
- インデックスサイズが大きい
- 全文検索、JSONB、配列型に適している
-
GiST:
- 検索速度が遅い
- 構築・更新が速い
- インデックスサイズが小さい
- 更新頻度が高いテーブル、幾何データ（地理情報）に適している
GINの内部構造
GINインデックスは以下の要素で構成される。
- エントリツリー（BTree）: 各トライグラムをキーとして保持
- ポスティングツリー/リスト: 各トライグラムがどの行に存在するかを記録
- ペンディングリスト: 最近の更新を一時的に保持
ペンディングリストの役割
GINインデックスは更新が遅いという特性があるため、fastupdate機能（デフォルトで有効）でペンディングリストを使った遅延更新を行う。
- INSERT/UPDATEでペンディングリストに即座に追加
- 検索時はメインインデックス + ペンディングリストの両方をスキャン
- 以下のいずれかでメインインデックスにマージ:
gin_pending_list_limit（デフォルト4MB）に達した時- VACUUM/ANALYZE実行時
gin_clean_pending_list関数の明示的呼び出し
ペンディングリストが大きくなると検索が遅くなるため、適切なVACUUM設定が重要である。
本文検索での課題
参考記事では、タイトル検索は成功したが本文検索は見送られている。
本文検索でRecheck処理が遅い理由
- 本文の文字数が多い: 数千〜数万文字
- インデックススキャンで抽出される候補が膨大: 本文が長いため、多くのトライグラムが一致する
- Recheckの処理対象が多い: 候補すべてに対して中間一致検索相当の処理を実行
結果として、Recheck処理に数秒〜十数秒かかってしまう。
Recheck無効化の試み
pg_bigmでRecheck処理をOFFにする実験も行われたが、以下の問題があった。
clineでclientが引っかかる（3-gram:cliが共通）- ユーザーの意図と異なる結果が多数含まれる
タイトルやトピックの短いテキストでは許容できても、本文検索ではユーザビリティが損なわれると判断された。
CONCURRENTLYオプションの注意点
参考記事では、インデックス作成時にCONCURRENTLYオプションを使用している。
CREATE INDEX CONCURRENTLY idx_my_column_on_my_table_using_trgm
ON my_table USING gin (my_column gin_trgm_ops);
メリット
- テーブルへの書き込みロックなしでインデックス作成
- サービスを停止せずにマイグレーション可能
注意点
- 2回のテーブルスキャンが必要（通常は1回）
- 時間がかかる: 通常のインデックス作成より時間が長い
- 失敗時の扱い: 途中で失敗すると「INVALID」状態のインデックスが残る（手動削除が必要）
- トランザクション制約: トランザクションブロック内では使えない
- ディスク容量: 完成までは新旧インデックスが共存するため一時的に容量増加
CDNキャッシュとインデックス改善の役割分担
参考記事では、最初にCDNキャッシュで対応し、その後pg_trgmインデックスを追加している。
CDNキャッシュの効果
- 人気キーワード（「PostgreSQL」「React」など）: キャッシュヒット率高い
- マイナーなキーワード、初回検索: キャッシュミス
なぜCDNだけでは不十分か
- キャッシュミス時は依然として遅い（1秒〜数秒）
- DB負荷の根本的な解決にならない
- ロングテールの検索クエリ（多様なキーワード）に対応できない
pg_trgmインデックスの役割
- キャッシュミス時でも高速化: フルスキャンを回避
- DB負荷を根本的に軽減: すべての検索クエリに効果
- CDNとの組み合わせで、全体的なパフォーマンス向上を実現
学んだこと
- n-gramの動作原理: 文字列を分割してインデックス化し、すべてのトライグラムが一致する文書を候補とする
- Recheck処理の必要性: false positiveを除外するため、インデックス検索後の厳密チェックが不可欠
- pg_trgmとpg_bigmの選択基準: ILIKE対応、エコシステムの安定性、インデックスサイズのトレードオフを考慮
- GINインデックスの仕組み: ペンディングリストによる遅延更新で書き込み性能を改善
- 本文検索の難しさ: Recheck処理の負荷が大きく、pg_trgmだけでは実用的でない
PostgreSQLの全文検索インデックスは奥が深く、用途に応じた適切な選択が重要であると改めて認識した。