This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-24048-f9dde71ec315833ea0bc39bd63104e613109e915 in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 882d90658a9334c3205c7994ac15b7c25163864c Author: Andrew Lamb <[email protected]> AuthorDate: Mon Aug 3 17:45:34 2026 -0400 docs: Add more documentation about `PartialSortExec` operator (#24048) ## Which issue does this PR close? N/A ## Rationale for this change I was trying to explain to someone recently how PartialSortExec works, and I found the datafusion docs weren't quite as explicit about the befits as I wanted ## What changes are included in this PR? 1. Update the PartialSortExec documentation to explain the streaming and memory implications better, and add a worked buffering example ## Are these changes tested? By CI ## Are there any user-facing changes? Better docs --------- Co-authored-by: Yongting You <[email protected]> --- datafusion/physical-plan/src/sorts/partial_sort.rs | 83 +++++++++++++++++++--- 1 file changed, 75 insertions(+), 8 deletions(-) diff --git a/datafusion/physical-plan/src/sorts/partial_sort.rs b/datafusion/physical-plan/src/sorts/partial_sort.rs index 3a4ddd2fbe..44e2b20adc 100644 --- a/datafusion/physical-plan/src/sorts/partial_sort.rs +++ b/datafusion/physical-plan/src/sorts/partial_sort.rs @@ -80,9 +80,9 @@ use log::trace; /// Sort execution plan for inputs that are already partially sorted. /// /// This operator takes input ordered by a prefix of the required ordering, and -/// produces output ordered by the required ordering. This is useful for -/// unbounded or large inputs where a [`SortExec`] must buffer all rows before -/// producing any output. +/// produces output ordered by the required ordering, emitting rows sooner +/// (streaming) and using less peak memory than [`SortExec`] which must buffer +/// all rows before producing any output. /// /// [`PartialSortExec`] relies on the property that rows with the same sort /// prefix are contiguous, so it can sort one prefix group at a time, emitting @@ -98,15 +98,82 @@ use log::trace; /// +---+---+---+ +---+---+---+ /// | a | b | c | | a | b | c | /// +---+---+---+ +---+---+---+ -/// | 0 | 0 | 3 | -- same group --> | 0 | 0 | 2 | -/// | 0 | 0 | 2 | | 0 | 0 | 3 | -/// | 0 | 1 | 1 | -- single row --> | 0 | 1 | 1 | -/// | 0 | 2 | 4 | -- same group --> | 0 | 2 | 0 | +/// | 0 | 0 | 3 | -- new group --> | 0 | 0 | 1 | +/// | 0 | 0 | 2 | | 0 | 0 | 2 | +/// | 0 | 0 | 1 | | 0 | 0 | 3 | +/// | 0 | 1 | 1 | -- new group --> | 0 | 1 | 1 | +/// | 0 | 2 | 4 | -- new group --> | 0 | 2 | 0 | /// | 0 | 2 | 0 | | 0 | 2 | 4 | -/// | 1 | 0 | 5 | -- single row --> | 1 | 0 | 5 | +/// | 1 | 0 | 5 | -- new group --> | 1 | 0 | 5 | /// +---+---+---+ +---+---+---+ /// ``` /// +/// # Buffering and Emitting Rows +/// +/// [`PartialSortExec`] buffers rows only until it can *prove* a prefix group +/// will never be seen again, then sorts and emits buffered rows. A group is +/// guaranteed to never be seen again once a row with a *different* prefix +/// value arrives. This relies on the input's existing ordering guarantees. +/// +/// Using the example from above, rows accumulate in the in-memory buffer in +/// batches. As long as the `(a, b)` prefix keeps repeating, more rows are +/// buffered. +/// +/// ```text +/// Buffer +/// +---+---+---+ +/// | a | b | c | +/// +---+---+---+ +/// | 0 | 0 | 3 | +/// | 0 | 0 | 2 | +/// | 0 | 0 | 1 | +/// +---+---+---+ +/// ``` +/// +/// Once a batch arrives that contains a new `(a, b)` prefix, e.g. `(0, 2)`: +/// every buffered row for previous prefixes may be emitted: +/// +/// ```text +/// Buffer +/// +---+---+---+ +/// | a | b | c | +/// +---+---+---+ +/// | 0 | 0 | 3 | +/// | 0 | 0 | 2 | +/// | 0 | 0 | 1 | +/// | 0 | 1 | 1 | <-- first row of new batch, new prefix +/// | 0 | 2 | 4 | <-- new prefix +/// | 0 | 2 | 0 | +/// | 1 | 0 | 5 | <-- last row of new batch, new prefix +/// +---+---+---+ +/// ``` +/// +/// Once known complete, the buffered rows are sorted by the full `(a, b, c)` +/// ordering and emitted as a [`RecordBatch`]; Any rows from the most recently +/// seen prefix remain buffered (as more rows with the same prefix may arrive in +/// future batches. +/// +/// ```text +/// Emitted <-- fully sorted on (a, b, c) +/// +---+---+---+ +/// | a | b | c | +/// +---+---+---+ +/// | 0 | 0 | 1 | <-- completed group +/// | 0 | 0 | 2 | +/// | 0 | 0 | 3 | +/// | 0 | 2 | 0 | <-- completed group +/// | 0 | 2 | 4 | +/// | 0 | 1 | 1 | <-- completed group +/// +---+---+---+ +/// +/// Buffer +/// +---+---+---+ +/// | a | b | c | +/// +---+---+---+ +/// | 1 | 0 | 5 | <-- (possibly) in progress group +/// +---+---+---+ +/// ``` +/// /// [`SortExec`]: crate::sorts::sort::SortExec #[derive(Debug, Clone)] pub struct PartialSortExec { --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
