（Postgres）検索エンジンを分解する

データベースはクエリを高速化するためにインデックスを使う。テーブルの行を1つずつ見て値が一致するか確かめる代わりに、まずインデックスでその値を探し、該当する行へ直接たどり着く。ほとんどのデータベースインデックスは b-tree または b+tree で、ある列の値を全順序で並べるため、完全一致、値の範囲、前方一致で素早く見つけられる。たとえば b-tree なら、名前が Rick のユーザー全員、価格が5ドル未満の商品すべて、作成日がとある年の11月に入る倉庫すべてを高速に洗い出せる。だが b-tree は文字列の途中には一致できない。全文検索インデックスはまさにそのためにある。こうしてはいけない——users テーブルのすべての行 name を検査することになる：

SELECT * FROM users
 WHERE name LIKE '% Royal';

こうするのはなおさらだめだ——vendors テーブルの各 description を3回検査することになる：

SELECT * FROM vendors
 WHERE description LIKE '%postgres%'
 AND description LIKE '%reliable%'
 AND description LIKE '%fast%';

こうした用途に正しい道具は転置インデックスで、ほぼすべての全文検索エンジンがこれを使って、文書に含まれる語から文書を素早く特定している。PlanetScale TIN は Postgres 向けの完全な全文検索インデックスである点に注意してほしい。TIN の機能、性能、実装の詳細は別の記事で深く掘り下げている。全文検索インデックスの体系的な復習が必要な読者は、このまま読み進めてほしい。

転置インデックスの概要

転置インデックスは、通常はディスク上に置かれるデータ構造で、語項を位置へ対応づける。仕組みは本の巻末索引そっくりだ。b-tree ともかなり似ているが、違いはこうだ。b-tree のキーはテキスト列の値そのものだが、転置インデックスのキーはテキストフィールドに現れる語の1つ1つである。ついでに言えば、なぜ「転置」と呼ぶのか。他のインデックスに対してではなく、テキストそのものに対して転置されているからだ。テキストは位置の並びであり、各位置に語が1つ対応する。転置インデックスは語の並びであり、各語に1つ以上の出現位置が対応する。構造の話に戻ろう。転置インデックスには少なくとも語項辞書と転置リストが含まれる。機能セットによっては、位置データや語頻度データを伴うこともある。ここでいくつか検索を試して、クエリがインデックス内の各転置リストの文書IDをどう和集合や積集合にしているか見てみよう。

語項辞書

語項辞書は、全文書に現れるすべての語項を転置リストへ対応づける。ディスク上では通常、B木か、辞書順に並んだ別の構造になっている。クエリが来ると、システムはクエリ中のすべての語項を語項辞書で引く。ワイルドカードやあいまい一致を含むクエリでは、一致する正確な語項を探すために語項辞書の一部、あるいは全体を走査することがある。たとえば g* は gonna と give の両方を引き、u~2 は u と編集距離が2文字以内の語項すべて、つまり you と up を引く。上の図で試してみてほしい。

転置リスト

語項辞書の各語項は、転置リストと呼ばれる位置のリストを指す。この位置は何らかの文書識別子で、データベースや検索エンジンがテーブルやファイルストレージの中で該当する文書を見つけられるだけの情報を持つ。ほとんどの転置インデックスでは連番で、文書が10個のインデックスなら0から9（あるいは1から10）を使う。ただし、一意に定まる識別子なら何でもよい。データベースは値を、転置インデックスに加えたn番目の文書ではなく、ある行へ対応づける必要がある。そのため転置インデックスは、文書IDから行への対応表を別に持つか、行識別子をそのまま転置リストに格納する。転置リストはほぼ常に整列され、何らかの形で圧縮される。文書IDがすべて256未満なら、各IDは最大8ビットで収まる。リストが密な場合（つまり多くの文書がある語項を含む場合）、転置リストは数値間の差分だけを格納できる。id1、id2-id1、id3-id2、といった具合だ。この差分は常にIDそのものより小さいので、より少ないビットで格納できる。例を挙げよう。30万文書のインデックスがあり、そのうち10万文書が単語 "who" を含むとする。各IDをそのまま格納すると、転置項目1つあたり lg(n) = 19 ビット必要になる。しかし隣り合うIDの平均間隔は（転置リストは整列されていることを思い出そう）わずか3で、2ビットに収まる。転置項目が非常に密なら、転置リストはビットマップを格納できる。文書 n がある語を含むならビットマップの n ビット目が1、そうでなければ0だ。この符号化は n 文書に対してちょうど n ビットを使う。およそ半分の文書がある語項を含むとき、これが最適になる。整列済みの転置リスト2つの和集合や積集合は、O(n)の1回の走査で済むので速い。ビットマップとして格納された転置リスト2つの和集合や積集合は極めて速い。ベクトル命令を備えた現代のCPUなら、128、256、果ては512ビットの OR や AND を1命令で実行できるからだ。

位置データ

スパンクエリやフレーズクエリをサポートする検索エンジンもある。スパンクエリは、語項が文書中の特定の位置に現れること、あるいは互いの距離が一定以内であることを要求する。たとえば rules IN FIRST 5% や gotta NEAR/3 understand. だ。フレーズクエリはスパンクエリの特殊形で、語が正確な順序で現れることを要求する。スパンクエリやフレーズクエリを支えるため、転置インデックスは位置データを格納できる。転置リストが各語項の含まれる文書を記録するのに対し、位置データは語項が文書中のどこに現れるかを記録する。ほとんどのクエリはスパンクエリでも位置クエリでもないため、位置データは通常、転置リストとは別に格納され、必要になったときだけ読み込まれる。

語の頻度データ

文書をスコアリングして並べ替える機能を持つ検索エンジンがある。一般的なスコアリング手法のひとつである BM25（詳細は後述）は、インデックス対象の文書に関する統計情報を必要とする。各文書の長さ、文書の平均長、各語項 t が各文書 d に出現する回数、そして語項 t を含む文書の総数だ。インデックスはこれらのデータをあらかじめ計算しておき、クエリごとの結果をスコアリングする際に素早く参照できるようにする。

インデックスのサイズ

インデックス対象の文書全体の集合をコーパスと呼ぶ。インデックスのサイズは通常、コーパスサイズの何倍かになる。倍数はインデックスがどの機能をサポートするかによって変わる。位置情報やスコアリングデータを持たないインデックスなら、コーパスサイズのおよそ 20% に収まることもある。重複トークン（完全一致や正規表現検索を支えるために使う）と位置情報を持つコード検索インデックスは、コーパスサイズの 300% に達することがある。位置情報と語の頻度統計を持つ英文テキストのインデックスは、通常コーパスサイズの 30% から 50% の間だ。これらの数値は文書の長さや語彙数などで変わるが、機能ごとの相対的なコストを掴む目安にはなる。

トークナイザー

インデックス対象の文書は、どれもひと続きの長いテキストだ。このテキストを語項に分割する処理をトークナイズ（tokenizing）と呼ぶ。用途ごと、とりわけ言語ごとに適したトークナイザーは異なる。you're はひとつの語項か、それともふたつか？ {[] => []} に語項はあるのか？ Unicode は語の境界を識別するための妥当なデフォルト規則を定義している。トークナイズの後、検索エンジンは語項を転置インデックスに加える前に変更したり、まるごと省略したりすることがある。言語学的な接尾辞を落とす処理をステミング（stemming）と呼ぶ。たとえば strangers を stranger に、thinking を think に写像すれば、ユーザーはひとつの語でその語のあらゆる形を含む文書を検索できる。中には一般的すぎて検索にはほとんど役立たない語もあり、こうした語をストップワード（stop words）と呼び、多くの検索エンジンはそもそもインデックスしない。だが new をストップワードとして扱うインデックスは、York を含む文書と New York を含む文書を区別できない。the と who の両方を捨てるインデックスでは、The Who をそもそも検索できない。ストップワードはトレードオフだ。インデックスは小さく速くなるが、これらの語が本当に重要な場面では精度が落ちる。

スコアリング：BM25 と top-k

一致するすべての結果ではなく、少数の「最良の」結果だけを取得したい検索もある。これは SQL とは違う。SQL では SELECT LIMIT 10 が任意の十行を返すことを許す。どの結果が最良かを判断する方法はいくつもあるが、そのひとつが BM25 によるスコアリングだ。BM25 はひとつの式であり、与えられたクエリ中のすべての語項に対する答えとして、ある文書がどれだけ優れているかを評価する。語の頻度を表す関数（ある語項がその文書に出現する回数を文書長に対して見たもの）と、逆文書頻度を表す関数（その語項を少なくとも一度含む文書の割合）を掛け合わせ、そのスコアをクエリ中のすべての語項について足し合わせる。BM25 が体現する直感はこうだ。稀な語項ほど重要であり、ある語項を何度も言及する文書は、その語項にとってより良い結果である。スコアリングはほとんどの場合、SQL の LIMIT 10 のように、期待する結果の数とともに使われる。ここから重要な最適化が生まれる。転置リスト（postings list）はブロックに分割でき、各ブロックは語の頻度統計を持つ。インデックスがスコアの高い k 件の文書を探すとき——すなわち top-k クエリ——あるブロックの統計が、そのブロック内にインデックスがすでに見つけた上位 k 件を超えるスコアの文書は存在しないと示していれば、インデックスはそのブロックの転置項目をまるごと飛ばせる。これにより top-k クエリは大幅に速くなり、k が小さいときほど効果が顕著だ。

セグメント、マージ、可変性

転置インデックスを構築する最も単純な方法は、一度にすべてを作ることだ。インデックスが十分小さければ、完全にメモリ上で構築できる。何しろ転置インデックスは Map> にすぎない。メモリ容量を超えるインデックスはブロックごとに書き出す。インデックス作成を続けてメモリが埋まったら、最初の n 文書を表す自己完結した転置インデックスをディスクにダンプする。そして同じことを繰り返し、メモリが再び埋まったら次の n 文書に対応する自己完結した転置インデックスをディスクにダンプする、という具合だ。この自己完結した転置インデックスのそれぞれをセグメント（segment）と呼ぶ。クエリを処理するとき、インデックス全体はすべてのセグメントで一致を探し、その結果をマージしなければならない。もちろん、多くのデータセットは時間とともに変化する。コーパスは文書が加わるにつれて成長する。新しい文書はメモリ上にまとめて溜め、セグメントひとつ分になったら書き出してもよいし、ディスク上の可変データ構造に一件ずつ即座に加えてもよい。この可変ストレージのレイアウトは不変セグメントほど効率的ではないが、可変であるという利点がある。すべての文書をあらかじめ知らなくても、効率よく文書を追加できるのだ。以降のクエリでは、可変ストレージ内の文書がすべての不変セグメントとともに検索される。TIN は転置リストを含む可変セグメントをひとつ使い、これは不変セグメントの非効率版に相当する。可変セグメントは遅いので、やがて封止（sealed）して不変セグメントに変換しなければならない。以下のサンプルセグメントで挿入、更新、削除を試してみてほしい。話を単純にするため、サンプルは不変セグメントを最大二つまでしか表示しない。可変セグメントがサイズ上限に達すると、サンプルは即座にそれを小さいほうの不変セグメントへマージする。実際には、封止された可変セグメントはしばらく小型の独立した不変セグメントとして存在する。やがてセグメントの数が増えすぎる。何百、何千もの小さなセグメントを検索するインデックスは、すべてのセグメントを追跡しクエリ結果をマージするだけで相当な CPU とメモリを食う。そこで転置インデックスは通常、セグメントをマージ（merge）する必要がある。マージでは、二つ以上のセグメントがひとつの大きなセグメントになる。文書 ID がセグメントごとの局所的な連番なら、それらはすべて振り直さなければならない。あるセグメントの文書 i を別のセグメントの文書 i と混同してはならない。マージのアルゴリズムは単純で、語項辞書と各転置リストを一度線形に走査するだけでよい。だがマージには大量のディスク容量と大量の I/O が要る。マージは二つ以上の不変セグメントを入力にとり、すべての入力セグメントの合計から削除済み文書の転置項目を差し引いた大きさの、新しい出力セグメントを生む。各セグメントは容易に数 GB に達するので、一度のマージで数十 GB のデータを読み書きし、同じだけの追加ディスク容量を一時的に占めることもある。セグメントのマージは常にトレードオフだ。一方にマージの I/O コスト、他方に多数のセグメントを保持することによる効率の低下がある。だがこれは文書の挿入の場合にすぎない。文書の削除はどうか？転置リストの途中から文書 ID を削除するのは現実的でない。リストの一部、あるいは全部を再圧縮する必要が出てしまう。だから削除はトゥームストーン（tombstone）を作るだけだ。トゥームストーンは、ある文書 ID がもはや有効でないことを示すテーブル内のレコードだ。転置インデックスはその文書 ID をクエリ結果として依然として生み出すが、各結果をトゥームストーンと照合し、呼び出し元に返す前にその ID を取り除く。ここにもトレードオフがある。削除された文書はそれぞれインデックス内のディスク容量を依然として占め、CPU 時間を浪費する。転置リストから取り出し、結果リストから除外しなければならないからだ。そしてトゥームストーンを消す唯一の方法はセグメントをマージし、トゥームストーン一覧で出力セグメントに書き込む文書 ID を絞り込むことだ。セグメント内の大部分（半分近く）の文書が削除されている場合、削除済み文書を消すためだけにそのセグメントを単独で書き直す価値があることもある。文書の更新とは、その旧バージョンを削除（トゥームストーンを付与）し、新バージョンを挿入することにほかならない。ここで述べた不変セグメントでは、その場での更新はできない。

Postgres での実装

最後に、Postgres で転置インデックスによる全文検索がどのように実装されているかを見ていく。どうすれば動かせるのか。

CREATE INDEX ON songs USING tin(lyrics);
SELECT title, performer
 FROM songs
 WHERE lyrics ==> 'make you cry'
 ORDER BY tin.score(ctid) DESC
 LIMIT 10;

各ドキュメントは、ある行のテキスト列の値だ。つまり、テーブル songs の lyrics 列にインデックスを張るなら、曲ごとの歌詞が 1 ドキュメントになる。転置インデックスは行識別子、すなわち ctid を提供し、Postgres のエグゼキュータにどの 10 行を取ってくるべきかを伝えなければならない title performer。転置インデックス全体をどこかに置く必要があり、できれば WAL を記録するインデックスリレーションにしたい。そうすれば Postgres のレプリケーションとバックアップがそれを運んでくれる。セグメントが削除されると、それが占めていたストレージは解放されるが、リレーションの途中に空いた穴を OS に返すことはできない。インデックスは自分で空きページのリストを管理し、後で再利用するしかない。マージは通常、セグメントが一定のサイズ閾値を超えたとき、または tombstone リストがドキュメント総数の一定割合を超えたときに発火する。ただし INSERT、UPDATE、DELETE の中でインラインにマージを実行したくはない（忘れないように言っておくと、数十 GB の読み書きで数分かかることもある）。だからタスクキューとバックグラウンドのメンテナンス worker が要る。Postgres である以上、VACUUM が使えなければならない。VACUUM はヒープから死んだ行バージョンを取り除き、各インデックスにそれらを指すエントリの削除を要求する。VACUUM FULL はテーブル内のすべての行を書き換えるので、ctid が変わる。転置インデックスが ctid を保持しているなら、それに追随して更新する必要がある。ドキュメントの挿入と削除はトランザクション番号と結び付けなければならず、そうすればコミット前は他のトランザクションから見えず、ロールバックもできる。インデックスは可視の結果をすべて返し、不可視のものは一切返してはならない。この要件があっても、top-k クエリは実際に k 行を返さなければならない。COUNT(*) と top-k クエリを効率的に動かすには、転置インデックスが行レベルの可視性とページレベルの可視性マップにアクセスできる必要がある。クエリは転置インデックスによる全文条件（たとえば lyrics ==> 'make you cry'）と従来の SQL 条件（たとえば year = 1987）を組み合わせることがよくある。クエリプランナは、いつ全文インデックスを使い、いつ b-tree を使い、いつ両方を使ってビットマップ積集合で結果をマージすべきかを知る必要がある。複数の列に全文条件があるクエリ、たとえば title と lyrics では、CustomScan を使ってフィルタリングを完全にインデックス実装の内部で行うべきだ。これは列ごとに結果セットを 1 つずつ返して Postgres に積集合を取らせるよりはるかに速い。

Postgres にとっての最適解

これらの課題をどう解決し、どんな成果が得られたかは、TIN の詳細解説——PlanetScale が Postgres 向けに作った新しい全文検索拡張——を参照してほしい。