NGA-TRAN commented on code in PR #8440:
URL: https://github.com/apache/arrow-datafusion/pull/8440#discussion_r1431942220
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -254,9 +295,91 @@ impl PruningPredicate {
is_always_true(&self.predicate_expr)
}
- pub(crate) fn required_columns(&self) -> &RequiredStatColumns {
+ pub(crate) fn required_columns(&self) -> &RequiredColumns {
&self.required_columns
}
+
+ /// Names of the columns that are known to be / not be in a set
+ /// of literals (constants). These are the columns the that may be passed
to
+ /// [`PruningStatistics::contained`] during pruning.
+ ///
+ /// This is useful to avoid fetching statistics for columns that will not
be
+ /// used in the predicate. For example, it can be used to avoid reading
+ /// uneeded bloom filters (a non trivial operation).
+ pub fn literal_columns(&self) -> Vec<String> {
+ let mut seen = HashSet::new();
+ self.literal_guarantees
+ .iter()
+ .map(|e| &e.column.name)
+ // avoid duplicates
+ .filter(|name| seen.insert(*name))
+ .map(|s| s.to_string())
+ .collect()
+ }
+}
+
+/// Builds the return `Vec` for [`PruningPredicate::prune`].
+#[derive(Debug)]
+struct BoolVecBuilder {
+ /// One element per container. Each element is
+ /// * `true`: if the container has row that may pass the predicate
+ /// * `false`: if the container has rows that DEFINITELY DO NOT pass the
predicate
+ inner: Vec<bool>,
+}
+
+impl BoolVecBuilder {
+ /// Create a new `BoolVecBuilder` with `num_containers` elements
+ fn new(num_containers: usize) -> Self {
+ Self {
+ // assume by default all containers may pass the predicate
+ inner: vec![true; num_containers],
+ }
+ }
+
+ /// Combines result `array` for a conjunct (e.g. `AND` clause) of a
+ /// predicate into the currently in progress array.
+ ///
+ /// Each `array` element is:
+ /// * `true`: container has row that may pass the predicate
+ /// * `false`: all container rows DEFINITELY DO NOT pass the predicate
+ /// * `null`: container may or may not have rows that pass the predicate
+ fn append_array(&mut self, array: &BooleanArray) {
+ assert_eq!(array.len(), self.inner.len());
+ for (cur, new) in self.inner.iter_mut().zip(array.iter()) {
+ // `false` for this conjunct means we know for sure no rows could
+ // pass the predicate and thus we set the corresponding container
+ // location to false.
+ if let Some(false) = new {
+ *cur = false;
+ }
+ }
+ }
+
+ /// Combines the results in the [`ColumnarValue`] to the currently in
+ /// progress array, following the same rules as [`Self::append_array`].
+ ///
+ /// # Panics
+ /// If `value` is not boolean
+ fn append_value(&mut self, value: ColumnarValue) {
+ match value {
+ ColumnarValue::Array(array) => {
+ self.append_array(array.as_boolean());
+ }
+ ColumnarValue::Scalar(ScalarValue::Boolean(Some(false))) => {
+ // False means all containers can not pass the predicate
+ self.inner = vec![false; self.inner.len()];
+ }
+ _ => {
+ // Null or true means the rows in container may pass this
+ // conjunct so we can't prune any containers based on that
+ }
+ }
+ }
Review Comment:
These append functions are nice. Easy to understand.
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -993,95 +1115,139 @@ mod tests {
///
/// Note All `ArrayRefs` must be the same size.
struct ContainerStats {
- min: ArrayRef,
- max: ArrayRef,
+ min: Option<ArrayRef>,
+ max: Option<ArrayRef>,
/// Optional values
null_counts: Option<ArrayRef>,
+ /// Optional known values (e.g. mimic a bloom filter)
+ /// (value, contained)
+ /// If present, all BooleanArrays must be the same size as min/max
+ contained: Vec<(HashSet<ScalarValue>, BooleanArray)>,
}
impl ContainerStats {
+ fn new() -> Self {
+ Default::default()
+ }
fn new_decimal128(
min: impl IntoIterator<Item = Option<i128>>,
max: impl IntoIterator<Item = Option<i128>>,
precision: u8,
scale: i8,
) -> Self {
- Self {
- min: Arc::new(
+ Self::new()
+ .with_min(Arc::new(
min.into_iter()
.collect::<Decimal128Array>()
.with_precision_and_scale(precision, scale)
.unwrap(),
- ),
- max: Arc::new(
+ ))
+ .with_max(Arc::new(
max.into_iter()
.collect::<Decimal128Array>()
.with_precision_and_scale(precision, scale)
.unwrap(),
- ),
- null_counts: None,
- }
+ ))
}
fn new_i64(
min: impl IntoIterator<Item = Option<i64>>,
max: impl IntoIterator<Item = Option<i64>>,
) -> Self {
- Self {
- min: Arc::new(min.into_iter().collect::<Int64Array>()),
- max: Arc::new(max.into_iter().collect::<Int64Array>()),
- null_counts: None,
- }
+ Self::new()
+ .with_min(Arc::new(min.into_iter().collect::<Int64Array>()))
+ .with_max(Arc::new(max.into_iter().collect::<Int64Array>()))
}
fn new_i32(
min: impl IntoIterator<Item = Option<i32>>,
max: impl IntoIterator<Item = Option<i32>>,
) -> Self {
- Self {
- min: Arc::new(min.into_iter().collect::<Int32Array>()),
- max: Arc::new(max.into_iter().collect::<Int32Array>()),
- null_counts: None,
- }
+ Self::new()
+ .with_min(Arc::new(min.into_iter().collect::<Int32Array>()))
+ .with_max(Arc::new(max.into_iter().collect::<Int32Array>()))
}
fn new_utf8<'a>(
min: impl IntoIterator<Item = Option<&'a str>>,
max: impl IntoIterator<Item = Option<&'a str>>,
) -> Self {
- Self {
- min: Arc::new(min.into_iter().collect::<StringArray>()),
- max: Arc::new(max.into_iter().collect::<StringArray>()),
- null_counts: None,
- }
+ Self::new()
+ .with_min(Arc::new(min.into_iter().collect::<StringArray>()))
+ .with_max(Arc::new(max.into_iter().collect::<StringArray>()))
}
fn new_bool(
min: impl IntoIterator<Item = Option<bool>>,
max: impl IntoIterator<Item = Option<bool>>,
) -> Self {
- Self {
- min: Arc::new(min.into_iter().collect::<BooleanArray>()),
- max: Arc::new(max.into_iter().collect::<BooleanArray>()),
- null_counts: None,
- }
+ Self::new()
+ .with_min(Arc::new(min.into_iter().collect::<BooleanArray>()))
+ .with_max(Arc::new(max.into_iter().collect::<BooleanArray>()))
}
fn min(&self) -> Option<ArrayRef> {
- Some(self.min.clone())
+ self.min.clone()
}
fn max(&self) -> Option<ArrayRef> {
- Some(self.max.clone())
+ self.max.clone()
}
fn null_counts(&self) -> Option<ArrayRef> {
self.null_counts.clone()
}
+ /// return an iterator over all arrays in this statistics
+ fn arrays(&self) -> Vec<ArrayRef> {
+ let contained_arrays = self
+ .contained
+ .iter()
+ .map(|(_values, contained)| Arc::new(contained.clone()) as
ArrayRef);
+
+ [
+ self.min.as_ref().cloned(),
+ self.max.as_ref().cloned(),
+ self.null_counts.as_ref().cloned(),
+ ]
+ .into_iter()
+ .flatten()
+ .chain(contained_arrays)
+ .collect()
+ }
+
fn len(&self) -> usize {
- assert_eq!(self.min.len(), self.max.len());
- self.min.len()
+ // pick the first non zero length
+ self.arrays().iter().map(|a| a.len()).next().unwrap_or(0)
+ }
Review Comment:
Maybe add comment to explain what this `len` function does so we understand
why it return first non zero length?
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -2484,10 +2630,466 @@ mod tests {
// TODO: add other negative test for other case and op
}
+ #[test]
+ fn prune_with_contained_one_column() {
+ let schema = Arc::new(Schema::new(vec![Field::new("s1",
DataType::Utf8, true)]));
+
+ // Model having information like a bloom filter for s1
+ let statistics = TestStatistics::new()
+ .with_contained(
+ "s1",
+ [ScalarValue::from("foo")],
+ [
+ // container 0 known to only contain "foo"",
+ Some(true),
+ // container 1 known to not contain "foo"
+ Some(false),
+ // container 2 unknown about "foo"
+ None,
+ // container 3 known to only contain "foo"
+ Some(true),
+ // container 4 known to not contain "foo"
+ Some(false),
+ // container 5 unknown about "foo"
+ None,
+ // container 6 known to only contain "foo"
+ Some(true),
+ // container 7 known to not contain "foo"
+ Some(false),
+ // container 8 unknown about "foo"
+ None,
+ ],
+ )
+ .with_contained(
+ "s1",
+ [ScalarValue::from("bar")],
+ [
+ // containers 0,1,2 known to only contain "bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 known to not contain "bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 unknown about "bar"
+ None,
+ None,
+ None,
+ ],
+ )
+ .with_contained(
+ // the way the tests are setup, this data is
+ // consulted if the "foo" and "bar" are being checked at the
same time
+ "s1",
+ [ScalarValue::from("foo"), ScalarValue::from("bar")],
+ [
+ // container 0,1,2 unknown about ("foo, "bar")
+ None,
+ None,
+ None,
+ // container 3,4,5 known to contain only either "foo" and
"bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 6,7,8 known ro contain neither "foo" and
"bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ ],
+ );
+
+ // s1 = 'foo'
+ prune_with_expr(
+ col("s1").eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers ('false) where we know foo is not present
+ vec![true, false, true, true, false, true, true, false, true],
+ );
+
+ // s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("bar")),
+ &schema,
+ &statistics,
+ // rule out containers where we know bar is not present
+ vec![true, true, true, false, false, false, true, true, true],
+ );
+
+ // s1 = 'baz' (unknown value)
+ prune_with_expr(
+ col("s1").eq(lit("baz")),
+ &schema,
+ &statistics,
+ // can't rule out anything
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' AND s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).and(col("s1").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // logically this predicate can't possibly be true (the column
can't
+ // take on both values) but we could rule it out if the stats tell
+ // us that both values are not present
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' OR s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).or(col("s1").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can rule out containers that we know contain neither foo nor bar
+ vec![true, true, true, true, true, true, false, false, false],
+ );
+
+ // s1 = 'foo' OR s1 = 'baz'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).or(col("s1").eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // can't rule out anything container
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' OR s1 = 'bar' OR s1 = 'baz'
+ prune_with_expr(
+ col("s1")
+ .eq(lit("foo"))
+ .or(col("s1").eq(lit("bar")))
+ .or(col("s1").eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // can rule out any containers based on knowledge of s1 and `foo`,
+ // `bar` and (`foo`, `bar`)
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 != foo
+ prune_with_expr(
+ col("s1").not_eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers we know for sure only contain foo
+ vec![false, true, true, false, true, true, false, true, true],
+ );
+
+ // s1 != bar
+ prune_with_expr(
+ col("s1").not_eq(lit("bar")),
+ &schema,
+ &statistics,
+ // rule out when we know for sure s1 has the value bar
+ vec![false, false, false, true, true, true, true, true, true],
+ );
+
+ // s1 != foo AND s1 != bar
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .and(col("s1").not_eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can rule out any container where we know s1 does not have
either 'foo' or 'bar'
+ vec![true, true, true, false, false, false, true, true, true],
+ );
+
+ // s1 != foo AND s1 != bar AND s1 != baz
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .and(col("s1").not_eq(lit("bar")))
+ .and(col("s1").not_eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // can't rule out any container based on knowledge of s1,s2
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 != foo OR s1 != bar
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .or(col("s1").not_eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // cant' rule out anything based on contains information
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 != foo OR s1 != bar OR s1 != baz
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .or(col("s1").not_eq(lit("bar")))
+ .or(col("s1").not_eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // cant' rule out anything based on contains information
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+ }
+
+ #[test]
+ fn prune_with_contained_two_columns() {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("s1", DataType::Utf8, true),
+ Field::new("s2", DataType::Utf8, true),
+ ]));
+
+ // Model having information like bloom filters for s1 and s2
+ let statistics = TestStatistics::new()
+ .with_contained(
+ "s1",
+ [ScalarValue::from("foo")],
+ [
+ // container 0, s1 known to only contain "foo"",
+ Some(true),
+ // container 1, s1 known to not contain "foo"
+ Some(false),
+ // container 2, s1 unknown about "foo"
+ None,
+ // container 3, s1 known to only contain "foo"
+ Some(true),
+ // container 4, s1 known to not contain "foo"
+ Some(false),
+ // container 5, s1 unknown about "foo"
+ None,
+ // container 6, s1 known to only contain "foo"
+ Some(true),
+ // container 7, s1 known to not contain "foo"
+ Some(false),
+ // container 8, s1 unknown about "foo"
+ None,
+ ],
+ )
+ .with_contained(
+ "s2", // for column s2
+ [ScalarValue::from("bar")],
+ [
+ // containers 0,1,2 s2 known to only contain "bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 s2 known to not contain "bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 s2 unknown about "bar"
+ None,
+ None,
+ None,
+ ],
+ );
+
+ // s1 = 'foo'
+ prune_with_expr(
+ col("s1").eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers where we know s1 is not present
+ vec![true, false, true, true, false, true, true, false, true],
+ );
+
+ // s1 = 'foo' OR s2 = 'bar'
+ let expr = col("s1").eq(lit("foo")).or(col("s2").eq(lit("bar")));
+ prune_with_expr(
+ expr,
+ &schema,
+ &statistics,
+ // can't rule out any container (would need to prove that s1 !=
foo AND s2 != bar)
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' AND s2 != 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).and(col("s2").not_eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can only rule out container where we know either:
+ // 1. s1 doesn't have the value 'foo` or
+ // 2. s2 has only the value of 'bar'
+ vec![false, false, false, true, false, true, true, false, true],
+ );
+
+ // s1 != 'foo' AND s2 != 'bar'
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .and(col("s2").not_eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // Can rule out any container where we know either
+ // 1. s1 has only the value 'foo'
+ // 2. s2 has only the value 'bar'
+ vec![false, false, false, false, true, true, false, true, true],
+ );
+
+ // s1 != 'foo' AND (s2 = 'bar' OR s2 = 'baz')
+ prune_with_expr(
+ col("s1").not_eq(lit("foo")).and(
+ col("s2")
+ .not_eq(lit("bar"))
+ .or(col("s2").not_eq(lit("baz"))),
+ ),
+ &schema,
+ &statistics,
+ // Can rule out any container where we know s1 has only the value
+ // 'foo'. Can't use knowledge of s2 and bar to rule out anything
+ vec![false, true, true, false, true, true, false, true, true],
+ );
+
+ // s1 like '%foo%bar%'
+ prune_with_expr(
+ col("s1").like(lit("foo%bar%")),
+ &schema,
+ &statistics,
+ // cant rule out anything with information we know
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 like '%foo%bar%' AND s2 = 'bar'
+ prune_with_expr(
+ col("s1")
+ .like(lit("foo%bar%"))
+ .and(col("s2").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can rule out any container where we know s2 does not have the
value 'bar'
+ vec![true, true, true, false, false, false, true, true, true],
+ );
+
+ // s1 like '%foo%bar%' OR s2 = 'bar'
+ prune_with_expr(
+ col("s1").like(lit("foo%bar%")).or(col("s2").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can't rule out anything (we would have to prove that both the
+ // like and the equality must be false)
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+ }
+
+ #[test]
+ fn prune_with_range_and_contained() {
+ // Setup mimics range information for i, a bloom filter for s
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("i", DataType::Int32, true),
+ Field::new("s", DataType::Utf8, true),
+ ]));
+
+ let statistics = TestStatistics::new()
+ .with(
+ "i",
+ ContainerStats::new_i32(
+ // Container 0, 3, 6: [-5 to 5]
+ // Container 1, 4, 7: [10 to 20]
+ // Container 2, 5, 9: unknown
+ vec![
+ Some(-5),
+ Some(10),
+ None,
+ Some(-5),
+ Some(10),
+ None,
+ Some(-5),
+ Some(10),
+ None,
+ ], // min
+ vec![
+ Some(5),
+ Some(20),
+ None,
+ Some(5),
+ Some(20),
+ None,
+ Some(5),
+ Some(20),
+ None,
+ ], // max
+ ),
+ )
+ // Add contained information about the s and "foo"
+ .with_contained(
+ "s",
+ [ScalarValue::from("foo")],
+ [
+ // container 0,1,2 known to only contain "foo"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 known to not contain "foo"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 unknown about "foo"
+ None,
+ None,
+ None,
+ ],
+ );
+
+ // i = 0 and s = 'foo'
+ prune_with_expr(
+ col("i").eq(lit(0)).and(col("s").eq(lit("foo"))),
+ &schema,
+ &statistics,
+ // Can rule out container where we know that either:
+ // 1. 0 is outside the min/max range of i
+ // 1. s does not contain foo
+ // (range is false, and contained is false)
+ vec![true, false, true, false, false, false, true, false, true],
+ );
+
+ // i = 0 and s != 'foo'
+ prune_with_expr(
+ col("i").eq(lit(0)).and(col("s").not_eq(lit("foo"))),
+ &schema,
+ &statistics,
+ // Can rule out containers where either:
+ // 1. 0 is outside the min/max range of i
+ // 2. s only contains foo
+ vec![false, false, false, true, false, true, true, false, true],
+ );
+
+ // i = 0 OR s = 'foo'
+ prune_with_expr(
+ col("i").eq(lit(0)).or(col("s").not_eq(lit("foo"))),
Review Comment:
```suggestion
col("i").eq(lit(0)).or(col("s").eq(lit("foo"))),
```
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -1090,14 +1256,36 @@ mod tests {
mut self,
counts: impl IntoIterator<Item = Option<i64>>,
) -> Self {
- // take stats out and update them
let null_counts: ArrayRef =
Arc::new(counts.into_iter().collect::<Int64Array>());
- assert_eq!(null_counts.len(), self.len());
+ self.assert_invariants();
self.null_counts = Some(null_counts);
self
}
+
+ /// Add contained informaation.
Review Comment:
```suggestion
/// Add contained information.
```
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -198,40 +232,47 @@ impl PruningPredicate {
///
/// [`ExprSimplifier`]:
crate::optimizer::simplify_expressions::ExprSimplifier
pub fn prune<S: PruningStatistics>(&self, statistics: &S) ->
Result<Vec<bool>> {
+ let mut builder = BoolVecBuilder::new(statistics.num_containers());
+
+ // Try to prove the predicate can't be true for the containers based on
+ // literal guarantees
+ for literal_guarantee in &self.literal_guarantees {
+ let LiteralGuarantee {
+ column,
+ guarantee,
+ literals,
+ } = literal_guarantee;
+ if let Some(results) = statistics.contained(column, literals) {
+ match guarantee {
+ // `In` means the values in the column must be one of the
+ // values in the set for the predicate to evaluate to true.
+ // If `contained` returns false, that means the column is
+ // not any of the values so we can prune the container
+ Guarantee::In => builder.append_array(&results),
+ // `NotIn` means the values in the column must must not be
+ // any of the values in the set for the predicate to
+ // evaluate to true. If contained returns true, it means
the
+ // column is only in the set of values so we can prune the
+ // container
+ Guarantee::NotIn => {
+ builder.append_array(&arrow::compute::not(&results)?)
Review Comment:
The Guarantee In and NotIn are used very nice here 👍
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -1135,13 +1323,34 @@ mod tests {
let container_stats = self
.stats
.remove(&col)
- .expect("Can not find stats for column")
+ .unwrap_or_default()
.with_null_counts(counts);
// put stats back in
self.stats.insert(col, container_stats);
self
}
+
+ /// Add contained informaation for the specified columm.
Review Comment:
```suggestion
/// Add contained information for the specified columm.
```
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -2484,10 +2630,466 @@ mod tests {
// TODO: add other negative test for other case and op
}
+ #[test]
+ fn prune_with_contained_one_column() {
+ let schema = Arc::new(Schema::new(vec![Field::new("s1",
DataType::Utf8, true)]));
+
+ // Model having information like a bloom filter for s1
+ let statistics = TestStatistics::new()
+ .with_contained(
+ "s1",
+ [ScalarValue::from("foo")],
+ [
+ // container 0 known to only contain "foo"",
+ Some(true),
+ // container 1 known to not contain "foo"
+ Some(false),
+ // container 2 unknown about "foo"
+ None,
+ // container 3 known to only contain "foo"
+ Some(true),
+ // container 4 known to not contain "foo"
+ Some(false),
+ // container 5 unknown about "foo"
+ None,
+ // container 6 known to only contain "foo"
+ Some(true),
+ // container 7 known to not contain "foo"
+ Some(false),
+ // container 8 unknown about "foo"
+ None,
+ ],
+ )
+ .with_contained(
+ "s1",
+ [ScalarValue::from("bar")],
+ [
+ // containers 0,1,2 known to only contain "bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 known to not contain "bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 unknown about "bar"
+ None,
+ None,
+ None,
+ ],
+ )
+ .with_contained(
+ // the way the tests are setup, this data is
+ // consulted if the "foo" and "bar" are being checked at the
same time
+ "s1",
+ [ScalarValue::from("foo"), ScalarValue::from("bar")],
+ [
+ // container 0,1,2 unknown about ("foo, "bar")
+ None,
+ None,
+ None,
+ // container 3,4,5 known to contain only either "foo" and
"bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 6,7,8 known ro contain neither "foo" and
"bar"
Review Comment:
```suggestion
// container 6,7,8 known to contain neither "foo" and
"bar"
```
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -2484,10 +2630,466 @@ mod tests {
// TODO: add other negative test for other case and op
}
+ #[test]
+ fn prune_with_contained_one_column() {
+ let schema = Arc::new(Schema::new(vec![Field::new("s1",
DataType::Utf8, true)]));
+
+ // Model having information like a bloom filter for s1
+ let statistics = TestStatistics::new()
+ .with_contained(
+ "s1",
+ [ScalarValue::from("foo")],
+ [
+ // container 0 known to only contain "foo"",
+ Some(true),
+ // container 1 known to not contain "foo"
+ Some(false),
+ // container 2 unknown about "foo"
+ None,
+ // container 3 known to only contain "foo"
+ Some(true),
+ // container 4 known to not contain "foo"
+ Some(false),
+ // container 5 unknown about "foo"
+ None,
+ // container 6 known to only contain "foo"
+ Some(true),
+ // container 7 known to not contain "foo"
+ Some(false),
+ // container 8 unknown about "foo"
+ None,
+ ],
+ )
+ .with_contained(
+ "s1",
+ [ScalarValue::from("bar")],
+ [
+ // containers 0,1,2 known to only contain "bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 known to not contain "bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 unknown about "bar"
+ None,
+ None,
+ None,
+ ],
+ )
+ .with_contained(
+ // the way the tests are setup, this data is
+ // consulted if the "foo" and "bar" are being checked at the
same time
+ "s1",
+ [ScalarValue::from("foo"), ScalarValue::from("bar")],
+ [
+ // container 0,1,2 unknown about ("foo, "bar")
+ None,
+ None,
+ None,
+ // container 3,4,5 known to contain only either "foo" and
"bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 6,7,8 known ro contain neither "foo" and
"bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ ],
+ );
+
+ // s1 = 'foo'
+ prune_with_expr(
+ col("s1").eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers ('false) where we know foo is not present
+ vec![true, false, true, true, false, true, true, false, true],
Review Comment:
Thanks for the comment
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -2484,10 +2630,466 @@ mod tests {
// TODO: add other negative test for other case and op
}
+ #[test]
+ fn prune_with_contained_one_column() {
+ let schema = Arc::new(Schema::new(vec![Field::new("s1",
DataType::Utf8, true)]));
+
+ // Model having information like a bloom filter for s1
+ let statistics = TestStatistics::new()
+ .with_contained(
+ "s1",
+ [ScalarValue::from("foo")],
+ [
+ // container 0 known to only contain "foo"",
+ Some(true),
+ // container 1 known to not contain "foo"
+ Some(false),
+ // container 2 unknown about "foo"
+ None,
+ // container 3 known to only contain "foo"
+ Some(true),
+ // container 4 known to not contain "foo"
+ Some(false),
+ // container 5 unknown about "foo"
+ None,
+ // container 6 known to only contain "foo"
+ Some(true),
+ // container 7 known to not contain "foo"
+ Some(false),
+ // container 8 unknown about "foo"
+ None,
+ ],
+ )
+ .with_contained(
+ "s1",
+ [ScalarValue::from("bar")],
+ [
+ // containers 0,1,2 known to only contain "bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 known to not contain "bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 unknown about "bar"
+ None,
+ None,
+ None,
+ ],
+ )
+ .with_contained(
+ // the way the tests are setup, this data is
+ // consulted if the "foo" and "bar" are being checked at the
same time
+ "s1",
+ [ScalarValue::from("foo"), ScalarValue::from("bar")],
+ [
+ // container 0,1,2 unknown about ("foo, "bar")
+ None,
+ None,
+ None,
+ // container 3,4,5 known to contain only either "foo" and
"bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 6,7,8 known ro contain neither "foo" and
"bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ ],
+ );
+
+ // s1 = 'foo'
+ prune_with_expr(
+ col("s1").eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers ('false) where we know foo is not present
+ vec![true, false, true, true, false, true, true, false, true],
+ );
+
+ // s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("bar")),
+ &schema,
+ &statistics,
+ // rule out containers where we know bar is not present
+ vec![true, true, true, false, false, false, true, true, true],
+ );
+
+ // s1 = 'baz' (unknown value)
+ prune_with_expr(
+ col("s1").eq(lit("baz")),
+ &schema,
+ &statistics,
+ // can't rule out anything
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' AND s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).and(col("s1").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // logically this predicate can't possibly be true (the column
can't
+ // take on both values) but we could rule it out if the stats tell
+ // us that both values are not present
+ vec![true, true, true, true, true, true, true, true, true],
Review Comment:
> but we could rule it out if the stats tell
> // us that both values are not present
Is it possible to have a test container `false` to say `both values are not
present`?
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -276,21 +383,21 @@ fn is_always_true(expr: &Arc<dyn PhysicalExpr>) -> bool {
/// Handles creating references to the min/max statistics
/// for columns as well as recording which statistics are needed
#[derive(Debug, Default, Clone)]
-pub(crate) struct RequiredStatColumns {
+pub(crate) struct RequiredColumns {
Review Comment:
Yeah, when I worked on statistics where I only needed min and max, I did not
see the need to to use the available struct that include a lot more info
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -2484,10 +2630,466 @@ mod tests {
// TODO: add other negative test for other case and op
}
+ #[test]
+ fn prune_with_contained_one_column() {
+ let schema = Arc::new(Schema::new(vec![Field::new("s1",
DataType::Utf8, true)]));
+
+ // Model having information like a bloom filter for s1
+ let statistics = TestStatistics::new()
+ .with_contained(
+ "s1",
+ [ScalarValue::from("foo")],
+ [
+ // container 0 known to only contain "foo"",
+ Some(true),
+ // container 1 known to not contain "foo"
+ Some(false),
+ // container 2 unknown about "foo"
+ None,
+ // container 3 known to only contain "foo"
+ Some(true),
+ // container 4 known to not contain "foo"
+ Some(false),
+ // container 5 unknown about "foo"
+ None,
+ // container 6 known to only contain "foo"
+ Some(true),
+ // container 7 known to not contain "foo"
+ Some(false),
+ // container 8 unknown about "foo"
+ None,
+ ],
+ )
+ .with_contained(
+ "s1",
+ [ScalarValue::from("bar")],
+ [
+ // containers 0,1,2 known to only contain "bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 known to not contain "bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 unknown about "bar"
+ None,
+ None,
+ None,
+ ],
+ )
+ .with_contained(
+ // the way the tests are setup, this data is
+ // consulted if the "foo" and "bar" are being checked at the
same time
+ "s1",
+ [ScalarValue::from("foo"), ScalarValue::from("bar")],
+ [
+ // container 0,1,2 unknown about ("foo, "bar")
+ None,
+ None,
+ None,
+ // container 3,4,5 known to contain only either "foo" and
"bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 6,7,8 known ro contain neither "foo" and
"bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ ],
+ );
+
+ // s1 = 'foo'
+ prune_with_expr(
+ col("s1").eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers ('false) where we know foo is not present
+ vec![true, false, true, true, false, true, true, false, true],
+ );
+
+ // s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("bar")),
+ &schema,
+ &statistics,
+ // rule out containers where we know bar is not present
+ vec![true, true, true, false, false, false, true, true, true],
+ );
+
+ // s1 = 'baz' (unknown value)
+ prune_with_expr(
+ col("s1").eq(lit("baz")),
+ &schema,
+ &statistics,
+ // can't rule out anything
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' AND s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).and(col("s1").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // logically this predicate can't possibly be true (the column
can't
+ // take on both values) but we could rule it out if the stats tell
+ // us that both values are not present
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' OR s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).or(col("s1").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can rule out containers that we know contain neither foo nor bar
+ vec![true, true, true, true, true, true, false, false, false],
+ );
+
+ // s1 = 'foo' OR s1 = 'baz'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).or(col("s1").eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // can't rule out anything container
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' OR s1 = 'bar' OR s1 = 'baz'
+ prune_with_expr(
+ col("s1")
+ .eq(lit("foo"))
+ .or(col("s1").eq(lit("bar")))
+ .or(col("s1").eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // can rule out any containers based on knowledge of s1 and `foo`,
+ // `bar` and (`foo`, `bar`)
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 != foo
+ prune_with_expr(
+ col("s1").not_eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers we know for sure only contain foo
+ vec![false, true, true, false, true, true, false, true, true],
+ );
+
+ // s1 != bar
+ prune_with_expr(
+ col("s1").not_eq(lit("bar")),
+ &schema,
+ &statistics,
+ // rule out when we know for sure s1 has the value bar
+ vec![false, false, false, true, true, true, true, true, true],
+ );
+
+ // s1 != foo AND s1 != bar
Review Comment:
I start getting confused. What is the difference between this and ` !(s1 =
'foo' OR s1 = 'bar')`. Their results are not opposite of each other. I guess
some inference here that I cannot figure out yet
##########
datafusion/core/src/physical_optimizer/pruning.rs:
##########
@@ -2484,10 +2630,466 @@ mod tests {
// TODO: add other negative test for other case and op
}
+ #[test]
+ fn prune_with_contained_one_column() {
+ let schema = Arc::new(Schema::new(vec![Field::new("s1",
DataType::Utf8, true)]));
+
+ // Model having information like a bloom filter for s1
+ let statistics = TestStatistics::new()
+ .with_contained(
+ "s1",
+ [ScalarValue::from("foo")],
+ [
+ // container 0 known to only contain "foo"",
+ Some(true),
+ // container 1 known to not contain "foo"
+ Some(false),
+ // container 2 unknown about "foo"
+ None,
+ // container 3 known to only contain "foo"
+ Some(true),
+ // container 4 known to not contain "foo"
+ Some(false),
+ // container 5 unknown about "foo"
+ None,
+ // container 6 known to only contain "foo"
+ Some(true),
+ // container 7 known to not contain "foo"
+ Some(false),
+ // container 8 unknown about "foo"
+ None,
+ ],
+ )
+ .with_contained(
+ "s1",
+ [ScalarValue::from("bar")],
+ [
+ // containers 0,1,2 known to only contain "bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 known to not contain "bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 unknown about "bar"
+ None,
+ None,
+ None,
+ ],
+ )
+ .with_contained(
+ // the way the tests are setup, this data is
+ // consulted if the "foo" and "bar" are being checked at the
same time
+ "s1",
+ [ScalarValue::from("foo"), ScalarValue::from("bar")],
+ [
+ // container 0,1,2 unknown about ("foo, "bar")
+ None,
+ None,
+ None,
+ // container 3,4,5 known to contain only either "foo" and
"bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 6,7,8 known ro contain neither "foo" and
"bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ ],
+ );
+
+ // s1 = 'foo'
+ prune_with_expr(
+ col("s1").eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers ('false) where we know foo is not present
+ vec![true, false, true, true, false, true, true, false, true],
+ );
+
+ // s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("bar")),
+ &schema,
+ &statistics,
+ // rule out containers where we know bar is not present
+ vec![true, true, true, false, false, false, true, true, true],
+ );
+
+ // s1 = 'baz' (unknown value)
+ prune_with_expr(
+ col("s1").eq(lit("baz")),
+ &schema,
+ &statistics,
+ // can't rule out anything
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' AND s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).and(col("s1").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // logically this predicate can't possibly be true (the column
can't
+ // take on both values) but we could rule it out if the stats tell
+ // us that both values are not present
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' OR s1 = 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).or(col("s1").eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can rule out containers that we know contain neither foo nor bar
+ vec![true, true, true, true, true, true, false, false, false],
+ );
+
+ // s1 = 'foo' OR s1 = 'baz'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).or(col("s1").eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // can't rule out anything container
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' OR s1 = 'bar' OR s1 = 'baz'
+ prune_with_expr(
+ col("s1")
+ .eq(lit("foo"))
+ .or(col("s1").eq(lit("bar")))
+ .or(col("s1").eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // can rule out any containers based on knowledge of s1 and `foo`,
+ // `bar` and (`foo`, `bar`)
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 != foo
+ prune_with_expr(
+ col("s1").not_eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers we know for sure only contain foo
+ vec![false, true, true, false, true, true, false, true, true],
+ );
+
+ // s1 != bar
+ prune_with_expr(
+ col("s1").not_eq(lit("bar")),
+ &schema,
+ &statistics,
+ // rule out when we know for sure s1 has the value bar
+ vec![false, false, false, true, true, true, true, true, true],
+ );
+
+ // s1 != foo AND s1 != bar
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .and(col("s1").not_eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can rule out any container where we know s1 does not have
either 'foo' or 'bar'
+ vec![true, true, true, false, false, false, true, true, true],
+ );
+
+ // s1 != foo AND s1 != bar AND s1 != baz
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .and(col("s1").not_eq(lit("bar")))
+ .and(col("s1").not_eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // can't rule out any container based on knowledge of s1,s2
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 != foo OR s1 != bar
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .or(col("s1").not_eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // cant' rule out anything based on contains information
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 != foo OR s1 != bar OR s1 != baz
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .or(col("s1").not_eq(lit("bar")))
+ .or(col("s1").not_eq(lit("baz"))),
+ &schema,
+ &statistics,
+ // cant' rule out anything based on contains information
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+ }
+
+ #[test]
+ fn prune_with_contained_two_columns() {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("s1", DataType::Utf8, true),
+ Field::new("s2", DataType::Utf8, true),
+ ]));
+
+ // Model having information like bloom filters for s1 and s2
+ let statistics = TestStatistics::new()
+ .with_contained(
+ "s1",
+ [ScalarValue::from("foo")],
+ [
+ // container 0, s1 known to only contain "foo"",
+ Some(true),
+ // container 1, s1 known to not contain "foo"
+ Some(false),
+ // container 2, s1 unknown about "foo"
+ None,
+ // container 3, s1 known to only contain "foo"
+ Some(true),
+ // container 4, s1 known to not contain "foo"
+ Some(false),
+ // container 5, s1 unknown about "foo"
+ None,
+ // container 6, s1 known to only contain "foo"
+ Some(true),
+ // container 7, s1 known to not contain "foo"
+ Some(false),
+ // container 8, s1 unknown about "foo"
+ None,
+ ],
+ )
+ .with_contained(
+ "s2", // for column s2
+ [ScalarValue::from("bar")],
+ [
+ // containers 0,1,2 s2 known to only contain "bar"
+ Some(true),
+ Some(true),
+ Some(true),
+ // container 3,4,5 s2 known to not contain "bar"
+ Some(false),
+ Some(false),
+ Some(false),
+ // container 6,7,8 s2 unknown about "bar"
+ None,
+ None,
+ None,
+ ],
+ );
+
+ // s1 = 'foo'
+ prune_with_expr(
+ col("s1").eq(lit("foo")),
+ &schema,
+ &statistics,
+ // rule out containers where we know s1 is not present
+ vec![true, false, true, true, false, true, true, false, true],
+ );
+
+ // s1 = 'foo' OR s2 = 'bar'
+ let expr = col("s1").eq(lit("foo")).or(col("s2").eq(lit("bar")));
+ prune_with_expr(
+ expr,
+ &schema,
+ &statistics,
+ // can't rule out any container (would need to prove that s1 !=
foo AND s2 != bar)
+ vec![true, true, true, true, true, true, true, true, true],
+ );
+
+ // s1 = 'foo' AND s2 != 'bar'
+ prune_with_expr(
+ col("s1").eq(lit("foo")).and(col("s2").not_eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // can only rule out container where we know either:
+ // 1. s1 doesn't have the value 'foo` or
+ // 2. s2 has only the value of 'bar'
+ vec![false, false, false, true, false, true, true, false, true],
+ );
+
+ // s1 != 'foo' AND s2 != 'bar'
+ prune_with_expr(
+ col("s1")
+ .not_eq(lit("foo"))
+ .and(col("s2").not_eq(lit("bar"))),
+ &schema,
+ &statistics,
+ // Can rule out any container where we know either
+ // 1. s1 has only the value 'foo'
+ // 2. s2 has only the value 'bar'
+ vec![false, false, false, false, true, true, false, true, true],
+ );
+
+ // s1 != 'foo' AND (s2 = 'bar' OR s2 = 'baz')
+ prune_with_expr(
+ col("s1").not_eq(lit("foo")).and(
+ col("s2")
+ .not_eq(lit("bar"))
+ .or(col("s2").not_eq(lit("baz"))),
Review Comment:
```suggestion
.eq(lit("bar"))
.or(col("s2").eq(lit("baz"))),
```
It does not change the meaning of the test though
--
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]
