asolimando commented on code in PR #25719:
URL: https://github.com/apache/datafusion/pull/25719#discussion_r4165294992
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -455,7 +460,56 @@ impl FilterExec {
column_statistics,
})
}
+}
+
+/// Fallback heuristic for when interval analysis is unsupported (e.g. scalar
subqueries).
+/// Iterates over conjunctions; uses `1.0 / NDV` for equalities involving a
column with known NDV,
+/// and applies `default_selectivity` for all other predicates.
+fn compute_fallback_selectivity(
+ predicate: &Arc<dyn PhysicalExpr>,
+ column_statistics: &[ColumnStatistics],
+ default_selectivity: u8,
+) -> f64 {
+ let exprs = split_conjunction(predicate);
+ let mut selectivity = 1.0;
+
+ for expr in exprs {
+ let mut handled = false;
+ if let Some(binary) = expr.downcast_ref::<BinaryExpr>() {
+ if binary.op() == &Operator::Eq {
+ let col = if let Some(c) =
binary.left().downcast_ref::<Column>() {
+ Some(c)
+ } else if let Some(c) =
binary.right().downcast_ref::<Column>() {
+ Some(c)
+ } else {
+ None
+ };
+
+ if let Some(c) = col {
+ if let Some(stat) = column_statistics.get(c.index()) {
+ match stat.distinct_count {
+ Precision::Exact(ndv) | Precision::Inexact(ndv)
+ if ndv > 0 =>
+ {
+ selectivity *= 1.0 / (ndv as f64);
+ handled = true;
+ }
+ _ => {}
+ }
+ }
+ }
+ }
+ }
+
+ if !handled {
+ selectivity *= default_selectivity as f64 / 100.0;
Review Comment:
This multiplies `default_selectivity` once for each conjunct that is not
handled. Today the whole predicate gets it once.
The fallback path runs when `check_support` fails for the whole predicate.
That happens for many common predicates: Utf8/Decimal columns, `<>`, `OR`,
`IN`, `LIKE`, function calls. For example, `s LIKE '%a%' AND t <> 'x' AND u IN
('p', 'q')` goes from 0.2 to 0.2^3 = 0.008, which is 25x lower, and it does not
contain a scalar subquery.
Suggestion: apply `default_selectivity` at most once for all conjuncts that
are not handled, and multiply it by `1/NDV` for each handled equality. That
way, a predicate with no handled equality keeps the estimate it has today.
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -414,10 +414,15 @@ impl FilterExec {
);
(selectivity, filtered_num_rows, cs)
} else {
- // Without interval boundaries, use the default selectivity and
- // apply the row-count constraints that still follow from the
- // filter predicate.
- let selectivity = default_selectivity as f64 / 100.0;
+ // Without interval boundaries, attempt a heuristic fallback
for selectivities.
+ // For instance, an equality filter against an unresolved
scalar subquery will
+ // fail `check_support`, but we can still estimate selectivity
as `1.0 / NDV`.
+ let selectivity = compute_fallback_selectivity(
Review Comment:
Note that `utf8_col = 'literal'` also fails `check_support`, so with this
change it gets `1/NDV` instead of 20%. It might be an improvement, but it
changes existing estimates for queries that are not about scalar subqueries.
Please mention it in the PR description and add tests around this.
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -455,7 +460,56 @@ impl FilterExec {
column_statistics,
})
}
+}
+
+/// Fallback heuristic for when interval analysis is unsupported (e.g. scalar
subqueries).
+/// Iterates over conjunctions; uses `1.0 / NDV` for equalities involving a
column with known NDV,
+/// and applies `default_selectivity` for all other predicates.
+fn compute_fallback_selectivity(
+ predicate: &Arc<dyn PhysicalExpr>,
+ column_statistics: &[ColumnStatistics],
+ default_selectivity: u8,
+) -> f64 {
+ let exprs = split_conjunction(predicate);
+ let mut selectivity = 1.0;
+
+ for expr in exprs {
+ let mut handled = false;
+ if let Some(binary) = expr.downcast_ref::<BinaryExpr>() {
+ if binary.op() == &Operator::Eq {
+ let col = if let Some(c) =
binary.left().downcast_ref::<Column>() {
Review Comment:
The left side is tried first, so for `col_a = col_b` the right column's NDV
is ignored. The estimate then depends on which side each column is written on.
Please use `1 / max(NDV(left), NDV(right))` when both sides have an NDV, and
the known side when only one side has one.
Also, `CAST(col) = (SELECT ...)` is not handled here, because the column
side is not a bare `Column`. Type coercion makes this case common for scalar
subqueries. It is fine to leave it for a follow-up, but please add a test that
shows the current behavior.
--
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]
