apache / apache/arrow-rs

Avoid eagerly expanding mask-backed `RowSelection` to RLE in mixed `intersection` / `union`

Open
#10,423 0 comments 1 reaction 0 assignees View on GitHub
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.**

Follow up to #10141.

`RowSelection::intersection` and `RowSelection::union` have specialized fast paths when both sides share the same backing (bitwise ops for Mask+Mask, run merging for Selectors+Selectors). The mixed arms, however, eagerly convert the entire mask to RLE via `mask_to_selectors()` and then run the selector-based algorithm.

For a fragmented bitmap this is the worst case: an alternating 3M-row mask (~375 KB as a bitmap) expands to 3M `RowSelector`s (~48 MB) just to compute an intersection. A natural use case that hits this is an externally supplied fragmented bitmap composed with selector-backed page-index pruning — DataFusion's `ParquetAccessPlan::scan_selection` performs exactly this kind of `intersection`.

Originally reported by @hhhizzz in https://github.com/apache/arrow-rs/pull/10141#discussion_r3608558294

**Describe the solution you'd like**

Options, roughly in order of preference:

1. Convert the selector-backed side to a bitmap (selectors → mask is cheap and contiguous via `boolean_mask_from_selectors`) and use the existing bitwise Mask+Mask path. When the pattern is fragmented enough to be mask-backed on one side, the result is likely best kept mask-backed anyway.
2. Stream the mask's runs through `MaskRunIter` into the selector-merge algorithms without materializing a `Vec`.

**Describe alternatives you've considered**

Keeping the eager conversion but capping it with the auto-strategy heuristic — more complex and still O(runs) allocation in the fragmented case.

**Additional context**

Per review feedback on #10141, this should land with benchmark coverage, e.g. a mixed-backing `intersection`/`union` case in `parquet/benches/row_selection_cursor.rs` using a fragmented (alternating) mask against a coarse selector-backed selection (`cargo bench -p parquet --bench row_selection_cursor`).

Contributor guide

Open the contributing guide

Research direction

Start with RowSelection::intersection and RowSelection::union, then inspect the existing mask_to_selectors and boolean_mask_from_selectors paths. Run parquet/benches/row_selection_cursor.rs with cargo bench -p parquet --bench row_selection_cursor, adding the fragmented alternating-mask and coarse-selector cases described. Done means mixed backing avoids eagerly materializing the mask as RLE while preserving intersection and union behavior and benchmark coverage.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.