ParadeDB cuts Postgres search COUNT cost with ctid partitioning, inverted doc maps and bitmaps

ParadeDB has published the second part of a technical series on search performance, this time focused on COUNT queries over its BM25 full-text indexes. Written by Ming Ying on the ParadeDB blog and surfaced on Hacker News's front page, the post details three optimizations measured on the Wikipedia dataset with eight concurrent clients over five-minute runs, then widens the comparison to filtered and sorted search queries, where ParadeDB claims to be up to 66 times faster than TIN.

The bottleneck: visibility checks

Counting documents that match a term looks cheap, but Postgres must still confirm that each matching row is visible to the current transaction. When ParadeDB profiled a single-term COUNT over its hn_items table, the visibility map plus stored row identifiers (ctids) accounted for 1,382 page accesses, about 81% of the total, while everything else, postings and metadata included, made up the remaining 19%.

ParadeDB and TIN both store their index in an LSM-like layout: immutable segments that merge as they reach size thresholds. Under a plain size-tiered merge policy, each segment effectively holds a random sample of the table, so a segment's minimum and maximum ctid can span nearly every page in the heap.

Splitting segments by page range

The first fix is a new partitioning and merge strategy, based on the Spooky LSM compaction paper, that can split segments by the values of one or more columns. Partitioning by ctid gives each segment a disjoint range of Postgres page numbers. Since each segment already records its ctid minimum and maximum, the engine can consult the visibility map up front and, if every page in the range is marked all-visible, skip per-row visibility checks and their associated page reads for the entire segment.

This also contains the damage from updates: a single modified page can no longer defeat the shortcut for most of the index, only for the one segment covering those pages. In the benchmark, visibility-related page accesses fell from 1,382 to 30.

An inverted document map

Pages that do require checking still force ctid resolution, and that becomes more likely the further the table is from its last vacuum. ParadeDB's previous format stored a ctid per document and fetched one for every match. The new format inverts the mapping: a compressed column maps each heap page number to the first document ID on that page, which works because segments are sorted by ctid, guaranteeing that documents on the same page have consecutive IDs.

With that layout, the engine checks the visibility map first and resolves ctids only for documents on pages that genuinely need checking. In a test run after 1,000 rows had been updated, buffer accesses dropped from more than 7,500 to just under 400, a 95% reduction according to the post.

Bitmaps for frequent terms

The third change targets posting-list encoding. Tantivy, the search library ParadeDB builds on, compresses postings with BP128, which divides the array into delta-encoded, bit-packed blocks of 128 IDs. According to ParadeDB, this works well for most terms but becomes expensive for very common terms with dense posting lists, where intersecting or unioning large BP128 arrays carries significant overhead.

For terms matching more than 10% of documents, ParadeDB now stores postings as bitmaps instead, letting unions and intersections process 64 documents per operation rather than walking arrays one entry at a time. The trade-off is deliberate: bitmaps waste effort on rare terms, where two 10-match postings intersect in a handful of comparisons but two bitmaps mean scanning mostly zero bits. The bitmap switch alone halved p99 latency in the Wikipedia count benchmark.

The wider comparison with TIN

The post acknowledges that TIN is very fast at the query shapes it was built for, namely Top K BM25 ranking and counts. ParadeDB, which positions itself as an Elasticsearch alternative running on Postgres, argues that production search involves much more, including filtered counts and varied sort orders, and it is on those shapes that ParadeDB measures its up-to-66x advantage. A technical deep dive on segment partitioning is promised next, with the company citing large additional gains for Top K and joins.

Why it matters

Filtered counts power facet panels, pagination totals and dashboards, and on large datasets they often run on every request. The post is valuable in three ways. First, it quantifies how much of a search index's work is really Postgres visibility bookkeeping, and shows that index layouts aligned with heap page ranges and the visibility map can eliminate most of it. Second, the page-keyed document map and adaptive posting encoding are concrete techniques any Postgres index developer can learn from. Third, it is a useful reminder that benchmark results depend heavily on query shape, a point ParadeDB itself makes, and one worth keeping in mind whenever search engines are compared on a single workload.