1818//! Merge that deals with an arbitrary size of streaming inputs.
1919//! This is an order-preserving merge.
2020
21- use std:: pin:: Pin ;
21+ use std:: fmt:: Debug ;
22+ use std:: future:: poll_fn;
2223use std:: sync:: Arc ;
23- use std:: task:: { Context , Poll , ready } ;
24+ use std:: task:: { Context , Poll } ;
2425
25- use crate :: RecordBatchStream ;
26+ use crate :: SendableRecordBatchStream ;
2627use crate :: metrics:: BaselineMetrics ;
2728use crate :: sorts:: builder:: BatchBuilder ;
2829use crate :: sorts:: cursor:: { Cursor , CursorValues } ;
2930use crate :: sorts:: stream:: PartitionedStream ;
31+ use crate :: stream:: { ObservedStream , RecordBatchStreamAdapter } ;
3032
3133use arrow:: datatypes:: SchemaRef ;
3234use arrow:: record_batch:: RecordBatch ;
3335use datafusion_common:: Result ;
36+ use datafusion_execution:: async_try_stream;
3437use datafusion_execution:: memory_pool:: MemoryReservation ;
35-
3638use futures:: Stream ;
3739
3840/// A fallible [`PartitionedStream`] of [`Cursor`] and [`RecordBatch`]
@@ -49,18 +51,6 @@ pub(crate) struct SortPreservingMergeStream<C: CursorValues> {
4951 /// used to record execution metrics
5052 metrics : BaselineMetrics ,
5153
52- /// If the stream has encountered an error or reaches the
53- /// `fetch` limit.
54- done : bool ,
55-
56- /// Whether buffered rows should be drained after `done` is set.
57- ///
58- /// This is enabled when we stop because the `fetch` limit has been
59- /// reached, allowing partial batches left over after overflow handling to
60- /// be emitted on subsequent polls. It remains disabled for terminal
61- /// errors so the stream does not yield data after returning `Err`.
62- drain_in_progress_on_done : bool ,
63-
6454 /// A loser tree that always produces the minimum cursor
6555 ///
6656 /// Node 0 stores the top winner, Nodes 1..num_streams store
@@ -93,12 +83,6 @@ pub(crate) struct SortPreservingMergeStream<C: CursorValues> {
9383 /// reference: <https://en.wikipedia.org/wiki/K-way_merge_algorithm#Tournament_Tree>
9484 loser_tree : Vec < usize > ,
9585
96- /// If the most recently yielded overall winner has been replaced
97- /// within the loser tree. A value of `false` indicates that the
98- /// overall winner has been yielded but the loser tree has not
99- /// been updated
100- loser_tree_adjusted : bool ,
101-
10286 /// Target batch size
10387 batch_size : usize ,
10488
@@ -150,9 +134,6 @@ pub(crate) struct SortPreservingMergeStream<C: CursorValues> {
150134
151135 /// number of rows produced
152136 produced : usize ,
153-
154- /// This vector contains the indices of the partitions that have not started emitting yet.
155- uninitiated_partitions : Vec < usize > ,
156137}
157138
158139impl < C : CursorValues > SortPreservingMergeStream < C > {
@@ -171,24 +152,36 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
171152 in_progress : BatchBuilder :: new ( schema, stream_count, batch_size, reservation) ,
172153 streams,
173154 metrics,
174- done : false ,
175- drain_in_progress_on_done : false ,
176155 cursors : ( 0 ..stream_count) . map ( |_| None ) . collect ( ) ,
177156 prev_cursors : ( 0 ..stream_count) . map ( |_| None ) . collect ( ) ,
178157 round_robin_tie_breaker_mode : false ,
179158 num_of_polled_with_same_value : vec ! [ 0 ; stream_count] ,
180159 current_reset_epoch : 0 ,
181160 poll_reset_epochs : vec ! [ 0 ; stream_count] ,
182161 loser_tree : vec ! [ ] ,
183- loser_tree_adjusted : false ,
184162 batch_size,
185163 fetch,
186164 produced : 0 ,
187- uninitiated_partitions : ( 0 ..stream_count) . collect ( ) ,
188165 enable_round_robin_tie_breaker,
189166 }
190167 }
191168
169+ pub ( crate ) fn into_stream ( self ) -> SendableRecordBatchStream
170+ where
171+ C : ' static ,
172+ {
173+ let schema_clone = Arc :: clone ( self . in_progress . schema ( ) ) ;
174+
175+ let cloned_metrics = self . metrics . clone ( ) ;
176+
177+ let stream = Box :: pin ( RecordBatchStreamAdapter :: new (
178+ schema_clone,
179+ self . create_stream ( ) ,
180+ ) ) ;
181+
182+ Box :: pin ( ObservedStream :: new ( stream, cloned_metrics, None ) )
183+ }
184+
192185 /// If the stream at the given index is not exhausted, and the last cursor for the
193186 /// stream is finished, poll the stream for the next RecordBatch and create a new
194187 /// cursor for the stream from the returned result
@@ -219,90 +212,88 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
219212 result
220213 }
221214
222- fn poll_next_inner (
223- & mut self ,
224- cx : & mut Context < ' _ > ,
225- ) -> Poll < Option < Result < RecordBatch > > > {
226- if self . done {
227- // When `build_record_batch()` hits an i32 offset overflow (e.g.
228- // combined string offsets exceed 2 GB), it emits a partial batch
229- // and keeps the remaining rows in `self.in_progress.indices`.
230- // Drain those leftover rows before terminating the stream,
231- // otherwise they would be silently dropped.
232- // Repeated overflows are fine — each poll emits another partial
233- // batch until `in_progress` is fully drained.
234- if self . drain_in_progress_on_done && !self . in_progress . is_empty ( ) {
235- return Poll :: Ready ( self . emit_in_progress_batch ( ) . transpose ( ) ) ;
236- }
237- return Poll :: Ready ( None ) ;
238- }
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 < _ > > ( ) ;
239220
240- // Once all partitions have set their corresponding cursors for the loser tree,
241- // we skip the following block. Until then, this function may be called multiple
242- // times and can return Poll::Pending if any partition returns Poll::Pending.
243- if self . loser_tree . is_empty ( ) {
244- ready ! ( self . initialize_all_partitions( cx) ) ?;
245- assert_eq ! (
246- self . uninitiated_partitions. len( ) ,
247- 0 ,
248- "all partitions should be initialized"
249- ) ;
221+ poll_fn ( |cx| self . initialize_all_partitions ( & mut uninitiated_partitions, cx) )
222+ . await ?;
223+
224+ assert_eq ! ( uninitiated_partitions. len( ) , 0 ) ;
250225
251226 // If there are no more uninitiated partitions, set up the loser tree and continue
252227 // to the next phase.
253228
254229 // Claim the memory for the uninitiated partitions
255- self . uninitiated_partitions . shrink_to_fit ( ) ;
230+ drop ( uninitiated_partitions ) ;
256231 self . init_loser_tree ( ) ;
257- }
258232
259- // NB timer records time taken on drop, so there are no
260- // calls to `timer.done()` below.
261- let elapsed_compute = self . metrics . elapsed_compute ( ) . clone ( ) ;
262- let _timer = elapsed_compute. timer ( ) ;
233+ // NB timer records time taken on drop, so there are no
234+ // calls to `timer.done()` below.
235+ let elapsed_compute = self . metrics . elapsed_compute ( ) . clone ( ) ;
236+ let mut timer = elapsed_compute. timer ( ) ;
237+
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) ;
244+
245+ // stop sorting if fetch has been reached
246+ if self . fetch_reached ( ) {
247+ break ;
248+ }
249+
250+ if self . in_progress . len ( ) >= self . batch_size
251+ && let Some ( batch) = self . emit_in_progress_batch ( ) ?
252+ {
253+ drop ( timer) ;
254+ emitter. emit ( batch) . await ;
255+ timer = elapsed_compute. timer ( ) ;
256+ }
263257
264- loop {
265- // Adjust the loser tree if necessary, returning control if needed
266- if !self . loser_tree_adjusted {
267258 let winner = self . loser_tree [ 0 ] ;
268259 // Fast path: skip the `maybe_poll_stream` call (and its `Poll`
269260 // plumbing) unless the winner's cursor is exhausted and needs a
270261 // fresh batch — it is live for almost every row.
271262 if self . cursors [ winner] . is_none ( ) {
272- match ready ! ( self . maybe_poll_stream( cx, winner) ) {
273- Ok ( ( ) ) => { }
274- Err ( e) => {
275- self . done = true ;
276- return Poll :: Ready ( Some ( Err ( e) ) ) ;
277- }
278- }
263+ drop ( timer) ;
264+ poll_fn ( |cx| self . maybe_poll_stream ( cx, winner) ) . await ?;
265+ timer = elapsed_compute. timer ( ) ;
279266 }
267+
268+ // Adjusting the loser tree if necessary
280269 self . update_loser_tree ( ) ;
281270 }
282271
283- let stream_idx = self . loser_tree [ 0 ] ;
284- if self . advance_cursors ( stream_idx) {
285- self . loser_tree_adjusted = false ;
286- self . in_progress . push_row ( stream_idx) ;
272+ drop ( timer) ;
287273
288- // stop sorting if fetch has been reached
289- if self . fetch_reached ( ) {
290- self . done = true ;
291- self . drain_in_progress_on_done = true ;
292- } else if self . in_progress . len ( ) < self . batch_size {
293- continue ;
294- }
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 ;
295283 }
296-
297- return Poll :: Ready ( self . emit_in_progress_batch ( ) . transpose ( ) ) ;
298- }
284+ Ok ( ( ) )
285+ } )
299286 }
300287
301288 /// Initialize all partitions, return `Poll::Pending` if any partition returns `Poll::Pending`
302289 ///
303290 /// This DOES NOT return `Poll::Pending` as soon as the first uninitiated partition returns `Poll::Pending`
304291 /// so we can continue to initialize the remaining partitions
305- fn initialize_all_partitions ( & mut self , cx : & mut Context ) -> Poll < Result < ( ) > > {
292+ fn initialize_all_partitions (
293+ & mut self ,
294+ uninitiated_partitions : & mut Vec < usize > ,
295+ cx : & mut Context ,
296+ ) -> Poll < Result < ( ) > > {
306297 assert_eq ! (
307298 self . loser_tree. len( ) ,
308299 0 ,
@@ -311,11 +302,10 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
311302
312303 // Manual indexing since we're iterating over the vector and shrinking it in the loop
313304 let mut idx = 0 ;
314- while idx < self . uninitiated_partitions . len ( ) {
315- let partition_idx = self . uninitiated_partitions [ idx] ;
305+ while idx < uninitiated_partitions. len ( ) {
306+ let partition_idx = uninitiated_partitions[ idx] ;
316307 match self . maybe_poll_stream ( cx, partition_idx) {
317308 Poll :: Ready ( Err ( e) ) => {
318- self . done = true ;
319309 return Poll :: Ready ( Err ( e) ) ;
320310 }
321311 Poll :: Pending => {
@@ -331,12 +321,12 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
331321 // place which we'll try in the next loop iteration
332322 // swap_remove will change the partition poll order, but that shouldn't
333323 // make a difference since we're waiting for all streams to be ready.
334- self . uninitiated_partitions . swap_remove ( idx) ;
324+ uninitiated_partitions. swap_remove ( idx) ;
335325 }
336326 }
337327 }
338328
339- if self . uninitiated_partitions . is_empty ( ) {
329+ if uninitiated_partitions. is_empty ( ) {
340330 Poll :: Ready ( Ok ( ( ) ) )
341331 } else {
342332 // There are still uninitiated partitions so return pending.
@@ -474,7 +464,6 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
474464 }
475465 self . loser_tree [ cmp_node] = winner;
476466 }
477- self . loser_tree_adjusted = true ;
478467 }
479468
480469 /// Resets the poll count by incrementing the reset epoch.
@@ -586,25 +575,6 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
586575 }
587576
588577 self . loser_tree [ 0 ] = winner;
589- self . loser_tree_adjusted = true ;
590- }
591- }
592-
593- impl < C : CursorValues + Unpin > Stream for SortPreservingMergeStream < C > {
594- type Item = Result < RecordBatch > ;
595-
596- fn poll_next (
597- mut self : Pin < & mut Self > ,
598- cx : & mut Context < ' _ > ,
599- ) -> Poll < Option < Self :: Item > > {
600- let poll = self . poll_next_inner ( cx) ;
601- self . metrics . record_poll ( poll)
602- }
603- }
604-
605- impl < C : CursorValues + Unpin > RecordBatchStream for SortPreservingMergeStream < C > {
606- fn schema ( & self ) -> SchemaRef {
607- Arc :: clone ( self . in_progress . schema ( ) )
608578 }
609579}
610580
@@ -618,7 +588,7 @@ mod tests {
618588 use datafusion_execution:: memory_pool:: {
619589 MemoryConsumer , MemoryPool , UnboundedMemoryPool ,
620590 } ;
621- use futures:: task :: noop_waker_ref ;
591+ use futures:: TryStreamExt ;
622592 use std:: cmp:: Ordering ;
623593
624594 #[ derive( Debug ) ]
@@ -661,8 +631,8 @@ mod tests {
661631 }
662632 }
663633
664- #[ test]
665- fn test_done_drains_buffered_rows ( ) {
634+ #[ tokio :: test]
635+ async fn test_done_drains_buffered_rows ( ) {
666636 let schema = Arc :: new ( Schema :: new ( vec ! [ Field :: new( "i" , DataType :: Int32 , false ) ] ) ) ;
667637 let pool: Arc < dyn MemoryPool > = Arc :: new ( UnboundedMemoryPool :: default ( ) ) ;
668638 let reservation = MemoryConsumer :: new ( "test" ) . register ( & pool) ;
@@ -678,24 +648,20 @@ mod tests {
678648 true ,
679649 ) ;
680650
651+ // Simulate rows left buffered in `in_progress` (as happens when
652+ // `build_record_batch` emits a partial batch on offset overflow). With
653+ // an empty input stream the merge loop breaks immediately, so the only
654+ // way these rows reach the consumer is the generator's final drain loop.
681655 let batch =
682656 RecordBatch :: try_new ( schema, vec ! [ Arc :: new( Int32Array :: from( vec![ 1 ] ) ) ] )
683657 . unwrap ( ) ;
684658 stream. in_progress . push_batch ( 0 , batch) . unwrap ( ) ;
685659 stream. in_progress . push_row ( 0 ) ;
686- stream. done = true ;
687- stream. drain_in_progress_on_done = true ;
688660
689- let waker = noop_waker_ref ( ) ;
690- let mut cx = Context :: from_waker ( waker ) ;
661+ // Drive the actual stream and confirm the buffered row is drained.
662+ let batches : Vec < RecordBatch > = stream . into_stream ( ) . try_collect ( ) . await . unwrap ( ) ;
691663
692- match stream. poll_next_inner ( & mut cx) {
693- Poll :: Ready ( Some ( Ok ( batch) ) ) => assert_eq ! ( batch. num_rows( ) , 1 ) ,
694- other => {
695- panic ! ( "expected buffered rows to be drained after done, got {other:?}" )
696- }
697- }
698- assert ! ( stream. in_progress. is_empty( ) ) ;
699- assert ! ( matches!( stream. poll_next_inner( & mut cx) , Poll :: Ready ( None ) ) ) ;
664+ assert_eq ! ( batches. len( ) , 1 ) ;
665+ assert_eq ! ( batches[ 0 ] . num_rows( ) , 1 ) ;
700666 }
701667}
0 commit comments