Variable-width per-tuple blooms — v1.3 design spec

Status: draft, targeting pg_tre 1.3.

Owner: unassigned.

Prerequisite: multi-leaf chain-rank repair — fully resolved in 1.2.3. The struct-vs-bytes bloom-header fix (1.2.2) plus the pending-overlay positional-filter fix (1.2.3) close out the long-running tier-3 bypass. Tier-3 is on by default and works correctly across single-leaf, multi-leaf, and pending-overlay code paths. Variable-width blooms are now an incremental size optimization on top of working tier-3.

Problem

The tier-3 per-tuple bloom is a fixed pg_tre.bloom_tuple_bits = 128 bits per heap row, sized to roughly hold one row's distinct trigrams at a tolerable false-positive rate. Two issues:

1. Wasteful for short rows. A row with 5 distinct trigrams needs <8 bits to keep FP rate below 1%; we burn 128.
2. Saturated for long rows. A row with 200 distinct trigrams in a 128-bit bloom has FP rate ≈ 1.0 — the bloom is useless, and tier-3 still has to read and check it.

Both extremes pay full cost in storage and in the per-row recheck phase.

Proposal

Encode the bloom width per row, sized from the row's distinct trigram count at index-build time. Three categories:

Width is decided once at build time per row. Stored in the posting-leaf payload as:

struct PerRowBloom {
    uint8 width_class;   // 0=empty, 1=16, 2=64, 3=always-pass
    uint8 nhashes;       // hash function count
    union {
        uint16 b16;
        uint64 b64;
        // width_class=0 or 3 carries no payload
    } bits;
}

Average payload:

For a corpus where most rows have <32 distinct trigrams (typical for code identifiers, log lines, SKUs), payload averages ≈4-6 bytes per row vs 16 today. 70-80% payload reduction.

For a corpus of long prose (paragraphs, articles), most rows land in width_class 2 or 3 — comparable to today's flat 128-bit, or smaller.

Read path

pg_tre_posting_lookup_tuple_bloom reads width_class first, then dispatches:

• 0: row matches every query trigram trivially (unlikely; only empty rows).
• 1, 2: dispatch to width-specific bloom check using the right nhashes value.
• 3: skip the bloom check, return "candidate, must recheck".

Why this depends on chain-rank repair

The current chain-rank lookup (in pg_tre_posting_lookup_tuple_bloom) is broken for multi-leaf posting trees: the per-row payload offset is computed from a per-leaf rank that doesn't accumulate across right-link chains. Today this is bypassed entirely via pg_tre.tuple_bloom_enable=false.

Fixing chain-rank means:

1. The chain walker maintains a running TID-count as it traverses leaves.
2. sm_rank on a per-leaf basis returns the local rank; the walker adds it to the running count.
3. The payload offset table (currently per-leaf) becomes a per-leaf-with-base offset, indexed by the global rank.

Once chain-rank works, switching tier-3 default back to true becomes safe. At that point variable-width blooms become a size optimization on top of a working tier-3.

On-disk format compatibility

Adding a width_class byte changes the per-row payload layout. Two options:

Option A (simpler): Bump PG_TRE_FORMAT_VERSION to 4. Existing 1.x indexes need REINDEX. Easy to test, simple upgrade-tests matrix update.

Option B (compatible): Encode width_class in the existing payload region by reserving a sentinel value. Existing fixed-128-bit blooms continue to read with the old code path; new builds emit variable-width. No format bump.

Option B requires careful sentinel-value choice and audit; Option A is cleaner. Since posting-page coalescing (v2.0) is also a format bump, this work might bundle with that and ship in v2.0 instead of v1.3. Decision deferred until chain-rank repair lands and we measure the actual size improvement on a real corpus.

Implementation phases

1. Phase 1 — chain-rank repair. pg_tre.tuple_bloom_enable becomes safe to set true; default still false. Regression tests for the multi-leaf 'the' case (currently masked).
2. Phase 2 — width_class encode/decode. Build path picks width based on row's distinct trigram count. Read path dispatches. No size change yet (still emits 16-byte payload, just with a width tag).
3. Phase 3 — variable storage. Width-1/2 actually emit 4 / 16-byte payloads. Format-version bump or sentinel compatibility shim per the decision above.
4. Phase 4 — re-default tier-3 to true. Once chain-rank and variable-width are correct and measured, flip pg_tre.tuple_bloom_enable default back to true.

Risks

• The chain-rank repair is non-trivial. Touches the scan path's hottest loop (per-row tier-3 lookup). Needs a benchmark before/after; risk of slowdown on the unaffected single-leaf case if the chain accumulator adds branches.
• Build CPU cost. Counting distinct trigrams per row is free at build time (we already accumulate them); width selection is one comparison. Negligible.
• Adversarial inputs. A row with crafted trigram count exactly at the width-class boundary (32, 256) could cause thrashing on rebuild after VACUUM removes tids; pin the width on the highest historical count to avoid oscillation.