Struct SortMergeJoinExec

pub struct SortMergeJoinExec {
    pub left: Arc<dyn ExecutionPlan>,
    pub right: Arc<dyn ExecutionPlan>,
    pub on: JoinOn,
    pub filter: Option<JoinFilter>,
    pub join_type: JoinType,
    pub sort_options: Vec<SortOptions>,
    pub null_equals_null: bool,
    /* private fields */
}

Join execution plan that executes equi-join predicates on multiple partitions using Sort-Merge join algorithm and applies an optional filter post join. Can be used to join arbitrarily large inputs where one or both of the inputs don’t fit in the available memory.

Join Expressions

Equi-join predicate (e.g. <col1> = <col2>) expressions are represented by Self::on.

Non-equality predicates, which can not be pushed down to join inputs (e.g. <col1> != <col2>) are known as “filter expressions” and are evaluated after the equijoin predicates. They are represented by Self::filter. These are optional expressions.

Sorting

Assumes that both the left and right input to the join are pre-sorted. It is not the responsibility of this execution plan to sort the inputs.

“Streamed” vs “Buffered”

The number of record batches of streamed input currently present in the memory will depend on the output batch size of the execution plan. There is no spilling support for streamed input. The comparisons are performed from values of join keys in streamed input with the values of join keys in buffered input. One row in streamed record batch could be matched with multiple rows in buffered input batches. The streamed input is managed through the states in StreamedState and streamed input batches are represented by StreamedBatch.

Buffered input is buffered for all record batches having the same value of join key. If the memory limit increases beyond the specified value and spilling is enabled, buffered batches could be spilled to disk. If spilling is disabled, the execution will fail under the same conditions. Multiple record batches of buffered could currently reside in memory/disk during the execution. The number of buffered batches residing in memory/disk depends on the number of rows of buffered input having the same value of join key as that of streamed input rows currently present in memory. Due to pre-sorted inputs, the algorithm understands when it is not needed anymore, and releases the buffered batches from memory/disk. The buffered input is managed through the states in BufferedState and buffered input batches are represented by BufferedBatch.

Depending on the type of join, left or right input may be selected as streamed or buffered respectively. For example, in a left-outer join, the left execution plan will be selected as streamed input while in a right-outer join, the right execution plan will be selected as the streamed input.

Reference for the algorithm: https://en.wikipedia.org/wiki/Sort-merge_join.

Helpful short video demonstration: https://www.youtube.com/watch?v=jiWCPJtDE2c.

Fields

left: Arc<dyn ExecutionPlan>

Left sorted joining execution plan

right: Arc<dyn ExecutionPlan>

Right sorting joining execution plan

on: JoinOn

Set of common columns used to join on

filter: Option<JoinFilter>

Filters which are applied while finding matching rows

join_type: JoinType

How the join is performed

sort_options: Vec<SortOptions>

Sort options of join columns used in sorting left and right execution plans

null_equals_null: bool

If null_equals_null is true, null == null else null != null

Implementations

impl SortMergeJoinExec

pub fn try_new( left: Arc<dyn ExecutionPlan>, right: Arc<dyn ExecutionPlan>, on: JoinOn, filter: Option<JoinFilter>, join_type: JoinType, sort_options: Vec<SortOptions>, null_equals_null: bool, ) -> Result<Self>

Tries to create a new SortMergeJoinExec. The inputs are sorted using sort_options are applied to the columns in the on

Error

This function errors when it is not possible to join the left and right sides on keys on.

pub fn probe_side(join_type: &JoinType) -> JoinSide

Get probe side (e.g streaming side) information for this sort merge join. In current implementation, probe side is determined according to join type.

pub fn on(&self) -> &[(PhysicalExprRef, PhysicalExprRef)]

Set of common columns used to join on

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

Ref to right execution plan

pub fn join_type(&self) -> JoinType

Join type

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

Ref to left execution plan

pub fn filter(&self) -> &Option<JoinFilter>

Ref to join filter

pub fn sort_options(&self) -> &[SortOptions]

Ref to sort options

pub fn null_equals_null(&self) -> bool

Null equals null

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

Trait Implementations

impl Clone for SortMergeJoinExec

fn clone(&self) -> SortMergeJoinExec

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for SortMergeJoinExec

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

Formats the value using the given formatter.

impl DisplayAs for SortMergeJoinExec

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 SortMergeJoinExec

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

Tries to swap the projection with its input SortMergeJoinExec. If it can be done, it returns the new swapped version having the SortMergeJoinExec as the top plan. Otherwise, it returns None.

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

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

fn as_any(&self) -> &dyn Any

Returns the execution plan as Any so that it can be downcast to a specific implementation.

fn properties(&self) -> &PlanProperties

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

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 required_input_ordering(&self) -> Vec<Option<LexRequirement>>

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 RecordBatches.

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>

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

fn static_name() -> &'static str

where Self: Sized,

Short name for the ExecutionPlan, such as ‘ParquetExec’. 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 benefits_from_input_partitioning(&self) -> Vec<bool>

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

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 supports_limit_pushdown(&self) -> bool

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

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

Returns a fetching variant of this ExecutionPlan node, if it supports fetch limits. Returns None otherwise.

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

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

fn cardinality_effect(&self) -> CardinalityEffect

Gets the effect on cardinality, if known