gabotechs commented on code in PR #27548:
URL: https://github.com/apache/datafusion/pull/27548#discussion_r4610524118
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -1501,6 +1542,95 @@ fn like_selectivity(
}
}
+/// Estimates `col [NOT] IN (literals)` as the share of the column's distinct
+/// values that the list names, within the non-null rows. Returns `None`, so
+/// that the default applies, for other lists and when the column has no
+/// usable statistics.
+///
+/// Like an equality, each distinct value is assumed to hold the same number of
+/// rows, and a listed value between the column's min and max is assumed to
+/// occur in the column.
+fn in_list_selectivity(in_list: &InListExpr, statistics: &Statistics) ->
Option<f64> {
+ if in_list.is_empty() {
Review Comment:
nit: is this early return needed? Without it, an empty list gives `listed =
0`, so `IN ()` comes out as 0 and `NOT IN ()` as 1, which are the exact answers
instead of the default. (The empty-list check in
`collect_null_rejecting_columns` is needed, though.)
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -1183,6 +1184,25 @@ fn restricted_column(expr: &Arc<dyn PhysicalExpr>) ->
Option<(usize, usize)> {
(!value.is_null()).then_some((column.index(), 1))
}
+/// The column a literal `IN` list tests, its distinct non-null values, and
+/// whether the list holds a NULL. The list must test a bare column and hold
+/// only literals.
+#[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue
has interior mutability but is intentionally used as hash key
+fn literal_in_list(in_list: &InListExpr) -> Option<(usize, Vec<&ScalarValue>,
bool)> {
+ let column = in_list.expr().downcast_ref::<Column>()?;
+ let mut values = HashSet::with_capacity(in_list.len());
+ let mut has_null = false;
+ for expr in in_list.list() {
+ let value = expr.downcast_ref::<Literal>()?.value();
+ if value.is_null() {
+ has_null = true;
+ } else {
+ values.insert(value);
+ }
+ }
+ Some((column.index(), values.into_iter().collect(), has_null))
Review Comment:
nit: both callers only count or iterate the values once, so copying the set
into a `Vec` isn't needed. Returning the `HashSet` (or the count plus an
iterator) would avoid the extra allocation.
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -4922,6 +5052,303 @@ mod tests {
}
}
+ /// Output statistics of `a [NOT] IN (list)` on a single column `a` of the
+ /// list's type.
+ fn in_list_filter_statistics(
+ num_rows: Precision<usize>,
+ column: ColumnStatistics,
+ list: &[ScalarValue],
+ negated: bool,
+ ) -> Result<Arc<Statistics>> {
+ use datafusion_physical_expr::expressions::in_list;
+
+ let schema = Schema::new(vec![Field::new("a", list[0].data_type(),
true)]);
+ let input = Arc::new(StatisticsExec::new(
+ Statistics {
+ num_rows,
+ total_byte_size: Precision::Absent,
+ column_statistics: vec![column],
+ },
+ schema.clone(),
+ ));
+ let list = list.iter().map(|value| lit(value.clone())).collect();
+ let predicate = in_list(col("a", &schema)?, list, &negated, &schema)?;
+ let filter = FilterExec::try_new(predicate, input)?;
+ StatisticsContext::new().compute(&filter, &StatisticsArgs::new())
+ }
+
+ fn int32_column(
+ min: i32,
+ max: i32,
+ null_count: Precision<usize>,
+ ) -> ColumnStatistics {
+ ColumnStatistics {
+ null_count,
+ min_value: Precision::Exact(ScalarValue::Int32(Some(min))),
+ max_value: Precision::Exact(ScalarValue::Int32(Some(max))),
+ ..Default::default()
+ }
+ }
+
+ fn int32_list(values: &[Option<i32>]) -> Vec<ScalarValue> {
+ values
+ .iter()
+ .map(|&value| ScalarValue::Int32(value))
+ .collect()
+ }
+
+ /// An `IN` list on an integer column without a distinct count counts the
+ /// values from min to max instead (#25621).
+ #[test]
+ fn test_filter_statistics_in_list_on_an_integer_range() -> Result<()> {
Review Comment:
The new tests overlap quite a bit, and `scale_to_non_null_rows` was moved
as-is, so its edge cases are already covered by
`test_filter_statistics_like_missing_or_zero_counts`. I think we could trim to
roughly half without losing coverage of any branch:
- Drop `sql_in_list_filter_selectivity` in `statistics.rs`. Each of its
cases is already a unit test here, and `parquet_statistics.slt` covers SQL
reaching `InListExpr` end to end.
- Merge this test into `..._values`. The full list making `NOT IN` 0 can be
one more row there.
- In `..._values`, drop the `(0, 11)` row since `(5, 50)` already covers
out-of-range values.
- In `..._null_and_row_counts`, keep the 200-nulls row, the
unknown-null-count row and the wider-than-rows cap, and drop the all-null,
zero-rows and unknown-rows rows.
- In `..._by_type_without_a_distinct_count`, keep `Date32` and one type that
keeps the default. The other four go through the same check.
- Optionally keep only one of the two SLT `EXPLAIN`s, since the
`pruning_predicate` lines break whenever pruning changes for unrelated reasons.
--
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]