jiangxt2 commented on PR #57336:
URL: https://github.com/apache/spark/pull/57336#issuecomment-5011071932
## Context
We run a telecom data platform where event tables reach tens-of-billions of
rows. A common pattern is filtering events by pre-defined user segments
(stored as `(group_id, user_id)` pairs with millions of members). At this
scale, broadcast hash join is infeasible and every query triggers a
SortMergeJoin.
`bitmap_contains` pre-computes segments as bitmap tables in ETL, then
replaces the shuffle join with a constant-time bit check:
```sql
-- ETL: once
CREATE TABLE seg_bitmaps AS
SELECT group_id, bitmap_bucket_number(user_id) AS bucket,
bitmap_construct_agg(bitmap_bit_position(user_id)) AS bm
FROM user_segments GROUP BY group_id, bitmap_bucket_number(user_id);
-- Query: bit check instead of shuffle join
SELECT e.* FROM events e
JOIN seg_bitmaps s
ON bitmap_bucket_number(e.user_id) = s.bucket AND s.group_id = 100
WHERE bitmap_contains(s.bm, bitmap_bit_position(e.user_id));
```
## Bloom Filter vs bitmap_contains
Both are join pre-filtering techniques, but they differ fundamentally:
| | Runtime Bloom Filter | bitmap_contains |
|---|---|---|
| **Mechanism** | Probabilistic: xxhash64 × k hashes →
`BloomFilterImpl.probe`. Has false positives | Deterministic: single `bm[pos/8]
& (1 << pos%8)`. Zero false positives |
| **Trigger** | Automatic via `InjectRuntimeFilter`. Requires ALL of: (1)
`isLikelySelective` filter on creation side with no Aggregate in the
Filter→Scan chain; (2) probe side scan ≥ `applicationSideScanSizeThreshold`
(default 10GB); (3) creation side ≤ `creationSideThreshold` (default 10MB —
almost never met for million-row segments) | Manual: (1) ETL
`bitmap_construct_agg`; (2) `bitmap_contains` in WHERE. No trigger restrictions
|
| **Scaling** | Probe cost grows with creation-side size (larger bloom
filter → more memory pressure, higher false-positive rate → more rows pass
through to join) | O(1) per check. Bitmap table fixed at ~6MB regardless of
segment cardinality |
| **Best for** | Small creation side (≤1M rows), one-off queries | Large
segments (≥5M rows), repeated queries, ETL-precomputed bitmaps |
| **Build cost** | Hidden in every query (cannot be separated) | Paid once
in ETL, zero at query time |
The key difference: bloom filter degrades as the creation side grows —
more rows to hash, larger filter, higher false-positive rate. Bitmap
query time is determined by domain size, not segment size. For large
segments (typical in production cohort filtering), this structural
difference matters.
Currently `bitmap_contains` uses `StaticInvoke` for evaluation (similar to
other bitmap functions), which adds a minor per-row overhead. A follow-up
could add `doGenCode()` for inline bitwise codegen — analogous to how
`BloomFilterMightContain` generates direct `mightContainLong()` calls inside
`WholeStageCodegen`. This is a small optimization (~30 lines) that would
give `bitmap_contains` the same codegen treatment bloom filter already has.
Cross-engine: ClickHouse, Doris, and StarRocks all provide this function.
Hive community has requested it (HIVE-27372). Uses Spark's existing
flat-bitmap convention without external dependencies.
Feedback welcome.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
