You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/07/26 20:10:35 UTC
(datafusion) branch main updated: chore: simplify SortPreservingMergeStream to be as textbook-like as possible (#23702)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/main by this push:
new 77b172e150 chore: simplify SortPreservingMergeStream to be as textbook-like as possible (#23702)
77b172e150 is described below
commit 77b172e1505283f9ac6af050ee8547f910c28262
Author: Raz Luvaton <16...@users.noreply.github.com>
AuthorDate: Sun Jul 26 22:55:27 2026 +0300
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
---
datafusion/physical-plan/src/sorts/merge.rs | 153 ++++++++++++++-------
.../physical-plan/src/sorts/streaming_merge.rs | 127 ++++++++++++++++-
2 files changed, 220 insertions(+), 60 deletions(-)
diff --git a/datafusion/physical-plan/src/sorts/merge.rs b/datafusion/physical-plan/src/sorts/merge.rs
index 986da549f7..310416c22d 100644
--- a/datafusion/physical-plan/src/sorts/merge.rs
+++ b/datafusion/physical-plan/src/sorts/merge.rs
@@ -32,9 +32,9 @@ use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
use arrow::datatypes::SchemaRef;
use arrow::record_batch::RecordBatch;
-use datafusion_common::Result;
-use datafusion_execution::async_try_stream;
+use datafusion_common::{DataFusionError, Result, assert_or_internal_err, internal_err};
use datafusion_execution::memory_pool::MemoryReservation;
+use datafusion_execution::{TryEmitter, async_try_stream};
use futures::Stream;
/// A fallible [`PartitionedStream`] of [`Cursor`] and [`RecordBatch`]
@@ -146,6 +146,9 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
reservation: MemoryReservation,
enable_round_robin_tie_breaker: bool,
) -> Self {
+ assert_ne!(batch_size, 0, "batch size cannot be 0");
+ assert_ne!(fetch, Some(0), "fetch must not be Some(0)");
+
let stream_count = streams.partitions();
Self {
@@ -173,7 +176,6 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
let schema_clone = Arc::clone(self.in_progress.schema());
let cloned_metrics = self.metrics.clone();
-
let stream = Box::pin(RecordBatchStreamAdapter::new(
schema_clone,
self.create_stream(),
@@ -212,79 +214,122 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
result
}
- fn create_stream(mut self) -> impl Stream<Item = Result<RecordBatch>> {
- async_try_stream(|mut emitter| async move {
- // This vector contains the indices of the partitions that have not started emitting yet.
- let mut uninitiated_partitions =
- (0..self.streams.partitions()).collect::<Vec<_>>();
+ async fn flush_in_progress(
+ &mut self,
+ mut emitter: TryEmitter<RecordBatch, DataFusionError>,
+ ) -> Result<()> {
+ if self.in_progress.is_empty() {
+ return Ok(());
+ }
- poll_fn(|cx| self.initialize_all_partitions(&mut uninitiated_partitions, cx))
- .await?;
+ let elapsed_compute = self.metrics.elapsed_compute().clone();
+ let mut timer = elapsed_compute.timer();
+
+ // When `build_record_batch()` hits an i32 offset overflow (e.g.
+ // combined string offsets exceed 2 GB), it emits a partial batch
+ // and keeps the remaining rows in `self.in_progress.indices`.
+ // Drain those leftover rows before terminating the stream,
+ // otherwise they would be silently dropped.
+ // Repeated overflows are fine — each poll emits another partial
+ // batch until `in_progress` is fully drained.
+ while let Some(batch) = self.emit_in_progress_batch()? {
+ drop(timer);
+ emitter.emit(batch).await;
+ timer = elapsed_compute.timer();
+ }
- assert_eq!(uninitiated_partitions.len(), 0);
+ Ok(())
+ }
- // If there are no more uninitiated partitions, set up the loser tree and continue
- // to the next phase.
+ fn create_stream(mut self) -> impl Stream<Item = Result<RecordBatch>> {
+ async_try_stream(|mut emitter| async move {
+ // 1. Make sure we have data from each stream so we can initialize the loser tree
+ {
+ // This vector contains the indices of the partitions that have not started emitting yet.
+ let mut uninitiated_partitions =
+ (0..self.streams.partitions()).collect::<Vec<_>>();
+
+ poll_fn(|cx| {
+ self.initialize_all_partitions(&mut uninitiated_partitions, cx)
+ })
+ .await?;
- // Claim the memory for the uninitiated partitions
- drop(uninitiated_partitions);
- self.init_loser_tree();
+ assert_eq!(uninitiated_partitions.len(), 0);
+ }
- // NB timer records time taken on drop, so there are no
- // calls to `timer.done()` below.
let elapsed_compute = self.metrics.elapsed_compute().clone();
let mut timer = elapsed_compute.timer();
- loop {
- let stream_idx = self.loser_tree[0];
- if !self.advance_cursors(stream_idx) {
- break;
- }
- self.in_progress.push_row(stream_idx);
+ // 2. Init loser tree
+ self.init_loser_tree();
- // stop sorting if fetch has been reached
+ // 3. loop until all streams have been exhausted
+ while !self.is_exhausted() {
+ // 3.1. add loser_tree[0] (minimum) stream to pending record batch
+ let winner_stream = self.loser_tree[0];
+ self.in_progress.push_row(winner_stream);
+
+ // 3.2. If the new row reached the limit
if self.fetch_reached() {
break;
}
- if self.in_progress.len() >= self.batch_size
- && let Some(batch) = self.emit_in_progress_batch()?
- {
+ // 3.3. if there is enough to emit for a full record batch
+ if self.in_progress.len() >= self.batch_size {
+ // 3.3.1 build pending record batch and reset builder
+ let Some(batch) = self.emit_in_progress_batch()? else {
+ return internal_err!("must have batch in progress to emit");
+ };
+
+ // 3.3.2 emit pending record batch
drop(timer);
emitter.emit(batch).await;
timer = elapsed_compute.timer();
}
- let winner = self.loser_tree[0];
- // Fast path: skip the `maybe_poll_stream` call (and its `Poll`
- // plumbing) unless the winner's cursor is exhausted and needs a
- // fresh batch — it is live for almost every row.
- if self.cursors[winner].is_none() {
- drop(timer);
- poll_fn(|cx| self.maybe_poll_stream(cx, winner)).await?;
- timer = elapsed_compute.timer();
+ // 3.4. advance cursor for the winner stream
+ {
+ let should_poll_next_batch_for_stream =
+ self.advance_cursors(winner_stream);
+
+ // Fast path: skip the `maybe_poll_stream` call (and its `Poll`
+ // plumbing) unless the winner's cursor is exhausted and needs a
+ // fresh batch — it is live for almost every row.
+ if should_poll_next_batch_for_stream {
+ assert_or_internal_err!(
+ self.cursors[winner_stream].is_none(),
+ "cursor should be exhausted"
+ );
+
+ drop(timer);
+ poll_fn(|cx| self.maybe_poll_stream(cx, winner_stream)).await?;
+ timer = elapsed_compute.timer();
+ }
}
- // Adjusting the loser tree if necessary
+ // 3.5. Adjusting the loser tree if necessary
self.update_loser_tree();
}
- drop(timer);
+ // 4. Flush any remaining rows in `self.in_progress`
+ self.flush_in_progress(emitter).await?;
- // When `build_record_batch()` hits an i32 offset overflow (e.g.
- // combined string offsets exceed 2 GB), it emits a partial batch
- // and keeps the remaining rows in `self.in_progress.indices`.
- // Drain those leftover rows before terminating the stream,
- // otherwise they would be silently dropped.
- // Repeated overflows are fine — each poll emits another partial
- // batch until `in_progress` is fully drained.
- while let Some(batch) = self.emit_in_progress_batch()? {
- emitter.emit(batch).await;
- }
Ok(())
})
}
+ /// Returns `true` once every input stream is exhausted.
+ ///
+ /// Should only be called for valid adjusted tree, i.e. the initial tree or after [`Self::update_loser_tree`] call
+ fn is_exhausted(&self) -> bool {
+ let winner = self.loser_tree[0];
+
+ // Checking only the tree root suffices for valid tree
+ // since the winner of the tree cannot be an exhausted stream for a valid tree
+ // as what value is winning over the non exhausted stream?
+ self.cursors[winner].is_none()
+ }
+
/// Initialize all partitions, return `Poll::Pending` if any partition returns `Poll::Pending`
///
/// 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> {
/// Advances the actual cursor. If it reaches its end, update the
/// previous cursor with it.
///
- /// If the given partition is not exhausted, the function returns `true`.
+ /// If the given partition batch is exhausted, return `true` to signal a poll is needed
fn advance_cursors(&mut self, stream_idx: usize) -> bool {
if let Some(cursor) = &mut self.cursors[stream_idx] {
let _ = cursor.advance();
- if cursor.is_finished() {
+ let finished = cursor.is_finished();
+ if finished {
// Take the current cursor, leaving `None` in its place
self.prev_cursors[stream_idx] = self.cursors[stream_idx].take();
}
- true
- } else {
- false
+ return finished;
}
+
+ // the entire stream is exhausted, so return true (poll won't help here anyway)
+ true
}
/// Returns `true` if the cursor at index `a` is greater than at index `b`.
diff --git a/datafusion/physical-plan/src/sorts/streaming_merge.rs b/datafusion/physical-plan/src/sorts/streaming_merge.rs
index e96138ef13..81adad8e9e 100644
--- a/datafusion/physical-plan/src/sorts/streaming_merge.rs
+++ b/datafusion/physical-plan/src/sorts/streaming_merge.rs
@@ -24,7 +24,7 @@ use crate::sorts::{
merge::SortPreservingMergeStream,
stream::{FieldCursorStream, RowCursorStream},
};
-use crate::{SendableRecordBatchStream, SpillManager};
+use crate::{EmptyRecordBatchStream, SendableRecordBatchStream, SpillManager};
use arrow::array::*;
use arrow::datatypes::{DataType, SchemaRef};
use datafusion_common::human_readable_size;
@@ -195,13 +195,22 @@ impl<'a> StreamingMergeBuilder<'a> {
let Some(expressions) = expressions else {
return internal_err!("Sort expressions cannot be empty for streaming merge");
};
+ let schema = schema.expect("Schema cannot be empty for streaming merge");
+
+ if fetch.is_some_and(|fetch| fetch == 0) {
+ return Ok(Box::pin(EmptyRecordBatchStream::new(schema)));
+ }
+
+ let batch_size =
+ batch_size.expect("Batch size cannot be empty for streaming merge");
+
+ if batch_size == 0 {
+ return internal_err!("Batch size cannot be zero for streaming merge");
+ }
if !sorted_spill_files.is_empty() {
// Unwrapping mandatory fields
- let schema = schema.expect("Schema cannot be empty for streaming merge");
let metrics = metrics.expect("Metrics cannot be empty for streaming merge");
- let batch_size =
- batch_size.expect("Batch size cannot be empty for streaming merge");
let reservation =
reservation.expect("Reservation cannot be empty for streaming merge");
@@ -227,10 +236,7 @@ impl<'a> StreamingMergeBuilder<'a> {
);
// Unwrapping mandatory fields
- let schema = schema.expect("Schema cannot be empty for streaming merge");
let metrics = metrics.expect("Metrics cannot be empty for streaming merge");
- let batch_size =
- batch_size.expect("Batch size cannot be empty for streaming merge");
let reservation =
reservation.expect("Reservation cannot be empty for streaming merge");
@@ -267,3 +273,110 @@ impl<'a> StreamingMergeBuilder<'a> {
.into_stream())
}
}
+
+#[cfg(test)]
+mod tests {
+ use crate::{common::collect, stream::RecordBatchStreamAdapter};
+ use std::sync::Arc;
+
+ use super::*;
+
+ use arrow::array::{ArrayRef, RecordBatch};
+ use arrow_schema::SortOptions;
+ use datafusion_common::Result;
+ use datafusion_execution::TaskContext;
+ use datafusion_physical_expr::{PhysicalSortExpr, expressions::col};
+ use datafusion_physical_expr_common::metrics::{
+ ExecutionPlanMetricsSet, SpillMetrics,
+ };
+
+ #[tokio::test]
+ async fn test_sort_merge_fetch_zero_with_only_1_stream() {
+ test_fetch_0_should_output_0_rows(1, 0).await.unwrap();
+ }
+ #[tokio::test]
+ async fn test_sort_merge_fetch_zero_with_2_streams() {
+ test_fetch_0_should_output_0_rows(2, 0).await.unwrap();
+ }
+ #[tokio::test]
+ async fn test_sort_merge_fetch_zero_with_only_1_spill_file() {
+ test_fetch_0_should_output_0_rows(0, 1).await.unwrap();
+ }
+ #[tokio::test]
+ async fn test_sort_merge_fetch_zero_with_2_spill_files() {
+ test_fetch_0_should_output_0_rows(0, 2).await.unwrap();
+ }
+ #[tokio::test]
+ async fn test_sort_merge_fetch_zero_with_1_stream_and_1_spill_file() {
+ test_fetch_0_should_output_0_rows(1, 1).await.unwrap();
+ }
+
+ async fn test_fetch_0_should_output_0_rows(
+ number_of_streams: usize,
+ number_of_spilled_files: usize,
+ ) -> Result<()> {
+ let task_ctx = Arc::new(TaskContext::default());
+ let a: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 7, 9, 3]));
+ let b: ArrayRef = Arc::new(StringArray::from(vec!["a", "b", "c", "d", "e"]));
+ let batch = RecordBatch::try_from_iter(vec![("a", a), ("b", b)]).unwrap();
+ let schema = batch.schema();
+
+ let sort: LexOrdering = [PhysicalSortExpr {
+ expr: col("b", &schema).unwrap(),
+ options: SortOptions {
+ descending: false,
+ nulls_first: true,
+ },
+ }]
+ .into();
+
+ let streams = (0..number_of_streams)
+ .map(|_| {
+ Box::pin(RecordBatchStreamAdapter::new(
+ Arc::clone(&schema),
+ futures::stream::iter(vec![Ok(batch.clone())]),
+ )) as SendableRecordBatchStream
+ })
+ .collect::<Vec<SendableRecordBatchStream>>();
+
+ let spill_manager = SpillManager::new(
+ task_ctx.runtime_env(),
+ SpillMetrics::new(&ExecutionPlanMetricsSet::new(), 0),
+ Arc::clone(&schema),
+ );
+
+ let mut sorted_spill_files: Vec<SortedSpillFile> = vec![];
+
+ for _ in 0..number_of_spilled_files {
+ let file = spill_manager
+ .spill_record_batch_and_finish(std::slice::from_ref(&batch), "spill")
+ .unwrap()
+ .unwrap();
+ sorted_spill_files.push(SortedSpillFile {
+ file,
+ max_record_batch_memory: batch.get_array_memory_size(),
+ });
+ }
+
+ let sorted_output_stream = StreamingMergeBuilder::new()
+ .with_batch_size(100)
+ .with_metrics(BaselineMetrics::new(&ExecutionPlanMetricsSet::new(), 0))
+ // Just to avoid having to provide memory pool
+ .with_bypass_mempool()
+ .with_schema(schema)
+ .with_streams(streams)
+ .with_sorted_spill_files(sorted_spill_files)
+ .with_spill_manager(spill_manager)
+ .with_expressions(&sort)
+ // The whole point of the test - fetch is 0
+ .with_fetch(Some(0))
+ .build()
+ .unwrap();
+
+ let collected = collect(sorted_output_stream).await.unwrap();
+ let total: usize = collected.iter().map(|b| b.num_rows()).sum();
+ assert_eq!(total, 0, "fetch=Some(0) must emit zero rows, got {total}");
+
+ Ok(())
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org