@@ -35,6 +35,7 @@ use crate::filter_pushdown::{
3535 ChildFilterDescription , ChildPushdownResult , FilterDescription , FilterPushdownPhase ,
3636 FilterPushdownPropagation , PushedDown ,
3737} ;
38+ use crate :: joins:: utils:: max_distinct_count;
3839use crate :: limit:: LocalLimitExec ;
3940use crate :: metrics:: { MetricBuilder , MetricType } ;
4041use crate :: projection:: {
@@ -63,13 +64,13 @@ use datafusion_execution::TaskContext;
6364use datafusion_expr:: Operator ;
6465use datafusion_physical_expr:: equivalence:: ProjectionMapping ;
6566use datafusion_physical_expr:: expressions:: {
66- BinaryExpr , Column , IsNotNullExpr , Literal , lit,
67+ BinaryExpr , Column , InListExpr , IsNotNullExpr , Literal , lit,
6768} ;
6869use datafusion_physical_expr:: intervals:: utils:: check_support;
6970use datafusion_physical_expr:: utils:: { collect_columns, reassign_expr_columns} ;
7071use datafusion_physical_expr:: {
7172 AcrossPartitions , AnalysisContext , ConstExpr , ExprBoundaries , PhysicalExpr , analyze,
72- conjunction, split_conjunction,
73+ conjunction, conjunction_opt , split_conjunction,
7374} ;
7475
7576use datafusion_physical_expr_common:: physical_expr:: fmt_sql;
@@ -359,29 +360,84 @@ impl FilterExec {
359360 } else {
360361 let null_rejecting_columns = collect_null_rejecting_columns ( predicate) ;
361362
362- if check_support ( predicate, schema) {
363+ // Estimate the predicate one top-level conjunct at a time. Interval
364+ // analysis rejects a whole predicate if any part of it is out of
365+ // reach, and an `IN` list is out of reach because the planner expands
366+ // it into a chain of `OR`s. Splitting first means a query like
367+ // `d_dom between 1 and 2 AND d_year IN (1999, 2000, 2001)` no longer
368+ // falls back to the default selectivity for all of it: TPC-DS
369+ // estimates that at 20% of `date_dim`, or 14,610 rows, where 72
370+ // survive.
371+ let ( supported, rest) : ( Vec < _ > , Vec < _ > ) = split_conjunction ( predicate)
372+ . into_iter ( )
373+ . partition ( |conjunct| check_support ( conjunct, schema) ) ;
374+ let split_anything = !rest. is_empty ( ) ;
375+
376+ // Selectivity of the conjuncts interval analysis cannot see. An
377+ // unrecognized one still contributes the default, once, as the whole
378+ // predicate used to.
379+ let mut unanalyzed_selectivity = 1.0 ;
380+ let mut has_unknown_conjunct = false ;
381+ for conjunct in rest {
382+ match in_list_selectivity (
383+ conjunct,
384+ & input_stats. column_statistics ,
385+ & input_num_rows,
386+ ) {
387+ Some ( selectivity) => unanalyzed_selectivity *= selectivity,
388+ None => has_unknown_conjunct = true ,
389+ }
390+ }
391+ if has_unknown_conjunct {
392+ unanalyzed_selectivity *= default_selectivity as f64 / 100.0 ;
393+ }
394+
395+ // Rebuilding the conjunction re-associates it, and interval
396+ // propagation is sensitive to the shape of the tree it walks, so the
397+ // predicate is passed through untouched unless something was actually
398+ // split off it. It must never be passed through when something was:
399+ // interval analysis rejects the parts that were split off, and asking
400+ // it to walk them anyway is an error rather than a fallback.
401+ let analyzable = if split_anything {
402+ conjunction_opt ( supported. into_iter ( ) . cloned ( ) )
403+ } else {
404+ Some ( Arc :: clone ( predicate) )
405+ } ;
406+ if let Some ( analyzable) = analyzable {
363407 let input_analysis_ctx = AnalysisContext :: try_from_statistics (
364408 schema,
365409 & input_stats. column_statistics ,
366410 ) ?;
367- let analysis_ctx = analyze ( predicate, input_analysis_ctx, schema) ?;
368- let selectivity = analysis_ctx. selectivity . unwrap_or ( 1.0 ) ;
411+ let analysis_ctx = analyze ( & analyzable, input_analysis_ctx, schema) ?;
412+ let selectivity =
413+ analysis_ctx. selectivity . unwrap_or ( 1.0 ) * unanalyzed_selectivity;
369414 let filtered_num_rows =
370415 input_num_rows. with_estimated_selectivity ( selectivity) ;
371- let cs = collect_new_statistics (
416+ let mut cs = collect_new_statistics (
372417 schema,
373418 & input_stats. column_statistics ,
374419 analysis_ctx. boundaries ,
375420 selectivity,
376421 & null_rejecting_columns,
377422 filtered_num_rows,
378423 ) ;
424+ // A column pinned by an equality that was split off has one
425+ // distinct value left, which interval analysis of the remaining
426+ // conjuncts cannot know.
427+ for idx in & eq_columns {
428+ if let Some ( col_stat) = cs. get_mut ( * idx)
429+ && col_stat. distinct_count != Precision :: Exact ( 1 )
430+ {
431+ col_stat. distinct_count =
432+ distinct_count_for_singleton_domain ( filtered_num_rows) ;
433+ }
434+ }
379435 ( selectivity, filtered_num_rows, cs)
380436 } else {
381- // Without interval boundaries, use the default selectivity and
382- // apply the row-count constraints that still follow from the
383- // filter predicate.
384- let selectivity = default_selectivity as f64 / 100.0 ;
437+ // Nothing to derive boundaries from, so keep the input's value
438+ // statistics and apply only the row-count constraints that still
439+ // follow from the filter predicate.
440+ let selectivity = unanalyzed_selectivity ;
385441 let filtered_num_rows =
386442 input_num_rows. with_estimated_selectivity ( selectivity) ;
387443 let mut cs = input_stats. to_inexact ( ) . column_statistics ;
@@ -959,6 +1015,91 @@ impl EmbeddedProjection for FilterExec {
9591015///
9601016/// Only AND conjunctions are traversed; OR is intentionally skipped
9611017/// since `a = 1 OR a = 2` does not pin NDV to 1.
1018+ /// Estimates the selectivity of `col IN (a, b, c)`, including the chain of
1019+ /// `OR`ed equalities the planner expands a short list into.
1020+ ///
1021+ /// Interval arithmetic cannot narrow a column from a disjunction, so without this
1022+ /// such a conjunct would contribute nothing but the default selectivity. Here the
1023+ /// fraction of values the list selects is `distinct literals / distinct values`,
1024+ /// the same reasoning `col = literal` gets from `1 / NDV`.
1025+ ///
1026+ /// Returns `None` when the conjunct is not a list of literals over one column.
1027+ fn in_list_selectivity (
1028+ conjunct : & Arc < dyn PhysicalExpr > ,
1029+ column_statistics : & [ ColumnStatistics ] ,
1030+ num_rows : & Precision < usize > ,
1031+ ) -> Option < f64 > {
1032+ let mut column = None ;
1033+ let mut values = HashSet :: new ( ) ;
1034+ if let Some ( in_list) = conjunct. downcast_ref :: < InListExpr > ( ) {
1035+ if in_list. negated ( ) {
1036+ // `NOT IN` selects the complement, which is usually most of the
1037+ // column, and is left to the default rather than guessed at.
1038+ return None ;
1039+ }
1040+ column = Some ( in_list. expr ( ) . downcast_ref :: < Column > ( ) ?) ;
1041+ for value in in_list. list ( ) {
1042+ values. insert ( value. downcast_ref :: < Literal > ( ) ?. value ( ) . clone ( ) ) ;
1043+ }
1044+ } else {
1045+ // Only a disjunction, so that a plain `col = literal` keeps whatever
1046+ // estimate it gets today rather than being re-derived here.
1047+ let binary = conjunct. downcast_ref :: < BinaryExpr > ( ) ?;
1048+ if * binary. op ( ) != Operator :: Or {
1049+ return None ;
1050+ }
1051+ collect_or_equalities ( conjunct, & mut column, & mut values) ?;
1052+ }
1053+
1054+ let column = column?;
1055+ if values. len ( ) < 2 {
1056+ return None ;
1057+ }
1058+ let stats = column_statistics. get ( column. index ( ) ) ?;
1059+ let distinct = * max_distinct_count ( num_rows, stats) . get_value ( ) ?;
1060+ if distinct == 0 {
1061+ return None ;
1062+ }
1063+ Some ( ( values. len ( ) as f64 / distinct as f64 ) . min ( 1.0 ) )
1064+ }
1065+
1066+ /// Collects the literals of an `OR` chain of equalities over a single column.
1067+ ///
1068+ /// Returns `None` as soon as the expression is anything else, so a mixed
1069+ /// disjunction such as `a = 1 OR b = 2` is not mistaken for a list.
1070+ fn collect_or_equalities < ' a > (
1071+ expr : & ' a Arc < dyn PhysicalExpr > ,
1072+ column : & mut Option < & ' a Column > ,
1073+ values : & mut HashSet < ScalarValue > ,
1074+ ) -> Option < ( ) > {
1075+ let binary = expr. downcast_ref :: < BinaryExpr > ( ) ?;
1076+ match binary. op ( ) {
1077+ Operator :: Or => {
1078+ collect_or_equalities ( binary. left ( ) , column, values) ?;
1079+ collect_or_equalities ( binary. right ( ) , column, values)
1080+ }
1081+ Operator :: Eq => {
1082+ let ( found, literal) = match (
1083+ binary. left ( ) . downcast_ref :: < Column > ( ) ,
1084+ binary. right ( ) . downcast_ref :: < Column > ( ) ,
1085+ ) {
1086+ ( Some ( col) , None ) => ( col, binary. right ( ) ) ,
1087+ ( None , Some ( col) ) => ( col, binary. left ( ) ) ,
1088+ _ => return None ,
1089+ } ;
1090+ // Every equality has to constrain the same column, or the fraction
1091+ // below would not describe the conjunct.
1092+ if column. is_some_and ( |current| current != found) {
1093+ return None ;
1094+ }
1095+ * column = Some ( found) ;
1096+ values. insert ( literal. downcast_ref :: < Literal > ( ) ?. value ( ) . clone ( ) ) ;
1097+ Some ( ( ) )
1098+ }
1099+ _ => None ,
1100+ }
1101+ }
1102+
9621103fn collect_equality_columns ( predicate : & Arc < dyn PhysicalExpr > ) -> ( HashSet < usize > , bool ) {
9631104 let mut eq_values: HashMap < usize , ScalarValue > = HashMap :: new ( ) ;
9641105 let mut infeasible = false ;
@@ -2747,9 +2888,10 @@ mod tests {
27472888 Arc :: new( Literal :: new( ScalarValue :: Utf8 ( Some ( "b" . to_string( ) ) ) ) ) ,
27482889 ) ) ,
27492890 ) ) ,
2750- // Input NDV is 50, but the 20% default selectivity on 100 rows
2751- // estimates 20 output rows, so NDV is capped at 20.
2752- vec![ Precision :: Inexact ( 20 ) ] ,
2891+ // The two listed values are 2 of the column's 50, so 4 of the
2892+ // 100 input rows are expected and NDV is capped at 4. Still not
2893+ // collapsed to 1, which is what this case guards.
2894+ vec![ Precision :: Inexact ( 4 ) ] ,
27532895 ) ,
27542896 (
27552897 "AND with mixed types (Utf8 + Int32)" ,
0 commit comments