@@ -32,9 +32,9 @@ use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
3232
3333use arrow:: datatypes:: SchemaRef ;
3434use arrow:: record_batch:: RecordBatch ;
35- use datafusion_common:: Result ;
36- use datafusion_execution:: async_try_stream;
35+ use datafusion_common:: { DataFusionError , Result , assert_or_internal_err, internal_err} ;
3736use datafusion_execution:: memory_pool:: MemoryReservation ;
37+ use datafusion_execution:: { TryEmitter , async_try_stream} ;
3838use futures:: Stream ;
3939
4040/// A fallible [`PartitionedStream`] of [`Cursor`] and [`RecordBatch`]
@@ -146,6 +146,9 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
146146 reservation : MemoryReservation ,
147147 enable_round_robin_tie_breaker : bool ,
148148 ) -> Self {
149+ assert_ne ! ( batch_size, 0 , "batch size cannot be 0" ) ;
150+ assert_ne ! ( fetch, Some ( 0 ) , "fetch must not be Some(0)" ) ;
151+
149152 let stream_count = streams. partitions ( ) ;
150153
151154 Self {
@@ -173,7 +176,6 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
173176 let schema_clone = Arc :: clone ( self . in_progress . schema ( ) ) ;
174177
175178 let cloned_metrics = self . metrics . clone ( ) ;
176-
177179 let stream = Box :: pin ( RecordBatchStreamAdapter :: new (
178180 schema_clone,
179181 self . create_stream ( ) ,
@@ -212,79 +214,122 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
212214 result
213215 }
214216
215- fn create_stream ( mut self ) -> impl Stream < Item = Result < RecordBatch > > {
216- async_try_stream ( |mut emitter| async move {
217- // This vector contains the indices of the partitions that have not started emitting yet.
218- let mut uninitiated_partitions =
219- ( 0 ..self . streams . partitions ( ) ) . collect :: < Vec < _ > > ( ) ;
217+ async fn flush_in_progress (
218+ & mut self ,
219+ mut emitter : TryEmitter < RecordBatch , DataFusionError > ,
220+ ) -> Result < ( ) > {
221+ if self . in_progress . is_empty ( ) {
222+ return Ok ( ( ) ) ;
223+ }
220224
221- poll_fn ( |cx| self . initialize_all_partitions ( & mut uninitiated_partitions, cx) )
222- . await ?;
225+ let elapsed_compute = self . metrics . elapsed_compute ( ) . clone ( ) ;
226+ let mut timer = elapsed_compute. timer ( ) ;
227+
228+ // When `build_record_batch()` hits an i32 offset overflow (e.g.
229+ // combined string offsets exceed 2 GB), it emits a partial batch
230+ // and keeps the remaining rows in `self.in_progress.indices`.
231+ // Drain those leftover rows before terminating the stream,
232+ // otherwise they would be silently dropped.
233+ // Repeated overflows are fine — each poll emits another partial
234+ // batch until `in_progress` is fully drained.
235+ while let Some ( batch) = self . emit_in_progress_batch ( ) ? {
236+ drop ( timer) ;
237+ emitter. emit ( batch) . await ;
238+ timer = elapsed_compute. timer ( ) ;
239+ }
223240
224- assert_eq ! ( uninitiated_partitions. len( ) , 0 ) ;
241+ Ok ( ( ) )
242+ }
225243
226- // If there are no more uninitiated partitions, set up the loser tree and continue
227- // to the next phase.
244+ fn create_stream ( mut self ) -> impl Stream < Item = Result < RecordBatch > > {
245+ async_try_stream ( |mut emitter| async move {
246+ // 1. Make sure we have data from each stream so we can initialize the loser tree
247+ {
248+ // This vector contains the indices of the partitions that have not started emitting yet.
249+ let mut uninitiated_partitions =
250+ ( 0 ..self . streams . partitions ( ) ) . collect :: < Vec < _ > > ( ) ;
251+
252+ poll_fn ( |cx| {
253+ self . initialize_all_partitions ( & mut uninitiated_partitions, cx)
254+ } )
255+ . await ?;
228256
229- // Claim the memory for the uninitiated partitions
230- drop ( uninitiated_partitions) ;
231- self . init_loser_tree ( ) ;
257+ assert_eq ! ( uninitiated_partitions. len( ) , 0 ) ;
258+ }
232259
233- // NB timer records time taken on drop, so there are no
234- // calls to `timer.done()` below.
235260 let elapsed_compute = self . metrics . elapsed_compute ( ) . clone ( ) ;
236261 let mut timer = elapsed_compute. timer ( ) ;
237262
238- loop {
239- let stream_idx = self . loser_tree [ 0 ] ;
240- if !self . advance_cursors ( stream_idx) {
241- break ;
242- }
243- self . in_progress . push_row ( stream_idx) ;
263+ // 2. Init loser tree
264+ self . init_loser_tree ( ) ;
244265
245- // stop sorting if fetch has been reached
266+ // 3. loop until all streams have been exhausted
267+ while !self . is_exhausted ( ) {
268+ // 3.1. add loser_tree[0] (minimum) stream to pending record batch
269+ let winner_stream = self . loser_tree [ 0 ] ;
270+ self . in_progress . push_row ( winner_stream) ;
271+
272+ // 3.2. If the new row reached the limit
246273 if self . fetch_reached ( ) {
247274 break ;
248275 }
249276
250- if self . in_progress . len ( ) >= self . batch_size
251- && let Some ( batch) = self . emit_in_progress_batch ( ) ?
252- {
277+ // 3.3. if there is enough to emit for a full record batch
278+ if self . in_progress . len ( ) >= self . batch_size {
279+ // 3.3.1 build pending record batch and reset builder
280+ let Some ( batch) = self . emit_in_progress_batch ( ) ? else {
281+ return internal_err ! ( "must have batch in progress to emit" ) ;
282+ } ;
283+
284+ // 3.3.2 emit pending record batch
253285 drop ( timer) ;
254286 emitter. emit ( batch) . await ;
255287 timer = elapsed_compute. timer ( ) ;
256288 }
257289
258- let winner = self . loser_tree [ 0 ] ;
259- // Fast path: skip the `maybe_poll_stream` call (and its `Poll`
260- // plumbing) unless the winner's cursor is exhausted and needs a
261- // fresh batch — it is live for almost every row.
262- if self . cursors [ winner] . is_none ( ) {
263- drop ( timer) ;
264- poll_fn ( |cx| self . maybe_poll_stream ( cx, winner) ) . await ?;
265- timer = elapsed_compute. timer ( ) ;
290+ // 3.4. advance cursor for the winner stream
291+ {
292+ let should_poll_next_batch_for_stream =
293+ self . advance_cursors ( winner_stream) ;
294+
295+ // Fast path: skip the `maybe_poll_stream` call (and its `Poll`
296+ // plumbing) unless the winner's cursor is exhausted and needs a
297+ // fresh batch — it is live for almost every row.
298+ if should_poll_next_batch_for_stream {
299+ assert_or_internal_err ! (
300+ self . cursors[ winner_stream] . is_none( ) ,
301+ "cursor should be exhausted"
302+ ) ;
303+
304+ drop ( timer) ;
305+ poll_fn ( |cx| self . maybe_poll_stream ( cx, winner_stream) ) . await ?;
306+ timer = elapsed_compute. timer ( ) ;
307+ }
266308 }
267309
268- // Adjusting the loser tree if necessary
310+ // 3.5. Adjusting the loser tree if necessary
269311 self . update_loser_tree ( ) ;
270312 }
271313
272- drop ( timer) ;
314+ // 4. Flush any remaining rows in `self.in_progress`
315+ self . flush_in_progress ( emitter) . await ?;
273316
274- // When `build_record_batch()` hits an i32 offset overflow (e.g.
275- // combined string offsets exceed 2 GB), it emits a partial batch
276- // and keeps the remaining rows in `self.in_progress.indices`.
277- // Drain those leftover rows before terminating the stream,
278- // otherwise they would be silently dropped.
279- // Repeated overflows are fine — each poll emits another partial
280- // batch until `in_progress` is fully drained.
281- while let Some ( batch) = self . emit_in_progress_batch ( ) ? {
282- emitter. emit ( batch) . await ;
283- }
284317 Ok ( ( ) )
285318 } )
286319 }
287320
321+ /// Returns `true` once every input stream is exhausted.
322+ ///
323+ /// Should only be called for valid adjusted tree, i.e. the initial tree or after [`Self::update_loser_tree`] call
324+ fn is_exhausted ( & self ) -> bool {
325+ let winner = self . loser_tree [ 0 ] ;
326+
327+ // Checking only the tree root suffices for valid tree
328+ // since the winner of the tree cannot be an exhausted stream for a valid tree
329+ // as what value is winning over the non exhausted stream?
330+ self . cursors [ winner] . is_none ( )
331+ }
332+
288333 /// Initialize all partitions, return `Poll::Pending` if any partition returns `Poll::Pending`
289334 ///
290335 /// This DOES NOT return `Poll::Pending` as soon as the first uninitiated partition returns `Poll::Pending`
@@ -369,18 +414,20 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
369414 /// Advances the actual cursor. If it reaches its end, update the
370415 /// previous cursor with it.
371416 ///
372- /// If the given partition is not exhausted, the function returns `true`.
417+ /// If the given partition batch is exhausted, return `true` to signal a poll is needed
373418 fn advance_cursors ( & mut self , stream_idx : usize ) -> bool {
374419 if let Some ( cursor) = & mut self . cursors [ stream_idx] {
375420 let _ = cursor. advance ( ) ;
376- if cursor. is_finished ( ) {
421+ let finished = cursor. is_finished ( ) ;
422+ if finished {
377423 // Take the current cursor, leaving `None` in its place
378424 self . prev_cursors [ stream_idx] = self . cursors [ stream_idx] . take ( ) ;
379425 }
380- true
381- } else {
382- false
426+ return finished;
383427 }
428+
429+ // the entire stream is exhausted, so return true (poll won't help here anyway)
430+ true
384431 }
385432
386433 /// Returns `true` if the cursor at index `a` is greater than at index `b`.
0 commit comments