@@ -870,16 +870,24 @@ impl NextFileMetadataPrefetch {
870870 scan_io_metrics : Arc < ScanIoMetrics > ,
871871 metadata_cache : Arc < FileMetadataCache > ,
872872 ) -> Self {
873+ // One pass from the back, so a long run of ranges of one path costs linear time. The next
874+ // file of `files[i]` is `files[i + 1]` when its path differs and `files[i + 1]`'s own next
875+ // file otherwise. Inserting while walking backwards lets the earliest of any duplicate
876+ // key win.
873877 let mut next_files = HashMap :: new ( ) ;
874- for ( position, file) in files. iter ( ) . enumerate ( ) {
878+ let mut next: Option < & PartitionedFile > = None ;
879+ for ( position, file) in files. iter ( ) . enumerate ( ) . rev ( ) {
875880 let location = & file. object_meta . location ;
876- let next = files[ position + 1 ..]
877- . iter ( )
878- . find ( |next| & next. object_meta . location != location) ;
881+ if let Some ( following) = files. get ( position + 1 ) {
882+ if & following. object_meta . location != location {
883+ next = Some ( following) ;
884+ }
885+ }
879886 if let Some ( next) = next {
880- next_files
881- . entry ( ( location. clone ( ) , file. range . clone ( ) ) )
882- . or_insert_with ( || ( next. object_meta . clone ( ) , next. metadata_size_hint ) ) ;
887+ next_files. insert (
888+ ( location. clone ( ) , file. range . clone ( ) ) ,
889+ ( next. object_meta . clone ( ) , next. metadata_size_hint ) ,
890+ ) ;
883891 }
884892 }
885893 Self {
@@ -1970,6 +1978,42 @@ mod tests {
19701978 assert ! ( in_flight_is_empty( & factory) ) ;
19711979 }
19721980
1981+ /// The map of next files comes from one pass over the group, so a path that comes back later
1982+ /// keeps the next file of its earliest range, and a long run of ranges of one path builds
1983+ /// without a search per range.
1984+ #[ tokio:: test]
1985+ async fn the_next_file_map_handles_repeated_paths_and_long_runs ( ) {
1986+ let file = |name : & str | PartitionedFile :: new ( name. to_string ( ) , 100 ) ;
1987+ let mut files = vec ! [
1988+ file( "a.parquet" ) ,
1989+ file( "b.parquet" ) ,
1990+ file( "a.parquet" ) ,
1991+ file( "c.parquet" ) ,
1992+ ] ;
1993+ // 40,000 ranges of one path: quadratic construction takes seconds, a linear pass doesn't.
1994+ files. extend ( ( 0 ..40_000 ) . map ( |i| file ( "d.parquet" ) . with_range ( i, i + 1 ) ) ) ;
1995+ let metrics = ExecutionPlanMetricsSet :: new ( ) ;
1996+ let started = std:: time:: Instant :: now ( ) ;
1997+ let factory = prefetching_factory ( Arc :: new ( InMemory :: new ( ) ) , & files, & metrics) ;
1998+ assert ! ( started. elapsed( ) < std:: time:: Duration :: from_secs( 1 ) ) ;
1999+
2000+ let prefetch = factory. next_file_prefetch . as_ref ( ) . unwrap ( ) ;
2001+ let next = |file : & PartitionedFile | {
2002+ prefetch
2003+ . next_files
2004+ . get ( & ( file. object_meta . location . clone ( ) , file. range . clone ( ) ) )
2005+ . map ( |( next, _) | next. location . to_string ( ) )
2006+ } ;
2007+ // The first a wins over the second, which would give c.
2008+ assert_eq ! ( next( & files[ 0 ] ) . as_deref( ) , Some ( "b.parquet" ) ) ;
2009+ assert_eq ! ( next( & files[ 1 ] ) . as_deref( ) , Some ( "a.parquet" ) ) ;
2010+ assert_eq ! ( next( & files[ 3 ] ) . as_deref( ) , Some ( "d.parquet" ) ) ;
2011+ // d has no file after its ranges.
2012+ assert_eq ! ( next( & files[ 4 ] ) , None ) ;
2013+ assert_eq ! ( next( & files[ files. len( ) - 1 ] ) , None ) ;
2014+ assert_eq ! ( prefetch. next_files. len( ) , 3 ) ;
2015+ }
2016+
19732017 /// A prefetch that fails yields nothing, so the file's open loads the metadata itself and
19742018 /// reports the error.
19752019 #[ tokio:: test( flavor = "multi_thread" , worker_threads = 2 ) ]
0 commit comments