Skip to content

Commit 096012e

Browse files
authored
chore: Simplifying SortPreservingMergeStream to use generators instead of state machine (#23407)
## Which issue does this PR close? - N/A ## Rationale for this change I'm trying to make some Sort optimization but it is hard to get stuff merged where the code is already complex even if adding a simple optimization (like when only 1 stream is left just return those batches). This makes the code simpler as you can now read it in straight line flow control, while not sacrificing performance I did not use `RecordBatchReceiverStreamBuilder` since I want pull based and not push based stream ## What changes are included in this PR? Added `genawaiter` dependency, replace the SortPersevingMergeStream main state machine loop with generator yield ## Are these changes tested? existing tests ## Are there any user-facing changes? no ----- ## Why not using `async-stream` crate from tokio? **Why not using `async-stream` crate from tokio (that we already have transitive dependency on) or other crates that are macro based.** Because couple of reasons: 1. `cargo fmt` does not format macros body, so you manually need to format and **validate** that the style is kept 2. more "magic" `yield` is not a function call i. When you read the code, you cant go to definition of the `yield` keyword since it is not a function ii. Cant put debugger on that keyword (from what I remember) iii. there is some hidden code that you need to 3. You can only use `yield` from the macro body (so you cant extract functions with `yield` for example)
1 parent 5340653 commit 096012e

3 files changed

Lines changed: 102 additions & 132 deletions

File tree

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
// under the License.
1717

1818
use std::cmp::Ordering;
19+
use std::fmt::Debug;
1920
use std::sync::Arc;
2021

2122
use arrow::array::{
@@ -32,7 +33,7 @@ use datafusion_execution::memory_pool::MemoryReservation;
3233
///
3334
/// This is a trait as there are several specialized implementations, such as for
3435
/// single columns or for normalized multi column keys ([`Rows`])
35-
pub trait CursorValues {
36+
pub trait CursorValues: Debug + Sync + Send {
3637
fn len(&self) -> usize;
3738

3839
/// Returns true if `l[l_idx] == r[r_idx]`
@@ -298,6 +299,7 @@ impl<T: ArrowNativeTypeOp> CursorValues for PrimitiveValues<T> {
298299
}
299300
}
300301

302+
#[derive(Debug)]
301303
pub struct ByteArrayValues<T: OffsetSizeTrait> {
302304
offsets: OffsetBuffer<T>,
303305
values: Buffer,

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

Lines changed: 93 additions & 127 deletions
Original file line numberDiff line numberDiff line change
@@ -18,21 +18,23 @@
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;
2223
use 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;
2627
use crate::metrics::BaselineMetrics;
2728
use crate::sorts::builder::BatchBuilder;
2829
use crate::sorts::cursor::{Cursor, CursorValues};
2930
use crate::sorts::stream::PartitionedStream;
31+
use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
3032

3133
use arrow::datatypes::SchemaRef;
3234
use arrow::record_batch::RecordBatch;
3335
use datafusion_common::Result;
36+
use datafusion_execution::async_try_stream;
3437
use datafusion_execution::memory_pool::MemoryReservation;
35-
3638
use 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

158139
impl<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

Comments
 (0)