JoinSelection Execution Planning Strategy

JoinSelection is an execution planning strategy (of SparkPlanner) that translates Join logical operator to one of the available join physical operators per join physical operator selection requirements.

Table 1. Join Physical Operator Selection Requirements (in execution order)
Physical Join Operator	Selection Requirements
BroadcastHashJoinExec	There are joining keys and one of the following holds: canBuildRight and right join side can be broadcast canBuildLeft and left join side can be broadcast
ShuffledHashJoinExec	There are joining keys and one of the following holds: spark.sql.join.preferSortMergeJoin is disabled, canBuildRight, canBuildLocalHashMap for right join side and finally right join side is much smaller than left side spark.sql.join.preferSortMergeJoin is disabled, canBuildLeft, canBuildLocalHashMap for left join side and finally left join side is much smaller than right Left join keys are not orderable
SortMergeJoinExec	Left join keys orderable
BroadcastNestedLoopJoinExec	There are no joining keys and one of the following holds: canBuildRight and right join side can be broadcast canBuildLeft and left join side can be broadcast
`CartesianProductExec`	There are no joining keys and join type is `INNER` or `CROSS`
BroadcastNestedLoopJoinExec	Default when no other have matched

Note	`JoinSelection` uses ExtractEquiJoinKeys to destructure a `Join` logical plan.

ExtractEquiJoinKeys is a pattern used to destructure a Join logical operator into a tuple for join physical operator selection.

(JoinType, Seq[Expression], Seq[Expression], Option[Expression], LogicalPlan, LogicalPlan)

muchSmaller(a: LogicalPlan, b: LogicalPlan): Boolean

muchSmaller condition holds when plan a is at least 3 times smaller than plan b.

Internally, muchSmaller calculates the estimated statistics for the input logical plans and compares their physical size in bytes (sizeInBytes).

Note	`muchSmaller` is used exclusively when `JoinSelection` checks join selection requirements for `ShuffledHashJoinExec` physical operator.

canBuildLocalHashMap(plan: LogicalPlan): Boolean

canBuildLocalHashMap condition holds for the logical plan whose single partition is small enough to build a hash table (i.e. spark.sql.autoBroadcastJoinThreshold multiplied by spark.sql.shuffle.partitions).

Internally, canBuildLocalHashMap calculates the estimated statistics for the input logical plans and takes the size in bytes (sizeInBytes).

Note	`canBuildLocalHashMap` is used when `JoinSelection` checks join selection requirements for `ShuffledHashJoinExec` physical operator.

canBuildLeft(joinType: JoinType): Boolean

canBuildLeft condition holds for CROSS, INNER and RIGHT OUTER join types. Otherwise, canBuildLeft is false.

Note	`canBuildLeft` is used when `JoinSelection` checks join selection requirements for `BroadcastHashJoinExec`, `ShuffledHashJoinExec` or `BroadcastNestedLoopJoinExec` physical operators.

canBuildRight(joinType: JoinType): Boolean

canBuildRight condition holds for joins that are:

Otherwise, canBuildRight is false.

Note	`canBuildRight` is used when `JoinSelection` checks join selection requirements for `BroadcastHashJoinExec`, `ShuffledHashJoinExec` or `BroadcastNestedLoopJoinExec` physical operators.

canBroadcast(plan: LogicalPlan): Boolean

canBroadcast condition holds for logical operators with statistics that can be broadcast and of non-negative size up to spark.sql.autoBroadcastJoinThreshold.

results matching ""