You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by hb...@apache.org on 2016/06/04 23:03:44 UTC
[28/41] incubator-quickstep git commit: Added hash join order
optimization for star schema queries. (#229)
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 <ji...@cs.wisc.edu>
Authored: Thu May 19 18:19:28 2016 -0500
Committer: Zuyu Zhang <zz...@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\u2014Madison.
*
* 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\u2014Madison.
#
# 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\u2014Madison.
+ *
+ * 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\u2014Madison.
+ *
+ * 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\u2014Madison.
+ *
+ * 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\u2014Madison.
+ *
+ * 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) {