quickstep-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hbdeshm...@apache.org
Subject [28/41] incubator-quickstep git commit: Added hash join order optimization for star schema queries. (#229)
Date Sat, 04 Jun 2016 23:03:44 GMT
Added hash join order optimization for star schema queries. (#229)

Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/0fffe505
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/0fffe505
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/0fffe505

Branch: refs/heads/query-id-operator-workorder
Commit: 0fffe5057da6b6abc1d9cdf0f7dab0accc8a0fe1
Parents: df4a05d
Author: Jianqiao Zhu <jianqiao@cs.wisc.edu>
Authored: Thu May 19 18:19:28 2016 -0500
Committer: Zuyu Zhang <zzhang@pivotal.io>
Committed: Mon May 30 15:47:52 2016 -0700

----------------------------------------------------------------------
 query_optimizer/CMakeLists.txt                  |   2 +
 query_optimizer/PhysicalGenerator.cpp           |  14 +
 query_optimizer/cost_model/CMakeLists.txt       |  32 +-
 .../cost_model/StarSchemaSimpleCostModel.cpp    | 258 ++++++++++++++++
 .../cost_model/StarSchemaSimpleCostModel.hpp    | 115 +++++++
 query_optimizer/rules/CMakeLists.txt            |  20 +-
 .../StarSchemaHashJoinOrderOptimization.cpp     | 309 +++++++++++++++++++
 .../StarSchemaHashJoinOrderOptimization.hpp     | 136 ++++++++
 query_optimizer/tests/CMakeLists.txt            |   1 +
 query_optimizer/tests/OptimizerTextTest.cpp     |  14 +
 10 files changed, 899 insertions(+), 2 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index feaecb3..aa2873e 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -182,10 +182,12 @@ target_link_libraries(quickstep_queryoptimizer_OptimizerTree
                       quickstep_utility_Macros
                       quickstep_utility_TreeStringSerializable)
 target_link_libraries(quickstep_queryoptimizer_PhysicalGenerator
+                      gflags_nothreads-static
                       quickstep_queryoptimizer_LogicalToPhysicalMapper
                       quickstep_queryoptimizer_logical_Logical
                       quickstep_queryoptimizer_physical_Physical
                       quickstep_queryoptimizer_rules_PruneColumns
+                      quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
                       quickstep_queryoptimizer_strategy_Aggregate
                       quickstep_queryoptimizer_strategy_Join
                       quickstep_queryoptimizer_strategy_OneToOne

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/PhysicalGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.cpp b/query_optimizer/PhysicalGenerator.cpp
index ee52966..662236f 100644
--- a/query_optimizer/PhysicalGenerator.cpp
+++ b/query_optimizer/PhysicalGenerator.cpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -25,17 +27,26 @@
 #include "query_optimizer/logical/Logical.hpp"
 #include "query_optimizer/physical/Physical.hpp"
 #include "query_optimizer/rules/PruneColumns.hpp"
+#include "query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp"
 #include "query_optimizer/strategy/Aggregate.hpp"
 #include "query_optimizer/strategy/Join.hpp"
 #include "query_optimizer/strategy/OneToOne.hpp"
 #include "query_optimizer/strategy/Selection.hpp"
 #include "query_optimizer/strategy/Strategy.hpp"
 
+#include "gflags/gflags.h"
+
 #include "glog/logging.h"
 
 namespace quickstep {
 namespace optimizer {
 
+DEFINE_bool(reorder_hash_joins, true,
+            "If true, apply hash join order optimization to each group of hash "
+            "joins. The optimization applies a greedy algorithm to favor smaller "
+            "cardinality and selective tables to be joined first, which is suitable "
+            "for queries on star-schema tables");
+
 namespace L = ::quickstep::optimizer::logical;
 namespace P = ::quickstep::optimizer::physical;
 namespace S = ::quickstep::optimizer::strategy;
@@ -77,6 +88,9 @@ P::PhysicalPtr PhysicalGenerator::generateInitialPlan(
 
 P::PhysicalPtr PhysicalGenerator::optimizePlan() {
   std::vector<std::unique_ptr<Rule<P::Physical>>> rules;
+  if (FLAGS_reorder_hash_joins) {
+    rules.emplace_back(new StarSchemaHashJoinOrderOptimization());
+  }
   rules.emplace_back(new PruneColumns());
 
   for (std::unique_ptr<Rule<P::Physical>> &rule : rules) {

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/cost_model/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/CMakeLists.txt b/query_optimizer/cost_model/CMakeLists.txt
index 6697d52..6bf5240 100644
--- a/query_optimizer/cost_model/CMakeLists.txt
+++ b/query_optimizer/cost_model/CMakeLists.txt
@@ -1,5 +1,7 @@
 #   Copyright 2011-2015 Quickstep Technologies LLC.
 #   Copyright 2015 Pivotal Software, Inc.
+#   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+#     University of Wisconsin—Madison.
 #
 #   Licensed under the Apache License, Version 2.0 (the "License");
 #   you may not use this file except in compliance with the License.
@@ -16,6 +18,9 @@
 # Declare micro-libs:
 add_library(quickstep_queryoptimizer_costmodel_CostModel ../../empty_src.cpp CostModel.hpp)
 add_library(quickstep_queryoptimizer_costmodel_SimpleCostModel SimpleCostModel.cpp SimpleCostModel.hpp)
+add_library(quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
+            StarSchemaSimpleCostModel.cpp
+            StarSchemaSimpleCostModel.hpp)
 
 # Link dependencies:
 target_link_libraries(quickstep_queryoptimizer_costmodel_CostModel
@@ -36,9 +41,34 @@ target_link_libraries(quickstep_queryoptimizer_costmodel_SimpleCostModel
                       quickstep_queryoptimizer_physical_TableReference
                       quickstep_queryoptimizer_physical_TopLevelPlan
                       quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
+                      glog
+                      quickstep_catalog_CatalogRelation
+                      quickstep_queryoptimizer_costmodel_CostModel
+                      quickstep_queryoptimizer_expressions_AttributeReference
+                      quickstep_queryoptimizer_expressions_ComparisonExpression
+                      quickstep_queryoptimizer_expressions_ExprId
+                      quickstep_queryoptimizer_expressions_ExpressionType
+                      quickstep_queryoptimizer_expressions_LogicalAnd
+                      quickstep_queryoptimizer_expressions_LogicalOr
+                      quickstep_queryoptimizer_expressions_PatternMatcher
+                      quickstep_queryoptimizer_expressions_Predicate
+                      quickstep_queryoptimizer_physical_Aggregate
+                      quickstep_queryoptimizer_physical_HashJoin
+                      quickstep_queryoptimizer_physical_NestedLoopsJoin
+                      quickstep_queryoptimizer_physical_Physical
+                      quickstep_queryoptimizer_physical_PhysicalType
+                      quickstep_queryoptimizer_physical_Selection
+                      quickstep_queryoptimizer_physical_SharedSubplanReference
+                      quickstep_queryoptimizer_physical_Sort
+                      quickstep_queryoptimizer_physical_TableGenerator
+                      quickstep_queryoptimizer_physical_TableReference
+                      quickstep_queryoptimizer_physical_TopLevelPlan
+                      quickstep_utility_Macros)
 
 # Module all-in-one library:
 add_library(quickstep_queryoptimizer_costmodel ../../empty_src.cpp CostModelModule.hpp)
 target_link_libraries(quickstep_queryoptimizer_costmodel
                       quickstep_queryoptimizer_costmodel_CostModel
-                      quickstep_queryoptimizer_costmodel_SimpleCostModel)
+                      quickstep_queryoptimizer_costmodel_SimpleCostModel
+                      quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel)

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
new file mode 100644
index 0000000..eb9fcc1
--- /dev/null
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
@@ -0,0 +1,258 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   Licensed under the Apache License, Version 2.0 (the "License");
+ *   you may not use this file except in compliance with the License.
+ *   You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing, software
+ *   distributed under the License is distributed on an "AS IS" BASIS,
+ *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *   See the License for the specific language governing permissions and
+ *   limitations under the License.
+ **/
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+
+#include <algorithm>
+#include <memory>
+#include <unordered_map>
+#include <vector>
+
+#include "catalog/CatalogRelation.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ComparisonExpression.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/expressions/ExpressionType.hpp"
+#include "query_optimizer/expressions/LogicalAnd.hpp"
+#include "query_optimizer/expressions/LogicalOr.hpp"
+#include "query_optimizer/expressions/Predicate.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
+#include "query_optimizer/physical/NestedLoopsJoin.hpp"
+#include "query_optimizer/physical/HashJoin.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/PhysicalType.hpp"
+#include "query_optimizer/physical/Selection.hpp"
+#include "query_optimizer/physical/SharedSubplanReference.hpp"
+#include "query_optimizer/physical/Sort.hpp"
+#include "query_optimizer/physical/TableGenerator.hpp"
+#include "query_optimizer/physical/TableReference.hpp"
+#include "query_optimizer/physical/TopLevelPlan.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+namespace cost {
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace P = ::quickstep::optimizer::physical;
+
+std::size_t StarSchemaSimpleCostModel::estimateCardinality(
+    const P::PhysicalPtr &physical_plan) {
+  switch (physical_plan->getPhysicalType()) {
+    case P::PhysicalType::kTopLevelPlan:
+      return estimateCardinalityForTopLevelPlan(
+          std::static_pointer_cast<const P::TopLevelPlan>(physical_plan));
+    case P::PhysicalType::kTableReference:
+      return estimateCardinalityForTableReference(
+          std::static_pointer_cast<const P::TableReference>(physical_plan));
+    case P::PhysicalType::kSelection:
+      return estimateCardinalityForSelection(
+          std::static_pointer_cast<const P::Selection>(physical_plan));
+    case P::PhysicalType::kTableGenerator:
+      return estimateCardinalityForTableGenerator(
+          std::static_pointer_cast<const P::TableGenerator>(physical_plan));
+    case P::PhysicalType::kHashJoin:
+      return estimateCardinalityForHashJoin(
+          std::static_pointer_cast<const P::HashJoin>(physical_plan));
+    case P::PhysicalType::kNestedLoopsJoin:
+      return estimateCardinalityForNestedLoopsJoin(
+          std::static_pointer_cast<const P::NestedLoopsJoin>(physical_plan));
+    case P::PhysicalType::kAggregate:
+      return estimateCardinalityForAggregate(
+          std::static_pointer_cast<const P::Aggregate>(physical_plan));
+    case P::PhysicalType::kSharedSubplanReference: {
+      const P::SharedSubplanReferencePtr shared_subplan_reference =
+          std::static_pointer_cast<const P::SharedSubplanReference>(physical_plan);
+      return estimateCardinality(
+          shared_subplans_[shared_subplan_reference->subplan_id()]);
+    }
+    case P::PhysicalType::kSort:
+      return estimateCardinality(
+          std::static_pointer_cast<const P::Sort>(physical_plan)->input());
+    default:
+      LOG(FATAL) << "Unsupported physical plan:" << physical_plan->toString();
+  }
+}
+
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForTopLevelPlan(
+    const P::TopLevelPlanPtr &physical_plan) {
+  return estimateCardinality(physical_plan->plan());
+}
+
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForTableReference(
+    const P::TableReferencePtr &physical_plan) {
+  std::size_t num_tuples = physical_plan->relation()->getStatistics().getNumTuples();
+  if (num_tuples == 0) {
+    num_tuples = physical_plan->relation()->estimateTupleCardinality();
+  }
+  return num_tuples;
+}
+
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForSelection(
+    const P::SelectionPtr &physical_plan) {
+  double selectivity = estimateSelectivityForSelection(physical_plan);
+  return std::max(static_cast<std::size_t>(estimateCardinality(physical_plan->input()) * selectivity),
+                  static_cast<std::size_t>(1));
+}
+
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForTableGenerator(
+    const P::TableGeneratorPtr &physical_plan) {
+  return physical_plan->generator_function_handle()->getEstimatedCardinality();
+}
+
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForHashJoin(
+    const P::HashJoinPtr &physical_plan) {
+  std::size_t left_cardinality = estimateCardinality(physical_plan->left());
+  std::size_t right_cardinality = estimateCardinality(physical_plan->right());
+  double left_selectivity = estimateSelectivity(physical_plan->left());
+  double right_selectivity = estimateSelectivity(physical_plan->right());
+  return std::max(static_cast<std::size_t>(left_cardinality * right_selectivity) + 1,
+                  static_cast<std::size_t>(right_cardinality * left_selectivity) + 1);
+}
+
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForNestedLoopsJoin(
+    const P::NestedLoopsJoinPtr &physical_plan) {
+  return std::max(estimateCardinality(physical_plan->left()),
+                  estimateCardinality(physical_plan->right()));
+}
+
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForAggregate(
+    const P::AggregatePtr &physical_plan) {
+  if (physical_plan->grouping_expressions().empty()) {
+    return 1;
+  }
+  return std::max(static_cast<std::size_t>(1),
+                  estimateCardinality(physical_plan->input()) / 10);
+}
+
+double StarSchemaSimpleCostModel::estimateSelectivity(
+    const physical::PhysicalPtr &physical_plan) {
+  switch (physical_plan->getPhysicalType()) {
+    case P::PhysicalType::kSelection: {
+      return estimateSelectivityForSelection(
+          std::static_pointer_cast<const P::Selection>(physical_plan));
+    }
+    case P::PhysicalType::kHashJoin: {
+      const P::HashJoinPtr &hash_join =
+          std::static_pointer_cast<const P::HashJoin>(physical_plan);
+      return std::min(estimateSelectivity(hash_join->left()),
+                      estimateSelectivity(hash_join->right()));
+    }
+    case P::PhysicalType::kNestedLoopsJoin: {
+      const P::NestedLoopsJoinPtr &nested_loop_join =
+          std::static_pointer_cast<const P::NestedLoopsJoin>(physical_plan);
+      return std::min(estimateSelectivity(nested_loop_join->left()),
+                      estimateSelectivity(nested_loop_join->right()));
+    }
+    case P::PhysicalType::kSharedSubplanReference: {
+      const P::SharedSubplanReferencePtr shared_subplan_reference =
+          std::static_pointer_cast<const P::SharedSubplanReference>(physical_plan);
+      return estimateSelectivity(
+          shared_subplans_[shared_subplan_reference->subplan_id()]);
+    }
+    default:
+      return 1.0;
+  }
+}
+
+double StarSchemaSimpleCostModel::estimateSelectivityForSelection(
+    const physical::SelectionPtr &physical_plan) {
+  const E::PredicatePtr &filter_predicate = physical_plan->filter_predicate();
+
+  // If the subplan is a table reference, gather the number of distinct values
+  // statistics for each column (attribute).
+  std::unordered_map<E::ExprId, std::size_t> num_distinct_values_map;
+  if (physical_plan->input()->getPhysicalType() == P::PhysicalType::kTableReference) {
+    const P::TableReferencePtr &table_reference =
+        std::static_pointer_cast<const P::TableReference>(physical_plan->input());
+    const CatalogRelation &relation = *table_reference->relation();
+    const std::vector<E::AttributeReferencePtr> &attributes = table_reference->attribute_list();
+    for (std::size_t i = 0; i < attributes.size(); ++i) {
+      std::size_t num_distinct_values = relation.getStatistics().getNumDistinctValues(i);
+      if (num_distinct_values > 0) {
+        num_distinct_values_map[attributes[i]->id()] = num_distinct_values;
+      }
+    }
+  }
+
+  return estimateSelectivityForPredicate(num_distinct_values_map, filter_predicate);
+}
+
+double StarSchemaSimpleCostModel::estimateSelectivityForPredicate(
+    const std::unordered_map<expressions::ExprId, std::size_t> &num_distinct_values_map,
+    const expressions::PredicatePtr &filter_predicate) {
+  if (filter_predicate == nullptr) {
+    return 1.0;
+  }
+
+  switch (filter_predicate->getExpressionType()) {
+    case E::ExpressionType::kComparisonExpression: {
+      // Case 1 - Number of distinct values statistics available
+      //   Case 1.1 - Equality comparison: 1.0 / num_distinct_values
+      //   Case 1.2 - Otherwise: 5.0 / num_distinct_values
+      // Case 2 - Number of distinct values statistics not available
+      //   Case 2.1 - Equality comparison: 0.1
+      //   Case 2.2 - Otherwise: 0.5
+      const E::ComparisonExpressionPtr &comparison_expression =
+          std::static_pointer_cast<const E::ComparisonExpression>(filter_predicate);
+      E::AttributeReferencePtr attr;
+      if ((E::SomeAttributeReference::MatchesWithConditionalCast(comparison_expression->left(), &attr) &&
+           E::SomeScalarLiteral::Matches(comparison_expression->right())) ||
+          (E::SomeAttributeReference::MatchesWithConditionalCast(comparison_expression->right(), &attr) &&
+           E::SomeScalarLiteral::Matches(comparison_expression->left()))) {
+        const auto it = num_distinct_values_map.find(attr->id());
+        if (it != num_distinct_values_map.end() && it->second > 0) {
+          double unit_selectivity = 1.0 / it->second;
+          return comparison_expression->isEqualityComparisonPredicate()
+                     ? unit_selectivity
+                     : std::min(0.5, unit_selectivity * 5.0);
+        }
+      }
+
+      return comparison_expression->isEqualityComparisonPredicate() ? 0.1 : 0.5;
+    }
+    case E::ExpressionType::kLogicalAnd: {
+      const E::LogicalAndPtr &logical_and =
+          std::static_pointer_cast<const E::LogicalAnd>(filter_predicate);
+      double selectivity = 1.0;
+      for (const auto &predicate : logical_and->operands()) {
+        selectivity =
+            std::min(selectivity,
+                     estimateSelectivityForPredicate(num_distinct_values_map, predicate));
+      }
+      return selectivity;
+    }
+    case E::ExpressionType::kLogicalOr: {
+      const E::LogicalOrPtr &logical_or =
+          std::static_pointer_cast<const E::LogicalOr>(filter_predicate);
+      double selectivity = 0;
+      for (const auto &predicate : logical_or->operands()) {
+        selectivity += estimateSelectivityForPredicate(num_distinct_values_map, predicate);
+      }
+      return std::min(selectivity, 1.0);
+    }
+    default:
+      break;
+  }
+  return 1.0;
+}
+
+}  // namespace cost
+}  // namespace optimizer
+}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp b/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
new file mode 100644
index 0000000..c63e55a
--- /dev/null
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
@@ -0,0 +1,115 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   Licensed under the Apache License, Version 2.0 (the "License");
+ *   you may not use this file except in compliance with the License.
+ *   You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing, software
+ *   distributed under the License is distributed on an "AS IS" BASIS,
+ *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *   See the License for the specific language governing permissions and
+ *   limitations under the License.
+ **/
+
+#ifndef QUERY_OPTIMIZER_COST_MODEL_STAR_SCHEMA_SIMPLE_COST_MODEL_HPP_
+#define QUERY_OPTIMIZER_COST_MODEL_STAR_SCHEMA_SIMPLE_COST_MODEL_HPP_
+
+#include <cstddef>
+#include <unordered_map>
+#include <vector>
+
+#include "query_optimizer/cost_model/CostModel.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/expressions/Predicate.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
+#include "query_optimizer/physical/NestedLoopsJoin.hpp"
+#include "query_optimizer/physical/HashJoin.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/Selection.hpp"
+#include "query_optimizer/physical/TableGenerator.hpp"
+#include "query_optimizer/physical/TableReference.hpp"
+#include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+namespace optimizer {
+namespace cost {
+
+/** \addtogroup CostModel
+ *  @{
+ */
+
+/**
+ * @brief A simple cost model for hash join planning.
+ */
+class StarSchemaSimpleCostModel : public CostModel {
+ public:
+  /**
+   * @brief Constructor.
+   */
+  explicit StarSchemaSimpleCostModel(const std::vector<physical::PhysicalPtr> &shared_subplans)
+      : shared_subplans_(shared_subplans) {}
+
+  /**
+   * @brief Estimate the cardinality of a physical plan.
+   *
+   * @param physical_plan The physical plan.
+   * @return The estimated cardinality.
+   */
+  std::size_t estimateCardinality(
+      const physical::PhysicalPtr &physical_plan) override;
+
+  /**
+   * @brief Estimate the "selectivity" of a physical plan under the assumption
+   *        that it acts as a filtered dimension table in a hash join.
+   *
+   * @param phyiscal_plan The physical plan.
+   * @return The estimated selectivity.
+   */
+  double estimateSelectivity(const physical::PhysicalPtr &physical_plan);
+
+ private:
+  std::size_t estimateCardinalityForTopLevelPlan(
+      const physical::TopLevelPlanPtr &physical_plan);
+
+  std::size_t estimateCardinalityForTableReference(
+      const physical::TableReferencePtr &physical_plan);
+
+  std::size_t estimateCardinalityForSelection(
+      const physical::SelectionPtr &physical_plan);
+
+  std::size_t estimateCardinalityForTableGenerator(
+      const physical::TableGeneratorPtr &physical_plan);
+
+  std::size_t estimateCardinalityForHashJoin(
+      const physical::HashJoinPtr &physical_plan);
+
+  std::size_t estimateCardinalityForNestedLoopsJoin(
+      const physical::NestedLoopsJoinPtr &physical_plan);
+
+  std::size_t estimateCardinalityForAggregate(
+      const physical::AggregatePtr &physical_plan);
+
+  double estimateSelectivityForSelection(
+      const physical::SelectionPtr &physical_plan);
+
+  double estimateSelectivityForPredicate(
+      const std::unordered_map<expressions::ExprId, std::size_t> &num_distinct_values_map,
+      const expressions::PredicatePtr &filter_predicate);
+
+  const std::vector<physical::PhysicalPtr> &shared_subplans_;
+
+  DISALLOW_COPY_AND_ASSIGN(StarSchemaSimpleCostModel);
+};
+
+/** @} */
+
+}  // namespace cost
+}  // namespace optimizer
+}  // namespace quickstep
+
+#endif /* QUERY_OPTIMIZER_COST_MODEL_STAR_SCHEMA_SIMPLE_COST_MODEL_HPP_ */

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/rules/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CMakeLists.txt b/query_optimizer/rules/CMakeLists.txt
index 7032af5..1990174 100644
--- a/query_optimizer/rules/CMakeLists.txt
+++ b/query_optimizer/rules/CMakeLists.txt
@@ -26,11 +26,14 @@ add_library(quickstep_queryoptimizer_rules_PushDownFilter PushDownFilter.cpp Pus
 add_library(quickstep_queryoptimizer_rules_PushDownSemiAntiJoin PushDownSemiAntiJoin.cpp PushDownSemiAntiJoin.hpp)
 add_library(quickstep_queryoptimizer_rules_Rule ../../empty_src.cpp Rule.hpp)
 add_library(quickstep_queryoptimizer_rules_RuleHelper RuleHelper.cpp RuleHelper.hpp)
+add_library(quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
+            StarSchemaHashJoinOrderOptimization.cpp
+            StarSchemaHashJoinOrderOptimization.hpp)
 add_library(quickstep_queryoptimizer_rules_TopDownRule ../../empty_src.cpp TopDownRule.hpp)
 add_library(quickstep_queryoptimizer_rules_UpdateExpression UpdateExpression.cpp UpdateExpression.hpp)
 add_library(quickstep_queryoptimizer_rules_UnnestSubqueries UnnestSubqueries.cpp UnnestSubqueries.hpp)
 
-                      
+
 # Link dependencies:
 target_link_libraries(quickstep_queryoptimizer_rules_BottomUpRule
                       glog
@@ -110,6 +113,20 @@ target_link_libraries(quickstep_queryoptimizer_rules_RuleHelper
                       quickstep_queryoptimizer_expressions_PatternMatcher
                       quickstep_queryoptimizer_expressions_Predicate
                       quickstep_queryoptimizer_rules_UpdateExpression)
+target_link_libraries(quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
+                      quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
+                      quickstep_queryoptimizer_expressions_AttributeReference
+                      quickstep_queryoptimizer_expressions_ExprId
+                      quickstep_queryoptimizer_expressions_NamedExpression
+                      quickstep_queryoptimizer_expressions_PatternMatcher
+                      quickstep_queryoptimizer_expressions_Predicate
+                      quickstep_queryoptimizer_physical_HashJoin
+                      quickstep_queryoptimizer_physical_PatternMatcher
+                      quickstep_queryoptimizer_physical_Physical
+                      quickstep_queryoptimizer_physical_PhysicalType
+                      quickstep_queryoptimizer_physical_TopLevelPlan
+                      quickstep_queryoptimizer_rules_Rule
+                      quickstep_utility_Macros)
 target_link_libraries(quickstep_queryoptimizer_rules_TopDownRule
                       quickstep_queryoptimizer_rules_Rule
                       quickstep_utility_Macros)
@@ -167,6 +184,7 @@ target_link_libraries(quickstep_queryoptimizer_rules
                       quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
                       quickstep_queryoptimizer_rules_Rule
                       quickstep_queryoptimizer_rules_RuleHelper
+                      quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
                       quickstep_queryoptimizer_rules_TopDownRule
                       quickstep_queryoptimizer_rules_UpdateExpression
                       quickstep_queryoptimizer_rules_UnnestSubqueries)

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
new file mode 100644
index 0000000..9770606
--- /dev/null
+++ b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
@@ -0,0 +1,309 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   Licensed under the Apache License, Version 2.0 (the "License");
+ *   you may not use this file except in compliance with the License.
+ *   You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing, software
+ *   distributed under the License is distributed on an "AS IS" BASIS,
+ *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *   See the License for the specific language governing permissions and
+ *   limitations under the License.
+ **/
+
+#include "query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp"
+
+#include <memory>
+#include <set>
+#include <unordered_map>
+#include <vector>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/NamedExpression.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
+#include "query_optimizer/physical/HashJoin.hpp"
+#include "query_optimizer/physical/PatternMatcher.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/PhysicalType.hpp"
+#include "query_optimizer/physical/TopLevelPlan.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace P = ::quickstep::optimizer::physical;
+
+P::PhysicalPtr StarSchemaHashJoinOrderOptimization::apply(const P::PhysicalPtr &input) {
+  DCHECK(input->getPhysicalType() == P::PhysicalType::kTopLevelPlan);
+  cost_model_.reset(
+      new cost::StarSchemaSimpleCostModel(
+          std::static_pointer_cast<const P::TopLevelPlan>(input)->shared_subplans()));
+
+  return applyInternal(input, nullptr);
+}
+
+P::PhysicalPtr StarSchemaHashJoinOrderOptimization::applyInternal(const P::PhysicalPtr &input,
+                                                                  JoinGroupInfo *parent_join_group) {
+  P::HashJoinPtr hash_join;
+  const bool is_hash_inner_join =
+      P::SomeHashJoin::MatchesWithConditionalCast(input, &hash_join)
+          && hash_join->join_type() == P::HashJoin::JoinType::kInnerJoin;
+
+  if (is_hash_inner_join) {
+    bool is_valid_cascading_hash_join = false;
+    if (hash_join->residual_predicate() == nullptr) {
+      is_valid_cascading_hash_join = true;
+      for (const E::NamedExpressionPtr expr : hash_join->project_expressions()) {
+        if (!E::SomeAttributeReference::Matches(expr)) {
+          is_valid_cascading_hash_join = false;
+          break;
+        }
+      }
+    }
+
+    std::unique_ptr<JoinGroupInfo> new_join_group;
+    JoinGroupInfo *join_group = nullptr;
+    if (parent_join_group == nullptr || !is_valid_cascading_hash_join) {
+      new_join_group.reset(new JoinGroupInfo());
+      join_group = new_join_group.get();
+    } else {
+      join_group = parent_join_group;
+    }
+
+    // Gather tables into the join group.
+    for (const P::PhysicalPtr &child : input->children()) {
+      applyInternal(child, join_group);
+    }
+
+    // Gather join attribute pairs.
+    for (std::size_t i = 0; i < hash_join->left_join_attributes().size(); ++i) {
+      const std::size_t left_attr_id = hash_join->left_join_attributes()[i]->id();
+      const std::size_t right_attr_id = hash_join->right_join_attributes()[i]->id();
+
+      join_group->join_attribute_pairs.emplace_back(left_attr_id, right_attr_id);
+    }
+
+    if (join_group != parent_join_group) {
+      // This node is the root node for a group of hash inner joins. Now plan the
+      // ordering of the joins.
+      P::PhysicalPtr output = generatePlan(*join_group,
+                                           hash_join->residual_predicate(),
+                                           hash_join->project_expressions());
+      if (parent_join_group == nullptr) {
+        return output;
+      } else {
+        parent_join_group->tables.emplace_back(output);
+        return nullptr;
+      }
+    } else {
+      return nullptr;
+    }
+  } else {
+    std::vector<P::PhysicalPtr> new_children;
+    bool has_changed_children = false;
+    for (const P::PhysicalPtr &child : input->children()) {
+      P::PhysicalPtr new_child = applyInternal(child, nullptr);
+      DCHECK(new_child != nullptr);
+      if (child != new_child && !has_changed_children) {
+        has_changed_children = true;
+      }
+      new_children.push_back(new_child);
+    }
+
+    P::PhysicalPtr output =
+        (has_changed_children ? input->copyWithNewChildren(new_children)
+                              : input);
+
+    if (parent_join_group == nullptr) {
+      return output;
+    } else {
+      parent_join_group->tables.emplace_back(output);
+      return nullptr;
+    }
+  }
+}
+
+physical::PhysicalPtr StarSchemaHashJoinOrderOptimization::generatePlan(
+    const JoinGroupInfo &join_group,
+    const E::PredicatePtr &residual_predicate,
+    const std::vector<E::NamedExpressionPtr> &project_expressions) {
+  const std::size_t num_tables = join_group.tables.size();
+  DCHECK_GE(num_tables, 2u);
+
+  std::vector<TableInfo> table_info_storage;
+  const std::vector<P::PhysicalPtr> &tables = join_group.tables;
+  for (std::size_t i = 0; i < join_group.tables.size(); ++i) {
+    table_info_storage.emplace_back(
+        i,
+        tables[i],
+        cost_model_->estimateCardinality(tables[i]),
+        cost_model_->estimateSelectivity(tables[i]));
+  }
+
+  // Auxiliary mapping info.
+  std::unordered_map<E::ExprId, std::size_t> attribute_id_to_table_info_index_map;
+  std::unordered_map<E::ExprId, E::AttributeReferencePtr> attribute_id_to_reference_map;
+  for (std::size_t table_idx = 0; table_idx < num_tables; ++table_idx) {
+    for (const E::AttributeReferencePtr &attr :
+             table_info_storage[table_idx].table->getOutputAttributes()) {
+      DCHECK(attribute_id_to_table_info_index_map.find(attr->id())
+                 == attribute_id_to_table_info_index_map.end());
+
+      attribute_id_to_table_info_index_map.emplace(attr->id(), table_idx);
+      attribute_id_to_reference_map.emplace(attr->id(), attr);
+    }
+  }
+
+  // Create a join graph where tables are vertices, and add an edge between vertices
+  // t1 and t2 for each join predicate t1.x = t2.y
+  std::vector<std::unordered_set<std::size_t>> join_graph(table_info_storage.size());
+  for (const auto &attr_id_pair : join_group.join_attribute_pairs) {
+    DCHECK(attribute_id_to_table_info_index_map.find(attr_id_pair.first)
+               != attribute_id_to_table_info_index_map.end());
+    DCHECK(attribute_id_to_table_info_index_map.find(attr_id_pair.second)
+               != attribute_id_to_table_info_index_map.end());
+
+    std::size_t first_table_idx =
+        attribute_id_to_table_info_index_map[attr_id_pair.first];
+    std::size_t second_table_idx =
+        attribute_id_to_table_info_index_map[attr_id_pair.second];
+    DCHECK_NE(first_table_idx, second_table_idx);
+
+    table_info_storage[first_table_idx].join_attribute_pairs.emplace(
+        attr_id_pair.first, attr_id_pair.second);
+    table_info_storage[second_table_idx].join_attribute_pairs.emplace(
+        attr_id_pair.second, attr_id_pair.first);
+
+    join_graph[first_table_idx].emplace(second_table_idx);
+    join_graph[second_table_idx].emplace(first_table_idx);
+  }
+
+  std::set<TableInfo*, TableInfoPtrLessComparator> table_info_ordered_by_priority;
+  for (std::size_t i = 0; i < table_info_storage.size(); ++i) {
+    table_info_ordered_by_priority.emplace(&table_info_storage[i]);
+  }
+
+  // Contruct hash join tree.
+  while (true) {
+    TableInfo *first_table_info = *table_info_ordered_by_priority.begin();
+    table_info_ordered_by_priority.erase(
+        table_info_ordered_by_priority.begin());
+    const std::size_t first_table_info_id = first_table_info->table_info_id;
+
+    TableInfo *second_table_info = nullptr;
+    std::set<TableInfo*, TableInfoPtrLessComparator>::iterator second_table_info_it;
+    for (auto candidate_table_info_it = table_info_ordered_by_priority.begin();
+         candidate_table_info_it != table_info_ordered_by_priority.end();
+         ++candidate_table_info_it) {
+      TableInfo *candidate_table_info = *candidate_table_info_it;
+      const std::size_t candidate_table_info_id = candidate_table_info->table_info_id;
+
+      if (join_graph[first_table_info_id].find(candidate_table_info_id)
+              == join_graph[first_table_info_id].end() &&
+          join_graph[candidate_table_info_id].find(first_table_info_id)
+              == join_graph[candidate_table_info_id].end()) {
+        continue;
+      } else if (second_table_info == nullptr) {
+        second_table_info = candidate_table_info;
+        second_table_info_it = candidate_table_info_it;
+      }
+
+      bool is_likely_many_to_many_join = false;
+      for (const auto join_attr_pair : first_table_info->join_attribute_pairs) {
+        if (candidate_table_info->joined_attribute_set.find(join_attr_pair.second)
+                != candidate_table_info->joined_attribute_set.end()) {
+          is_likely_many_to_many_join = true;
+          break;
+        }
+      }
+      for (const auto join_attr_pair : candidate_table_info->join_attribute_pairs) {
+        if (first_table_info->joined_attribute_set.find(join_attr_pair.second)
+                != first_table_info->joined_attribute_set.end()) {
+          is_likely_many_to_many_join = true;
+          break;
+        }
+      }
+      if (!is_likely_many_to_many_join) {
+        second_table_info = candidate_table_info;
+        second_table_info_it = candidate_table_info_it;
+        break;
+      }
+    }
+    DCHECK(second_table_info != nullptr);
+    table_info_ordered_by_priority.erase(second_table_info_it);
+
+    const P::PhysicalPtr &left_child = first_table_info->table;
+    const P::PhysicalPtr &right_child = second_table_info->table;
+    std::vector<E::NamedExpressionPtr> output_attributes;
+    for (const E::AttributeReferencePtr &left_attr : left_child->getOutputAttributes()) {
+      output_attributes.emplace_back(left_attr);
+    }
+    for (const E::AttributeReferencePtr &right_attr : right_child->getOutputAttributes()) {
+      output_attributes.emplace_back(right_attr);
+    }
+
+    std::vector<E::AttributeReferencePtr> left_join_attributes;
+    std::vector<E::AttributeReferencePtr> right_join_attributes;
+    std::unordered_set<expressions::ExprId> new_joined_attribute_set;
+    for (const auto &join_attr_pair : first_table_info->join_attribute_pairs) {
+      if (second_table_info->join_attribute_pairs.find(join_attr_pair.second)
+              != second_table_info->join_attribute_pairs.end()) {
+        left_join_attributes.emplace_back(
+            attribute_id_to_reference_map[join_attr_pair.first]);
+        right_join_attributes.emplace_back(
+            attribute_id_to_reference_map[join_attr_pair.second]);
+
+        new_joined_attribute_set.emplace(join_attr_pair.first);
+        new_joined_attribute_set.emplace(join_attr_pair.second);
+      }
+    }
+    DCHECK_GE(left_join_attributes.size(), static_cast<std::size_t>(1));
+
+    if (table_info_ordered_by_priority.size() > 0) {
+      P::PhysicalPtr output =
+          P::HashJoin::Create(left_child,
+                              right_child,
+                              left_join_attributes,
+                              right_join_attributes,
+                              nullptr,
+                              output_attributes,
+                              P::HashJoin::JoinType::kInnerJoin);
+
+      second_table_info->table = output;
+
+      // TODO(jianqiao): Cache the estimated cardinality for each plan in cost
+      // model to avoid duplicated estimation.
+      second_table_info->estimated_cardinality = cost_model_->estimateCardinality(output);
+
+      second_table_info->join_attribute_pairs.insert(first_table_info->join_attribute_pairs.begin(),
+                                                     first_table_info->join_attribute_pairs.end());
+      second_table_info->joined_attribute_set.insert(first_table_info->joined_attribute_set.begin(),
+                                                     first_table_info->joined_attribute_set.end());
+      second_table_info->joined_attribute_set.insert(new_joined_attribute_set.begin(),
+                                                     new_joined_attribute_set.end());
+      table_info_ordered_by_priority.emplace(second_table_info);
+
+      join_graph[second_table_info->table_info_id].insert(join_graph[first_table_info_id].begin(),
+                                                          join_graph[first_table_info_id].end());
+
+    } else {
+      return P::HashJoin::Create(left_child,
+                                 right_child,
+                                 left_join_attributes,
+                                 right_join_attributes,
+                                 residual_predicate,
+                                 project_expressions,
+                                 P::HashJoin::JoinType::kInnerJoin);
+    }
+  }
+}
+
+}  // namespace optimizer
+}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp
new file mode 100644
index 0000000..deddffd
--- /dev/null
+++ b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp
@@ -0,0 +1,136 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   Licensed under the Apache License, Version 2.0 (the "License");
+ *   you may not use this file except in compliance with the License.
+ *   You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing, software
+ *   distributed under the License is distributed on an "AS IS" BASIS,
+ *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *   See the License for the specific language governing permissions and
+ *   limitations under the License.
+ **/
+
+#ifndef QUICKSTEP_QUERY_OPTIMIZER_RULES_STAR_SCHEMA_HASH_JOIN_ORDER_OPTIMIZATION_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_RULES_STAR_SCHEMA_HASH_JOIN_ORDER_OPTIMIZATION_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/expressions/NamedExpression.hpp"
+#include "query_optimizer/expressions/Predicate.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/rules/Rule.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+namespace optimizer {
+
+/** \addtogroup OptimizerRules
+ *  @{
+ */
+
+/**
+ * @brief TODO
+ */
+class StarSchemaHashJoinOrderOptimization : public Rule<physical::Physical> {
+ public:
+  StarSchemaHashJoinOrderOptimization() {}
+
+  ~StarSchemaHashJoinOrderOptimization() override {}
+
+  std::string getName() const override {
+    return "StarSchemaHashJoinOrderOptimization";
+  }
+
+  physical::PhysicalPtr apply(const physical::PhysicalPtr &input) override;
+
+ private:
+  /**
+   * @brief A group of tables to form a hash join tree.
+   */
+  struct JoinGroupInfo {
+    std::vector<physical::PhysicalPtr> tables;
+    std::vector<std::pair<expressions::ExprId, expressions::ExprId>> join_attribute_pairs;
+  };
+
+  /**
+   * @brief Auxiliary information of a table for the optimizer.
+   */
+  struct TableInfo {
+    TableInfo(const std::size_t in_table_info_id,
+              const physical::PhysicalPtr &in_table,
+              const std::size_t in_estimated_cardinality,
+              const double in_estimated_selectivity)
+        : table_info_id(in_table_info_id),
+          table(in_table),
+          estimated_cardinality(in_estimated_cardinality),
+          estimated_selectivity(in_estimated_selectivity) {
+    }
+
+    const std::size_t table_info_id;
+    physical::PhysicalPtr table;
+    std::size_t estimated_cardinality;
+    double estimated_selectivity;
+    std::unordered_multimap<expressions::ExprId, expressions::ExprId> join_attribute_pairs;
+    std::unordered_set<expressions::ExprId> joined_attribute_set;
+  };
+
+  /**
+   * @brief Comparator that compares the join priorities between two tables.
+   */
+  struct TableInfoPtrLessComparator {
+    inline bool operator() (const TableInfo *lhs, const TableInfo *rhs) {
+      bool swapped = false;
+      if (lhs->estimated_cardinality > rhs->estimated_cardinality) {
+        std::swap(lhs, rhs);
+        swapped = true;
+      }
+
+      if (lhs->estimated_selectivity < rhs->estimated_selectivity) {
+        return !swapped;
+      } else if (lhs->estimated_cardinality < 1000u &&
+                 rhs->estimated_cardinality > 10000u &&
+                 lhs->estimated_selectivity < rhs->estimated_selectivity * 1.5) {
+        return !swapped;
+      } else if (lhs->estimated_selectivity > rhs->estimated_selectivity) {
+        return swapped;
+      } else if (lhs->estimated_cardinality != rhs->estimated_cardinality) {
+        return !swapped;
+      } else {
+        return swapped ^ (lhs->table < rhs->table);
+      }
+    }
+  };
+
+  physical::PhysicalPtr applyInternal(const physical::PhysicalPtr &input,
+                                      JoinGroupInfo *paret_join_group);
+
+  physical::PhysicalPtr generatePlan(
+      const JoinGroupInfo &join_group_info,
+      const expressions::PredicatePtr &residual_predicate,
+      const std::vector<expressions::NamedExpressionPtr> &project_expressions);
+
+  std::unique_ptr<cost::StarSchemaSimpleCostModel> cost_model_;
+
+  DISALLOW_COPY_AND_ASSIGN(StarSchemaHashJoinOrderOptimization);
+};
+
+/** @} */
+
+}  // namespace optimizer
+}  // namespace quickstep
+
+#endif /* QUICKSTEP_QUERY_OPTIMIZER_RULES_STAR_SCHEMA_HASH_JOIN_ORDER_OPTIMIZATION_HPP_ */

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/tests/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/CMakeLists.txt b/query_optimizer/tests/CMakeLists.txt
index 5647bfd..07af404 100644
--- a/query_optimizer/tests/CMakeLists.txt
+++ b/query_optimizer/tests/CMakeLists.txt
@@ -132,6 +132,7 @@ target_link_libraries(quickstep_queryoptimizer_tests_ExecutionGeneratorTest
                       tmb
                       ${LIBS})
 target_link_libraries(quickstep_queryoptimizer_tests_OptimizerTextTest
+                      gflags_nothreads-static
                       glog
                       gtest
                       gtest_main

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0fffe505/query_optimizer/tests/OptimizerTextTest.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/OptimizerTextTest.cpp b/query_optimizer/tests/OptimizerTextTest.cpp
index c35cfa3..f3c243b 100644
--- a/query_optimizer/tests/OptimizerTextTest.cpp
+++ b/query_optimizer/tests/OptimizerTextTest.cpp
@@ -22,8 +22,18 @@
 #include "query_optimizer/tests/OptimizerTextTestRunner.hpp"
 #include "utility/textbased_test/TextBasedTestDriver.hpp"
 
+#include "gflags/gflags.h"
+
 #include "glog/logging.h"
 
+namespace quickstep {
+namespace optimizer {
+
+DECLARE_bool(reorder_hash_joins);
+
+}
+}
+
 using quickstep::TextBasedTest;
 
 QUICKSTEP_GENERATE_TEXT_TEST(OPTIMIZER_TEST);
@@ -45,6 +55,10 @@ int main(int argc, char** argv) {
   test_driver->registerOptions(
       quickstep::optimizer::OptimizerTextTestRunner::kTestOptions);
 
+  // Turn off join order optimization for optimizer test since it is up to change
+  // and affects a large number of test cases.
+  quickstep::optimizer::FLAGS_reorder_hash_joins = false;
+
   ::testing::InitGoogleTest(&argc, argv);
   int success = RUN_ALL_TESTS();
   if (success != 0) {


Mime
View raw message