You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "hhhizzz (via GitHub)" <gi...@apache.org> on 2026/05/10 10:36:39 UTC

[PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

hhhizzz opened a new pull request, #9956:
URL: https://github.com/apache/arrow-rs/pull/9956

   # Which issue does this PR close?
   
   - Closes #8846
   - Part of #7456
   - Addresses #9591
   - Related to #9589
   - Follow-up to #8565
   
   # Rationale for this change
   
   `RowFilter` can be much slower than a full scan for fragmented selections, especially when page indexes provide little pruning and the resulting `ReadPlan` contains many tiny select/skip runs. #8565 shows an extreme case where predicate pushdown is around 10x slower than scanning and filtering afterwards.
   
   This PR improves the `RowSelectionPolicy::Auto` path so it can make better strategy decisions for fragmented row selections and avoid continuing with row-filter pushdown when the observed shape suggests the pushdown path is unlikely to help.
   
   The main goal is to reduce the performance cliff without changing explicit `Mask` / `Selectors` behavior.
   
   While working on the Auto strategy, this PR also fixes a correctness issue in the `Mask` execution path. With sparse page-loaded ranges, a mask-backed read plan could previously attempt to consume selected rows outside the loaded ranges and fail during decoding. This made `Mask` risky for some page-index / fragmented-selection cases.
   
   This PR makes the loaded row ranges explicit in the read plan and adds coverage for sparse loaded-range execution. After this change, using `Mask` should no longer hit this known failure mode.
   
   
   # What changes are included in this PR?
   
   - Adds structured `RowSelection` shape analysis and strategy decision metrics.
   - Improves `RowSelectionPolicy::Auto` so it can choose between mask and selectors using selection shape and loaded page ranges.
   - Adds sparse loaded-range tracking from page offsets so fragmented page-loaded selections can avoid expensive mask execution.
   - Adds adaptive post-filter fallback for Auto:
     - observes the first row group;
     - keeps pushdown for sparse/low-selectivity cases where it is still useful;
     - switches later row groups to post-filter for high-selectivity or fragmented moderate/high-selectivity cases.
   - Preserves correctness around fallback:
     - does not reuse sparse predicate chunks when rebuilding a base/full read;
     - disables post-filter fallback for `try_next_reader` handoff paths;
     - avoids evaluating `ArrowPredicate` twice for the same current row group when caller-provided row selection is present.
   - Simplifies fallback trigger metrics to shape-based reasons only, avoiding unused timing/cache fields.
   - Replaces loaded range intersection with a linear two-pointer merge.
   - Extends `arrow_reader_row_filter` benchmarks to cover strategy-sensitive cases.
   - Fixes a known `Mask` correctness failure with sparse loaded page ranges.
   - Preserves explicit `Mask` behavior while ensuring sparse loaded ranges are tracked so mask execution does not read outside available page ranges.
   
   
   # Are these changes tested?
   
   Yes.
   
   Unit / integration validation:
   
   - `cargo fmt -p parquet -- --check`
   - `git diff --check`
   - `cargo test -p parquet --lib arrow::push_decoder`
     - 38 passed
   - `cargo test -p parquet --lib arrow::arrow_reader::read_plan`
     - 28 passed
   - `cargo test -p parquet --lib arrow::arrow_reader::selection`
     - 25 passed
   - `cargo test -p parquet --lib`
     - 1132 passed
   
   New focused tests cover:
   
   - Auto fallback with caller-provided row selection does not evaluate the current row group predicate twice.
   - `try_next_reader` does not use post-filter fallback in normal reader handoff mode.
   - Sparse/current-row fallback does not reuse incompatible predicate chunks.
   - Explicit `Mask` execution remains correct with sparse loaded page ranges.
   - Auto switches away from `Mask` when sparse loaded ranges make selector execution safer.
   - Multi-column loaded row-range intersection remains correct after switching to a linear merge.
   - Auto strategy decisions for sparse loaded ranges and expensive fragmented output.
   
   Benchmark evidence from `arrow_reader_row_filter` comparing `origin/main` vs this branch:
   
   | case | origin/main | this branch | change |
   |---|---:|---:|---:|
   | `utf8View != ''`, all columns | 7.91 ms | 5.52 ms | +43.2% |
   | `int64 > 90`, all columns | 7.29 ms | 5.34 ms | +36.5% |
   | `int64 > 90`, exclude filter column | 6.97 ms | 5.23 ms | +33.3% |
   | `utf8View != ''`, exclude filter column | 6.77 ms | 5.53 ms | +22.5% |
   | `float64 > 99.0`, exclude filter column | 4.94 ms | 4.38 ms | +12.9% |
   
   Across the 16 async `arrow_reader_row_filter` cases run, geometric mean speedup was about 1.08x. The worst observed regression in that run was about -3.3%.
   
   
   # Are there any user-facing changes?
   
   No intended breaking API changes.
   
   `RowSelectionPolicy::Auto` may choose different internal execution strategies than before. Explicit `Mask` and `Selectors` policies remain available for callers that want fixed behavior.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4560507353

   > (I am not likely going to be able to review 8k lines in detail, however, so I will probably look at the high level first)
   
   Thanks for taking a look at this PR! I completely understand that an 8k-line diff is daunting to review in detail.
   
   To help make the review process easier, I wanted to clarify only about **3,450 lines** are production code, while the remaining 4,800+ lines are benchmarks and extensive unit/integration tests.
   
   If you still feel this is too large to review as a single PR, I would be more than happy to split this into smaller , incremental PRs.πŸ˜„ Here is how we can cleanly divide the work:
   
   * **PR 1 (Infrastructure & Metrics)**: Expose `ArrowReaderMetrics` + refactor/extract `strategy.rs` and its isolated test file `selection/tests.rs` (No functional changes to the reader).
   * **PR 2 (Post-Decode Filter State)**: Introduce `post_filter.rs` with its internal unit tests (Laying the groundwork for the fallback path).
   * **PR 3 (Selection Policy & Cost Model)**: Add `cost_model.rs`, `selection_policy.rs`, integrate them into the push decoder state machine, and add the main benchmarks.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "etseidl (via GitHub)" <gi...@apache.org>.
etseidl commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4565734716

   > If you still feel this is too large to review as a single PR, I would be more than happy to split this into smaller , incremental PRs.πŸ˜„ Here is how we can cleanly divide the work:
   
   Please do...that would help me, and would provide a baseline to compare the improvements against.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4769646397

   I think the best model is **multi-level adaptivity**.
   
   DataFusion has more **high-level context**, such as query semantics, file / row-group statistics, projected columns across the whole scan, and cross-file predicate selectivity. That makes it a good place to decide whether a `RowFilter` should be used at all, or to override the default behavior when it has stronger information.
   
   However, the part this PR is trying to handle is **lower-level**. The actual shape of the final `RowSelection` is only known after the Parquet reader has decoded the predicate columns for a specific row group and evaluated the `RowFilter`. For example, whether the result is clustered, fragmented, mostly selected, or sparse is not available to DataFusion at logical / physical planning time without duplicating Parquet reader internals.
   
   So I see the responsibilities as:
   
   - **DataFusion** decides the higher-level scan / filtering strategy.
   - **arrow-rs** decides how to execute a row filter once it sees the actual row-group-level selection shape and loaded page ranges.
   
   The explicit policy APIs are important because they still allow DataFusion to override the automatic choice. But I think the default `Auto` behavior belongs in arrow-rs, because the information it uses is produced inside the Parquet reader during execution.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4783286107

   > @hhhizzz I just thought about coming back to #9118 #9415 and saw your work here.
   > 
   > I think it looks like a better framework for tackling the issues than my PRs:
   > 
   > * [[Parquet] Support skipping pages with mask based evaluationΒ #9118](https://github.com/apache/arrow-rs/pull/9118)
   > * [Add statistics-based thresholds for deferring `RowFilter` selection in `ReadPlanBuilder`Β #9659](https://github.com/apache/arrow-rs/pull/9659)
   > 
   > I'll take a closer look at #10135 and try to help with the next PRs coming! πŸš€
   
   See also https://github.com/apache/arrow-rs/pull/10141 from @haohuaijin 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4588791775

   Closed the PR as a reference, I'll split it to smaller PRs.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "sdf-jkl (via GitHub)" <gi...@apache.org>.
sdf-jkl commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4700154023

   @hhhizzz I just thought about coming back to #9118 #9415 and saw your work here.
   
   I think it looks like a better framework for tackling the issues than my PRs:
   - #9118 
   - #9659
   
   I'll take a closer look at #10135 and try to help with the next PRs coming! :rocket: 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz closed pull request #9956: Optimize parquet row filter auto strategy with adaptive fallback
URL: https://github.com/apache/arrow-rs/pull/9956


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4769412416

   One thing @adriangb and @zhuqi-lucas  and I have noticed in DataFusion is that getting heuristics to work well is very challenging -- for example cutoff values often vary from architecture to architecture (e.g. is 32 contiguous 1s good, or should it be 64?)
   
   One thing we have been exploring is a more dynamic approach -- aka to switch the predicate evaluation strategy at certain times when the decoder naturally has to re-create some state, such as between row groups, like in this PR:
   - https://github.com/apache/arrow-rs/pull/10158
   
   It seems as if you have taken a similar approach in this PR 
   
   > Adds an adaptive post-filter cost model for row groups
   
   (caveat I have not had a chance to read this one carefully, and for that I apologize)
   
   I think we had been planning to put more of the adaptivity at a higher level (DataFusion specifically) as it has more information about things like statistics, and cross file predicate selectivity.
   
   I wonder if you have thought about where these auto adaptive decisions would best be made. 
   
   I do think the APIs you have outlined allow for both automatic and manually overriding (e.g. DataFusion could override the decisions made automatically) which is interesting


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4456409814

   > πŸ‘‹
   
   πŸ‘‹πŸ» I find the result is still not stable next day I publish it, I can repro some regression in some rare case, still working on it.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4769463376

   > I think we had been planning to put more of the adaptivity at a higher level (DataFusion specifically) as it has more information about things like statistics, and cross file predicate selectivity.
   
   The pattern that seems to work well is:
   - Seed with cheap heuristics
   - Adapt once runtime information is available
   - Have multiple levels of adaptivity
   
   That last case specifically applies here:
   - Datafusion can decide what even is a row filter or not
   - arrow-rs can optimize how it applies those row filters (e.g. when it pays the price of flattening / rolling over a mask, etc.) at a more fine-grained level


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4454352277

   πŸ‘‹ 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4460752061

   Yeah, we are at the point where the code is already pretty fast, so additional optimizations get harder and harder


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4519603832

   A bit of context on how this PR evolved.
   
   The initial motivation was #8565: predicate pushdown is not always cheaper than scanning when the produced `RowSelection` becomes highly fragmented. After my last PR(https://github.com/apache/arrow-rs/pull/8733), I think there would be more improvement. My first attempt was to make `Auto` prefer `Mask` more often for fragmented selections, because a dense bitmap can avoid some of the tiny select/skip run overhead.
   
   That turned out to be incomplete. Page pruning means the loaded pages may be sparse, and the previous mask path could assume rows were available even when their pages had not been loaded. So the work split into two parts:
   
   1. make explicit `Mask` safe by tracking loaded row ranges;
   2. keep `Auto` free to choose `Selectors`, `Mask`, or post-filter execution based on the shape of the actual read.
   
   I also tried several purely static rules based on selectivity, projection shape, and data type. Some helped, but the results were fragile: rules that improved one fragmented case could regress sparse output reads or cacheable predicate cases. In particular, string / variable-width cases were easy to overfit. That is why the final design moved toward a small adaptive cost model instead of a larger pile of static heuristics.
   
   The current implementation is roughly:
   
   - use row-selection shape analysis to decide between `Mask` and `Selectors`;
   - represent sparse loaded ranges explicitly so `Mask` does not fail on page-pruned data;
   - observe early row-group pushdown behavior;
   - switch later row groups to post-filter execution only when pushdown appears unlikely to pay for itself;
   - keep explicit `Mask` / `Selectors` policies as caller intent and only apply this adaptive behavior to `Auto`.
   
   I also added focused benchmark cases after seeing that the original benchmark suite did not clearly expose the cost-model-sensitive cases. The goal was to cover both the original fragmented-selection cliff and the cases where an overly aggressive rule could regress.
   
   So the PR is larger than a single heuristic change because the important part was separating the concepts:
   
   - what rows are selected;
   - which pages are actually loaded;
   - how that selection should be represented;
   - whether pushdown or post-filter execution is cheaper for `Auto`.
   
   That separation is what makes the `Mask` correctness fix and the adaptive `Auto` behavior fit together.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4558041723

   Thank you @hhhizzz  -- I will try and review this later today or tomorrw


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Optimize parquet row filter auto strategy with adaptive fallback [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9956:
URL: https://github.com/apache/arrow-rs/pull/9956#issuecomment-4558045053

   (I am not likely going to be able to review 8k lines in detail, however, so I will probably look at the high level first)


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org