HN 日本語サマリー

← 一覧へ戻る
Web開発

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

ParadeDB Search Performance Improvements (paradedb.com)

65 pointsby craigkerstiens10 コメント

要約

PlanetScaleがPostgres用の全文検索拡張機能「TIN」をリリースし、ParadeDBのパフォーマンスを上回る結果を示しました。ParadeDBはこの結果を受け、パフォーマンス最適化に注力し、わずか2週間でTINのベンチマーク結果と同等以上のパフォーマンスを達成しました。この改善は、主にドキュメント識別子の違いではなく、コード内の最適化、特にフィールドノーム(Fieldnorms)のアクセス方法の変更や、ブロックマックス(Blockmax)のプルーニングアルゴリズムの選択によって実現されました。

全文翻訳

PlanetScaleがテキスト検索をリリース、我々が言いたいことは山ほどある(パートI)

[画像: Ming Yingのヘッドショット]

Ming Ying 著、2026年10月1日

[画像: テキスト検索、濃縮、BM25とカウントとラベルされたブリキ缶]

2週間前、PlanetScaleはPostgres向けのフルテキスト検索拡張機能であるTINを発表しました。彼らのローンチ投稿では、ParadeDBのテキスト検索機能の一部、特にBM25ランク付けされたテキスト検索とドキュメントカウントにおいて、印象的なパフォーマンスの勝利を報告していました。

PlanetScaleチームに賛辞を送りたいと思います1。他のPostgresプラットフォームが検索に投資しているのを見るのは素晴らしいことです(リレーショナルデータを検索したい人々がいることが判明しました)、そしてTINには多くの思慮深いエンジニアリングが注がれていることは明らかです。また、PlanetScaleがParadeDBのベンチマーカーツールを採用したことも喜ばしいです。これはまさにこのようなテストのために私たちが構築したものです。

一つのことを明確にしておきましょう。TINは高速です(PlanetScaleのすべてのベンチマークでParadeDB 0.25よりも少なくとも8倍高速です)。あまりにも高速だったため、取るべき唯一の対応は、黙ってパフォーマンス最適化の帽子をかぶることでした。2週間後、同じStackExchangeベンチマークデータセット、ハーネス、およびマシンタイプを使用して、BM25ランク付けの最適化前後の結果を以下に示します(TINはオープンソースではないため、PlanetScale上で実行されています)2:

StackExchange トップK検索
150M ドキュメント · 8 同時クライアント · 5分間実行

クエリ
表示
パーセンタイル
↑ 高いほど良い

ウォームキャッシュ、読み取り専用実行。TINは dense_ratio=2 を使用し、検索エリジョンは無効になっています。詳細は共通語の処理を参照してください。1秒バケット。レイテンシは最近接ランクパーセンタイルを使用します。線は中心9秒移動平均を使用します。凡例の値は平滑化されていないフルラン結果です。

興味深いのは、私たちがすぐにギャップを埋めたことではなく、どのように埋めたかです。TINの投稿では、そのパフォーマンスはPostgresの内部 ctid フィールドをドキュメント識別子として使用する根本的なアーキテクチャの違いによるものだと主張しています。しかし、私たちは、ドキュメントの識別方法とはほとんど関係のないいくつかの最適化パスを通じて、このギャップを埋めました。また、完全に公平な比較を提供しないベンチマーク設定も調整しました。これについては後述します。

修正点と設定変更を一つずつ見ていきましょう。

テキスト検索の概要とTINが高速であると主張する理由

テキストインデックスなし

シーケンシャルスキャンは、各ドキュメントを順番にチェックし、ドキュメントID 2と4を見つけます。

テキストインデックスあり

テキストインデックスは、データベースの投稿リストに直接ジャンプし、ドキュメントID 2と4を返します。
データベース
2
4

あらゆるテキスト検索インデックスの中心は投稿リストです。これは、その用語を含むドキュメント識別子のリストです。例えば、インデックスにドキュメント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スコアによるトップKマッチと、一致するドキュメントの COUNT クエリという2つの広範なクエリタイプをベンチマークしています。

カウントの場合、ctid の引数は理にかなっていました。数百万件の一致が可視性チェックを必要とする場合、DocId 値を ctid 値に変換するのに時間がかかります。Postgresページを中心に投稿を整理することで、より少ないデータを読み込み、その作業をバッチ処理する機会が生まれます。

BM25トップKクエリについては、懐疑的でした。ParadeDBは、最終的なトップKドキュメントが集まるまで ctid のルックアップを延期します。トップ10クエリの場合、それは10回のルックアップを意味します。これらのルックアップは無料ではありませんが、プロファイルではごくわずかであり、桁違いのギャップを説明するものではありません。

代わりに、コードの他の部分のさまざまな最適化機会でギャップを埋めることができると疑っていました。

この投稿では、トップK BM25の最適化に焦点を当てます。また、パートIIで説明する COUNT も最適化しました。

最適化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には、ページアクセスをそのページに格納されているデータ構造に帰属させる新しい機能があります。それはすぐに問題があることを示しました。

データ構造ページアクセスの割合
Fieldnorms1,513 (83%)
その他すべて(投稿、メタデータなど)311 (17%)

「Fieldnorms」は、BM25がスコアを正規化するために使用するドキュメントのインデックス付きフィールドの長さをエンコードします。Tantivyにおけるフィールドノルムは非常に小さいです。単一バイトの fieldnorm_id 値に量子化されたドキュメント長です。なぜ小さいものがそれほど多くの読み込みを占めることができるのでしょうか?

問題は局所性でした。Tantivyはフィールドノルムを投稿リストとは別に、DocId でインデックスされた配列に格納します。用語の投稿リストの読み取りはシーケンシャルですが、対応するフィールドノルムの取得は、その配列全体を飛び回る可能性があります。Tantivyの通常のメモリマップドストレージでは、このレイアウトは問題ないでしょう3。各常駐フィールドノルムは安価なメモリールックアップであるためですが、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:適切なBlockmaxプルーニングアルゴリズムの選択

フィールドノルムの分離は、用語数が少ないクエリで大幅な高速化をもたらしましたが、多くの用語を含むディスジャンクションクエリのパフォーマンスにはまだ満足していませんでした。例えば、このクエリはこれらの用語のいずれかを含むドキュメントに一致します。

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%しか低下しなかったことに気づきました。これは、このケースのボトルネックがアルゴリズムであることを示唆しています。

プロファイリングを行った結果、ほとんどの時間がBlockmax WANDループと呼ばれるものに費やされていることが判明しました。

背景として:Blockmaxは、検索エンジンがディスジャンクション(例:termA OR termB)クエリを実行する際に、投稿リストのチャンクを効率的にスキップするために使用する標準的なアルゴリズムです。BlockmaxにはWANDとMAXSCOREの2つのファミリーがあります。それらがどのように機能するかの詳細には立ち入りません(このための優れた技術ブログがたくさんあります)が、大まかに言うと:

  • 「Blockmax」とは、投稿リストをブロックに分割し、各ブロックについて、そのブロックのどの用語も最終的なBM25スコアに貢献できる最大スコアを事前計算して格納できるという事実から来ています。
  • ブロックはその最大スコアが現在のトップKしきい値を上回る可能性がない場合にスキップされます。WANDとMAXSCOREは、このスキップを行う2つの異なる方法です。

WANDとMAXSCOREのトレードオフは、スキップする作業の量です。WANDはより多くスキップしますが、それを行うためにCPUサイクルをより多く費やします。MAXSCOREはより少なくスキップしますが、オーバーヘッドは少なくなります。クエリに用語が多く含まれるほど、WANDのオーバーヘッドが増加し、スキップした作業のメリットを上回ることがあります。
TantivyはWANDを使用しています。Luceneも2023年までWANDを使用していましたが、特定のクエリに対してMAXSCOREを導入しました。現在、Luceneはクエリの形状に応じて動的にWANDまたはMAXSCOREを選択します。

私たちは、単純な選択ヒューリスティックを備えたMAXSCOREパスを実装しました。これは、3つ以上の用語と十分に密な投稿リストを持つディスジャンクションにはMAXSCOREを使用し、それ以外の場合はWANDを使用します。上記の10個の用語を含むクエリでは、p50レイテンシを約6倍、p95を約8倍に短縮しただけでなく、28.7MのHNデータセットでTINよりも2倍高速になりました。

Hacker News トップK検索
28.7M ドキュメント · 8 同時クライアント · 5分間実行

結果
用語
一致
表示
パーセンタイル
↑ 高いほど良い

ウォームキャッシュ、読み取り専用実行。TINは dense_ratio=0.1 を使用し、検索エリジョンが有効になっています。詳細は共通語の処理を参照してください。1秒バケット。レイテンシは最近接ランクパーセンタイルを使用します。マッチセレクタは1単語クエリには適用されません。線は中心9秒移動平均を使用します。凡例の値は平滑化されていないフルラン結果です。

ベンチマーク設定の変更

PlanetScaleのベンチマークは公正に構築されていましたが、TINを意図せず有利にした2つの例外がありました。それはParadeDBの構文の誤りと、TINが共通語を処理する方法です。

ParadeDBの構文

TINのベンチマークではParadeDBのクエリ文字列パーサーが使用されており、これは @@@ 演算子を介してTantivyのミニクエリ言語を受け入れます。問題は、これらのクエリがフィールド名で修飾されていなかったことです。例:<query> の代わりに <field>:<query>。

クエリが修飾されていない場合、ParadeDBはデフォルトでインデックス化されたすべてのテキストフィールドを検索します。StackExchangeデータセットでは、id と body の両方の列がインデックス化されていたため、ParadeDBはクエリごとに2つの列を検索していたのに対し、TINは1つしか検索していなかったため不利でした。

これを防ぐために、すべてのParadeDBクエリをネイティブの |||(ディスジャンクション)、&&&(コンジャンクション)、および ###(フレーズ)演算子を使用するように変更しました。

共通語の処理

HNベンチマークではBM25検索クエリでTINを容易に上回っていましたが、PlanetScaleのStackExchangeデータセットとクエリをロードしたところ、テールレイテンシが長かったため、スループットで30%遅れていました。なぜ私たちのベンチマークでは数倍高速なのに、PlanetScaleのベンチマークでは遅いのでしょうか?

TINが「dense-term elision」と呼ぶ、共通語に対するスコアリングのショートカットが原因であることが判明しました。そして、特にStackExchangeデータセットでのその使用は議論の余地があると考えています。

簡単な説明:'the' や 'is' のような共通語は、膨大な投稿リストを持ち、読み取りとスコアリングにコストがかかります。しかし、BM25はそれらに非常に低い重みを与えるため、最終的なランキングをほとんど動かしません。ほとんどの検索エンジンは、インデックス作成時にストップワード辞書でこれを処理します(両方のエンジンがこれをサポートしていますが、ベンチマークでは有効になっていませんでした)。TINは異なるアプローチを取ります。クエリ時に、コーパスの10%以上に現れる用語のスコアリングをスキップします(dense_ratio で設定可能)。これは検索実務家の観点からTINの最も興味深いアイデアであり、これについてはさらに時間をかけて検討する予定です。

もちろん、常にトレードオフがあり、ここでは正確性です。エリジョンがオンの場合、TINは共通語を無視することでBM25の近似値を計算し、結果が真のBM25とは異なる順序で返される可能性があります。これはほとんどの実際のクエリでは問題になりませんが、クエリが共通語のみで構成されている場合は例外です。

Stack Exchangeベンチマークが実行していたものを調べたところ、これらの共通語で構成されたクエリ全体が見つかりました。これは、Stack Exchangeコーパスから連続した単語の範囲をサンプリングして生成されたため、「is it」、「to a」、「is to」のようなクエリが生成されたからです4。ParadeDBとTINの間の最大のレイテンシギャップをランク付けしたところ、それらの同じクエリ(実際の検索クエリではない)がリストを支配しました。それらでは、TINはほとんどのスコアリング作業をスキップしましたが、ParadeDBは正確なスコアを計算しました。

TINでは、エリジョンが有効な場合、以下のことが判明しました5:

  1. クエリの47.8%で、少なくとも1つの結果が「真の」トップ10以外の結果としてトップ10内に返されました。
  2. クエリの6.4%で、トップ10の結果が「真の」トップ10内に含まれていない結果が返されました。つまり、すべての結果が間違っていました。
  3. ディスジャンクションは特に不正確でした。ディスジャンクションクエリの88.2%で、少なくとも1つの非トップ10結果がトップ10内に現れました。
TINクエリスタイル「真の」トップ10外の結果が少なくとも1つ含まれる
コンジャンクション39.9%
ディスジャンクション88.2%
フレーズ13.8%
全体47.8%

明確にしておきますが、「正確なBM25と異なる」ことが自動的に「悪い」ことを意味するとは言っていません。エリジョンされた用語は設計上低い重みを持っており、エリジョンされた結果が関連性が低いかどうかを判断するには人間の関連性判断が必要ですが、このベンチマークにはそれはありません。しかし、ワークロードはBM25トップK検索としてフレーム化されており、エリジョンが有効な場合、TINとParadeDBは同じランキングを計算していません。

この理由から、私たちのヘッドライン比較では、両方のエンジンで正確なBM25を使用し、TINは dense_ratio=2 で設定されています。以下に、TINのデフォルトのエリジョン有効設定も示します。これにより彼らは私たちを「上回って」いますが、それが元のベンチマークで使用されたものです。

読者が独自の結論を導き出せるように、両方の結果セットを共有しています。ベンチマーク設定がParadeDBに行ったパフォーマンス改善の妨げになることは望んでいません。同時に、それらが元々公開された結果に大きな違いをもたらすため、言及しないわけにはいきません。念のため、ストップワードを有効にしたParadeDBも含まれています。

TIN dense_ratio比較
150M ドキュメント · ミックスドトップK · 8 同時クライアント · 5分間実行

表示
パーセンタイル
↑ 高いほど良い

ウォームキャッシュ、ミックスドクエリ実行。1秒バケット。レイテンシは最近接ランクパーセンタイルを使用します。線は中心9秒移動平均を使用します。凡例の値は平滑化されていないフルラン結果です。

それでは、優れたドキュメント識別子は存在するのか?

TINの投稿では、パフォーマンス上の優位性は DocId 値ではなく ctid 値を使用することに起因すると主張しています。しかし、私たちはドキュメント識別子を変更せずにギャップを埋めました。

  1. 局所性の高い、より密なデータ構造を作成した。
  2. スループットの高いBlockmaxアルゴリズムを使用した。
  3. その他のいくつかの小さな最適化(他のデータの遅延読み込みに関連するもの)。

これらの変更のほとんどは、私たちの検索ライブラリであるTantivyで行われました。

過去数年間、ParadeDBにとってTantivyを基盤とすることが正しい選択だったのか、それともTINのアプローチのように新しい検索エンジンをゼロから構築するのか、しばしば議論してきました。この調査は、Tantivyを使用するという私たちの決定への信念を強化しました。それは10年以上の開発、世界最大級の企業による実戦テスト、そして驚異的なスピードをもたらします。Tantivyは必ずしもPostgresのブロックレイアウトにすぐに適合するわけではありませんが、その拡張性と機能はそれを補って余りあります。

なぜこれらの最適化をまだ行っていなかったのか、と疑問に思うかもしれません。パフォーマンス作業は終わりがなく、エンジニアリングリソースは有限です。テキスト検索ベンチマークでElasticsearchと同等の性能を達成した後、私たちはParadeDBの機能を「テキスト検索だけ」から、複雑なフィルター、ファセット、結合を含む検索クエリを効率的に実行することへと拡大することに注力しました。今では私たちの検索APIは非常に広範なので、TINがこのコア最適化の機会に私たちの注意を向けさせてくれたことを嬉しく思います。

終わりに

オープンソースの検索コミュニティには、長年の協力の伝統があります。例えば、競合する検索ライブラリであるにもかかわらず、LuceneとTantivyは頻繁にアイデアを共有し、友好的に互いをベンチマークしています。私たちは、これが両方のプロジェクトにどのように利益をもたらすかを、Tantivyの作者Paul Masurelとの対談で探りました。これがそのもう一つの例となることを願っています。私たちにとって、これは楽しいスプリントでした。

TINの著者がプロジェクト自体はオープンソースではないものの、エンジニアリング上の決定の一部をブログで共有してくれたことに感謝しています。私たちのすべての作業はオープンであり、このスパイクからの関連する改善をすでにTantivyにアップストリームし始めています。

これらの結果が再現可能であることを示すために、0.26.0-rc.2 リリース候補をカットしました。既存のParadeDBユーザーの場合、これらの改善は次の安定リリースである0.26.0(来週予定)に折り込まれます。これらの変更は後方互換性があることを確認しましたが、すべての最適化を引き継ぐには再インデックスが必要です。

コミュニティの貢献者の皆様へ:この調査は時間制限があり、特に効率的なBlockmaxプルーニングとバッファアクセス削減の方向で、さらに多くの最適化の糸口があると考えています。パフォーマンスのフロンティアをさらに押し広げるあらゆる貢献を歓迎します。

パートII:COUNTとその他の検索を本当に高速にする方法では、COUNT パフォーマンスに関する最適化について議論します(ヒント:これらもドキュメント識別子を変更する必要はありませんでした)。検索を楽しんでください!Postgresと検索コミュニティに、より高速なテキストクエリを提供できることを楽しみにしています。


フットノート

  1. 特に、かつてParadeDBに勤務し、PlanetScale TIN製品を推進したEric ZomboDBに感謝します。↩
  2. あるいは、可能な限り近づけました。TINはオープンソースではないため、8 CPU / 32 GB / NVMeインスタンスを使用してPlanetScaleのクラウド上で実行する必要がありました。ParadeDBは、同じEC2ファミリーの同様のサイズのマシンに、Dockerコンテナでデプロイされました。ParadeDBはネットワークレイテンシが約1ミリ秒少なかったです。PlanetScaleのベンチマークと同じ設定を使用しましたが、ParadeDBのバージョン、ParadeDBのインデックス作成フラグ、およびTINの dense_ratio 設定のみを変更しました(これについては投稿で詳しく説明します)。ベンチマークの実行にはPlanetScaleのbenchmarkerフォークを使用しましたが、機能を私たち自身のものにプルバックする予定です。↩
  3. OSレベルで4KBページを使用するMMAPでも問題ない可能性もあります。↩
  4. 私たちのHNデータセットは、興味深い単語のリストからのみ単語を組み合わせているため、この問題の影響を受けません。これも問題がありますが、ゴールドスタンダードは、人々が実際にタイプしたもののリストを含む、ドメイン固有のコーパスです。↩
  5. これらの測定値は、dense_ratio を 0.1 に設定した場合と 2(無効)に設定した場合のTINによって生成された結果を比較することによって得られました。「真の」トップ10は、TINがdense-termエリジョンなしで生成した結果として定義し、それらの結果が正しいと仮定します。↩