ParadeDB 透過段落分割槽、DocId 反轉與點陣圖最佳化，將 COUNT 查詢速度提升 66 倍

作者 Ming Ying，發表於 2026 年 10 月 13 日

在 Part I 中，我們將 ParadeDB 的 Top K BM25 效能提升了數個量級。最後，我們承諾釋出一個 Part II，專注於 COUNT。本文將說明使我們的 COUNT 查詢更快的最佳化措施。以下是最終結果，使用與原始 TIN 文章相同的 Wikipedia 資料集和基準測試框架：

首先，我們將說明如何提升 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 壓縮論文，允許我們按一個或多個欄位的值分割區段。我們已經在過去幾個月開發此功能，並將很快分享技術深度探討（對 Top K 與連線的效益巨大）。就此查詢而言，關鍵在於我們可以按 ctid（Postgres 的內部列識別符）分割，為每個區段提供一個互斥的 Postgres 頁碼範圍¹：

Without partitioning (overlapping min/max page ranges):

Postgres pages:  0----------2999  0----------2999  0----------2999
                 [ Segment A ]    [ Segment B ]    [ Segment C ]

With partitioning (disjoint page ranges):

Postgres pages:  0-----------999  1000-------1999  2000-------2999
                 [ Segment A ]    [ Segment B ]    [ Segment C ]

每個區段已經儲存最小與最大 ctid。透過此佈局，我們可以在前期將此範圍與可見性地圖對照。若範圍內的每一頁都標記為全可見，我們可以一次性跳過該區段的可見性檢查（以及所有相關頁面讀取）。

使用純大小層級壓縮時，這些 ctid 最小/最大範圍可能覆蓋表格的大部分。單一更新頁面即可使大多數區段失去捷徑。按 ctid 分割將此影響限制於包含受影響頁面的區段，其他區段則可繼續跳過逐行檢查。

對於我們的基準查詢，這使得與可見性相關的頁面存取從 1,382 次降至僅 30 次。

最佳化 2：反轉我們的 DocId 對映

但如果段落的 ctid 範圍內至少有一頁需要進行可見性檢查，情況又如何？隨著距離上一次（自動）vacuum 越遠，這種情況越可能發生，而我們不想讓少數已修改的頁面強迫每一次匹配都進行 ctid 讀取。

TIN 部落格說，將 DocIds 轉換為 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。

After: document boundaries indexed by page

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

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

使用此新格式，我們可以先檢查可見性對映，然後僅對需要檢查的頁面查詢檔案範圍：

  Page needing checks:   11
  DocIDs needing checks: [2, 5)
  Query matches:         [0, 3, 6]
                             |
                             v
                    Only do a CTID lookup for DocIds in 2, 5) -> Doc 3

對於上述單一術語計數查詢，在更新 1,000 行後，這將緩衝區存取次數從 7,500 次以上降至不到 400 次：減少 95%。

最佳化 3：點陣圖非常適用於常見術語

Tantivy 為其倒排列表使用 BP128 編碼。BP128 表示倒排陣列被分割為 128 大小的區塊，每個區塊都進行位元封包與差分編碼。這些區塊還攜帶分數邊界，允許 blockmax 演算法 在 BM25 排名時跳過不具競爭力的區塊。

在分析時，我們發現這種表示方式對大多數術語都有效，唯一例外是具有稠密倒排列表的非常常見術語。對於這些常見術語，我們發現交叉或合併大型 BP128 陣列會產生大量開銷，而將倒排列表表示為點陣圖則使這些合併與交叉的成本大幅降低。

Document IDs: [1, 3, 4, 7]

Bitmap: one bit per possible document ID

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

BP128: store gaps between document IDs, then bitpack

  Doc IDs:     1     3     4     7
  Gaps:        1     2     1     3
  In binary:  01    10    01    11
              └── 2 bits per gap ──┘

A second block starts at the 129th posting.

為了說明 BP128 與點陣圖之間的權衡，請考慮兩種情境。首先，假設有兩個稀有術語，每個術語匹配 100 萬篇檔案中的 10 篇。交叉它們的 BP128 編碼陣列僅需少量比較，而掃描兩個等效的點陣圖則意味著需要處理每個點陣圖 100 萬位，其中大部分為零（即浪費工作）。

接下來，假設兩個術語是常見的，每個術語匹配 100 萬篇檔案中的約 500K 篇。這意味著它們的陣列各有約 500K 個條目。在這種情況下，點陣圖可能更有效，因為位元 AND/OR 可以一次處理 64 篇檔案，而不是逐條專案遍歷陣列。

我們為足夠稠密、匹配超過 10% 檔案的術語引入了點陣圖表示。僅此改動就將我們的 Wikipedia 計數基準的 p99 延遲減半。

現在談談其餘搜尋

TIN 在其最佳化的查詢形態上非常快速：按 BM25 排序的 Top K 以及計數。ParadeDB 旨在成為 Postgres 上的 Elasticsearch 替代品，從這個角度看，BM25 和計數僅是我們在生產環境中看到的查詢的冰山一角。

例如，請考慮以下針對 Hacker News 資料集的搜尋查詢：

1. 篩選計數

How many posts contain the term "database" AND received more than 10 Hacker News points?

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

ParadeDB 持續 777 QPS，而 TIN 為 78 QPS，吞吐量差異為 10.0 倍。

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 持續 820 QPS 對比 TIN 的 71 QPS，吞吐量差距為 11.6 倍。

3. 按時間排序的 Top K 搜尋

請給我包含關鍵字「database」的最近 10 篇貼文。

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

ParadeDB 持續 378 QPS 對比 TIN 的 17 QPS，吞吐量差距為 21.7 倍。

PlanetScale 同意這些查詢很重要。引用他們自己的部落格文章：

「在 Postgres 中，一個好的文字索引必須支援所有這些功能，同時處理連線、複雜的 WHERE 子句，跨全文檢索和其他欄位型別。」

TIN 在這些過濾和時間排序的查詢上還不是很快。但由於他們的 Wikipedia 和 StackExchange 工作負載僅包含單一索引文本欄位，並未顯示這一差距。實際應用表格更寬：搜尋結果通常會以元資料值過濾，或按時間戳、數值等欄位排序。

這帶我們到一個更廣泛的觀點：你選擇的工作負載往往決定了你所說的故事。當我們首次推出our benchmarker時，我們說明瞭我們構建了一個能夠容納任何工作負載的工具。PlanetScale 設計了一個 TIN 擅長的工作負載。我們欣賞它揭示了我們 BM25 和計數效能的盲點，並嚴格推動了對這些查詢的最佳化。

但儘管 ParadeDB 在上述查詢上更快，我們不認為它能確立「最快的搜尋引擎」，無論是在 Postgres 還是其他平臺。沒有單一基準能做到這一點，尤其是由同一個開發團隊設計的基準。這同樣適用於 ParadeDB 的 Hacker News 基準，就像適用於 PlanetScale 的 StackExchange 和 Wikipedia 基準一樣。

瞭解哪種搜尋對你（讀者）最快的唯一方法是自行在自己的資料上測試查詢。搜尋查詢有許多不同形態，我們的目標是盡可能加速這些形態。如果在目前的資料庫上使用過濾、排序或分面搜尋時速度令人沮喪，可以嘗試在 ParadeDB 上執行。

是否存在根本的架構差異？

TIN 的發布文章將其效能優勢歸因於其選擇的檔案識別符。正如我們在第一部分所說，我們持懷疑態度。但我們確實認為存在一個更深層、更根本的架構差異，能解釋這些更複雜查詢中的差距：有多少查詢能被推到索引層。

TIN 明確為純文字索引。每個索引僅覆蓋一個文字欄位，將非文字過濾留給 Postgres 及其其他索引。對於我們執行的篩選數值或按時間排序的查詢，TIN 依賴於對那些非文字欄位的 B-tree 索引。相對地，ParadeDB 能將所有這些欄位一起索引於同一個索引。

這一區別對過濾和排序都很重要。對於同時包含文字和非文字過濾的查詢，TIN 與 B-tree 索引必須各自獨立產生所有匹配，然後再合併。這樣會錯過避免大量工作機會：B-tree 不知道哪些檔案符合文字查詢，因而可能收集到數百萬個匹配，交集後才被丟棄。對於其他排序方式，例如按時間排序，TIN 無法將文字匹配與時間排序協調。Postgres 必須在索引之外對匹配進行排序，而不是讓搜尋隨著程序追蹤最新的 10 個匹配。

現代引擎如 ParadeDB（以及 Elasticsearch）透過將文字與元資料結構一起存放，並以相同的檔案識別符作鍵，來解決此問題。這使查詢執行能在進行中協調文字匹配、過濾與排序，而非先生成大型獨立候選集再合併。欲進一步瞭解，請參閱我們如何在 Postgres 中最佳化 Top K。

這些執行所用的索引定義清楚顯示差異。ParadeDB 將可搜尋文字以及用於過濾和排序的欄位儲存在同一索引中：

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");

結語

第一部分引發的反應超出我們預期。我們想重申在那篇文章結尾所寫的內容：開源搜尋與資料庫社群長期以來都有友好合作與競爭的傳統。像 Lucene 與 Tantivy 這類專案不斷交換想法並在效能上互相挑戰，卻沒有任何敵意，因為這推進了前沿並使實際應用更快。作為 Tantivy 的提交者，我們也秉持這種精神。

我們看到 TIN 在回應第一部分後提升了 BM25 效能，並想再次向團隊致以讚賞。我們很樂意在新版本發布後進行另一輪比較。² 同時，搜尋領域廣闊、令人興奮，我們期待看到其他資料庫與搜尋引擎接下來的挑戰。

若想在自己的資料上測試這些查詢，您可以使用我們的快速入門指南在本機執行 ParadeDB。

關於  的一句話

在之前的文章中，所有數字都來自 our benchmarker 工具，該工具使用 k6 執行工作負載（PlanetScale 建立了一個分支，我們將有用的功能拉回）。然而，當我們開始使用 benchmarker 進行 COUNT 比較時，發現了一個問題。

在這次客戶端執行的 Wikipedia COUNT 執行中，k6 報告 TIN 的 p50 為 3.6ms，ParadeDB 為 1.6ms。在這麼小的延遲下，TIN 路徑上的額外網路時間實質改變了結果。我們知道 TIN 的延遲被網路延遲膨脹的程度比 ParadeDB 更大，因此停止使用 benchmarker 進行此比較，並開始研究能消除網路差異的方法。我們也知道 TIN launch post 報告的吞吐量接近 10,000 查詢每秒，遠高於我們測得的大約 2,000。

我們改為使用更為特殊的伺服器端 PL/pgSQL 基準測試方法，該方法在不經任何網路傳輸的情況下記錄這些工作負載的吞吐量和延遲測量。這樣可消除測量中的網路開銷。我們不太喜歡使用另一個工具，但這是唯一能準確比較兩個系統而不讓 PlanetScale 因更高延遲和抖動受到不公平懲罰的方法。³ 有趣的是，即使此方法更公平，最終比例差異仍很小。PlanetScale 的基準測試沒有這個問題，因為它們可以在本地執行兩個系統（pg_search 是開源的）。

我們已在主倉庫之外 發布了這個基準測試工具。我們不太可能在未來維護它，雖然如果有人想接手，裡面可能有很好的伺服器端基準測試擴充想法。

腳註

1. 使用選項將 partition_by = ctid 傳入索引。↩

2. 此篇文章測試 TIN 版本 1.0.4，即撰寫時可用的最新版本。ParadeDB 以 main 的提交 a637cbee55a987807325e445b00c31ae64ef7241 進行基準測試。對於現有使用者，bitmap/ctid 最佳化需要重新建立索引。↩

3. 仍有一些差異。TIN 使用的是 PlanetScale M-640 Intel 機器，而 ParadeDB 在一臺 i7i.8xlarge 例項上以 8 核 Docker 容器執行。雖然我們無法確定 TIN 的排程方式，但兩者配置使用相同的 NVMe 儲存與 Intel 晶片。↩