Skip to content

Commit 4e05212

Browse files
committed
address review: build the next-file map in one pass from the back
1 parent 37ba40d commit 4e05212

1 file changed

Lines changed: 51 additions & 7 deletions

File tree

‎native/core/src/parquet/eager_page_index_reader_factory.rs‎

Lines changed: 51 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -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

Comments
 (0)