Bloom filters are sized by value count, not distinct count: 19.3x over-provisioned, 29% of load time, 361 MB raw against a 262 MB table

[ChronicallyJD]

Problem

PgColumnarBloomBuild sizes each filter from the value count, not the distinct count:

/* columnar_bloom.c */
#define BLOOM_BITS_PER_VALUE 10
#define BLOOM_MAX_BITS (1u << 21)   /* 256 KB cap per chunk */
...
nbits = next_pow2(n * BLOOM_BITS_PER_VALUE);   /* n = number of hashes, not distinct */

A filter is stored per column per stripe, so n is pgcolumnar.stripe_row_limit
(default 150,000). That gives 1.5 Mbit, which next_pow2 rounds to exactly 2^21 —
256 KB for every bloomable column of every stripe, regardless of that column's
cardinality. A column with 5 distinct values gets the same 256 KB filter as a unique one.

Measured on 2M ClickBench hits rows (105 columns), distinct values per 150,000-row
stripe:

distinct per stripe	columns	filter utilisation
< 64	68	~99.98% empty, still 256 KB each
64 – 1k	11	>99% empty
1k – 10k	10	>93% empty
10k – 50k	4	>66% empty
>= 50k	12	reasonably used

Sized by distinct count these filters need 11.4 Mbit; they are allocated 220 Mbit
— 19.3x over-provisioned. (The next_pow2 rounding is a further ~40% on top: 1.5 Mbit
of intent becomes 2.097 Mbit allocated, i.e. 14 bits/value rather than the 10 BLOOM_K = 6
was chosen for.)

Note this is not the n < 64 early-out or the BLOOM_MAX_BITS refusal doing their job —
both test the value count, which is 150,000 here, so neither fires. Every column gets a
filter.

Cost

All arms encode_effort = fast (FSST out of the picture), serial COPY, 2M rows, every
arm asserted at exactly 2,000,000 rows:

arm	load	bloom TOAST written	pglz_compress in profile
bloom on (default)	44.6s	58 MB	10.4%
bloom off	31.7s	0 MB	absent
bloom on, filter SET STORAGE EXTERNAL	40.7s	361 MB	absent

• Bloom costs 12.9s of a 44.6s load — 29%.
• Uncompressed the filters are 361 MB against a 262 MB table — the index is larger than
  the data.

How this was found, and a correction worth recording

This started as "why is pglz_compress at 7.7% when pgcolumnar.compression = zstd?"
Answer: pgcolumnar.bloom.filter is bytea storage=x, so TOAST compresses it with
default_toast_compression, which is stock pglz. Turning bloom off makes pglz_compress
vanish from the profile entirely — that is the caller, established by ablation.

My first hypothesis was that pglz on bloom filters was waste, since bloom filters are
normally high-entropy and near-incompressible. SET STORAGE EXTERNAL refuted it: pglz
takes 361 MB down to 58 MB, a 6.2x ratio, for 3.9s. That is one of the better trades in
the write path and should be left alone.

The 6.2x is the tell: filters compress that well only because they are almost entirely
zeros. pglz was masking the over-provisioning, not causing it. Correctly sized filters
would compress far less and this would never have shown up in a profile.

So: do not change default_toast_compression or the column's storage. (lz4 is not
even available — this build lacks --with-lz4.) The problem is upstream of compression.

Suggested direction

Deduplicate the hashes before sizing. A bloom filter's membership set is the distinct
set, so a filter built over distinct hashes answers every probe identically — this is a
size/time change, not a semantic one. PgColumnarFsstDictWins already has a cheap
open-addressing distinct probe over a corpus that could be modelled on.

Two things to measure before committing, not assume:

1. Does dedup cost more than it saves on the 12 genuinely high-cardinality columns?
   Those are the ones where the current sizing is roughly right and a dedup pass is pure
   overhead.
2. What happens to read-side skip rates? A smaller filter has a higher false-positive
   rate for the same k. Sizing by distinct count at 10 bits/value should preserve the ~1%
   target, but that needs verifying against actual chunk-group skip counts, not arithmetic.

A secondary, independent win: next_pow2 rounding wastes up to 2x. Allocating
ceil(n_distinct * 10 / 8) bytes directly, or rounding to a byte rather than a power of
two, removes that — the modulo-free indexing a power of two buys is not obviously worth 40%
of the space.

Caveats

• One fixture shape (ClickBench hits), which is wide and heavily low-cardinality. A
  narrow high-cardinality table would show much less over-provisioning — possibly none.
• Two foreign CPU-bound backends (2 of 16 cores) were present for all arms equally.
• Bloom sizing is not user-tunable today: pgcolumnar.enable_bloom_filter is on/off only.
  The comment at columnar_bloom.c:101 already anticipates a reloption.

[jdatcmd]

Claiming this (jdatcmd), per the claim-before-code rule.

Confirmed the arithmetic against the code before planning, since the whole issue turns on it. PgColumnarBloomBuild takes n = value count, and both existing guards test it: n < 64 never fires at the default because n is 150,000, and the BLOOM_MAX_BITS refusal only fires above n = 209,715. So next_pow2(150000 * 10) = 2^21 = 256 KB per bloomable column per stripe, cardinality-blind. Your reading is right.

Direction

Dedup before sizing, as you suggest. The load-bearing property is that this is not a semantic change: a bloom filter's membership set is the distinct set, so a filter built over distinct hashes answers every probe identically. That equivalence is what the tests have to prove rather than assume.

Two sub-decisions I would rather settle with you than unilaterally

1. Does the < 64 early-out move to the distinct count? 68 of your 105 columns have < 64 distinct per stripe. If it moves, all 68 lose their filter entirely.

My inclination is no — keep that guard on the value count. A 64-bit filter is 8 bytes and still skips, and a low-cardinality column is exactly where an equality probe skips best: if the value is not among the 5 present, the whole group goes. Dropping the filter there would take the biggest win off the table to save 8 bytes. But it is your issue and your measurement, so say if you read it differently.

2. The MAX_BITS refusal should move to the distinct count. Its stated reason is bits-per-value falling below what BLOOM_K = 6 needs, which distinct sizing fixes. A large stripe of low-cardinality data is currently refused a filter for a problem it does not have.

Seams I intend to test at

	Seam	Observed through
A	pgcolumnar.bloom.filter	octet_length(filter) per column per group — exact, no timing
B	results with bloom on vs off	the equivalence claim
C	skip counters on an equality probe	a filter that no longer skips is worthless at any size
D	load time and TOAST bytes	the 29% claim — the only timing-dependent arm

A is the primary one: the defect is a size, and filter is a bytea in a catalog table, so it is directly measurable without a timing harness. C is the one that matters most adversarially — it is what catches "made the filter small by making it useless", which is the failure mode a size-only test would call a success.

I will assert the relation between a low-cardinality and a high-cardinality column in the same table rather than a literal byte count, so the test does not snapshot today's next_pow2 constants. Premises first on the fixture's actual distinct counts, because a "5 distinct" column that really holds 150k distinct proves nothing.

Noted and not touched

Not changing default_toast_compression or the column storage. Your SET STORAGE EXTERNAL ablation settled that — 361 MB to 58 MB for 3.9s is a good trade. Worth restating your own conclusion because it is counter-intuitive and someone will re-profile this later: the 6.2x ratio is the symptom, filters compress that well because they are nearly all zeros, and correctly sized filters will compress far less. That is expected, not a regression. It goes in the commit message so the next profile reader does not "fix" it back.