兩週前，PlanetScale 發布了 TIN，一個針對 Postgres 的全文檢索擴充套件。他們的發表文章報告了在 ParadeDB 部分文字檢索功能（特別是 BM25 排序的全文檢索和文件計數）上的顯著效能提升。
我們想對 PlanetScale 團隊表示敬意。看到另一個 Postgres 平台投入搜尋技術（顯然使用者想搜尋他們的關聯資料）非常令人振奮，而且很明顯 TIN 背後有大量深思熟慮的工程設計。我們也很高興看到 PlanetScale 採用了我們為此類測試打造的 ParadeDB 基準測試工具。
先說清楚一件事：TIN 非常快（在 PlanetScale 的每個基準測試中至少比 ParadeDB 0.25 快 8 倍）。快到我們唯一的反應就是閉嘴並戴上效能優化的帽子。兩週後，這是使用相同 StackExchange 基準資料集、測試工具和機器類型（雖然 TIN 不是開源，必須在 PlanetScale 上執行）的 BM25 排序前後比較：
（此處省略圖表說明）
有趣的不是我們迅速縮小差距，而是我們如何縮小差距。TIN 的文章聲稱他們的效能來自於一個根本的架構差異：使用 Postgres 內部的 ctid 欄位作為文件識別碼。然而，我們是透過幾輪優化，與文件識別方式無關的改進來縮小差距。我們也調整了一些基準設定，這些設定並不完全公平——稍後會詳述。
接下來逐一拆解我們的修正和設定變更。
任何全文檢索索引的核心是 postings list：每個詞彙對應的文件識別碼列表。例如，若索引有文件 1 到 10，且詞彙“database”出現在文件 2 和 4，則“database”的 postings list 就是 [2, 4]。postings list 讓你能有效率地識別包含特定詞彙的文件。
ParadeDB 背後的搜尋庫 Tantivy 使用連續的 u32 文件 ID 作為 postings 的識別碼。這些識別碼是 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 查詢。
對於計數查詢，使用 ctid 有其道理。當數百萬筆匹配需要可見性檢查時，將 DocId 轉換為 ctid 會增加成本。以 Postgres 頁面為單位組織 postings，有助於減少讀取資料量並批次處理。
但對 BM25 Top K 查詢，我們持懷疑態度。ParadeDB 延遲 ctid 查找直到收集到最終的 Top K 文件。對於 top 10 查詢，只有 10 次查找。這些查找雖然有成本，但在效能分析中非常微小，無法解釋數量級的差距。
我們反而懷疑能在其他程式碼優化機會中縮小差距。
本文聚焦於我們對 Top K BM25 查詢的優化。我們也優化了 COUNT 查詢，將在第二部分討論。
我們從一個簡單查詢開始：找出包含單一詞彙且 BM25 排序前十的文件。為了更快的本地迭代，我們使用較小的 2870 萬筆 Hacker News 資料集。
TIN 在此查詢中觸及的 Postgres 頁面遠少於 ParadeDB，因此我們懷疑這是其較快的主要原因。當 StackExchange 資料集部分讀取來自磁碟時，這差異會更明顯。ParadeDB 有一項新功能，能將頁面存取歸因到該頁面中存放的資料結構，立刻告訴我們問題所在：
「Fieldnorms」編碼文件中索引欄位的長度，BM25 用來正規化分數。Tantivy 中的 fieldnorm 非常小：文件長度被量化成單字節的 fieldnorm_id。怎麼會這麼小的東西造成這麼多讀取？
問題在於區域性。Tantivy 將 fieldnorm 與 postings 分開存放，在一個以 DocId 索引的陣列中。讀取詞彙的 postings 是連續的，但對應的 fieldnorm 讀取會在陣列中跳躍。使用 Tantivy 通常的記憶體映射儲存，這種配置可能沒問題，因為每個駐留的 fieldnorm 是廉價的記憶體查找，但在 Postgres 中，這代表此查詢會觸及約 1500 個不同的 fieldnorm 頁面。
我們的修正是將 fieldnorm 陣列與每個 postings list 一起存放，且順序與 postings 的 DocId 值相同。這樣在計分時可以與 postings 一起順序讀取 fieldnorm，消除分散的查找。此變更後，fieldnorm 存取從 1500 頁降至僅 30 頁！
代價是儲存空間，因為文件的 fieldnorm 現在會為每個不同詞彙重複存放。幸運的是，這不一定意味著 fieldnorm 儲存會乘以詞彙數量。實際語料中，大多數詞彙的 postings list 很短，對應的 fieldnorm 陣列也很小。例如，此變更使 2870 萬筆 HN 索引大小增加約 9%。
將 fieldnorm 分離帶來了小詞彙數查詢的巨大加速，但對於包含許多詞彙的 disjunction 查詢，我們仍不滿意效能。例如，以下查詢匹配包含任一詞彙的文件：
（此處省略查詢示例）
我們注意到，儘管前次優化後緩衝區讀取下降約 80%，查詢時間卻只下降 5%，顯示瓶頸在於演算法。
分析發現大部分時間花在所謂的 Blockmax WAND 迴圈。
背景說明：Blockmax 是搜尋引擎用來有效跳過 postings 區塊以執行 disjunction（例如 termA OR termB）查詢的標準演算法。Blockmax 有兩種家族：WAND 和 MAXSCORE。我們不深入細節，但大致上：
WAND 和 MAXSCORE 的取捨在於跳過判斷的工作量。WAND 跳過更多，但花更多 CPU；MAXSCORE 跳過較少，但開銷較低。當查詢詞彙數增加，WAND 的開銷會增大，可能超過它跳過的工作量。
Tantivy 使用 WAND。Lucene 直到 2023 年也用 WAND，後來為某些查詢引入 MAXSCORE。現在 Lucene 會根據查詢形態動態選擇 WAND 或 MAXSCORE。
我們實作了 MAXSCORE 路徑，簡單的選擇啟發式：對於至少三個詞且 postings 足夠密集的 disjunction 查詢使用 MAXSCORE，其他使用 WAND。對上述包含 10 個詞的查詢，我們不僅將 p50 延遲降低約 6 倍，p95 降低約 8 倍，且在 2870 萬筆 HN 資料集上速度是 TIN 的兩倍：
（此處省略圖表說明）
PlanetScale 的基準測試大致公平，除了兩個無意中偏向 TIN 的異常：ParadeDB 語法疏忽和 TIN 處理常見詞彙的方式。
我們發現 TIN 基準使用 ParadeDB 的查詢字串解析器，接受 Tantivy 的迷你查詢語言（@@@ 運算子）。問題是這些查詢沒有指定欄位名稱，例如 <query> 而非 <field>:<query>。
未指定欄位時，ParadeDB 預設搜尋所有索引的文字欄位。StackExchange 資料集中，id 與 body 欄位皆被索引，導致 ParadeDB 每次查詢搜尋兩個欄位，TIN 則只搜尋一個，ParadeDB 因此處於劣勢。
為避免此問題，我們將所有 ParadeDB 查詢改用原生的 |||（或）、&&&（且）和 ###（片語）運算子。
我們在 HN 基準中輕鬆擊敗 TIN 的 BM25 查詢。但載入 PlanetScale 的 StackExchange 資料集與查詢後，因為尾端延遲較長，吞吐量仍落後約 30%。為何在我們的基準中快數倍，卻在 PlanetScale 基準中較慢？
差距來自 TIN 對常見詞彙的計分捷徑，稱為 dense-term elision，我們認為其在 StackExchange 資料集上的使用值得商榷。
簡單說明：像 "the"、"is" 這類常見詞彙有龐大 postings list，讀取與計分成本高，但 BM25 權重極低，幾乎不影響最終排序。大多數搜尋引擎在索引時用停用詞字典處理（兩套引擎都支援，但基準未啟用）。TIN 採用不同方法：查詢時跳過出現超過 10% 語料庫的詞彙計分（可透過 dense_ratio 設定）。這是 TIN 中最有趣的想法，我們將深入探討。
當然有取捨，這裡是正確性。啟用 elision 時，TIN 計算的是 BM25 的近似值，忽略常見詞，可能導致結果排序與真實 BM25 不同。大多數真實查詢不會有問題，除非查詢完全由常見詞組成。
我們查看 Stack Overflow 基準查詢，驚訝發現有整個查詢由這些常見詞組成，因為查詢是從 Stack Exchange 語料連續字串抽樣產生，如 "is it"、"to a"、"is to"。在延遲差距最大的查詢中，這些非真實查詢佔多數。對它們，TIN 跳過大部分計分工作，ParadeDB 則計算精確分數。
對於啟用 elision 的 TIN，我們發現：
（此處省略數據說明）
我們並非說「與精確 BM25 不同」就等於「較差」。elision 的詞彙本來權重低，判斷是否較不相關需人工評估，基準無此資料。但基準框架是 BM25 top-K 搜尋，啟用 elision 後 TIN 與 ParadeDB 排序不同。
因此，我們的主要比較使用兩套引擎的精確 BM25，TIN 設定 dense_ratio=2。下方也展示 TIN 預設啟用 elision 的設定，該設定下他們「勝過」我們，因為原始基準使用此設定。
我們分享兩組結果，讓讀者自行判斷。我們不希望基準設定掩蓋我們對 ParadeDB 的效能提升。同時也必須提及這些設定，因為它們對原始結果影響甚大。我們也包含了啟用停用詞的 ParadeDB 結果。
（此處省略圖表說明）
至於 TIN 使用 ctid 與 ParadeDB 使用 u32 文件識別碼的選擇，我們認為也是一種取捨。
TIN 文章的前提是 ctid 是 postings list 的普遍好選擇。問題是，沒有什麼比密集、排序且唯一的整數壓縮得更好。因此大多數搜尋系統使用 u32 DocId。切換到 48 位元的文件識別碼不一定更有效率，因為 ctid 的 48 位元是兩個不同領域數字的串接（區塊號碼，數百萬級；元組偏移，最多 291）。
密集的 u32 DocId 另一優勢是容易連結到欄位式儲存。postings 告訴你哪些文件匹配；欄位則能有效存取文件的元資料（如數值或分類標籤）。
欄位式儲存常與 OLAP 資料庫相關，但對搜尋查詢也很重要：
所有這些搜尋查詢都需要欄位式格式。使用 DocId，連結非常直接。在一個 segment 中，文件 42 對應每個欄位的第 42 列。拿到 postings list 的 ID 後，我們可以直接查欄位值。
ctid 無法提供欄位位置。它識別 Postgres 的物理位置，如頁面 190、槽位 17。要從欄位取得該文件的價格，必須先找出 (190, 17) 對應的欄位列，這需要映射或等效查找。
TIN 在 BM25 計分和文件計數上表現優異，但這只是像 Elasticsearch 這類搜尋引擎的一部分。對於「其餘搜尋功能」，需要欄位式表示。如果 TIN 決定做欄位式，估計也得付出 ctid / DocId 轉換成本（反向）。
TIN 文章將效能優勢歸因於使用 ctid 取代 DocId。但我們在不改變文件識別碼的情況下縮小差距，方法包括：
（此處省略具體優化列表）
這些改進多數發生在 Tantivy，我們的搜尋庫。
過去幾年，我們常討論是否選擇 Tantivy 是 ParadeDB 的正確決定，與 TIN 看似從零打造新搜尋引擎的做法相比。這次調查強化了我們使用 Tantivy 的信念。它帶來十多年開發歷史、全球大型企業的實戰考驗與卓越速度。Tantivy 不一定能完美配合 Postgres 的區塊配置，但其擴充性和功能彌補了這點。
你可能會問：為何我們之前沒做這些優化？效能工作永無止境，工程資源有限。在達到 Elasticsearch 同等效能後，我們將注意力轉向擴展 ParadeDB 能力，超越「僅是文字搜尋」，朝向有效執行包含複雜過濾、分面和連接的搜尋查詢。現在我們的搜尋 API 非常廣泛，很高興 TIN 讓我們注意到核心優化的機會。
開源搜尋社群有長久的合作傳統。例如，Lucene 與 Tantivy 雖是競爭搜尋庫，卻經常分享想法並友好地互相基準測試。我們在與 Tantivy 創建者 Paul Masurel 的對話中探討這如何雙贏。我們希望這次也是一例。這對我們來說是一場有趣的衝刺。
我們感謝 TIN 作者在部落格分享部分工程決策，儘管專案本身非開源。我們的工作皆公開，且已開始將相關改進回饋至 Tantivy。
我們釋出 0.26.0-rc.2 候選版本以便重現這些結果。對現有 ParadeDB 用戶，這些改進將納入下個穩定版本 0.26.0，預計下週發布。我們確保這些變更向後相容，但需重新建立索引以繼承所有優化。
對社群貢獻者：此調查有時間限制，我們認為還有許多優化空間（尤其在更有效的 Blockmax 修剪和減少緩衝區存取方面）。歡迎任何推動效能極限的貢獻。
下一部分將討論我們對 COUNT 查詢效能的優化（提示：同樣不需更改文件識別碼）。在此之前，祝搜尋愉快！我們期待為 Postgres 與搜尋社群帶來更快的文字查詢體驗。
特別感謝曾任 ParadeDB 員工並推動 PlanetScale TIN 產品的 Eric ZomboDB。
