[CALCITE-299] Divide the join graph into partitions that can be optimized separately

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Won't Fix
• Labels: github-import
• Assignee: Unassigned
• Reporter: GitHub Import
• Created: 18/Jun/14 09:05
• Updated: 10/Apr/19 19:19
• Resolved: 10/Apr/19 19:19

Description

Currently Optiq's join optimization is exhaustive. The search space increases combinatorially, so for a query with more than about 8 joins, this is impractical. I propose a "divide and conquer" approach that tames the search space but doesn't cut out the important parts of the search space.

First, there is a planning phase that gathers together all joins into a single mega relational expression, MultiJoinRel.

Then an algorithm builds a join graph, and finds a sub-graph (tree) that minimizes some cost function. Then divide that sub-graph into clusters; the nodes in a cluster are tightly connected, and the links between clusters are relatively loosely connected.

The output of this algorithm is the graph, partitioned into moderately sized groups of nodes (say 5 - 7 maximum). Typically, in a multi-star query, each group of nodes would have a "fact table" at its center, surrounded by "dimension tables" connected by many-to-one relationships. (Fact table and dimension table are relative terms.)

We put in place fire walls (maybe a special kind of RelNode) to prevent join transformation rules from working across clusters. Then we invoke the conventional planning process.

---------------- Imported from GitHub ----------------
Url: https://github.com/julianhyde/optiq/issues/299
Created by: julianhyde
Labels:
Created at: Wed Jun 11 23:24:08 CEST 2014
State: open

Issue Links

• relates to: CALCITE-482 Implement SQL and planner hints