You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by ji...@apache.org on 2016/11/07 21:34:26 UTC
[15/15] incubator-quickstep git commit: Optimizer changes for TPC-H
queries
Optimizer changes for TPC-H queries
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/c5b3eec7
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/c5b3eec7
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/c5b3eec7
Branch: refs/heads/collision-free-agg
Commit: c5b3eec7a24ce1a68f5fdcee9ae4d80939d443e1
Parents: 564897f
Author: Jianqiao Zhu <ji...@cs.wisc.edu>
Authored: Mon Nov 7 14:01:36 2016 -0600
Committer: Jianqiao Zhu <ji...@cs.wisc.edu>
Committed: Mon Nov 7 15:32:34 2016 -0600
----------------------------------------------------------------------
query_optimizer/CMakeLists.txt | 2 +
query_optimizer/LogicalGenerator.cpp | 2 +
query_optimizer/Optimizer.cpp | 4 +-
query_optimizer/Optimizer.hpp | 3 -
query_optimizer/PhysicalGenerator.cpp | 2 +
query_optimizer/PhysicalGenerator.hpp | 11 +-
.../cost_model/StarSchemaSimpleCostModel.cpp | 14 +-
query_optimizer/rules/BottomUpRule.hpp | 34 ++--
query_optimizer/rules/CMakeLists.txt | 53 ++++-
.../EliminateSemiAntiJoinResidualPredicate.cpp | 160 +++++++++++++++
.../EliminateSemiAntiJoinResidualPredicate.hpp | 55 +++++
.../rules/ReduceGroupByAttributes.cpp | 203 +++++++++++++++++++
.../rules/ReduceGroupByAttributes.hpp | 99 +++++++++
query_optimizer/rules/SwapProbeBuild.cpp | 28 +--
utility/PlanVisualizer.cpp | 3 +-
15 files changed, 629 insertions(+), 44 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index 23929e8..6091d2d 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -184,6 +184,7 @@ target_link_libraries(quickstep_queryoptimizer_LogicalGenerator
quickstep_queryoptimizer_logical_Logical
quickstep_queryoptimizer_resolver_Resolver
quickstep_queryoptimizer_rules_CollapseProject
+ quickstep_queryoptimizer_rules_EliminateSemiAntiJoinResidualPredicate
quickstep_queryoptimizer_rules_GenerateJoins
quickstep_queryoptimizer_rules_PushDownFilter
quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
@@ -216,6 +217,7 @@ target_link_libraries(quickstep_queryoptimizer_PhysicalGenerator
quickstep_queryoptimizer_rules_InjectJoinFilters
quickstep_queryoptimizer_rules_PruneColumns
quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
+ quickstep_queryoptimizer_rules_ReduceGroupByAttributes
quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
quickstep_queryoptimizer_rules_SwapProbeBuild
quickstep_queryoptimizer_strategy_Aggregate
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/LogicalGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/LogicalGenerator.cpp b/query_optimizer/LogicalGenerator.cpp
index abeca53..e9b56de 100644
--- a/query_optimizer/LogicalGenerator.cpp
+++ b/query_optimizer/LogicalGenerator.cpp
@@ -29,6 +29,7 @@
#include "query_optimizer/logical/Logical.hpp"
#include "query_optimizer/resolver/Resolver.hpp"
#include "query_optimizer/rules/CollapseProject.hpp"
+#include "query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.hpp"
#include "query_optimizer/rules/GenerateJoins.hpp"
#include "query_optimizer/rules/PushDownFilter.hpp"
#include "query_optimizer/rules/PushDownSemiAntiJoin.hpp"
@@ -66,6 +67,7 @@ void LogicalGenerator::optimizePlan() {
if (optimizer_context_->has_nested_queries()) {
rules.emplace_back(new UnnestSubqueries(optimizer_context_));
}
+ rules.emplace_back(new EliminateSemiAntiJoinResidualPredicate(optimizer_context_));
rules.emplace_back(new PushDownSemiAntiJoin());
rules.emplace_back(new PushDownFilter());
rules.emplace_back(new GenerateJoins());
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/Optimizer.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/Optimizer.cpp b/query_optimizer/Optimizer.cpp
index b14c938..2c15ead 100644
--- a/query_optimizer/Optimizer.cpp
+++ b/query_optimizer/Optimizer.cpp
@@ -21,6 +21,7 @@
#include "query_optimizer/ExecutionGenerator.hpp"
#include "query_optimizer/LogicalGenerator.hpp"
+#include "query_optimizer/PhysicalGenerator.hpp"
namespace quickstep {
namespace optimizer {
@@ -30,10 +31,11 @@ void Optimizer::generateQueryHandle(const ParseStatement &parse_statement,
OptimizerContext *optimizer_context,
QueryHandle *query_handle) {
LogicalGenerator logical_generator(optimizer_context);
+ PhysicalGenerator physical_generator(optimizer_context);
ExecutionGenerator execution_generator(catalog_database, query_handle);
execution_generator.generatePlan(
- physical_generator_.generatePlan(
+ physical_generator.generatePlan(
logical_generator.generatePlan(*catalog_database, parse_statement)));
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/Optimizer.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/Optimizer.hpp b/query_optimizer/Optimizer.hpp
index 36f956a..13b6d94 100644
--- a/query_optimizer/Optimizer.hpp
+++ b/query_optimizer/Optimizer.hpp
@@ -20,7 +20,6 @@
#ifndef QUICKSTEP_QUERY_OPTIMIZER_OPTIMIZER_HPP_
#define QUICKSTEP_QUERY_OPTIMIZER_OPTIMIZER_HPP_
-#include "query_optimizer/PhysicalGenerator.hpp"
#include "utility/Macros.hpp"
namespace quickstep {
@@ -70,8 +69,6 @@ class Optimizer {
QueryHandle *query_handle);
private:
- PhysicalGenerator physical_generator_;
-
DISALLOW_COPY_AND_ASSIGN(Optimizer);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/PhysicalGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.cpp b/query_optimizer/PhysicalGenerator.cpp
index dc9eab7..3828be6 100644
--- a/query_optimizer/PhysicalGenerator.cpp
+++ b/query_optimizer/PhysicalGenerator.cpp
@@ -30,6 +30,7 @@
#include "query_optimizer/rules/InjectJoinFilters.hpp"
#include "query_optimizer/rules/PruneColumns.hpp"
#include "query_optimizer/rules/PushDownLowCostDisjunctivePredicate.hpp"
+#include "query_optimizer/rules/ReduceGroupByAttributes.hpp"
#include "query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp"
#include "query_optimizer/rules/SwapProbeBuild.hpp"
#include "query_optimizer/strategy/Aggregate.hpp"
@@ -108,6 +109,7 @@ P::PhysicalPtr PhysicalGenerator::optimizePlan() {
std::vector<std::unique_ptr<Rule<P::Physical>>> rules;
rules.emplace_back(new PruneColumns());
rules.emplace_back(new PushDownLowCostDisjunctivePredicate());
+ rules.emplace_back(new ReduceGroupByAttributes(optimizer_context_));
if (FLAGS_reorder_hash_joins) {
rules.emplace_back(new StarSchemaHashJoinOrderOptimization());
rules.emplace_back(new PruneColumns());
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/PhysicalGenerator.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.hpp b/query_optimizer/PhysicalGenerator.hpp
index 886a173..a0b6496 100644
--- a/query_optimizer/PhysicalGenerator.hpp
+++ b/query_optimizer/PhysicalGenerator.hpp
@@ -33,6 +33,8 @@
namespace quickstep {
namespace optimizer {
+class OptimizerContext;
+
/** \addtogroup QueryOptimizer
* @{
*/
@@ -43,9 +45,12 @@ namespace optimizer {
class PhysicalGenerator : public LogicalToPhysicalMapper {
public:
/**
- * @brief Constructor
+ * @brief Constructor.
+ *
+ * @param optimizer_context The optimizer context.
*/
- PhysicalGenerator() {
+ PhysicalGenerator(OptimizerContext *optimizer_context)
+ : optimizer_context_(optimizer_context) {
createStrategies();
}
@@ -125,6 +130,8 @@ class PhysicalGenerator : public LogicalToPhysicalMapper {
*/
std::unordered_map<logical::LogicalPtr, physical::PhysicalPtr> logical_to_physical_map_;
+ OptimizerContext *optimizer_context_;
+
/**
* @brief The complete physical plan.
*/
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
index 8d38dc9..986915c 100644
--- a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
@@ -143,9 +143,13 @@ std::size_t StarSchemaSimpleCostModel::estimateCardinalityForTableGenerator(
std::size_t StarSchemaSimpleCostModel::estimateCardinalityForFilterInjection(
const P::FilterInjectionPtr &physical_plan) {
+ double build_side_filter_selectivity =
+ estimateSelectivityForPredicate(physical_plan->build_side_filter_predicate(),
+ physical_plan->right());
std::size_t left_cardinality = estimateCardinality(physical_plan->left());
double right_selectivity = estimateSelectivity(physical_plan->right());
- return static_cast<std::size_t>(left_cardinality * right_selectivity + 0.5);
+ return static_cast<std::size_t>(
+ left_cardinality * build_side_filter_selectivity * right_selectivity + 0.5);
}
std::size_t StarSchemaSimpleCostModel::estimateCardinalityForHashJoin(
@@ -283,8 +287,12 @@ double StarSchemaSimpleCostModel::estimateSelectivity(
case P::PhysicalType::kFilterInjection: {
const P::FilterInjectionPtr &filter_injection =
std::static_pointer_cast<const P::FilterInjection>(physical_plan);
- return estimateSelectivity(filter_injection->left()) *
- estimateSelectivity(filter_injection->right());
+ double left_selectivity = estimateSelectivity(filter_injection->left());
+ double right_selectivity = estimateSelectivity(filter_injection->right());
+ double build_side_filter_selectivity =
+ estimateSelectivityForPredicate(filter_injection->build_side_filter_predicate(),
+ filter_injection->right());
+ return left_selectivity * right_selectivity * build_side_filter_selectivity;
}
case P::PhysicalType::kHashJoin: {
const P::HashJoinPtr &hash_join =
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/rules/BottomUpRule.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/BottomUpRule.hpp b/query_optimizer/rules/BottomUpRule.hpp
index 53dff0d..4cafdb6 100644
--- a/query_optimizer/rules/BottomUpRule.hpp
+++ b/query_optimizer/rules/BottomUpRule.hpp
@@ -57,21 +57,7 @@ class BottomUpRule : public Rule<TreeType> {
DCHECK(tree != nullptr);
init(tree);
- std::vector<std::shared_ptr<const TreeType>> new_children;
- bool has_changed_children = false;
- for (const std::shared_ptr<const TreeType> &child : tree->children()) {
- std::shared_ptr<const TreeType> new_child = apply(child);
- if (child != new_child && !has_changed_children) {
- has_changed_children = true;
- }
- new_children.push_back(new_child);
- }
-
- if (has_changed_children) {
- return applyToNode(tree->copyWithNewChildren(new_children));
- } else {
- return applyToNode(tree);
- }
+ return applyInternal(tree);
}
protected:
@@ -93,6 +79,24 @@ class BottomUpRule : public Rule<TreeType> {
}
private:
+ TreeNodePtr applyInternal(const TreeNodePtr &tree) {
+ std::vector<std::shared_ptr<const TreeType>> new_children;
+ bool has_changed_children = false;
+ for (const std::shared_ptr<const TreeType> &child : tree->children()) {
+ std::shared_ptr<const TreeType> new_child = applyInternal(child);
+ if (child != new_child && !has_changed_children) {
+ has_changed_children = true;
+ }
+ new_children.push_back(new_child);
+ }
+
+ if (has_changed_children) {
+ return applyToNode(tree->copyWithNewChildren(new_children));
+ } else {
+ return applyToNode(tree);
+ }
+ }
+
DISALLOW_COPY_AND_ASSIGN(BottomUpRule);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/rules/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CMakeLists.txt b/query_optimizer/rules/CMakeLists.txt
index cace3f2..0994b68 100644
--- a/query_optimizer/rules/CMakeLists.txt
+++ b/query_optimizer/rules/CMakeLists.txt
@@ -21,6 +21,9 @@ add_subdirectory(tests)
add_library(quickstep_queryoptimizer_rules_AttachLIPFilters AttachLIPFilters.cpp AttachLIPFilters.hpp)
add_library(quickstep_queryoptimizer_rules_BottomUpRule ../../empty_src.cpp BottomUpRule.hpp)
add_library(quickstep_queryoptimizer_rules_CollapseProject CollapseProject.cpp CollapseProject.hpp)
+add_library(quickstep_queryoptimizer_rules_EliminateSemiAntiJoinResidualPredicate
+ EliminateSemiAntiJoinResidualPredicate.cpp
+ EliminateSemiAntiJoinResidualPredicate.hpp)
add_library(quickstep_queryoptimizer_rules_GenerateJoins GenerateJoins.cpp GenerateJoins.hpp)
add_library(quickstep_queryoptimizer_rules_InjectJoinFilters InjectJoinFilters.cpp InjectJoinFilters.hpp)
add_library(quickstep_queryoptimizer_rules_PruneColumns PruneColumns.cpp PruneColumns.hpp)
@@ -29,6 +32,9 @@ add_library(quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
PushDownLowCostDisjunctivePredicate.cpp
PushDownLowCostDisjunctivePredicate.hpp)
add_library(quickstep_queryoptimizer_rules_PushDownSemiAntiJoin PushDownSemiAntiJoin.cpp PushDownSemiAntiJoin.hpp)
+add_library(quickstep_queryoptimizer_rules_ReduceGroupByAttributes
+ ReduceGroupByAttributes.cpp
+ ReduceGroupByAttributes.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
@@ -71,6 +77,30 @@ target_link_libraries(quickstep_queryoptimizer_rules_CollapseProject
quickstep_queryoptimizer_rules_Rule
quickstep_queryoptimizer_rules_RuleHelper
quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_rules_EliminateSemiAntiJoinResidualPredicate
+ glog
+ quickstep_expressions_aggregation_AggregateFunctionCount
+ quickstep_queryoptimizer_OptimizerContext
+ quickstep_queryoptimizer_expressions_AggregateFunction
+ quickstep_queryoptimizer_expressions_Alias
+ quickstep_queryoptimizer_expressions_AttributeReference
+ quickstep_queryoptimizer_expressions_ComparisonExpression
+ quickstep_queryoptimizer_expressions_ExpressionUtil
+ quickstep_queryoptimizer_expressions_Predicate
+ quickstep_queryoptimizer_expressions_ScalarLiteral
+ quickstep_queryoptimizer_logical_Aggregate
+ quickstep_queryoptimizer_logical_Filter
+ quickstep_queryoptimizer_logical_HashJoin
+ quickstep_queryoptimizer_logical_Logical
+ quickstep_queryoptimizer_logical_PatternMatcher
+ quickstep_queryoptimizer_rules_BottomUpRule
+ quickstep_types_LongType
+ quickstep_types_TypedValue
+ quickstep_types_operations_comparisons_Comparison
+ quickstep_types_operations_comparisons_ComparisonID
+ quickstep_types_operations_comparisons_EqualComparison
+ quickstep_types_operations_comparisons_GreaterComparison
+ quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_rules_GenerateJoins
glog
quickstep_queryoptimizer_expressions_AttributeReference
@@ -140,6 +170,25 @@ target_link_libraries(quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
quickstep_queryoptimizer_logical_PatternMatcher
quickstep_queryoptimizer_rules_TopDownRule
quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_rules_ReduceGroupByAttributes
+ quickstep_catalog_CatalogRelation
+ quickstep_types_TypeID
+ quickstep_queryoptimizer_OptimizerContext
+ quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
+ quickstep_queryoptimizer_expressions_NamedExpression
+ quickstep_queryoptimizer_expressions_AttributeReference
+ quickstep_queryoptimizer_expressions_ExprId
+ quickstep_queryoptimizer_expressions_ExpressionUtil
+ quickstep_queryoptimizer_physical_Aggregate
+ quickstep_queryoptimizer_physical_HashJoin
+ quickstep_queryoptimizer_physical_PatternMatcher
+ quickstep_queryoptimizer_physical_Physical
+ quickstep_queryoptimizer_physical_PhysicalType
+ quickstep_queryoptimizer_physical_TableReference
+ quickstep_queryoptimizer_physical_TopLevelPlan
+ quickstep_queryoptimizer_rules_PruneColumns
+ quickstep_queryoptimizer_rules_Rule
+ quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_rules_Rule
glog
quickstep_utility_Macros)
@@ -170,6 +219,7 @@ target_link_libraries(quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOpti
quickstep_utility_DisjointTreeForest
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_rules_SwapProbeBuild
+ glog
quickstep_queryoptimizer_costmodel_SimpleCostModel
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_physical_HashJoin
@@ -204,7 +254,6 @@ target_link_libraries(quickstep_queryoptimizer_rules_InjectJoinFilters
quickstep_utility_lipfilter_LIPFilter)
target_link_libraries(quickstep_queryoptimizer_rules_UnnestSubqueries
quickstep_queryoptimizer_OptimizerContext
- quickstep_queryoptimizer_expressions_Alias
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_ComparisonExpression
quickstep_queryoptimizer_expressions_Exists
@@ -252,12 +301,14 @@ target_link_libraries(quickstep_queryoptimizer_rules
quickstep_queryoptimizer_rules_AttachLIPFilters
quickstep_queryoptimizer_rules_BottomUpRule
quickstep_queryoptimizer_rules_CollapseProject
+ quickstep_queryoptimizer_rules_EliminateSemiAntiJoinResidualPredicate
quickstep_queryoptimizer_rules_GenerateJoins
quickstep_queryoptimizer_rules_InjectJoinFilters
quickstep_queryoptimizer_rules_PruneColumns
quickstep_queryoptimizer_rules_PushDownFilter
quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
+ quickstep_queryoptimizer_rules_ReduceGroupByAttributes
quickstep_queryoptimizer_rules_Rule
quickstep_queryoptimizer_rules_RuleHelper
quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.cpp b/query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.cpp
new file mode 100644
index 0000000..c46aa50
--- /dev/null
+++ b/query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.cpp
@@ -0,0 +1,160 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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/EliminateSemiAntiJoinResidualPredicate.hpp"
+
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+#include "expressions/aggregation/AggregateFunctionCount.hpp"
+#include "query_optimizer/OptimizerContext.hpp"
+#include "query_optimizer/expressions/AggregateFunction.hpp"
+#include "query_optimizer/expressions/Alias.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ComparisonExpression.hpp"
+#include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/expressions/Predicate.hpp"
+#include "query_optimizer/expressions/ScalarLiteral.hpp"
+#include "query_optimizer/logical/Aggregate.hpp"
+#include "query_optimizer/logical/Filter.hpp"
+#include "query_optimizer/logical/HashJoin.hpp"
+#include "query_optimizer/logical/Logical.hpp"
+#include "query_optimizer/logical/PatternMatcher.hpp"
+#include "types/LongType.hpp"
+#include "types/TypedValue.hpp"
+#include "types/operations/comparisons/Comparison.hpp"
+#include "types/operations/comparisons/ComparisonID.hpp"
+#include "types/operations/comparisons/EqualComparison.hpp"
+#include "types/operations/comparisons/GreaterComparison.hpp"
+
+namespace quickstep {
+namespace optimizer {
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace L = ::quickstep::optimizer::logical;
+
+L::LogicalPtr EliminateSemiAntiJoinResidualPredicate::applyToNode(
+ const L::LogicalPtr &input) {
+ L::HashJoinPtr hash_join;
+ if (!L::SomeHashJoin::MatchesWithConditionalCast(input, &hash_join) ||
+ hash_join->residual_predicate() == nullptr) {
+ return input;
+ }
+
+ switch (hash_join->join_type()) {
+ case L::HashJoin::JoinType::kLeftSemiJoin: // Fall through
+ case L::HashJoin::JoinType::kLeftAntiJoin:
+ break;
+ default:
+ return input;
+ }
+
+ E::ComparisonExpressionPtr comparison_expression;
+ const bool is_comparison =
+ E::SomeComparisonExpression::MatchesWithConditionalCast(
+ hash_join->residual_predicate(),
+ &comparison_expression);
+ if (!is_comparison ||
+ comparison_expression->comparison().getComparisonID() != ComparisonID::kNotEqual) {
+ return input;
+ }
+
+ E::AttributeReferencePtr lhs_attribute;
+ E::AttributeReferencePtr rhs_attribute;
+ if (!E::SomeAttributeReference::MatchesWithConditionalCast(
+ comparison_expression->left(), &lhs_attribute) ||
+ !E::SomeAttributeReference::MatchesWithConditionalCast(
+ comparison_expression->right(), &rhs_attribute)) {
+ return input;
+ }
+
+ const L::LogicalPtr &left_child = hash_join->left();
+ const L::LogicalPtr &right_child = hash_join->right();
+
+ // TODO(jianqiao): IMPORTANT: (limited) check query containment: right_child
+ // $\supersetequal$ left_child
+
+ E::AttributeReferencePtr probe_side_attribute;
+ E::AttributeReferencePtr build_side_attribute;
+ if (E::ContainsExprId(left_child->getOutputAttributes(), lhs_attribute->id())) {
+ DCHECK(E::ContainsExprId(right_child->getOutputAttributes(), rhs_attribute->id()));
+ probe_side_attribute = lhs_attribute;
+ build_side_attribute = rhs_attribute;
+ } else {
+ DCHECK(E::ContainsExprId(left_child->getOutputAttributes(), rhs_attribute->id()));
+ DCHECK(E::ContainsExprId(right_child->getOutputAttributes(), lhs_attribute->id()));
+ probe_side_attribute = rhs_attribute;
+ build_side_attribute = lhs_attribute;
+ }
+
+ // TODO(jianqiao): IMPORTANT: count_distinct_equal_one operator
+
+ const E::AggregateFunctionPtr count_function =
+ E::AggregateFunction::Create(quickstep::AggregateFunctionCount::Instance(),
+ {build_side_attribute},
+ true /* is_vector_aggregate */,
+ false /* is_distinct */);
+ const E::AliasPtr count_alias =
+ E::Alias::Create(context_->nextExprId(),
+ count_function,
+ "",
+ "COUNT(" + build_side_attribute->attribute_name() + ")");
+
+ const L::AggregatePtr aggregate =
+ L::Aggregate::Create(right_child,
+ E::ToNamedExpressions(hash_join->right_join_attributes()),
+ {count_alias});
+
+ const E::ScalarLiteralPtr literal_one =
+ E::ScalarLiteral::Create(TypedValue(static_cast<std::int64_t>(1)),
+ LongType::InstanceNonNullable());
+
+ E::PredicatePtr uniqueness_predicate;
+ switch (hash_join->join_type()) {
+ case L::HashJoin::JoinType::kLeftSemiJoin: {
+ uniqueness_predicate =
+ E::ComparisonExpression::Create(quickstep::GreaterComparison::Instance(),
+ E::ToRef(count_alias),
+ literal_one);
+ break;
+ }
+ case L::HashJoin::JoinType::kLeftAntiJoin:
+ uniqueness_predicate =
+ E::ComparisonExpression::Create(quickstep::EqualComparison::Instance(),
+ E::ToRef(count_alias),
+ literal_one);
+ break;
+ default:
+ LOG(FATAL) << "Not supported";
+ }
+
+ const L::FilterPtr filter =
+ L::Filter::Create(aggregate, uniqueness_predicate);
+
+ return L::HashJoin::Create(left_child,
+ filter,
+ hash_join->left_join_attributes(),
+ hash_join->right_join_attributes(),
+ nullptr,
+ L::HashJoin::JoinType::kLeftSemiJoin);
+}
+
+} // namespace optimizer
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.hpp b/query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.hpp
new file mode 100644
index 0000000..77a63a2
--- /dev/null
+++ b/query_optimizer/rules/EliminateSemiAntiJoinResidualPredicate.hpp
@@ -0,0 +1,55 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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_ELIMINATE_SEMI_ANTI_JOIN_RESIDUAL_PREDICATE_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_RULES_ELIMINATE_SEMI_ANTI_JOIN_RESIDUAL_PREDICATE_HPP_
+
+#include <string>
+
+#include "query_optimizer/logical/Logical.hpp"
+#include "query_optimizer/rules/BottomUpRule.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+namespace optimizer {
+
+class OptimizerContext;
+
+class EliminateSemiAntiJoinResidualPredicate : public BottomUpRule<logical::Logical> {
+ public:
+ EliminateSemiAntiJoinResidualPredicate(OptimizerContext *context)
+ : context_(context) {}
+
+ std::string getName() const override {
+ return "EliminateSemiAntiJoinResidualPredicate";
+ }
+
+ protected:
+ logical::LogicalPtr applyToNode(const logical::LogicalPtr &input) override;
+
+ private:
+ OptimizerContext *context_;
+
+ DISALLOW_COPY_AND_ASSIGN(EliminateSemiAntiJoinResidualPredicate);
+};
+
+} // namespace optimizer
+} // namespace quickstep
+
+#endif // QUICKSTEP_QUERY_OPTIMIZER_RULES_ELIMINATE_SEMI_ANTI_JOIN_RESIDUAL_PREDICATE_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/rules/ReduceGroupByAttributes.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/ReduceGroupByAttributes.cpp b/query_optimizer/rules/ReduceGroupByAttributes.cpp
new file mode 100644
index 0000000..effe5a8
--- /dev/null
+++ b/query_optimizer/rules/ReduceGroupByAttributes.cpp
@@ -0,0 +1,203 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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/ReduceGroupByAttributes.hpp"
+
+#include <algorithm>
+#include <map>
+#include <vector>
+#include <unordered_set>
+#include <utility>
+
+#include "catalog/CatalogRelation.hpp"
+#include "query_optimizer/OptimizerContext.hpp"
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/expressions/NamedExpression.hpp"
+#include "query_optimizer/physical/Aggregate.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/TableReference.hpp"
+#include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/rules/PruneColumns.hpp"
+#include "types/TypeID.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace P = ::quickstep::optimizer::physical;
+
+
+P::PhysicalPtr ReduceGroupByAttributes::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()));
+
+ // Check
+ P::PhysicalPtr output = applyInternal(input);
+ if (output != input) {
+ output = PruneColumns().apply(output);
+ }
+ return output;
+}
+
+P::PhysicalPtr ReduceGroupByAttributes::applyInternal(const P::PhysicalPtr &input) {
+ std::vector<P::PhysicalPtr> new_children;
+ for (const P::PhysicalPtr &child : input->children()) {
+ new_children.push_back(applyInternal(child));
+ }
+
+ if (new_children != input->children()) {
+ return applyToNode(input->copyWithNewChildren(new_children));
+ } else {
+ return applyToNode(input);
+ }
+}
+
+P::PhysicalPtr ReduceGroupByAttributes::applyToNode(const P::PhysicalPtr &input) {
+ P::TableReferencePtr table_reference;
+ if (P::SomeTableReference::MatchesWithConditionalCast(input, &table_reference)) {
+ for (const auto &attr : table_reference->attribute_list()) {
+ source_.emplace(attr->id(), std::make_pair(table_reference, attr));
+ }
+ return input;
+ }
+
+ P::AggregatePtr aggregate;
+ if (!P::SomeAggregate::MatchesWithConditionalCast(input, &aggregate) ||
+ aggregate->grouping_expressions().size() <= 1u) {
+ return input;
+ }
+
+ std::map<P::TableReferencePtr, std::vector<E::AttributeReferencePtr>> table_attributes;
+ for (const auto &expr : aggregate->grouping_expressions()) {
+ const auto source_it = source_.find(expr->id());
+ if (source_it != source_.end()) {
+ table_attributes[source_it->second.first].emplace_back(source_it->second.second);
+ }
+ }
+
+ std::unordered_set<E::ExprId> erased_grouping_attr_ids;
+ std::vector<std::pair<P::TableReferencePtr, E::AttributeReferencePtr>> hoisted_tables;
+ for (const auto &pair : table_attributes) {
+ const P::TableReferencePtr table = pair.first;
+ const std::vector<E::AttributeReferencePtr> &attributes = pair.second;
+ // TODO(jianqiao): find a cost-based metic instead of hard-coding the threshold
+ // number of group-by attributes.
+ if (attributes.size() <= 3u) {
+ continue;
+ }
+
+ std::vector<AttributeInfo> attr_infos;
+ std::vector<const AttributeInfo *> attr_info_refs;
+ for (const auto &attr : attributes) {
+ attr_infos.emplace_back(attr,
+ cost_model_->impliesUniqueAttributes(table, {attr}),
+ !attr->getValueType().isVariableLength(),
+ attr->getValueType().maximumByteLength());
+ attr_info_refs.emplace_back(&attr_infos.back());
+ }
+ std::sort(attr_info_refs.begin(),
+ attr_info_refs.end(),
+ AttributeInfo::IsBetterThan);
+
+ const AttributeInfo &best_candidate = *attr_info_refs.front();
+ if (!best_candidate.is_unique) {
+ // Cannot find a key attribute
+ continue;
+ }
+
+ const E::AttributeReferencePtr &key_attribute = best_candidate.attribute;
+ hoisted_tables.emplace_back(table, key_attribute);
+
+ for (const auto &attr : attributes) {
+ if (attr->id() != key_attribute->id()) {
+ erased_grouping_attr_ids.emplace(attr->id());
+ }
+ }
+ }
+
+ if (erased_grouping_attr_ids.empty()) {
+ return input;
+ }
+
+ std::vector<E::NamedExpressionPtr> reduced_grouping_expressions;
+ for (const auto &expr : aggregate->grouping_expressions()) {
+ if (erased_grouping_attr_ids.find(expr->id()) == erased_grouping_attr_ids.end()) {
+ reduced_grouping_expressions.emplace_back(expr);
+ }
+ }
+
+ const P::AggregatePtr new_aggregate =
+ P::Aggregate::Create(aggregate->input(),
+ reduced_grouping_expressions,
+ aggregate->aggregate_expressions(),
+ aggregate->filter_predicate());
+
+ P::PhysicalPtr output = new_aggregate;
+ std::vector<E::NamedExpressionPtr> project_expressions =
+ E::ToNamedExpressions(output->getOutputAttributes());
+ for (const auto &pair : hoisted_tables) {
+ const P::TableReferencePtr &source_table = pair.first;
+ const E::AttributeReferencePtr &probe_attribute = pair.second;
+
+ E::AttributeReferencePtr build_attribute;
+ std::vector<E::AttributeReferencePtr> new_attribute_list;
+ for (const auto &attr : source_table->attribute_list()) {
+ if (attr->id() == probe_attribute->id()) {
+ build_attribute =
+ E::AttributeReference::Create(optimizer_context_->nextExprId(),
+ attr->attribute_name(),
+ attr->attribute_alias(),
+ attr->relation_name(),
+ attr->getValueType(),
+ E::AttributeReferenceScope::kLocal);
+ new_attribute_list.emplace_back(build_attribute);
+ } else {
+ new_attribute_list.emplace_back(attr);
+ project_expressions.emplace_back(attr);
+ }
+ }
+
+ DCHECK(build_attribute != nullptr);
+ const P::TableReferencePtr build_side_table =
+ P::TableReference::Create(source_table->relation(),
+ source_table->relation()->getName(),
+ new_attribute_list);
+ output = P::HashJoin::Create(output,
+ build_side_table,
+ {probe_attribute},
+ {build_attribute},
+ nullptr,
+ project_expressions,
+ P::HashJoin::JoinType::kInnerJoin);
+ }
+
+ return output;
+}
+
+} // namespace optimizer
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/rules/ReduceGroupByAttributes.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/ReduceGroupByAttributes.hpp b/query_optimizer/rules/ReduceGroupByAttributes.hpp
new file mode 100644
index 0000000..9402ef0
--- /dev/null
+++ b/query_optimizer/rules/ReduceGroupByAttributes.hpp
@@ -0,0 +1,99 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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_REDUCE_GROUP_BY_ATTRIBUTES_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_RULES_REDUCE_GROUP_BY_ATTRIBUTES_HPP_
+
+#include <memory>
+#include <string>
+#include <unordered_map>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/TableReference.hpp"
+#include "query_optimizer/rules/Rule.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+namespace optimizer {
+
+class OptimizerContext;
+
+class ReduceGroupByAttributes : public Rule<physical::Physical> {
+ public:
+ ReduceGroupByAttributes(OptimizerContext *optimizer_context)
+ : optimizer_context_(optimizer_context) {}
+
+ ~ReduceGroupByAttributes() override {}
+
+ std::string getName() const override {
+ return "ReduceGroupByAttributes";
+ }
+
+ physical::PhysicalPtr apply(const physical::PhysicalPtr &input) override;
+
+ private:
+ struct AttributeInfo {
+ AttributeInfo(const expressions::AttributeReferencePtr attribute_in,
+ const bool is_unique_in,
+ const bool is_fixed_length_in,
+ const std::size_t maximum_size_in)
+ : attribute(attribute_in),
+ is_unique(is_unique_in),
+ is_fixed_length(is_fixed_length_in),
+ maximum_size(maximum_size_in) {}
+
+ inline static bool IsBetterThan(const AttributeInfo *lhs,
+ const AttributeInfo *rhs) {
+ if (lhs->is_unique != rhs->is_unique) {
+ return lhs->is_unique;
+ }
+ if (lhs->is_fixed_length != rhs->is_fixed_length) {
+ return lhs->is_fixed_length;
+ }
+ if (lhs->maximum_size != rhs->maximum_size) {
+ return lhs->maximum_size < rhs->maximum_size;
+ }
+ return lhs->attribute->id() < rhs->attribute->id();
+ }
+
+ const expressions::AttributeReferencePtr attribute;
+ const bool is_unique;
+ const bool is_fixed_length;
+ const std::size_t maximum_size;
+ };
+
+ physical::PhysicalPtr applyInternal(const physical::PhysicalPtr &input);
+ physical::PhysicalPtr applyToNode(const physical::PhysicalPtr &input);
+
+ OptimizerContext *optimizer_context_;
+ std::unique_ptr<cost::StarSchemaSimpleCostModel> cost_model_;
+
+ std::unordered_map<expressions::ExprId,
+ std::pair<physical::TableReferencePtr,
+ expressions::AttributeReferencePtr>> source_;
+
+ DISALLOW_COPY_AND_ASSIGN(ReduceGroupByAttributes);
+};
+
+} // namespace optimizer
+} // namespace quickstep
+
+#endif // QUICKSTEP_QUERY_OPTIMIZER_RULES_REDUCE_GROUP_BY_ATTRIBUTES_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/query_optimizer/rules/SwapProbeBuild.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/SwapProbeBuild.cpp b/query_optimizer/rules/SwapProbeBuild.cpp
index cc3f1e2..c51776b 100644
--- a/query_optimizer/rules/SwapProbeBuild.cpp
+++ b/query_optimizer/rules/SwapProbeBuild.cpp
@@ -30,6 +30,7 @@
#include "query_optimizer/physical/TopLevelPlan.hpp"
#include "query_optimizer/rules/Rule.hpp"
+#include "glog/logging.h"
namespace quickstep {
namespace optimizer {
@@ -39,20 +40,17 @@ P::PhysicalPtr SwapProbeBuild::applyToNode(const P::PhysicalPtr &input) {
if (P::SomeHashJoin::MatchesWithConditionalCast(input, &hash_join)
&& hash_join->join_type() == P::HashJoin::JoinType::kInnerJoin) {
- P::PhysicalPtr left = hash_join->left();
- P::PhysicalPtr right = hash_join->right();
+ const P::PhysicalPtr &left = hash_join->left();
+ const P::PhysicalPtr &right = hash_join->right();
- std::size_t left_cardinality = cost_model_->estimateCardinality(left);
- std::size_t right_cardinality = cost_model_->estimateCardinality(right);
+ const std::size_t left_cardinality = cost_model_->estimateCardinality(left);
+ const std::size_t right_cardinality = cost_model_->estimateCardinality(right);
if (right_cardinality > left_cardinality) {
- std::vector<E::AttributeReferencePtr> left_join_attributes = hash_join->left_join_attributes();
- std::vector<E::AttributeReferencePtr> right_join_attributes = hash_join->right_join_attributes();
-
P::PhysicalPtr output = P::HashJoin::Create(right,
left,
- right_join_attributes,
- left_join_attributes,
+ hash_join->right_join_attributes(),
+ hash_join->left_join_attributes(),
hash_join->residual_predicate(),
hash_join->project_expressions(),
hash_join->join_type());
@@ -66,15 +64,9 @@ P::PhysicalPtr SwapProbeBuild::applyToNode(const P::PhysicalPtr &input) {
}
void SwapProbeBuild::init(const P::PhysicalPtr &input) {
- if (cost_model_ == nullptr) {
- P::TopLevelPlanPtr top_level;
- if (P::SomeTopLevelPlan::MatchesWithConditionalCast(input, &top_level)) {
- cost_model_.reset(new C::SimpleCostModel(top_level->shared_subplans()));
- } else {
- std::vector<P::PhysicalPtr> plans = {input};
- cost_model_.reset(new C::SimpleCostModel(plans));
- }
- }
+ DCHECK(input->getPhysicalType() == P::PhysicalType::kTopLevelPlan);
+ cost_model_.reset(new C::SimpleCostModel(
+ std::static_pointer_cast<const P::TopLevelPlan>(input)->shared_subplans()));
}
} // namespace optimizer
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c5b3eec7/utility/PlanVisualizer.cpp
----------------------------------------------------------------------
diff --git a/utility/PlanVisualizer.cpp b/utility/PlanVisualizer.cpp
index 1124f6a..1d0fd16 100644
--- a/utility/PlanVisualizer.cpp
+++ b/utility/PlanVisualizer.cpp
@@ -136,7 +136,8 @@ void PlanVisualizer::visit(const P::PhysicalPtr &input) {
for (const auto &attr : child->getOutputAttributes()) {
if (referenced_ids.find(attr->id()) != referenced_ids.end()) {
- edge_info.labels.emplace_back(attr->attribute_alias());
+ edge_info.labels.emplace_back(
+ "[" + std::to_string(attr->id()) + "] " + attr->attribute_alias());
}
}
}