Skip to content

Commit adffd19

Browse files
fix: leave memory for others when a spilled sort merges its runs (apache#26264)
## Which issue does this PR close? - Part of apache#25804 (finding 9: "The final spill merge grows its reservation until the pool refuses"). ## Rationale for this change A sort that has spilled finishes with a merge of its spilled runs. That merge seats as many runs as the memory pool will admit (the fan-in is unlimited by default), and it holds those buffers until its output is fully consumed. In a query with several partitions, partitions that finish their input early start this final merge while other partitions are still buffering input, and while the operator above the sort is still running. Each early merge takes whatever the pool admits, and the pool can be exhausted. The partition that is still sorting then fails to grow its reservation and the query fails with `ResourcesExhausted`, even though only memory for read-ahead buffers was taken. A standalone reproduction (below): 6.67M rows, `SUM(p) OVER (PARTITION BY g ORDER BY k ROWS UNBOUNDED PRECEDING)` followed by `MAX`, 10 target partitions, a `FairSpillPool` of 62.5 MB, 40 runs per setting: | `sort_spill_reservation_bytes` | main (2c568b4) | this PR | |---|---|---| | 1 MB | 25 / 40 succeed | 40 / 40 | | 1.6 MB | 34 / 40 | 40 / 40 | | 3 MB | 7 / 40 | 35 / 40 | The failures are the partitions that are still sorting: `Failed to allocate additional 3.0 MB for ExternalSorterMerge[6] with 0.0 B already allocated`, `... 598.8 KB for ExternalSorter[8] with 0.0 B ...`, or `... 144.1 KB for ExternalSorterMerge[7]` in `BatchBuilder::push_batch` while merging in-memory batches to spill. With a pool instrumented to record each consumer's reservation, five partitions in their final merge held 12-29 MB each when the refusal happened. Capping `max_spill_merge_fan_in` at 4 made the same runs succeed, which confirms that the merge fan-in causes the failures. ## What changes are included in this PR? apache#25383 lets aggregate spill replay leave memory for the aggregate: the merge asks the pool to admit its buffers plus as much again, then returns the extra. The sort uses a narrower form of that policy: - The minimum merge of two runs is admitted as before, against the pool alone. A sort under tight memory keeps its current behavior: it does not re-spill runs smaller or emit shorter batches only to leave headroom. - Each run beyond the minimum is seated only if the pool can admit what the merge takes beyond the workspace it already holds (`sort_spill_reservation_bytes`, retained since apache#24740), plus as much again. The extra is returned before the merge starts. Seating runs within the merge's own workspace needs no headroom, because it takes nothing from others. When the pool refuses, the merge seats fewer runs and merges in more passes, as it already does under memory pressure. The policy is a new `with_fan_in_headroom` option on `StreamingMergeBuilder` and `MultiLevelMergeBuilder`, enabled by `ExternalSorter`. The aggregate's replay headroom is unchanged. Headroom is kept only while someone may need it: while another partition of the same `SortExec` is still reading its input, or while another consumer holds memory in the pool. Partitions that have already started their own final merge are covered by the second check. A partition leaves the count when it has read all its input, or when it is dropped before that (its stream dropped early, or its input failed). A sort with the pool to itself seats every run that fits, as before, and so does the last partition to finish reading: keeping headroom there cost an extra merge pass (up to 1.8x the spilled rows) whether or not anyone needed the memory. With all 2M rows in one of 4 partitions, most pools between 16 and 64 MB spilled 1.5-1.8x the rows with headroom on; with the count of partitions still reading, every pool from 16 to 128 MB spills the same rows as without headroom. On balanced multi-partition sorts (2M rows, greedy pool, 20 runs each, same build with headroom off and on; measured by @jayzhan211 before headroom followed the count of partitions still reading, which moved these configs from 54 to 49 of 60 successes, against 32 without headroom): | partitions / pool / reservation | success, off → on | spilled rows, off → on | |---|---|---| | 4 / 96 MB / 1 MB | 8 → 17 of 20 | 2.76M → 3.35M | | 8 / 192 MB / 10 MB | 12 → 17 of 20 | 2.00M → 2.16M | | 2 / 64 MB / 1 MB | 12 → 20 of 20 | 3.00M → 3.82M | Where another consumer holds memory, headroom is kept and the merge seats fewer runs, so it rewrites rows in more passes. That is the price of the fix: with a skewed 4-partition sort under `SortPreservingMergeExec`, or two one-partition sorts sharing a pool, @jayzhan211 measured up to 1.9x the spilled rows at 24297ff. `sort_tpch` SF1 Q3/Q4/Q11 showed no wall-clock change above noise. <details> <summary>Measured cost at 24297ff, same build with headroom off and on (by @jayzhan211)</summary> | Plan | Pool | Success, off → on | Spilled rows, off → on | |---|---|---|---| | 4 partitions, 97/1/1/1 of 2M rows, under `SortPreservingMergeExec` | 24 MB | 9/9 → 9/9 | 7.66M → 11.01M | | same | 32 MB | 9/9 → 9/9 | 4.99M → 9.38M | | same | 48 MB | 1/9 → 9/9 | 2.99M → 4.40M | | same | 64 MB | 9/9 → 9/9 | 1.94M → 3.12M | | Two one-partition `SortExec`s, 1.5M rows each | 32 MB | 20/20 → 20/20 | 7.83M → 14.28M | | same | 48 MB | 17/20 → 19/20 | 6.10M → 8.24M | Greedy pool, 1 MB `sort_spill_reservation_bytes`. </details> ### What this does not fix Each merge leaves as much free as it takes, but merges that start one after another still compound: in the remaining 3 MB failures, nine partitions held 3-18 MB each (17.9, 11.5, 7.7, 5.1, ... MB), and the last partition to start could not reserve its own 3 MB `sort_spill_reservation_bytes`. With 10 partitions, the workspaces alone are half of this pool. A guarantee would need each merge to know how many partitions share the pool, for example a per-partition share of the limit. I left that out of this PR, because it is a larger policy change and I would like to hear whether it is wanted. A single-partition sort, or the last partition to finish reading, still leaves nothing for the operator above it: that operator reserves nothing before its first batch, so the merge cannot see it. A `SortExec` whose partitions are not all executed (for example under a `LIMIT` that stops early) counts the partitions never started as still reading, so it keeps headroom. ## What is the testing strategy for this PR? - `test_final_spilled_merge_leaves_headroom` (sort/spill_tests.rs) spills a sort and leaves the pool room for the final merge to seat every run, but not to seat every run and still leave as much free. It checks that whatever the merge takes beyond its workspace, it leaves as much free, and that the output is correct and every reservation is released. It fails on main ("the final merge takes 168128 bytes beyond its workspace and leaves 109728 free"). - `test_sort_exec_keeps_headroom_only_while_siblings_read_input` runs a `SortExec` partition with no sibling, an idle sibling, a sibling that has finished reading, and a sibling whose stream was dropped unpolled; it fails if the condition is replaced by `true` or `false`, or if a dropped partition stays counted. - `test_sort_exec_rerun_without_reset_state_keeps_no_headroom` executes a lone partition three times without `reset_state`; it fails if the count wraps. - Existing tests pass unchanged: `datafusion-physical-plan` (2970), `datafusion-execution`, the `memory_limit` tests in `core_integration`, and the sort, merge, spilling and aggregate fuzz tests (`extended_tests`). In particular, the batch-size test under a tight limit (`..._when_having_to_spill`) and the workspace retention tests from apache#24740 are unaffected. <details> <summary>Reproduction</summary> `Cargo.toml`: ```toml [package] name = "sortrepro" version = "0.1.0" edition = "2024" [dependencies] datafusion = { git = "https://github.com/apache/datafusion", default-features = false } tokio = { version = "1", features = ["rt-multi-thread"] } futures = "0.3" ``` `src/main.rs`, run as `sortrepro <sort_spill_reservation_bytes> <runs>`: ```rust //! A window over a spilling sort, 10 partitions, one FairSpillPool. //! Usage: sortrepro <sort_spill_reservation_bytes> <runs> use std::sync::Arc; use datafusion::arrow::array::{Decimal256Array, Int32Array, RecordBatch}; use datafusion::arrow::datatypes::{DataType, Field, Schema, SchemaRef, i256}; use datafusion::catalog::streaming::StreamingTable; use datafusion::common::ScalarValue; use datafusion::functions_aggregate::expr_fn::max; use datafusion::functions_aggregate::sum::sum_udaf; use datafusion::logical_expr::expr::WindowFunction; use datafusion::logical_expr::{ Expr, ExprFunctionExt, WindowFrame, WindowFrameBound, WindowFrameUnits, WindowFunctionDefinition, col, }; use datafusion::execution::memory_pool::FairSpillPool; use datafusion::execution::runtime_env::RuntimeEnvBuilder; use datafusion::execution::{SendableRecordBatchStream, TaskContext}; use datafusion::physical_plan::stream::RecordBatchStreamAdapter; use datafusion::physical_plan::streaming::PartitionStream; use datafusion::prelude::{SessionConfig, SessionContext}; const ROWS: i32 = 6_666_815; const BATCH: i32 = 8192; const POOL: usize = 65_484_800; // 62.5 MB /// (g, k, p): 1000 groups of increasing k, with a decimal to sum. #[derive(Debug)] struct Gen(SchemaRef); impl PartitionStream for Gen { fn schema(&self) -> &SchemaRef { &self.0 } fn execute(&self, _: Arc<TaskContext>) -> SendableRecordBatchStream { let schema = Arc::clone(&self.0); let s = Arc::clone(&schema); let batches = (0..(ROWS + BATCH - 1) / BATCH).map(move |b| { let (lo, hi) = (b * BATCH, ((b + 1) * BATCH).min(ROWS)); let k: Vec<i32> = (lo..hi).map(|i| i * 3).collect(); let g: Vec<i32> = k.iter().map(|k| k % 1000).collect(); let p: Vec<i256> = k .iter() .map(|k| i256::from_i128((*k as i128 * 7919) % 10_000_000)) .collect(); let p = Decimal256Array::from(p).with_precision_and_scale(76, 2)?; Ok(RecordBatch::try_new( Arc::clone(&s), vec![ Arc::new(Int32Array::from(g)), Arc::new(Int32Array::from(k)), Arc::new(p), ], )?) }); Box::pin(RecordBatchStreamAdapter::new( schema, futures::stream::iter(batches), )) } } async fn run(sort_spill_reservation_bytes: usize) -> datafusion::error::Result<()> { let mut config = SessionConfig::new() .with_target_partitions(10) .with_batch_size(BATCH as usize); config.options_mut().execution.sort_spill_reservation_bytes = sort_spill_reservation_bytes; let runtime = RuntimeEnvBuilder::new() .with_memory_pool(Arc::new(FairSpillPool::new(POOL))) .build_arc()?; let ctx = SessionContext::new_with_config_rt(config, runtime); let schema = Arc::new(Schema::new(vec![ Field::new("g", DataType::Int32, false), Field::new("k", DataType::Int32, false), Field::new("p", DataType::Decimal256(76, 2), false), ])); let table = StreamingTable::try_new( Arc::clone(&schema), vec![Arc::new(Gen(schema))], )?; // SELECT max(s) FROM (SELECT sum(p) OVER (PARTITION BY g ORDER BY k // ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS s FROM t) let s = Expr::from(WindowFunction::new( WindowFunctionDefinition::AggregateUDF(sum_udaf()), vec![col("p")], )) .partition_by(vec![col("g")]) .order_by(vec![col("k").sort(true, false)]) .window_frame(WindowFrame::new_bounds( WindowFrameUnits::Rows, WindowFrameBound::Preceding(ScalarValue::UInt64(None)), WindowFrameBound::CurrentRow, )) .build()? .alias("s"); ctx.read_table(Arc::new(table))? .window(vec![s])? .aggregate(vec![], vec![max(col("s"))])? .collect() .await?; Ok(()) } fn main() { let args: Vec<String> = std::env::args().collect(); let reservation: usize = args[1].parse().unwrap(); let runs: usize = args[2].parse().unwrap(); let rt = tokio::runtime::Builder::new_multi_thread() .worker_threads(10) .enable_all() .build() .unwrap(); let mut ok = 0; for _ in 0..runs { match rt.block_on(run(reservation)) { Ok(()) => ok += 1, Err(e) => println!("{e}"), } } println!("sort_spill_reservation_bytes={reservation}: {ok} / {runs} succeeded"); } ``` </details> ## Are there any user-facing changes? No API changes. A sort that spills to many runs may merge in more passes when the pool is shared, instead of failing other consumers of the pool.
1 parent 6c42917 commit adffd19

4 files changed

Lines changed: 557 additions & 9 deletions

File tree

‎datafusion/physical-plan/src/sorts/multi_level_merge.rs‎

Lines changed: 245 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ use std::task::{Context, Poll};
1515

1616
use arrow::datatypes::SchemaRef;
1717
use datafusion_common::{Result, internal_err, resources_err};
18-
use datafusion_execution::memory_pool::{MemoryReservation, MergeMemoryPool};
18+
use datafusion_execution::memory_pool::{MemoryPool, MemoryReservation, MergeMemoryPool};
1919

2020
use crate::sorts::builder::try_grow_reservation_to_at_least;
2121
use crate::sorts::sort::get_reserved_bytes_for_record_batch_size;
@@ -28,6 +28,24 @@ use datafusion_physical_expr_common::sort_expr::LexOrdering;
2828
use futures::TryStreamExt;
2929
use futures::{Stream, StreamExt};
3030

31+
/// Leave memory for others sharing the execution pool when a merge seats
32+
/// more than the minimum two runs.
33+
#[derive(Debug, Clone)]
34+
pub(crate) struct FanInHeadroom {
35+
/// The execution pool: the parent of the merge pool when there is one.
36+
pub(crate) pool: Arc<dyn MemoryPool>,
37+
/// Other partitions share `pool`, even if they hold nothing right now.
38+
pub(crate) siblings: bool,
39+
}
40+
41+
impl FanInHeadroom {
42+
/// Whether another consumer may need the pool: sibling partitions exist,
43+
/// or the pool holds more than the `owned` bytes this merge holds in it.
44+
fn is_contended(&self, owned: usize) -> bool {
45+
self.siblings || self.pool.reserved() > owned
46+
}
47+
}
48+
3149
/// Merges a stream of sorted cursors and record batches into a single sorted stream
3250
///
3351
/// This is a wrapper around [`SortPreservingMergeStream`](crate::sorts::merge::SortPreservingMergeStream)
@@ -148,6 +166,11 @@ pub(crate) struct MultiLevelMergeBuilder {
148166
merge_pool: Option<Arc<MergeMemoryPool>>,
149167
/// Leave memory for the aggregate consuming the merged spill rows.
150168
reserve_replay_headroom: bool,
169+
/// When set and the pool is shared, seat runs beyond the minimum two only
170+
/// if the pool can admit their buffers plus as much again as they exceed
171+
/// the retained workspace, so a merge does not take the memory that other
172+
/// partitions sharing the pool need.
173+
fan_in_headroom: Option<FanInHeadroom>,
151174
/// Avoid merging more runs than needed before the final replay pass.
152175
size_intermediate_merges: bool,
153176
fetch: Option<usize>,
@@ -191,6 +214,7 @@ impl MultiLevelMergeBuilder {
191214
reservation,
192215
merge_pool: None,
193216
reserve_replay_headroom: false,
217+
fan_in_headroom: None,
194218
size_intermediate_merges: false,
195219
enable_round_robin_tie_breaker,
196220
fetch,
@@ -216,6 +240,17 @@ impl MultiLevelMergeBuilder {
216240
self
217241
}
218242

243+
/// Leave headroom when seating runs beyond the minimum two while the pool
244+
/// is shared. The minimum merge is admitted against the pool alone, as
245+
/// without headroom.
246+
pub(super) fn with_fan_in_headroom(
247+
mut self,
248+
headroom: Option<FanInHeadroom>,
249+
) -> Self {
250+
self.fan_in_headroom = headroom;
251+
self
252+
}
253+
219254
pub(super) fn with_intermediate_merge_sizing(
220255
mut self,
221256
min_spill_batch_rows: Option<usize>,
@@ -584,6 +619,20 @@ impl MultiLevelMergeBuilder {
584619
// allocation, preventing starvation under memory pressure.
585620
let mut total_needed: usize = 0;
586621
let mut accepted_memory: usize = 0;
622+
// What this merge already holds from the pool: its retained workspace
623+
// when it has one. Seating runs within it takes nothing from others.
624+
let owned = self
625+
.merge_pool
626+
.as_ref()
627+
.map_or_else(|| reservation.size(), |pool| pool.reserved());
628+
// Headroom is for others sharing the pool. With no sibling partitions
629+
// and nobody else holding memory in it, seat every run that fits, as
630+
// without headroom, rather than rewrite runs in an extra merge pass
631+
// for no one.
632+
let fan_in_contended = self
633+
.fan_in_headroom
634+
.as_ref()
635+
.is_some_and(|headroom| headroom.is_contended(owned));
587636

588637
for (spill, _) in &self.sorted_spill_files {
589638
if number_of_spills_to_read_for_current_phase >= max_spill_files
@@ -609,7 +658,20 @@ impl MultiLevelMergeBuilder {
609658
&& number_of_spills_to_read_for_current_phase
610659
< minimum_number_of_required_streams;
611660
let check_headroom = self.reserve_replay_headroom && !skip_headroom;
612-
let admission = if check_headroom {
661+
let check_fan_in_headroom = !check_headroom
662+
&& fan_in_contended
663+
&& number_of_spills_to_read_for_current_phase
664+
>= minimum_number_of_required_streams;
665+
let admission = if check_fan_in_headroom {
666+
// Ask the pool for what this merge takes beyond its own
667+
// workspace, plus as much again, then return the spare bytes.
668+
match total_needed.checked_add(total_needed.saturating_sub(owned)) {
669+
Some(with_headroom) => {
670+
try_grow_reservation_to_at_least(reservation, with_headroom)
671+
}
672+
None => resources_err!("Spill merge headroom exceeds usize::MAX"),
673+
}
674+
} else if check_headroom {
613675
// Ask the pool for merge buffers plus equal replay space, then
614676
// return the spare bytes before exposing the merge stream.
615677
match total_needed.checked_mul(2) {
@@ -677,7 +739,7 @@ impl MultiLevelMergeBuilder {
677739
}
678740
}
679741

680-
if self.reserve_replay_headroom {
742+
if self.reserve_replay_headroom || fan_in_contended {
681743
// `total_needed` may include a rejected candidate. Keep only the
682744
// buffers that were admitted, releasing temporary replay headroom.
683745
reservation.shrink(reservation.size() - accepted_memory);
@@ -977,7 +1039,7 @@ mod tests {
9771039
use arrow::compute::concat_batches;
9781040
use arrow::datatypes::{DataType, Field, Int64Type, Schema};
9791041
use datafusion_execution::memory_pool::{
980-
GreedyMemoryPool, MemoryConsumer, MemoryPool,
1042+
GreedyMemoryPool, MemoryConsumer, MemoryPool, UnboundedMemoryPool,
9811043
};
9821044
use datafusion_execution::runtime_env::{RuntimeEnv, RuntimeEnvBuilder};
9831045
use datafusion_physical_expr::expressions::{Column, col};
@@ -1474,6 +1536,185 @@ mod tests {
14741536
Ok(())
14751537
}
14761538

1539+
/// Registers a consumer holding `size` bytes of `pool`, so a merge sharing
1540+
/// it sees another user and leaves headroom.
1541+
fn hold(pool: &Arc<dyn MemoryPool>, size: usize) -> Result<MemoryReservation> {
1542+
let other = MemoryConsumer::new("other consumer").register(pool);
1543+
other.try_grow(size)?;
1544+
Ok(other)
1545+
}
1546+
1547+
/// Headroom for others sharing `pool`, with or without sibling partitions.
1548+
fn headroom(pool: &Arc<dyn MemoryPool>, siblings: bool) -> FanInHeadroom {
1549+
FanInHeadroom {
1550+
pool: Arc::clone(pool),
1551+
siblings,
1552+
}
1553+
}
1554+
1555+
#[rstest::rstest]
1556+
#[case::without_headroom(false, true, false, 4, 8)]
1557+
#[case::headroom_without_others(true, false, false, 4, 8)]
1558+
#[case::headroom_with_others(true, true, false, 3, 6)]
1559+
#[case::headroom_with_idle_siblings(true, false, true, 3, 6)]
1560+
fn fan_in_headroom_limits_runs_beyond_the_minimum(
1561+
#[case] with_headroom: bool,
1562+
#[case] others: bool,
1563+
#[case] siblings: bool,
1564+
#[case] seated: usize,
1565+
#[case] retained_batches: usize,
1566+
) -> Result<()> {
1567+
let env = Arc::new(RuntimeEnv::default());
1568+
let schema = test_schema();
1569+
let spill_manager = build_spill_manager(&env, &schema);
1570+
let spills = (0..4)
1571+
.map(|value| make_sorted_spill_file(&spill_manager, &schema, vec![value]))
1572+
.collect::<Vec<_>>();
1573+
let batch_memory = spills[0].max_record_batch_memory;
1574+
let pool: Arc<dyn MemoryPool> =
1575+
Arc::new(GreedyMemoryPool::new(13 * batch_memory));
1576+
let other = others.then(|| hold(&pool, 1)).transpose()?;
1577+
let mut builder = build_merge_builder(spill_manager, schema, spills, &pool, 1)
1578+
.with_fan_in_headroom(with_headroom.then(|| headroom(&pool, siblings)));
1579+
let mut reservation = builder.reservation.new_empty();
1580+
let SpillFilesToMerge::Ready(spills, buffer_len) =
1581+
builder.get_sorted_spill_files_to_merge(1, 2, &mut reservation, false)?
1582+
else {
1583+
panic!("the minimum merge should fit the pool");
1584+
};
1585+
assert_eq!(buffer_len, 1);
1586+
// Each run takes two batches. With headroom, the third run needs 12
1587+
// batches and is seated; the fourth needs 16 and is not. When nobody
1588+
// else holds memory and there are no sibling partitions, all four are
1589+
// seated, as without headroom.
1590+
assert_eq!(spills.len(), seated);
1591+
assert_eq!(reservation.size(), retained_batches * batch_memory);
1592+
drop((reservation, spills, builder, other));
1593+
assert_eq!(pool.reserved(), 0);
1594+
Ok(())
1595+
}
1596+
1597+
/// The minimum two runs are admitted against the pool alone, even when
1598+
/// their buffers plus headroom would not fit.
1599+
#[test]
1600+
fn fan_in_headroom_admits_the_minimum_merge_without_headroom() -> Result<()> {
1601+
let env = Arc::new(RuntimeEnv::default());
1602+
let schema = test_schema();
1603+
let spill_manager = build_spill_manager(&env, &schema);
1604+
let spills = (0..3)
1605+
.map(|value| make_sorted_spill_file(&spill_manager, &schema, vec![value]))
1606+
.collect::<Vec<_>>();
1607+
let batch_memory = spills[0].max_record_batch_memory;
1608+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(5 * batch_memory));
1609+
let other = hold(&pool, 1)?;
1610+
let mut builder = build_merge_builder(spill_manager, schema, spills, &pool, 1)
1611+
.with_fan_in_headroom(Some(headroom(&pool, false)));
1612+
let mut reservation = builder.reservation.new_empty();
1613+
let SpillFilesToMerge::Ready(spills, _) =
1614+
builder.get_sorted_spill_files_to_merge(1, 2, &mut reservation, false)?
1615+
else {
1616+
panic!("the minimum merge should fit the pool");
1617+
};
1618+
// Two runs take four batches; with headroom they would take eight. The
1619+
// third would take twelve.
1620+
assert_eq!(spills.len(), 2);
1621+
assert_eq!(reservation.size(), 4 * batch_memory);
1622+
drop((reservation, spills, builder, other));
1623+
assert_eq!(pool.reserved(), 0);
1624+
Ok(())
1625+
}
1626+
1627+
/// With a retained workspace `W`, seating the third run, for buffers `T`
1628+
/// in all, asks the parent for `2 * (T - W)` more, and nothing when
1629+
/// `T <= W`. Afterwards the child holds `T` and the parent is charged
1630+
/// `max(W, T)`.
1631+
#[rstest::rstest]
1632+
#[case::runs_within_workspace(6, 0, 0, 3)]
1633+
#[case::runs_below_workspace(8, 0, 0, 3)]
1634+
#[case::exactly_the_headroom(2, 8, 0, 3)]
1635+
#[case::just_below_the_headroom(2, 8, 1, 2)]
1636+
fn fan_in_headroom_counts_the_retained_workspace(
1637+
#[case] workspace_batches: usize,
1638+
#[case] free_batches: usize,
1639+
#[case] short_by_bytes: usize,
1640+
#[case] seated: usize,
1641+
) -> Result<()> {
1642+
let env = Arc::new(RuntimeEnv::default());
1643+
let schema = test_schema();
1644+
let spill_manager = build_spill_manager(&env, &schema);
1645+
let spills = (0..3)
1646+
.map(|value| make_sorted_spill_file(&spill_manager, &schema, vec![value]))
1647+
.collect::<Vec<_>>();
1648+
let batch_memory = spills[0].max_record_batch_memory;
1649+
let per_run =
1650+
get_reserved_bytes_for_record_batch_size(batch_memory, batch_memory);
1651+
assert_eq!(per_run, 2 * batch_memory);
1652+
let workspace = workspace_batches * batch_memory;
1653+
let free = free_batches * batch_memory - short_by_bytes;
1654+
let capacity = 32 * batch_memory;
1655+
let parent: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(capacity));
1656+
let merge_pool = Arc::new(MergeMemoryPool::new(
1657+
Arc::clone(&parent),
1658+
MemoryConsumer::new("merge workspace"),
1659+
));
1660+
let pool: Arc<dyn MemoryPool> = Arc::clone(&merge_pool) as Arc<dyn MemoryPool>;
1661+
let mut builder = build_merge_builder(spill_manager, schema, spills, &pool, 1)
1662+
.with_merge_pool(Some(Arc::clone(&merge_pool)))
1663+
.with_fan_in_headroom(Some(headroom(&parent, false)));
1664+
builder.reservation.try_grow(workspace)?;
1665+
merge_pool.retain(workspace);
1666+
builder.reservation.free();
1667+
assert_eq!(merge_pool.reserved(), workspace);
1668+
let other = hold(&parent, capacity - workspace - free)?;
1669+
1670+
let mut reservation = builder.reservation.new_empty();
1671+
let SpillFilesToMerge::Ready(spills, _) =
1672+
builder.get_sorted_spill_files_to_merge(1, 2, &mut reservation, false)?
1673+
else {
1674+
panic!("the minimum merge should fit the pool");
1675+
};
1676+
assert_eq!(spills.len(), seated);
1677+
let total = seated * per_run;
1678+
assert_eq!(reservation.size(), total);
1679+
assert_eq!(merge_pool.reserved(), workspace.max(total));
1680+
assert_eq!(parent.reserved(), other.size() + workspace.max(total));
1681+
drop((reservation, spills, builder, other));
1682+
merge_pool.release_unused();
1683+
assert_eq!(parent.reserved(), 0);
1684+
Ok(())
1685+
}
1686+
1687+
#[test]
1688+
fn fan_in_headroom_beyond_usize_stops_seating_runs() -> Result<()> {
1689+
let env = Arc::new(RuntimeEnv::default());
1690+
let schema = test_schema();
1691+
let spill_manager = build_spill_manager(&env, &schema);
1692+
// Three runs whose buffers fit in a usize, but whose headroom for the
1693+
// third does not.
1694+
let batch_memory = usize::MAX / 10;
1695+
let spills = (0..3)
1696+
.map(|value| SortedSpillFile {
1697+
max_record_batch_memory: batch_memory,
1698+
..make_sorted_spill_file(&spill_manager, &schema, vec![value])
1699+
})
1700+
.collect::<Vec<_>>();
1701+
let pool: Arc<dyn MemoryPool> = Arc::new(UnboundedMemoryPool::default());
1702+
let other = hold(&pool, 1)?;
1703+
let mut builder = build_merge_builder(spill_manager, schema, spills, &pool, 1)
1704+
.with_fan_in_headroom(Some(headroom(&pool, false)));
1705+
let mut reservation = builder.reservation.new_empty();
1706+
let SpillFilesToMerge::Ready(spills, _) =
1707+
builder.get_sorted_spill_files_to_merge(1, 2, &mut reservation, false)?
1708+
else {
1709+
panic!("the minimum merge should fit an unbounded pool");
1710+
};
1711+
assert_eq!(spills.len(), 2);
1712+
assert_eq!(reservation.size(), 4 * batch_memory);
1713+
drop((reservation, spills, builder, other));
1714+
assert_eq!(pool.reserved(), 0);
1715+
Ok(())
1716+
}
1717+
14771718
#[tokio::test]
14781719
async fn replay_headroom_still_enforces_the_actual_pool() -> Result<()> {
14791720
let env = Arc::new(RuntimeEnv::default());

0 commit comments

Comments
 (0)