ParadeDBの検索パフォーマンス改善

PlanetScaleがテキスト検索をリリースし、我々には言うべきことがたくさんある（パートI） ミング・イン著 2026年10月1日 2週間前、PlanetScaleはPostgres用の全文検索拡張機能であるTINを発表しました。彼らのローンチ投稿では、ParadeDBのテキスト検索機能の一部、特にBM25ランク付けされたテキスト検索とドキュメント数において、印象的なパフォーマンスの勝利を報告しました。 PlanetScaleチームに称賛を送りたいと思います。 検索に投資する別のPostgresプラットフォームが登場するのは素晴らしいことです（リレーショナルデータを検索したい人がいることが判明しました）。そして、TINに多くの思慮深いエンジニアリングが注がれたことは明らかです。 また、PlanetScaleがParadeDBのベンチマーカーツールを採用したことも嬉しく思います。このツールは、まさにこのような種類のテストのために私たちが構築したものです。 一つのことを非常に明確にしましょう：TINは高速です（PlanetScaleの全てのベンチマークでParadeDB 0.25よりも少なくとも8倍高速です）。あまりにも高速だったので、唯一の適切な対応は、黙ってパフォーマンス最適化の帽子をかぶることでした。 2週間後、同じStackExchangeベンチマークデータセット、ハーネス、およびマシンタイプを使用して、BM25ランク付けの最適化前後の結果を示します（TINはオープンソースではないため、PlanetScale上で実行されています）。 StackExchange Top K検索 1億5000万ドキュメント · 8同時クライアント · 5分実行 クエリ 混合 接続詞 分離詞 フレーズ ビュー スループット レイテンシ パーセンタイル P50 P90 P95 P99 ParadeDB 81.9 QPS TIN 33 QPS ↑ 高いほど良い ウォームキャッシュ、読み取り専用実行。 TINはdense_ratio=2、search elision無効を使用しています（「Handling Common Terms」を参照）。 1秒バケット；レイテンシは最近接ランクパーセンタイルを使用。 線は中心9秒移動平均を使用；凡例の値は平滑化されていないフルラン結果です。 興味深いのは、私たちがすぐに差を縮めたことではなく、どのように縮めたかです。 TINの投稿では、そのパフォーマンスは、Postgresの内部ctidフィールドをドキュメント識別子として使用するという根本的なアーキテクチャの違いによるものだと主張しています。しかし、私たちは、ドキュメントの識別方法とはほとんど関係のないいくつかの最適化パスを通じて、この差を縮めました。 また、ベンチマーク設定をいくつか調整しましたが、これは完全には公平な比較ではありませんでした。これについては後で詳しく説明します。 修正点と設定変更を一つずつ見ていきましょう。 テキスト検索の概要とTINがテキストインデックスなしで高速であると主張する方法 シーケンシャルスキャンは、各ドキュメントを順番にチェックし、ドキュメントID 2と4を見つけます。 … テキストインデックス付き テキストインデックスは、データベースの投稿リストに直接ジャンプし、ドキュメントID 2と4を返します。 database24… テキスト検索インデックスの核心は、投稿リストです。これは、その用語を含むドキュメント識別子の、用語ごとのリストです。例えば、インデックスにドキュメント1から10まであり、「database」という単語がドキュメント2と4に出現した場合、「database」の投稿リストは単に[2, 4]となります。 投稿リストにより、特定の用語に一致するドキュメントを非常に効率的に識別できます。 Tantivy、ParadeDBの背後にある検索ライブラリは、投稿リストにシーケンシャルなu32ドキュメントIDを使用します。これらの識別子はTantivyの内部のものであり、挿入順序のみに基づいて割り当てられます。 この記事の残りの部分では、DocIdはTantivyとParadeDBが使用するu32ドキュメント識別子を指します。 Postgresは、ctid値でその行を識別します。ctidは、Postgresのブロックベースストレージ内の行の物理的な場所を示すタプルです。(190, 17)は、ブロック190のスロット17に現在見つかっている行を識別します。 ParadeDBはTantivyによって駆動されるPostgresインデックスであるため、DocIdとctid値の間にはマッピングが存在する必要があります。 TINの投稿の核心は、ctid値をドキュメント識別子として直接使用することで、このマッピングが不要になり、効率的なビットマップ操作と可視性チェックが可能になるということです。 PlanetScaleは、TINのパフォーマンス上の利点の多くを、その選択による下流のメリットに帰しています。 しかし、すべては異なるドキュメント識別子に関するものか？ ローンチ投稿では、BM25スコアによるTop Kマッチと、一致するドキュメントのCOUNTクエリという2つの広範なクエリタイプをベンチマークしています。 カウントの場合、ctidの議論は理にかなっていました。数百万の検索結果で可視性チェックが必要な場合、DocId値をctid値に変換すると時間がかかります。 Postgresページを中心に投稿を整理することで、より少ないデータを読み込み、その作業をバッチ処理する機会が生まれます。 BM25 Top Kクエリについては、懐疑的でした。 ParadeDBは、最終的なTop Kドキュメントが集まるまでctidルックアップを延期します。トップ10クエリの場合、それは10回のルックアップを意味します。 これらのルックアップは無料ではありませんが、プロファイルではごくわずかであり、桁違いの差を説明するものではありません。 代わりに、コードの他の場所にある様々な最適化の機会で差を縮めることができると疑っていました。 この記事は、Top K BM25の最適化に焦点を当てています。 COUNTも最適化しましたが、これはパートIIで説明します。 最適化1：BM25スコアリング中のランダムアクセス削減 単純なクエリから始めました：単一の用語を含む最も関連性の高い10件のドキュメントをBM25スコアで並べ替えて取得する。 ローカルでの迅速なイテレーションのために、より小さな28.7MのHacker Newsデータセットを使用しました。 EXPLAIN (ANALYZE, BUFFERS) SELECT id, title, by FROM hn_items WHERE title === 'database' ORDER BY pdb.score(id) DESC LIMIT 10; TINはこのクエリでParadeDBよりもはるかに少ないPostgresページにアクセスしたため、それが主な理由だと推測しました。 StackExchangeデータセットで、ディスクから読み取る場合、これはさらに累積します。 ParadeDBには、データ構造が格納されているページへのページアクセスを属性付ける新しい機能があります。それはすぐに問題があることを示しました。 データ構造 ページアクセスの割合 Fieldnorms 1,513 (83%) その他（投稿、メタデータなど） 311 (17%) 「Fieldnorms」は、BM25がスコアを正規化するために使用するドキュメントのフィールド長をエンコードします。 Tantivyのフィールドノームは非常に小さいです：ドキュメント長は1バイトのfieldnorm_id値に量子化されます。 なぜこんなに小さいものがそれほど多くの読み込みを引き起こすのでしょうか？ 問題は局所性でした。 Tantivyはフィールドノームを投稿リストとは別に、DocIdでインデックス付けされた配列に格納します。 用語の投稿リストの読み取りはシーケンシャルですが、対応するフィールドノームの取得は、その配列全体を飛び回る可能性があります。 Tantivyの通常のメモリマップドストレージでは、このレイアウトは問題ないでしょう。各常駐フィールドノームは安価なメモリールックアップであるためですが、Postgresでは、このクエリのために約1,500の異なるフィールドノームページにアクセスする必要がありました。 私たちの修正は、各投稿リストの隣に、投稿のDocId値と同じ順序でフィールドノーム配列を格納することでした。 これにより、スコアリングは投稿と並行してフィールドノームをシーケンシャルに読み取ることができ、散発的なルックアップを排除しました。 この変更後、フィールドノームアクセスは1,500ページからわずか30ページに減少しました（！）。 前：共有フィールドノーム配列 投稿リスト フィールドノーム 「database」：[DocId値] [全ドキュメントのフィールドノームID] 「rust」：[DocId値] ... 後：用語ごとのフィールドノーム配列 投稿リスト フィールドノーム 「database」：[DocId値] 「database」：[フィールドノームID] 「rust」：[DocId値] 「rust」：[フィールドノームID] ... ... トレードオフはストレージです。なぜなら、ドキュメントのフィールドノームは、それが含む各用語に対して繰り返されることになるからです。 幸いなことに、これは必ずしもフィールドノームストレージを用語数で乗算することを意味しません。 実際のコーパスでは、ほとんどの用語は短い投稿リストを持ち、それに応じて小さいフィールドノーム配列を持ちます。 例えば、この変更により28.7MのHNインデックスは約9%増加しました。 最適化2：適切なブロックマックスプルーニングアルゴリズムの選択 フィールドノームを分離したことで、用語数が少ないクエリの速度が大幅に向上しましたが、用語数が多い分離クエリのパフォーマンスにはまだ満足していませんでした。 例えば、このクエリはこれらの用語のいずれかを含むドキュメントに一致します。 EXPLAIN (ANALYZE, BUFFERS) SELECT id, title, by FROM hn_items WHERE text ||| 'rust arc clone memory safety borrow checker ownership lifetime rules' ORDER BY pdb.score(id) DESC LIMIT 10; このクエリでは、前の最適化の後でバッファ読み取りが約80%減少したにもかかわらず、クエリ時間はわずか5%しか減少しませんでした。これは、このケースのボトルネックがアルゴリズム的であったことを示唆しています。 プロファイリングした結果、時間のほとんどがブロックマックスWANDループと呼ばれるものに費やされていることが判明しました。 背景として：ブロックマックスは、検索エンジンが効率的にスキップするために使用する標準的なアルゴリズムです。