apache / apache/datafusion

[EPIC] Adaptive predicate evaluation

Open
#22,883 4 comments 1 reaction 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.