PlanetScale Released Text Search and We Have a Lot to Say (Part I)
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.
An Overview of Text Search, and How TIN Claims to Be Faster
Without Text Index
With Text Index
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.
But Is It All About a Different Document Identifier?
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.
Optimization 1: Reducing Random Access During BM25 Scoring
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:
| Data structure | Share of page accesses |
|---|---|
| Fieldnorms | 1,513 (83%) |
| Everything else (postings, metadata, etc.) | 311 (17%) |
“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 (!).
Before: Shared fieldnorm array
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%.
Optimization 2: Choosing the Right Blockmax Pruning Algorithm
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:
- “Blockmax” comes from the fact that we can partition postings into blocks and for each block precompute and store the maximum possible score that any term from this block could contribute to the final BM25 score.
- A block is skipped if its max score cannot possibly beat the current Top K threshold. WAND and MAXSCORE are two different ways of doing this skipping.
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.
Benchmark Configuration Changes
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.
ParadeDB Syntax
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.
Handling Common Terms
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:
- 47.8% of queries returned at least one result in the Top 10 that was not in the “true” Top 10.
- 6.4% of queries returned results where none of the Top 10 were in the “true” Top 10 — in other words, all the results were wrong.
- Disjunctions were especially inaccurate: at least one non-Top-10 result appeared in the Top 10 for 88.2% of disjunction queries.
| TIN Query Style | At least one result outside the “true” Top 10 |
|---|---|
| Conjunction | 39.9% |
| Disjunction | 88.2% |
| Phrase | 13.8% |
| Overall | 47.8% |
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 enabled, TIN and ParadeDB are not computing the same ranking.
For this reason our headline comparison uses exact BM25 for both engines, with TIN configured with dense_ratio=2. Below we also show TIN's default elision-enabled configuration, where they “beat” us, because that is what the original benchmark used.
We’re sharing both sets of results so readers can draw their own conclusions. We don’t want benchmark settings to distract from the performance improvements we made to ParadeDB. At the same time, we would be remiss not to mention them, as they make such a big difference to the originally published results. For good measure we have also included ParadeDB with stopwords enabled.
Warm-cache, read-only mixed-query runs. One-second buckets; latency uses nearest-rank percentiles. Lines use a centered 9-second moving average; legend values are unsmoothed full-run results.
So Is There a Superior Document Identifier?
As for the choice of TIN’s ctid vs. ParadeDB’s u32 document identifiers, we see it as a tradeoff as well.
A premise of the TIN post is that ctid values are a universally good choice for postings lists. The problem with this is that nothing compresses better than dense, sorted, unique integers. Consequently, most search systems use u32 DocId values. Switching to a 48-bit document identifier is not inherently more efficient, especially since the 48 bits in a ctid are the concatenation of numbers from two different domains (block numbers, numbered in the millions, and tuple offsets, at most 291).
Dense u32 DocId values have another advantage: they make it easy to connect postings to columnar storage. Postings tell you which documents match; columns let you efficiently access those documents’ metadata attributes (like numeric values or category labels).
Column stores are often associated with OLAP databases, but they’re also crucial for search queries:
- Top K by field: “Give me products matching my query, ordered by price.”
- Range filters: “Give me matching products between $50 and $100.”
- Faceting: “Give me the top 10 products, and facet by the number of matches in each category.”
All of these search queries require a columnar format. With DocId values, the connection is straightforward. Within a segment, document 42 corresponds to row 42 in each column. Once a postings list gives us that ID, we can look up its columnar value directly.
A ctid doesn’t give us that column position. It identifies a physical Postgres location, such as page 190, slot 17. To retrieve that document’s price from a column, we first need to determine which column row corresponds to (190, 17). That requires a mapping or an equivalent lookup.
TIN is great at BM25 scoring and document counting, but that’s just the tip of what makes up a search engine like Elasticsearch. For the “rest of search”, you need a columnar representation. If TIN decides to make one, we suspect they’ll have to pay the same ctid/DocId translation cost (but in the reverse direction).
Why Tantivy Remains the Right Choice for Us
TIN’s post attributes its performance advantage to using ctid values instead of DocId values. But we closed the gap without changing our document identifiers by:
- Writing denser data structures with better locality.
- Using a Blockmax algorithm with higher throughput.
- A few other small optimizations related to lazy reading of other pieces of data.
Most of these changes happened in Tantivy, our search library.
Over the past few years we’ve often debated whether building on Tantivy was the right choice for ParadeDB, versus what appears to be the TIN approach of writing a new search engine from scratch. This investigation has reinforced our belief in our decision to use Tantivy. It brings over a decade of development, battle testing by some of the world’s largest companies, and remarkable speed. Tantivy doesn’t always mesh perfectly with Postgres’ block layout right off the shelf, but its extensibility and features more than make up for that.
You might ask: why hadn’t we done these optimizations already? Performance work never ends, and our engineering resources are finite. After reaching Elasticsearch parity on our text search benchmarks, we shifted our attention toward expanding ParadeDB’s capabilities beyond “just text search” into efficiently executing search queries that involve complex filters, facets, and joins. By now our search API is very broad, so we’re glad that TIN brought our attention to this opportunity for core optimization.
Closing Thoughts
The open source search community has a longstanding tradition of collaboration. For instance, despite being competitive search libraries, Lucene and Tantivy frequently share ideas and benchmark against each other in a friendly way. We explored how this benefits both projects in our conversation with Paul Masurel, creator of Tantivy. We hope this becomes another example of this. It’s been a fun sprint for us.
We appreciate that the TIN authors shared some of their engineering decisions in their blog, even if the project itself isn’t open source. All of our work is open, and we’ve already begun to upstream the relevant improvements from this spike to Tantivy.
We’ve cut a 0.26.0-rc.2 release candidate so these results are reproducible. For existing ParadeDB users, these improvements will be folded into the next stable release, 0.26.0, targeted for next week. We’ve made sure that these changes are backwards compatible, although a reindex will be required to inherit all the optimizations.
To our community contributors: this investigation was time-boxed, and we think there are many more optimization strings to pull on (especially in the direction of more efficient Blockmax pruning and reducing buffer access). We welcome any contributions that push the performance frontier further.
In the next part we’ll discuss the optimizations we made around our COUNT performance (hint: they also didn’t require changing our document identifiers). Until then, happy searching! We’re excited to deliver faster text queries to the Postgres and search communities.
Footnotes
Footnotes
-
And especially Eric ZomboDB, who used to work for ParadeDB and drove the PlanetScale TIN product. ↩
-
Or as close as we could get. TIN is not open-source so we had to run on PlanetScale’s cloud using an 8 CPU / 32 GB / NVMe instance. ParadeDB was deployed on a similarly sized machine of the same EC2 family, in a Docker container. ParadeDB had ~1 millisecond less network latency. We kept the same settings as in the PlanetScale benchmarks, changing only the ParadeDB version, the ParadeDB index creation flags, and the TIN
dense_ratiosetting (more on this in the post). We used the PlanetScale fork of benchmarker to run the benchmarks, but we intend to pull back the features into our own. ↩ -
It’s also possible that this is not fine in MMAP, since MMAP also uses 4 KB pages at the OS level. ↩
-
Our HN dataset does not suffer from this because we only combine words from a list of interesting words. This has issues too, the gold standard is a domain specific corpus with a list of things that people have actually typed in. ↩
-
We obtained these measurements by comparing the results produced by TIN with
dense_ratioset to0.1versus2(disabled). We define the “true” Top 10 as the results produced by TIN without dense-term elision and assume those results are correct. ↩