parquet: Improve performance of mask/selection construction in `ReadPlanBuilder::with_predicate_options`
- 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`
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
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