Skip to content

Commit 0646a31

Browse files
fix: reduce peak memory usage when round robin tiebreaker is disabled (apache#23606)
## Which issue does this PR close? - First part of apache#23604 ## Rationale for this change Don't pay the memory price when the tie breaking feature is disabled. ## What changes are included in this PR? Mostly tests to show the issue ## Are these changes tested? Yes ## Are there any user-facing changes? No
1 parent 1a18915 commit 0646a31

11 files changed

Lines changed: 323 additions & 66 deletions

File tree

‎Cargo.lock‎

Lines changed: 0 additions & 2 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎benchmarks/Cargo.toml‎

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -65,11 +65,6 @@ tokio-util = { version = "0.7.17" }
6565
toml = "0.9.8"
6666

6767
[dev-dependencies]
68-
# `pool`/`arrow_buffer_pool` are enabled only for tests, so the benchmark
69-
# binaries are built exactly as before. They let `memory_pool`'s tests cover
70-
# Arrow-side reservations reaching the pool via `ArrowMemoryPool`.
71-
arrow-buffer = { workspace = true, features = ["pool"] }
72-
datafusion-execution = { workspace = true, features = ["arrow_buffer_pool"] }
7368
datafusion-proto = { workspace = true, features = ["parquet"] }
7469
tempfile = { workspace = true }
7570

‎benchmarks/src/bin/external_aggr.rs‎

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -34,14 +34,12 @@ use datafusion::datasource::listing::{
3434
use datafusion::datasource::{MemTable, TableProvider};
3535
use datafusion::error::Result;
3636
use datafusion::execution::SessionStateBuilder;
37-
use datafusion::execution::memory_pool::FairSpillPool;
37+
use datafusion::execution::memory_pool::{FairSpillPool, PeakRecordingPool};
3838
use datafusion::execution::runtime_env::RuntimeEnvBuilder;
3939
use datafusion::physical_plan::display::DisplayableExecutionPlan;
4040
use datafusion::physical_plan::{collect, displayable};
4141
use datafusion::prelude::*;
42-
use datafusion_benchmarks::util::{
43-
BenchmarkRun, CommonOpt, PeakRecordingPool, QueryResult,
44-
};
42+
use datafusion_benchmarks::util::{BenchmarkRun, CommonOpt, QueryResult};
4543
use datafusion_common::instant::Instant;
4644
use datafusion_common::utils::get_available_parallelism;
4745
use datafusion_common::{DEFAULT_PARQUET_EXTENSION, exec_err};

‎benchmarks/src/util/memory.rs‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -15,9 +15,7 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
use datafusion::execution::memory_pool::MemoryPool;
19-
20-
use super::PeakRecordingPool;
18+
use datafusion::execution::memory_pool::{MemoryPool, PeakRecordingPool};
2119

2220
/// Print Peak RSS, Peak Commit, Page Faults based on mimalloc api, followed by
2321
/// the peak reservation of `memory_pool` when a memory limit was configured.

‎benchmarks/src/util/mod.rs‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,11 +18,9 @@
1818
//! Shared benchmark utilities
1919
pub mod latency_object_store;
2020
mod memory;
21-
mod memory_pool;
2221
mod options;
2322
mod run;
2423

2524
pub use memory::print_memory_stats;
26-
pub use memory_pool::PeakRecordingPool;
2725
pub use options::CommonOpt;
2826
pub use run::{BenchQuery, BenchmarkRun, QueryResult};

‎benchmarks/src/util/options.rs‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,10 @@ use clap::Args;
2121
use datafusion::{
2222
execution::{
2323
disk_manager::DiskManagerBuilder,
24-
memory_pool::{FairSpillPool, GreedyMemoryPool, MemoryPool, TrackConsumersPool},
24+
memory_pool::{
25+
FairSpillPool, GreedyMemoryPool, MemoryPool, PeakRecordingPool,
26+
TrackConsumersPool,
27+
},
2528
object_store::ObjectStoreUrl,
2629
runtime_env::{RuntimeEnv, RuntimeEnvBuilder},
2730
},
@@ -30,7 +33,7 @@ use datafusion::{
3033
use datafusion_common::{DataFusionError, Result};
3134
use object_store::local::LocalFileSystem;
3235

33-
use super::{latency_object_store::LatencyObjectStore, memory_pool::PeakRecordingPool};
36+
use super::latency_object_store::LatencyObjectStore;
3437

3538
// Common benchmark options (don't use doc comments otherwise this doc
3639
// shows up in help files)

‎benchmarks/src/util/run.rs‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,7 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
use super::memory_pool::PeakRecordingPool;
19-
use datafusion::execution::memory_pool::MemoryPool;
18+
use datafusion::execution::memory_pool::{MemoryPool, PeakRecordingPool};
2019
use datafusion::{DATAFUSION_VERSION, error::Result};
2120
use datafusion_common::utils::get_available_parallelism;
2221
use serde::{Serialize, Serializer};

‎datafusion/core/tests/fuzz_cases/spilling_fuzz_in_memory_constrained_env.rs‎

Lines changed: 255 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ use std::sync::Arc;
2323
use crate::fuzz_cases::aggregate_fuzz::assert_spill_count_metric;
2424
use crate::fuzz_cases::once_exec::OnceExec;
2525
use arrow::array::UInt64Array;
26+
use arrow::row::{RowConverter, SortField};
2627
use arrow::{array::StringArray, compute::SortOptions, record_batch::RecordBatch};
2728
use arrow_schema::{DataType, Field, Schema};
2829
use datafusion::common::Result;
@@ -45,9 +46,19 @@ use datafusion_physical_plan::aggregates::{
4546
AggregateExec, AggregateMode, PhysicalGroupBy,
4647
};
4748
use datafusion_physical_plan::metrics::MetricValue;
49+
use datafusion_physical_plan::spill::get_record_batch_memory_size;
4850
use datafusion_physical_plan::stream::RecordBatchStreamAdapter;
4951
use futures::StreamExt;
5052

53+
use arrow::array::Int32Array;
54+
use datafusion::datasource::memory::MemorySourceConfig;
55+
use datafusion::physical_plan::sorts::sort_preserving_merge::SortPreservingMergeExec;
56+
use datafusion_execution::memory_pool::{
57+
MemoryPool, PeakRecordingPool, UnboundedMemoryPool,
58+
};
59+
use datafusion_physical_plan::metrics::{ExecutionPlanMetricsSet, SpillMetrics};
60+
use datafusion_physical_plan::spill::SpillManager;
61+
5162
#[tokio::test]
5263
async fn test_sort_with_limited_memory() -> Result<()> {
5364
let record_batch_size = 8192;
@@ -290,6 +301,250 @@ async fn test_sort_with_limited_memory_and_oversized_record_batch() -> Result<()
290301
Ok(())
291302
}
292303

304+
#[tokio::test]
305+
async fn test_sort_preserving_merge_peak_memory_with_spilled_input_round_robin()
306+
-> Result<()> {
307+
run_sort_preserving_merge_peak_memory_with_spilled_input(true, false, false).await
308+
}
309+
310+
#[tokio::test]
311+
async fn test_sort_preserving_merge_peak_memory_with_spilled_input_no_round_robin()
312+
-> Result<()> {
313+
run_sort_preserving_merge_peak_memory_with_spilled_input(false, false, false).await
314+
}
315+
316+
#[tokio::test]
317+
async fn test_sort_preserving_merge_peak_memory_with_spilled_input_round_robin_multi_column()
318+
-> Result<()> {
319+
run_sort_preserving_merge_peak_memory_with_spilled_input(true, true, false).await
320+
}
321+
322+
#[tokio::test]
323+
async fn test_sort_preserving_merge_peak_memory_with_spilled_input_no_round_robin_multi_column()
324+
-> Result<()> {
325+
run_sort_preserving_merge_peak_memory_with_spilled_input(false, true, false).await
326+
}
327+
328+
#[tokio::test]
329+
async fn test_sort_preserving_merge_peak_memory_with_spilled_input_round_robin_tied_values()
330+
-> Result<()> {
331+
run_sort_preserving_merge_peak_memory_with_spilled_input(true, false, true).await
332+
}
333+
334+
#[tokio::test]
335+
async fn test_sort_preserving_merge_peak_memory_with_spilled_input_no_round_robin_tied_values()
336+
-> Result<()> {
337+
run_sort_preserving_merge_peak_memory_with_spilled_input(false, false, true).await
338+
}
339+
340+
/// Intended to measure the maximum number of record batches held in memory by
341+
/// the SortPreservingMergeStream in a convoluted way by measuring the peak
342+
/// memory reservation. Relevant for merging spilled streams, where the produced
343+
/// record batches suffer from the following issue:
344+
/// https://github.com/apache/arrow-rs/issues/6363
345+
///
346+
/// After an IPC roundtrip, all columns in a [`RecordBatch`] share a single
347+
/// parent buffer. It causes the memory reservation to be inflated, but the
348+
/// bigger issue is the increase in the peak allocated memory caused by
349+
/// prev_cursors in SortPreservingMergeExec. The increase is caused by the fact
350+
/// that the FieldCursor inside prev_cursors holds a reference for the entire
351+
/// Buffer allocated for the input record batch, preventing it from being
352+
/// dropped and thus increasing the number of concomitent input record batches
353+
/// living during the merging phase
354+
async fn run_sort_preserving_merge_peak_memory_with_spilled_input(
355+
round_robin: bool,
356+
multi_column_sort: bool,
357+
tied_values: bool,
358+
) -> Result<()> {
359+
let num_batches = 10usize;
360+
let num_rows_per_batch = 100usize;
361+
// payload is ~100x larger than the sort key (i32 = 4 bytes, string ≈ 400 bytes)
362+
let large_string = "x".repeat(400);
363+
364+
let schema = Arc::new(Schema::new(vec![
365+
Field::new("sort_key", DataType::Int32, false),
366+
Field::new("payload", DataType::Utf8, false),
367+
]));
368+
369+
// Unbounded env used only for spilling the input; the merge runs under its
370+
// own pool below.
371+
let spill_env = Arc::new(RuntimeEnvBuilder::new().build()?);
372+
373+
let mut partition_batches: Vec<Vec<RecordBatch>> = Vec::new();
374+
375+
for stream_idx in 0..2usize {
376+
// Each stream covers a non-overlapping key range so both are individually
377+
// sorted: stream 0 → [0, 1000), stream 1 → [1000, 2000). When
378+
// `tied_values` is set, every row of every batch in both streams
379+
// instead carries the same sort key, so every comparison between the
380+
// two streams is a tie.
381+
let batches: Vec<RecordBatch> = (0..num_batches)
382+
.map(|b| {
383+
// Interleave streams: stream 0 → even slots [0,200,400,...],
384+
// stream 1 → odd slots [100,300,500,...] so the merge
385+
// alternates between them on every batch.
386+
let base = ((b * 2 + stream_idx) * num_rows_per_batch) as i32;
387+
let sort_col: Int32Array = if tied_values {
388+
std::iter::repeat_n(0, num_rows_per_batch).collect()
389+
} else {
390+
(base..base + num_rows_per_batch as i32).collect()
391+
};
392+
let payload_col: StringArray =
393+
std::iter::repeat_n(large_string.as_str(), num_rows_per_batch)
394+
.map(Some)
395+
.collect();
396+
RecordBatch::try_new(
397+
Arc::clone(&schema),
398+
vec![Arc::new(sort_col), Arc::new(payload_col)],
399+
)
400+
.unwrap()
401+
})
402+
.collect();
403+
404+
// Spill to disk then read back: each RecordBatch is now IPC-backed,
405+
// meaning all columns share a single parent buffer. As a result,
406+
// get_buffer_memory_size() on the sort_key column returns the full
407+
// parent-buffer capacity (≈ batch size of both columns combined) rather
408+
// than just the key data (num_rows * 4 bytes).
409+
let metrics = SpillMetrics::new(&ExecutionPlanMetricsSet::new(), 0);
410+
let manager =
411+
SpillManager::new(Arc::clone(&spill_env), metrics, Arc::clone(&schema));
412+
let spill_file = manager
413+
.spill_record_batch_and_finish(&batches, "stream")?
414+
.expect("non-empty input should produce a spill file");
415+
416+
let mut stream = manager.read_spill_as_stream(spill_file, None)?;
417+
let mut ipc_batches: Vec<RecordBatch> = Vec::new();
418+
while let Some(batch) = stream.next().await {
419+
ipc_batches.push(batch?);
420+
}
421+
partition_batches.push(ipc_batches);
422+
}
423+
424+
let ipc_batch_size = get_record_batch_memory_size(&partition_batches[0][0]);
425+
426+
// Build a 2-partition plan from the IPC-recovered batches.
427+
let input =
428+
MemorySourceConfig::try_new_exec(&partition_batches, Arc::clone(&schema), None)?;
429+
430+
let sort_key_expr = PhysicalSortExpr {
431+
expr: col("sort_key", &schema)?,
432+
options: SortOptions {
433+
descending: false,
434+
nulls_first: true,
435+
},
436+
};
437+
// `payload` has the same value in every row, so adding it as a secondary
438+
// sort key doesn't change the resulting order — it only forces the merge
439+
// onto the row-oriented (`RowValues`/`RowCursorStream`) comparison path
440+
// used whenever more than one sort expression is present.
441+
let mut sort_exprs = vec![sort_key_expr];
442+
if multi_column_sort {
443+
sort_exprs.push(PhysicalSortExpr {
444+
expr: col("payload", &schema)?,
445+
options: SortOptions {
446+
descending: false,
447+
nulls_first: true,
448+
},
449+
});
450+
}
451+
452+
// When sorting by more than one column, the merge switches to the
453+
// row-oriented `RowValues`/`RowCursorStream` path
454+
//
455+
// `RowCursorStream` also tracks one *shared* (not per-partition)
456+
// reservation sized to `converter.size()` (`stream.rs`:
457+
// `self.reservation.try_resize(self.converter.size())`) — the
458+
// `RowConverter`'s own fixed internal state, separate from the `Rows`
459+
// it produces per batch.
460+
let (row_batch_size, converter_size) = if multi_column_sort {
461+
let sort_fields = sort_exprs
462+
.iter()
463+
.map(|s| {
464+
let data_type = s.expr.data_type(&schema)?;
465+
Ok(SortField::new_with_options(data_type, s.options))
466+
})
467+
.collect::<Result<Vec<_>>>()?;
468+
let converter = RowConverter::new(sort_fields)?;
469+
let cols = sort_exprs
470+
.iter()
471+
.map(|s| {
472+
s.expr
473+
.evaluate(&partition_batches[0][0])?
474+
.into_array(partition_batches[0][0].num_rows())
475+
})
476+
.collect::<Result<Vec<_>>>()?;
477+
let rows = converter.convert_columns(&cols)?;
478+
(rows.size(), converter.size())
479+
} else {
480+
(0, 0)
481+
};
482+
483+
let merge = Arc::new(
484+
SortPreservingMergeExec::new(LexOrdering::new(sort_exprs).unwrap(), input)
485+
.with_round_robin_repartition(round_robin),
486+
);
487+
488+
// PeakRecordingPool records peak reserved bytes as a running high-water mark
489+
// (via grow/shrink deltas), independent of any per-consumer registration
490+
// bookkeeping - unlike TrackConsumersPool, whose tracked-consumer entry (and
491+
// its peak) gets discarded the moment the consumer unregisters, which now
492+
// happens mid-poll (inside the drain loop below) rather than when the
493+
// caller eventually drops the returned stream.
494+
let tracking_pool = Arc::new(PeakRecordingPool::new(Arc::new(
495+
UnboundedMemoryPool::default(),
496+
)));
497+
let runtime = RuntimeEnvBuilder::new()
498+
.with_memory_pool(Arc::clone(&tracking_pool) as Arc<dyn MemoryPool>)
499+
.build()?;
500+
let task_ctx = Arc::new(
501+
TaskContext::default()
502+
.with_session_config(SessionConfig::new().with_batch_size(num_rows_per_batch))
503+
.with_runtime(Arc::new(runtime)),
504+
);
505+
506+
let mut output = merge.execute(0, task_ctx)?;
507+
let mut total_rows = 0usize;
508+
while let Some(batch) = output.next().await {
509+
total_rows += batch?.num_rows();
510+
}
511+
assert_eq!(total_rows, 2 * num_batches * num_rows_per_batch);
512+
513+
let peak_bytes = tracking_pool.peak_reserved();
514+
515+
// in the single column case, the cursor takes up an ipc_batch_size worth of memory due to the
516+
// IPC roundtrip issue
517+
// for the multi-column case, we've calculated row_batch_size above
518+
let cursor_unit = if multi_column_sort {
519+
row_batch_size
520+
} else {
521+
ipc_batch_size
522+
};
523+
524+
// BatchBuilder needs to hold 3 Record batches simultaneously to merge two
525+
// streams (because a stream can cross a record batch boundary)
526+
// there is also one cursor needed per stream
527+
let mut max_peak = 3 * ipc_batch_size + 2 * cursor_unit + converter_size;
528+
529+
// with round robin enabled, 2 extra cursors live in memory
530+
// see https://github.com/apache/datafusion/issues/23604
531+
if round_robin {
532+
max_peak += 2 * cursor_unit;
533+
};
534+
535+
assert!(
536+
peak_bytes > 0,
537+
"peak reservation {peak_bytes} should be greater than 0"
538+
);
539+
assert!(
540+
peak_bytes <= max_peak,
541+
"peak reservation {peak_bytes} bytes exceeds max_peak ({max_peak} bytes); \
542+
round_robin={round_robin}, multi_column_sort={multi_column_sort}",
543+
);
544+
545+
Ok(())
546+
}
547+
293548
struct RunTestWithLimitedMemoryArgs {
294549
pool_size: usize,
295550
task_ctx: Arc<TaskContext>,

‎datafusion/execution/src/memory_pool/mod.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,7 @@ use std::fmt::Display;
2424
use std::hash::{Hash, Hasher};
2525
use std::{cmp::Ordering, sync::Arc, sync::atomic};
2626

27+
mod peak_recording;
2728
mod pool;
2829

2930
#[cfg(feature = "arrow_buffer_pool")]
@@ -36,6 +37,7 @@ pub mod proxy {
3637
pub use datafusion_common::{
3738
human_readable_count, human_readable_duration, human_readable_size, units,
3839
};
40+
pub use peak_recording::*;
3941
pub use pool::*;
4042

4143
/// Tracks and potentially limits memory use across operators during execution.

0 commit comments

Comments
 (0)