Repository navigation
parquet: Improve performance of mask/selection construction in ReadPlanBuilder::with_predicate_options #10776
Description
Describe the problem
- I am working to make pushdown evaluation faster -- see WIP: DO NOT REVIEW: Benchmark enabling parquet filter pushdown by default with one-shot row group I/O datafusion#24426
- Related to Improve performance of CachedArrayreader filter+concat #10774
Profiling ClickBench Q25 against hits_partitioned (no page index) with a --profile=profiling build of datafusion-cli:
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
- 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 / oneRowSelector)
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:
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.
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()
}
Activity
[-]parquet: RowFilter selection construction materializes selectors even when the selection strategy resolves to Mask[/-][+]parquet: Improve performance of mask/selection construction in ParquetReader[/+][-]parquet: Improve performance of mask/selection construction in ParquetReader[/-][+]parquet: Improve performance of mask/selection construction in ReadPlanBuilder::with_predicate_options[/+][-]parquet: Improve performance of mask/selection construction in ReadPlanBuilder::with_predicate_options[/-][+]parquet: Improve performance of mask/selection construction in `ReadPlanBuilder::with_predicate_options`[/+]alamb commentedon Aug 21, 2026
Another example where it might be better to incrementally build the output
(it allocates a new array)
alamb commentedon Aug 21, 2026
FYI @haohuaijin and @hhhizzz -- this might be interesting to you
haohuaijin commentedon Aug 21, 2026
thank you @alamb for write this, i can do some research and test on this part
hhhizzz commentedon Aug 23, 2026
Thanks for the ping. I did a focused experiment on this today to quantify the Boolean filter -> selectors -> mask overhead described in this issue.
For the experiment, I generated deterministic
BooleanArrayinputs with several selection shapes and measured the selection construction + lowering path separately from predicate evaluation and Parquet decoding. I included a Q25-like case with ~15% scattered short runs, an alternating run-1 case, the run-32 Auto boundary, a clustered run-128 case, a sparse long-run case, and all-selected. I also ran the candidate through the existing async Parquet reader path using paired measurements against a clean baseline.The results suggest this round trip is indeed quite expensive for fragmented predicate results:
I also tried an unconditional mask-first variant as an experiment. It improved the fragmented cases, but regressed the lowering path by 30.74% for run-128 and 107.55% for the sparse case. So simply constructing a mask first for every predicate result does not look like a good general solution.
For correctness, I compared 50,000 randomized inputs against the current behavior, including the selected strategy/backing, logical selection, selected-row count, and total length, and all 50,000 matched. I also covered LIMIT/padding, non-byte-aligned buffers, runs crossing filter boundaries, empty filters, and the run-31/run-32 Auto boundary. The async exact-payload preflight passed all 9 cases as well.
I haven't run a full DataFusion ClickBench Q25 comparison yet because current DataFusion/Arrow main have some unrelated compatibility differences that would require additional porting. For now I kept this experiment focused on the specific selection-construction cost identified here.
These results look promising, but this is still a focused experiment rather than a production-ready change. I plan to spend the next few days working through the implementation details and testing a broader set of cases to make sure an optimization here doesn't introduce regressions elsewhere. @haohuaijin, since you're also looking at this area, happy to coordinate so we don't duplicate work.
haohuaijin commentedon Aug 24, 2026
Thanks @hhhizzz for the detailed testing! I ran some similar tests and get the almost same results. Since you’ve already covered more cases, feel free to take the lead on this. I’m happy to help with reviews, discussion, and testing.
alamb commentedon Aug 24, 2026
FYI I have a PR up that pins to arrow-rs head (and resolves those conflicts) that you can probably use to experiment with:
alamb commentedon Aug 24, 2026
Thanks @hhhizzz and @haohuaijin
If we can skip the round trip to Vec that seems like it will be a win to me
The challenge might be how to figure out what selector type Auto mode will resolve to (as I think that happens now after filter application) 🤔
hhhizzz commentedon Aug 26, 2026
PR for this issue:
#10852
Core result
The implementation constructs normalized selectors only until Auto's strict run-count threshold proves that the final strategy must be Mask. It then builds the bitmap directly from the predicate BooleanArrays. Selector-friendly inputs continue to use selectors.
In a focused benchmark over 4,194,304 rows (512 x 8,192-row BooleanArrays), the median of three Criterion rounds was:
Mask-first was not a safe general solution: it regressed run-128 by 30.7% and sparse input by 107.6% because selector-friendly inputs then had to lower a bitmap back into selectors.
At the async Parquet-reader level, three paired rounds showed -26.0% for the Q25-like shape and -48.9% for alternating run-1. Run-32, run-128, sparse, and all-selected stayed within the 3-5% practical regression gate.
The branch also fixes a reachability issue: page-skipping preparation previously resolved Auto to Selectors even when no selection existed, preventing the new first-predicate path from running.
What I found after the #10852 fix
The construction fix removes the Boolean -> selectors -> mask round trip, but it is only one part of the original end-to-end pushdown gap. I continued with a separate experiment to understand the remaining costs.
1. Predicate/output overlap
For Q25,
SearchPhraseis both the predicate column and the output column. The normal pushdown path still builds a selection, manages the predicate cache, and then creates an output reader around the same string column. A direct-output path can decode the predicate/output union once, evaluate the predicate, and return the filtered output directly.2. Whole-row-group materialization was not acceptable
The first direct-output prototype collected all filtered batches for a Row Group before returning. I replaced this for the DataFusion path with a streaming reader that owns the stateful
RowFilteruntil row-group EOF and returns it to the decoder through a completion slot. Dropping an undrained reader fails closed instead of reusing a positionally staleFnMutpredicate.3. Ordered split predicates should remain Arrow-owned
Combining predicates in DataFusion could regress when Arrow later rejected the direct path: the predicates had already lost sequential short-circuiting, but there was no direct-output benefit. The experiment therefore lets Arrow execute ordered split predicates, with each later predicate evaluating only the prior survivors, and composes the masks in original-row coordinates.
4. Regressions exposed missing admission signals
Two useful counterexamples shaped the final experimental policy:
URLas both output and a late predicate column. The union therefore looked like zero deferred output, but direct decoding front-loadedURLbefore selective numeric predicates. Detecting staged predicate projections and observing one Row Group reduced the 20-run average regression from +16.8% to +1.5%.The resulting experimental admission rule uses three signals:
It also rejects actual pre-existing
RowSelection, offset/limit, virtual columns, and nested top-level projections. Merely loading page-index metadata does not reject the path if no page-level selection was produced.End-to-end experimental result
With the broader direct-output experiment enabled:
I intentionally kept all of this broader work out of the #10776 branch. My current view is that the capped Auto construction is a focused fix for this issue, while streaming/adaptive direct output should be reviewed separately.
alamb commentedon Aug 27, 2026
Thank you @hhhizzz -- FYI I am testing this as part of
[Parquet] Improve Auto RowSelection construction for scattered predic…
[Parquet] Improve Auto RowSelection construction for scattered predic…
perf(parquet): fuse consecutive filters on the same projection (#10859)