ParadeDB Search Performance Improvements

Two weeks ago, PlanetScale unveiled TIN, a full-text search extension for Postgres. Their launch post reported impressive performance wins over a subset of ParadeDB’s text search functionality, specifically BM25-ranked text search and document counts.

We’d like to extend kudos to the PlanetScale team 1. It’s great to see another Postgres platform investing in search (turns out people want to search their relational data), and it’s clear that a lot of thoughtful engineering went into TIN. We’re also happy to see PlanetScale’s adoption of ParadeDB’s benchmarker tool, which we built for exactly this kind of testing.

Let’s be very clear about one thing: TIN is fast (at least 8x faster than ParadeDB 0.25 in every PlanetScale benchmark). So fast that the only response which made sense was to shut up and put on our performance optimization hats. Two weeks later, here’s the BM25-ranked before and after, using the same StackExchange benchmark dataset, harness, and machine types (although TIN isn’t open-source so it’s running on PlanetScale)2:

Warm-cache, read-only runs. TIN uses dense_ratio=2 with search elision disabled; see Handling Common Terms. One-second buckets; latency uses nearest-rank percentiles. Lines use a centered 9-second moving average; legend values are unsmoothed full-run results.

What’s interesting is not that we quickly closed the gap, but how we closed it. TIN’s post claims that their performance is due to a fundamental architectural difference that uses Postgres’ internal ctid fields as document identifiers. However, we closed this gap through a few optimization passes that had little to do with how documents are identified. We also tweaked some benchmark settings that didn’t give a fully fair comparison — more on this later.

Let’s unpack our fixes and the configuration changes one by one.

Without Text Index

A sequential scan checks each document in turn, finding document IDs 2 and 4.…

With Text Index

The text index jumps directly to the postings for database, returning document IDs 2 and 4.database24…

The heart of any text search index is a postings list: a per-term list of document identifiers containing that term. For instance, if an index has documents 1 to 10 and the word “database” appears in documents 2 and 4, the postings list for “database” is simply [2, 4]. Postings lists allow you to identify documents matching specific terms very efficiently.

Tantivy, the search library behind ParadeDB, uses sequential u32 document IDs for its postings. These identifiers are internal to Tantivy, and are assigned based purely on insertion order. For the remainder of this post, DocId refers to the u32 document identifier used by Tantivy and ParadeDB.

Postgres identifies its rows by ctid values. A ctid is a tuple pointing to a row’s physical location in Postgres’ block-based storage. (190, 17) identifies the row which is currently found in slot 17 of block 190.

Because ParadeDB is a Postgres index powered by Tantivy, there has to exist a map between DocId and ctid values. The crux of TIN’s post is that using ctid values directly as document identifiers eliminates this map and enables efficient bitmap operations and visibility checks. PlanetScale attributes much of TIN’s performance advantage to the downstream benefits of that choice.

The launch post benchmarks two broad query types: Top K matches by BM25 score and COUNT queries over matching documents.

For counts, the ctid argument made sense. When millions of matches require visibility checks, translating DocId values into ctid values adds up. Organizing postings around Postgres pages creates opportunities to read less data and batch that work.

For BM25 Top K queries, we were skeptical. ParadeDB defers ctid lookups until the final Top K documents have been gathered. For a top 10 query, that means 10 lookups. These lookups aren’t free, but they’re tiny in the profile and don’t explain an orders-of-magnitude gap.

Instead, we suspected that we could close the gap with various optimization opportunities elsewhere in our code.

This post focuses on our Top K BM25 optimizations. We’ve also optimized COUNT, which will come in Part II.

We started with a simple query: give me the ten most relevant documents containing a single term ordered by BM25 score. For faster local iteration, we used the smaller 28.7M Hacker News dataset.

EXPLAIN (ANALYZE, BUFFERS) SELECT id, title, by FROM hn_items WHERE title === 'database' ORDER BY pdb.score(id) DESC LIMIT 10;

TIN touched far fewer Postgres pages than ParadeDB on this query, so we suspected that was the main reason it was faster. This would also compound on the StackExchange dataset when some reads come off disk. ParadeDB has a new feature that attributes page accesses to the data structures stored in those pages. It told us straight away that we had an issue:

“Fieldnorms” encode the length of a document’s indexed field, which BM25 uses to normalize scores. A fieldnorm in Tantivy is tiny: a document length quantized into a single-byte fieldnorm_id value. How could something tiny account for so many reads?

The problem was locality. Tantivy stores fieldnorms separately from postings, in an array indexed by DocId. Reading a term’s postings is sequential, but fetching the corresponding fieldnorms can jump all over that array. With Tantivy’s usual memory-mapped storage, this layout is likely fine3 because each resident fieldnorm is a cheap memory lookup, but in Postgres it meant touching roughly 1,500 distinct fieldnorm pages for this query.

Our fix was to store a fieldnorm array alongside each postings list, in the same order as the postings’ DocId values. Scoring could then read fieldnorms sequentially alongside postings, eliminating the scattered lookups. After this change, fieldnorm accesses dropped from 1,500 pages to just 30 (!).

Postings Fieldnorms "database": [DocId values] [fieldnorm IDs for all documents] "rust": [DocId values] ...

After: Fieldnorm array per term

Postings Fieldnorms "database": [DocId values] "database": [fieldnorm IDs] "rust": [DocId values] "rust": [fieldnorm IDs] ... ...

The tradeoff is storage, since a document’s fieldnorm is now repeated for each distinct term it contains. Fortunately, this doesn’t necessarily mean multiplying fieldnorm storage by the number of terms. In real-world corpora, most terms have short postings lists and correspondingly small fieldnorm arrays. For instance, this change grew the 28.7M HN index by about 9%.

Breaking out fieldnorms delivered a huge speedup for queries with a small number of terms, but we were still not satisfied with our performance in disjunction queries with many terms. For instance, this query matches documents containing any of these terms:

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;

In this query, we noticed that even though buffer reads after the previous optimization fell by roughly 80%, query times only dropped by 5%, suggesting that the bottleneck in this case was algorithmic.

We profiled and discovered that most of the time was spent in something called the Blockmax WAND loop.

For context: Blockmax is the standard algorithm used by search engines to efficiently skip past chunks of postings when executing disjunction (e.g. termA OR termB) queries. There are two families of Blockmax: WAND and MAXSCORE. We won’t go into the intricacies of how they work (there are lots of good technical blogs for this), but at a high level:

The tradeoff between WAND and MAXSCORE is how much work they spend deciding what to skip. WAND skips more, but spends more CPU cycles to do so. MAXSCORE skips less, but incurs less overhead. When queries contain more terms, WAND’s overhead grows and can outweigh the work it skips.

Tantivy uses WAND. Lucene also used WAND until 2023, when they introduced MAXSCORE for certain queries. Today, Lucene dynamically chooses either WAND or MAXSCORE depending on the query shape.

We implemented a MAXSCORE path with a simple selection heuristic that uses MAXSCORE for disjunctions with at least three terms and sufficiently dense postings and WAND for everything else. For the query above containing 10 terms, we not only brought p50 latency down by ~6x and p95 by ~8x, we are now 2x faster vs. TIN on our 28.7M HN dataset:

Warm-cache, read-only runs. TIN uses dense_ratio=0.1 with search elision enabled; see Handling Common Terms. One-second buckets; latency uses nearest-rank percentiles. The match selector does not apply to one-term queries. Lines use a centered 9-second moving average; legend values are unsmoothed full-run results.

PlanetScale’s benchmarks were constructed fairly, with the exception of two anomalies that unintentionally favored TIN: a ParadeDB syntax oversight and how TIN handles common terms.

We noticed that the TIN benchmarks used ParadeDB’s query string parser, which accepts Tantivy’s mini query language via the @@@ operator. The problem is that these queries weren’t qualified with a field name, e.g. <query> instead of <field>:<query>.

When queries are unqualified, ParadeDB searches over all indexed text fields by default. In the StackExchange dataset, both the id and body columns were indexed, which means ParadeDB was disadvantaged because it was searching over two columns per query whereas TIN searched only one.

To guard against this, we moved all ParadeDB queries to use our native ||| (disjunction), &&& (conjunction), and ### (phrase) operators.

We were easily beating TIN on the BM25 search queries in our HN benchmark. But when we loaded PlanetScale’s StackExchange dataset and queries, we were still 30% behind on throughput because of our much longer tail latencies. How could we be several times faster on our benchmark but slower on PlanetScale’s?

It turns out the gap came from a scoring shortcut for common terms that TIN calls dense-term elision, and we think its use over the StackExchange dataset specifically is debatable.

A brief explainer: common terms like "the" and "is" have enormous postings lists that are expensive to read and score. Yet BM25 weights them so low that they barely move the final ranking. Most search engines handle this at indexing time with a stopword dictionary (both engines support this, but it wasn't enabled in the benchmark). TIN takes a different approach: at query time, it skips scoring for any term that appears in more than 10% of the corpus (configurable via dense_ratio). It's the most interesting idea in TIN from a search practitioner's point of view, and we will spend more time thinking about this.

Of course there is always a tradeoff, and here it is correctness. With elision on, TIN computes an approximation of BM25 by ignoring common words, causing results to potentially come back in a different order than true BM25 would produce. This usually isn’t a problem for most real-world queries, unless the query is made up entirely of common words.

When we looked at what the Stack Overflow benchmark ran, we were surprised to find entire queries made up of these common words. That’s because they were generated by sampling consecutive word spans from the Stack Exchange corpus, which produced queries like "is it", "to a", and "is to" 4. When we ranked the largest latency gaps between ParadeDB and TIN, those same queries (which are not real search queries) dominated the list. On them, TIN skipped most of the scoring work while ParadeDB computed exact scores.

For TIN, with elision enabled, we found that 5:

To be clear, we’re not saying that "different from exact BM25" automatically means "worse". Elided terms have low weight by design, and determining whether the elided results are less relevant would require human relevance judgments, which this benchmark does not have. But the workload is framed as BM25 top-K search, and with elision