hhhizzz opened a new issue, #23933: URL: https://github.com/apache/datafusion/issues/23933
### Is your feature request related to a problem or challenge? `HashJoinExec` dynamic filters currently retain both min/max bounds and an exact membership predicate: ```text min <= probe_key AND probe_key <= max AND probe_key IN (build_keys) ``` For larger build sides, the membership predicate is a hash-table lookup instead of an `InListExpr`. Keeping both predicates is useful in the general case: bounds provide cheap pruning and short-circuiting, while membership removes values in gaps. This distinction was discussed when membership pushdown was added in #18393 ([question](https://github.com/apache/datafusion/pull/18393#discussion_r2546056222), [answer](https://github.com/apache/datafusion/pull/18393#discussion_r2546317584)). However, exact membership is redundant when a single-column integer build-key domain is contiguous. For example: ```text distinct build keys = {100, 101, 102, 103} min = 100 max = 103 distinct_count = 4 inclusive_span = max - min + 1 = 4 ``` In this case, the bounds and membership predicates accept exactly the same matchable integer values. Evaluating an `InListExpr` or `HashTableLookupExpr` for every probe row therefore adds CPU cost without providing additional filtering. This is a narrow follow-up to #17171 and #18393. It also addresses one provable subset of the dynamic-filter evaluation overhead tracked in #19858. ### Describe the solution you'd like When constructing a HashJoin dynamic filter, omit its exact membership predicate if all of the following can be proven: 1. The dynamic filter has exactly one key column. 2. Its min and max values have the same supported integer type. 3. The distinct matchable build-key count is available. 4. The inclusive integer span can be computed safely. 5. The following equality holds: ```text distinct_key_count == max - min + 1 ``` Let `K` be the set of distinct matchable build keys and let `I` be the inclusive integer interval from `min(K)` through `max(K)`. By definition, `K` is a subset of `I`, and `|I| = max(K) - min(K) + 1`. Therefore, if `|K| == |I|`, then `K == I`, so exact membership and inclusive bounds are equivalent. Existing null handling is unchanged; HashJoin dynamic-filter pushdown is already disabled for `NullEqualsNull` joins. The implementation can reuse the distinct-key count already maintained by the build hash map. For the `InList` strategy, that count can be carried alongside the values, avoiding another scan or deduplication pass. The same proof applies to both `InListExpr` and `HashTableLookupExpr`. When the proof succeeds, the generated dynamic filter should contain only the bounds. An observability counter for the number of elided membership filters would also make the optimization visible in execution metrics. The optimization must fail closed and retain the current membership predicate for: - zero or multiple join-key columns; - non-integer key types; - mismatched min/max types; - unavailable, null, reversed, or otherwise unsupported bounds; - unsafe or unrepresentable span arithmetic; - unavailable or inconsistent distinct-key counts; - any gapped domain; - any other shape for which equivalence cannot be proven. This is exact canonicalization only. It does not introduce a density threshold, cost heuristic, configuration option, or public API. When filters are composed per partition, the count and bounds used by the proof must describe the same key set. If partition filters are first merged globally, the proof should run after that merge. ### Describe alternatives you've considered 1. **Always retain bounds and membership.** This remains the correct fallback for general and gapped domains, but pays membership evaluation cost when the predicate is provably redundant. 2. **Skip membership based on filter placement.** #23701 proposes broadly skipping membership when filters are not pushed into the scan. That is complementary but uses a different condition. Exact domain canonicalization remains useful when Arrow row-filter pushdown is enabled. 3. **Choose membership based on estimated selectivity or runtime cost.** This may be useful as a broader adaptive policy, but it is a separate optimization. This proposal changes expression shape only when the two predicates are semantically equivalent. 4. **Only make membership evaluation faster.** Faster `IN` and hash-table evaluation helps gapped domains where membership is necessary. It cannot remove unnecessary work in a contiguous domain. There is active structural work around the same expression-building seam: - #21931 simplifies HashJoin dynamic-filter shapes and merges membership data; - #23370 centralizes expression composition; - #23701 makes membership generation aware of pushdown placement; - #23817 explores storing partitioning in dynamic filters. None of these currently implements the contiguous-integer cardinality proof. If one lands first, this optimization can be placed after membership merging or in the centralized expression composer. ### Additional context _No response_ -- 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]
