Re: [PR] Improve EnforceSorting docs. [datafusion]

via GitHub Sat, 15 Feb 2025 02:07:10 -0800


alamb commented on code in PR #14673:
URL: https://github.com/apache/datafusion/pull/14673#discussion_r1957081251



##########
datafusion/physical-optimizer/src/enforce_sorting/mod.rs:
##########
@@ -151,10 +163,15 @@ fn update_coalesce_ctx_children(
     };
 }
 
-/// The boolean flag `repartition_sorts` defined in the config indicates
-/// whether we elect to transform [`CoalescePartitionsExec`] + [`SortExec`] 
cascades
-/// into [`SortExec`] + [`SortPreservingMergeExec`] cascades, which enables us 
to
-/// perform sorting in parallel.
+/// Performs optimizations based upon a series of subrules.

Review Comment:
   👍 



##########
datafusion/physical-optimizer/src/enforce_sorting/mod.rs:
##########
@@ -243,20 +260,66 @@ fn replace_with_partial_sort(
     Ok(plan)
 }
 
-/// This function turns plans of the form
+/// Transform [`CoalescePartitionsExec`] + [`SortExec`] into
+/// [`SortExec`] + [`SortPreservingMergeExec`] as illustrated below:
+///
+/// The [`CoalescePartitionsExec`] + [`SortExec`] cascades
+/// combine the partitions first, and then sort:
+/// ```text
+///   ┌ ─ ─ ─ ─ ─ ┐                                                            
                       
+///    ┌─┬─┬─┐                                                                 
                       
+///   ││B│A│D│... ├──┐                                                         
                       
+///    └─┴─┴─┘       │                                                         
                       
+///   └ ─ ─ ─ ─ ─ ┘  │  ┌────────────────────────┐   ┌ ─ ─ ─ ─ ─ ─ ┐   
┌────────┐    ┌ ─ ─ ─ ─ ─ ─ ─ ┐
+///    Partition 1   │  │        Coalesce        │    ┌─┬─┬─┬─┬─┐      │       
 │     ┌─┬─┬─┬─┬─┐     
+///                  ├──▶(no ordering guarantees)│──▶││B│E│A│D│C│...───▶  Sort 
 ├───▶││A│B│C│D│E│... │
+///                  │  │                        │    └─┴─┴─┴─┴─┘      │       
 │     └─┴─┴─┴─┴─┘     
+///   ┌ ─ ─ ─ ─ ─ ┐  │  └────────────────────────┘   └ ─ ─ ─ ─ ─ ─ ┘   
└────────┘    └ ─ ─ ─ ─ ─ ─ ─ ┘
+///    ┌─┬─┐         │                                 Partition               
        Partition      
+///   ││E│C│ ...  ├──┘                                                         
                       
+///    └─┴─┘                                                                   
                       
+///   └ ─ ─ ─ ─ ─ ┘                                                            
                       
+///    Partition 2                                                             
                       
+/// ```                                                                        
                         
+///
+///
+/// The [`SortExec`] + [`SortPreservingMergeExec`] cascades
+/// sorts each partition first, then merge partitions while retaining the sort:
+/// ```text
+///   ┌ ─ ─ ─ ─ ─ ┐   ┌────────┐   ┌ ─ ─ ─ ─ ─ ┐                               
                  
+///    ┌─┬─┬─┐        │        │    ┌─┬─┬─┐                                    
                  
+///   ││B│A│D│... │──▶│  Sort  │──▶││A│B│D│... │──┐                            
                  
+///    └─┴─┴─┘        │        │    └─┴─┴─┘       │                            
                  
+///   └ ─ ─ ─ ─ ─ ┘   └────────┘   └ ─ ─ ─ ─ ─ ┘  │  ┌─────────────────────┐   
 ┌ ─ ─ ─ ─ ─ ─ ─ ┐
+///    Partition 1                  Partition 1   │  │                     │   
  ┌─┬─┬─┬─┬─┐     
+///                                               ├──▶ SortPreservingMerge 
├───▶││A│B│C│D│E│... │
+///                                               │  │                     │   
  └─┴─┴─┴─┴─┘     
+///   ┌ ─ ─ ─ ─ ─ ┐   ┌────────┐   ┌ ─ ─ ─ ─ ─ ┐  │  └─────────────────────┘   
 └ ─ ─ ─ ─ ─ ─ ─ ┘
+///    ┌─┬─┐          │        │    ┌─┬─┐         │                            
   Partition      
+///   ││E│C│ ...  │──▶│  Sort  ├──▶││C│E│ ...  │──┘                            
                  
+///    └─┴─┘          │        │    └─┴─┘                                      
                  
+///   └ ─ ─ ─ ─ ─ ┘   └────────┘   └ ─ ─ ─ ─ ─ ┘                               
                  
+///    Partition 2                  Partition 2                                
                  
+/// ```
+///
+/// The latter [`SortExec`] + [`SortPreservingMergeExec`] cascade performs the
+/// sort first on a per-partition basis, thereby parallelizing the sort.
+///
+///
+/// The outcome is that plans of the form

Review Comment:
   nice



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] Improve EnforceSorting docs. [datafusion]

Reply via email to