GitHub user leborchuk created a discussion: [Ideas] Bloom filter performance: four experiments
### Description This is a **research issue**. The deliverable for each task is a short 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. Each of the four tasks below is independent and can be a separate PR/report. Read "How to produce results we can act on" 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` in `gpcontrib/anser/src/anserplan.c:50-51` | | 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`, `optimal_k()` | | 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()`, `gpcontrib/anser/src/anserfilter.c` | | union lock | runs while holding `AnserChannelLock` **EXCLUSIVE** | `AnserStorePayloadDSM()`, `gpcontrib/anser/src/anser.c:1868` (the `Assert`) | | wire format | raw header + raw bitset, uncompressed, binary bytea | `AnserBloomSerializePart()`, sent by `anserclient.c` | | give up early | never | — | ### 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. ## How to produce results we can act on This section is the actual hard part of this issue. Results that don't follow it will be sent back, not because of process for its own sake, but because we cannot make a shipping decision from them. ### 1. Build discipline (most common way to waste a week) - **Never benchmark a build configured with `--enable-cassert` or `--enable-debug` only.** 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 the 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. ### 2. Measure at two layers, always both | Layer | How | Answers | | --- | --- | --- | | **Micro** | a SQL-callable C benchmark added to `gpcontrib/anser/src/anser_test.c` (follow the existing `anser_test_bloom_*` helpers), e.g. `anser_test_bench_fold(bytes, iters)` returning elapsed ms | "is the OR faster?" | | **End-to-end** | query wall time on a demo/real cluster, TPC-DS with SF=100 | "does the query get faster?" | A micro-benchmark win that does not move end-to-end time is a **negative result** — report it as such. That happens constantly and is fine. Keep benchmark helpers out of the regression expected output; they are nondeterministic. They are for manual runs. #### Notes about TPC-DS **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). You could use special extension to run TPC-DS https://github.com/avamingli/pg_tpcds **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: 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_fi 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) | | --- | --- | --- | --- | --- | --- | | q19 | | | | | | 2. *Non-injected queries* — one line: worst regression observed, 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 al vs variant. Geomean, not arithmetic mean: one 300 s query otherwise drowns out twenty 2 s ones. ### 3. Vary one thing at a time, across a data matrix Minimum matrix per task (9 cells; more if cheap): - **build side distinct keys**: 10 K (below the 1 MB floor), 1 M, 20 M - **probe selectivity** (fraction of probe rows that actually join): ~1%, ~50%, ~99% Selectivity is not optional. A filter that prunes 99% of rows and one that prunes 1% have opposite cost/benefit, and a change that helps one can hurt the other. Report every cell, including the ones where your change loses. Also state probe row count and whether keys are uniform or skewed. ### 4. 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. ### 5. Environment matters differently per task - Task 2.2 (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. ### 6. Report format One markdown comment (or file under `gpcontrib/anser/doc/bench/`) per task: ``` ## 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 (see below). 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. ``` ### 7. 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, network bytes, lock hold 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()` ORs the bitsets one *byte* at a time. Should it use wider words or SIMD? **Do this first, 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 the function and look for `por`/`vpor`/`vmovdqu`. Report what you find. If it is already vectorized, hand-written intrinsics will gain ~nothing and the task is a two-paragraph negative result. **Then do the bandwidth arithmetic and check whether you are even compute-bound.** 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. **The finding that probably matters more than SIMD.** That loop runs while holding `AnserChannelLock` in EXCLUSIVE mode (`anser.c:1868`), so a 64 MB fold stalls *every* Anser operation cluster-wide for the duration. Measure the lock hold time (`pg_stat_activity` wait events, or time the region directly) and report it. If it is significant, the valuable change is restructuring so the OR happens outside the exclusive section — a much bigger win than instruction selection, and a design question worth its own issue. **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; lock hold time; end-to-end effect. **Depends on task 2.3** — if we shrink filters to 2 MB, this task may become irrelevant. Consider doing 2.3 first. ## Task 2.2 — Should parts be compressed on the wire? **Question.** Parts travel uncompressed. Would Golomb/Golomb-Rice coding (a Golomb-coded set) or a general-purpose codec pay off? **Start by measuring bit density**, i.e. the fraction of set bits in a real part. This determines the whole answer and takes an afternoon: - A bloom filter loaded to its design point is **~50% ones — maximum entropy, essentially incompressible.** No codec will help there. - Anser filters are frequently *far* below their design point, because of the 1 MB floor and because `total_elems` is a planner estimate that can be much too high. A sparse bitset compresses enormously. So the real question is not "which codec" but "how often are our filters sparse, and by how much". Report a density histogram over the workload matrix *before* implementing any codec. **Architectural consequence you must address.** A Golomb-coded set is **not unionable by OR**. The coordinator's cheap in-place fold (task 2.1) would become decode → merge → re-encode for every part. Quantify that: compare (a) transfer of raw bitset + OR fold, against (b) transfer of coded set + decode/merge/encode. Include the coordinator CPU cost, not just bytes on the wire. It is entirely possible that compression wins on bandwidth and loses on total latency. **Cheap comparison you should include:** zstd level 1 (already a dependency in this tree — see `gpcontrib/zstd` and `with_zstd`) applied to the serialized part, which keeps the format OR-able after decompression. If zstd gets 80% of the benefit for 5% of the complexity, that is the recommendation. **Required numbers:** bit density distribution; compressed size and compress/decompress ms per codec per density; wire time at a stated link bandwidth; end-to-end effect; the union-cost comparison above. **Remember the loopback trap in "Environment matters" — 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 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 this 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; payload bytes; fold time; **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 + network + 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 for this: publish a cancel (`ExecAnserBloomFilterProduceCancel()` in `anserbloomproduce.c`), which cancels the channel and makes every consumer fail open. Note that 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. ### Use case/motivation _No response_ ### Related issues _No response_ ### Are you willing to submit a PR? - [ ] Yes I am willing to submit a PR! GitHub link: https://github.com/apache/cloudberry/discussions/1959 ---- This is an automatically sent email for [email protected]. To unsubscribe, please send an email to: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
