Skip to content

Commit 1659313

Browse files
committed
Compact the build side only after it is fully reserved and keep spilled and replayed batches as they arrived so the memory-limited path never copies a pass
1 parent a886459 commit 1659313

2 files changed

Lines changed: 249 additions & 38 deletions

File tree

‎datafusion/physical-plan/src/joins/nested_loop_join.rs‎

Lines changed: 21 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1204,8 +1204,7 @@ async fn collect_left_input(
12041204
) -> Result<LeftLoad> {
12051205
let schema = stream.schema();
12061206
let metrics = join_metrics;
1207-
let mut chunks: Vec<RecordBatch> = Vec::new();
1208-
let mut coalescer = chunk_coalescer(&schema, target_batch_size);
1207+
let mut batches: Vec<RecordBatch> = Vec::new();
12091208

12101209
while let Some(batch) = stream.next().await {
12111210
let batch = batch?;
@@ -1216,10 +1215,7 @@ async fn collect_left_input(
12161215
metrics.build_mem_used.add(batch_size);
12171216
metrics.build_input_batches.add(1);
12181217
metrics.build_input_rows.add(batch.num_rows());
1219-
coalescer.push_batch(batch)?;
1220-
while let Some(chunk) = coalescer.next_completed_batch() {
1221-
chunks.push(chunk);
1222-
}
1218+
batches.push(batch);
12231219
}
12241220
Err(e) if is_spillable_oom(&e, spill_manager.as_ref()) => {
12251221
// Do not keep the operator timer running while the spill path
@@ -1228,14 +1224,10 @@ async fn collect_left_input(
12281224
let spill_manager = spill_manager.expect("checked by is_spillable_oom");
12291225
metrics.build_input_batches.add(1);
12301226
metrics.build_input_rows.add(batch.num_rows());
1231-
coalescer.finish_buffered_batch()?;
1232-
while let Some(chunk) = coalescer.next_completed_batch() {
1233-
chunks.push(chunk);
1234-
}
12351227
let spilled = spill_left_input(
12361228
spill_manager,
12371229
Arc::clone(&schema),
1238-
chunks,
1230+
batches,
12391231
Some(batch),
12401232
stream,
12411233
metrics,
@@ -1257,10 +1249,9 @@ async fn collect_left_input(
12571249
// polling the child stream above.
12581250
let build_timer = metrics.build_time.timer();
12591251

1260-
coalescer.finish_buffered_batch()?;
1261-
while let Some(chunk) = coalescer.next_completed_batch() {
1262-
chunks.push(chunk);
1263-
}
1252+
// Compacted only once the whole side is reserved, so a load that spills never has a
1253+
// partially built chunk to materialize while the pool is exhausted.
1254+
let chunks = coalesce_chunks(batches, &schema, target_batch_size)?;
12641255

12651256
// Reserve memory for visited_left_side bitmap if required by join type
12661257
let visited_left_side = if with_visited_left_side {
@@ -1342,21 +1333,16 @@ fn is_spillable_oom(
13421333
)
13431334
}
13441335

1345-
/// Chunks are `target_batch_size` rows; a batch already at or above half that passes through
1346-
/// without being copied.
1347-
fn chunk_coalescer(schema: &SchemaRef, target_batch_size: usize) -> BatchCoalescer {
1348-
BatchCoalescer::new(Arc::clone(schema), target_batch_size)
1349-
.with_biggest_coalesce_batch_size(Some(target_batch_size / 2))
1350-
}
1351-
1352-
/// Compacts already-buffered batches into chunks. Every input must be reserved by the caller:
1353-
/// the copy this makes is bounded by the input, so the pass that reserved it bounds the copy.
1336+
/// Compacts a fully buffered build side into `target_batch_size`-row chunks; a batch already at
1337+
/// or above half that passes through without being copied. Concatenation completes one chunk at
1338+
/// a time, so the unreserved copy in flight is at most one chunk, like any operator's output batch.
13541339
fn coalesce_chunks(
13551340
batches: Vec<RecordBatch>,
13561341
schema: &SchemaRef,
13571342
target_batch_size: usize,
13581343
) -> Result<Vec<RecordBatch>> {
1359-
let mut coalescer = chunk_coalescer(schema, target_batch_size);
1344+
let mut coalescer = BatchCoalescer::new(Arc::clone(schema), target_batch_size)
1345+
.with_biggest_coalesce_batch_size(Some(target_batch_size / 2));
13601346
let mut chunks = Vec::with_capacity(batches.len());
13611347
for batch in batches {
13621348
coalescer.push_batch(batch)?;
@@ -1371,16 +1357,14 @@ fn coalesce_chunks(
13711357
Ok(chunks)
13721358
}
13731359

1374-
/// Write the already-completed chunks, the batch that hit the limit, and the remainder of the
1375-
/// same stream to one spill file. Nothing is reserved past this point, so the remainder is
1376-
/// written batch by batch as it arrives instead of being coalesced, which would hold up to a
1377-
/// chunk's worth of unreserved rows; the memory-limited replay coalesces each pass it reads
1378-
/// back, after reserving it.
1360+
/// Write the batches buffered so far, the batch that hit the limit, and the remainder of the
1361+
/// same stream to one spill file, each as it arrived. Nothing is copied or coalesced here, so the
1362+
/// spill allocates nothing beyond the file writer while the pool is exhausted.
13791363
/// Returns `None` when the left side carried no rows at all, which needs no spill file.
13801364
async fn spill_left_input(
13811365
spill_manager: SpillManager,
13821366
schema: SchemaRef,
1383-
chunks: Vec<RecordBatch>,
1367+
batches: Vec<RecordBatch>,
13841368
pending: Option<RecordBatch>,
13851369
mut stream: SendableRecordBatchStream,
13861370
metrics: BuildProbeJoinMetrics,
@@ -1390,10 +1374,10 @@ async fn spill_left_input(
13901374
let mut spill_file =
13911375
spill_manager.create_in_progress_file("NestedLoopJoin left spill")?;
13921376

1393-
for batch in chunks {
1377+
for batch in batches {
13941378
spill_file.append_batch(&batch)?;
13951379
}
1396-
// The in-memory chunks are spilled and dropped, so their reservation goes back to the pool
1380+
// The buffered batches are spilled and dropped, so their reservation goes back to the pool
13971381
// before the rest of the stream is drained.
13981382
reservation.free();
13991383
if let Some(batch) = pending.filter(|b| b.num_rows() > 0) {
@@ -1447,7 +1431,7 @@ enum NLJState {
14471431
}
14481432
/// Outcome of the single pass over the left (build) input.
14491433
pub(crate) enum LeftLoad {
1450-
/// The left side fit the memory budget and is buffered as one batch.
1434+
/// The left side fit the memory budget and is buffered as chunks.
14511435
InMemory(Arc<JoinLeftData>),
14521436
/// The budget ran out, so the left side was spilled during that same pass. Every partition
14531437
/// shares this handle, and each left chunk pass re-opens the file.
@@ -1887,7 +1871,6 @@ impl FallbackCoordinator {
18871871
&mut reservation,
18881872
carryover,
18891873
Arc::clone(&left_schema),
1890-
task_context.session_config().batch_size(),
18911874
build_time.clone(),
18921875
);
18931876
let load_result = {
@@ -1985,7 +1968,6 @@ impl FallbackCoordinator {
19851968
reservation: &mut MemoryReservation,
19861969
carryover: Option<RecordBatch>,
19871970
left_schema: SchemaRef,
1988-
target_batch_size: usize,
19891971
build_time: Time,
19901972
) -> Result<LoadOutcome> {
19911973
// The previous chunk's bytes were moved into its `JoinLeftData`, so
@@ -2042,8 +2024,9 @@ impl FallbackCoordinator {
20422024
}
20432025

20442026
let _build_timer = build_time.timer();
2045-
// Every batch of the pass is reserved above, so compacting it here stays within budget.
2046-
let chunks = coalesce_chunks(pending_batches, &left_schema, target_batch_size)?;
2027+
// Kept as read back: compacting the pass would copy it while its reserved inputs are
2028+
// still live, on top of a pool that is already full.
2029+
let chunks = pending_batches;
20472030
let n_rows: usize = chunks.iter().map(|c| c.num_rows()).sum();
20482031
let visited_left_side = if self.with_visited_bitmap {
20492032
let buffer_size = n_rows.div_ceil(8);
Lines changed: 228 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,228 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Peak-allocation check for the NestedLoopJoin build side under a memory limit.
19+
//!
20+
//! The memory pool only sees what the operator reserves, so a copy of the build side that is
21+
//! never reserved (the `concat_batches` this operator used to make, or coalescing a pass while
22+
//! its inputs are still live) is invisible to pool-based assertions. This binary counts live
23+
//! bytes at the allocator instead, and must stay the only test in it so nothing else runs
24+
//! alongside the measurement.
25+
26+
use std::alloc::{GlobalAlloc, Layout, System};
27+
use std::any::Any;
28+
use std::fmt;
29+
use std::sync::Arc;
30+
use std::sync::atomic::{AtomicUsize, Ordering};
31+
32+
use arrow::array::{Int32Array, StringArray};
33+
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
34+
use arrow::record_batch::RecordBatch;
35+
use datafusion_common::{JoinSide, JoinType, Result};
36+
use datafusion_execution::TaskContext;
37+
use datafusion_execution::runtime_env::RuntimeEnvBuilder;
38+
use datafusion_expr::Operator;
39+
use datafusion_physical_expr::expressions::{BinaryExpr, Column};
40+
use datafusion_physical_plan::common::collect;
41+
use datafusion_physical_plan::joins::NestedLoopJoinExec;
42+
use datafusion_physical_plan::joins::utils::{ColumnIndex, JoinFilter};
43+
use datafusion_physical_plan::memory::{LazyBatchGenerator, LazyMemoryExec};
44+
use datafusion_physical_plan::test::TestMemoryExec;
45+
use datafusion_physical_plan::{ExecutionPlan, PhysicalExpr};
46+
use parking_lot::RwLock;
47+
48+
struct PeakTrackingAllocator;
49+
50+
static LIVE_BYTES: AtomicUsize = AtomicUsize::new(0);
51+
static PEAK_BYTES: AtomicUsize = AtomicUsize::new(0);
52+
53+
fn record_alloc(bytes: usize) {
54+
let live = LIVE_BYTES.fetch_add(bytes, Ordering::Relaxed) + bytes;
55+
PEAK_BYTES.fetch_max(live, Ordering::Relaxed);
56+
}
57+
58+
unsafe impl GlobalAlloc for PeakTrackingAllocator {
59+
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
60+
let ptr = unsafe { System.alloc(layout) };
61+
if !ptr.is_null() {
62+
record_alloc(layout.size());
63+
}
64+
ptr
65+
}
66+
67+
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
68+
unsafe { System.dealloc(ptr, layout) };
69+
LIVE_BYTES.fetch_sub(layout.size(), Ordering::Relaxed);
70+
}
71+
72+
unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
73+
let new_ptr = unsafe { System.realloc(ptr, layout, new_size) };
74+
if !new_ptr.is_null() {
75+
LIVE_BYTES.fetch_sub(layout.size(), Ordering::Relaxed);
76+
record_alloc(new_size);
77+
}
78+
new_ptr
79+
}
80+
}
81+
82+
#[global_allocator]
83+
static GLOBAL: PeakTrackingAllocator = PeakTrackingAllocator;
84+
85+
const ROW_BYTES: usize = 64 * 1024;
86+
const BUILD_ROWS: usize = 512;
87+
const POOL_BYTES: usize = 8 * 1024 * 1024;
88+
89+
/// One row per batch, each with its own 64 KiB string allocation, so a target-row coalescer
90+
/// would merge a whole pass into a single chunk and copy every byte of it. The count is shared
91+
/// across `reset_state` so the test can read it after the run.
92+
#[derive(Debug)]
93+
struct WideRows {
94+
schema: SchemaRef,
95+
emitted: Arc<AtomicUsize>,
96+
}
97+
98+
impl fmt::Display for WideRows {
99+
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
100+
write!(
101+
f,
102+
"WideRows(emitted={})",
103+
self.emitted.load(Ordering::Relaxed)
104+
)
105+
}
106+
}
107+
108+
impl LazyBatchGenerator for WideRows {
109+
fn as_any(&self) -> &dyn Any {
110+
self
111+
}
112+
113+
fn generate_next_batch(&mut self) -> Result<Option<RecordBatch>> {
114+
if self.emitted.load(Ordering::Relaxed) == BUILD_ROWS {
115+
return Ok(None);
116+
}
117+
self.emitted.fetch_add(1, Ordering::Relaxed);
118+
let batch = RecordBatch::try_new(
119+
Arc::clone(&self.schema),
120+
vec![
121+
Arc::new(Int32Array::from(vec![0])),
122+
Arc::new(StringArray::from(vec!["x".repeat(ROW_BYTES)])),
123+
],
124+
)?;
125+
Ok(Some(batch))
126+
}
127+
128+
fn reset_state(&self) -> Arc<RwLock<dyn LazyBatchGenerator>> {
129+
Arc::new(RwLock::new(WideRows {
130+
schema: Arc::clone(&self.schema),
131+
emitted: Arc::clone(&self.emitted),
132+
}))
133+
}
134+
}
135+
136+
/// `left.k > right.k` with every left `k` at 0 and every right `k` at 1, so the join keeps its
137+
/// full probe shape while producing no rows to hold on to.
138+
fn never_matching_filter() -> JoinFilter {
139+
let expression: Arc<dyn PhysicalExpr> = Arc::new(BinaryExpr::new(
140+
Arc::new(Column::new("k", 0)),
141+
Operator::Gt,
142+
Arc::new(Column::new("k", 1)),
143+
));
144+
let column_indices = vec![
145+
ColumnIndex {
146+
index: 0,
147+
side: JoinSide::Left,
148+
},
149+
ColumnIndex {
150+
index: 0,
151+
side: JoinSide::Right,
152+
},
153+
];
154+
let schema = Schema::new(vec![
155+
Field::new("k", DataType::Int32, false),
156+
Field::new("k", DataType::Int32, false),
157+
]);
158+
JoinFilter::new(expression, column_indices, Arc::new(schema))
159+
}
160+
161+
#[tokio::test]
162+
async fn build_side_spill_and_replay_stay_within_the_pool() -> Result<()> {
163+
let left_schema = Arc::new(Schema::new(vec![
164+
Field::new("k", DataType::Int32, false),
165+
Field::new("s", DataType::Utf8, false),
166+
]));
167+
let emitted = Arc::new(AtomicUsize::new(0));
168+
let left: Arc<dyn ExecutionPlan> = Arc::new(LazyMemoryExec::try_new(
169+
Arc::clone(&left_schema),
170+
vec![Arc::new(RwLock::new(WideRows {
171+
schema: left_schema,
172+
emitted: Arc::clone(&emitted),
173+
}))],
174+
)?);
175+
176+
let right_schema =
177+
Arc::new(Schema::new(vec![Field::new("k", DataType::Int32, false)]));
178+
let right_batch = RecordBatch::try_new(
179+
Arc::clone(&right_schema),
180+
vec![Arc::new(Int32Array::from(vec![1, 1, 1, 1]))],
181+
)?;
182+
let right: Arc<dyn ExecutionPlan> =
183+
TestMemoryExec::try_new_exec(&[vec![right_batch]], right_schema, None)?;
184+
185+
let join = NestedLoopJoinExec::try_new(
186+
left,
187+
right,
188+
Some(never_matching_filter()),
189+
&JoinType::Inner,
190+
None,
191+
)?;
192+
let runtime = RuntimeEnvBuilder::new()
193+
.with_memory_limit(POOL_BYTES, 1.0)
194+
.build_arc()?;
195+
let ctx = Arc::new(TaskContext::default().with_runtime(runtime));
196+
197+
let baseline = LIVE_BYTES.load(Ordering::Relaxed);
198+
PEAK_BYTES.store(baseline, Ordering::Relaxed);
199+
let output = collect(join.execute(0, ctx)?).await?;
200+
let peak = PEAK_BYTES.load(Ordering::Relaxed) - baseline;
201+
202+
let output_rows: usize = output.iter().map(|b| b.num_rows()).sum();
203+
assert_eq!(output_rows, 0);
204+
let metrics = join.metrics().expect("metrics");
205+
assert!(
206+
metrics.spill_count().unwrap_or(0) > 0,
207+
"the build side must spill"
208+
);
209+
assert_eq!(
210+
emitted.load(Ordering::Relaxed),
211+
BUILD_ROWS,
212+
"every build row must be consumed"
213+
);
214+
215+
// The build side is four times the pool, so it spills and is replayed pass by pass, each pass
216+
// filling the pool. Any unreserved copy of a pass (a coalesced spill chunk at the spill
217+
// transition, or a coalesced replay pass) doubles that peak; ordinary bookkeeping (the
218+
// carried-over batch, spill reader buffers, the probe side) stays far below half a pool.
219+
let limit = POOL_BYTES + POOL_BYTES / 2;
220+
assert!(
221+
peak < limit,
222+
"peak live allocation {:.2} MiB exceeds {:.2} MiB with an {:.0} MiB pool",
223+
peak as f64 / (1024.0 * 1024.0),
224+
limit as f64 / (1024.0 * 1024.0),
225+
POOL_BYTES as f64 / (1024.0 * 1024.0),
226+
);
227+
Ok(())
228+
}

0 commit comments

Comments
 (0)