apache / apache/arrow-rs

Parquet- thoughts on adding Ribbon filters as a bloom alternative?

Open
#9,761 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 18h
Merged PRs (30d)
169

Description

Hey — wanted to float an idea: [Ribbon filter](https://arxiv.org/pdf/2103.02515)(been shipping in RocksDB since 6.15) as a second option next to the existing SBBF in `bloom_filter/`. Writer picks one, reader dispatches on the thrift algorithm tag.

### Why I think it's worth talking about

SBBF sits around 10 bits/key for 1% FPR. Ribbon gets close to the information-theoretic floor — ~6.7 bits/key for the same FPR. That's roughly a third off the bloom footprint. For a Parquet file with bloom on a handful of columns across a bunch of row groups, that adds up to real bytes in the footer.

Where I think it actually shows up:
- Cold opens from S3 / GCS — fewer bytes per `GET`
- Lakehouse setups with tons of small-ish files — metadata cache holds more files
- Anywhere DataFusion's `prune_by_bloom_filters` is doing real work today

What I don't want to oversell:
- Query throughput is ~3× slower per probe in the paper's benchmark. But the paper's own limitations section calls out that this is a throughput measurement; for uncorrelated single probes (which is what Parquet actually does) latency is memory-bound and basically a wash.
- Construction is 6–25× slower per key. That's a real cost on the writer side. Probably fine for write-once lake data, probably annoying for high-QPS streaming ETL.

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing implementation under `bloom_filter/`, the Parquet thrift algorithm tag handling, and DataFusion's `prune_by_bloom_filters` integration. Determine the required writer and reader changes, compatibility implications, and tests needed before deciding whether a Ribbon filter can be added as an alternative to SBBF.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.