apache / apache/arrow-rs

Expose flexible apis for building bloom filters when writing parquet

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

Description

**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**

I'm want to generate parquet files that efficiently support prefix, substring, and suffix queries on strings. E.g., given a column of strings, find all strings containing a given query as a substring as quickly as possible.

Currently, as far as I know, this can't be done in the general case without loading all the data and doing an exhaustive scan.

**Describe the solution you'd like**

What I'd like to be able to do is build a bloom filter for my data consisting of ngrams. E.g., if my column contained the string "Hello, World!", and I was building a bloom filter with ngrams of length 4, I'd want to insert the sequences ["Hell", "ello", "llo,", ..., "rld!"] into a bloom filter. Later, when querying for a substring, I'd check if all ngrams of the same length were in the bloom filter. E.g., to search for "World", I would check whether the bloom filter contained "Worl" and "orld".

I don't really want this exact feature to be implemented in this library because I actually want a bit of flexibility to change things (e.g., maybe I want to index additional ngrams containing sentinels for start of word and end of word, maybe I want to delay the sizing of the bloom filter until I observe how many distinct ngrams I have) and I don't necessarily think my solution described above is appropriate as a general solution for everyone. Instead, I want to have the ability to customize how bloom filters are built and then implement this logic myself.

I'm not sure exactly how to best implement this, but I imagine something like having a trait
```
pub trait SbbfBuilder {
fn insert(&mut self, value: &T);
fn build(self) -> Sbbf;
}
```
allowing a `Box` to be set on `ColumnProperties` and changing the `bloom_filter: Option` in `ColumnValueEncoderImpl` and `ByteArrayEncoder` to instead be a `Option>` would work.

Contributor guide

Open the contributing guide

Research direction

Start by reading ColumnProperties, ColumnValueEncoderImpl, and ByteArrayEncoder to understand how bloom filters are configured, collected, and finalized. Review the proposed SbbfBuilder shape and the existing Sbbf flow, then define and test an API that lets callers provide custom bloom-filter construction logic while preserving parquet writing behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.