|
| 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