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

["Haisheng Yuan (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/CALCITE-299?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16811737#comment-16811737 ] 

Haisheng Yuan commented on CALCITE-299:
---------------------------------------

[~julianhyde] Is this still an issue?

> Divide the join graph into partitions that can be optimized separately
> ----------------------------------------------------------------------
>
>                 Key: CALCITE-299
>                 URL: https://issues.apache.org/jira/browse/CALCITE-299
>             Project: Calcite
>          Issue Type: Bug
>            Reporter: GitHub Import
>            Priority: Major
>              Labels: github-import
>
> 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|https://github.com/julianhyde]
> Labels: 
> Created at: Wed Jun 11 23:24:08 CEST 2014
> State: open



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)