PostgresのCOUNT問題を解決する

COUNTとその他の検索を非常に高速にする（パートII）

［画像: Ming Yingのヘッドショット］

Ming Ying著 2026年10月13日

［画像: 開いた缶からText Search, Condensed, BM25とカウントのラベルが付いたSpaghettiOsが飛び出している］

パートIでは、ParadeDBのTop K BM25パフォーマンスを桁違いに改善しました。最後に、COUNTに焦点を当てたパートIIを公開することを約束しました。この記事では、COUNTクエリを大幅に高速化した最適化について説明します。元のTIN投稿と同じWikipediaデータセットとベンチマークハーネスを使用した、最終結果は次のとおりです。

Wikipedia COUNT検索
8並列クライアント · 5分間の実行

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

テーブルをクリーンアップ。各ワーカーの順序付けられた生クエリタイミングと測定された開始/終了間隔から再構築された1秒バケット。レイテンシは連続パーセンタイルを使用します。線は中心9秒移動平均を使用します。凡例の値は平滑化されていないフルラン結果です。

まず、COUNTパフォーマンスをどのように改善したかを説明します。後半では、フィルタリングされていないBM25と単純なCOUNTクエリを超えて、さまざまなフィルタとソート順序を持つ検索クエリをテストします。ここではParadeDBは最大66倍高速です。その理由を説明し、ベンチマークを比較する際やアプリケーションの検索エンジンを選択する際にこれらの違いが何を意味するかを議論します。

しかし、まずCOUNTを高速化することから始めましょう！

最適化1：セグメントパーティショニング

以下は、私たちが開始した単純なクエリです：databaseという用語に一致するドキュメントの数をカウントします。

EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*)
FROM hn_items
WHERE text === 'database';

プロファイリング中に、可視性チェックがページアクセスの80%以上を占めていることがわかりました。これは、一致するたびにそのctid値（TINはドキュメントインデックスがctidであるためスキップできます）を取得してデコードする必要があるため、理にかなっています。

クエリを見ているうちに、私たちが取り組んできた（後日発表される）新機能であるセグメントパーティショニングを使用できることに気づきました。

ParadeDBとTINはどちらも、LSMツリーに似た構造にデータを格納しています。大まかに言うと、データは不変のセグメントにパーティション分割され、サイズしきい値に達するとマージされます。小さなセグメントは、十分なデータが集まって次のサイズティアに達すると結合されます。単純なナイーブマージ戦略は、セグメントに含まれるデータを無視するため、各セグメントがデータセットのランダムなサンプルを効果的に含んでいると仮定できます。

Spooky LSMコンパクション論文に基づいた新しいセグメントパーティショニングおよびマージ戦略により、1つ以上の列の値でセグメントを分割できます。私たちはこれを数ヶ月かけて構築しており、近日中に技術的な詳細を共有します（Top Kおよび結合で見られるメリットは非常に大きいです）。このクエリの目的のために、有用な部分はctid（Postgresの内部行識別子）でパーティション分割できることです。これにより、各セグメントはPostgresページ番号の分離された範囲を持つことになります1：

パーティショニングなし（重複する最小/最大ページ範囲）：

Postgresページ：  0----------2999  0----------2999  0----------2999
                 [ セグメントA ]    [ セグメントB ]    [ セグメントC ]

パーティショニングあり（分離されたページ範囲）：

Postgresページ：  0-----------999  1000-------1999  2000-------2999
                 [ セグメントA ]    [ セグメントB ]    [ セグメントC ]

各セグメントは既に最小および最大ctidを格納しています。このレイアウトでは、可視性マップを事前にチェックできます。範囲内のすべてのページがall-visibleとマークされている場合、そのセグメント全体の可視性チェック（および可視性関連のすべてのページ読み取り）をスキップできます。

純粋なサイズ階層コンパクションでは、これらのctid最小/最大範囲はテーブルの大部分をカバーする可能性があります。更新された単一ページは、ほとんどのセグメントのショートカットを無効にする可能性があります。ctidでパーティション分割すると、その影響は影響を受けたページをカバーするセグメントに限定されるため、他のセグメントは行ごとのチェックをスキップし続けることができます。

私たちのベンチマーククエリでは、これにより可視性関連のページアクセスが1,382からわずか30に削減されました。

最適化2：DocIdマップの反転

しかし、セグメントのctid範囲の少なくとも1ページが可視性チェックを必要とする場合はどうでしょうか？これは、最後の（自動）バキュームから時間が経つほど可能性が高くなり、少数の変更されたページがすべてのマッチに対してctid読み取りを強制することを望みません。

TINのブログでは、DocIdをctid値に変換する必要があることによるオーバーヘッドについて説明しており、それは真実です。しかし、それが言及していないのは、DocIdからctidへのマップがいかに効率的であるかということです。

既存のアプローチでは、すべてのドキュメントに対してctidを格納し、一致するたびにそれを取得します。n個の一致をカウントすることは、n回のctidルックアップを意味しました。

  Doc ID:    0       1       2       3       4       5       6
  CTID:    (10,1)  (10,2)  (11,1)  (11,2)  (11,3)  (15,1)  (15,2)

はるかに効率的な表現は、マップを実質的に反転することです：Postgresページ番号（つまり、ctidタプルの最初の数値）をそのページで見つかった最初のDocIdにマッピングする圧縮された列です。これは、セグメントが既にctidでソートされているため、同じページ上のドキュメントが連続したDocIdを持つことを保証するため機能します。

後：ページごとにインデックス付けされたドキュメント境界

  Heap page:      10  11  12  13  14  15  end
  Starting DocId:  0   2   -   -   -   5    7

  Page 11 --> doc IDs [2, 5)

この新しい形式では、可視性マップを事前にチェックし、チェックが必要なページに対してのみドキュメント範囲を検索できます。

  チェックが必要なページ：   11
  チェックが必要なDocIDs： [2, 5)
  クエリマッチ：         [0, 3, 6]
                             |
                             v
                    DocIds 2, 5) のみ CTID ルックアップを実行 -> Doc 3

上記の単一用語カウントクエリでは、1,000行を更新した後、バッファアクセスが7,500以上からわずか400未満に削減されました。これは95%の削減です。

最適化3：ビットマップは一般的な用語に最適

Tantivyは、ポスティングリストにBP128エンコーディングを使用しています。BP128とは、ポスティング配列が128個のブロックに分割され、各ブロックはビットパックされデルタエンコードされていることを意味します。これらのブロックは、blockmaxアルゴリズムがBM25ランキング中に競争力のないブロックをスキップできるようにするスコア境界も保持しています。

プロファイリング中に、この表現はほとんどの用語でうまく機能することがわかりましたが、非常に一般的な用語で、密なポスティングリストを持つものは例外でした。これらの一般的な用語の場合、大きなBP128配列の交差または和集合はかなりのオーバーヘッドを発生させ、ポスティングをビットマップとして表現すると、それらの和集合と交差がはるかに安価になることがわかりました。

ドキュメントID： [1, 3, 4, 7]

ビットマップ：各ドキュメントIDに1ビット

  Doc ID:   0 1 2 3 4 5 6 7
  Bit:      0 1 0 1 1 0 0 1

BP128：ドキュメントID間のギャップを格納し、その後ビットパック

  Doc IDs:     1     3     4     7
  Gaps:        1     2     1     3
  バイナリで：  01    10    01    11
              └── 2ビット/ギャップ ──┘

2番目のブロックは129番目のポスティングから始まります。

BP128とビットマップのトレードオフを示すために、2つのシナリオを考えます。まず、それぞれ100万ドキュメントのうち10件に一致する2つのまれな用語があると想像してください。それらのBP128エンコードされた配列を交差させるには、わずかな比較で済みますが、同等のビットマップを2つスキャンするには、それぞれ100万ビットを処理する必要があります。そのほとんどはゼロ（つまり無駄な作業）です。

次に、それらの用語が一般的で、それぞれ100万ドキュメントのうち約50万件に一致すると想像してください。つまり、配列はそれぞれ約50万エントリになります。この場合、ビット単位のAND/ORは一度に64ドキュメントを処理できるため、ビットマップの方が効率的です。一方、配列を一度に1つのエントリずつウォークします。

ドキュメントの10%以上（約100万ドキュメントのうち10万件）に一致する十分に密な用語に対して、ポスティングのビットマップ表現を導入しました。この変更だけでも、Wikipediaカウントベンチマークでのp99レイテンシが半分になりました。

さて、検索の残りは

TINは、最適化されたクエリ形状（BM25によるTop Kとカウント）では非常に高速です。ParadeDBはPostgres上のElasticsearchの代替となることを目指しており、その観点から見ると、BM25とカウントは、本番環境で実行されるクエリの氷山の一角にすぎません。

例えば、Hacker Newsデータセットに対する次の検索クエリを考えてみましょう。

1. フィルタリングされたカウント

「database」という用語を含み、かつ10ポイント以上のHacker Newsポイントを獲得した投稿はいくつありますか？

SELECT COUNT(*)
FROM hn_items
WHERE text ||| 'database'
  AND score > 10;

ParadeDBはTINの78 QPSに対して777 QPSを維持しました。これは10.0倍のスループット差です。

Hacker News COUNT、スコアフィルタ付き
8並列クライアント · 5分間のターゲット

ビュー
パーセンタイル
↑ 高いほど良い

テーブルをクリーンアップ。各ワーカーの順序付けられた生クエリタイミングと測定された開始/終了間隔から再構築された1秒バケット。フルランの凡例値には、バッチ完了オーバーランが含まれます。線は中心9秒移動平均を使用します。凡例の値は平滑化されていないフルラン結果です。

2. BM25関連性によるフィルタリングされたTop K

「database」という用語を含み、かつ10ポイント以上のHacker Newsポイントを獲得した、最も関連性の高い投稿Top 10を教えてください。

SELECT id, text, "by", score, pdb.score(id) AS relevance
FROM hn_items
WHERE text ||| 'database'
  AND score > 10
ORDER BY relevance DESC
LIMIT 10;

ここでは、ParadeDBはTINの71 QPSに対して820 QPSを維持しました。これは11.6倍のスループット差です。

Hacker News Top K、スコアフィルタ付き
8並列クライアント · 5分間のターゲット

ビュー
パーセンタイル
↑ 高いほど良い

テーブルをクリーンアップ。各ワーカーの順序付けられた生クエリタイミングと測定された開始/終了間隔から再構築された1秒バケット。フルランの凡例値には、バッチ完了オーバーランが含まれます。線は中心9秒移動平均を使用します。凡例の値は平滑化されていないフルラン結果です。

3. 時間順にソートされたTop K検索

「database」という用語を含む、最も新しい投稿Top 10を教えてください。

SELECT id, text, "by", score, "time"
FROM hn_items
WHERE text ||| 'database'
ORDER BY "time" DESC NULLS LAST
LIMIT 10;

ここでは、ParadeDBはTINの17 QPSに対して378 QPSを維持しました。これは21.7倍のスループット差です。

Hacker News Top K、時間順ソート
8並列クライアント · 5分間のターゲット

ビュー
パーセンタイル
↑ 高いほど良い

テーブルをクリーンアップ。各ワーカーの順序付けられた生クエリタイミングと測定された開始/終了間隔から再構築された1秒バケット。クエリが完了しなかった秒は0 QPSを示し、レイテンシサンプルに寄与しません。線は中心9秒移動平均を使用します。凡例の値は平滑化されていないフルラン結果です。

PlanetScaleも、これらのクエリが重要であることに同意しています。彼らのブログ投稿からの引用です。

“Postgresで優れたテキストインデックスは、これらすべてをサポートすると同時に、全文およびその他の列タイプにまたがる複雑なWHERE句を処理する必要があります。”

TINは、これらのフィルタリングおよび時間順ソートクエリではまだそれほど高速ではありません。しかし、WikipediaとStackExchangeのワークロードにはインデックス付きテキスト列が1つしかないため、このギャップは露呈しません。実際のアプリケーションテーブルはより幅広く、検索結果は通常、タイムスタンプや数値フィールドのようなフィールドでフィルタリングされたり、順序付けされたりします。

これが、より広範なポイントにつながります。選択するワークロードが、語るストーリーを決定することがよくあります。最初にベンチマーカーを導入したとき、私たちはあらゆるワークロードに対応できるツールを構築したと説明しました。PlanetScaleは、TINが優れているものを作成しました。私たちは、それが私たちのBM25とカウントパフォーマンスの盲点を露呈させたことに感謝し、それらのクエリの最適化を厳密に推進しました。

しかし、ParadeDBは上記のクエリでより高速ですが、Postgresまたはその他のいずれかの「最速の検索エンジン」を確立したとは考えていません。特に製品を構築したのと同じチームによって設計されたベンチマークでは、単一のベンチマークでは不可能です。これは、ParadeDBのHacker Newsベンチマークにも、PlanetScaleのStackExchangeおよびWikipediaベンチマークにも当てはまります。

あなた（読者）にとって何が最速かを見つける唯一の方法は、あなた自身のデータであなた自身のクエリをテストすることです。検索クエリの形状は数多くあり、私たちの目標はこれらの形状のできるだけ多くを加速することです。現在のデータベースでフィルタリング、ソート、またはファセットを使用した検索が遅くてイライラする場合は、ParadeDBで試してみてください。

基本的なアーキテクチャの違いはありますか？

TINのローンチ投稿では、パフォーマンスの優位性をドキュメント識別子の選択に帰しました。パートIで説明したように、私たちは懐疑的でした。しかし、これらのより複雑なクエリでのギャップを説明する、より深い根本的なアーキテクチャの違いが存在すると考えています。それは、クエリのどれだけがインデックスにプッシュダウンできるかということです。

TINは明確にテキスト専用インデックスです。各インデックスは1つのテキスト列をカバーし、非テキストフィルタはPostgresとその他のインデックスに任されます。数値値によるフィルタリングや時間によるソートを行ったクエリでは、TINはそれらの非テキスト列に対するB-treeインデックスに依存します。一方、ParadeDBは、これらのすべての列を1つのインデックスにまとめてインデックス付けできます。

この区別は、フィルタリングとソートの両方にとって重要です。テキストと非テキストの両方のフィルタを持つクエリの場合、TINとB-treeインデックスは、結合される前に独立してすべてのマッチを生成する必要があります。これにより、大量の作業を回避する機会が失われます。B-treeはどのドキュメントがテキストクエリに一致するかを知らないため、交差によって後で破棄される数百万のマッチを収集する可能性があります。時間によるソートのような他のソート順序では、TINはテキストマッチングと時間順序付けを調整できません。Postgresは、検索が最新の10件のマッチを追跡するのではなく、インデックスの外で一致を順序付ける必要があります。

ParadeDB（およびElasticsearch）のような最新のエンジンは、テキストとメタデータ構造を同じドキュメント識別子をキーとして一緒に格納することで、この問題を解決します。これにより、クエリ実行は、大規模な独立した候補セットを具体化して後で結合するのではなく、テキストマッチング、フィルタリング、および順序付けを逐次的に調整できます。詳細については、PostgresでTop Kを最適化した方法を参照してください。

これらの実行に使用されたインデックス定義は、その違いを明確にします。ParadeDBは、検索可能なテキストとフィルタリングおよび順序付けに使用されるフィールドを1つのインデックスに保持します。

CREATE INDEX hn_items_idx
ON public.hn_items
USING paradedb (
  ((text)::pdb.unicode_words(
    'pnorms=true',
  )),
  score,
  "time"
)
WITH (partition_by=ctid, target_segment_count=4);

TINはtextを個別にインデックス付けし、他のフィールドにはB-treeを使用します。

CREATE INDEX hn_items_text_bm25_idx
ON public.hn_items
USING tin (text)
WITH (initial_segment_count='4');

CREATE INDEX hn_items_score
ON public.hn_items USING btree (score);

CREATE INDEX hn_items_time
ON public.hn_items USING btree ("time");

締めくくり

パートIは、予想以上に多くの反響を呼びました。その投稿の最後に書いたことを改めて強調したいと思います。オープンソースの検索およびデータベースコミュニティには、長年にわたる友好的な協力と競争の伝統があります。LuceneやTantivyのようなプロジェクトは常にアイデアを交換し、パフォーマンスで互いを凌駕していますが、それはフロンティアを前進させ、実際のアプリケーションをより速くするため、敵意は全くありません。Tantivyのコミッターとして、私たちはその精神を共有しています。

パートIに応答してTINがBM25パフォーマンスを改善したのを見て、チームに再び称賛を送りたいと思います。新バージョンが入手可能になったら、もう一度比較を行うことを嬉しく思います。2それまでの間、検索空間は広大でエキサイティングであり、他のデータベースや検索エンジンが次に何に取り組むかを見るのを楽しみにしています。

これらのクエリをあなた自身のデータでテストしたい場合は、私たちの開始ガイドを使用してParadeDBをローカルで実行できます。

---

ベンチマークアプローチに関する注意

以前の投稿では、すべての数値は私たちのベンチマーカーツールから得られました。このツールはk6を使用してワークロードを実行します（PlanetScaleはフォークを作成し、有用な機能を取り戻しました）。しかし、COUNT比較のためにベンチマーカーを使い始めたとき、問題が発生しました。

クライアント観測のWikipedia COUNTレイテンシ
8並列クライアント · 順次30秒実行

↓ 低いほど良い

k6ダッシュボードエクスポートの194,906件の生のクライアント観測クエリ期間から計算された1秒バケット。順次実行は経過時間で整列されます。線は平滑化されていません。凡例の値はフルラン結果です。

このクライアントサイドのWikipedia COUNT実行では、k6はTINのp50を3.6ms、ParadeDBのp50を1.6msと報告しました。これほど低いレイテンシでは、TINのパスでの追加のネットワーク時間が結果を大きく変えました。TINがParadeDBよりもネットワーク遅延によって不当に増加していることを知っていたため、この比較のためにベンチマーカーの使用を中止し、ネットワークの違いを排除するアプローチの調査を開始しました。また、TINのローンチ投稿が、私たちが測定した約2,000よりもはるかに高い、毎秒10,000クエリに近いスループットを報告していたことも知っていました。

ネットワークトラバーサルなしでこれらのワークロードのスループットとレイテンシ測定値を記録する、よりエキゾチックなサーバーサイドPL/pgSQLベンチマークアプローチを使用するように移行しました。これにより、ネットワークオーバーヘッドが測定値から除去されます。別のツールを使用するのは好きではありませんが、PlanetScaleが遅延とジッターの両方で不当にペナルティを受けないように、システムを正確に比較する唯一の方法でした3。興味深いことに、このアプローチはより公平であるにもかかわらず、最終的な比率にはほとんど違いがありませんでした。PlanetScaleのベンチマークにはこの問題はありません。なぜなら、両方のシステムをローカルで実行できるからです（pg_searchはオープンソースです）。

このベンチマークツールをメインリポジトリの外で公開しました。メインリポジトリの外で公開しました。将来的にメンテナンスする可能性は低いですが、誰かが引き継ぎたいのであれば、そこには素晴らしいサーバーサイドベンチマーク拡張機能のアイデアがあるかもしれません。

---

フットノート

1. インデックスにpartition_by = ctidをオプションとともに渡します。↩

2. この記事では、TINバージョン1.0.4をベンチマークしています。これは執筆時点で利用可能な最新バージョンです。ParadeDBは、コミットa637cbee55a987807325e445b00c31ae64ef7241のmainからベンチマークされました。既存のユーザーの場合、ビットマップ/ctid最適化には再インデックスが必要です。↩

3. まだいくつかの違いがあります。TINはPlanetScale M-640 Intelマシンを使用しましたが、ParadeDBはi7i.8xlargeインスタンス上の8-CPU Dockerコンテナで実行されました。TINがどのようにスケジュールされたかは正確にはわかりませんが、構成は同じNVMeストレージとIntelチップセットを使用しました。↩