apache / apache/arrow-rs

Optimize Arrow boolean/null filtering with BMI isntructions

Open
#10,098 2 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 14h
Merged PRs (30d)
167

Description

**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
[`arrow-select::filter::filter_null_mask`](https://github.com/apache/arrow-rs/blob/main/arrow-select/src/filter.rs#L578-L588) filters validity bitmaps through [`filter_bits`](https://github.com/apache/arrow-rs/blob/main/arrow-select/src/filter.rs#L600-L640), which currently gathers selected bits via index iteration or copies contiguous slices. For dense or irregular predicates, this can do more per-bit work than necessary when compacting a source bitmap by a predicate bitmap.

**Describe the solution you'd like**
Add or reuse a `compress(value: u64, mask: u64) -> u64` bit utility, equivalent to Intel BMI2 [`_pext_u64`](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_pext_u64), in `arrow-buffer` and use it in [`arrow-select::filter_bits`](https://github.com/apache/arrow-rs/blob/main/arrow-select/src/filter.rs#L600-L640). The implementation could process 64-bit chunks of `(source_bits, predicate_bits)`, append `compress(source_bits, predicate_bits)` with `predicate_bits.count_ones()` bits, and fall back to existing handling for offsets/remainders.

**Describe alternatives you've considered**
The existing index and slice strategies are general and correct, and slice copying remains good for long contiguous true runs. Another option is to keep the helper local to parquet, but [`filter_null_mask`](https://github.com/apache/arrow-rs/blob/main/arrow-select/src/filter.rs#L578-L588) lives in `arrow-select`, so sharing it from `arrow-buffer` seems more reusable.

**Additional context**
PR [#9848](https://github.com/apache/arrow-rs/pull/9848) adds a parquet-local `compress` helper for compacting validity bits while decoding definition levels. The same primitive appears applicable to filtering [`BooleanBuffer`](https://github.com/apache/arrow-rs/blob/main/arrow-buffer/src/buffer/boolean.rs) values and null masks in [`arrow-select::filter_bits`](https://github.com/apache/arrow-rs/blob/main/arrow-select/src/filter.rs#L600-L640), especially for boolean arrays and filtered validity buffers.

Contributor guide

Open the contributing guide

Research direction

Start with arrow-select/src/filter.rs, especially filter_null_mask and filter_bits, then inspect arrow-buffer for a reusable bit utility and PR #9848's parquet-local compress helper. Confirm how offsets and remainders are handled before changing the 64-bit compaction path. Done means boolean and validity filtering preserve existing behavior while using the shared compression primitive where applicable.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.