Consider an enclosing-range fallback for `IN` lists above `max_in_list_size`
- 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
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