(datafusion) 01/01: docs: Add more documentation about `PartialSortExec` operator (#24048)

[gi...@apache.org]

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 <an...@nerdnetworks.org>
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 <20...@gmail.com>
---
 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: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org