object JoinReorderDP extends PredicateHelper with Logging
Reorder the joins using a dynamic programming algorithm. This implementation is based on the paper: Access Path Selection in a Relational Database Management System. https://dl.acm.org/doi/10.1145/582095.582099
First we put all items (basic joined nodes) into level 0, then we build all two-way joins at level 1 from plans at level 0 (single items), then build all 3-way joins from plans at previous levels (two-way joins and single items), then 4-way joins ... etc, until we build all n-way joins and pick the best plan among them.
When building m-way joins, we only keep the best plan (with the lowest cost) for the same set of m items. E.g., for 3-way joins, we keep only the best plan for items {A, B, C} among plans (A J B) J C, (A J C) J B and (B J C) J A. We also prune cartesian product candidates when building a new plan if there exists no join condition involving references from both left and right. This pruning strategy significantly reduces the search space. E.g., given A J B J C J D with join conditions A.k1 = B.k1 and B.k2 = C.k2 and C.k3 = D.k3, plans maintained for each level are as follows: level 0: p({A}), p({B}), p({C}), p({D}) level 1: p({A, B}), p({B, C}), p({C, D}) level 2: p({A, B, C}), p({B, C, D}) level 3: p({A, B, C, D}) where p({A, B, C, D}) is the final output plan.
For cost evaluation, since physical costs for operators are not available currently, we use cardinalities and sizes to compute costs.
- Alphabetic
- By Inheritance
- JoinReorderDP
- PredicateHelper
- Logging
- AliasHelper
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Type Members
- case class JoinPlan(itemIds: Set[Int], plan: LogicalPlan, joinConds: ExpressionSet, planCost: Cost) extends Product with Serializable
Partial join order in a specific level.
Partial join order in a specific level.
- itemIds
Set of item ids participating in this partial plan.
- plan
The plan tree with the lowest cost for these items found so far.
- joinConds
Join conditions included in the plan.
- planCost
The cost of this plan tree is the sum of costs of all intermediate joins.
- type JoinPlanMap = LinkedHashMap[Set[Int], JoinPlan]
Map[set of item ids, join plan for these items]
- implicit class LogStringContext extends AnyRef
- Definition Classes
- Logging
Value Members
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- def MDC(key: LogKey, value: Any): MDC
- Attributes
- protected
- Definition Classes
- Logging
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def buildBalancedPredicate(expressions: Seq[Expression], op: (Expression, Expression) => Expression): Expression
Builds a balanced output predicate in bottom up approach, by applying binary operator op pair by pair on input predicates exprs recursively.
Builds a balanced output predicate in bottom up approach, by applying binary operator op pair by pair on input predicates exprs recursively. Example: exprs = [a, b, c, d], op = And, returns (a And b) And (c And d) exprs = [a, b, c, d, e, f], op = And, returns ((a And b) And (c And d)) And (e And f)
- Attributes
- protected
- Definition Classes
- PredicateHelper
- def canEvaluate(expr: Expression, plan: LogicalPlan): Boolean
Returns true if
exprcan be evaluated using only the output ofplan.Returns true if
exprcan be evaluated using only the output ofplan. This method can be used to determine when it is acceptable to move expression evaluation within a query plan.For example consider a join between two relations R(a, b) and S(c, d).
-
canEvaluate(EqualTo(a,b), R)returnstrue-canEvaluate(EqualTo(a,c), R)returnsfalse-canEvaluate(Literal(1), R)returnstrueas literals CAN be evaluated on any plan- Attributes
- protected
- Definition Classes
- PredicateHelper
- def canEvaluateWithinJoin(expr: Expression): Boolean
Returns true iff
exprcould be evaluated as a condition within join.Returns true iff
exprcould be evaluated as a condition within join.- Attributes
- protected
- Definition Classes
- PredicateHelper
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @IntrinsicCandidate() @native()
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- def extractPredicatesWithinOutputSet(condition: Expression, outputSet: AttributeSet): Option[Expression]
Returns a filter that its reference is a subset of
outputSetand it contains the maximum constraints fromcondition.Returns a filter that its reference is a subset of
outputSetand it contains the maximum constraints fromcondition. This is used for predicate pushdown. When there is no such filter,Noneis returned.- Attributes
- protected
- Definition Classes
- PredicateHelper
- def findExpressionAndTrackLineageDown(exp: Expression, plan: LogicalPlan): Option[(Expression, LogicalPlan)]
Find the origin of where the input references of expression exp were scanned in the tree of plan, and if they originate from a single leaf node.
Find the origin of where the input references of expression exp were scanned in the tree of plan, and if they originate from a single leaf node. Returns optional tuple with Expression, undoing any projections and aliasing that has been done along the way from plan to origin, and the origin LeafNode plan from which all the exp
- Definition Classes
- PredicateHelper
- def getAliasMap(exprs: Iterable[NamedExpression]): AttributeMap[Alias]
- Attributes
- protected
- Definition Classes
- AliasHelper
- def getAliasMap(plan: Aggregate): AttributeMap[Alias]
- Attributes
- protected
- Definition Classes
- AliasHelper
- def getAliasMap(plan: Project): AttributeMap[Alias]
- Attributes
- protected
- Definition Classes
- AliasHelper
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @IntrinsicCandidate() @native()
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @IntrinsicCandidate() @native()
- def initializeLogIfNecessary(isInterpreter: Boolean, silent: Boolean): Boolean
- Attributes
- protected
- Definition Classes
- Logging
- def initializeLogIfNecessary(isInterpreter: Boolean): Unit
- Attributes
- protected
- Definition Classes
- Logging
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- def isLikelySelective(e: Expression): Boolean
Returns whether an expression is likely to be selective
Returns whether an expression is likely to be selective
- Definition Classes
- PredicateHelper
- def isNullIntolerant(expr: Expression): Boolean
- Attributes
- protected
- Definition Classes
- PredicateHelper
- def isTraceEnabled(): Boolean
- Attributes
- protected
- Definition Classes
- Logging
- def log: Logger
- Attributes
- protected
- Definition Classes
- Logging
- def logBasedOnLevel(level: Level)(f: => MessageWithContext): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logDebug(msg: => String, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logDebug(entry: LogEntry, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logDebug(entry: LogEntry): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logDebug(msg: => String): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logError(msg: => String, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logError(entry: LogEntry, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logError(entry: LogEntry): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logError(msg: => String): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logInfo(msg: => String, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logInfo(entry: LogEntry, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logInfo(entry: LogEntry): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logInfo(msg: => String): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logName: String
- Attributes
- protected
- Definition Classes
- Logging
- def logTrace(msg: => String, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logTrace(entry: LogEntry, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logTrace(entry: LogEntry): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logTrace(msg: => String): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logWarning(msg: => String, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logWarning(entry: LogEntry, throwable: Throwable): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logWarning(entry: LogEntry): Unit
- Attributes
- protected
- Definition Classes
- Logging
- def logWarning(msg: => String): Unit
- Attributes
- protected
- Definition Classes
- Logging
- final def mergeAliases(alias: Alias): Alias
Merge an Alias(Alias(x)) into Alias(x) preserving metadata.
Merge an Alias(Alias(x)) into Alias(x) preserving metadata.
If the outer alias has explicit metadata, it is preserved. Else if the inner alias has explicit metadata, the result has explicit outer.metadata. Else both are deriving the metadata. the result is deriving metadata, with the union of noninheritable keys.
- alias
An Alias with a child Alias, Alias(Alias(x))
- returns
The merged alias, Alias(x)
- Attributes
- protected
- Definition Classes
- AliasHelper
- final def mergeAndTrimAliases(alias: Alias): Alias
Merge any stack of aliases under the top-level alias, and then drops any aliases deeper in the expression tree.
Merge any stack of aliases under the top-level alias, and then drops any aliases deeper in the expression tree. So Alias1(Alias2(Alias3(Foo(Alias4(x))))) becomes Alias5(Foo(x)) where Alias5 preserves the metadata of Alias{1,2,3} and the name and exprId of Alias1. Alias4 is simply removed.
- Attributes
- protected
- Definition Classes
- AliasHelper
- Annotations
- @tailrec()
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @IntrinsicCandidate() @native()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @IntrinsicCandidate() @native()
- def outputWithNullability(output: Seq[Attribute], nonNullAttrExprIds: Seq[ExprId]): Seq[Attribute]
- Attributes
- protected
- Definition Classes
- PredicateHelper
- def replaceAlias(expr: Expression, aliasMap: AttributeMap[Alias]): Expression
Replace all attributes, that reference an alias, with the aliased expression
Replace all attributes, that reference an alias, with the aliased expression
- Attributes
- protected
- Definition Classes
- AliasHelper
- def replaceAliasButKeepName(expr: NamedExpression, aliasMap: AttributeMap[Alias]): NamedExpression
Replace all attributes, that reference an alias, with the aliased expression, but keep the name of the outermost attribute.
Replace all attributes, that reference an alias, with the aliased expression, but keep the name of the outermost attribute.
- Attributes
- protected
- Definition Classes
- AliasHelper
- def search(conf: SQLConf, items: Seq[LogicalPlan], conditions: ExpressionSet, output: Seq[Attribute]): LogicalPlan
- def splitConjunctivePredicates(condition: Expression): Seq[Expression]
- Attributes
- protected
- Definition Classes
- PredicateHelper
- def splitDisjunctivePredicates(condition: Expression): Seq[Expression]
- Attributes
- protected
- Definition Classes
- PredicateHelper
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toString(): String
- Definition Classes
- AnyRef → Any
- def trimAliases(e: Expression): Expression
- Attributes
- protected
- Definition Classes
- AliasHelper
- def trimNonTopLevelAliases[T <: Expression](e: T): T
- Attributes
- protected
- Definition Classes
- AliasHelper
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- def withLogContext(context: Map[String, String])(body: => Unit): Unit
- Attributes
- protected
- Definition Classes
- Logging
Deprecated Value Members
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable]) @Deprecated
- Deprecated
(Since version 9)