@@ -26,14 +26,23 @@ use datafusion_execution::memory_pool::MemoryReservation;
2626use log:: warn;
2727use std:: sync:: Arc ;
2828
29- #[ derive( Debug , Copy , Clone , Default ) ]
29+ #[ derive( Debug , Copy , Clone ) ]
3030struct BatchCursor {
3131 /// The index into BatchBuilder::batches
3232 batch_idx : usize ,
3333 /// The row index within the given batch
3434 row_idx : usize ,
3535}
3636
37+ impl BatchCursor {
38+ /// A cursor whose batch has been released. `push_row` must not be called
39+ /// for the stream until `push_batch` installs a new cursor.
40+ const RELEASED : Self = Self {
41+ batch_idx : usize:: MAX ,
42+ row_idx : 0 ,
43+ } ;
44+ }
45+
3746/// Provides an API to incrementally build a [`RecordBatch`] from partitioned [`RecordBatch`]
3847#[ derive( Debug ) ]
3948pub struct BatchBuilder {
@@ -81,7 +90,7 @@ impl BatchBuilder {
8190 Self {
8291 schema,
8392 batches : Vec :: with_capacity ( stream_count * 2 ) ,
84- cursors : vec ! [ BatchCursor :: default ( ) ; stream_count] ,
93+ cursors : vec ! [ BatchCursor :: RELEASED ; stream_count] ,
8594 indices : Vec :: with_capacity ( batch_size) ,
8695 reservation,
8796 batches_mem_used : 0 ,
@@ -108,6 +117,14 @@ impl BatchBuilder {
108117
109118 /// Append the next row from `stream_idx`
110119 pub fn push_row ( & mut self , stream_idx : usize ) {
120+ debug_assert ! (
121+ self . batches
122+ . get( self . cursors[ stream_idx] . batch_idx)
123+ . is_some_and( |( _, batch) | {
124+ self . cursors[ stream_idx] . row_idx < batch. num_rows( )
125+ } ) ,
126+ "push_row on stream {stream_idx} with no live batch"
127+ ) ;
111128 let cursor = & mut self . cursors [ stream_idx] ;
112129 let row_idx = cursor. row_idx ;
113130 cursor. row_idx += 1 ;
@@ -157,33 +174,10 @@ impl BatchBuilder {
157174 // Remove consumed indices, keeping any remaining for the next call.
158175 self . indices . drain ( ..rows_to_emit) ;
159176
160- // Only clean up fully-consumed batches when all indices are drained,
161- // because remaining indices may still reference earlier batches.
162- // In the overflow/partial-emit case this may retain some extra memory
163- // across a few drain polls, but avoids costly index scanning on the
164- // hot path. The retention is bounded and short-lived since leftover
165- // rows are drained over subsequent polls.
166177 if self . indices . is_empty ( ) {
167- // New cursors are only created once the previous cursor for the stream
168- // is finished. This means all remaining rows from all but the last batch
169- // for each stream have been yielded to the newly created record batch
170- //
171- // We can therefore drop all but the last batch for each stream
172- let mut batch_idx = 0 ;
173- let mut retained = 0 ;
174- self . batches . retain ( |( stream_idx, batch) | {
175- let stream_cursor = & mut self . cursors [ * stream_idx] ;
176- let retain = stream_cursor. batch_idx == batch_idx;
177- batch_idx += 1 ;
178-
179- if retain {
180- stream_cursor. batch_idx = retained;
181- retained += 1 ;
182- } else {
183- self . batches_mem_used -= get_record_batch_memory_size ( batch) ;
184- }
185- retain
186- } ) ;
178+ self . retain_cursor_batches ( ) ;
179+ } else {
180+ self . retain_live_batches ( ) ;
187181 }
188182
189183 // Release excess memory back to the pool, but never shrink below
@@ -197,6 +191,75 @@ impl BatchBuilder {
197191 RecordBatch :: try_new ( Arc :: clone ( & self . schema ) , columns) . map_err ( Into :: into)
198192 }
199193
194+ fn retain_cursor_batches ( & mut self ) {
195+ // New cursors are only created once the previous cursor for the stream
196+ // is finished. This means all remaining rows from all but the last batch
197+ // for each stream have been yielded to the newly created record batch
198+ //
199+ // We can therefore drop all but the last live cursor batch for each stream
200+ let mut batch_idx = 0 ;
201+ let mut retained = 0 ;
202+ self . batches . retain ( |( stream_idx, batch) | {
203+ let stream_cursor = & mut self . cursors [ * stream_idx] ;
204+ let is_cursor_batch = stream_cursor. batch_idx == batch_idx;
205+ let retain = is_cursor_batch && stream_cursor. row_idx < batch. num_rows ( ) ;
206+ batch_idx += 1 ;
207+
208+ if retain {
209+ stream_cursor. batch_idx = retained;
210+ retained += 1 ;
211+ } else {
212+ if is_cursor_batch {
213+ * stream_cursor = BatchCursor :: RELEASED ;
214+ }
215+ self . batches_mem_used -= get_record_batch_memory_size ( batch) ;
216+ }
217+ retain
218+ } ) ;
219+ }
220+
221+ fn retain_live_batches ( & mut self ) {
222+ let mut retain_batch = vec ! [ false ; self . batches. len( ) ] ;
223+ for ( batch_idx, _) in & self . indices {
224+ retain_batch[ * batch_idx] = true ;
225+ }
226+
227+ for cursor in & self . cursors {
228+ if self
229+ . batches
230+ . get ( cursor. batch_idx )
231+ . is_some_and ( |( _, batch) | cursor. row_idx < batch. num_rows ( ) )
232+ {
233+ retain_batch[ cursor. batch_idx ] = true ;
234+ }
235+ }
236+
237+ let mut batch_idx = 0 ;
238+ let mut retained = 0 ;
239+ let mut remap = vec ! [ usize :: MAX ; self . batches. len( ) ] ;
240+ self . batches . retain ( |( _, batch) | {
241+ let retain = retain_batch[ batch_idx] ;
242+ if retain {
243+ remap[ batch_idx] = retained;
244+ retained += 1 ;
245+ } else {
246+ self . batches_mem_used -= get_record_batch_memory_size ( batch) ;
247+ }
248+ batch_idx += 1 ;
249+ retain
250+ } ) ;
251+
252+ for ( batch_idx, _) in & mut self . indices {
253+ * batch_idx = remap[ * batch_idx] ;
254+ }
255+ for cursor in & mut self . cursors {
256+ if let Some ( new_idx) = remap. get ( cursor. batch_idx ) {
257+ // `usize::MAX` means the cursor's batch was released.
258+ cursor. batch_idx = * new_idx;
259+ }
260+ }
261+ }
262+
200263 /// Drains the in_progress row indexes, and builds a new RecordBatch from them
201264 ///
202265 /// Will then drop any batches for which all rows have been yielded to the output.
@@ -280,6 +343,7 @@ mod tests {
280343 use arrow:: array:: { Array , ArrayDataBuilder , Int32Array , ListArray } ;
281344 use arrow:: buffer:: Buffer ;
282345 use arrow:: datatypes:: { DataType , Field , Schema } ;
346+ use arrow:: record_batch:: RecordBatch ;
283347 use datafusion_execution:: memory_pool:: {
284348 MemoryConsumer , MemoryPool , UnboundedMemoryPool ,
285349 } ;
@@ -303,6 +367,96 @@ mod tests {
303367 RecordBatch :: try_new ( schema, vec ! [ Arc :: new( list) ] ) . unwrap ( )
304368 }
305369
370+ fn reservation ( ) -> MemoryReservation {
371+ let pool: Arc < dyn MemoryPool > = Arc :: new ( UnboundedMemoryPool :: default ( ) ) ;
372+ MemoryConsumer :: new ( "test" ) . register ( & pool)
373+ }
374+
375+ fn int_batch ( values : Vec < i32 > ) -> RecordBatch {
376+ let schema = Arc :: new ( Schema :: new ( vec ! [ Field :: new( "i" , DataType :: Int32 , false ) ] ) ) ;
377+ RecordBatch :: try_new ( schema, vec ! [ Arc :: new( Int32Array :: from( values) ) ] ) . unwrap ( )
378+ }
379+
380+ fn push_n_rows ( builder : & mut BatchBuilder , stream_idx : usize , n : usize ) {
381+ for _ in 0 ..n {
382+ builder. push_row ( stream_idx) ;
383+ }
384+ }
385+
386+ fn emit_n_rows ( builder : & mut BatchBuilder , n : usize ) -> RecordBatch {
387+ let columns = builder
388+ . try_interleave_columns ( & builder. indices [ ..n] )
389+ . unwrap ( ) ;
390+ builder. finish_record_batch ( n, columns) . unwrap ( )
391+ }
392+
393+ fn assert_int_output ( batch : & RecordBatch , expected : & [ i32 ] ) {
394+ let actual = batch
395+ . column ( 0 )
396+ . as_any ( )
397+ . downcast_ref :: < Int32Array > ( )
398+ . unwrap ( )
399+ . values ( ) ;
400+ assert_eq ! ( actual, expected) ;
401+ }
402+
403+ #[ test]
404+ fn test_partial_emit_releases_unreferenced_and_retains_live_batches ( ) {
405+ let batch0 = int_batch ( vec ! [ 10 , 11 ] ) ;
406+ let batch1 = int_batch ( vec ! [ 20 , 21 ] ) ;
407+ let batch2 = int_batch ( vec ! [ 30 , 31 ] ) ;
408+ let batch1_size = get_record_batch_memory_size ( & batch1) ;
409+ let batch2_size = get_record_batch_memory_size ( & batch2) ;
410+ let schema = batch0. schema ( ) ;
411+ let mut builder = BatchBuilder :: new ( Arc :: clone ( & schema) , 3 , 6 , reservation ( ) ) ;
412+
413+ builder. push_batch ( 0 , batch0) . unwrap ( ) ;
414+ push_n_rows ( & mut builder, 0 , 2 ) ;
415+ builder. push_batch ( 1 , batch1) . unwrap ( ) ;
416+ push_n_rows ( & mut builder, 1 , 2 ) ;
417+ // Keep one stream empty so an unloaded cursor cannot retain consumed batches.
418+ builder. push_batch ( 0 , batch2) . unwrap ( ) ;
419+
420+ let output = emit_n_rows ( & mut builder, 2 ) ;
421+ assert_int_output ( & output, & [ 10 , 11 ] ) ;
422+
423+ assert_eq ! ( builder. len( ) , 2 ) ;
424+ assert_eq ! ( builder. batches. len( ) , 2 ) ;
425+ assert_eq ! ( builder. batches_mem_used, batch1_size + batch2_size) ;
426+ assert_eq ! ( builder. reservation. size( ) , batch1_size + batch2_size) ;
427+
428+ push_n_rows ( & mut builder, 0 , 2 ) ;
429+ let output = emit_n_rows ( & mut builder, 4 ) ;
430+ assert_int_output ( & output, & [ 20 , 21 , 30 , 31 ] ) ;
431+
432+ assert ! ( builder. is_empty( ) ) ;
433+ assert ! ( builder. batches. is_empty( ) ) ;
434+ assert_eq ! ( builder. batches_mem_used, 0 ) ;
435+ assert_eq ! ( builder. reservation. size( ) , 0 ) ;
436+ }
437+
438+ #[ test]
439+ fn test_released_cursor_accepts_new_batch_for_stream ( ) {
440+ let batch0 = int_batch ( vec ! [ 10 ] ) ;
441+ let batch1 = int_batch ( vec ! [ 20 ] ) ;
442+ let schema = batch0. schema ( ) ;
443+ let mut builder = BatchBuilder :: new ( Arc :: clone ( & schema) , 1 , 1 , reservation ( ) ) ;
444+
445+ builder. push_batch ( 0 , batch0) . unwrap ( ) ;
446+ builder. push_row ( 0 ) ;
447+ let output = emit_n_rows ( & mut builder, 1 ) ;
448+ assert_int_output ( & output, & [ 10 ] ) ;
449+ assert ! ( builder. batches. is_empty( ) ) ;
450+
451+ builder. push_batch ( 0 , batch1) . unwrap ( ) ;
452+ builder. push_row ( 0 ) ;
453+ let output = emit_n_rows ( & mut builder, 1 ) ;
454+ assert_int_output ( & output, & [ 20 ] ) ;
455+ assert ! ( builder. batches. is_empty( ) ) ;
456+ assert_eq ! ( builder. batches_mem_used, 0 ) ;
457+ assert_eq ! ( builder. reservation. size( ) , 0 ) ;
458+ }
459+
306460 #[ test]
307461 fn test_retry_interleave_halves_rows_until_success ( ) {
308462 let mut attempts = Vec :: new ( ) ;
0 commit comments