jayzhan211 commented on PR #25292: URL: https://github.com/apache/datafusion/pull/25292#issuecomment-5749518045
Thanks @gruuya, the caching fix looks good, and on ≈ off in the unclustered case matches what I'd expect now. On the default: rather than picking between 100k / 32K / 0, I wonder if we can drop hash_join_dynamic_pruning_max_distinct_values (and _max_size) altogether. The cap is only needed because we keep the exact key set: an O(n log n) sort under the OnceLock on the first file open, 8·n bytes that aren't accounted for, and the raw key array pinned by the plan. But pruning only asks "is there a build key in [min, max]?", and any superset of the keys answers that soundly. Precision is limited by how many containers there are, not by how many keys, so a fixed-size summary should lose very little. Concretely, a bucket bitmap over the key bounds we already compute in collect_left_input: - Build: one O(n) pass over left_values[0], no sort or dedup. bucket = (v.wrapping_sub(min) as u64) >> shift, the same offset trick as ArrayMap::key_to_index. - Size: clamp(next_pow2(8 * num_rows), 2^10, 2^20) bits, so at most 128 KB per partition (same figure as hash_join_inlist_pushdown_max_size). If range + 1 fits, use shift = 0 and the bitmap is exact, which covers date keys and small surrogate-id dims. - Check: clamp the container's [min, max] to the build bounds, map both ends to buckets, scan for any set bit with early exit. A wide container, like the unclustered repro above, hits a set bit in the first word. - No benefit means no cost: if every bucket is set, the summary can't prune anything the bounds predicate doesn't already, so return None and emit no pruning clause. That is a property of the summary rather than a tuned cutoff, and it behaves the same as "off". - No cliff: the false-keep rate for a narrow container is bounded by the fill ratio (≤ n/B, so ≤ 12.5% up to 128k keys) and degrades gradually after that. Clustered keys, the only case where this feature helps, share buckets, so fill stays low at any n. Today a clustered 150k-key build side gets nothing. On your example from the description (40k keys, range ≈ 2M, bucket width 4, row groups 1000 wide) I'd expect the same 2000 → 200 row groups. It also simplifies the PR a bit: - PruningDomain (Mutex + OnceLock + built-for-type cache + the builder closure) becomes a plain Option<Arc<KeyRangeSummary>> on HashTableLookupExpr, built eagerly and charged to the build reservation. - build_in_list_domain_expr, string_values, binary_values and the PrimitiveInListDomain::from_array additions go away. - The OptimizerOptions semver failure disappears with the two configs. - The CaseExpr → OR-of-branches rewrite stays as is. Trade-offs I can see: - v1 would cover integer-like keys only (ints, dates, timestamps, decimals). Strings could follow by stripping the common prefix of the global min/max and taking the next 8 big-endian bytes; floats need an order-preserving bit mapping. - A sentinel key (-1, i64::MAX) stretches the range and coarsens the buckets. If that shows up in practice, a sampled core range plus two tail intervals keeps it O(n). - The O(n) pass is paid on every build that falls back to Map. I'd expect it to be small next to the hash build, but it needs measuring on a large build side. I haven't benchmarked any of this yet. Happy to prototype it on top of your branch and post A/B numbers (your clustered case, the unclustered repro, and a clustered build side past 100k keys) if you think it's worth pursuing. If you'd rather land the current approach first, I'd lean towards a lower default for now and do this as a follow-up. -- 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]
