TIN：Postgres に全文検索をもたらす
PlanetScaleがPostgres全文検索拡張TINをリリース、48ビットのctidをそのままpostingのネイティブ形式として使用し、85 GB・1億5000万文書のベンチマークでスループットがParadeDB、pg_textsearch、組み込みGINより少なくとも8倍高く、インデックス作成は8分10秒。
日本語
コピー
顧客から最も多く寄せられる Postgres への要望のひとつが全文検索だ。本日、高速で機能が揃い、信頼できる Postgres 全文検索拡張 TIN をリリースする。TIN は「Text INdex」の略で、その名のとおりの仕事をする。TIN は GA 版としてすぐに利用できる。Postgres と Neki データベースのすべてが対象だ。見てほしい：
CREATE INDEX an_index_name ON table_name USING tin(text_column_name);
SELECT * FROM table_name
WHERE text_column_name ==> 'some words';
TIN を作ったのは、優れたテキストインデックスなら次のことができるはずだと考えているからだ：
- ブール式、フレーズクエリ、span クエリ
- 語項のあいまい一致、ワイルドカード一致、正規表現一致
- 大文字小文字とアクセントの折りたたみ
COUNT(*)クエリと BM25 スコアによる top-k クエリ
そして Postgres で使いものになるテキストインデックスは、これらすべてを備えたうえで、join、全文列と他の列型にまたがる複雑な WHERE 句、継続的な更新、レプリケーション、バックアップ、正しいトランザクション可視性にも対応しなければならない。Postgres には既製のテキスト検索インデックスが少なくとも 3 つあるが、これらの要件をすべて満たすものはひとつもなかった。TIN は満たす。しかも TIN は驚くほど速い。
TIN の用途
アプリケーション開発者はテキストインデックスでさまざまな検索機能を作る。EC プラットフォームなら、すべてのキーワードを含む商品トップ 10 件を取得したいかもしれない：
SELECT * FROM products
WHERE description ==> 'stretch denim jeans'
ORDER BY tin.score(ctid) DESC
LIMIT 10
法律フォレンジックのプラットフォームなら、あるキーワード群のいずれかを含む文書をすべて返したいが、順序にはまったく関心がないかもしれない：
SELECT * FROM emails
WHERE body ==> '[insider trading conspiracy]'
画像タグ付けのプラットフォームなら、あるタグが付いた画像の正確な件数を表示したいかもしれない：
SELECT COUNT(*) FROM photos
WHERE tags ==> '"san francisco"';
ほとんどのアプリケーションは、インデックスへのクエリを続けながら文書を挿入、更新、削除する必要もある。検索クエリは、新しい行や変更された行がコミットされた直後に、それらを一致結果として返さなければならない。
TIN の性能とベンチマーク
こうしたシナリオを含む各種の性能を評価するため、ベンチマークを実行した。試したワークロードは次のとおり：
- 合接（すべての語を含む必要がある）、離接（いずれかの語を含めばよい）、フレーズ（すべての語を順序どおりに含む）のクエリ、およびこれらを混ぜたクエリ。
- 文書数を数えるクエリと、BM25 スコアで上位 k 件を取るクエリ。
- ベンチマークのクエリ負荷と並行して、クライアントがインデックスに新しいデータを書き込む場合と書き込まない場合。
ワークロードとコーパス
TIN はさまざまなテキストコーパスと比較テストしてきた。Wikipedia 全体、合計 2.3 TB の Reddit コメント集合、そしてそのまま「pile」と呼んでいる混合ワークロード——797 GB のオープンアクセス研究論文、法律文書、パブリックドメインの書籍、Enron メールを含む。本記事で共有するベンチマーク結果は、Stack Exchange の Q&A をエクスポートしたデータによるものだ。85 GB のコーパスで 1 億 5,000 万文書。このコーパスには標準的なクエリトレースがないため、サンプリングで合成クエリを生成した。長さ 2 から 15 語項の部分文字列を抽出する。各部分文字列を 3 通りに解釈する——合接、離接、フレーズクエリ——合計 1,719 クエリだ。
テスト環境
ベンチマークは AWS i7i.8xlarge EC2 インスタンス 1 台で、ローカル NVMe ストレージ、AVX-512 対応 CPU 上で実行した。テキスト検索拡張ごとに、分離コンテナ内に Postgres 18.6 をインストールし、8 vCPU と 32 GB メモリに制限した。このスペックは、インデックスが Postgres のバッファにすべて収まらないときの各インデックスシステムの挙動を見るのに十分小さい。各ベンチマーク段階は順番に実行するので、エンジン間でリソースを奪い合うことはない。独立した EC2 インスタンスを選んだのは、運用上のオーバーヘッドとレプリケーションの影響を最小限にし、競合するテキスト検索インデックスのベンチマークを再現したい人が同じインスタンス種別とコンテナ制限でできるようにするためだ。Postgres コンテナに検索トラフィックを流すには ParadeDB Benchmarker を使った。測定開始前にウォームアップし、読み取りバイト数と WAL 書き込みバイト数の指標を追加したフォーク版を用意している。3 つを除いて Postgres のパラメータはすべて Benchmarker の既定値のままにした：max_parallel_workers を 8（元は 40）、shared_buffers を 24 GB（元は 128 MB）、maintenance_work_mem を 24 GB（元は 64 MB）に設定し、コンテナのリソースになるべく合わせた。Benchmarker は対象の Postgres サーバーと同じ EC2 インスタンス上で動かし、ネットワーク遅延が測定結果に影響しないようにした。各シナリオで TIN v1.0.2 を、そのワークロードを少なくとも実行できる他のすべての Postgres テキスト検索インデックスと比較した：ParadeDB v0.25.2、pg_textsearch v1.4.0、Postgres v18.6 内蔵の GIN インデックス。TIN 以外では ParadeDB だけが全ベンチマークを完走した。
インデックス構築時間とサイズ
各インデックスのサイズはコーパスの 33% から 61% の範囲で、準備、構築、後処理にかかった時間は 8 分から 129 分だった。TIN 以外の 3 エンジンはコンテナに設定した 32 GB の制限下で失敗したため、インデックス構築時のみ表に示すとおり利用可能メモリを増やした。クエリを実行する前に、すべてのコンテナのメモリを 32 GB に戻した。
| 総所要時間 | インデックスサイズ | 必要メモリ | |
|---|---|---|---|
| TIN | 8分10秒 | 50.7 GB | 32 GB |
| ParadeDB | 19分20秒 | 52.1 GB | 64 GB |
| pg_textsearch | 26分49秒 | 41.5 GB | 128 GB |
| Postgres GIN | 2時間09分04秒 | 28.0 GB | 64 GB |
ハイブリッドクエリ、上位10件をソート
最初のベンチマークでは TIN と ParadeDB を比較した。負荷はハイブリッドクエリ（合取、析取、フレーズ）で、BM25 スコア順に上位10件を取得し、インデックスへの並行書き込みはない。TIN が毎秒処理するクエリ数は ParadeDB の25倍、p99 レイテンシは26分の1。GIN はこのベンチマークを完走できなかった。析取検索の実行中にメモリを使い果たしたためだ。pg_textsearch も完走できなかった。析取検索_しか_扱えないからだ。
インタラクティブチャート：ハイブリッドクエリ、上位10件、読み取り専用
合取とフレーズクエリ、上位10件をソート
次のベンチマークでは TIN を ParadeDB と Postgres GIN と比較した。負荷は合取とフレーズクエリで上位10件を取得、並行書き込みはない。TIN と ParadeDB は BM25 で、GIN は ts_rank_cd でソートする。TIN が処理するクエリ数は ParadeDB の10倍、GIN の541倍、p99 レイテンシはそれぞれ6分の1と1,356分の1。pg_textsearch はここでも不在。析取クエリしか扱えないからだ。
インタラクティブチャート：合取とフレーズクエリ、上位10件、読み取り専用
並行書き込みありの析取クエリ
3つ目の結果では TIN を ParadeDB と pg_textsearch と比較した。負荷は析取クエリで BM25 スコア順に上位10件を取得し、同時に並行クライアントが毎秒1,000行のペースで UPDATE を書き込む。TIN が処理するクエリ数は pg_textsearch の36倍、ParadeDB の57倍、p99 レイテンシはそれぞれ24分の1と36分の1。10分間の実行で、TIN は270,279件の更新を完了し、ParadeDB は185,584件、pg_textsearch はわずか735件だった。ParadeDB の書き込みの受け入れ方は読み取りスループットとレイテンシを犠牲にしている。pg_textsearch の読み取り側は書き込みがあってもなくても 3.5 QPS のまま。絶え間ない読み取りトラフィックのせいで書き込みがいつまでも必要なロックを取れず、書き込みは数秒で止まってしまう。GIN はここでも不在。析取クエリでメモリを使い果たすからだ。
インタラクティブチャート：析取クエリ、上位10件、読み書き並行
インデックスがすべてメモリに載るとき
冒頭で TIN は目を見張るほど速いと書いた。最後のチャートは、インデックスが shared buffers に完全に収まるときの TIN、ParadeDB、Postgres GIN の挙動を示す。この負荷は 8.0 GB の Wikipedia コーパス上で、ある析取クエリにマッチするドキュメント数を数える（ソートはしない）。pg_textsearch はここでも不在。top-k クエリしかできず、カウントクエリはできないからだ。
インタラクティブチャート：析取クエリ、COUNT(*)、読み取り専用
完全な結果
チャートはもう十分だろうが、それでもすべてのユースケースを網羅しているわけではない。以下では同じシナリオに加えてさらにいくつかを表で示す。「MB/query」列は、クエリごとに各インデックスがディスクまたはバッファキャッシュからどれだけのデータを読んだかを表す。TIN はこの数値が低く、それが速さの理由のひとつでもある。同時に、TIN のクエリがバッファキャッシュと I/O 容量に与える影響も小さくなる。つまり、同じサーバー上の他のクエリも速いままでいられる。
Conjunction, disjunction, and phrase queries; top-10
┌────────────────────────────────────────────────────────────────────┐
│ QPS p99 MB/query Updates │
├─────────────────────────┬───────┬──────────┬───────────┬───────────┤
│ TIN - read-only │ 199 │ 256ms │ 65 │ │
│ - with updates │ 172 │ 284ms │ 88 │ 271,398 │
├─────────────────────────┼───────┼──────────┼───────────┼───────────┤
│ ParadeDB - read-only │ 7.9 │ 6,765ms │ 582 │ │
│ - with updates │ 6.0 │ 7,990ms │ 591 │ 193,487 │
└─────────────────────────┴───────┴──────────┴───────────┴───────────┘
Conjunction and phrase queries; top-10 (read-only)
┌───────────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────────┬───────┬───────────┬───────────┤
│ TIN │ 242 │ 212ms │ 73 │
├───────────────┼───────┼───────────┼───────────┤
│ ParadeDB │ 24 │ 1,279ms │ 668 │
├───────────────┼───────┼───────────┼───────────┤
│ Postgres GIN │ 0.4 │ 288,066ms │ 595 │
└───────────────┴───────┴───────────┴───────────┘
Disjunction queries; top-10
┌────────────────────────────────────────────────────────────────────────┐
│ QPS p99 MB/query Updates │
├──────────────────────────────┬───────┬───────────┬─────────┬───────────┤
│ TIN - read-only │ 148 │ 324ms │ 48 │ │
│ - with updates │ 125 │ 354ms │ 77 │ 270,279 │
├──────────────────────────────┼───────┼───────────┼─────────┼───────────┤
│ ParadeDB - read-only │ 17 │ 2,385ms │ 303 │ │
│ - with updates │ 2.2 │ 12,634ms │ 394 │ 185,584 │
├──────────────────────────────┼───────┼───────────┼─────────┼───────────┤
│ pg_textsearch - read-only │ 3.5 │ 8,646ms │ 11,639 │ │
│ - with updates │ 3.5 │ 8,409ms │ 11,656 │ 735 │
└──────────────────────────────┴───────┴───────────┴─────────┴───────────┘
Conjunction, disjunction, and phrase queries; COUNT(*) (read-only)
┌─────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────┬───────┬──────────┬──────────┤
│ TIN │ 179 │ 438ms │ 97 │
├───────────┼───────┼──────────┼──────────┤
│ ParadeDB │ 10 │ 2,704ms │ 544 │
└───────────┴───────┴──────────┴──────────┘
Disjunction queries; COUNT(*); Wikipedia corpus (read-only)
┌───────────────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────────┬──────────┬─────────────┬──────────┤
│ TIN │ 10,260 │ 2ms │ 1.7 │
├───────────────┼──────────┼─────────────┼──────────┤
│ ParadeDB │ 291 │ 95ms │ 22 │
├───────────────┼──────────┼─────────────┼──────────┤
│ Postgres GIN │ 1.4 │ 30,292ms │ 2.5 │
└───────────────┴──────────┴─────────────┴──────────┘
見てのとおり、さまざまなシナリオで TIN のスループットは他の選択肢より少なくとも8倍高く、ディスクから読むデータははるかに少なく、インデックスが毎秒数百行更新されても性能の低下はごくわずかだ。
TIN はなぜこんなに速いのか
ベンチマークでの TIN の結果は信じがたいかもしれない。それを少しでも納得してもらうため、あるいは少なくとも読者の好奇心を満たすために、これほど速くしているアーキテクチャ上の選択をいくつか説明する。ひと言でいえば、すべてのドキュメント posting に連続したドキュメント識別子ではなく Postgres の ctid を使っている。これにより、現代の CPU 上で高度にベクトル化された積集合・和集合演算を行うのに向いている。
ドキュメント識別
テキストインデックスは、インデックス対象の各ドキュメントの各バージョンに識別子を用意する必要がある。それをグループ化して高度に圧縮された posting リストに詰め込む。posting リストは、ある語を含むすべてのドキュメントを記録したものだ。大規模なコーパスでは、「the」のような頻出語の posting リストは数十億件の posting を含みうるし、「xyz-9876」のような語の posting リストは数件しかない。
ほとんどのテキスト検索システムはインデックスをセグメント単位で構成する。セグメント内で posting を持つ n 件のドキュメントには、通常 1 から n のドキュメント識別子が割り当てられる。連続したドキュメント識別子のおかげで、posting リストは delta エンコーディングや bit-packing といった手法で高度に圧縮できる。だがその代わり、セグメントごとにドキュメント識別子が独立して割り当てられる。第4セグメントのドキュメント ID 42 と第7セグメントの ID 42 はまったく別のドキュメントだ。
TIN もインデックスをセグメントとして組織するが、目的はドキュメントに番号を振ることではない。TIN は Postgres の ctid 値をそのままドキュメント識別子として使う。
Postgres のテーブルに格納された各行（タプル）の各バージョンには、対応する ctid 値がある。ctid は「current tuple identifier」（現在のタプル識別子）の略だ。挿入または更新された行はすべて新しい ctid を取得する。これは 48 ビットの数値で、そのタプルの Postgres ヒープ内の物理位置を直接指し示す。テキスト表記では (<block number>, <offset number>) となり、上位 32 ビットがブロック番号、下位 16 ビットがブロック内のオフセットだ。以下では <block number> の部分を「ページ番号」または「ページ」と呼ぶ。
ctid が (190, 17) であれば、それが表すタプルは 190 番ページの 17 番目のスロットにあるとわかる。O(1) の検索が即座に完了する。ctid を使ってヒープから直接行全体を取得することもできる：
-- retrieve the first 10 rows from "books" in physical heap order
SELECT ctid, id, title FROM books ORDER BY ctid LIMIT 10;
-- no scan required! instant O(1) lookup of the row
SELECT * FROM books WHERE ctid = '(190, 17)';
TIN が ctid をそのまま使うのは、Postgres の内部が ctid を使っているからだ。新しいインデックス型を実装する Postgres 拡張は ctid を返さなければならない。Postgres の bitmap scan の背後にあるのは、不正確になりうる ctid ビットマップだ。Postgres の組み込みインデックス型（b-tree、GIN、GiST、hash）はすべて ctid を posting として使う。ctid は Postgres の至るところに存在する。
Postgres の内部で動作するには、連続した識別子を付与するテキスト検索システムは、どこかの時点でそれらの識別子を ctid に変換し直さなければならず、そうして初めて Postgres が使えるようになる。ParadeDB と pg_textsearch はどちらも、このマッピング専用の別個のデータ構造を維持している。1 回のテキスト検索が 1,000 万行にヒットした場合、ParadeDB と pg_textsearch はそれぞれの ctid マッピングで 1,000 万個の識別子を引かなければならない。TIN はこの作業を完全に省いている。
48 ビット識別子は無茶苦茶だ
通常の posting リスト圧縮テクニックは、連続しない 48 ビット数には効果が薄い。delta エンコーディングはページ境界ごとに途切れ、ビットマップは疎すぎて割に合わない。幸い、Postgres のページにはいくつか興味深い性質があり、それによって 2 段階のビットマップエンコーディングが実現可能になる。8KB のページに入るタプルは最大 291 個（8192 バイトから 24 バイトのページヘッダを引き、空でないタプル 1 個あたり最低 28 バイトで割った値）で、TEXT などの列を持つテーブル定義では、ページ内のタプルは 32 個以下であることが多い。つまりページ番号のリストはビットマップが使えるほど稠密で、各ページの内部ではオフセット番号のリストも（十分小さく）ページごとの小さなビットマップが使えるほど稠密だ。
48 ビットの ctid 値をそのまま格納する場合と比べて、節約はかなり大きくなりうる。コーパス全体で見ると、高頻度の語項は posting あたりほぼ 1 ビット、中頻度の語項は約 7 ビット、低頻度の語項は 25 ビットに近づく。一度しか出現しない語項はビットマップとしてすら格納されない。
省かれる作業とベクトル化
TIN のページレベルビットマップ（どのページがある語項を含むか）は 256 ビットで、AVX2 以上をサポートする x86 CPU のベクトルレジスタにちょうど収まる。これによっていくつかの最適化が可能になる。
クエリ the AND rareword を考えてみよう。TIN はページレベルビットマップの AND を 256 ビット（ページ）単位で一度に行う。積集合に存在しないビットはすべて、TIN がそのオフセットレベルビットマップをデコードする必要がまったくないページに対応する。
the OR rareword のような COUNT(*) の選言クエリでは、TIN は posting リストの読み取りをしばしば完全にスキップする。TIN のインデックスメタデータには、各語項の正確な posting 数が格納されている。2 つの語のページレベルビットマップに共通ビットがなければ、それらの選言のカウントは 2 つの正確な posting 数の和に等しい。
各ページレベルビットマップは AVX2 レジスタ 1 個に収まり、各オフセットレベルビットマップは AVX-512 レジスタ 1 個または AVX2 レジスタ 2 個に収まる。合取クエリと選言クエリは、これらのベクトルレジスタに対してそれぞれ AND 命令と OR 命令を実行するだけだ。一致数を数える必要があるクエリは、CPU ネイティブの POPCNT 命令で結果ビットマップのビットを数えられる。高コストなループや分岐命令はほぼすべて回避できる。
カウントではなく行全体を返す必要があるクエリは、ディスクに問い合わせることなくビットの位置から ctid を直接計算する。セットされた位置が_まさに_ ctid なのだ。
TIN があるセグメントから Postgres に返すドキュメント ctid は、本質的にヒープ順でページとページ内のタプルを識別する。つまり Postgres が一致したタプルをヒープから読み取る必要があるとき、それはヒープ順に行われる。最新の NVMe ディスクであっても、シーケンシャルアクセスはランダムアクセスよりはるかに速く、TIN はこの最適化をただで手に入れている。
MVCC の解決
TIN が返す結果は MVCC 的に正しい。つまり、ある時点で実行された 1 つの文は、その時点で自分に見えるタプルだけを見る、あるいは作用する。これは、ヒープベースのクエリ結果のそれぞれが、現在のスナップショットに対して可視性チェックを受ける必要があることを意味する。
ヒープチェック
いくつか異なるやり方がある。クエリによっては本質的にヒープチェックを行う：
SELECT a, b, c FROM lyrics WHERE content ==> 'give you up'
このクエリは実際のヒープデータ（a, b, c の 3 列）を返すため、TIN は何であれ ==> 'give you up' が返すすべての一致する ctid をヒープから取得しなければならない。TIN が各 ctid の背後にある物理的なタプルデータを Postgres に要求すると、Postgres はそのタプルが現在のスナップショットに可視かどうかを TIN に伝える。可視なら返し、不可視なら次の一致する ctid に進み、可視の一致をすべて返し終えるまで続ける。
可視性マッピング
Postgres の「Index Only Scan」のように実行できるクエリ形状もある。インデックスから直接答えを返し、ヒープに触れない（少なくともヒープ全体には触れずに済むことを期待する）。カウントだけを行う次のクエリを考えてみよう。
SELECT COUNT(*) FROM lyrics WHERE content ==> 'give you up'
すべてのヒープページが全可視とマークされていれば、TIN はヒープページに一切触れずにこのカウントを返せる。
もちろん、すべてのデータが静的というわけではない。ヒープが変更された場合、TIN は追加の最適化を行う。Postgres の可視性マップと直接交差させることで、可視の行だけを数えるようにする。TIN のページレベルのビットマップは、同じくページレベルのビットマップである Postgres の可視性マップと効率よく交差できる、まさに適切な仕組みだ。全可視でないページ上の ctid だけがヒープで確認する必要がある。通常、Postgres のインデックスは可視かどうかに関係なく一致するすべての ctid を返し、Postgres のエグゼキュータが1つずつ可視性チェックを行う。TIN はカスタムスキャンを計画し、可視性チェックを TIN 自身の内部に移すことで、ページレベルのビットマップに対するベクトル命令を活用できる。
VACUUM と TIN の生存ビットマップ
ドキュメントの削除をサポートするテキストインデックスは、通常、エンジンに適した何らかの「墓石」リストを維持する。TIN も例外ではない。TIN はセグメントごとに生存ビットマップを維持し、ctid ごとに1ビットを持ち、ページレベル・オフセットレベルのビットマップと同じように構成する。VACUUM が実行され、ある ctid が（UPDATE や DELETE によって）ヒープから削除されたと判定すると、TIN はその ctid の生存ビットをクリアする。クリアされたビットを少なくとも1つ含むページはグループとしてマークされ、クエリがマークされたページグループに触れると、TIN は posting リスト内のオフセットビットマップとその生存ビットマップを AND する。したがって、実際に削除されたタプルを返したり数えたりすることは決してない。
セグメントとマージ
あるテーブルに対して初めて新しいインデックスを作成するとき、TIN は n 個の不変セグメントを作成し、各セグメントはそのテーブルのヒープ内のページの 1/n の posting を含む。データが変化するにつれて、TIN は可変セグメントを作成する。これは検索効率が低いが、新しいドキュメントを挿入しやすい。やがてバックグラウンド worker が各可変セグメントを不変セグメントへ昇格させる。もはや変化しないが、検索効率ははるかに高い。
しばらくすると、TIN は不変セグメントをより大きな不変セグメントへマージし始める。これもバックグラウンドで行われる。
連続したドキュメント識別子を使うテキストインデックスシステムは、マージ後の新しいセグメントを作成するとき、すべてのドキュメントに番号を振り直さなければならない。前述のとおり、第4セグメントのドキュメント ID 42 と第7セグメントの ID 42 は同じドキュメントではない。したがって第4セグメントと第7セグメントをマージするときは、マージ後のドキュメント集合に番号を振り直し、各セグメントのすべてのデータを再パック、再圧縮、再書き込みする必要がある。2つのセグメントをマージするストレージコストは元の2倍とまではいかないが、それに近づきうる。
TIN には番号の振り直しの問題も、そこから生じる書き込み増幅もない。TIN は Postgres の ctid 値をドキュメント識別子として使うため、振り直す必要のあるものが何もない。(190, 17) のような posting はどのセグメントでも同じ意味を持つ。ページレベル・オフセットレベルのビットマップもどのセグメントでも同じ意味を持つ。TIN がセグメントをマージするとき、各旧セグメントの多くのビットマップを新セグメントでそのまま再利用できる。再圧縮する必要はなく、コピーする必要すらない。TIN はディスク上にあるビットマップの帰属を旧セグメントから新セグメントへ直接移せる。これにより書き込み増幅が減り、通常はセグメントのマージに伴う CPU と I/O のオーバーヘッドの大部分も省ける。
まとめ
これが、TIN があらゆるベンチマークで少なくとも8倍速い理由だ。ctid をインデックス内のすべての posting のネイティブ形式として選んだことが、一連の下流効果を生んでいる。
TIN があなたのテキストデータでどれだけ速いか知りたければ、機能をさらに読むか、入門ガイドに進んでほしい。あなたがこれで何を作るのか楽しみにしている。