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/07/11 03:10:40 UTC
[4/8] incubator-quickstep git commit: updates to planner
updates to planner
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/604edced
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/604edced
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/604edced
Branch: refs/heads/adaptive-bloom-filters
Commit: 604edced0f29a2d0dd6ecb4f831522d2dd4340ff
Parents: 0ed5e8b
Author: Jianqiao Zhu <ji...@cs.wisc.edu>
Authored: Sun Jul 10 13:56:23 2016 -0500
Committer: Jianqiao Zhu <ji...@cs.wisc.edu>
Committed: Sun Jul 10 21:50:18 2016 -0500
----------------------------------------------------------------------
.../cost_model/StarSchemaSimpleCostModel.cpp | 10 +-
query_optimizer/rules/AttachBloomFilters.cpp | 120 +++++++++++++++----
query_optimizer/rules/AttachBloomFilters.hpp | 26 ++--
.../StarSchemaHashJoinOrderOptimization.cpp | 8 +-
4 files changed, 126 insertions(+), 38 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/604edced/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
index fac6f60..e00766d 100644
--- a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
@@ -173,8 +173,14 @@ double StarSchemaSimpleCostModel::estimateSelectivity(
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()));
+ double left_selectivity = estimateSelectivity(hash_join->left());
+ double right_selectivity = estimateSelectivity(hash_join->right());
+ double min_sel = std::min(left_selectivity, right_selectivity);
+ double max_sel = std::max(left_selectivity, right_selectivity);
+ if (max_sel < 1) {
+ min_sel *= std::max(max_sel, 0.9);
+ }
+ return min_sel;
}
case P::PhysicalType::kNestedLoopsJoin: {
const P::NestedLoopsJoinPtr &nested_loop_join =
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/604edced/query_optimizer/rules/AttachBloomFilters.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/AttachBloomFilters.cpp b/query_optimizer/rules/AttachBloomFilters.cpp
index 34822e5..b3cf0da 100644
--- a/query_optimizer/rules/AttachBloomFilters.cpp
+++ b/query_optimizer/rules/AttachBloomFilters.cpp
@@ -21,6 +21,7 @@
#include <set>
#include <unordered_set>
#include <unordered_map>
+#include <utility>
#include <vector>
#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
@@ -47,16 +48,23 @@ P::PhysicalPtr AttachBloomFilters::apply(const P::PhysicalPtr &input) {
new cost::StarSchemaSimpleCostModel(
std::static_pointer_cast<const P::TopLevelPlan>(input)->shared_subplans()));
- visitProducer(input);
+ visitProducer(input, 0);
visitConsumer(input);
- for (const auto &info_vec_pair : producers_) {
+ for (const auto &info_vec_pair : consumers_) {
std::cerr << "--------\n"
<< "Node " << info_vec_pair.first->getName()
- << info_vec_pair.first << "\n";
+ << " " << info_vec_pair.first << "\n";
+
for (const auto &info : info_vec_pair.second) {
- std::cerr << info.attribute->attribute_alias() << "@"
- << info.source
+ std::cerr << info.attribute->attribute_alias();
+ if (info.attribute->id() != info.source_attribute->id()) {
+ std::cerr << "{FROM " << info.source_attribute->attribute_alias() << "}";
+ }
+ if (info.from_sibling) {
+ std::cerr << " sibling";
+ }
+ std::cerr << " @" << info.source << "[" << info.depth << "]"
<< ": " << info.selectivity << "\n";
}
std::cerr << "********\n";
@@ -65,8 +73,19 @@ P::PhysicalPtr AttachBloomFilters::apply(const P::PhysicalPtr &input) {
return input;
}
-void AttachBloomFilters::visitProducer(const P::PhysicalPtr &node) {
- std::vector<const BloomFilterInfo> bloom_filters;
+void AttachBloomFilters::visitProducer(const P::PhysicalPtr &node, int depth) {
+ for (const P::PhysicalPtr &child : node->children()) {
+ visitProducer(child, depth+1);
+ }
+
+ std::vector<BloomFilterInfo> bloom_filters;
+
+ const std::vector<E::AttributeReferencePtr> output_attributes(
+ node->getOutputAttributes());
+ std::unordered_set<E::ExprId> output_attribute_ids;
+ for (const auto &attr : output_attributes) {
+ output_attribute_ids.emplace(attr->id());
+ }
// First check inherited bloom filters
std::vector<const BloomFilterInfo*> candidates;
@@ -75,11 +94,8 @@ void AttachBloomFilters::visitProducer(const P::PhysicalPtr &node) {
case P::PhysicalType::kSelection:
case P::PhysicalType::kHashJoin: {
for (const P::PhysicalPtr &child : node->children()) {
- const auto bloom_filters_it = producers_.find(child);
- if (bloom_filters_it != producers_.end()) {
- for (const BloomFilterInfo info : bloom_filters_it->second) {
- candidates.emplace_back(&info);
- }
+ for (const BloomFilterInfo &info : producers_[child]) {
+ candidates.emplace_back(&info);
}
}
}
@@ -87,16 +103,10 @@ void AttachBloomFilters::visitProducer(const P::PhysicalPtr &node) {
break;
}
- const std::vector<E::AttributeReferencePtr> output_attributes(
- node->getOutputAttributes());
-
- std::unordered_set<E::ExprId> output_attribute_ids;
- for (const auto &attr : output_attributes) {
- output_attribute_ids.emplace(attr->id());
- }
for (const BloomFilterInfo *info : candidates) {
if (output_attribute_ids.find(info->attribute->id()) != output_attribute_ids.end()) {
- bloom_filters.emplace_back(*info);
+ bloom_filters.emplace_back(
+ info->source, info->attribute, info->depth, info->selectivity, false);
}
}
@@ -104,7 +114,7 @@ void AttachBloomFilters::visitProducer(const P::PhysicalPtr &node) {
double selectivity = cost_model_->estimateSelectivity(node);
if (selectivity < 1.0) {
for (const auto &attr : output_attributes) {
- bloom_filters.emplace_back(node, attr, selectivity, false);
+ bloom_filters.emplace_back(node, attr, depth, selectivity, false);
}
}
@@ -112,6 +122,74 @@ void AttachBloomFilters::visitProducer(const P::PhysicalPtr &node) {
}
void AttachBloomFilters::visitConsumer(const P::PhysicalPtr &node) {
+ std::vector<BloomFilterInfo> bloom_filters;
+
+ // Bloom filters from parent
+ const auto &parent_bloom_filters = consumers_[node];
+ if (!parent_bloom_filters.empty()) {
+ for (const auto &child : node->children()) {
+ std::unordered_set<E::ExprId> child_output_attribute_ids;
+ for (const auto &attr : child->getOutputAttributes()) {
+ child_output_attribute_ids.emplace(attr->id());
+ }
+
+ std::vector<BloomFilterInfo> bloom_filters;
+ for (const auto &info : parent_bloom_filters) {
+ if (child_output_attribute_ids.find(info.attribute->id())
+ != child_output_attribute_ids.end()) {
+ bloom_filters.emplace_back(info.source,
+ info.attribute,
+ info.depth,
+ info.selectivity,
+ false,
+ info.source_attribute);
+ }
+ }
+ consumers_.emplace(child, std::move(bloom_filters));
+ }
+ }
+
+ // Bloom filters from siblings via HashJoin
+ if (node->getPhysicalType() == P::PhysicalType::kHashJoin) {
+ const P::HashJoinPtr hash_join =
+ std::static_pointer_cast<const P::HashJoin>(node);
+ std::vector<P::PhysicalPtr> children =
+ { hash_join->left(), hash_join->right() };
+
+ std::unordered_map<E::ExprId, E::AttributeReferencePtr> join_attribute_pairs;
+ for (std::size_t i = 0; i < hash_join->left_join_attributes().size(); ++i) {
+ const E::AttributeReferencePtr left_join_attribute =
+ hash_join->left_join_attributes()[i];
+ const E::AttributeReferencePtr right_join_attribute =
+ hash_join->right_join_attributes()[i];
+ join_attribute_pairs.emplace(left_join_attribute->id(),
+ right_join_attribute);
+ join_attribute_pairs.emplace(right_join_attribute->id(),
+ left_join_attribute);
+ }
+
+ for (int side = 0; side < 2; ++side) {
+ const P::PhysicalPtr &producer_child = children[side];
+ const P::PhysicalPtr &consumer_child = children[1-side];
+
+ auto &consumer_bloom_filters = consumers_[consumer_child];
+ for (const auto &info : producers_[producer_child]) {
+ const auto pair_it = join_attribute_pairs.find(info.attribute->id());
+ if (pair_it != join_attribute_pairs.end()) {
+ consumer_bloom_filters.emplace_back(info.source,
+ pair_it->second,
+ info.depth,
+ info.selectivity,
+ true,
+ info.attribute);
+ }
+ }
+ }
+ }
+
+ for (const auto &child : node->children()) {
+ visitConsumer(child);
+ }
}
} // namespace optimizer
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/604edced/query_optimizer/rules/AttachBloomFilters.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/AttachBloomFilters.hpp b/query_optimizer/rules/AttachBloomFilters.hpp
index dfcc7f5..69b50e6 100644
--- a/query_optimizer/rules/AttachBloomFilters.hpp
+++ b/query_optimizer/rules/AttachBloomFilters.hpp
@@ -61,33 +61,37 @@ class AttachBloomFilters : public Rule<physical::Physical> {
struct BloomFilterInfo {
BloomFilterInfo(const physical::PhysicalPtr &source_in,
const expressions::AttributeReferencePtr &attribute_in,
+ const int depth_in,
const double selectivity_in,
- const bool from_sibling_in)
+ const bool from_sibling_in,
+ const expressions::AttributeReferencePtr &source_attribute_in = nullptr)
: source(source_in),
attribute(attribute_in),
+ depth(depth_in),
selectivity(selectivity_in),
- from_sibling(from_sibling_in) {
- }
- BloomFilterInfo(const BloomFilterInfo &info)
- : source(info.source),
- attribute(info.attribute),
- selectivity(info.selectivity),
- from_sibling(info.from_sibling) {
+ from_sibling(from_sibling_in),
+ source_attribute(
+ source_attribute_in == nullptr
+ ? attribute_in
+ : source_attribute_in) {
+
}
physical::PhysicalPtr source;
expressions::AttributeReferencePtr attribute;
+ int depth;
double selectivity;
bool from_sibling;
+ expressions::AttributeReferencePtr source_attribute;
};
- void visitProducer(const physical::PhysicalPtr &node);
+ void visitProducer(const physical::PhysicalPtr &node, int depth);
void visitConsumer(const physical::PhysicalPtr &node);
std::unique_ptr<cost::StarSchemaSimpleCostModel> cost_model_;
- std::map<physical::PhysicalPtr, std::vector<const BloomFilterInfo>> producers_;
- std::map<physical::PhysicalPtr, std::vector<const BloomFilterInfo>> consumers_;
+ std::map<physical::PhysicalPtr, std::vector<BloomFilterInfo>> producers_;
+ std::map<physical::PhysicalPtr, std::vector<BloomFilterInfo>> consumers_;
DISALLOW_COPY_AND_ASSIGN(AttachBloomFilters);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/604edced/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
index 2e0b6c6..e198149 100644
--- a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
+++ b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
@@ -242,10 +242,10 @@ physical::PhysicalPtr StarSchemaHashJoinOrderOptimization::generatePlan(
CHECK(selected_probe_table_info != nullptr);
CHECK(selected_build_table_info != nullptr);
- std::cerr << selected_probe_table_info->estimated_num_output_attributes
- << " -- "
- << selected_build_table_info->estimated_num_output_attributes
- << "\n";
+// std::cerr << selected_probe_table_info->estimated_num_output_attributes
+// << " -- "
+// << selected_build_table_info->estimated_num_output_attributes
+// << "\n";
remaining_tables.erase(selected_probe_table_info);
remaining_tables.erase(selected_build_table_info);