Solving Postgres' Count Problem

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:

Clean 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!

These results use a one-off server-side benchmark. Read the methodology or view the benchmark harness.

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).

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. 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.

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.

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.

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:

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.

Clean 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.

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.

Clean 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.

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.

Clean 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. Seconds with no completed TIN query show zero QPS and contribute no latency sample. Lines use a centered 9-second moving average; legend values are unsmoothed full-run results.

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.

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 queri