Repository: incubator-quickstep Updated Branches: refs/heads/lip-refactor-optimizer 166860222 -> 3cfea1d5b
Updates Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/3cfea1d5 Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/3cfea1d5 Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/3cfea1d5 Branch: refs/heads/lip-refactor-optimizer Commit: 3cfea1d5b4d92277f7f38ead630186156f3e733e Parents: 1668602 Author: Jianqiao Zhu <jianq...@cs.wisc.edu> Authored: Tue Oct 11 14:08:53 2016 -0500 Committer: Jianqiao Zhu <jianq...@cs.wisc.edu> Committed: Tue Oct 11 14:08:53 2016 -0500 ---------------------------------------------------------------------- query_optimizer/PhysicalGenerator.cpp | 2 +- query_optimizer/physical/TopLevelPlan.hpp | 41 +++++++++++++------- query_optimizer/rules/AttachLIPFilters.cpp | 10 +---- query_optimizer/rules/AttachLIPFilters.hpp | 18 +++++++++ .../StarSchemaHashJoinOrderOptimization.hpp | 6 ++- utility/CMakeLists.txt | 4 +- utility/DisjointTreeForest.hpp | 1 + utility/lip_filter/CMakeLists.txt | 2 +- utility/lip_filter/LIPFilter.hpp | 12 ------ 9 files changed, 56 insertions(+), 40 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/query_optimizer/PhysicalGenerator.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/PhysicalGenerator.cpp b/query_optimizer/PhysicalGenerator.cpp index 41d822e..8143d5c 100644 --- a/query_optimizer/PhysicalGenerator.cpp +++ b/query_optimizer/PhysicalGenerator.cpp @@ -51,7 +51,7 @@ DEFINE_bool(reorder_hash_joins, true, "for queries on star-schema tables."); DEFINE_bool(use_lip_filters, false, - "If true, use LIP (Lookahead Information Passing) filters to accelerate " + "If true, use LIP (lookahead information passing) filters to accelerate " "hash joins."); DEFINE_bool(visualize_plan, false, http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/query_optimizer/physical/TopLevelPlan.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/physical/TopLevelPlan.hpp b/query_optimizer/physical/TopLevelPlan.hpp index c6ea940..7dfc2b6 100644 --- a/query_optimizer/physical/TopLevelPlan.hpp +++ b/query_optimizer/physical/TopLevelPlan.hpp @@ -90,6 +90,29 @@ class TopLevelPlan : public Physical { return shared_subplans_[index]; } + /** + * @brief Creates a copy of the TopLevelPlan with lip_filter_configuration_ + * replaced by \p new_lip_filter_configuration. + * + * @param new_lip_filter_configuration The new lip_filter_configuration to be + * substituted for the existing one. + * @return A copy of this TopLevelPlan with the new lip_filter_configuration. + */ + TopLevelPlanPtr copyWithLIPFilterConfiguration( + const LIPFilterConfigurationPtr &new_lip_filter_configuration) const { + return TopLevelPlan::Create(plan_, + shared_subplans_, + uncorrelated_subquery_map_, + new_lip_filter_configuration); + } + + /** + * @return The LIPFilter configuration information for the overall query plan. + */ + const LIPFilterConfigurationPtr& lip_filter_configuration() const { + return lip_filter_configuration_; + } + PhysicalPtr copyWithNewChildren( const std::vector<PhysicalPtr> &new_children) const override { DCHECK_EQ(getNumChildren(), new_children.size()); @@ -121,25 +144,15 @@ class TopLevelPlan : public Physical { return false; } - TopLevelPlanPtr copyWithLIPFilterConfiguration( - const LIPFilterConfigurationPtr &new_lip_filter_configuration) const { - return TopLevelPlan::Create(plan_, - shared_subplans_, - uncorrelated_subquery_map_, - new_lip_filter_configuration); - } - - const LIPFilterConfigurationPtr& lip_filter_configuration() const { - return lip_filter_configuration_; - } - /** * @brief Creates a TopLevelPlan. * * @param plan The query plan. * @param shared_subplans The subplans referenced in the main input plan. - * @param Map from the expression ID of an attribute reference to the - * uncorrelated subquery that produces the attribute. + * @param uncorrelated_subquery_map Map from the expression ID of an attribute + * reference to the uncorrelated subquery that produces the attribute. + * @param lip_filter_configuration The LIPFilter configuration information + * for the overall query plan. * @return An immutable TopLevelPlan. */ static TopLevelPlanPtr Create( http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/query_optimizer/rules/AttachLIPFilters.cpp ---------------------------------------------------------------------- diff --git a/query_optimizer/rules/AttachLIPFilters.cpp b/query_optimizer/rules/AttachLIPFilters.cpp index d67eacd..32fc3b7 100644 --- a/query_optimizer/rules/AttachLIPFilters.cpp +++ b/query_optimizer/rules/AttachLIPFilters.cpp @@ -51,6 +51,7 @@ namespace P = ::quickstep::optimizer::physical; P::PhysicalPtr AttachLIPFilters::apply(const P::PhysicalPtr &input) { DCHECK(input->getPhysicalType() == P::PhysicalType::kTopLevelPlan); + const P::TopLevelPlanPtr top_level_plan = std::static_pointer_cast<const P::TopLevelPlan>(input); cost_model_.reset( @@ -61,15 +62,6 @@ P::PhysicalPtr AttachLIPFilters::apply(const P::PhysicalPtr &input) { std::set<E::ExprId> already_filtered_attributes; attachLIPFilters(NodeList(input), &already_filtered_attributes); -// for (const auto &pair : attaches_) { -// for (const auto &build_info : pair.second->getBuildInfo()) { -// std::cout << "Build: " << build_info.build_attribute->attribute_alias() << "\n"; -// } -// for (const auto &probe_info : pair.second->getProbeInfo()) { -// std::cout << "Probe: " << probe_info.probe_attribute->attribute_alias() << "\n"; -// } -// } - P::PhysicalPtr output; if (!lip_filter_configuration_->getBuildInfoMap().empty() || !lip_filter_configuration_->getProbeInfoMap().empty()) { http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/query_optimizer/rules/AttachLIPFilters.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/rules/AttachLIPFilters.hpp b/query_optimizer/rules/AttachLIPFilters.hpp index d0a6fa5..74cf885 100644 --- a/query_optimizer/rules/AttachLIPFilters.hpp +++ b/query_optimizer/rules/AttachLIPFilters.hpp @@ -46,8 +46,14 @@ namespace optimizer { * @{ */ +/** + * @brief Rule that applies to a physical plan to attach LIPFilters. + */ class AttachLIPFilters : public Rule<physical::Physical> { public: + /** + * @brief Constructor. + */ AttachLIPFilters() {} ~AttachLIPFilters() override {} @@ -59,6 +65,9 @@ class AttachLIPFilters : public Rule<physical::Physical> { physical::PhysicalPtr apply(const physical::PhysicalPtr &input) override; private: + /** + * @brief Internal data structure for passing around LIPFilter information. + */ struct LIPFilterInfo { LIPFilterInfo(const expressions::AttributeReferencePtr &attribute_in, const physical::PhysicalPtr &source_in, @@ -77,6 +86,7 @@ class AttachLIPFilters : public Rule<physical::Physical> { : source_attribute_in) { } + static bool isBetterThan(const LIPFilterInfo &a, const LIPFilterInfo &b) { if (a.estimated_selectivity == b.estimated_selectivity) { return a.depth > b.depth; @@ -84,6 +94,7 @@ class AttachLIPFilters : public Rule<physical::Physical> { return a.estimated_selectivity < b.estimated_selectivity; } } + expressions::AttributeReferencePtr attribute; physical::PhysicalPtr source; int depth; @@ -94,12 +105,16 @@ class AttachLIPFilters : public Rule<physical::Physical> { typedef std::shared_ptr<const LIPFilterInfo> LIPFilterInfoPtr; + /** + * @brief Functional list data structure for internal use. + */ struct NodeList { NodeList(const physical::PhysicalPtr &node_in) : node(node_in), next(nullptr), depth(0) { } + NodeList(const physical::PhysicalPtr &node_in, const NodeList *next_in, const int depth_in) @@ -107,12 +122,15 @@ class AttachLIPFilters : public Rule<physical::Physical> { next(next_in), depth(depth_in) { } + inline const NodeList *cdr() const { return next; } + inline const NodeList cons(const physical::PhysicalPtr &new_node) const { return NodeList(new_node, this, depth+1); } + const physical::PhysicalPtr node; const NodeList *next; const int depth; http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp ---------------------------------------------------------------------- diff --git a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp index 8dea1ba..998a5d5 100644 --- a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp +++ b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp @@ -45,7 +45,11 @@ namespace optimizer { */ /** - * @brief TODO + * @brief Rule that applies to a physical plan to optimize hash join orders. + * + * This optimization applies a greedy algorithm to favor smaller cardinality + * and selective tables to be joined first, which is suitable for queries on + * star-schema or snowflake-schema tables. */ class StarSchemaHashJoinOrderOptimization : public Rule<physical::Physical> { public: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/utility/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/utility/CMakeLists.txt b/utility/CMakeLists.txt index 1863089..f3f3fa3 100644 --- a/utility/CMakeLists.txt +++ b/utility/CMakeLists.txt @@ -234,7 +234,7 @@ target_link_libraries(quickstep_utility_DAG glog quickstep_utility_Macros) target_link_libraries(quickstep_utility_DisjointTreeForest - quickstep_utility_Macros) + glog) target_link_libraries(quickstep_utility_ExecutionDAGVisualizer quickstep_catalog_CatalogRelationSchema quickstep_queryexecution_QueryExecutionTypedefs @@ -391,7 +391,7 @@ target_link_libraries(DisjointTreeForest_unittest gtest gtest_main quickstep_utility_DisjointTreeForest) -add_test(TemplateUtil_unittest TemplateUtil_unittest) +add_test(DisjointTreeForest_unittest DisjointTreeForest_unittest) add_executable(EqualsAnyConstant_unittest "${CMAKE_CURRENT_SOURCE_DIR}/tests/EqualsAnyConstant_unittest.cpp") target_link_libraries(EqualsAnyConstant_unittest http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/utility/DisjointTreeForest.hpp ---------------------------------------------------------------------- diff --git a/utility/DisjointTreeForest.hpp b/utility/DisjointTreeForest.hpp index a274bfa..ce9e23c 100644 --- a/utility/DisjointTreeForest.hpp +++ b/utility/DisjointTreeForest.hpp @@ -22,6 +22,7 @@ #include <limits> #include <utility> #include <unordered_map> +#include <vector> #include "glog/logging.h" http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/utility/lip_filter/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/utility/lip_filter/CMakeLists.txt b/utility/lip_filter/CMakeLists.txt index 3b3131b..2232abe 100644 --- a/utility/lip_filter/CMakeLists.txt +++ b/utility/lip_filter/CMakeLists.txt @@ -16,4 +16,4 @@ # under the License. # Declare micro-libs: -add_library(quickstep_utility_lipfilter_LIPFilter ../../empty_src.cpp LIPFilter.hpp) +add_library(quickstep_utility_lipfilter_LIPFilter ../../empty_src.cpp LIPFilter.hpp) \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3cfea1d5/utility/lip_filter/LIPFilter.hpp ---------------------------------------------------------------------- diff --git a/utility/lip_filter/LIPFilter.hpp b/utility/lip_filter/LIPFilter.hpp index 76c5640..33165ed 100644 --- a/utility/lip_filter/LIPFilter.hpp +++ b/utility/lip_filter/LIPFilter.hpp @@ -20,20 +20,8 @@ #ifndef QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_HPP_ #define QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_HPP_ -#include <cstddef> -#include <vector> - -#include "catalog/CatalogTypedefs.hpp" -#include "storage/StorageBlockInfo.hpp" -#include "utility/Macros.hpp" - -#include "glog/logging.h" - namespace quickstep { -class Type; -class ValueAccessor; - /** \addtogroup Utility * @{ */
