[Ideas] Bloom filter performance: four experiments

[leborchuk]

Description

Anser (gpcontrib/anser/) builds one bloom filter per segment over a
join-build key, ships each part to the coordinator over the dispatch
connection, unions them there, and pushes the merged filter back to every
segment. See gpcontrib/anser/README.md for the architecture first.

Four separate performance questions have accumulated about that path. Each is
independent and each is a research task: the deliverable is a report with
numbers and a recommendation, not a patch. Code is welcome as evidence, but
"we measured X, therefore do Y" is the output we want. A negative result is a
successful outcome and must be reported with the same rigour as a positive
one: "we tried this, it gained 0.8%, not worth the complexity" is valuable and
closes the question permanently.

Read "The benchmarks" before starting any of them.

The current implementation, in facts

Aspect	Anser today	Where
sizing target	2 bytes (16 bits) per key	bloom_create(), src/backend/lib/bloomfilter.c:96-101
bitset floor / cap	1 MB floor, 64 MB cap	same, plus ANSER_RF_MIN_BYTES / ANSER_RF_MAX_BYTES (gpcontrib/anser/src/anserplan.c:48-49)
bitset rounded	down to a power of two	my_bloom_power()
hash functions	optimal_k() = round(0.693 × m/n), capped at 10	bloomfilter.c, MAX_HASH_FUNCS
per-element cost	one hash_any_extended() + k cheap derivations + k random bitset accesses	k_hashes()
union of parts	for (i…) abits[i] |= pbits[i]; — one byte at a time	AnserBloomFoldPartInPlace() (src/anserfilter.c:126)
where the union runs	in the QD backend, from the dispatcher's notify handler, on a plain palloc'd accumulator — no shared memory, no DSM, no lock	anser_disp_apply_part() (src/anserdispatch.c:302)
wire format, segment → QD	text header + base64 body (a NOTIFY payload must be a NUL-free string)	anser_sideband_format() (src/ansersideband.c:389)
wire format, QD → segment	raw binary (pqPutnchar does no conversion)	anser_disp_push() (src/anserdispatch.c:394)
give up early	never	—

The measured baseline

A traced exchange, 3-segment demo cluster, 1 MB filter, from the anser.debug
log:

t (ms)	Event
0.0	3 producers build their filters
8.7 – 10.0	all 3 published
10.2	3 consumers subscribe and block
16.8 / 24.0 / 31.4	coordinator folds part 1 / 2 / 3
31.4	complete, delivering
33.2 – 34.0	all 3 consumers hold the filter

34 ms end to end. The parts were sent within 1.3 ms of each other but
folded ~7.2 ms apart, so roughly 21 ms — 60% — is the coordinator picking
parts up one at a time, gated by the interconnect wait loop. A 1 MB fold is
~0.1 ms. Keep those proportions in mind: they decide which of the four tasks
below can possibly matter.

Cloudberry already answers three of these questions differently

The core runtime filter (src/backend/executor/nodeRuntimeFilter.c) uses
bloom_create_aggresive() (bloomfilter.c), and its choices are the opposite
of Anser's:

	Anser (bloom_create)	core RF (bloom_create_aggresive)
bits per key	16	9 (total_elems * 9 / 8 bytes)
floor / cap	1 MB / 64 MB	128 KB / 2 MB
hash functions	up to 10 (optimal_k)	2 or 3, hard-coded, "balance false positive rate and calculation costs"
refuses to build	never	when bits_per_elem < 1.6 → returns NULL, "too many elements"
abandons mid-build	never	yes: inner_threshold = bloom_total_bits(bf) / 1.6, then build_suspend = true (nodeRuntimeFilter.c:246,311)

Start every task by explaining why Anser differs from this, and treat the
aggressive profile as a candidate answer that someone in this codebase already
committed to. Do not invent new thresholds before measuring against that one.

The benchmarks

Every task reports results from the same three levels. Level 2 and Level 3 are
mandatory; Level 1 is mandatory only for tasks 2.1 and 2.3.

Reports go in gpcontrib/anser/doc/performance.md, following the structure of
contrib/pax_storage/doc/performance.md (Environment → SQL report → Summary),
which is the existing convention in this repo. Use milliseconds and give a
min–max spread; several of these effects are single-digit percent and the PAX
report's whole-second granularity would hide them.

Build discipline (most common way to waste a week)

• Never benchmark a build configured with --enable-cassert. Assertions
  make PostgreSQL 20-40% slower and distort exactly the kind of tight loop you
  are measuring. Configure a separate optimized build (-O2, no cassert) and
  paste the configure line into your report.
• Record compiler and version. Auto-vectorization differs between GCC and Clang
  and between versions; a result without a compiler version is not reproducible.
• Pin a baseline commit hash and re-measure the baseline in the same session
  as the variant. Never compare against numbers from yesterday's machine state.

Level 1 — micro-benchmark (C, SQL-callable)

Add benchmark helpers next to the existing anser_test_bloom_* functions in
gpcontrib/anser/src/anser_test.c, so anyone can reproduce a number with one
SELECT. Suggested signatures:

SELECT anser_test_bench_fold(bitset_bytes int4, iters int4);      -- ms per union
SELECT anser_test_bench_add(total_elems int8, payload_bytes int4, -- ms per 1M adds
                            nkeys int4);
SELECT anser_test_bench_probe(total_elems int8, payload_bytes int4,
                              nkeys int4, nprobes int4);          -- ms + observed FPR
SELECT anser_test_bench_frame(bitset_bytes int4, density_pct int4,
                              framing text);                      -- ms + wire bytes

Keep them out of the regression expected output — they are nondeterministic and
meant for manual runs.

Level 2 — the simple benchmark (always run this)

One hash join, three knobs, no other moving parts. This is the harness for all
four tasks — do not invent a different one per task.

-- Setup (per cell).  build side is distributed by a non-join column so the
-- join key must be redistributed, which is the shape the plan pass targets.
CREATE TABLE bench_build (id bigint, pad text) DISTRIBUTED BY (pad);
CREATE TABLE bench_probe (id bigint, pad text) DISTRIBUTED BY (id);

-- knobs:
--   BUILD_KEYS  distinct keys on the build side
--   PROBE_ROWS  rows scanned on the probe side
--   KEY_SPACE   probe id range; match_pct = BUILD_KEYS / KEY_SPACE
INSERT INTO bench_build
  SELECT g, repeat('b', 16) FROM generate_series(1, :BUILD_KEYS) g;
INSERT INTO bench_probe
  SELECT (g % :KEY_SPACE) + 1, repeat('p', 16)
    FROM generate_series(1, :PROBE_ROWS) g;
ANALYZE bench_build;
ANALYZE bench_probe;

-- Measure (repeat 6x, discard the first)
SET enable_nestloop = off; SET enable_mergejoin = off;
\timing on
SET anser.runtime_filter = off;   -- baseline
SELECT count(*) FROM bench_build b JOIN bench_probe p ON b.id = p.id;
SET anser.runtime_filter = on;    -- variant
SELECT count(*) FROM bench_build b JOIN bench_probe p ON b.id = p.id;

Cells — 9 per variant, PROBE_ROWS fixed (100 M; use 20 M while iterating):

	match 1% (KEY_SPACE = 100×)	match 50% (2×)	match 99% (1.01×)
BUILD_KEYS = 10 000
BUILD_KEYS = 1 000 000
BUILD_KEYS = 20 000 000

10 000 is deliberately below the 1 MB bitset floor, 1 M is just above it, 20 M
is where the 64 MB cap and cache residency bite. A change that only moves the
middle row is a change that only matters sometimes — say so.

Per cell record: query time (median of 5, plus min–max), consumer wait,
coordinator fold/pickup time (anser.debug gives both today), rows pruned,
observed FPR, wire bytes, peak memory.

Level 3 — TPC-DS (the number that decides it)

Scale factor 100 minimum. SF 1 and SF 10 are not acceptable evidence: the
tables fit in memory, the filter is pure overhead, and the result tells us
nothing about production. Use SF 1000 if the hardware allows, and state the
cluster shape (hosts × segments per host).

Use whichever TPC-DS harness the team already runs (or the official kit from
tpc.org — dsdgen / dsqgen). State the harness and its version, and commit
the DDL, distribution keys and query set you used under
gpcontrib/anser/doc/bench/ so the run is reproducible. A TPC-DS number without
the DDL is not reviewable — distribution keys alone can swing results 2×.

Step 1 — find out which queries Anser even touches. The plan pass only
injects into one join shape, so most of the 99 queries will be untouched and
their timings are noise. Establish the injected subset first:

for q in $(seq 1 99); do
  n=$(psql -d tpcds -c "SET anser.runtime_filter=on;" \
           -c "EXPLAIN (COSTS OFF) $(cat query${q}.sql)" 2>/dev/null \
      | grep -c 'Anser Bloom Consumer')
  echo "query$q injected=$n"
done

Report that list — it is a result in its own right, and if it is empty, stop and
open a bug instead of benchmarking. Expect the star-schema fact/dimension joins
(q3, q7, q13, q17, q19, q25, q29, q42, q43, q46, q52, q55, q64, q68, q72, q79,
q88, q96, q98 are the usual candidates), but use your measured list, not this
one.

Step 2 — run the full suite, 3 iterations, anser.runtime_filter off then
on, everything else identical. Report per-query medians.

Step 3 — report in three parts:

1. Injected queries — the detail table:

Query	baseline (s)	variant (s)	Δ%	consumer wait (ms)	rows pruned
q19

2. Non-injected queries — one line: worst regression observed, and the count
   of queries outside ±2%. This is the safety check; a feature that speeds up
   15 queries and slows 30 others is a net loss.

3. Summary — total suite time and geometric mean across all 99, baseline
   vs variant. Geomean, not arithmetic mean: one 300 s query otherwise drowns
   out twenty 2 s ones.

Setup for this run: shared_preload_libraries='anser' and
anser.enable=on, cluster restarted. No CREATE EXTENSION is needed — the
subsystem creates no catalog objects. Verify injection with the Step 1 loop
before trusting a single timing. optimizer (ORCA) is on by default and TPC-DS
is normally run with it; Anser injects post-plan for both optimizers, so report
which you used, and both if you have time.

Runs and statistics

• ≥ 5 runs per cell. Discard the first (cache/page-cache warm-up) and say
  that you did.
• Report median and min–max (or p95). Never a bare mean, never a single
  run.
• If median differences are inside the min–max spread, the honest conclusion is
  "no measurable difference" — write that, do not pick the favourable run.

Environment matters differently per task

• Task 2.2 (framing/compression) cannot be evaluated on a single-host demo
  cluster: segment→coordinator traffic goes over loopback at ~10+ GB/s and
  compression will always look worthless. Use a real multi-host cluster, or
  emulate a link with tc qdisc … netem rate 1gbit delay 1ms and report the
  emulated bandwidth/latency. State which you did.
• Tasks 2.1/2.3 are memory-bandwidth and cache sensitive: report CPU model, core
  count, L2/L3 sizes, RAM, and segment count per host.

Report format

One markdown section per task under gpcontrib/anser/doc/performance.md:

## Question
One sentence.

## Setup
configure line, compiler, commit, CPU/RAM/cache, cluster shape, table DDL +
row counts, GUCs changed.

## Method
What you changed, how you measured, how many runs, what you discarded.

## Results
The table. Absolute numbers AND percentage vs baseline.

## Interpretation
Why the numbers look like that. Name the bottleneck you believe you hit and
the evidence for it (perf output, bandwidth math, cache size, etc.).

## Recommendation
Adopt / adopt with conditions / reject — and the one-line reason.

## Limits
What you did not test and what could change the answer.

Attach the raw numbers as CSV in the PR so someone else can re-plot them.

Decision rule

Propose "adopt" only if, on the matrix above:

• median end-to-end improvement ≥ 5% in at least one workload class, and
• no workload class regresses by > 2%, and
• correctness is unchanged: the filter must never reject a row that joins
  (measure the false-negative rate — it must be exactly 0).

If a change is a wash end-to-end but strictly reduces resource use (memory,
wire bytes, coordinator time) with no regression, say so — that can still be
worth adopting, and the decision is ours to make from your numbers.

---

Task 2.1 — Is the bitwise union worth vectorizing?

Question. AnserBloomFoldPartInPlace() (src/anserfilter.c:126) ORs the
bitsets one byte at a time. Should it use wider words or SIMD?

Read the baseline first. In the measured trace, folding a 1 MB filter costs
~0.1 ms out of a 34 ms exchange, while pickup latency costs ~21 ms. Unless
task 2.3 leaves us with much larger filters, this task is very likely a
two-paragraph negative result, and that is a perfectly good outcome. Do it
early and cheaply so nobody optimizes it on instinct later.

Do this before writing any intrinsics: determine whether the compiler
already vectorizes that loop. Build with -fopt-info-vec-optimized (GCC) or
-Rpass=loop-vectorize (Clang), or disassemble and look for
por/vpor/vmovdqu. Report what you find.

Then do the bandwidth arithmetic. A fold of an N-byte bitset touches 3N
bytes (read accumulator, read part, write accumulator). At ~10 GB/s that is
~19 ms for a 64 MB filter and ~0.3 ms for a 1 MB one, per fold, and there are
(segments − 1) folds. If your measurement is close to the bandwidth bound, no
instruction-level change can help and the report should say so.

What is no longer true. Earlier drafts of this issue said the fold ran while
holding AnserChannelLock in EXCLUSIVE mode, stalling the whole subsystem. That
was the shared-memory design. The union now runs in the QD backend on a private
palloc'd buffer with no locking at all — but still on the query's critical
path, inside the dispatcher's notify handler, which is reached from the
interconnect wait loop. So the cost to report is added latency to the
coordinator's tuple reception, not lock contention.

Required numbers: fold time vs bitset size (1 MB, 8 MB, 64 MB) for
byte loop / uint64 loop / SIMD (if you write it); measured GB/s; end-to-end
effect; and the fold's share of the whole exchange.

Depends on task 2.3 — if we shrink filters, this becomes even less
relevant. Consider doing 2.3 first.

Task 2.2 — Framing and compression on the QE → QD leg

Question. A NOTIFY payload must be a NUL-free C string, so parts are
currently base64 — a flat +33% on the biggest thing we send. Can we do
better?

gpcontrib/../plans/anser-payload-framing-considerations.md (this repo, if
still present) collects the reasoning; the short version:

• Only one direction needs framing. QD → segment already ships raw binary
  via pqPutnchar. Only segment → QD is text-constrained — and that is the leg
  sent once per part, while the merged payload is sent once per consumer.
• Binary is actually safe on this connection. pq_sendstring calls
  pg_server_to_client(), which short-circuits when client and database
  encodings match, and the dispatcher sets exactly that on every QD→QE
  connection (src/backend/cdb/dispatcher/cdbconn.c:227-229). So a byte-stuffing
  scheme such as COBS (≤0.4% overhead, pointer-walk decode) is legal where
  base64 costs 33%. Because that is an invariant of connection setup rather than
  a protocol guarantee, any implementation must assert it and fall back to
  base64 rather than silently corrupt a filter.
• A loaded bloom filter is ~50% ones — maximum entropy, incompressible. zstd
  would burn ~110-160 ms on 64 MB to save nothing. Compression only pays when
  the filter is sparse, which happens because of the 1 MB floor or an
  over-estimated total_elems. So measure a bit-density histogram over a real
  workload before choosing any codec.
• Preferred candidate: block-sparse framing. Split the bitset into fixed
  blocks (512 B or 4 KB), send a bitmap of non-zero blocks plus only those
  blocks. One linear scan, no codec, no dependency — and it stays OR-able, so
  the coordinator can fold straight from the wire format into its dense
  accumulator, touching only non-empty blocks. A zstd payload cannot do that: it
  must be decompressed to dense first, reintroducing a full-size copy.

Required numbers: bit-density distribution over the Level-2 matrix; then
encode + decode + fold together, at 1 MB and 8 MB bitsets, at densities
1% / 10% / 50%, for raw+base64, raw+COBS, block-sparse+COBS,
zstd1+COBS. Report wire bytes and CPU separately, plus fold-from-wire versus
fold-from-dense. Then the end-to-end effect on a realistic link.

Remember the loopback trap — this task is invalid on a single-host cluster.

Task 2.3 — How many bits per key do we actually need?

Question. Anser uses 16 bits/key with up to 10 hash probes. The core
runtime filter uses 9 bits/key with 2-3 probes. Which is right for Anser, and
should the cap be 64 MB or 2 MB?

Why this is likely the highest-value task of the four. Fewer bits/key
shrinks memory, wire bytes, base64 cost, pickup latency (fewer bytes to move)
and union time proportionally — and cuts hash probes per probe row. Because
k_hashes() costs one real hash plus k random accesses into the bitset, and
a 64 MB bitset does not fit in cache, the per-row cost is roughly k cache
misses. Going from k=10 to k=3 on a large probe side is potentially a
several-fold reduction in probe cost, entirely separate from the memory saving.
Measure it directly: probe throughput (rows/s) as a function of bitset size and
k, including a size that fits in L2/L3 and one that does not.

Variants to measure: 16/10 (baseline), 12/8, 9/3 (the core profile), 8/6,
4/3. Plus caps 64 MB vs 8 MB vs 2 MB.

Required numbers, per matrix cell: query time; observed FPR (measure, do not
compute); rows pruned; probe throughput; wire bytes; fold time; pickup latency;
false-negative rate (must be 0).

Watch out for: the 1 MB floor and power-of-two rounding making small cases
insensitive; and the fact that a worse FPR only matters where it changes how
many rows survive to the join — a 2% FPR on a filter that prunes 99% of rows is
almost free, on a filter that prunes 5% it is noise on noise.

Task 2.4 — When should we stop building a filter?

Question. Anser always builds and always publishes. When the build side
turns out much larger than estimated, the filter saturates, the FPR approaches
1, and every segment pays memory + wire + wait time for a filter that prunes
nothing. When should a producer give up?

Prior art to measure against, not replace: the core runtime filter suspends
its build at bloom_total_bits / 1.6 elements and refuses to create a filter
below 1.6 bits/key (~47% FPR). Evaluate that exact rule on Anser's workloads
first, then argue for a different threshold if the data supports it.

Design questions your report must answer:

• What is the trigger? Rows added exceeding a multiple of the estimate;
  measured bit density crossing a threshold; or elapsed build time. Which
  correlates best with "the filter turned out useless" in your data?
• What happens after the trigger? Anser has an existing, tested path:
  publish a cancel (ExecAnserBloomFilterProduceCancel() in
  src/anserbloomproduce.c), which marks the channel cancelled and makes every
  consumer fail open. Note this is all-or-nothing per channel — one segment
  abandoning kills the filter for all of them. Is that right, or should a
  saturated part still be published? Argue from numbers.
• How bad is a wrong decision? Measure the cost of abandoning a filter that
  would have been useful (lost pruning) against the cost of not abandoning one
  that was useless (wasted wait + bytes + memory). The asymmetry decides how
  aggressive the threshold should be.

Required numbers: for build sides at 1×, 5×, 20×, 100× the planner estimate
— query time with today's always-build behaviour, with the core RF rule, and
with your proposed rule; plus observed FPR and rows pruned in each. Include at
least one case where the estimate is too low by 100×, since that is the case
this task exists for.

Suggested order

1. 2.3 (sizing) — biggest expected effect, and its answer changes 2.1 and 2.2.
2. 2.4 (abandonment) — independent, self-contained, clear win/no-win answer.
3. 2.2 (framing) — needs the density data and a realistic network.
4. 2.1 (vectorization) — do the "is it already vectorized?" check early (an
   hour); full work only if filters stay large after 2.3.

The per-node wait times from the instrumentation issue make all four easier to
report. anser.debug already gives publish / fold / delivery / receive
timestamps today, which is enough to get started.

Definition of done (per task)

• Report in the format above, every matrix cell filled, raw CSV attached.
• configure line, compiler version, commit hash, hardware, cluster shape.
• Median of ≥5 runs with spread; first run discarded and stated.
• False-negative rate measured and equal to 0 for every variant.
• An explicit Adopt / Adopt-with-conditions / Reject recommendation, with
  the decision rule applied to your own numbers.
• If you wrote code: a branch or draft PR referenced from the report. It
  does not have to be merge-ready.

Use case/motivation

No response

Related issues

#1942

Are you willing to submit a PR?

• Yes I am willing to submit a PR!