apache / apache/datafusion

Consider an enclosing-range fallback for `IN` lists above `max_in_list_size`

Open
#24,708 1 comment 0 reactions 0 assignees View on GitHub
enhancement performance
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

Follow-up from #24526.

Today an `IN` list longer than `datafusion.execution.parquet.max_in_list_size` falls through to the unhandled-predicate hook, so it contributes no container pruning at all. (Other predicates and literal/containment pruning, including Bloom filters, still apply.)

A much weaker form is available at close to no cost: collapse the list to its extrema and test interval overlap, roughly `vmin <= col_max AND col_min <= vmax`. Constant-size predicate, a couple of comparisons per container, and finding the extrema is one O(N) pass with no sort. It also wouldn't need a custom `PhysicalExpr` or the string-only restriction, so it could apply to any orderable type.

The tradeoff is that it can only rule out containers lying entirely outside the hull — it can never prune a gap, which is exactly the precision the compact form exists to preserve. How much it's worth probably depends on how clustered the requested values are relative to the data's ordering: for a set spread across the whole domain it prunes nothing, while for clustered or time-correlated identifiers (ULIDs came up in review) it may capture much of the available win.

Open questions:

- Is this worth having as a tier below the cap's current give-up behaviour?
- If so, what policy? It changes the current eligibility contract, and should presumably still respect `max_in_list_size = 0` as a full opt-out.
- Does it also make sense as the fallback for types a compact path doesn't cover (#24709)?

It doesn't help `NOT IN` — an overlapping interval says nothing about whether every row is excluded.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing follow-up #24526 and the current handling of IN lists above datafusion.execution.parquet.max_in_list_size. Compare the proposed enclosing-range fallback with the compact path in #24709, including max_in_list_size=0 and NOT IN behavior; done requires an agreed policy and implementation scope.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.