asolimando commented on code in PR #25719:
URL: https://github.com/apache/datafusion/pull/25719#discussion_r4183080870
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -4465,4 +4538,212 @@ mod tests {
);
Ok(())
}
+
+ // ---------------------------------------------------------------
+ // Unit tests for compute_fallback_selectivity
+ // ---------------------------------------------------------------
+
+ #[test]
+ fn test_fallback_selectivity_single_handled_equality() {
+ // col_0 = <expr>, NDV(col_0) = 100 → selectivity = 1/100
+ let schema = Schema::new(vec![Field::new("a", DataType::Int32,
false)]);
+ let predicate: Arc<dyn PhysicalExpr> = binary(
+ col("a", &schema).unwrap(),
+ Operator::Eq,
+ lit(42i32),
+ &schema,
+ )
+ .unwrap();
+ let col_stats = vec![ColumnStatistics {
+ distinct_count: Precision::Inexact(100),
+ ..Default::default()
+ }];
+ let result = compute_fallback_selectivity(&predicate, &col_stats, 20);
+ assert!(
+ (result - 0.01).abs() < 1e-12,
+ "expected 1/100 = 0.01, got {result}"
+ );
+ }
+
+ #[test]
+ fn test_fallback_selectivity_multiple_unhandled_conjuncts() {
+ // s LIKE '%abc' AND t <> 'x' AND u IN ('p','q')
+ // None are handled equalities → selectivity = default once = 0.2
+ let schema = Schema::new(vec![
+ Field::new("s", DataType::Utf8, false),
+ Field::new("t", DataType::Utf8, false),
+ Field::new("u", DataType::Utf8, false),
+ ]);
+ // Simulate three non-equality conjuncts via NotEq operators
+ let pred1 = binary(
+ col("s", &schema).unwrap(),
+ Operator::NotEq,
+ lit("abc"),
+ &schema,
+ )
+ .unwrap();
+ let pred2 = binary(
+ col("t", &schema).unwrap(),
+ Operator::NotEq,
+ lit("x"),
+ &schema,
+ )
+ .unwrap();
+ let pred3 = binary(
+ col("u", &schema).unwrap(),
+ Operator::NotEq,
+ lit("p"),
+ &schema,
+ )
+ .unwrap();
+ let combined: Arc<dyn PhysicalExpr> = conjunction(vec![pred1, pred2,
pred3]);
+ let col_stats = vec![
+ ColumnStatistics::new_unknown(),
+ ColumnStatistics::new_unknown(),
+ ColumnStatistics::new_unknown(),
+ ];
+ let result = compute_fallback_selectivity(&combined, &col_stats, 20);
+ // default_selectivity applied exactly once: 0.2
+ assert!((result - 0.2).abs() < 1e-12, "expected 0.2, got {result}");
+ }
+
+ #[test]
+ fn test_fallback_selectivity_mixed_handled_and_unhandled() {
+ // col_a = 42 AND col_b <> 'x'
+ // col_a has NDV=50, col_b is unhandled
+ // selectivity = (1/50) * 0.2 = 0.004
+ let schema = Schema::new(vec![
+ Field::new("a", DataType::Int32, false),
+ Field::new("b", DataType::Utf8, false),
+ ]);
+ let eq_pred = binary(
+ col("a", &schema).unwrap(),
+ Operator::Eq,
+ lit(42i32),
+ &schema,
+ )
+ .unwrap();
+ let neq_pred = binary(
+ col("b", &schema).unwrap(),
+ Operator::NotEq,
+ lit("x"),
+ &schema,
+ )
+ .unwrap();
+ let combined: Arc<dyn PhysicalExpr> = conjunction(vec![eq_pred,
neq_pred]);
+ let col_stats = vec![
+ ColumnStatistics {
+ distinct_count: Precision::Inexact(50),
+ ..Default::default()
+ },
+ ColumnStatistics::new_unknown(),
+ ];
+ let result = compute_fallback_selectivity(&combined, &col_stats, 20);
+ let expected = (1.0 / 50.0) * 0.2;
+ assert!(
+ (result - expected).abs() < 1e-12,
+ "expected {expected}, got {result}"
+ );
+ }
+
+ #[test]
+ fn test_fallback_selectivity_col_eq_col_uses_max_ndv() {
+ // col_a = col_b, NDV(a)=100, NDV(b)=200
+ // selectivity = 1 / max(100, 200) = 1/200
+ let schema = Schema::new(vec![
+ Field::new("a", DataType::Int32, false),
+ Field::new("b", DataType::Int32, false),
+ ]);
+ let predicate: Arc<dyn PhysicalExpr> = binary(
+ col("a", &schema).unwrap(),
+ Operator::Eq,
+ col("b", &schema).unwrap(),
+ &schema,
+ )
+ .unwrap();
+ let col_stats = vec![
+ ColumnStatistics {
+ distinct_count: Precision::Inexact(100),
+ ..Default::default()
+ },
+ ColumnStatistics {
+ distinct_count: Precision::Inexact(200),
+ ..Default::default()
+ },
+ ];
+ let result = compute_fallback_selectivity(&predicate, &col_stats, 20);
+ assert!(
+ (result - 1.0 / 200.0).abs() < 1e-12,
+ "expected 1/200 = 0.005, got {result}"
+ );
+ }
+
+ #[test]
+ fn test_fallback_selectivity_no_conjuncts_returns_default() {
+ // A single non-equality predicate → default_selectivity once
+ let schema = Schema::new(vec![Field::new("a", DataType::Int32,
false)]);
+ let predicate: Arc<dyn PhysicalExpr> = binary(
+ col("a", &schema).unwrap(),
+ Operator::Gt,
+ lit(10i32),
+ &schema,
+ )
+ .unwrap();
+ let col_stats = vec![ColumnStatistics {
+ distinct_count: Precision::Inexact(100),
+ ..Default::default()
+ }];
+ let result = compute_fallback_selectivity(&predicate, &col_stats, 20);
+ assert!((result - 0.2).abs() < 1e-12, "expected 0.2, got {result}");
+ }
+
+ #[test]
+ fn test_fallback_selectivity_cast_col_not_handled() {
Review Comment:
In a real plan, `CAST(a AS Int64) = 42` passes `check_support` (`CastExpr`
and `Int64` literals are supported), so the fallback never runs for this
predicate. The same is true for `a = 42` and `a > 10` in the other tests.
Testing the function directly is fine, but please also add a test for the
case this PR fixes: a `FilterExec` over a `StatisticsExec` with a known NDV,
and the predicate `a = <ScalarSubqueryExpr>`, with an assertion on `num_rows`,
as in `test_filter_statistics_basic_expr`.
A second test with `CAST(a) = <ScalarSubqueryExpr>` would show the case that
is still not handled.
##########
datafusion/sqllogictest/test_files/subquery.slt:
##########
@@ -3187,3 +3187,35 @@ DROP TABLE oj_a;
statement ok
DROP TABLE oj_b;
+
+#############
+## Scalar subquery equality: NDV-based row estimate
+## When a filter contains `col = (SELECT ...)`, the interval solver
+## cannot resolve the subquery, but the fallback heuristic uses
+## `1 / NDV(col)` instead of the flat 20% default.
+#############
+
+statement ok
+CREATE TABLE ndv_main AS
+ SELECT column1 AS id, column2 AS val
+ FROM (VALUES (1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e'),
+ (6, 'f'), (7, 'g'), (8, 'h'), (9, 'i'), (10, 'j'));
+
+statement ok
+CREATE TABLE ndv_lookup AS SELECT 5 AS v;
+
+# The filter `id = (SELECT v FROM ndv_lookup)` should use the NDV of `id`
+# (10 distinct values) to estimate ~1 row instead of the 20% default (~2 rows).
+query TT
+EXPLAIN SELECT * FROM ndv_main WHERE id = (SELECT v FROM ndv_lookup);
+----
+logical_plan
+<slt:ignore>
Review Comment:
With `<slt:ignore>` for both plans and without
`datafusion.explain.show_statistics`, this test checks no row estimate, so it
would also pass on `main`. The table made from `VALUES` probably has no NDV
either, so the filter would use 20% anyway.
It is difficult to get a column NDV in an SLT. I suggest you remove this
test and add a `FilterExec` statistics test in `filter.rs` instead (see
https://github.com/apache/datafusion/pull/25719/changes#r4183080870).
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -4465,4 +4538,212 @@ mod tests {
);
Ok(())
}
+
+ // ---------------------------------------------------------------
+ // Unit tests for compute_fallback_selectivity
+ // ---------------------------------------------------------------
+
+ #[test]
+ fn test_fallback_selectivity_single_handled_equality() {
+ // col_0 = <expr>, NDV(col_0) = 100 → selectivity = 1/100
+ let schema = Schema::new(vec![Field::new("a", DataType::Int32,
false)]);
+ let predicate: Arc<dyn PhysicalExpr> = binary(
+ col("a", &schema).unwrap(),
+ Operator::Eq,
+ lit(42i32),
+ &schema,
+ )
+ .unwrap();
+ let col_stats = vec![ColumnStatistics {
+ distinct_count: Precision::Inexact(100),
+ ..Default::default()
+ }];
+ let result = compute_fallback_selectivity(&predicate, &col_stats, 20);
+ assert!(
+ (result - 0.01).abs() < 1e-12,
+ "expected 1/100 = 0.01, got {result}"
+ );
+ }
+
+ #[test]
+ fn test_fallback_selectivity_multiple_unhandled_conjuncts() {
+ // s LIKE '%abc' AND t <> 'x' AND u IN ('p','q')
Review Comment:
nit: the comment says `LIKE` and `IN`, but the test uses three `<>`
predicates
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -4465,4 +4538,212 @@ mod tests {
);
Ok(())
}
+
+ // ---------------------------------------------------------------
+ // Unit tests for compute_fallback_selectivity
+ // ---------------------------------------------------------------
+
+ #[test]
+ fn test_fallback_selectivity_single_handled_equality() {
+ // col_0 = <expr>, NDV(col_0) = 100 → selectivity = 1/100
+ let schema = Schema::new(vec![Field::new("a", DataType::Int32,
false)]);
+ let predicate: Arc<dyn PhysicalExpr> = binary(
+ col("a", &schema).unwrap(),
+ Operator::Eq,
+ lit(42i32),
+ &schema,
+ )
+ .unwrap();
+ let col_stats = vec![ColumnStatistics {
+ distinct_count: Precision::Inexact(100),
+ ..Default::default()
+ }];
+ let result = compute_fallback_selectivity(&predicate, &col_stats, 20);
+ assert!(
+ (result - 0.01).abs() < 1e-12,
+ "expected 1/100 = 0.01, got {result}"
+ );
+ }
+
+ #[test]
+ fn test_fallback_selectivity_multiple_unhandled_conjuncts() {
+ // s LIKE '%abc' AND t <> 'x' AND u IN ('p','q')
+ // None are handled equalities → selectivity = default once = 0.2
+ let schema = Schema::new(vec![
+ Field::new("s", DataType::Utf8, false),
+ Field::new("t", DataType::Utf8, false),
+ Field::new("u", DataType::Utf8, false),
+ ]);
+ // Simulate three non-equality conjuncts via NotEq operators
+ let pred1 = binary(
+ col("s", &schema).unwrap(),
+ Operator::NotEq,
+ lit("abc"),
+ &schema,
+ )
+ .unwrap();
+ let pred2 = binary(
+ col("t", &schema).unwrap(),
+ Operator::NotEq,
+ lit("x"),
+ &schema,
+ )
+ .unwrap();
+ let pred3 = binary(
+ col("u", &schema).unwrap(),
+ Operator::NotEq,
+ lit("p"),
+ &schema,
+ )
+ .unwrap();
+ let combined: Arc<dyn PhysicalExpr> = conjunction(vec![pred1, pred2,
pred3]);
+ let col_stats = vec![
+ ColumnStatistics::new_unknown(),
+ ColumnStatistics::new_unknown(),
+ ColumnStatistics::new_unknown(),
+ ];
+ let result = compute_fallback_selectivity(&combined, &col_stats, 20);
+ // default_selectivity applied exactly once: 0.2
+ assert!((result - 0.2).abs() < 1e-12, "expected 0.2, got {result}");
+ }
+
+ #[test]
+ fn test_fallback_selectivity_mixed_handled_and_unhandled() {
+ // col_a = 42 AND col_b <> 'x'
+ // col_a has NDV=50, col_b is unhandled
+ // selectivity = (1/50) * 0.2 = 0.004
+ let schema = Schema::new(vec![
+ Field::new("a", DataType::Int32, false),
+ Field::new("b", DataType::Utf8, false),
+ ]);
+ let eq_pred = binary(
+ col("a", &schema).unwrap(),
+ Operator::Eq,
+ lit(42i32),
+ &schema,
+ )
+ .unwrap();
+ let neq_pred = binary(
+ col("b", &schema).unwrap(),
+ Operator::NotEq,
+ lit("x"),
+ &schema,
+ )
+ .unwrap();
+ let combined: Arc<dyn PhysicalExpr> = conjunction(vec![eq_pred,
neq_pred]);
+ let col_stats = vec![
+ ColumnStatistics {
+ distinct_count: Precision::Inexact(50),
+ ..Default::default()
+ },
+ ColumnStatistics::new_unknown(),
+ ];
+ let result = compute_fallback_selectivity(&combined, &col_stats, 20);
+ let expected = (1.0 / 50.0) * 0.2;
+ assert!(
+ (result - expected).abs() < 1e-12,
+ "expected {expected}, got {result}"
+ );
+ }
+
+ #[test]
+ fn test_fallback_selectivity_col_eq_col_uses_max_ndv() {
+ // col_a = col_b, NDV(a)=100, NDV(b)=200
+ // selectivity = 1 / max(100, 200) = 1/200
+ let schema = Schema::new(vec![
+ Field::new("a", DataType::Int32, false),
+ Field::new("b", DataType::Int32, false),
+ ]);
+ let predicate: Arc<dyn PhysicalExpr> = binary(
+ col("a", &schema).unwrap(),
+ Operator::Eq,
+ col("b", &schema).unwrap(),
+ &schema,
+ )
+ .unwrap();
+ let col_stats = vec![
+ ColumnStatistics {
+ distinct_count: Precision::Inexact(100),
+ ..Default::default()
+ },
+ ColumnStatistics {
+ distinct_count: Precision::Inexact(200),
+ ..Default::default()
+ },
+ ];
+ let result = compute_fallback_selectivity(&predicate, &col_stats, 20);
+ assert!(
+ (result - 1.0 / 200.0).abs() < 1e-12,
+ "expected 1/200 = 0.005, got {result}"
+ );
+ }
+
+ #[test]
+ fn test_fallback_selectivity_no_conjuncts_returns_default() {
Review Comment:
Nit: this test covers a single non-equality conjunct, a name such as
`..._non_equality_returns_default` would match it better IMO
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -1182,6 +1187,74 @@ fn holds_each_value_once(column: &ColumnStatistics,
num_rows: &Precision<usize>)
distinct.saturating_add(*nulls) >= *rows
}
+/// Heuristic selectivity for predicates that fail interval analysis.
+///
+/// Splits the predicate into AND conjuncts. For each equality (`col = expr`)
+/// where at least one side is a [`Column`] with a known NDV, the selectivity
+/// contribution is `1 / NDV`. When both sides are columns with known NDV,
+/// `1 / max(left_NDV, right_NDV)` is used. All remaining conjuncts that
+/// cannot be estimated are covered by a single application of
+/// `default_selectivity`, preserving the pre-existing estimate for predicates
+/// that contain no recognizable equality.
+fn compute_fallback_selectivity(
+ predicate: &Arc<dyn PhysicalExpr>,
+ column_statistics: &[ColumnStatistics],
+ default_selectivity: u8,
+) -> f64 {
+ let conjuncts = split_conjunction(predicate);
+ let mut selectivity = 1.0;
+ let mut has_unhandled = false;
+
+ for expr in conjuncts {
+ let mut handled = false;
+
+ if let Some(binary) = expr.downcast_ref::<BinaryExpr>()
+ && *binary.op() == Operator::Eq
+ {
+ let left_ndv = column_ndv(binary.left(), column_statistics);
+ let right_ndv = column_ndv(binary.right(), column_statistics);
+
+ let ndv = match (left_ndv, right_ndv) {
+ (Some(l), Some(r)) => Some(l.max(r)),
+ (Some(n), None) | (None, Some(n)) => Some(n),
+ (None, None) => None,
+ };
+
+ if let Some(n) = ndv {
+ selectivity *= 1.0 / (n as f64);
+ handled = true;
+ }
+ }
+
+ if !handled {
+ has_unhandled = true;
+ }
+ }
+
+ // Apply the default selectivity at most once for all unhandled conjuncts,
+ // so that a predicate with no handled equalities keeps the same estimate
+ // as the previous flat-fallback path.
Review Comment:
please describe the current behavior only, as any references to "the
previous" path becomes unclear after this PR merges
--
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]
