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:

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 it’s document index is ctid).

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 numbers¹:

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. With this layout, we can check that range against the visibility map up front. If every page in the range is marked all-visible, we can skip visibility checking (and all the visibility-related page reads) for that entire segment altogether.

With pure size-tiered compaction, those ctid min/max ranges can span most of the table. A single updated page can defeat the shortcut for most segments. Partitioning by ctid confines that effect to the segment covering the affected pages, so that other segments can continue skipping per-row checks.

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.

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.

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;

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.

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;

SELECT id, text, "by", score,
       tin.score(ctid, dense_ratio => 0.1) 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.

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;

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.

PlanetScale agrees that these queries matter. To quote their own blog post:

“A good text index in Postgres must support all of those things while also handling joins, complicated WHERE clauses across full-text and other column types.”

TIN isn’t very fast at these filtered and time-sorted queries yet. But because their Wikipedia and StackExchange workloads only contain a single indexed text column, they do not expose this gap. Real application tables are wider: search results are commonly filtered by metadata values or ordered by fields like timestamps or numeric values.

Which brings us to a broader point: the workload you pick often determines the story you tell. When we first introduced our benchmarker, we explained that we built a tool that could accommodate any workload. PlanetScale designed one where TIN excelled. We appreciated that it exposed blind spots in our BM25 and count performance and rigorously drove optimizations over those queries.

But even though ParadeDB is faster on the queries above, we do not believe it establishes a “fastest search engine,” on Postgres or otherwise. No single benchmark can, especially one designed by the same team building the product. That applies to ParadeDB’s Hacker News benchmark just as much as PlanetScale’s StackExchange and Wikipedia benchmarks.

The only way to find out what’s fastest for you (the reader) is to test your own queries on your own data. There are many search query shapes and our goal is to accelerate as many of these shapes as possible. If search with filters, sorting, or facets are frustratingly slow on your current database, try running them on ParadeDB.

Is There a Fundamental Architecture Difference?

TIN’s launch post attributed its performance advantage to its choice of document identifier. As we explained in Part I, we were skeptical. But we do think there exists a deeper, fundamental architecture difference that explains the gap on these more complex queries: how much of the query can be pushed down to the index.

TIN is explicitly a text-only index. Each index covers one text column, leaving non-text filters to Postgres and its other indexes. For the queries we ran where we filtered by a numeric value or sorted by time, TIN relies on B-tree indexes over those non-text columns. On the other hand, ParadeDB is able to index all of those columns together in one index.

That distinction matters for both filtering and sorting. For queries with both text and non-text filters, the TIN and B-tree indexes must independently produce all their matches before they are combined. This misses opportunities to avoid large amounts of work: the B-tree doesn’t know which documents match the text query, so it can collect millions of matches that the intersection will later discard. For other sort orders, such as sorting by time, TIN cannot coordinate text matching with time ordering. Postgres must order the matches outside the index rather than letting the search track the newest 10 matches as it goes.

Modern engines like ParadeDB (and Elasticsearch) solve this problem by storing text and metadata structures together, keyed by the same document identifier. That lets query execution coordinate text matching, filtering, and ordering as it goes, instead of materializing large independent candidate sets and combining them afterward. For a deeper dive, see How We Optimized Top K in Postgres.

The index definitions used for these runs make the difference clear. ParadeDB keeps the searchable text and the fields used for filtering and ordering in one index:

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 indexes text separately and uses B-trees for the other fields:

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

Closing Thoughts

Part I stirred up more reactions than we anticipated. We’d like to reiterate something we wrote at the end of that post: the open source search and database communities have a longstanding tradition of friendly collaboration and competition. Projects like Lucene and Tantivy are constantly trading ideas and besting each other on performance, yet there is zero animosity because it pushes the frontier forward and makes real world applications faster. As committers to Tantivy we share that ethos.

We saw that TIN improved its BM25 performance in response to Part I and we’d like to extend another round of kudos to the team. We’re happy to do another round of comparisons once the new version becomes available.² In the meantime, the search space is vast, exciting, and we look forward to seeing what other databases and search engines tackle next.

If you’d like to test these queries on your own data, you can run ParadeDB locally using our getting-started guide.