Skip to content

[EPIC] Faster performance for parquet predicate evaluation for non selective filters #7456

Open

Description

@alamb

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

When evaluating filters on data stored in parquet, you can:

  1. Use the with_row_filter API to apply predicates during the scan
  2. Read the data and apply the predicate using the filter kernel afterwards

Currently, it is faster to use with_row_filter for some predicates and filter for others. In DataFusion we have a configuration setting to choose between the strategies (filter_pushdown, see apache/datafusion#3463) but that is a bad UX as it
means the user must somehow know which strategy to choose, but the strategy changes

In general the queries that are slower when with_row_filter is used:

  1. The predicates are not very selective (e.g. they pass more than 1% of the rows)
  2. The filters are applied to columns which are also used in the query result (e.g. the a filter column is also in the projection)

More Background:

The predicates are provides as a RowFilter (see docs for more details)

RowFilter applies predicates in order, after decoding only the columns required. As predicates eliminate rows, fewer rows from subsequent columns may be required, thus potentially reducing IO and decode.

Describe the solution you'd like

I would like the evaluation of predicates in RowFilter (aka pushed down predicates) to never be worse than decoding the columns first and then filtering them with the filter kernel

We have added a benchmark #7401, which hopefully can

cargo bench --all-features --bench arrow_reader_row_filter

Describe alternatives you've considered
This goal will likely require several changes to the codebase. Here are some options:

Activity

  1. alamb commented on Apr 30, 2025

    @alamb
    ContributorAuthor

    I just spoke with @XiangpengHao -- from my perspective the current status is:

    1. Parquet decoder / decoded predicate / page / results Cache #7363: blocked on getting some benchmark results that show the decoded page cache improves performance; Then we can proceed / merge the page cache change
    2. In paralell / then we can move on to working on a better representation for RowFilter (Adaptive Parquet Predicate Pushdown Evaluation #5523 / Consider removing skip from RowSelector #7450 / RowSelection::and_then is slow #7458)
  2. alamb commented on May 8, 2025

    @alamb
    ContributorAuthor

    Fascinatingly, Clickbench released a blog post recently about their parquet pushdown work

    https://clickhouse.com/blog/clickhouse-and-parquet-a-foundation-for-fast-lakehouse-analytics

    Possibly even more interesting is that they link to a master's thesis from Peter Boncz's group about how to quickly evaluate predicates during Parquet Decoding: https://homepages.cwi.nl/~boncz/msc/2018-BoudewijnBraams.pdf

    This thesis directly addresses some of the work we are considering (though they only consider Selection masks (bitmask) and Selection Vector (selected indices)

  3. alamb commented on May 12, 2025

    @alamb
    ContributorAuthor

    @zhuqi-lucas has a great insight in #7454 -- namely that instead of a two pass algorithm (evaluate RowFilter to form a final RowSelection and then re-decode the filter) we can combine the filter application and decode steps (see #7454 (review))

    The current flow goes something like:

    1. A set of array readers is created for the filter columns, and uses the provided RowSelection (this captures prunning
      pages ).
    2. The decoded batches are used to evaluate the RowFilter / ArrowPredicates, which produces a BooleanArray bitmap
    3. The "final" RowSelection is created, by unioning the existing RowSelection with the BooleanArrays
    4. A new set of array readers is created with the updated RowSelection

    The current PR starts heading down a slightly modified flow, where the RowSelection and RowFilters are not combined.

    I think a combined solution would look something like:

    1. Create Decoders for filter columns and projection (only) columns

    Decoding proceeds like:

    1. read rows from initial RowSelection (reads a 8192 rows) from filter columns, if any
    2. Apply any RowFilters on it (produces a BooleanArray)
    3. repeat 1-2 until there are at least 8192 (batch size) rows that pass the filter. (This means we have Vec<BooleanArray> with 8192 1s and a Vec for each filter column that is also a projection column)
    4. Then decode as maby RecordBatches from the projection (only) columns using the initial RowSelection)
    5. Apply the filters to each array to form the final output batch (in projection columns)
  4. alamb commented on May 16, 2025

    @alamb
    ContributorAuthor

    @zhuqi-lucas and I have been working on various strategies / structures to make the filtering faster. I believe we now have evidence enough to proceed with a more sophisticated implementation

    Specifically,

    Thus my next steps will be:

    1. Create a few refactoring PRs that gets the predicate code into shape

    Perhaps then @zhuqi-lucas can help port the hybrid Filter/RowSelection to the ReadPlan to get better performance without changing any public interfaces

  5. zhuqi-lucas commented on May 16, 2025

    @zhuqi-lucas
    Contributor

    Thank you @alamb , i will help port the hybrid Filter/RowSelection to the ReadPlan to get better performance without changing any public interfaces and also testing, review.

  6. alamb commented on May 16, 2025

    @alamb
    ContributorAuthor

    Thank you @alamb , i will help port the hybrid Filter/RowSelection to the ReadPlan to get better performance without changing any public interfaces and also testing, review.

    Thank you so much @zhuqi-lucas -- it is great working with you

  7. zhuqi-lucas commented on May 17, 2025

    @zhuqi-lucas
    Contributor

    Thank you @alamb , i tried the draft POC for adaptive predicate pushdown based read plan PR today, it shows good result:

    #7524 (comment)

  8. self-assigned this
    on May 19, 2025
  9. alamb commented on May 20, 2025

    @alamb
    ContributorAuthor

    Update: I am quite happy with how reusing filtered results is coming along, see:

    I also had some thoughts on reducing the buffering required here: #6692 (comment)

  10. alamb commented on May 21, 2025

    @alamb
    ContributorAuthor

    Status update

    The high level plan to improve performance has two parts:

    1. adaptive iteration / representation of filter results (basically Adaptive Parquet Predicate Pushdown Evaluation #5523)
    2. Caching the results of filtering when the column is used in the final projection (basically improve: reuse Arc<dyn Array> in parquet record batch reader. #4864)

    My main concern about resuing the result of filtering is memory usage and I think it is important to keep the usage to a minimum -- the current APIs (filter and concat kernels) require a 2x memory overhead so I think it is important to reduce that as well as add some way to limit memory consumption when the filtering result

    We also need to implement more sophisticated logic when there are multiple predicates.

    My next steps are:

    1. Try and factor the adaptive representation of filter results with @zhuqi-lucas
    2. Explore ways to reduce the memory overhead with caching results (this should help other APIs too).
  11. alamb commented on Jun 2, 2025

    @alamb
    ContributorAuthor

    I plan to work on a filter + concat benchmark this week

  12. alamb commented on Jun 27, 2025

    @alamb
    ContributorAuthor

    Here is a dataset I got from running clickbench Q30 and saving the results of evaluating filters (boolean arrays) into new parquet files. There are 325 parquet files corresponding to the 325 row groups in the 100 clickbench partitioned dataset files:

    filters_clickbench_q30.zip

    SELECT "SearchEngineID", "ClientIP", COUNT(*) AS c, SUM("IsRefresh"), AVG("ResolutionWidth") FROM hits WHERE "SearchPhrase" <> '' GROUP BY "SearchEngineID", "ClientIP" ORDER BY c DESC LIMIT 10;

    I don't really have a plan of how I will analyze them yet, but I will leave any notes on

  13. hhhizzz commented on Oct 9, 2025

    @hhhizzz
    Contributor

    Sorry to bother @tustvold @alamb @XiangpengHao , I was wondering if you are still focusing on this feature, as I noticed there haven't been any updates for a while.
    I see that the design(#5523) is quite mature, and there's also a draft(#6624) for boolean arrays that can be referenced. If you're not actively focusing on this issue right now, I think I could contribute code to this part

  14. XiangpengHao commented on Oct 11, 2025

    @XiangpengHao
    Contributor

    @hhhizzz go for it! I’ve been quite busy lately and probably won’t be able to pick it up for a few months, so it’d be awesome if you take the lead.

  15. alamb commented on Oct 14, 2025

    @alamb
    ContributorAuthor

    Yes, thank you @hhhizzz !

    I have been quite busy recently helping @etseidl get the new parquet metadata decoder in. See the following tickets if you are interested

    maybe @zhuqi-lucas also has some ideas / time to help as he had several good PRs

    One thing I tried to do to help here is this PR:

    I think the trickiest part of this project is not degrading performance for the existing cases where the current RowSelection is really good (namely representing large contiguous selections)

    One thing that @lwwmanning mentioned that works pretty well in Vortex was to use a LazyLock to hold an alternate predicate representations and computing it on demand.

  16. lwwmanning commented on Oct 14, 2025

    @lwwmanning

    Yep, we play some fun games with Masks in Vortex: https://github.com/vortex-data/vortex/blob/0.54.0/vortex-mask/src/lib.rs#L98-L121

    (published as the vortex-mask crate on crates.io if you want to use directly, or obviously feel free to just inline bits and bobs as you wish, it's Apache-2.0)

  17. zhuqi-lucas commented on Oct 15, 2025

    @zhuqi-lucas
    Contributor

    Thank you @hhhizzz , @alamb .
    Sorry i am busy with internal work currently, i can help review when i am free.

  18. alamb commented on Oct 31, 2025

    @alamb
    ContributorAuthor

    In case anyone is interested, @hhhizzz has a (very nice!) PR up to add adaptive filter representation that is showing good results:

  19. alamb commented on Dec 12, 2025

    @alamb
    ContributorAuthor

    An update:

    1. We merged [Parquet] Adaptive Parquet Predicate Pushdown #8733 and it shipped in arrow 57.1.0
    2. We published the blog post yesterday from @hhhizzz about this work: https://arrow.apache.org/blog/2025/12/11/parquet-late-materialization-deep-dive/ 🎉
    3. I am working on a PR that has an adaptive RowSelection (that has both RowSelector and Bitmask backed version) based on work from @zhuqi-lucas and @XiangpengHao - I think it is now in good enough shape to benchmark. Once I can show it makes a difference, I'll get it ready for more reviews
  20. hhhizzz commented on Aug 10, 2026

    @hhhizzz
    Contributor

    I spent a while building and evaluating selection pushdown into Parquet dictionary decoding — the SIGMOD'23 "Selection Pushdown in Column Stores using Bit Manipulation Instructions" approach(https://dl.acm.org/doi/10.1145/3589323) — on top of the Mask selection infrastructure. The end-to-end conclusion is negative and I'm not proposing it as a feature, but two of the findings bear directly on this epic, especially on the second slow case in the description ("the filters are applied to columns which are also used in the query result"). Writing them up here in case they save someone the same weeks.

    What was built

    An opt-in reader path that decodes only the selected dictionary indices, rather than decoding every value and filtering afterwards. Five additive layers from the RLE/dictionary decoder up to read_mask_batch, admitted only when every projected column is flat, required and primitive, and execution is on the Mask path. Wired through both the sync and async/push-decoder paths, plus a DataFusion session option, and evaluated end to end on ClickBench, TPC-DS SF10 and TPC-H.

    The leaf kernel is genuinely fast

    Against the production-shaped comparator — stock get_batch_with_dict full decode followed by arrow::compute::filter, both arms digest-verified to produce identical output before any timing was recorded:

    captured fixture survival selected vs production
    ClickBench hits.WatchID 2.8% 4.55x
    TPC-DS cr_returned_date_sk 0.9% 3.75x
    TPC-DS cr_refunded_hdemo_sk 5.1% 3.28x
    TPC-DS cr_returned_date_sk 10.9% 2.63x
    near-full survival (99.5%+) ~100% inverts — production 15–20% faster

    The inversion at the top end is worth noting for this epic specifically: at high pass rates the selected path degenerates into the same full decode plus overhead, so it does nothing for the non-selective regime this issue targets. It helps the selective end, which is the opposite corner.

    Finding 1 — the predicate cache and selected decoding are mutually exclusive today

    This is the one most relevant here. CachedArrayReader exists to avoid decoding a column twice when it is read by both a filter and the output projection — the exact case in this issue's description. But a cache wrapper cannot participate in an admission check it does not forward: mine inherited the trait default and reported "not eligible", and under an all-or-nothing subtree rule that single wrapper disqualified the whole scan.

    So the two available answers to the same problem do not compose:

    • caching avoids the second decode entirely;
    • selected decoding makes the second decode cheap (only the surviving rows).

    Right now the cache silently wins, because the wrapped column is invisible to any admission predicate added to ArrayReader. Measured on TPC-H: disabling the predicate cache moved coverage from 10/22 to 14/22 queries and 3.9x the rows. On ClickBench the only queries I ever covered at 100% were q30/q31 — whose filter column (SearchPhrase) is not in their output projection, so nothing was cached and nothing was disqualified.

    If someone pursues this direction, that choice probably wants to be made per column with knowledge of both costs, rather than decided implicitly by which wrapper got there first.

    Finding 2 — the filter chain is where selection pushdown actually earns its keep, and it is the easiest thing to leave out

    ReadPlanBuilder::with_predicate_options builds its reader with ParquetRecordBatchReader::new. That reader is not incidental: predicate N reads under the selection accumulated from predicates 1..N-1, which is precisely the mechanism RowFilter's doc comment describes ("as predicates eliminate rows, fewer rows from subsequent columns may be required").

    I threaded my option through the output path and not through that constructor. The result, traced call by call on TPC-H Q6 — the original paper's own headline query, three chained predicates leaving ~1.9% of rows:

    call class calls rows
    filter chain, eligible columns 711 ~6,000,000
    output phase 106 114,160

    So the wiring reached under 2% of the maskable rows in the query the whole technique was designed around. Anyone building this should thread that constructor first, not last.

    Correctness: two traps, one of them silent

    An end-to-end differential gate over per-query output digests failed on its first run and surfaced both.

    1. Subtree admission must be decided before any child produces output. Discovering a mixed projection after an earlier child has already written compact (already-filtered) data cannot be unwound — you hold one filtered and one unfiltered column destined for the same RecordBatch. Fixed with a side-effect-free predicate answered for the whole subtree before the first byte is decoded.

    2. A column chunk can change encoding mid-chunk. Writers abandon dictionary encoding once the dictionary outgrows its page budget, so RLE_DICTIONARY pages can be followed by PLAIN ones in the same chunk. My decoder declined at the first PLAIN page and returned a short read; the layer above interpreted that as "chunk exhausted" and advanced to the next row group. The row count still came out exactly right, with values taken from the wrong place. Only a full-value content check caught it — row-count assertions and tolerance-based aggregate comparisons all passed. Fixed by never declining for a structurally eligible column and falling back to decode-then-filter internally.

    Why I stopped

    No query-level benefit was established, and I stopped at a pre-registered gate.

    Coverage under the conservative admission rule was 0/99 TPC-DS queries and 4/42 ClickBench queries (TPC-H, measured later, reaches 10/22). The two fully-covered queries ran at 100% coverage over 65M rows each and showed no reproducible direction across two rounds — one swung 19% on identical binaries on dedicated hardware. Independently of the noise, the covered queries are 3.0–3.6% of suite runtime, so even pretending the entire covered portion were dictionary decode, a 2x–4x kernel bounds total improvement at roughly 1.4%–2.5%.

    I'd also temper expectations against the paper's numbers if anyone uses them for sizing. Its 3.1x for TPC-H Q6 is measured against a 2023 C++ baseline; a separate arm of this investigation found modern arrow-rs's existing full-decode path has already internalised most of that headroom (~2.8x geomean against the paper's own baseline shape). The residual against today's main should be expected to be substantially smaller.

    Possibly reusable

    • a regression case for reading across a mid-chunk dictionary→PLAIN change under RowSelection, validating the full value sequence rather than row counts. I'd want to check whether upstream already covers this before proposing it, and I'm not claiming it reproduces on unmodified main;
    • captured real-workload selection traces with provenance;
    • a coverage-counter methodology for proving an experimental path is actually executed — with the counter itself unit-tested, since a dead counter is indistinguishable from a dead path.

    Full write-up with data, commit pins, the reproduction notes and the caveats: https://github.com/hhhizzz/arrow-rs/blob/exp/v21-rle-selected-fill-20260807/experiments/shape-aware-selected-decoding/README.md

    It ran long and landed on "don't ship it", but the process turned out to have more in it than the verdict did, so I'd like to write the whole thing up as a blog post @alamb — the measurement design, the two traps, and why a fast kernel can reach almost none of its own benchmark. Happy to fold in anything people here think is worth emphasising, or to dig further into any of the numbers.

  21. alamb commented on Aug 10, 2026

    @alamb
    ContributorAuthor

    It ran long and landed on "don't ship it", but the process turned out to have more in it than the verdict did, so I'd like to write the whole thing up as a blog post @alamb — the measurement design, the two traps, and why a fast kernel can reach almost none of its own benchmark. Happy to fold in anything people here think is worth emphasising, or to dig further into any of the numbers.

    I will be honest I didn't fully follow this all thsi writeup @hhhizzz -- thank you for postiing it

    Did you find anything small that is worth pursuing? For example, does "the filter chain is where selection pushdown actually earns its keep, and it is the easiest thing to leave out" mean we should integrate the filter application earlier or differently?

    so I'd like to write the whole thing up as a blog post @alamb

    It sounds like it could be interesting. I am not sure a "here is a step by step thing I did" would necessairly make for the most interesting blog post. I think a more interesting would have some insight that is generally applicable to readers -- for example we will teach you about a technique" or "here is some way you should use arrow-rs to improve your workloads"

    So basically, I suggest we think more about what the story arc that you would want to tell before writing up details

  22. hhhizzz commented on Aug 11, 2026

    @hhhizzz
    Contributor

    I will be honest I didn't fully follow this

    Thanks for reading it — sorry it was so long. Quick answers:

    • "filter chain" clarification: That wasn't a suggestion for arrow-rs — arrow-rs already does this correctly. I meant my own experiment wired the flag into the wrong constructor, so I only measured ~2% of the opportunity. Just a gotcha I ran into, nothing to change on your end.

    • Anything small worth pursuing? No. The kernel is fast and that turns out not to matter.

    • Next: I'd like to pick up [Parquet] Adaptively to pick between RowSelection and Mask filter representation #8846 (adaptive Mask/Selectors). Also happy to measure predicate-cache cost/benefit if that'd be useful — I've got the benchmark setup ready.

    • Blog arc: "I'm thinking a debugging/methodology style post rather than a performance tuning guide. Something like "how to tell if your optimization is running at all" — coverage counters, probe tests, and the gotchas I hit along the way. Does that direction sound right to you?

  23. alamb commented on Aug 11, 2026

    @alamb
    ContributorAuthor

    Next: I'd like to pick up #8846 (adaptive Mask/Selectors). Also happy to measure predicate-cache cost/benefit if that'd be useful — I've got the benchmark setup ready.

    I do think that would be useful -- basically what I would like is to get to the point where enabling filter pushdown is always faster than non filter pushdown (other than I/O). I think we are close

    Blog arc: "I'm thinking a debugging/methodology style post rather than a performance tuning guide. Something like "how to tell if your optimization is running at all" — coverage counters, probe tests, and the gotchas I hit along the way. Does that direction sound right to you?

    I think it could be interesting -- I think it would be most interesting if it was applicable to the readers. So it might be worth asking "who do you want to read your blog" (is it other arrow-rs developers? Is it systems programmers in general who want general tips / how to use tools? Is it database internal develpers? etc)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

enhancementNew feature/additionparquetChanges to the parquet crate

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions