sunchao commented on code in PR #24781:
URL: https://github.com/apache/datafusion/pull/24781#discussion_r3916354962
##########
datafusion/pruning/src/string_in_list.rs:
##########
@@ -151,19 +184,46 @@ impl PhysicalExpr for StringInListPruningExpr {
// uses actual Arrow partition values.
PrunableStatistics
// trusts file providers' bounds: there is no ordering
gate
// for arbitrary statistics providers here.
- let index = self.values.partition_point(|v|
v.as_bytes() < min);
- Some(self.values.get(index).is_some_and(|v|
v.as_bytes() <= max))
+ match self.membership {
+ SetMembership::In => {
+ let index =
+ self.values.partition_point(|v|
v.as_bytes() < min);
+ Some(
+ self.values
+ .get(index)
+ .is_some_and(|v| v.as_bytes() <= max),
+ )
+ }
+ // A wider interval can always hold a value
outside the
+ // domain, which satisfies NOT IN. Only an interval
+ // pinned to one domain value rules out every row.
+ // Truncated Parquet bounds cannot fake that: min
+ // truncates downward and max upward, so equal
bounds
+ // mean the true values were equal too. This arm
also
+ // compares for equality rather than order, so it
does
+ // not rely on the bound ordering the IN arm needs.
+ SetMembership::NotIn => {
+ Some(min != max || !self.contains(min))
+ }
+ }
}
// A missing bound makes that end of the interval
unbounded.
// Exclude only when the whole domain lies beyond the
known bound;
// gaps within the domain and equality cannot prove
disjointness.
+ // An unbounded interval is never single-valued, so NOT IN
takes
+ // neither arm.
(Some(min), None)
- if self.values.last().is_some_and(|v| v.as_bytes() <
min) =>
+ if self.membership == SetMembership::In
Review Comment:
[P2] Preserve the OR short circuit when only one bound is known
For `NOT IN`, these guards send every one-sided interval to `None`,
including cases where the old comparison chain returned `true`. For example,
with `s_min = 'zzz'`, absent `s_max`, and no null rows, every comparison in `s
NOT IN ('a00', ..., 'a20')` is already true on the known bound. Returning NULL
still keeps the same containers, but an enclosing OR now has to evaluate its
other branch. Modern Parquet min/max fields are independently optional, and
this metadata passes the existing ordering/trust checks.
I reproduced this with cap 1,024 and 4,096 Utf8View containers: `s NOT IN
('a00', ..., 'a20') OR n IN (0, 10, ..., 10230)`, with `n_min = n_max = 10229`,
null counts 0 and row counts 128. Base pruning took 0.142 ms versus 5.46 ms
here (about 38x); both retained every container. This is extra CPU, not
incorrect data.
Could we add explicit `NotIn` arms that return `Some(true)` when the known
bound is absent from the domain, keeping UNKNOWN when it is a domain member,
and cover this composed-OR case?
##########
datafusion/pruning/src/string_in_list.rs:
##########
@@ -151,19 +184,46 @@ impl PhysicalExpr for StringInListPruningExpr {
// uses actual Arrow partition values.
PrunableStatistics
// trusts file providers' bounds: there is no ordering
gate
// for arbitrary statistics providers here.
- let index = self.values.partition_point(|v|
v.as_bytes() < min);
- Some(self.values.get(index).is_some_and(|v|
v.as_bytes() <= max))
+ match self.membership {
+ SetMembership::In => {
+ let index =
+ self.values.partition_point(|v|
v.as_bytes() < min);
+ Some(
+ self.values
+ .get(index)
+ .is_some_and(|v| v.as_bytes() <= max),
+ )
+ }
+ // A wider interval can always hold a value
outside the
+ // domain, which satisfies NOT IN. Only an interval
+ // pinned to one domain value rules out every row.
+ // Truncated Parquet bounds cannot fake that: min
+ // truncates downward and max upward, so equal
bounds
+ // mean the true values were equal too. This arm
also
+ // compares for equality rather than order, so it
does
+ // not rely on the bound ordering the IN arm needs.
+ SetMembership::NotIn => {
+ Some(min != max || !self.contains(min))
Review Comment:
[P2] Avoid scanning long bounds before checking domain membership
This new path first goes through `min > max` above, then evaluates `min !=
max` before looking in the domain. Both comparisons can scan the entire common
prefix even when short list literals could reject `min` immediately. The
previous per-literal equality kernels reject such values using their
length/prefix.
With cap 21, literals `a00000000` through `a00000020`, and 4,096 Utf8View
containers whose bounds are `"z".repeat(16384) + "a"` and `"z".repeat(16384) +
"z"`, pruning took 0.229 ms on base versus 6.63 ms here (about 29x), with
identical keep decisions. These are prepared-statistics pruning timings; actual
Parquet statistics conversion adds work in both versions. The case is reachable
with larger/untruncated statistics or custom statistics providers, while the
default writer's 64-byte truncation limits exposure.
Could we handle `NotIn` before the ordering guard and use a
domain-membership rejection before comparing the full bounds, with a benchmark
for long common prefixes?
--
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]
