Repository: incubator-quickstep Updated Branches: refs/heads/selection-probe-fuse 8f705ed54 -> e7232c13d
Moved hash swap logic from ExecutionGenerator to physical optimization. Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/e7232c13 Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/e7232c13 Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/e7232c13 Branch: refs/heads/selection-probe-fuse Commit: e7232c13d28e9ff784376fbf19de297328012ea6 Parents: 8f705ed Author: Hakan Memisoglu <hakanmemiso...@apache.org> Authored: Thu Jul 28 00:16:08 2016 -0500 Committer: Hakan Memisoglu <hakanmemiso...@apache.org> Committed: Thu Jul 28 00:16:08 2016 -0500 ---------------------------------------------------------------------- query_optimizer/CMakeLists.txt | 1 + query_optimizer/ExecutionGenerator.cpp | 5 ++- query_optimizer/PhysicalGenerator.cpp | 3 ++ query_optimizer/physical/HashJoin.cpp | 6 +-- query_optimizer/physical/HashJoin.hpp | 8 ++-- query_optimizer/rules/CMakeLists.txt | 1 + query_optimizer/rules/FuseJoinSelect.cpp | 3 +- query_optimizer/rules/SwapProbeBuild.cpp | 53 +++++++++++++++++++++++++++ query_optimizer/rules/SwapProbeBuild.hpp | 38 +++++++++++++++++++ 9 files changed, 108 insertions(+), 10 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt index 65368c3..9e405ae 100644 --- a/query_optimizer/CMakeLists.txt +++ b/query_optimizer/CMakeLists.txt @@ -198,6 +198,7 @@ target_link_libraries(quickstep_queryoptimizer_PhysicalGenerator quickstep_queryoptimizer_rules_FuseJoinSelect quickstep_queryoptimizer_rules_PruneColumns quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization + quickstep_queryoptimizer_rules_SwapProbeBuild quickstep_queryoptimizer_strategy_Aggregate quickstep_queryoptimizer_strategy_Join quickstep_queryoptimizer_strategy_OneToOne http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/ExecutionGenerator.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/ExecutionGenerator.cpp b/query_optimizer/ExecutionGenerator.cpp index 9f6c5f2..ce8ab97 100644 --- a/query_optimizer/ExecutionGenerator.cpp +++ b/query_optimizer/ExecutionGenerator.cpp @@ -669,6 +669,7 @@ void ExecutionGenerator::convertHashJoin(const P::HashJoinPtr &physical_plan) { key_types.push_back(&left_attribute_type); } + /** std::size_t probe_cardinality = cost_model_->estimateCardinality(probe_physical); std::size_t build_cardinality = cost_model_->estimateCardinality(build_physical); // For inner join, we may swap the probe table and the build table. @@ -685,6 +686,7 @@ void ExecutionGenerator::convertHashJoin(const P::HashJoinPtr &physical_plan) { std::swap(referenced_stored_probe_relation, referenced_stored_build_relation); } } + **/ // Convert the residual predicate proto. QueryContext::predicate_id residual_predicate_index = QueryContext::kInvalidPredicateId; @@ -749,7 +751,8 @@ void ExecutionGenerator::convertHashJoin(const P::HashJoinPtr &physical_plan) { build_relation->getAttributeById(build_attribute)->getType().getProto()); } - hash_table_proto->set_estimated_num_entries(build_cardinality); + // hash_table_proto->set_estimated_num_entries(build_cardinality); + hash_table_proto->set_estimated_num_entries(0); // Create three operators. const QueryPlan::DAGNodeIndex build_operator_index = http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/PhysicalGenerator.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/PhysicalGenerator.cpp b/query_optimizer/PhysicalGenerator.cpp index 41d33a9..db6b33c 100644 --- a/query_optimizer/PhysicalGenerator.cpp +++ b/query_optimizer/PhysicalGenerator.cpp @@ -29,6 +29,7 @@ #include "query_optimizer/rules/FuseJoinSelect.hpp" #include "query_optimizer/rules/PruneColumns.hpp" #include "query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp" +#include "query_optimizer/rules/SwapProbeBuild.hpp" #include "query_optimizer/strategy/Aggregate.hpp" #include "query_optimizer/strategy/Join.hpp" #include "query_optimizer/strategy/OneToOne.hpp" @@ -100,6 +101,8 @@ P::PhysicalPtr PhysicalGenerator::optimizePlan() { } rules.emplace_back(new PruneColumns()); + rules.emplace_back(new SwapProbeBuild()); + rules.emplace_back(new FuseJoinSelect()); for (std::unique_ptr<Rule<P::Physical>> &rule : rules) { http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/physical/HashJoin.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/physical/HashJoin.cpp b/query_optimizer/physical/HashJoin.cpp index 6420940..d2f2c47 100644 --- a/query_optimizer/physical/HashJoin.cpp +++ b/query_optimizer/physical/HashJoin.cpp @@ -102,9 +102,9 @@ void HashJoin::getFieldStringItems( non_container_child_field_names->push_back("residual_predicate"); non_container_child_fields->push_back(residual_predicate_); } - if (filter_predicate_ != nullptr) { - non_container_child_field_names->push_back("right_filter_predicate"); - non_container_child_fields->push_back(filter_predicate_); + if (left_filter_predicate_ != nullptr) { + non_container_child_field_names->push_back("left_filter_predicate"); + non_container_child_fields->push_back(left_filter_predicate_); } container_child_field_names->push_back("left_join_attributes"); http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/physical/HashJoin.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/physical/HashJoin.hpp b/query_optimizer/physical/HashJoin.hpp index 7fb6e29..6e81f9e 100644 --- a/query_optimizer/physical/HashJoin.hpp +++ b/query_optimizer/physical/HashJoin.hpp @@ -103,7 +103,7 @@ class HashJoin : public BinaryJoin { * @brief Fused filter predicate. */ const expressions::PredicatePtr& filter_predicate() const { - return filter_predicate_; + return left_filter_predicate_; } /** @@ -201,13 +201,13 @@ class HashJoin : public BinaryJoin { const expressions::PredicatePtr &residual_predicate, const std::vector<expressions::NamedExpressionPtr> &project_expressions, const JoinType join_type, - const expressions::PredicatePtr &filter_predicate = nullptr) + const expressions::PredicatePtr &left_filter_predicate = nullptr) : BinaryJoin(left, right, project_expressions), left_join_attributes_(left_join_attributes), right_join_attributes_(right_join_attributes), residual_predicate_(residual_predicate), join_type_(join_type), - filter_predicate_(filter_predicate) { + left_filter_predicate_(left_filter_predicate) { } std::vector<expressions::AttributeReferencePtr> left_join_attributes_; @@ -215,7 +215,7 @@ class HashJoin : public BinaryJoin { expressions::PredicatePtr residual_predicate_; JoinType join_type_; - expressions::PredicatePtr filter_predicate_; + expressions::PredicatePtr left_filter_predicate_; DISALLOW_COPY_AND_ASSIGN(HashJoin); }; http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/rules/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/query_optimizer/rules/CMakeLists.txt b/query_optimizer/rules/CMakeLists.txt index 4c064e9..482d877 100644 --- a/query_optimizer/rules/CMakeLists.txt +++ b/query_optimizer/rules/CMakeLists.txt @@ -30,6 +30,7 @@ add_library(quickstep_queryoptimizer_rules_RuleHelper RuleHelper.cpp RuleHelper. add_library(quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization StarSchemaHashJoinOrderOptimization.cpp StarSchemaHashJoinOrderOptimization.hpp) +add_library(quickstep_queryoptimizer_rules_SwapProbeBuild SwapProbeBuild.cpp SwapProbeBuild.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) http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/rules/FuseJoinSelect.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/rules/FuseJoinSelect.cpp b/query_optimizer/rules/FuseJoinSelect.cpp index 5dfe015..fecaaa1 100644 --- a/query_optimizer/rules/FuseJoinSelect.cpp +++ b/query_optimizer/rules/FuseJoinSelect.cpp @@ -16,14 +16,13 @@ namespace P = ::quickstep::optimizer::physical; namespace E = ::quickstep::optimizer::expressions; P::PhysicalPtr FuseJoinSelect::applyToNode(const P::PhysicalPtr &input) { - P::HashJoinPtr hash_join; P::SelectionPtr selection; P::TableReferencePtr table_reference; if (P::SomeHashJoin::MatchesWithConditionalCast(input, &hash_join) && hash_join->join_type() == P::HashJoin::JoinType::kInnerJoin - && P::SomeSelection::MatchesWithConditionalCast(hash_join->right(), &selection) + && P::SomeSelection::MatchesWithConditionalCast(hash_join->left(), &selection) && P::SomeTableReference::MatchesWithConditionalCast(selection->input(), &table_reference)) { const E::PredicatePtr filter_predicate = selection->filter_predicate(); P::PhysicalPtr output = P::HashJoin::CreateWithFusedSelect(hash_join->left(), http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/rules/SwapProbeBuild.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/rules/SwapProbeBuild.cpp b/query_optimizer/rules/SwapProbeBuild.cpp new file mode 100644 index 0000000..0d18693 --- /dev/null +++ b/query_optimizer/rules/SwapProbeBuild.cpp @@ -0,0 +1,53 @@ +#include "query_optimizer/rules/SwapProbeBuild.hpp" + +#include <cstddef> +#include <vector> + +#include "query_optimizer/physical/HashJoin.hpp" +#include "query_optimizer/physical/PatternMatcher.hpp" +#include "query_optimizer/physical/TopLevelPlan.hpp" +#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp" + +namespace quickstep { +namespace optimizer { + +P::PhysicalPtr SwapProbeBuild::applyToNode(const P::PhysicalPtr &input) { + P::HashJoinPtr hash_join; + + if (P::SomeHashJoin::MatchesWithConditionalCast(input, &hash_join)) { + P::PhysicalPtr left = hash_join->left(); + P::PhysicalPtr right = hash_join->right(); + + P::TopLevelPlanPtr top_level; + if (P::SomeTopLevelPlan::MatchesWithConditionalCast(input, &top_level)) { + cost_model_.reset(new C::StarSchemaSimpleCostModel(top_level->shared_subplans())); + } else { + std::vector<P::PhysicalPtr> plans = {input}; + cost_model_.reset(new C::StarSchemaSimpleCostModel(plans)); + } + + std::size_t left_cardinality = cost_model_->estimateCardinality(left); + 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->residual_predicate(), + hash_join->project_expressions(), + hash_join->join_type()); + LOG_APPLYING_RULE(input, output); + return output; + } + } + + LOG_IGNORING_RULE(input); + return input; +} + +} +} http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e7232c13/query_optimizer/rules/SwapProbeBuild.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/rules/SwapProbeBuild.hpp b/query_optimizer/rules/SwapProbeBuild.hpp new file mode 100644 index 0000000..ed5e940 --- /dev/null +++ b/query_optimizer/rules/SwapProbeBuild.hpp @@ -0,0 +1,38 @@ +#ifndef QUICKSTEP_QUERY_OPTIMIZER_RULES_SWAP_PROBE_BUILD_HPP_ +#define QUICKSTEP_QUERY_OPTIMIZER_RULES_SWAP_PROBE_BUILD_HPP_ + +#include <string> + +#include "query_optimizer/physical/Physical.hpp" +#include "query_optimizer/rules/Rule.hpp" +#include "query_optimizer/rules/BottomUpRule.hpp" +#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp" +#include "utility/Macros.hpp" + +namespace quickstep { +namespace optimizer { + +namespace P = ::quickstep::optimizer::physical; +namespace E = ::quickstep::optimizer::expressions; +namespace C = ::quickstep::optimizer::cost; + +class SwapProbeBuild : public BottomUpRule<P::Physical> { + public: + SwapProbeBuild() { + } + + std::string getName() const override { return "SwapProbeBuild"; } + + protected: + P::PhysicalPtr applyToNode(const P::PhysicalPtr &input) override; + + private: + DISALLOW_COPY_AND_ASSIGN(SwapProbeBuild); + + std::unique_ptr<C::StarSchemaSimpleCostModel> cost_model_; +}; + +} +} + +#endif