Github user nsyca commented on a diff in the pull request:
https://github.com/apache/spark/pull/15363#discussion_r106290042
--- Diff:
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/CostBasedJoinReorder.scala
---
@@ -51,6 +51,11 @@ case class CostBasedJoinReorder(conf: CatalystConf)
extends Rule[LogicalPlan] wi
def reorder(plan: LogicalPlan, output: AttributeSet): LogicalPlan = {
val (items, conditions) = extractInnerJoins(plan)
+ // Find the star schema joins. Currently, it returns the star join
with the largest
+ // fact table. In the future, it can return more than one star join
(e.g. F1-D1-D2
+ // and F2-D3-D4).
+ val starJoinPlans = StarSchemaDetection(conf).findStarJoins(items,
conditions.toSeq)
--- End diff --
One technique to reduce the exponential growth of a DP join enumeration is
to apply a divide and conquer strategy by classifying the n-table join into
small clusters of joins heuristically. That is to reduce the problem of
generating f(2**n) to f(2**i) + f(2**j) where i < n, j < n, and i+j = n.
Star-join schema detection is one way of applying this divide and conquer.
This paper: "Query Simplification: Graceful Degradation for Join-Order
Optimization" by Thomas Neumann in SIGMOD'09 discusses an interesting way of
reducing the complexity of join enumeration.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
