@@ -49,9 +49,11 @@ use datafusion_expr::Operator;
4949
5050use crate :: source:: OpenArgs ;
5151use datafusion_common:: stats:: { Precision , is_known_empty} ;
52- use datafusion_physical_expr:: expressions:: { BinaryExpr , Column } ;
52+ use datafusion_physical_expr:: expressions:: {
53+ BinaryExpr , Column , OptionalFilterPhysicalExpr ,
54+ } ;
5355use datafusion_physical_expr:: projection:: { ProjectionExprs , ProjectionMapping } ;
54- use datafusion_physical_expr:: utils:: reassign_expr_columns;
56+ use datafusion_physical_expr:: utils:: { is_optional_filter , reassign_expr_columns} ;
5557use datafusion_physical_expr:: { EquivalenceProperties , Partitioning , split_conjunction} ;
5658use datafusion_physical_expr_adapter:: PhysicalExprAdapterFactory ;
5759use datafusion_physical_expr_common:: physical_expr:: { PhysicalExpr , is_volatile} ;
@@ -62,8 +64,9 @@ use datafusion_physical_plan::execution_plan::SchedulingType;
6264use datafusion_physical_plan:: {
6365 DisplayAs , DisplayFormatType ,
6466 display:: { ProjectSchemaDisplay , display_orderings} ,
65- filter_pushdown:: FilterPushdownPropagation ,
67+ filter_pushdown:: { FilterPushdownPropagation , PushedDown } ,
6668 metrics:: ExecutionPlanMetricsSet ,
69+ repartition:: round_robin_beneficial_for_rows,
6770} ;
6871use log:: { debug, warn} ;
6972use std:: any:: Any ;
@@ -1055,9 +1058,37 @@ impl DataSource for FileScanConfig {
10551058 . map ( |filter| reassign_expr_columns ( filter, table_schema) )
10561059 . collect :: < Result < Vec < _ > > > ( ) ?;
10571060
1058- let result = self
1061+ // A filter that the scan applies runs in the partitions of the scan.
1062+ // If the optimizer would run a `FilterExec` above this scan in more
1063+ // partitions than the scan has, keep the required filters above the
1064+ // scan. The file source gets them as optional filters: it can use
1065+ // them to prune, and it can skip them, because the filter above
1066+ // removes the rows.
1067+ let keep_above = self . filters_run_in_more_partitions_above ( config) ?;
1068+ let kept_above: Vec < bool > = remapped_filters
1069+ . iter ( )
1070+ . map ( |filter| keep_above && !is_optional_filter ( filter) )
1071+ . collect ( ) ;
1072+ let remapped_filters = remapped_filters
1073+ . into_iter ( )
1074+ . zip ( & kept_above)
1075+ . map ( |( filter, kept_above) | {
1076+ if * kept_above {
1077+ Arc :: new ( OptionalFilterPhysicalExpr :: new ( filter) ) as _
1078+ } else {
1079+ filter
1080+ }
1081+ } )
1082+ . collect ( ) ;
1083+
1084+ let mut result = self
10591085 . file_source
10601086 . try_pushdown_filters ( remapped_filters, config) ?;
1087+ for ( pushed_down, kept_above) in result. filters . iter_mut ( ) . zip ( kept_above) {
1088+ if kept_above {
1089+ * pushed_down = PushedDown :: No ;
1090+ }
1091+ }
10611092 match result. updated_node {
10621093 Some ( new_file_source) => {
10631094 let mut new_file_scan_config = self . clone ( ) ;
@@ -1306,6 +1337,49 @@ impl FileScanConfig {
13061337 )
13071338 }
13081339
1340+ /// Returns `true` if a filter above this scan runs in more partitions than
1341+ /// a filter in this scan.
1342+ ///
1343+ /// A filter that the scan applies runs in the partitions of the scan. A
1344+ /// `FilterExec` above the scan runs in the partitions of its input. If
1345+ /// the scan cannot give `target_partitions` partitions, the
1346+ /// `EnforceDistribution` rule puts a round-robin `RepartitionExec`
1347+ /// between the scan and the `FilterExec`, when the input can have more
1348+ /// rows than one batch. The `FilterExec` then runs in
1349+ /// `target_partitions` partitions.
1350+ ///
1351+ /// This function uses the same checks as `EnforceDistribution`: the
1352+ /// partitions that [`DataSource::repartitioned`] gives, and
1353+ /// [`round_robin_beneficial_for_rows`] on the rows that the scan reads.
1354+ /// The rows before the filter are the input of that round-robin
1355+ /// repartition. An exact count is a limit: when it is at most one batch,
1356+ /// a round-robin repartition cannot split the work.
1357+ fn filters_run_in_more_partitions_above (
1358+ & self ,
1359+ config : & ConfigOptions ,
1360+ ) -> Result < bool > {
1361+ let target_partitions = config. execution . target_partitions ;
1362+ let partitions = self . output_partitioning ( ) . partition_count ( ) ;
1363+ if !config. optimizer . enable_round_robin_repartition
1364+ || partitions >= target_partitions
1365+ || !round_robin_beneficial_for_rows ( & self . statistics . num_rows , config)
1366+ {
1367+ return Ok ( false ) ;
1368+ }
1369+ if !config. optimizer . repartition_file_scans {
1370+ return Ok ( true ) ;
1371+ }
1372+ let repartitioned = self . repartitioned (
1373+ target_partitions,
1374+ config. optimizer . repartition_file_min_size ,
1375+ self . eq_properties ( ) . output_ordering ( ) ,
1376+ ) ?;
1377+ let partitions = repartitioned
1378+ . map ( |source| source. output_partitioning ( ) . partition_count ( ) )
1379+ . unwrap_or ( partitions) ;
1380+ Ok ( partitions < target_partitions)
1381+ }
1382+
13091383 /// Get the file schema (schema of the files without partition columns)
13101384 pub fn file_schema ( & self ) -> & SchemaRef {
13111385 self . file_source . table_schema ( ) . file_schema ( )
@@ -4127,4 +4201,193 @@ mod tests {
41274201
41284202 assert ! ( !would_duplicate_costly_exprs( & inner, & outer) ) ;
41294203 }
4204+
4205+ /// Tests for the filters that stay above a scan that cannot give the
4206+ /// parallelism of a filter above it.
4207+ mod filters_above_scan {
4208+ use super :: * ;
4209+ use datafusion_physical_expr:: expressions:: { binary, lit} ;
4210+
4211+ /// A file source that applies all filters that it gets.
4212+ #[ derive( Clone ) ]
4213+ struct FilteringSource {
4214+ metrics : ExecutionPlanMetricsSet ,
4215+ table_schema : TableSchema ,
4216+ filter : Option < Arc < dyn PhysicalExpr > > ,
4217+ }
4218+
4219+ impl FileSource for FilteringSource {
4220+ fn create_file_opener (
4221+ & self ,
4222+ _object_store : Arc < dyn ObjectStore > ,
4223+ _base_config : & FileScanConfig ,
4224+ _partition : usize ,
4225+ ) -> Result < Arc < dyn crate :: file_stream:: FileOpener > > {
4226+ unimplemented ! ( )
4227+ }
4228+
4229+ fn table_schema ( & self ) -> & TableSchema {
4230+ & self . table_schema
4231+ }
4232+
4233+ fn with_batch_size ( & self , _batch_size : usize ) -> Arc < dyn FileSource > {
4234+ Arc :: new ( self . clone ( ) )
4235+ }
4236+
4237+ fn metrics ( & self ) -> & ExecutionPlanMetricsSet {
4238+ & self . metrics
4239+ }
4240+
4241+ fn file_type ( & self ) -> & str {
4242+ "filtering"
4243+ }
4244+
4245+ fn filter ( & self ) -> Option < Arc < dyn PhysicalExpr > > {
4246+ self . filter . clone ( )
4247+ }
4248+
4249+ fn try_pushdown_filters (
4250+ & self ,
4251+ filters : Vec < Arc < dyn PhysicalExpr > > ,
4252+ _config : & ConfigOptions ,
4253+ ) -> Result < FilterPushdownPropagation < Arc < dyn FileSource > > > {
4254+ let pushed_down = vec ! [ PushedDown :: Yes ; filters. len( ) ] ;
4255+ let source = Self {
4256+ filter : Some ( datafusion_physical_expr:: conjunction ( filters) ) ,
4257+ ..self . clone ( )
4258+ } ;
4259+ Ok (
4260+ FilterPushdownPropagation :: with_parent_pushdown_result ( pushed_down)
4261+ . with_updated_node ( Arc :: new ( source) as _ ) ,
4262+ )
4263+ }
4264+
4265+ fn apply_expressions (
4266+ & self ,
4267+ _f : & mut dyn FnMut ( & Arc < dyn PhysicalExpr > ) -> Result < TreeNodeRecursion > ,
4268+ ) -> Result < TreeNodeRecursion > {
4269+ Ok ( TreeNodeRecursion :: Continue )
4270+ }
4271+ }
4272+
4273+ fn schema ( ) -> SchemaRef {
4274+ Arc :: new ( Schema :: new ( vec ! [ Field :: new( "a" , DataType :: Int32 , false ) ] ) )
4275+ }
4276+
4277+ /// A scan of `files` files of `file_size` bytes each, one file in each
4278+ /// partition, with `num_rows` rows in total.
4279+ fn scan ( files : usize , file_size : u64 , num_rows : usize ) -> FileScanConfig {
4280+ let schema = schema ( ) ;
4281+ let source = FilteringSource {
4282+ metrics : ExecutionPlanMetricsSet :: new ( ) ,
4283+ table_schema : TableSchema :: from ( & schema) ,
4284+ filter : None ,
4285+ } ;
4286+ let files = ( 0 ..files)
4287+ . map ( |i| {
4288+ FileGroup :: new ( vec ! [ PartitionedFile :: new(
4289+ format!( "f{i}.parquet" ) ,
4290+ file_size,
4291+ ) ] )
4292+ } )
4293+ . collect :: < Vec < _ > > ( ) ;
4294+ FileScanConfigBuilder :: new (
4295+ ObjectStoreUrl :: local_filesystem ( ) ,
4296+ Arc :: new ( source) ,
4297+ )
4298+ . with_file_groups ( files)
4299+ . with_statistics (
4300+ Statistics :: new_unknown ( & schema)
4301+ . with_num_rows ( Precision :: Exact ( num_rows) ) ,
4302+ )
4303+ . build ( )
4304+ }
4305+
4306+ fn config ( target_partitions : usize ) -> ConfigOptions {
4307+ let mut config = ConfigOptions :: default ( ) ;
4308+ config. execution . target_partitions = target_partitions;
4309+ config
4310+ }
4311+
4312+ fn a_gt_5 ( ) -> Arc < dyn PhysicalExpr > {
4313+ binary (
4314+ col ( "a" , & schema ( ) ) . unwrap ( ) ,
4315+ Operator :: Gt ,
4316+ lit ( 5 ) ,
4317+ & schema ( ) ,
4318+ )
4319+ . unwrap ( )
4320+ }
4321+
4322+ /// Pushes `a > 5` into `scan`. Returns if the scan applies it, and
4323+ /// the filter of the new file source.
4324+ fn push (
4325+ scan : & FileScanConfig ,
4326+ filter : Arc < dyn PhysicalExpr > ,
4327+ config : & ConfigOptions ,
4328+ ) -> ( Vec < PushedDown > , String ) {
4329+ let result = scan. try_pushdown_filters ( vec ! [ filter] , config) . unwrap ( ) ;
4330+ let node = result. updated_node . expect ( "the source takes the filter" ) ;
4331+ let node = node. downcast_ref :: < FileScanConfig > ( ) . unwrap ( ) ;
4332+ let filter = node. file_source . filter ( ) . unwrap ( ) . to_string ( ) ;
4333+ ( result. filters , filter)
4334+ }
4335+
4336+ #[ test]
4337+ fn filter_stays_above_a_scan_that_cannot_split ( ) {
4338+ // One small file: the scan has one partition and cannot split
4339+ // the file, thus a filter above the scan runs in 4 partitions.
4340+ let ( pushed_down, filter) =
4341+ push ( & scan ( 1 , 1024 , 100_000 ) , a_gt_5 ( ) , & config ( 4 ) ) ;
4342+ assert ! ( matches!( pushed_down[ ..] , [ PushedDown :: No ] ) ) ;
4343+ assert_eq ! ( filter, "Optional(a@0 > 5)" ) ;
4344+ }
4345+
4346+ #[ test]
4347+ fn scan_applies_the_filter_when_it_has_the_partitions ( ) {
4348+ // One file for each target partition.
4349+ let ( pushed_down, filter) =
4350+ push ( & scan ( 4 , 1024 , 100_000 ) , a_gt_5 ( ) , & config ( 4 ) ) ;
4351+ assert ! ( matches!( pushed_down[ ..] , [ PushedDown :: Yes ] ) ) ;
4352+ assert_eq ! ( filter, "a@0 > 5" ) ;
4353+
4354+ // One large file that the scan splits into 4 byte ranges.
4355+ let ( pushed_down, filter) =
4356+ push ( & scan ( 1 , 1 << 30 , 100_000 ) , a_gt_5 ( ) , & config ( 4 ) ) ;
4357+ assert ! ( matches!( pushed_down[ ..] , [ PushedDown :: Yes ] ) ) ;
4358+ assert_eq ! ( filter, "a@0 > 5" ) ;
4359+
4360+ // One target partition.
4361+ let ( pushed_down, _) = push ( & scan ( 1 , 1024 , 100_000 ) , a_gt_5 ( ) , & config ( 1 ) ) ;
4362+ assert ! ( matches!( pushed_down[ ..] , [ PushedDown :: Yes ] ) ) ;
4363+ }
4364+
4365+ #[ test]
4366+ fn scan_applies_the_filter_when_a_round_robin_does_not_help ( ) {
4367+ // The scan reads at most one batch: a round-robin repartition
4368+ // cannot split the work.
4369+ let ( pushed_down, _) = push ( & scan ( 1 , 1024 , 8192 ) , a_gt_5 ( ) , & config ( 4 ) ) ;
4370+ assert ! ( matches!( pushed_down[ ..] , [ PushedDown :: Yes ] ) ) ;
4371+ let ( pushed_down, _) = push ( & scan ( 1 , 1024 , 0 ) , a_gt_5 ( ) , & config ( 4 ) ) ;
4372+ assert ! ( matches!( pushed_down[ ..] , [ PushedDown :: Yes ] ) ) ;
4373+
4374+ // Round-robin repartitions are off.
4375+ let mut config = config ( 4 ) ;
4376+ config. optimizer . enable_round_robin_repartition = false ;
4377+ let ( pushed_down, _) = push ( & scan ( 1 , 1024 , 100_000 ) , a_gt_5 ( ) , & config) ;
4378+ assert ! ( matches!( pushed_down[ ..] , [ PushedDown :: Yes ] ) ) ;
4379+ }
4380+
4381+ #[ test]
4382+ fn optional_filter_goes_into_the_scan ( ) {
4383+ // An optional filter is not needed for correctness, thus it does
4384+ // not need a filter above the scan.
4385+ let optional: Arc < dyn PhysicalExpr > =
4386+ Arc :: new ( OptionalFilterPhysicalExpr :: new ( a_gt_5 ( ) ) ) ;
4387+ let ( pushed_down, filter) =
4388+ push ( & scan ( 1 , 1024 , 100_000 ) , optional, & config ( 4 ) ) ;
4389+ assert ! ( matches!( pushed_down[ ..] , [ PushedDown :: Yes ] ) ) ;
4390+ assert_eq ! ( filter, "Optional(a@0 > 5)" ) ;
4391+ }
4392+ }
41304393}
0 commit comments