Uploaded image for project: 'Calcite'
  1. Calcite
  2. CALCITE-349

Add heuristic join-optimizer that can generate bushy joins

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 0.9.0-incubating
    • Component/s: None
    • Labels:
      None

      Description

      Add OptimizeBushyJoinRule, a heuristic join-optimizer that can generate bushy joins.

      We already have LoptOptimizeJoinRule, which is capable of optimizing join order using heuristics, but it is not capable of generating bushy joins. We also have rules that can exhaustively generate all join-orderings (and OPTIQ-346 adds another rule) but this is impractical for N above about 7.

      This is a different approach to OPTIQ-299. Like 299, after choosing a global order, we want to be able to apply regular Optiq rules to optimize further; but rather than adding "firewall" relational expressions to partitioning the graph, as advocated by 299, we might change the Volcano engine to allow regular rules if they immediately generate a cheaper relational expression or if they generate a cheaper relational expression after a maximum of N steps or C worsening of cost.

        Issue Links

          Activity

          Hide
          julianhyde Julian Hyde added a comment -
          Show
          julianhyde Julian Hyde added a comment - Working on this in https://github.com/julianhyde/optiq/commits/optiq-349 .
          Hide
          julianhyde Julian Hyde added a comment -

          Fixed in http://git-wip-us.apache.org/repos/asf/incubator-optiq/commit/b0aff0df.

          The rule is disabled by default, but is used in a few tests and seems to produce somewhat reasonable plans. We need further discussion on the list to figure out how to make them better (e.g. better stats and/or join cardinality estimation).

          Show
          julianhyde Julian Hyde added a comment - Fixed in http://git-wip-us.apache.org/repos/asf/incubator-optiq/commit/b0aff0df . The rule is disabled by default, but is used in a few tests and seems to produce somewhat reasonable plans. We need further discussion on the list to figure out how to make them better (e.g. better stats and/or join cardinality estimation).
          Hide
          julianhyde Julian Hyde added a comment -

          Close issues resolved in release 0.9.0-incubating (2014-08-25).

          Show
          julianhyde Julian Hyde added a comment - Close issues resolved in release 0.9.0-incubating (2014-08-25).

            People

            • Assignee:
              julianhyde Julian Hyde
              Reporter:
              julianhyde Julian Hyde
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development