Skip to content

Commit 64e67f5

Browse files
committed
[prototype] Bound eager read-ahead with a prefetch budget shared by the files of a partition
datafusion.execution.read_ahead_prefetch_budget_bytes (default 0, no bound) gives each scan partition one byte budget for the eager fetches of the files waiting behind the file being read. Files take from it in the order they are opened, each at most read_ahead_eager_bytes, and give the bytes back when the fetch lands in the decoder or the stream is dropped.
1 parent 67c6969 commit 64e67f5

5 files changed

Lines changed: 187 additions & 14 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1128,6 +1128,13 @@ config_namespace! {
11281128
/// turns it off.
11291129
pub read_ahead_eager_bytes: usize, default = 0
11301130

1131+
/// Bytes that the files waiting behind the file being read may hold
1132+
/// in eager read-ahead, over all files of one scan partition. Each
1133+
/// file still takes at most `read_ahead_eager_bytes`. Files take
1134+
/// from this budget in the order they are opened, and a file gives
1135+
/// its bytes back when the scan reaches it. 0 means no shared bound.
1136+
pub read_ahead_prefetch_budget_bytes: usize, default = 0
1137+
11311138
/// Number of files to read in parallel when inferring schema and statistics
11321139
pub meta_fetch_concurrency: ConfigNonZeroUsize, default = non_zero_usize_default(32)
11331140

‎datafusion/datasource-parquet/src/opener/mod.rs‎

Lines changed: 76 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -35,8 +35,8 @@ use crate::metrics::{ByteProgress, RowFilterSkippedFullyMatchedMetric};
3535
use crate::optional_filter::OptionalFilterOptions;
3636
use crate::page_filter::PagePruningAccessPlanFilter;
3737
use crate::push_decoder::{
38-
DecoderBuilderConfig, InitialDecoderState, PushDecoderStreamState, ReadAhead,
39-
ReadAheadMemory, RgPlanEntry, RowFilterContext, RowGroupPruner,
38+
DecoderBuilderConfig, InitialDecoderState, PrefetchBudget, PushDecoderStreamState,
39+
ReadAhead, ReadAheadMemory, RgPlanEntry, RowFilterContext, RowGroupPruner,
4040
};
4141
use crate::row_filter::{OptionalFilterRowFilterContext, PrebuiltRowFilterCandidate};
4242
use crate::row_group_filter::{RowGroupAccessPlanFilter, row_group_in_range};
@@ -325,6 +325,11 @@ pub(super) struct ParquetMorselizer {
325325
/// Bytes each file stream fetches when it is built. Sourced from
326326
/// `datafusion.execution.read_ahead_eager_bytes`. 0 turns it off.
327327
pub read_ahead_eager_bytes: u64,
328+
/// The budget that bounds eager read-ahead over all files of this
329+
/// partition. Sourced from
330+
/// `datafusion.execution.read_ahead_prefetch_budget_bytes`. `None` means
331+
/// no shared bound.
332+
pub read_ahead_prefetch_budget: Option<Arc<PrefetchBudget>>,
328333
/// Whether to read row groups in reverse order
329334
pub reverse_row_groups: bool,
330335
/// Optional sort order used to reorder row groups by their min/max statistics.
@@ -533,6 +538,7 @@ struct PreparedParquetOpen {
533538
row_group_range_assignment: RowGroupRangeAssignment,
534539
read_ahead_bytes: Option<u64>,
535540
read_ahead_eager_bytes: u64,
541+
read_ahead_prefetch_budget: Option<Arc<PrefetchBudget>>,
536542
reverse_row_groups: bool,
537543
sort_order_for_reorder: Option<LexOrdering>,
538544
preserve_order: bool,
@@ -1183,6 +1189,7 @@ impl ParquetMorselizer {
11831189
row_group_range_assignment: self.row_group_range_assignment,
11841190
read_ahead_bytes: self.read_ahead_bytes,
11851191
read_ahead_eager_bytes: self.read_ahead_eager_bytes,
1192+
read_ahead_prefetch_budget: self.read_ahead_prefetch_budget.clone(),
11861193
reverse_row_groups: self.reverse_row_groups,
11871194
sort_order_for_reorder: self.sort_order_for_reorder.clone(),
11881195
preserve_order: self.preserve_order,
@@ -1925,6 +1932,7 @@ impl RowGroupsPrunedParquetOpen {
19251932

19261933
let read_ahead_bytes = prepared.read_ahead_bytes;
19271934
let read_ahead_eager_bytes = prepared.read_ahead_eager_bytes;
1935+
let read_ahead_prefetch_budget = prepared.read_ahead_prefetch_budget.clone();
19281936

19291937
// Lazily-registered suppression counter shared by the open-time first-RG
19301938
// skip below and the stream's per-RG toggle (registered on first use so
@@ -2152,7 +2160,10 @@ impl RowGroupsPrunedParquetOpen {
21522160
projection_builder,
21532161
read_ahead,
21542162
};
2155-
stream_state.start_eager_read_ahead(read_ahead_eager_bytes);
2163+
stream_state.start_eager_read_ahead(
2164+
read_ahead_eager_bytes,
2165+
read_ahead_prefetch_budget.as_ref(),
2166+
);
21562167
let stream = stream_state.into_stream();
21572168

21582169
// Wrap the stream so a dynamic filter can stop the file scan early, but
@@ -2470,6 +2481,7 @@ mod test {
24702481
row_group_range_assignment: RowGroupRangeAssignment,
24712482
read_ahead_bytes: Option<u64>,
24722483
read_ahead_eager_bytes: u64,
2484+
read_ahead_prefetch_budget: Option<Arc<PrefetchBudget>>,
24732485
memory_pool: Option<Arc<dyn MemoryPool>>,
24742486
reverse_row_groups: bool,
24752487
preserve_order: bool,
@@ -2695,6 +2707,7 @@ mod test {
26952707
row_group_range_assignment: RowGroupRangeAssignment::default(),
26962708
read_ahead_bytes: None,
26972709
read_ahead_eager_bytes: 0,
2710+
read_ahead_prefetch_budget: None,
26982711
memory_pool: None,
26992712
reverse_row_groups: false,
27002713
preserve_order: false,
@@ -2792,6 +2805,15 @@ mod test {
27922805
self
27932806
}
27942807

2808+
/// Set the shared prefetch budget of eager read-ahead.
2809+
fn with_read_ahead_prefetch_budget(
2810+
mut self,
2811+
budget: Arc<PrefetchBudget>,
2812+
) -> Self {
2813+
self.read_ahead_prefetch_budget = Some(budget);
2814+
self
2815+
}
2816+
27952817
/// Set the eager read-ahead bytes (`read_ahead_eager_bytes`).
27962818
fn with_read_ahead_eager_bytes(mut self, bytes: u64) -> Self {
27972819
self.read_ahead_eager_bytes = bytes;
@@ -2942,6 +2964,7 @@ mod test {
29422964
row_group_range_assignment: self.row_group_range_assignment,
29432965
read_ahead_bytes: self.read_ahead_bytes,
29442966
read_ahead_eager_bytes: self.read_ahead_eager_bytes,
2967+
read_ahead_prefetch_budget: self.read_ahead_prefetch_budget.clone(),
29452968
reverse_row_groups: self.reverse_row_groups,
29462969
sort_order_for_reorder: None,
29472970
virtual_state,
@@ -7229,6 +7252,56 @@ mod test {
72297252
(before, rows)
72307253
}
72317254

7255+
/// Verifies that a shared prefetch budget bounds the eager fetches of
7256+
/// the files of one partition: a second file that does not fit waits,
7257+
/// and the first file returns its bytes when its stream is read.
7258+
#[tokio::test]
7259+
async fn prefetch_budget_bounds_eager_fetches_across_files() {
7260+
let store = Arc::new(InMemory::new()) as Arc<dyn ObjectStore>;
7261+
let (schema, len) = write_file(&store).await;
7262+
let fetches = Arc::new(Mutex::new(vec![]));
7263+
let factory = RecordingReaderFactory {
7264+
inner: DefaultParquetFileReaderFactory::new(Arc::clone(&store)),
7265+
fetches: Arc::clone(&fetches),
7266+
};
7267+
let pool: Arc<dyn MemoryPool> =
7268+
Arc::new(GreedyMemoryPool::new(64 * 1024 * 1024));
7269+
let budget_bytes = 400 * 1024;
7270+
let budget = Arc::new(PrefetchBudget::new(budget_bytes));
7271+
let morselizer = ParquetMorselizerBuilder::new()
7272+
.with_store(Arc::clone(&store))
7273+
.with_schema(schema)
7274+
.with_projection_indices(&[0, 1])
7275+
.with_parquet_file_reader_factory(Arc::new(factory))
7276+
.with_read_ahead_bytes(WINDOW)
7277+
.with_read_ahead_eager_bytes(WINDOW / 2)
7278+
.with_read_ahead_prefetch_budget(Arc::clone(&budget))
7279+
.with_memory_pool(Arc::clone(&pool))
7280+
.build();
7281+
let file =
7282+
|| PartitionedFile::new("read_ahead.parquet".to_string(), len as u64);
7283+
7284+
let first = open_file(&morselizer, file()).await.unwrap();
7285+
let second = open_file(&morselizer, file()).await.unwrap();
7286+
tokio::time::sleep(std::time::Duration::from_millis(50)).await;
7287+
let before = fetches.lock().unwrap().clone();
7288+
assert_eq!(before.len(), 1, "only the first file fits: {before:?}");
7289+
assert_eq!(budget.remaining(), budget_bytes - before[0]);
7290+
7291+
let (_batches, rows) = count_batches_and_rows(first).await;
7292+
assert_eq!(rows, ROWS as usize);
7293+
assert_eq!(
7294+
budget.remaining(),
7295+
budget_bytes,
7296+
"the first file gave its bytes back"
7297+
);
7298+
let (_batches, rows) = count_batches_and_rows(second).await;
7299+
assert_eq!(rows, ROWS as usize);
7300+
drop(morselizer);
7301+
assert_eq!(budget.remaining(), budget_bytes);
7302+
assert_eq!(pool.reserved(), 0);
7303+
}
7304+
72327305
/// Verifies that eager read-ahead fetches data before the stream is
72337306
/// polled, within its limit, and that the scan still reads every row.
72347307
#[tokio::test]

‎datafusion/datasource-parquet/src/push_decoder.rs‎

Lines changed: 91 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@
3838
use std::collections::{HashSet, VecDeque};
3939
use std::ops::Range;
4040
use std::sync::Arc;
41+
use std::sync::atomic::{AtomicU64, Ordering};
4142
use std::time::Duration;
4243

4344
use arrow::array::RecordBatch;
@@ -1238,6 +1239,68 @@ struct InFlight {
12381239
ranges: Vec<TaggedRange>,
12391240
/// Total length of `ranges`.
12401241
bytes: u64,
1242+
/// The prefetch budget that an eager fetch holds. Dropping the fetch,
1243+
/// when it lands or when the stream is dropped, returns the bytes.
1244+
_grant: Option<PrefetchGrant>,
1245+
}
1246+
1247+
/// A byte budget shared by the files of one scan partition for eager
1248+
/// read-ahead (see [`PushDecoderStreamState::start_eager_read_ahead`]).
1249+
///
1250+
/// The files that wait behind the file being read take from it in the order
1251+
/// they are opened. A file returns its bytes when its eager fetch lands in the
1252+
/// decoder or when its stream is dropped. Thus the budget bounds the data that
1253+
/// waiting files hold, whatever the number of files opened ahead.
1254+
#[derive(Debug)]
1255+
pub(crate) struct PrefetchBudget {
1256+
remaining: AtomicU64,
1257+
}
1258+
1259+
impl PrefetchBudget {
1260+
pub(crate) fn new(bytes: u64) -> Self {
1261+
Self {
1262+
remaining: AtomicU64::new(bytes),
1263+
}
1264+
}
1265+
1266+
/// Take at most `max` bytes. Returns the bytes taken, 0 if the budget is
1267+
/// empty.
1268+
fn take(&self, max: u64) -> u64 {
1269+
let mut remaining = self.remaining.load(Ordering::Acquire);
1270+
loop {
1271+
let taken = remaining.min(max);
1272+
match self.remaining.compare_exchange_weak(
1273+
remaining,
1274+
remaining - taken,
1275+
Ordering::AcqRel,
1276+
Ordering::Acquire,
1277+
) {
1278+
Ok(_) => return taken,
1279+
Err(current) => remaining = current,
1280+
}
1281+
}
1282+
}
1283+
1284+
fn give_back(&self, bytes: u64) {
1285+
self.remaining.fetch_add(bytes, Ordering::AcqRel);
1286+
}
1287+
1288+
#[cfg(test)]
1289+
pub(crate) fn remaining(&self) -> u64 {
1290+
self.remaining.load(Ordering::Acquire)
1291+
}
1292+
}
1293+
1294+
/// Bytes taken from a [`PrefetchBudget`], returned on drop.
1295+
struct PrefetchGrant {
1296+
budget: Arc<PrefetchBudget>,
1297+
bytes: u64,
1298+
}
1299+
1300+
impl Drop for PrefetchGrant {
1301+
fn drop(&mut self) {
1302+
self.budget.give_back(self.bytes);
1303+
}
12411304
}
12421305

12431306
/// Accounts read-ahead in the [`MemoryPool`]: the bytes the decoder holds
@@ -1605,7 +1668,7 @@ impl PushDecoderStreamState {
16051668
if ranges.is_empty() {
16061669
return;
16071670
}
1608-
self.spawn_read_ahead(ranges);
1671+
self.spawn_read_ahead(ranges, None);
16091672
}
16101673

16111674
/// Start the first read-ahead fetch now, before the stream is polled,
@@ -1617,28 +1680,50 @@ impl PushDecoderStreamState {
16171680
///
16181681
/// Planned ranges are taken in order while they fit. Thus if the first
16191682
/// planned range is bigger than `limit`, this fetches nothing.
1620-
pub(crate) fn start_eager_read_ahead(&mut self, limit: u64) {
1683+
pub(crate) fn start_eager_read_ahead(
1684+
&mut self,
1685+
limit: u64,
1686+
budget: Option<&Arc<PrefetchBudget>>,
1687+
) {
16211688
let Some(read_ahead) = self.read_ahead.as_mut() else {
16221689
return;
16231690
};
16241691
if limit == 0 || read_ahead.in_flight.is_some() || self.reader.is_none() {
16251692
return;
16261693
}
1627-
let free = limit.min(read_ahead.window);
1694+
let mut free = limit.min(read_ahead.window);
1695+
if let Some(budget) = budget {
1696+
free = budget.take(free);
1697+
if free == 0 {
1698+
return;
1699+
}
1700+
}
16281701
let current = read_ahead.current_row_group;
16291702
let ranges = read_ahead.take_ranges(
16301703
free,
16311704
keep_row_group(current, &self.rg_plan, self.row_group_pruner.as_mut()),
16321705
);
1706+
let bytes: u64 = ranges.iter().map(|(r, _)| r.end - r.start).sum();
1707+
let grant = budget.map(|budget| {
1708+
budget.give_back(free - bytes);
1709+
PrefetchGrant {
1710+
budget: Arc::clone(budget),
1711+
bytes,
1712+
}
1713+
});
16331714
if ranges.is_empty() {
16341715
return;
16351716
}
16361717
read_ahead.first_fetch = false;
1637-
self.spawn_read_ahead(ranges);
1718+
self.spawn_read_ahead(ranges, grant);
16381719
}
16391720

16401721
/// Spawn a background fetch of `ranges` with the idle reader.
1641-
fn spawn_read_ahead(&mut self, mut ranges: Vec<TaggedRange>) {
1722+
fn spawn_read_ahead(
1723+
&mut self,
1724+
mut ranges: Vec<TaggedRange>,
1725+
grant: Option<PrefetchGrant>,
1726+
) {
16421727
ranges.sort_by_key(|(range, _)| range.start);
16431728
let fetch: Vec<Range<u64>> = ranges.iter().map(|(r, _)| r.clone()).collect();
16441729
let bytes = fetch.iter().map(|r| r.end - r.start).sum();
@@ -1654,6 +1739,7 @@ impl PushDecoderStreamState {
16541739
task,
16551740
ranges,
16561741
bytes,
1742+
_grant: grant,
16571743
});
16581744
}
16591745

‎datafusion/datasource-parquet/src/source.rs‎

Lines changed: 10 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@ use crate::opener::ParquetMorselizer;
2828
use crate::opener::build_pruning_predicates;
2929
use crate::opener::build_virtual_columns_state;
3030
use crate::optional_filter::{DecodeCost, OptionalFilterOptions, OptionalFilterSites};
31+
use crate::push_decoder::PrefetchBudget;
3132
use crate::row_filter::can_expr_be_pushed_down_with_schemas;
3233
use arrow_schema::Fields;
3334
use arrow_schema::extension::ExtensionType;
@@ -726,6 +727,7 @@ impl ParquetSource {
726727
.read_ahead_bytes
727728
.map(|bytes| bytes as u64),
728729
read_ahead_eager_bytes: 0,
730+
read_ahead_prefetch_budget: None,
729731
reverse_row_groups: self.reverse_row_groups,
730732
sort_order_for_reorder: self.sort_order_for_reorder.clone(),
731733
virtual_state,
@@ -786,11 +788,14 @@ impl FileSource for ParquetSource {
786788
.map(|_| Arc::clone(context.memory_pool()));
787789
let mut morselizer =
788790
self.build_morselizer(object_store, base_config, partition, memory_pool)?;
789-
morselizer.read_ahead_eager_bytes = context
790-
.session_config()
791-
.options()
792-
.execution
793-
.read_ahead_eager_bytes as u64;
791+
let execution = &context.session_config().options().execution;
792+
morselizer.read_ahead_eager_bytes = execution.read_ahead_eager_bytes as u64;
793+
morselizer.read_ahead_prefetch_budget =
794+
(execution.read_ahead_prefetch_budget_bytes > 0).then(|| {
795+
Arc::new(PrefetchBudget::new(
796+
execution.read_ahead_prefetch_budget_bytes as u64,
797+
))
798+
});
794799
Ok(Box::new(morselizer))
795800
}
796801

‎datafusion/datasource/src/file_scan_config/mod.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -62,10 +62,12 @@ use datafusion_physical_plan::execution_plan::SchedulingType;
6262
use datafusion_physical_plan::{
6363
DisplayAs, DisplayFormatType,
6464
display::{ProjectSchemaDisplay, display_orderings},
65-
filter_pushdown::{FilterPushdownPropagation, PushedDown},
65+
filter_pushdown::FilterPushdownPropagation,
6666
metrics::ExecutionPlanMetricsSet,
6767
repartition::round_robin_beneficial_for_rows,
6868
};
69+
#[cfg(test)]
70+
use datafusion_physical_plan::filter_pushdown::PushedDown;
6971
use log::{debug, warn};
7072
use std::any::Any;
7173
use std::{fmt::Debug, fmt::Formatter, fmt::Result as FmtResult, sync::Arc};

0 commit comments

Comments
 (0)