Bug report: count(*)’s fast-path visibility gate is O(heap pages), not O(matches)

To: pg_fts maintainers From: pg_weave (a PostgreSQL-licensed fork of pg_fts, forked from pg_fts 1.5.8, 2026-09-05) Affects: pg_fts v1.8.3 (166b0b0), function bm25_count_dictdf_fastpath(), pg_fts_am_scan.c Date: 2026-09-21

This report does not assume you know pg_weave. Every claim below is checkable in your own tree; the line numbers are from pg_fts_am_scan.c as it exists in your repository today (we read it there, not in our fork).

The claim

bm25_count_dictdf_fastpath() answers count(*) for a single plain positive term by (1) summing the term’s document frequency across segment dictionaries, then (2) proving the entire heap is all-visible to the snapshot before trusting that sum as an exact MVCC-correct count. Step (2) is implemented as one VM_ALL_VISIBLE() call per heap block:

heap = table_open(index->rd_index->indrelid, AccessShareLock);
nblocks = RelationGetNumberOfBlocks(heap);
for (blk = 0; blk < nblocks; blk++)
{
    if (!VM_ALL_VISIBLE(heap, blk, &vmbuf))
    {
        all_visible = false;
        break;
    }
}

That is at pg_fts_am_scan.c:4402 in your tree today (the if (!VM_ALL_VISIBLE(...)) line inside the for (blk = 0; blk < nblocks; blk++) loop starting a few lines above it, function bm25_count_dictdf_fastpath, comment block above it says “Gate (4)”). Please verify this yourselves — quote what is actually at that line in your checkout, since line numbers drift across commits.

The cost of that loop tracks the number of heap blocks, not the number of matching documents. A term matching zero documents pays for the same per-block scan as a term matching every document in the corpus, because gate (4) runs regardless of the df computed in gate (earlier), as long as the term has any pending-segment presence check that clears.

The measurement

Host c7i.2xlarge, 1M-document corpus, 87,486-page heap, harness /scratch/pg_weave/g38.sh (ours, not committed to either repository), two passes agreeing to the last digit:

query df latency notes
count(*) rare 25 0.278 ms
count(*) mid 2,505 0.291 ms
count(*) common 196,785 0.278 ms
count(*) no-match 0 0.280 ms

Flat from df 0 to df 196,785. EXPLAIN (ANALYZE, BUFFERS) reported shared hit=8 on every one of these runs — so the ~0.28 ms was never I/O. It was 87,486 function calls to VM_ALL_VISIBLE(), once per heap block, every time, independent of the term.

The tell that found it, because it will generalize to your own regressions: we had an apparent 2.2x slowdown between two benchmark runs (0.43 ms -> 0.95 ms at the same scale) and initially suspected our own code. What ruled that out is that pg_fts v1.8.3 measured 0.94 ms on the same table, in the same run — agreeing with our number to 0.01 ms. Two independently-maintained forks agreeing that closely on a number that looked like a regression is itself evidence the mechanism is shared, not that either fork’s recent changes are innocent by coincidence. The number that actually explained it was not the match-count ratio (df 25 vs df 196,785 — no correlation) but the heap-size ratio: 0.43 ms / 0.95 ms / 3.81 ms at three heap sizes (1,076 MB, 2,357 MB, 9,238 MB — a straight line at roughly 3.2 ns per heap page). If two of your own benchmark runs ever disagree on a count(*) number and the disagreement doesn’t track the query, check whether it tracks the table size instead — that is the signature of this gate.

Why it is a defect, not a trade-off

The path this gate exists to avoid — the ordinary posting-scan count(*) path — answered df 25 in about 0.007 ms in our measurement. So below roughly df 9,000 on an 87,486-page heap, the “fast” path was up to 40x slower than the code it exists to short-circuit, and the crossover point moves with heap size, not with anything a user can see or tune. A term that matches nothing pays the same cost as a term that matches nearly every document — the opposite of what a reader would expect from a function named ..._fastpath.

What we did (for context, not something we are asking you to adopt verbatim)

We shipped two changes: (1) a zero-df early-out — if no segment’s dictionary holds the term at all, the answer is 0 regardless of visibility, so gate (4) never has to run; (2) for the nonzero case, replacing the per-block VM_ALL_VISIBLE() loop with visibilitymap_count(), which reads visibility-map pages and popcounts them, turning an O(heap_pages) loop of function calls into an O(heap_pages / 32672) loop of buffer reads. Measured on a separate, smaller heap (683 MB, not the 87,486-page one above — the two numbers should not be divided against each other), the fixed gate ran flat at 0.003-0.005 ms across every df, a 69-93x improvement on that heap.

The one hazard that swap introduces: visibilitymap_count() counts bits over the whole map, including bits belonging to any block past the relation’s current end, so a count that merely equals nblocks could in principle include stale bits past RelationGetNumberOfBlocks(). We did not just reason our way past this — we ship the old per-block scan as a cross-check under USE_ASSERT_CHECKING, so a debug build re-derives and asserts agreement on every count. Whether that hazard is reachable in your relation-truncation code path is something you would need to check independently; in ours it is not (visibilitymap_truncate() runs inside RelationTruncate()’s critical section under XLOG_SMGR_TRUNCATE), but that reasoning is exactly the kind doc/CONVENTIONS.md in our tree tells us to distrust without a cross-check, which is why the assert exists.

What was NOT measured

  • We did not measure the fixed gate against pg_fts on the same table/heap — the fix was measured on a different, smaller corpus (683 MB) than the one that produced the 0.278-0.291 ms numbers above (87,486-page heap). No post-fix ratio against pg_fts is claimed anywhere in this report.
  • We did not check whether pg_fts has a different code path for count(*) on a negated term, a phrase, or a boolean combination — this report is about the single plain positive term path only, which is what bm25_count_dictdf_fastpath() says it handles.
  • We did not check pg_fts versions before 1.8.3 or any version after it that may exist by the time you read this.
  • We did not profile whether the fix’s visibilitymap_count() approach interacts correctly with your merge/vacuum machinery — that would need to be re-verified in your tree, not assumed from ours, since the two trees' merge/vacuum code has diverged.

What we would need from you

Nothing required. If useful: a confirmation that pg_fts_am_scan.c:4402 (or wherever it has moved to by the time you read this) is the function you’d want a patch against, and whether you want the zero-df early-out and the visibilitymap_count() swap as one patch or two. We are a fork/importer of pg_fts and are happy to send a patch adapted to your current tree if that is useful; we understand you may have already found and fixed this independently, or may have reasons not to want the assert-checked fallback we carry.