sunchao commented on PR #24526: URL: https://github.com/apache/datafusion/pull/24526#issuecomment-5431228525
Thanks @adriangb — responding to [your review](https://github.com/apache/datafusion/pull/24526#pullrequestreview-5031171856). **Origin:** This grew out of our Spark/Comet work on sparse runtime filters. We developed the implementation for that workload using sorted-set interval lookup, then brought the approach into DataFusion. I don't have a particular paper to cite, and I'm not claiming algorithmic novelty. There is related earlier work in #8669, which we found while assessing the upstream contribution. **Limits:** I've added an explicit table to the PR description and builder docs in [80898fa](https://github.com/apache/datafusion/pull/24526/commits/80898fa91dd2c514175884e59c4877a8c3d25189), and corrected the configuration docs. With nonempty input length `N` (before deduplication) and configured cap `C`, the boundaries are inclusive: `N <= min(20, C)` uses the existing per-value rewrite; `20 < N <= C` uses the compact form only for eligible positive, non-null literal strings, otherwise the existing rewrite. `N > C` and `C = 0` skip this `IN` min/max rewrite, not all pruning. Other predicates and literal/containment pruning, including Bloom filters, remain available. **Large non-string lists:** Agreed, raising the same cap can still produce a large OR tree for numeric `IN` lists (or an AND chain for `NOT IN`). The docs now warn about that. A separate expansion budget and compact-domain admission limit would address this more directly; I would handle that separately rather than change the existing cap policy in this PR. **Enclosing-range fallback:** Agreed that it can still be useful, including for clustered or time-correlated identifiers. The loss of sparse-gap precision is a tradeoff, not a reason to rule it out. It gives a constant-size predicate and a constant number of comparisons per interval; finding the list's extrema still requires an O(N) pass. Adding it above the cap would change the current eligibility contract, so it needs an explicit policy that preserves the zero-cap opt-out. **Other types:** There is no fundamental string-only limitation to the interval lookup. Integers and binary values are natural follow-ups, with their own ordering and representation tests. This PR stays focused on the string workload; types with additional ordering concerns, such as floats, need separate handling. **NOT IN / NULL:** These also merit follow-up work, but column null counts alone are not sufficient. A non-null `x` can produce UNKNOWN from `x NOT IN (..., NULL)`. Dropping the NULL literal changes UNKNOWN to FALSE for the corresponding positive `IN`, which can make the inverse-predicate proof incorrectly classify a whole row group as fully matching. The direct physical-source regression with `LIMIT 1` checks that this query does not bypass filtering; unit tests separately assert that NULL-containing lists do not use the compact path. Also, negating interval intersection is not a valid `NOT IN` implementation: an overlapping interval does not prove every row belongs to the excluded set. I kept both exclusions here; support needs to preserve predicate-generated UNKNOWN in the all-match proof and use an appropriate `NOT IN` pruning rule. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
