Skip to content

Commit 77b172e

Browse files
authored
chore: simplify SortPreservingMergeStream to be as textbook-like as possible (#23702)
## Which issue does this PR close? N/A ## Rationale for this change `SortPreservingMergeStream` is a little complex, so add some guiding comments and make it as textbook-like as possible ## What changes are included in this PR? Added comments, reorder code While this was done this also fixed couple of bugs due to how it work: 1. leftover drain was not counted in the `elapsed_compute` 2. `limit(0)` returns 0 rows and not 1 ## Are these changes tested? Existing tests ## Are there any user-facing changes? Not API ones. `limit(0)` now returns 0 rows
1 parent 7576762 commit 77b172e

2 files changed

Lines changed: 220 additions & 60 deletions

File tree

‎datafusion/physical-plan/src/sorts/merge.rs‎

Lines changed: 100 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -32,9 +32,9 @@ use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
3232

3333
use arrow::datatypes::SchemaRef;
3434
use 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};
3736
use datafusion_execution::memory_pool::MemoryReservation;
37+
use datafusion_execution::{TryEmitter, async_try_stream};
3838
use 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`.

‎datafusion/physical-plan/src/sorts/streaming_merge.rs‎

Lines changed: 120 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ use crate::sorts::{
2424
merge::SortPreservingMergeStream,
2525
stream::{FieldCursorStream, RowCursorStream},
2626
};
27-
use crate::{SendableRecordBatchStream, SpillManager};
27+
use crate::{EmptyRecordBatchStream, SendableRecordBatchStream, SpillManager};
2828
use arrow::array::*;
2929
use arrow::datatypes::{DataType, SchemaRef};
3030
use datafusion_common::human_readable_size;
@@ -195,13 +195,22 @@ impl<'a> StreamingMergeBuilder<'a> {
195195
let Some(expressions) = expressions else {
196196
return internal_err!("Sort expressions cannot be empty for streaming merge");
197197
};
198+
let schema = schema.expect("Schema cannot be empty for streaming merge");
199+
200+
if fetch.is_some_and(|fetch| fetch == 0) {
201+
return Ok(Box::pin(EmptyRecordBatchStream::new(schema)));
202+
}
203+
204+
let batch_size =
205+
batch_size.expect("Batch size cannot be empty for streaming merge");
206+
207+
if batch_size == 0 {
208+
return internal_err!("Batch size cannot be zero for streaming merge");
209+
}
198210

199211
if !sorted_spill_files.is_empty() {
200212
// Unwrapping mandatory fields
201-
let schema = schema.expect("Schema cannot be empty for streaming merge");
202213
let metrics = metrics.expect("Metrics cannot be empty for streaming merge");
203-
let batch_size =
204-
batch_size.expect("Batch size cannot be empty for streaming merge");
205214
let reservation =
206215
reservation.expect("Reservation cannot be empty for streaming merge");
207216

@@ -227,10 +236,7 @@ impl<'a> StreamingMergeBuilder<'a> {
227236
);
228237

229238
// Unwrapping mandatory fields
230-
let schema = schema.expect("Schema cannot be empty for streaming merge");
231239
let metrics = metrics.expect("Metrics cannot be empty for streaming merge");
232-
let batch_size =
233-
batch_size.expect("Batch size cannot be empty for streaming merge");
234240
let reservation =
235241
reservation.expect("Reservation cannot be empty for streaming merge");
236242

@@ -267,3 +273,110 @@ impl<'a> StreamingMergeBuilder<'a> {
267273
.into_stream())
268274
}
269275
}
276+
277+
#[cfg(test)]
278+
mod tests {
279+
use crate::{common::collect, stream::RecordBatchStreamAdapter};
280+
use std::sync::Arc;
281+
282+
use super::*;
283+
284+
use arrow::array::{ArrayRef, RecordBatch};
285+
use arrow_schema::SortOptions;
286+
use datafusion_common::Result;
287+
use datafusion_execution::TaskContext;
288+
use datafusion_physical_expr::{PhysicalSortExpr, expressions::col};
289+
use datafusion_physical_expr_common::metrics::{
290+
ExecutionPlanMetricsSet, SpillMetrics,
291+
};
292+
293+
#[tokio::test]
294+
async fn test_sort_merge_fetch_zero_with_only_1_stream() {
295+
test_fetch_0_should_output_0_rows(1, 0).await.unwrap();
296+
}
297+
#[tokio::test]
298+
async fn test_sort_merge_fetch_zero_with_2_streams() {
299+
test_fetch_0_should_output_0_rows(2, 0).await.unwrap();
300+
}
301+
#[tokio::test]
302+
async fn test_sort_merge_fetch_zero_with_only_1_spill_file() {
303+
test_fetch_0_should_output_0_rows(0, 1).await.unwrap();
304+
}
305+
#[tokio::test]
306+
async fn test_sort_merge_fetch_zero_with_2_spill_files() {
307+
test_fetch_0_should_output_0_rows(0, 2).await.unwrap();
308+
}
309+
#[tokio::test]
310+
async fn test_sort_merge_fetch_zero_with_1_stream_and_1_spill_file() {
311+
test_fetch_0_should_output_0_rows(1, 1).await.unwrap();
312+
}
313+
314+
async fn test_fetch_0_should_output_0_rows(
315+
number_of_streams: usize,
316+
number_of_spilled_files: usize,
317+
) -> Result<()> {
318+
let task_ctx = Arc::new(TaskContext::default());
319+
let a: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 7, 9, 3]));
320+
let b: ArrayRef = Arc::new(StringArray::from(vec!["a", "b", "c", "d", "e"]));
321+
let batch = RecordBatch::try_from_iter(vec![("a", a), ("b", b)]).unwrap();
322+
let schema = batch.schema();
323+
324+
let sort: LexOrdering = [PhysicalSortExpr {
325+
expr: col("b", &schema).unwrap(),
326+
options: SortOptions {
327+
descending: false,
328+
nulls_first: true,
329+
},
330+
}]
331+
.into();
332+
333+
let streams = (0..number_of_streams)
334+
.map(|_| {
335+
Box::pin(RecordBatchStreamAdapter::new(
336+
Arc::clone(&schema),
337+
futures::stream::iter(vec![Ok(batch.clone())]),
338+
)) as SendableRecordBatchStream
339+
})
340+
.collect::<Vec<SendableRecordBatchStream>>();
341+
342+
let spill_manager = SpillManager::new(
343+
task_ctx.runtime_env(),
344+
SpillMetrics::new(&ExecutionPlanMetricsSet::new(), 0),
345+
Arc::clone(&schema),
346+
);
347+
348+
let mut sorted_spill_files: Vec<SortedSpillFile> = vec![];
349+
350+
for _ in 0..number_of_spilled_files {
351+
let file = spill_manager
352+
.spill_record_batch_and_finish(std::slice::from_ref(&batch), "spill")
353+
.unwrap()
354+
.unwrap();
355+
sorted_spill_files.push(SortedSpillFile {
356+
file,
357+
max_record_batch_memory: batch.get_array_memory_size(),
358+
});
359+
}
360+
361+
let sorted_output_stream = StreamingMergeBuilder::new()
362+
.with_batch_size(100)
363+
.with_metrics(BaselineMetrics::new(&ExecutionPlanMetricsSet::new(), 0))
364+
// Just to avoid having to provide memory pool
365+
.with_bypass_mempool()
366+
.with_schema(schema)
367+
.with_streams(streams)
368+
.with_sorted_spill_files(sorted_spill_files)
369+
.with_spill_manager(spill_manager)
370+
.with_expressions(&sort)
371+
// The whole point of the test - fetch is 0
372+
.with_fetch(Some(0))
373+
.build()
374+
.unwrap();
375+
376+
let collected = collect(sorted_output_stream).await.unwrap();
377+
let total: usize = collected.iter().map(|b| b.num_rows()).sum();
378+
assert_eq!(total, 0, "fetch=Some(0) must emit zero rows, got {total}");
379+
380+
Ok(())
381+
}
382+
}

0 commit comments

Comments
 (0)