sunchao commented on code in PR #24781:
URL: https://github.com/apache/datafusion/pull/24781#discussion_r3931041925
##########
datafusion/pruning/src/string_in_list.rs:
##########
@@ -27,48 +27,78 @@ use datafusion_common::{Result, assert_eq_or_internal_err};
use datafusion_physical_expr::{PhysicalExpr, PhysicalExprRef};
use datafusion_physical_plan::ColumnarValue;
-/// Tests whether a sorted string domain intersects an inclusive statistics
interval.
+/// Which `IN` form a sorted string domain is pruning for.
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub(crate) enum SetMembership {
+ /// `col IN (...)`. A row matches only where the domain intersects the
+ /// interval, so a disjoint interval excludes every row.
+ In,
+ /// `col NOT IN (...)`. Overlap proves nothing here: values outside the
+ /// domain still satisfy the predicate. An interval excludes every row only
+ /// when it holds a single value that the domain contains.
+ NotIn,
+}
+
+/// Tests an inclusive statistics interval against a sorted string domain.
///
/// [`PhysicalExpr::evaluate`] returns one nullable Boolean per min/max
interval:
-/// * `true`: the interval intersects the domain, so matching rows may exist.
-/// * `false`: the available bounds prove the interval disjoint from the
domain.
+/// * `true`: matching rows may exist, so the container must be read.
+/// * `false`: the available bounds prove no row can match.
/// * `NULL`: incomplete, invalid, or unusable bounds prevent a safe decision.
///
-/// A single known bound can still prove disjointness. Otherwise, unknown
results
-/// keep the container eligible for reading.
+/// [`SetMembership`] selects the test. For [`SetMembership::In`] a single
known
+/// bound can still prove disjointness. For [`SetMembership::NotIn`], one known
+/// bound outside the domain proves the container may match, while two equal
+/// bounds in the domain prove it cannot. This is the same reach as the
per-value
+/// `min != v OR v != max` chain it replaces. Otherwise, unknown results keep
the
+/// container eligible for reading.
///
/// This expression is used only for pruning; the original IN remains the row
filter.
#[derive(Debug, Eq)]
pub(crate) struct StringInListPruningExpr {
+ membership: SetMembership,
min: PhysicalExprRef,
max: PhysicalExprRef,
values: Arc<[String]>,
}
impl StringInListPruningExpr {
pub(crate) fn new(
+ membership: SetMembership,
min: PhysicalExprRef,
max: PhysicalExprRef,
mut values: Vec<String>,
) -> Self {
values.sort_unstable();
values.dedup();
Self {
+ membership,
min,
max,
values: values.into(),
}
}
+
+ /// Does the sorted, deduplicated domain hold `value`?
+ fn contains(&self, value: &[u8]) -> bool {
+ self.values
+ .binary_search_by(|candidate| candidate.as_bytes().cmp(value))
Review Comment:
[P2] Reject impossible string lengths before scanning shared prefixes
There is still a long-prefix regression when the list literals also share
the statistics prefix. `contains()` performs lexicographic comparisons even
when the bound and every candidate have different lengths. The former Arrow
equality kernels reject these candidates by length without reading the string
buffers.
For example, use cap 21, `prefix = "z".repeat(16384)`, literals `prefix +
"domain00000000"` through `prefix + "domain00000020"`, and 4,096 Utf8View
containers with `min = max = prefix + "a"`. Identical base/head probes keep
every container, but prepared-statistics pruning takes 0.230 ms on base versus
8.96 ms here (about 39x). The added long-prefix benchmark uses short literals,
so it misses this case.
This is a CPU regression, not an incorrect-result issue. It requires a
raised cap and long untruncated/custom statistics; the default cap of 20 avoids
the path, and the control with 64-byte bounds improved when construction was
included. Actual Parquet metadata conversion is outside these timings.
Could we sort and search the existing `NOT IN` domain by `(byte length,
bytes)`, using the same comparator in both places, while keeping positive `IN`
lexicographically ordered for interval searches? That rejects absent lengths
before scanning prefixes without adding another collection. Please also cover
long literals sharing the bounds' prefix in the benchmark.
--
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]
