apache / apache/arrow-rs

parquet: Improve performance of mask/selection construction in `ReadPlanBuilder::with_predicate_options`

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

Description

## Describe the problem
- I am working to make pushdown evaluation faster -- see https://github.com/apache/datafusion/pull/24426
- Related to #10774

Profiling ClickBench Q25 against `hits_partitioned` (no page index) with a `--profile=profiling` build of `datafusion-cli`:

```sql
SELECT "SearchPhrase" FROM hits WHERE "SearchPhrase" <> '' ORDER BY "SearchPhrase" LIMIT 10;
```

The predicate selects ~15% of rows, scattered (short runs).

Enabling filter pushdown adds ~300ms of CPU per query vs evaluating the same filter in a `FilterExec` above the scan. One big difference is `ReadPlanBuilder::with_predicate_options`

| self CPU ms/query | % of delta | function |
|---|---|---|
| 82.3 | 27% | `ReadPlanBuilder::with_predicate_options` |
| 21.9 | 7% | `ReadPlan::build` |

About 10% of the total execution time is actually spent in the main body of `ReadPlanBuilder::with_predicate_options`

Image

So I want to try and improve the performance of `ReadPlanBuilder::with_predicate_options`

## Observations

1. For a first predicate with no prior `RowSelection` (the common no-page-index case), the boolean filter results are **always** materialized as **selectors** (aka RLE / one `RowSelector`)

https://github.com/apache/arrow-rs/blob/59.2.0/parquet/src/arrow/arrow_reader/read_plan.rs#L277-L285

The `from_boolean_buffer` arm only fires when a *prior* selection is already mask-form. `RowSelection::from_filters` (https://github.com/apache/arrow-rs/blob/59.2.0/parquet/src/arrow/arrow_reader/selection/mod.rs#L312-L324) walks every boolean array with `SlicesIterator`, producing millions of tiny selectors for a scattered selection — the 82ms/query above.

Later, `RowSelectionPolicy::Auto` resolves the strategy to `Mask` for this selection shape, and `ReadPlan::build` converts the selectors back into a mask:

https://github.com/apache/arrow-rs/blob/59.2.0/parquet/src/arrow/arrow_reader/read_plan.rs#L331-L337

So the pipeline for this shape is booleans → selectors → mask, where a boolean-buffer concatenation (`filters_to_boolean_buffer`, ~1ms for the same data) would have sufficed.

## Expected behavior

Make it faster

## Things to explore

### Don't convert to selectors if we are going to convert back to mask

###
When building a mask backed selector, don't force a copy (this function always copies the bitmap) -- it is probably better to incrementally build the output buffer than buffer then copy.

```rust
fn filters_to_boolean_buffer(filters: &[BooleanArray]) -> BooleanBuffer {
let total_rows = filters.iter().map(|f| f.len()).sum();
let mut builder = BooleanBufferBuilder::new(total_rows);
for filter in filters {
assert_eq!(filter.null_count(), 0);
builder.append_buffer(filter.values());
}
builder.finish()
}
```

Contributor guide

Open the contributing guide

Research direction

Start in parquet/src/arrow/arrow_reader/read_plan.rs at ReadPlanBuilder::with_predicate_options, then compare RowSelection::from_filters in parquet/src/arrow/arrow_reader/selection/mod.rs with filters_to_boolean_buffer. Profile the ClickBench Q25 query using datafusion-cli and check whether the boolean-to-selector-to-mask path is avoided without changing selection behavior. Done means the profiled construction is faster.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
backend, performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.