Making COUNTs and the Rest of Search Really Fast (Part II)

By Ming Ying on October 13, 2026 In Part I, we improved ParadeDB’s Top K BM25 performance by orders of magnitude. At the end, we committed to publishing a Part II focusing on COUNT. This post walks through the optimizations that made our COUNT queries much faster. Here’s the end result, using the same Wikipedia dataset and benchmark harness as the original TIN post: Wikipedia COUNT search8 concurrent clients · 5 minute runQueriesViewPercentile↑ Higher is betterClean tables. One-second buckets reconstructed from each worker's ordered raw query timings and measured start/finish interval; latency uses continuous percentiles. Lines use a centered 9-second moving average; legend values are unsmoothed full-run results. First, we’ll explain how we improved COUNT performance. In the second half, we’ll go beyond unfiltered BM25 and simple COUNT queries to test search queries with different filters and sort orders, where ParadeDB is up to 66 times faster. We’ll explain why and discuss what these differences mean when comparing benchmarks and choosing a search engine for your application. But first, let’s dive into making COUNT faster! Optimization 1: Segment Partitioning Below is the simple query we started with: count the number of documents matching the term database. EXPLAIN (ANALYZE, BUFFERS) SELECT COUNT(*) FROM hn_items WHERE text === 'database'; When profiling this query visibility checking accounted for over 80% of our page accesses. This makes sense because for every match, we need to fetch and decode its ctid value (which TIN can skip because its document index is ctid). Data structureShare of page accessesVisibility map + stored CTIDs1382 (81%)Everything else (postings, metadata, etc.)325 (19%) While looking at the query we realised that we could use a (to be announced) feature that we’ve been working on: segment partitioning. ParadeDB and TIN both store data in a structure which is similar to an LSM tree. At a high level this means data is partitioned into immutable segments that are merged together when they reach a size threshold: smaller segments are combined when enough data accumulates to reach the next size tier. A simple naive merging strategy is oblivious to the data contained within the segment, so we can assume that each segment effectively contains a random sample of the dataset. Our new segment partitioning and merge strategy, based on the Spooky LSM compaction paper, lets us split up segments by the values of one or more columns. We’ve been building this for the past few months and will share a technical deep dive soon (the benefits we’re seeing for Top K and joins are huge). For the purposes of this query, the useful part is that we can partition by ctid (Postgres’ internal row identifiers), which gives each segment a disjoint range of Postgres page numbers1: 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 ] Each segment already stores the minimum and maximum ctid.

For our benchmark query, this brought visibility-related page accesses down from 1,382 to just 30. Optimization 2: Inverting Our DocId Map But what about the case when at least one page in a segment’s ctid range does need to be visibility checked? This becomes more likely the further we get from the last (auto)vacuum, and we don’t want a few modified pages to force ctid reads for every match. The TIN blog explains that needing to convert DocIds to ctid values introduces overhead, and that’s true. But what it doesn’t mention is just how efficient a DocId to ctid map can be. Our existing approach stores a ctid for every document and fetches it for every match. Counting n matches meant n ctid lookups: Doc ID: 0 1 2 3 4 5 6 CTID: (10,1) (10,2) (11,1) (11,2) (11,3) (15,1) (15,2) A much more efficient representation is to essentially invert the map: a compressed column that maps a Postgres page numbers (i.e. first number in the ctid tuple) to the first DocId found on that page. This works because our segments are already sorted by ctid, guaranteeing that documents on the same page have consecutive DocIds. 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) With this new format, we can check the visibility map up front, then look up document ranges only for pages that need checking: 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 For the single-term count query above, after updating 1,000 rows, this reduced buffer accesses from over 7,500 to just under 400: a 95% reduction. Optimization 3: Bitmaps are Great for Common Terms Tantivy uses BP128 encoding for its posting lists. BP128 means that the postings array is divided into 128-sized blocks, where each block is bitpacked and delta-encoded.

These blocks also carry the score bounds that let the blockmax algorithm skip uncompetitive blocks during BM25 ranking.

When profiling we found that this representation works well for most terms, with the exception of very common terms that have dense posting lists. For these common terms, we found that intersecting or unioning large BP128 arrays incurred significant overhead, and that representing postings as bitmaps instead made those unions and intersections much cheaper.

To demonstrate the tradeoff between BP128 and bitmaps, consider two scenarios. First, imagine two rare terms that each match 10 out of a million documents. Intersecting their BP128-encoded arrays requires only a handful of comparisons, whereas scanning two equivalent bitmaps means processing a million bits each, most of which are zeroes (i.e.

wasted work).

Next, imagine that the two terms are common, each matching ~500K out of a million documents. That means their arrays are ~500K entries each. In this case, bitmaps can be more efficient because bitwise AND/OR can process 64 documents at a time, versus walking the arrays one entry at a time. We introduced a bitmap representation of postings for sufficiently dense terms matching more than 10% of the documents. This change alone halved p99 latency in our Wikipedia count benchmark. Now for the Rest of Search TIN is very fast at the query shapes it’s optimized for: Top K by BM25 and counts. ParadeDB aims to be an Elasticsearch alternative on Postgres, and from that perspective, BM25 and counts are just the tip of the iceberg when it comes to the queries we see running in production. For instance, consider the following search queries over the Hacker News dataset: 1. Filtered count 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 sustained 777 QPS versus TIN’s 78 QPS, a 10.0x throughput difference. Hacker News COUNT with score filter8 concurrent clients · 5 minute targetViewPercentile↑ Higher is betterClean tables.

One-second buckets reconstructed from each worker's ordered raw query timings and measured start/finish interval. Full-run legend values include batch-completion overrun.

Lines use a centered 9-second moving average; legend values are unsmoothed full-run results. 2.

Filtered Top K by BM25 relevance Give me the Top 10 most relevant posts containing the term "database" AND received more than 10 Hacker News points. 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; Here ParadeDB sustained 820 QPS versus TIN’s 71 QPS, an 11.6x throughput difference. Hacker News Top K with score filter8 concurrent clients · 5 minute targetViewPercentile↑ Higher is betterClean tables. One-second buckets reconstructed from each worker's ordered raw query timings and measured start/finish interval.

Full-run legend values include batch-completion overrun.

Lines use a centered 9-second moving average; legend values are unsmoothed full-run results.

3.

Top K search ordered by time Give me the Top 10 most recent posts containing the term "database". SELECT id, text, "by", score, "time" FROM hn_items WHERE text ||| 'database' ORDER BY "time" DESC NULLS LAST LIMIT 10; ParadeDB sustained 378 QPS versus TIN’s 17 QPS, a 21.7x throughput difference. Hacker News Top K sorted by time8 concurrent clients · 5 minute targetViewPercentile↑ Higher is betterClean tables.

One-second buckets reconstructed from each worker's ordered raw query timings and measured start/finish interval.

Lines use a centered 9-second moving average; legend values are unsmoothed full-run results.

PlanetScale agrees that these queries matter.