Divide the join graph into partitions that can be optimized separately

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