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 2017/01/30 18:26:43 UTC
[1/2] incubator-quickstep git commit: Add unit test for
CatalogRelationStatistics [Forced Update!]
Repository: incubator-quickstep
Updated Branches:
refs/heads/push-down-disjunctive-predicate f3e06b528 -> 6a184c8ad (forced update)
Add unit test for CatalogRelationStatistics
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/0f4938ca
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/0f4938ca
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/0f4938ca
Branch: refs/heads/push-down-disjunctive-predicate
Commit: 0f4938caa29096f18bb699c8f746a733f2262698
Parents: 0780b84
Author: Jianqiao Zhu <ji...@cs.wisc.edu>
Authored: Mon Jan 23 20:54:51 2017 -0600
Committer: Zuyu Zhang <zu...@apache.org>
Committed: Sun Jan 29 23:13:45 2017 -0800
----------------------------------------------------------------------
catalog/CMakeLists.txt | 27 +++
.../CatalogRelationStatistics_unittest.cpp | 219 +++++++++++++++++++
2 files changed, 246 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0f4938ca/catalog/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/catalog/CMakeLists.txt b/catalog/CMakeLists.txt
index 7de9a67..3c64e97 100644
--- a/catalog/CMakeLists.txt
+++ b/catalog/CMakeLists.txt
@@ -225,6 +225,31 @@ target_link_libraries(Catalog_unittest
quickstep_utility_PtrVector)
add_test(Catalog_unittest Catalog_unittest)
+add_executable(CatalogRelationStatistics_unittest
+ "${CMAKE_CURRENT_SOURCE_DIR}/tests/CatalogRelationStatistics_unittest.cpp")
+target_link_libraries(CatalogRelationStatistics_unittest
+ gtest
+ gtest_main
+ quickstep_catalog_Catalog
+ quickstep_catalog_CatalogDatabase
+ quickstep_catalog_CatalogRelation
+ quickstep_catalog_CatalogRelationStatistics
+ quickstep_cli_CommandExecutor
+ quickstep_cli_DropRelation
+ quickstep_parser_ParseStatement
+ quickstep_parser_SqlParserWrapper
+ quickstep_queryexecution_ForemanSingleNode
+ quickstep_queryexecution_QueryExecutionTypedefs
+ quickstep_queryexecution_QueryExecutionUtil
+ quickstep_queryexecution_Worker
+ quickstep_queryexecution_WorkerDirectory
+ quickstep_queryoptimizer_QueryHandle
+ quickstep_queryoptimizer_QueryProcessor
+ quickstep_storage_StorageConstants
+ quickstep_storage_StorageManager
+ tmb)
+add_test(CatalogRelationStatistics_unittest CatalogRelationStatistics_unittest)
+
if(QUICKSTEP_HAVE_LIBNUMA)
add_executable(NUMAPlacementScheme_unittest
"${CMAKE_CURRENT_SOURCE_DIR}/tests/NUMAPlacementScheme_unittest.cpp")
@@ -253,3 +278,5 @@ target_link_libraries(PartitionScheme_unittest
quickstep_types_operations_comparisons_Comparison
quickstep_types_operations_comparisons_EqualComparison)
add_test(PartitionScheme_unittest PartitionScheme_unittest)
+
+file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/catalog_relation_statistics_test_data)
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/0f4938ca/catalog/tests/CatalogRelationStatistics_unittest.cpp
----------------------------------------------------------------------
diff --git a/catalog/tests/CatalogRelationStatistics_unittest.cpp b/catalog/tests/CatalogRelationStatistics_unittest.cpp
new file mode 100644
index 0000000..294a6c7
--- /dev/null
+++ b/catalog/tests/CatalogRelationStatistics_unittest.cpp
@@ -0,0 +1,219 @@
+/**
+ * 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 <cstdio>
+#include <fstream>
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "catalog/Catalog.hpp"
+#include "catalog/CatalogDatabase.hpp"
+#include "catalog/CatalogRelation.hpp"
+#include "catalog/CatalogRelationStatistics.hpp"
+#include "cli/CommandExecutor.hpp"
+#include "cli/DropRelation.hpp"
+#include "parser/ParseStatement.hpp"
+#include "parser/SqlParserWrapper.hpp"
+#include "query_execution/ForemanSingleNode.hpp"
+#include "query_execution/QueryExecutionTypedefs.hpp"
+#include "query_execution/QueryExecutionUtil.hpp"
+#include "query_execution/Worker.hpp"
+#include "query_execution/WorkerDirectory.hpp"
+#include "query_optimizer/QueryHandle.hpp"
+#include "query_optimizer/QueryProcessor.hpp"
+#include "storage/StorageConstants.hpp"
+#include "storage/StorageManager.hpp"
+
+#include "glog/logging.h"
+#include "gtest/gtest.h"
+
+#include "tmb/id_typedefs.h"
+
+namespace quickstep {
+
+namespace {
+
+constexpr char kStoragePath[] = "./catalog_relation_statistics_test_data/";
+
+constexpr attribute_id kFirstAttributeId = 0;
+constexpr attribute_id kSecondAttributeId = 1;
+
+} // namespace
+
+class CatalogRelationStatisticsTest : public ::testing::Test {
+ protected:
+ virtual void SetUp() {
+ // Set up the environment for running end-to-end queries.
+ quickstep::ClientIDMap::Instance();
+
+ bus_.Initialize();
+
+ main_thread_client_id_ = bus_.Connect();
+ bus_.RegisterClientAsSender(main_thread_client_id_, kAdmitRequestMessage);
+ bus_.RegisterClientAsSender(main_thread_client_id_, kPoisonMessage);
+ bus_.RegisterClientAsReceiver(main_thread_client_id_, kWorkloadCompletionMessage);
+
+ std::string catalog_path(kStoragePath);
+ catalog_path.append(kCatalogFilename);
+
+ std::ofstream catalog_file(catalog_path.c_str());
+ Catalog catalog;
+ catalog.addDatabase(new CatalogDatabase(nullptr, "default"));
+ catalog.getProto().SerializeToOstream(&catalog_file);
+ catalog_file.close();
+
+ storage_manager_.reset(new StorageManager(kStoragePath));
+ query_processor_.reset(new QueryProcessor(std::move(catalog_path)));
+
+ worker_.reset(new Worker(0, &bus_));
+ worker_directory_.reset(
+ new WorkerDirectory(1, {worker_->getBusClientID()}, {-1}));
+
+ foreman_.reset(
+ new ForemanSingleNode(main_thread_client_id_,
+ worker_directory_.get(),
+ &bus_,
+ query_processor_->getDefaultDatabase(),
+ storage_manager_.get()));
+
+ worker_->start();
+ foreman_->start();
+ }
+
+ virtual void TearDown() {
+ for (const auto &relation : *query_processor_->getDefaultDatabase()) {
+ DropRelation::Drop(relation,
+ query_processor_->getDefaultDatabase(),
+ storage_manager_.get());
+ }
+
+ QueryExecutionUtil::BroadcastPoisonMessage(main_thread_client_id_, &bus_);
+ worker_->join();
+ foreman_->join();
+ }
+
+ void executeQuery(const std::string &query_string) {
+ SqlParserWrapper parser_wrapper;
+ parser_wrapper.feedNextBuffer(new std::string(query_string));
+
+ ParseResult result = parser_wrapper.getNextStatement();
+ DCHECK(result.condition == ParseResult::kSuccess);
+
+ const ParseStatement &statement = *result.parsed_statement;
+ std::unique_ptr<QueryHandle> query_handle =
+ std::make_unique<QueryHandle>(query_processor_->query_id(),
+ main_thread_client_id_,
+ statement.getPriority());
+ query_processor_->generateQueryHandle(statement, query_handle.get());
+
+ QueryExecutionUtil::ConstructAndSendAdmitRequestMessage(
+ main_thread_client_id_,
+ foreman_->getBusClientID(),
+ query_handle.release(),
+ &bus_);
+
+ QueryExecutionUtil::ReceiveQueryCompletionMessage(main_thread_client_id_, &bus_);
+ }
+
+ void executeAnalyze(const std::string &rel_name) {
+ SqlParserWrapper parser_wrapper;
+ parser_wrapper.feedNextBuffer(new std::string("\\analyze " + rel_name));
+
+ ParseResult result = parser_wrapper.getNextStatement();
+ DCHECK(result.condition == ParseResult::kSuccess);
+
+ const ParseStatement &statement = *result.parsed_statement;
+ DCHECK(statement.getStatementType() == ParseStatement::kCommand);
+ quickstep::cli::executeCommand(statement,
+ *(query_processor_->getDefaultDatabase()),
+ main_thread_client_id_,
+ foreman_->getBusClientID(),
+ &bus_,
+ storage_manager_.get(),
+ query_processor_.get(),
+ stdout);
+ }
+
+ const CatalogRelation *getRelationByName(const std::string &rel_name) const {
+ const CatalogRelation *relation =
+ query_processor_->getDefaultDatabase()->getRelationByName(rel_name);
+ DCHECK(relation != nullptr);
+ return relation;
+ }
+
+ private:
+ MessageBusImpl bus_;
+ tmb::client_id main_thread_client_id_;
+
+ std::unique_ptr<StorageManager> storage_manager_;
+ std::unique_ptr<QueryProcessor> query_processor_;
+
+ std::unique_ptr<Worker> worker_;
+ std::unique_ptr<WorkerDirectory> worker_directory_;
+ std::unique_ptr<ForemanSingleNode> foreman_;
+};
+
+TEST_F(CatalogRelationStatisticsTest, AnalyzeTest) {
+ executeQuery("CREATE TABLE analyzetest(x INT, y DOUBLE);");
+ executeQuery("INSERT INTO analyzetest VALUES(0, -0.5);");
+ executeQuery("INSERT INTO analyzetest VALUES(1, 0);");
+ executeQuery("INSERT INTO analyzetest VALUES(0, 0.5);");
+ executeAnalyze("analyzetest");
+
+ const CatalogRelation *relation = getRelationByName("analyzetest");
+ const CatalogRelationStatistics &stat = relation->getStatistics();
+
+ EXPECT_EQ(3u, stat.getNumTuples());
+
+ EXPECT_EQ(2u, stat.getNumDistinctValues(kFirstAttributeId));
+ EXPECT_EQ(0, stat.getMinValue(kFirstAttributeId).getLiteral<int>());
+ EXPECT_EQ(1, stat.getMaxValue(kFirstAttributeId).getLiteral<int>());
+
+ EXPECT_EQ(3u, stat.getNumDistinctValues(kSecondAttributeId));
+ EXPECT_EQ(-0.5, stat.getMinValue(kSecondAttributeId).getLiteral<double>());
+ EXPECT_EQ(0.5, stat.getMaxValue(kSecondAttributeId).getLiteral<double>());
+}
+
+TEST_F(CatalogRelationStatisticsTest, ExactnessTest) {
+ executeQuery("CREATE TABLE exactnesstest(x INT);");
+
+ const CatalogRelationStatistics &stat =
+ getRelationByName("exactnesstest")->getStatistics();
+
+ EXPECT_FALSE(stat.isExact());
+
+ const std::vector<std::string> queries = {
+ "INSERT INTO exactnesstest VALUES(1);",
+ "INSERT INTO exactnesstest SELECT i FROM generate_series(2, 10) AS gs(i);",
+ "DELETE FROM exactnesstest WHERE x = 5;",
+ "UPDATE exactnesstest SET x = 100 WHERE x = 10;"
+ };
+
+ for (const std::string &query : queries) {
+ executeQuery(query);
+ EXPECT_FALSE(stat.isExact());
+
+ executeAnalyze("exactnesstest");
+ EXPECT_TRUE(stat.isExact());
+ }
+}
+
+} // namespace quickstep
[2/2] incubator-quickstep git commit: Push down low cost disjunctive
predicates to filter the stored relations early
Posted by ji...@apache.org.
Push down low cost disjunctive predicates to filter the stored relations early
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/6a184c8a
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/6a184c8a
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/6a184c8a
Branch: refs/heads/push-down-disjunctive-predicate
Commit: 6a184c8ad981343dd50f04c76d3937bcdce34ddc
Parents: 0f4938c
Author: Jianqiao Zhu <ji...@cs.wisc.edu>
Authored: Mon Jan 30 01:02:19 2017 -0600
Committer: Jianqiao Zhu <ji...@cs.wisc.edu>
Committed: Mon Jan 30 12:26:16 2017 -0600
----------------------------------------------------------------------
query_optimizer/CMakeLists.txt | 1 +
query_optimizer/PhysicalGenerator.cpp | 2 +
query_optimizer/rules/CMakeLists.txt | 23 ++
.../PushDownLowCostDisjunctivePredicate.cpp | 218 +++++++++++++++++++
.../PushDownLowCostDisjunctivePredicate.hpp | 118 ++++++++++
5 files changed, 362 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6a184c8a/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index b6c794d..3bb60d4 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -207,6 +207,7 @@ target_link_libraries(quickstep_queryoptimizer_PhysicalGenerator
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_rules_AttachLIPFilters
quickstep_queryoptimizer_rules_PruneColumns
+ quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
quickstep_queryoptimizer_rules_SwapProbeBuild
quickstep_queryoptimizer_strategy_Aggregate
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6a184c8a/query_optimizer/PhysicalGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.cpp b/query_optimizer/PhysicalGenerator.cpp
index 7cb97dc..03ae913 100644
--- a/query_optimizer/PhysicalGenerator.cpp
+++ b/query_optimizer/PhysicalGenerator.cpp
@@ -27,6 +27,7 @@
#include "query_optimizer/logical/Logical.hpp"
#include "query_optimizer/physical/Physical.hpp"
#include "query_optimizer/rules/AttachLIPFilters.hpp"
+#include "query_optimizer/rules/PushDownLowCostDisjunctivePredicate.hpp"
#include "query_optimizer/rules/PruneColumns.hpp"
#include "query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp"
#include "query_optimizer/rules/SwapProbeBuild.hpp"
@@ -103,6 +104,7 @@ P::PhysicalPtr PhysicalGenerator::generateInitialPlan(
P::PhysicalPtr PhysicalGenerator::optimizePlan() {
std::vector<std::unique_ptr<Rule<P::Physical>>> rules;
rules.emplace_back(new PruneColumns());
+ rules.emplace_back(new PushDownLowCostDisjunctivePredicate());
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/6a184c8a/query_optimizer/rules/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CMakeLists.txt b/query_optimizer/rules/CMakeLists.txt
index 7fffadc..b62e99e 100644
--- a/query_optimizer/rules/CMakeLists.txt
+++ b/query_optimizer/rules/CMakeLists.txt
@@ -24,6 +24,9 @@ add_library(quickstep_queryoptimizer_rules_CollapseProject CollapseProject.cpp C
add_library(quickstep_queryoptimizer_rules_GenerateJoins GenerateJoins.cpp GenerateJoins.hpp)
add_library(quickstep_queryoptimizer_rules_PruneColumns PruneColumns.cpp PruneColumns.hpp)
add_library(quickstep_queryoptimizer_rules_PushDownFilter PushDownFilter.cpp PushDownFilter.hpp)
+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_Rule ../../empty_src.cpp Rule.hpp)
add_library(quickstep_queryoptimizer_rules_RuleHelper RuleHelper.cpp RuleHelper.hpp)
@@ -110,6 +113,25 @@ target_link_libraries(quickstep_queryoptimizer_rules_PushDownFilter
quickstep_queryoptimizer_rules_RuleHelper
quickstep_queryoptimizer_rules_TopDownRule
quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
+ quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
+ quickstep_queryoptimizer_expressions_AttributeReference
+ quickstep_queryoptimizer_expressions_ExpressionUtil
+ 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_PatternMatcher
+ quickstep_queryoptimizer_physical_Physical
+ quickstep_queryoptimizer_physical_PhysicalType
+ quickstep_queryoptimizer_physical_Selection
+ quickstep_queryoptimizer_physical_TableReference
+ quickstep_queryoptimizer_physical_TopLevelPlan
+ quickstep_queryoptimizer_rules_Rule
+ quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_ExpressionUtil
@@ -212,6 +234,7 @@ target_link_libraries(quickstep_queryoptimizer_rules
quickstep_queryoptimizer_rules_GenerateJoins
quickstep_queryoptimizer_rules_PruneColumns
quickstep_queryoptimizer_rules_PushDownFilter
+ quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
quickstep_queryoptimizer_rules_Rule
quickstep_queryoptimizer_rules_RuleHelper
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6a184c8a/query_optimizer/rules/PushDownLowCostDisjunctivePredicate.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/PushDownLowCostDisjunctivePredicate.cpp b/query_optimizer/rules/PushDownLowCostDisjunctivePredicate.cpp
new file mode 100644
index 0000000..7db8f7f
--- /dev/null
+++ b/query_optimizer/rules/PushDownLowCostDisjunctivePredicate.cpp
@@ -0,0 +1,218 @@
+/**
+ * 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/PushDownLowCostDisjunctivePredicate.hpp"
+
+#include <cstddef>
+#include <vector>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/expressions/LogicalAnd.hpp"
+#include "query_optimizer/expressions/LogicalOr.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
+#include "query_optimizer/expressions/Predicate.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
+#include "query_optimizer/physical/HashJoin.hpp"
+#include "query_optimizer/physical/NestedLoopsJoin.hpp"
+#include "query_optimizer/physical/PatternMatcher.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/PhysicalType.hpp"
+#include "query_optimizer/physical/Selection.hpp"
+#include "query_optimizer/physical/TableReference.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 PushDownLowCostDisjunctivePredicate::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(
+ new cost::StarSchemaSimpleCostModel(
+ top_level_plan->shared_subplans()));
+
+ collectApplicablePredicates(input);
+
+ if (!applicable_predicates_.empty()) {
+ // Apply the selected predicates to stored relations.
+ return attachPredicates(input);
+ } else {
+ return input;
+ }
+}
+
+void PushDownLowCostDisjunctivePredicate::collectApplicablePredicates(
+ const physical::PhysicalPtr &input) {
+ P::TableReferencePtr table_reference;
+ if (P::SomeTableReference::MatchesWithConditionalCast(input, &table_reference)) {
+ // Consider only stored relations with small cardinality as targets.
+ if (cost_model_->estimateCardinality(input) <= 100u) {
+ applicable_nodes_.emplace_back(input, &table_reference->attribute_list());
+ }
+ return;
+ }
+
+ for (const auto &child : input->children()) {
+ collectApplicablePredicates(child);
+ }
+
+ E::PredicatePtr filter_predicate = nullptr;
+ switch (input->getPhysicalType()) {
+ case P::PhysicalType::kAggregate: {
+ filter_predicate =
+ std::static_pointer_cast<const P::Aggregate>(input)->filter_predicate();
+ break;
+ }
+ case P::PhysicalType::kHashJoin: {
+ const P::HashJoinPtr hash_join =
+ std::static_pointer_cast<const P::HashJoin>(input);
+ if (hash_join->join_type() == P::HashJoin::JoinType::kInnerJoin) {
+ filter_predicate = hash_join->residual_predicate();
+ }
+ break;
+ }
+ case P::PhysicalType::kNestedLoopsJoin: {
+ filter_predicate =
+ std::static_pointer_cast<const P::NestedLoopsJoin>(input)->join_predicate();
+ break;
+ }
+ case P::PhysicalType::kSelection: {
+ filter_predicate =
+ std::static_pointer_cast<const P::Selection>(input)->filter_predicate();
+ break;
+ }
+ default:
+ break;
+ }
+
+ E::LogicalOrPtr disjunctive_predicate;
+ if (filter_predicate == nullptr ||
+ !E::SomeLogicalOr::MatchesWithConditionalCast(filter_predicate, &disjunctive_predicate)) {
+ return;
+ }
+
+ // Consider only disjunctive normal form, i.e. disjunction of conjunctions.
+ // Divide the disjunctive components into groups.
+ std::vector<std::vector<E::PredicatePtr>> candidate_predicates;
+ std::vector<std::vector<std::vector<E::AttributeReferencePtr>>> candidate_attributes;
+ for (const auto &conjunctive_predicate : disjunctive_predicate->operands()) {
+ candidate_predicates.emplace_back();
+ candidate_attributes.emplace_back();
+ E::LogicalAndPtr logical_and;
+ if (E::SomeLogicalAnd::MatchesWithConditionalCast(conjunctive_predicate, &logical_and)) {
+ for (const auto &predicate : logical_and->operands()) {
+ candidate_predicates.back().emplace_back(predicate);
+ candidate_attributes.back().emplace_back(
+ predicate->getReferencedAttributes());
+ }
+ } else {
+ candidate_predicates.back().emplace_back(conjunctive_predicate);
+ candidate_attributes.back().emplace_back(
+ conjunctive_predicate->getReferencedAttributes());
+ }
+ }
+
+ // Check whether the conditions are met for pushing down part of the predicates
+ // to each small-cardinality stored relation.
+ for (const auto &node_pair : applicable_nodes_) {
+ const std::vector<E::AttributeReferencePtr> &target_attributes = *node_pair.second;
+ std::vector<E::PredicatePtr> selected_disj_preds;
+ for (std::size_t i = 0; i < candidate_predicates.size(); ++i) {
+ const auto &cand_preds = candidate_predicates[i];
+ const auto &cand_attrs = candidate_attributes[i];
+
+ std::vector<E::PredicatePtr> selected_conj_preds;
+ for (std::size_t j = 0; j < cand_preds.size(); ++j) {
+ if (E::SubsetOfExpressions(cand_attrs[j], target_attributes)) {
+ selected_conj_preds.emplace_back(cand_preds[j]);
+ }
+ }
+ if (selected_conj_preds.empty()) {
+ // Not every disjunctive component contains a predicate that can be applied
+ // to the table reference node -- condition failed, exit.
+ selected_disj_preds.clear();
+ break;
+ } else {
+ selected_disj_preds.emplace_back(
+ CreateConjunctive(selected_conj_preds));
+ }
+ }
+ if (!selected_disj_preds.empty()) {
+ applicable_predicates_[node_pair.first].add(
+ CreateDisjunctive(selected_disj_preds));
+ }
+ }
+}
+
+P::PhysicalPtr PushDownLowCostDisjunctivePredicate::attachPredicates(
+ const P::PhysicalPtr &input) const {
+ std::vector<P::PhysicalPtr> new_children;
+ for (const P::PhysicalPtr &child : input->children()) {
+ const P::PhysicalPtr new_child = attachPredicates(child);
+ new_children.push_back(new_child);
+ }
+
+ const P::PhysicalPtr output =
+ new_children == input->children() ? input
+ : input->copyWithNewChildren(new_children);
+
+ const auto &node_it = applicable_predicates_.find(input);
+ if (node_it != applicable_predicates_.end()) {
+ const E::PredicatePtr filter_predicate =
+ CreateConjunctive(node_it->second.predicates);
+ return P::Selection::Create(output,
+ E::ToNamedExpressions(output->getOutputAttributes()),
+ filter_predicate);
+ }
+
+ return output;
+}
+
+E::PredicatePtr PushDownLowCostDisjunctivePredicate::CreateConjunctive(
+ const std::vector<E::PredicatePtr> predicates) {
+ DCHECK_GE(predicates.size(), 1u);
+ if (predicates.size() == 1) {
+ return predicates.front();
+ } else {
+ return E::LogicalAnd::Create(predicates);
+ }
+}
+
+E::PredicatePtr PushDownLowCostDisjunctivePredicate::CreateDisjunctive(
+ const std::vector<E::PredicatePtr> predicates) {
+ DCHECK_GE(predicates.size(), 1u);
+ if (predicates.size() == 1) {
+ return predicates.front();
+ } else {
+ return E::LogicalOr::Create(predicates);
+ }
+}
+
+
+} // namespace optimizer
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6a184c8a/query_optimizer/rules/PushDownLowCostDisjunctivePredicate.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/PushDownLowCostDisjunctivePredicate.hpp b/query_optimizer/rules/PushDownLowCostDisjunctivePredicate.hpp
new file mode 100644
index 0000000..bf84293
--- /dev/null
+++ b/query_optimizer/rules/PushDownLowCostDisjunctivePredicate.hpp
@@ -0,0 +1,118 @@
+/**
+ * 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_PUSH_DOWN_LOW_COST_DISJUNCTIVE_PREDICATE_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_RULES_PUSH_DOWN_LOW_COST_DISJUNCTIVE_PREDICATE_HPP_
+
+#include <cstddef>
+#include <map>
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/AttributeReference.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 Rule that applies to a physical plan to push down low-cost disjunctive
+ * predicate when proper conditions are met.
+ *
+ * Here we elaborate the conditions.
+ *
+ * Let
+ * P = p_{1,1} AND ... AND p_{1, m_1} OR ... OR p_{n,1} AND ... AND p_{n, m_n}
+ * be a predicate in disjunctive normal form.
+ *
+ * Now consider each small-cardinality relation R, if for each i in 1..n, there
+ * exists at least one predicate p_{i, k_i} that is applicable to R. Then we can
+ * construct a new predicate
+ * P' = p_{1, k_1} OR ... OR p_{n, k_n}
+ * and push down P' to be applied to R.
+ *
+ * Also, if any conjunctive component in P contains more than one predicate that
+ * is applicable to R, then we can combine all these applicable predicates as a
+ * conjunctive component in P'.
+ *
+ * Finally, note that if there exists a conjunctive component that contains no
+ * predicate applicable to R. Then the condition fails and we cannot do a push
+ * down for R.
+ */
+class PushDownLowCostDisjunctivePredicate : public Rule<physical::Physical> {
+ public:
+ /**
+ * @brief Constructor.
+ */
+ PushDownLowCostDisjunctivePredicate() {}
+
+ ~PushDownLowCostDisjunctivePredicate() override {}
+
+ std::string getName() const override {
+ return "PushDownLowCostDisjunctivePredicate";
+ }
+
+ physical::PhysicalPtr apply(const physical::PhysicalPtr &input) override;
+
+ private:
+ struct PredicateInfo {
+ PredicateInfo() {}
+ inline void add(expressions::PredicatePtr predicate) {
+ predicates.emplace_back(predicate);
+ }
+ std::vector<expressions::PredicatePtr> predicates;
+ };
+
+ void collectApplicablePredicates(const physical::PhysicalPtr &input);
+ physical::PhysicalPtr attachPredicates(const physical::PhysicalPtr &input) const;
+
+ static expressions::PredicatePtr CreateConjunctive(
+ const std::vector<expressions::PredicatePtr> predicates);
+
+ static expressions::PredicatePtr CreateDisjunctive(
+ const std::vector<expressions::PredicatePtr> predicates);
+
+ std::unique_ptr<cost::StarSchemaSimpleCostModel> cost_model_;
+
+ std::vector<std::pair<physical::PhysicalPtr,
+ const std::vector<expressions::AttributeReferencePtr> *>> applicable_nodes_;
+ std::map<physical::PhysicalPtr, PredicateInfo> applicable_predicates_;
+
+ // Currently consider only stored relations with small cardinality as targets.
+ static constexpr std::size_t kCardinalityThreshold = 100u;
+
+ DISALLOW_COPY_AND_ASSIGN(PushDownLowCostDisjunctivePredicate);
+};
+
+/** @} */
+
+} // namespace optimizer
+} // namespace quickstep
+
+#endif // QUICKSTEP_QUERY_OPTIMIZER_RULES_PUSH_DOWN_LOW_COST_DISJUNCTIVE_PREDICATE_HPP_