[EPIC] Adaptive predicate evaluation
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
This is a tracking ticket for work @adriangb @neilconway and others have discussed in various places. I am putting it into a single ticket so it is easier to track
## Summary
The idea is that the order of applying filters can make a big difference in performance. For example
1. running very selective filters before non selective filters is often a good idea
2. Running filters *during* the parquet scan rather than decoding first then filtering is often a good ida
However in practice, neither of the above is always true:
1. Sometimes selective filters are very expensive to evaluate (e.g. a regexp_match) compared to a relative less expensive filter (e.g. `int8_col = 1`)
2. Sometimes pushing predicates down into the parquet scan actually slows things down (see https://github.com/apache/datafusion/issues/3463)
We have some heuristics for choosing the predicate evaluation order and when to push filters down, but they inevitably get it wrong sometimes (e.g. because the selectivity estimate is wrong, or the selected row pattern is bad).
The idea is to track how effective (and expensive) a predicate actually is at runtime and then adapt the ordering and placement based on that
## Related PRs
- #22144 — [Experiment] Adaptive filter pushdown (umbrella experiment)
- #22234 — `OptionalFilterPhysicalExpr` wrapper + proto (mark a filter as droppable)
- #22235 — Per-conjunct pruning statistics for `PruningPredicate`
- #22236 — `SelectivityTracker` adaptive filter cost model
- #22237 — Adaptive filter pushdown for the parquet scan (integration)
- #21752 — Adaptive filter scheduling for Parquet scans (prior full PR)
- #20363 — (Test) Advanced adaptive filter selectivity evaluation
- #19639 — feat: adaptive filter selectivity tracking for Parquet row filters (closed prototype)
- apache/arrow-rs#9659 — complementary compute-only filter evaluation optimizations
## Related issues
- #15512 — [Epic] Dynamic filtering related items
- #21207 — [DISCUSSION] Future of Dynamic Filters Sync
- #3463 — Enable parquet `filter_pushdown` by default
- https://github.com/apache/arrow-rs/issues/8846 in arrow-rs from @hhhizzz
Contributor guide
Research direction
This is a tracking epic rather than a self-contained change. Start by reading related PRs #22144, #22234, #22235, #22236, and #22237, along with issue #3463, to understand the existing adaptive filter work. Done would require a defined implementation scope for runtime predicate evaluation ordering and placement, plus corresponding validation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100