Struct SortPreservingMergeExec 

pub struct SortPreservingMergeExec {
    input: Arc<dyn ExecutionPlan>,
    expr: LexOrdering,
    metrics: ExecutionPlanMetricsSet,
    fetch: Option<usize>,
    cache: PlanProperties,
    enable_round_robin_repartition: bool,
}

Sort preserving merge execution plan

Overview

This operator implements a K-way merge. It is used to merge multiple sorted streams into a single sorted stream and is highly optimized.

Inputs:

1. A list of sort expressions
2. An input plan, where each partition is sorted with respect to these sort expressions.

Output:

1. A single partition that is also sorted with respect to the expressions

Diagram

┌─────────────────────────┐
│ ┌───┬───┬───┬───┐       │
│ │ A │ B │ C │ D │ ...   │──┐
│ └───┴───┴───┴───┘       │  │
└─────────────────────────┘  │  ┌───────────────────┐    ┌───────────────────────────────┐
  Stream 1                   │  │                   │    │ ┌───┬───╦═══╦───┬───╦═══╗     │
                             ├─▶│SortPreservingMerge│───▶│ │ A │ B ║ B ║ C │ D ║ E ║ ... │
                             │  │                   │    │ └───┴─▲─╩═══╩───┴───╩═══╝     │
┌─────────────────────────┐  │  └───────────────────┘    └─┬─────┴───────────────────────┘
│ ╔═══╦═══╗               │  │
│ ║ B ║ E ║     ...       │──┘                             │
│ ╚═══╩═══╝               │              Stable sort if `enable_round_robin_repartition=false`:
└─────────────────────────┘              the merged stream places equal rows from stream 1
  Stream 2


 Input Partitions                                          Output Partition
   (sorted)                                                  (sorted)

Error Handling

If any of the input partitions return an error, the error is propagated to the output and inputs are not polled again.

Fields

input: Arc<dyn ExecutionPlan>

Input plan with sorted partitions

expr: LexOrdering

Sort expressions

metrics: ExecutionPlanMetricsSet

Execution metrics

fetch: Option<usize>

Optional number of rows to fetch. Stops producing rows after this fetch

cache: PlanProperties

Cache holding plan properties like equivalences, output partitioning etc.

enable_round_robin_repartition: bool

Use round-robin selection of tied winners of loser tree

See Self::with_round_robin_repartition for more information.

Implementations

impl SortPreservingMergeExec

pub fn new(expr: LexOrdering, input: Arc<dyn ExecutionPlan>) -> Self

Create a new sort execution plan

pub fn with_fetch(self, fetch: Option<usize>) -> Self

Sets the number of rows to fetch

pub fn with_round_robin_repartition( self, enable_round_robin_repartition: bool, ) -> Self

Sets the selection strategy of tied winners of the loser tree algorithm

If true (the default) equal output rows are placed in the merged stream in round robin fashion. This approach consumes input streams at more even rates when there are many rows with the same sort key.

If false, equal output rows are always placed in the merged stream in the order of the inputs, resulting in potentially slower execution but a stable output order.

pub fn input(&self) -> &Arc<dyn ExecutionPlan>

Input schema

pub fn expr(&self) -> &LexOrdering

Sort expressions

pub fn fetch(&self) -> Option<usize>

Fetch

fn compute_properties( input: &Arc<dyn ExecutionPlan>, ordering: LexOrdering, ) -> PlanProperties

Creates the cache object that stores the plan properties such as schema, equivalence properties, ordering, partitioning, etc.

Trait Implementations

impl Clone for SortPreservingMergeExec

fn clone(&self) -> SortPreservingMergeExec

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SortPreservingMergeExec

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DisplayAs for SortPreservingMergeExec

fn fmt_as(&self, t: DisplayFormatType, f: &mut Formatter<'_>) -> Result

Format according to DisplayFormatType, used when verbose representation looks different from the default one

impl ExecutionPlan for SortPreservingMergeExec

fn as_any(&self) -> &dyn Any

Return a reference to Any that can be used for downcasting

fn with_fetch(&self, limit: Option<usize>) -> Option<Arc<dyn ExecutionPlan>>

Sets the number of rows to fetch

fn try_swapping_with_projection( &self, projection: &ProjectionExec, ) -> Result<Option<Arc<dyn ExecutionPlan>>>

Tries to swap the projection with its input SortPreservingMergeExec. If this is possible, it returns the new SortPreservingMergeExec whose child is a projection. Otherwise, it returns None.

fn name(&self) -> &'static str

Short name for the ExecutionPlan, such as ‘DataSourceExec’.

fn properties(&self) -> &PlanProperties

Return properties of the output of the ExecutionPlan, such as output ordering(s), partitioning information etc.

fn fetch(&self) -> Option<usize>

Gets the fetch count for the operator, None means there is no fetch.

fn required_input_distribution(&self) -> Vec<Distribution>

Specifies the data distribution requirements for all the children for this ExecutionPlan, By default it’s [Distribution::UnspecifiedDistribution] for each child,

fn benefits_from_input_partitioning(&self) -> Vec<bool>

Specifies whether the ExecutionPlan benefits from increased parallelization at its input for each child.

fn required_input_ordering(&self) -> Vec<Option<OrderingRequirements>>

Specifies the ordering required for all of the children of this ExecutionPlan.

fn maintains_input_order(&self) -> Vec<bool>

Returns false if this ExecutionPlan’s implementation may reorder rows within or between partitions.

fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>>

Get a list of children ExecutionPlans that act as inputs to this plan. The returned list will be empty for leaf nodes such as scans, will contain a single value for unary nodes, or two values for binary nodes (such as joins).

fn with_new_children( self: Arc<Self>, children: Vec<Arc<dyn ExecutionPlan>>, ) -> Result<Arc<dyn ExecutionPlan>>

Returns a new ExecutionPlan where all existing children were replaced by the children, in order

fn execute( &self, partition: usize, context: Arc<TaskContext>, ) -> Result<SendableRecordBatchStream>

Begin execution of partition, returning a Stream of [RecordBatch]es.

fn metrics(&self) -> Option<MetricsSet>

Return a snapshot of the set of Metrics for this ExecutionPlan. If no Metrics are available, return None.

fn statistics(&self) -> Result<Statistics>

👎Deprecated since 48.0.0: Use partition_statistics method instead

Returns statistics for this ExecutionPlan node. If statistics are not available, should return Statistics::new_unknown (the default), not an error.

fn partition_statistics(&self, _partition: Option<usize>) -> Result<Statistics>

Returns statistics for a specific partition of this ExecutionPlan node. If statistics are not available, should return Statistics::new_unknown (the default), not an error. If partition is None, it returns statistics for the entire plan.

fn supports_limit_pushdown(&self) -> bool

Returns true if a limit can be safely pushed down through this ExecutionPlan node.

fn static_name() -> &'static str

where Self: Sized,

Short name for the ExecutionPlan, such as ‘DataSourceExec’. Like name but can be called without an instance.

fn schema(&self) -> SchemaRef

Get the schema for this execution plan

fn check_invariants(&self, check: InvariantLevel) -> Result<()>

Returns an error if this individual node does not conform to its invariants. These invariants are typically only checked in debug mode.

fn reset_state(self: Arc<Self>) -> Result<Arc<dyn ExecutionPlan>>

Reset any internal state within this ExecutionPlan.

fn repartitioned( &self, _target_partitions: usize, _config: &ConfigOptions, ) -> Result<Option<Arc<dyn ExecutionPlan>>>

If supported, attempt to increase the partitioning of this ExecutionPlan to produce target_partitions partitions.

fn cardinality_effect(&self) -> CardinalityEffect

Gets the effect on cardinality, if known

fn gather_filters_for_pushdown( &self, _phase: FilterPushdownPhase, parent_filters: Vec<Arc<dyn PhysicalExpr>>, _config: &ConfigOptions, ) -> Result<FilterDescription>

Collect filters that this node can push down to its children. Filters that are being pushed down from parents are passed in, and the node may generate additional filters to push down. For example, given the plan FilterExec -> HashJoinExec -> DataSourceExec, what will happen is that we recurse down the plan calling ExecutionPlan::gather_filters_for_pushdown:

fn handle_child_pushdown_result( &self, _phase: FilterPushdownPhase, child_pushdown_result: ChildPushdownResult, _config: &ConfigOptions, ) -> Result<FilterPushdownPropagation<Arc<dyn ExecutionPlan>>>

Handle the result of a child pushdown. This method is called as we recurse back up the plan tree after pushing filters down to child nodes via ExecutionPlan::gather_filters_for_pushdown. It allows the current node to process the results of filter pushdown from its children, deciding whether to absorb filters, modify the plan, or pass filters back up to its parent.

fn with_new_state( &self, _state: Arc<dyn Any + Send + Sync>, ) -> Option<Arc<dyn ExecutionPlan>>

Injects arbitrary run-time state into this execution plan, returning a new plan instance that incorporates that state if it is relevant to the concrete node implementation.