@@ -63,7 +63,7 @@ use datafusion_execution::TaskContext;
6363use datafusion_expr:: Operator ;
6464use datafusion_physical_expr:: equivalence:: ProjectionMapping ;
6565use datafusion_physical_expr:: expressions:: {
66- BinaryExpr , Column , IsNotNullExpr , Literal , lit,
66+ BinaryExpr , Column , InListExpr , IsNotNullExpr , Literal , lit,
6767} ;
6868use datafusion_physical_expr:: intervals:: utils:: check_support;
6969use datafusion_physical_expr:: utils:: { collect_columns, reassign_expr_columns} ;
@@ -343,6 +343,11 @@ impl FilterExec {
343343 let input_num_rows = input_stats. num_rows ;
344344 let input_total_byte_size = input_stats. total_byte_size ;
345345
346+ // A column holding each of its values once, as a primary key or unique
347+ // constraint says, matches one row per value asked for. No selectivity
348+ // expresses that.
349+ let match_limit = unique_match_limit ( predicate, & input_stats) ;
350+
346351 let ( selectivity, num_rows, column_statistics) = if is_infeasible {
347352 // Contradictory predicate: no rows survive. Row-bounded counts are
348353 // zero; value statistics are undefined on an empty column.
@@ -406,6 +411,10 @@ impl FilterExec {
406411 }
407412 } ;
408413
414+ let num_rows = match ( match_limit, num_rows. get_value ( ) ) {
415+ ( Some ( limit) , Some ( rows) ) if * rows > limit => Precision :: Inexact ( limit) ,
416+ _ => num_rows,
417+ } ;
409418 let total_byte_size =
410419 scale_byte_size_at_rows ( input_total_byte_size, selectivity, num_rows) ;
411420
@@ -972,6 +981,76 @@ impl EmbeddedProjection for FilterExec {
972981 }
973982}
974983
984+ /// The most rows a filter can match, when it restricts a column holding each value
985+ /// once to a fixed set of values: one row per value.
986+ fn unique_match_limit (
987+ predicate : & Arc < dyn PhysicalExpr > ,
988+ statistics : & Statistics ,
989+ ) -> Option < usize > {
990+ let mut limit: Option < usize > = None ;
991+ for expr in split_conjunction ( predicate) {
992+ let Some ( ( index, values) ) = restricted_column ( expr) else {
993+ continue ;
994+ } ;
995+ let holds_once = statistics
996+ . column_statistics
997+ . get ( index)
998+ . is_some_and ( |column| holds_each_value_once ( column, & statistics. num_rows ) ) ;
999+ if !holds_once {
1000+ continue ;
1001+ }
1002+ limit = Some ( limit. map_or ( values, |limit : usize | limit. min ( values) ) ) ;
1003+ }
1004+ limit
1005+ }
1006+
1007+ /// The column an expression restricts to a fixed set of values, and how many values
1008+ /// that is. NULL is never one of them: it matches nothing.
1009+ fn restricted_column ( expr : & Arc < dyn PhysicalExpr > ) -> Option < ( usize , usize ) > {
1010+ if let Some ( in_list) = expr. downcast_ref :: < InListExpr > ( ) {
1011+ if in_list. negated ( ) {
1012+ return None ;
1013+ }
1014+ let column = in_list. expr ( ) . downcast_ref :: < Column > ( ) ?;
1015+ let mut values: Vec < & ScalarValue > = vec ! [ ] ;
1016+ for expr in in_list. list ( ) {
1017+ let value = expr. downcast_ref :: < Literal > ( ) ?. value ( ) ;
1018+ if !value. is_null ( ) && !values. contains ( & value) {
1019+ values. push ( value) ;
1020+ }
1021+ }
1022+ return Some ( ( column. index ( ) , values. len ( ) ) ) ;
1023+ }
1024+
1025+ let binary = expr. downcast_ref :: < BinaryExpr > ( ) ?;
1026+ if * binary. op ( ) != Operator :: Eq {
1027+ return None ;
1028+ }
1029+ let ( column, literal) = match (
1030+ binary. left ( ) . downcast_ref :: < Column > ( ) ,
1031+ binary. right ( ) . downcast_ref :: < Column > ( ) ,
1032+ ) {
1033+ ( Some ( column) , None ) => ( column, binary. right ( ) ) ,
1034+ ( None , Some ( column) ) => ( column, binary. left ( ) ) ,
1035+ _ => return None ,
1036+ } ;
1037+ let value = literal. downcast_ref :: < Literal > ( ) ?. value ( ) ;
1038+ ( !value. is_null ( ) ) . then_some ( ( column. index ( ) , 1 ) )
1039+ }
1040+
1041+ /// Whether the column has as many distinct values as it has non-null rows, so each
1042+ /// value appears once.
1043+ fn holds_each_value_once ( column : & ColumnStatistics , num_rows : & Precision < usize > ) -> bool {
1044+ let ( Some ( rows) , Some ( distinct) , Some ( nulls) ) = (
1045+ num_rows. get_value ( ) ,
1046+ column. distinct_count . get_value ( ) ,
1047+ column. null_count . get_value ( ) ,
1048+ ) else {
1049+ return false ;
1050+ } ;
1051+ distinct. saturating_add ( * nulls) >= * rows
1052+ }
1053+
9751054/// Collects column equality information from `col = literal` predicates in a
9761055/// conjunction.
9771056///
@@ -1486,6 +1565,100 @@ mod tests {
14861565 Ok ( ( ) )
14871566 }
14881567
1568+ /// An equality on a column that holds each value once matches one row at most,
1569+ /// including on a type interval analysis cannot read, where the default
1570+ /// selectivity would otherwise apply.
1571+ #[ tokio:: test]
1572+ async fn test_filter_statistics_equality_on_a_unique_column ( ) -> Result < ( ) > {
1573+ let schema = Schema :: new ( vec ! [ Field :: new( "id" , DataType :: Utf8 , true ) ] ) ;
1574+ let unique = ColumnStatistics {
1575+ null_count : Precision :: Exact ( 0 ) ,
1576+ distinct_count : Precision :: Exact ( 100 ) ,
1577+ ..Default :: default ( )
1578+ } ;
1579+ let rows = |column : ColumnStatistics | -> Result < Precision < usize > > {
1580+ let input = Arc :: new ( StatisticsExec :: new (
1581+ Statistics {
1582+ num_rows : Precision :: Exact ( 100 ) ,
1583+ total_byte_size : Precision :: Exact ( 800 ) ,
1584+ column_statistics : vec ! [ column] ,
1585+ } ,
1586+ schema. clone ( ) ,
1587+ ) ) ;
1588+ let predicate =
1589+ binary ( col ( "id" , & schema) ?, Operator :: Eq , lit ( "seven" ) , & schema) ?;
1590+ let filter: Arc < dyn ExecutionPlan > =
1591+ Arc :: new ( FilterExec :: try_new ( predicate, input) ?) ;
1592+ Ok ( StatisticsContext :: new ( )
1593+ . compute ( filter. as_ref ( ) , & StatisticsArgs :: new ( ) ) ?
1594+ . num_rows )
1595+ } ;
1596+
1597+ assert_eq ! ( rows( unique. clone( ) ) ?, Precision :: Inexact ( 1 ) ) ;
1598+
1599+ // The nulls a unique column may repeat do not make it hold a value twice.
1600+ assert_eq ! (
1601+ rows( ColumnStatistics {
1602+ null_count: Precision :: Exact ( 10 ) ,
1603+ distinct_count: Precision :: Exact ( 90 ) ,
1604+ ..unique. clone( )
1605+ } ) ?,
1606+ Precision :: Inexact ( 1 )
1607+ ) ;
1608+
1609+ // Without a distinct count, the default selectivity applies as before.
1610+ assert_eq ! (
1611+ rows( ColumnStatistics {
1612+ distinct_count: Precision :: Absent ,
1613+ ..unique
1614+ } ) ?,
1615+ Precision :: Inexact ( 20 )
1616+ ) ;
1617+
1618+ Ok ( ( ) )
1619+ }
1620+
1621+ /// Asking a unique column for three values matches three rows at most.
1622+ #[ tokio:: test]
1623+ async fn test_filter_statistics_in_list_on_a_unique_column ( ) -> Result < ( ) > {
1624+ use datafusion_physical_expr:: expressions:: in_list;
1625+
1626+ let schema = Schema :: new ( vec ! [ Field :: new( "id" , DataType :: Utf8 , true ) ] ) ;
1627+ let rows = |list : Vec < & str > , negated : bool | -> Result < Precision < usize > > {
1628+ let input = Arc :: new ( StatisticsExec :: new (
1629+ Statistics {
1630+ num_rows : Precision :: Exact ( 100 ) ,
1631+ total_byte_size : Precision :: Exact ( 800 ) ,
1632+ column_statistics : vec ! [ ColumnStatistics {
1633+ null_count: Precision :: Exact ( 0 ) ,
1634+ distinct_count: Precision :: Exact ( 100 ) ,
1635+ ..Default :: default ( )
1636+ } ] ,
1637+ } ,
1638+ schema. clone ( ) ,
1639+ ) ) ;
1640+ let predicate = in_list (
1641+ col ( "id" , & schema) ?,
1642+ list. into_iter ( ) . map ( |value| lit ( value) as _ ) . collect ( ) ,
1643+ & negated,
1644+ & schema,
1645+ ) ?;
1646+ let filter: Arc < dyn ExecutionPlan > =
1647+ Arc :: new ( FilterExec :: try_new ( predicate, input) ?) ;
1648+ Ok ( StatisticsContext :: new ( )
1649+ . compute ( filter. as_ref ( ) , & StatisticsArgs :: new ( ) ) ?
1650+ . num_rows )
1651+ } ;
1652+
1653+ assert_eq ! ( rows( vec![ "a" , "b" , "c" ] , false ) ?, Precision :: Inexact ( 3 ) ) ;
1654+ // Repeats ask for the same row twice.
1655+ assert_eq ! ( rows( vec![ "a" , "b" , "a" ] , false ) ?, Precision :: Inexact ( 2 ) ) ;
1656+ // `NOT IN` selects nearly everything, so the default applies.
1657+ assert_eq ! ( rows( vec![ "a" , "b" , "c" ] , true ) ?, Precision :: Inexact ( 20 ) ) ;
1658+
1659+ Ok ( ( ) )
1660+ }
1661+
14891662 #[ tokio:: test]
14901663 async fn test_filter_statistics_basic_expr ( ) -> Result < ( ) > {
14911664 // Table:
0 commit comments