lance-format / lance-format/lance

Support dynamic filter pushdown in FilteredReadExec

Open
#7,562 3 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement performance rust
Dominant language
Rust
Stars
7.1k
Forks
852
Avg merge
3d 18h
Merged PRs (30d)
272

Description

DataFusion 53.1 (our vendored version) implements dynamic filter pushdown for hash joins: HashJoinExec builds a DynamicFilterPhysicalExpr from the build side's join keys once the build phase completes, and propagates it to the probe side via ExecutionPlan::gather_filters_for_pushdown / handle_child_pushdown_result (datafusion-physical-plan-53.1.0/src/joins/hash_join/{exec.rs,shared_bounds.rs}; see also the DataFusion blog post).

FilteredReadExec (rust/lance/src/io/exec/filtered_read.rs) does not implement either trait method, so this pushdown is currently a no-op for any plan where a Lance scan is the probe side of a join — the filter is generated and offered but has nowhere to land.

Why this matters

merge_insert (#7367) plans the target scan as a FilteredReadExec probed against a hash join built from the (usually smaller) source side. If FilteredReadExec accepted the pushed-down dynamic filter, it could skip decoding — or, if per-page/fragment key statistics are available, skip reading entirely — target rows that can't match any source key, in a single sequential scan pass. That would avoid the join → TakeExec round trip (and its random-I/O cost) that late-materialization approaches have to reason about, for at least the case where a dynamic filter usefully narrows the scan.

This is likely useful beyond merge_insert for any join where a Lance scan is the probe side and the build side is small/selective.

Scope

  • Implement ExecutionPlan::gather_filters_for_pushdown / handle_child_pushdown_result on FilteredReadExec to accept a dynamically-populated PhysicalExpr.
  • Apply the filter during scan execution: at minimum evaluate it per-batch/row before returning results; if feasible, use existing column statistics (if any) for page/fragment-level pruning.
  • Benchmark against a join-heavy workload (e.g. merge_insert backfill) to confirm it reduces I/O without regressing plans where the filter doesn't help (non-clustered keys, filters that can't prune anything).

Surfaced while assessing follow-up work for #7367 (merge_insert late materialization).

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in rust/lance/src/io/exec/filtered_read.rs and compare its execution-plan methods with DataFusion's hash join implementation in datafusion-physical-plan-53.1.0/src/joins/hash_join/{exec.rs,shared_bounds.rs}. Trace gather_filters_for_pushdown and handle_child_pushdown_result first, then run a join-heavy workload such as the merge_insert backfill. Done means the dynamic filter reaches scan execution, filters rows before results are returned, and benchmarks show reduced I/O without regressions when pruning is ineffective.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
backend, data-engineering, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.