apache / apache/arrow-rs

Optimize `RowSelection::and_then` for dense masks

Open
#10,967 1 comment 0 reactions 1 assignee Claimed by @haohuaijin View on GitHub
enhancement
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 16h
Merged PRs (30d)
168

Description

### Is your feature request related to a problem or challenge?

When both `RowSelection::and_then` operands are mask-backed, the current implementation maps each selected inner row to a set bit in the outer mask. This is efficient for sparse masks but expensive for large, dense masks.

### Describe the solution you'd like

Add a word-at-a-time bitmap expansion path for dense masks while retaining the existing implementation for other inputs.

Based on benchmarks, use the new path when:

- the outer mask has at least 8,192 rows;
- outer selectivity is approximately 75% or greater; and
- inner selectivity is approximately 5% or greater.

On an Apple M4, all 104 benchmark cases selected by these thresholds improved over `main`, with mean execution time reduced by 30.0% to 97.9%.

### Describe alternatives you've considered

_No response_

### Additional context

_No response_

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.