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/10/31 05:34:25 UTC
[2/2] incubator-quickstep git commit: Support for
BitVectorExactFilter.
Support for BitVectorExactFilter.
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/6f941122
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/6f941122
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/6f941122
Branch: refs/heads/exact-filter
Commit: 6f941122c9931b5415862ca1d0cc1ffe974092e4
Parents: 8b68fa5
Author: Jianqiao Zhu <ji...@cs.wisc.edu>
Authored: Sat Oct 29 16:22:59 2016 -0500
Committer: Jianqiao Zhu <ji...@cs.wisc.edu>
Committed: Mon Oct 31 00:34:15 2016 -0500
----------------------------------------------------------------------
cli/QuickstepCli.cpp | 6 -
query_optimizer/CMakeLists.txt | 6 +-
query_optimizer/ExecutionGenerator.cpp | 45 ++-
query_optimizer/ExecutionGenerator.hpp | 9 +-
query_optimizer/LIPFilterGenerator.cpp | 86 +++--
query_optimizer/LIPFilterGenerator.hpp | 47 ++-
query_optimizer/PhysicalGenerator.cpp | 8 +-
query_optimizer/cost_model/CMakeLists.txt | 2 +
query_optimizer/cost_model/SimpleCostModel.cpp | 9 +
query_optimizer/cost_model/SimpleCostModel.hpp | 5 +
.../cost_model/StarSchemaSimpleCostModel.cpp | 32 +-
.../cost_model/StarSchemaSimpleCostModel.hpp | 4 +
query_optimizer/physical/CMakeLists.txt | 7 +-
query_optimizer/physical/FilterInjection.cpp | 102 +++++
query_optimizer/physical/FilterInjection.hpp | 146 +++++++
query_optimizer/physical/FilterJoin.cpp | 98 -----
query_optimizer/physical/FilterJoin.hpp | 134 -------
.../physical/LIPFilterConfiguration.hpp | 65 +++-
query_optimizer/physical/PatternMatcher.hpp | 4 +-
query_optimizer/physical/PhysicalType.hpp | 2 +-
query_optimizer/physical/TopLevelPlan.hpp | 3 +-
query_optimizer/rules/AttachLIPFilters.cpp | 14 +-
query_optimizer/rules/CMakeLists.txt | 10 +-
query_optimizer/rules/InjectJoinFilters.cpp | 386 +++++++++++++++++++
query_optimizer/rules/InjectJoinFilters.hpp | 99 +++++
query_optimizer/rules/TransformFilterJoins.cpp | 92 -----
query_optimizer/rules/TransformFilterJoins.hpp | 73 ----
relational_operators/BuildLIPFilterOperator.cpp | 115 ++++++
relational_operators/BuildLIPFilterOperator.hpp | 164 ++++++++
relational_operators/CMakeLists.txt | 23 ++
utility/CMakeLists.txt | 1 +
utility/PlanVisualizer.cpp | 19 +-
utility/lip_filter/BitVectorExactFilter.hpp | 10 +-
utility/lip_filter/LIPFilter.proto | 14 +-
utility/lip_filter/LIPFilterDeployment.cpp | 70 ++--
utility/lip_filter/LIPFilterDeployment.hpp | 28 +-
utility/lip_filter/LIPFilterFactory.cpp | 26 +-
37 files changed, 1430 insertions(+), 534 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/cli/QuickstepCli.cpp
----------------------------------------------------------------------
diff --git a/cli/QuickstepCli.cpp b/cli/QuickstepCli.cpp
index b89a0f3..8269197 100644
--- a/cli/QuickstepCli.cpp
+++ b/cli/QuickstepCli.cpp
@@ -84,7 +84,6 @@ typedef quickstep::LineReaderDumb LineReaderImpl;
#include "gflags/gflags.h"
#include "glog/logging.h"
-#include "google/protobuf/text_format.h"
#include "tmb/address.h"
#include "tmb/id_typedefs.h"
@@ -301,11 +300,6 @@ int main(int argc, char* argv[]) {
LOG(FATAL) << "NON-STANDARD EXCEPTION DURING STARTUP";
}
- std::string str;
- google::protobuf::TextFormat::PrintToString(
- query_processor->getDefaultDatabase()->getProto(), &str);
- std::cerr << str << "\n";
-
// Parse the CPU affinities for workers and the preloader thread, if enabled
// to warm up the buffer pool.
const vector<int> worker_cpu_affinities =
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index 3211919..0699bbd 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -98,7 +98,7 @@ target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
quickstep_queryoptimizer_physical_CreateTable
quickstep_queryoptimizer_physical_DeleteTuples
quickstep_queryoptimizer_physical_DropTable
- quickstep_queryoptimizer_physical_FilterJoin
+ quickstep_queryoptimizer_physical_FilterInjection
quickstep_queryoptimizer_physical_HashJoin
quickstep_queryoptimizer_physical_InsertSelection
quickstep_queryoptimizer_physical_InsertTuple
@@ -118,6 +118,7 @@ target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
quickstep_queryoptimizer_physical_WindowAggregate
quickstep_relationaloperators_AggregationOperator
quickstep_relationaloperators_BuildHashOperator
+ quickstep_relationaloperators_BuildLIPFilterOperator
quickstep_relationaloperators_CreateIndexOperator
quickstep_relationaloperators_CreateTableOperator
quickstep_relationaloperators_DeleteOperator
@@ -164,6 +165,7 @@ target_link_libraries(quickstep_queryoptimizer_LIPFilterGenerator
quickstep_queryoptimizer_QueryPlan
quickstep_queryoptimizer_expressions_ExprId
quickstep_queryoptimizer_physical_Aggregate
+ quickstep_queryoptimizer_physical_FilterInjection
quickstep_queryoptimizer_physical_HashJoin
quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_Physical
@@ -209,10 +211,10 @@ target_link_libraries(quickstep_queryoptimizer_PhysicalGenerator
quickstep_queryoptimizer_logical_Logical
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_rules_AttachLIPFilters
+ quickstep_queryoptimizer_rules_InjectJoinFilters
quickstep_queryoptimizer_rules_PruneColumns
quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
quickstep_queryoptimizer_rules_SwapProbeBuild
- quickstep_queryoptimizer_rules_TransformFilterJoins
quickstep_queryoptimizer_strategy_Aggregate
quickstep_queryoptimizer_strategy_Join
quickstep_queryoptimizer_strategy_OneToOne
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/ExecutionGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.cpp b/query_optimizer/ExecutionGenerator.cpp
index f97e448..e449c49 100644
--- a/query_optimizer/ExecutionGenerator.cpp
+++ b/query_optimizer/ExecutionGenerator.cpp
@@ -74,7 +74,7 @@
#include "query_optimizer/physical/CreateTable.hpp"
#include "query_optimizer/physical/DeleteTuples.hpp"
#include "query_optimizer/physical/DropTable.hpp"
-#include "query_optimizer/physical/FilterJoin.hpp"
+#include "query_optimizer/physical/FilterInjection.hpp"
#include "query_optimizer/physical/HashJoin.hpp"
#include "query_optimizer/physical/InsertSelection.hpp"
#include "query_optimizer/physical/InsertTuple.hpp"
@@ -94,6 +94,7 @@
#include "query_optimizer/physical/WindowAggregate.hpp"
#include "relational_operators/AggregationOperator.hpp"
#include "relational_operators/BuildHashOperator.hpp"
+#include "relational_operators/BuildLIPFilterOperator.hpp"
#include "relational_operators/CreateIndexOperator.hpp"
#include "relational_operators/CreateTableOperator.hpp"
#include "relational_operators/DeleteOperator.hpp"
@@ -270,6 +271,9 @@ void ExecutionGenerator::generatePlanInternal(
case P::PhysicalType::kDropTable:
return convertDropTable(
std::static_pointer_cast<const P::DropTable>(physical_plan));
+ case P::PhysicalType::kFilterInjection:
+ return convertFilterInjection(
+ std::static_pointer_cast<const P::FilterInjection>(physical_plan));
case P::PhysicalType::kHashJoin:
return convertHashJoin(
std::static_pointer_cast<const P::HashJoin>(physical_plan));
@@ -607,6 +611,45 @@ void ExecutionGenerator::convertSharedSubplanReference(const physical::SharedSub
}
}
+void ExecutionGenerator::convertFilterInjection(const P::FilterInjectionPtr &physical_plan) {
+ P::PhysicalPtr probe_physical = physical_plan->left();
+ P::PhysicalPtr build_physical = physical_plan->right();
+
+ P::FilterInjectionPtr filter_injection;
+ if (P::SomeFilterInjection::MatchesWithConditionalCast(build_physical, &filter_injection)) {
+ build_physical = filter_injection->left();
+ DCHECK(build_physical->getPhysicalType() != P::PhysicalType::kFilterInjection);
+ }
+
+ const CatalogRelationInfo *probe_relation_info =
+ findRelationInfoOutputByPhysical(probe_physical);
+ const CatalogRelationInfo *build_relation_info =
+ findRelationInfoOutputByPhysical(build_physical);
+
+ const QueryPlan::DAGNodeIndex build_filter_operator_index =
+ execution_plan_->addRelationalOperator(
+ new BuildLIPFilterOperator(
+ query_handle_->query_id(),
+ *build_relation_info->relation,
+ build_relation_info->isStoredRelation()));
+
+ if (!build_relation_info->isStoredRelation()) {
+ execution_plan_->addDirectDependency(build_filter_operator_index,
+ build_relation_info->producer_operator_index,
+ false /* is_pipeline_breaker */);
+ }
+
+ physical_to_output_relation_map_.emplace(
+ std::piecewise_construct,
+ std::forward_as_tuple(physical_plan),
+ std::forward_as_tuple(probe_relation_info->producer_operator_index,
+ probe_relation_info->relation));
+
+ DCHECK(lip_filter_generator_ != nullptr);
+ lip_filter_generator_->addFilterInjectionInfo(physical_plan,
+ build_filter_operator_index);
+}
+
void ExecutionGenerator::convertHashJoin(const P::HashJoinPtr &physical_plan) {
// HashJoin is converted to three operators:
// BuildHash, HashJoin, DestroyHash. The second is the primary operator.
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/ExecutionGenerator.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.hpp b/query_optimizer/ExecutionGenerator.hpp
index 95608e7..a874dbb 100644
--- a/query_optimizer/ExecutionGenerator.hpp
+++ b/query_optimizer/ExecutionGenerator.hpp
@@ -46,7 +46,7 @@
#include "query_optimizer/physical/CreateTable.hpp"
#include "query_optimizer/physical/DeleteTuples.hpp"
#include "query_optimizer/physical/DropTable.hpp"
-#include "query_optimizer/physical/FilterJoin.hpp"
+#include "query_optimizer/physical/FilterInjection.hpp"
#include "query_optimizer/physical/HashJoin.hpp"
#include "query_optimizer/physical/InsertSelection.hpp"
#include "query_optimizer/physical/InsertTuple.hpp"
@@ -249,6 +249,13 @@ class ExecutionGenerator {
void convertSharedSubplanReference(const physical::SharedSubplanReferencePtr &physical_plan);
/**
+ * @brief Converts a FilterInjection to a BuildLIPFilter operator.
+ *
+ * @param physical_plan The FilterInjection to be converted.
+ */
+ void convertFilterInjection(const physical::FilterInjectionPtr &physical_plan);
+
+ /**
* @brief Converts a HashJoin to BuildHash, HashJoin and
* DestroyHash operators.
*
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/LIPFilterGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/LIPFilterGenerator.cpp b/query_optimizer/LIPFilterGenerator.cpp
index 404037e..37559ed 100644
--- a/query_optimizer/LIPFilterGenerator.cpp
+++ b/query_optimizer/LIPFilterGenerator.cpp
@@ -30,6 +30,8 @@
#include "utility/lip_filter/LIPFilter.hpp"
#include "utility/lip_filter/LIPFilter.pb.h"
+#include "google/protobuf/text_format.h"
+
#include "glog/logging.h"
namespace quickstep {
@@ -64,8 +66,9 @@ void LIPFilterGenerator::registerAttributeMap(
}
void LIPFilterGenerator::deployLIPFilters(QueryPlan *execution_plan,
- serialization::QueryContext *query_context_proto) const {
- LIPFilterBuilderMap lip_filter_builder_map;
+ serialization::QueryContext *query_context_proto) {
+ lip_filter_builder_map_.clear();
+ lip_filter_deployment_protos_.clear();
// Deploy builders
const auto &build_info_map = lip_filter_configuration_->getBuildInfoMap();
@@ -76,8 +79,7 @@ void LIPFilterGenerator::deployLIPFilters(QueryPlan *execution_plan,
query_context_proto,
info.builder_node,
info.builder_operator_index,
- build_it->second,
- &lip_filter_builder_map);
+ build_it->second);
}
}
@@ -90,10 +92,22 @@ void LIPFilterGenerator::deployLIPFilters(QueryPlan *execution_plan,
query_context_proto,
info.prober_node,
info.prober_operator_index,
- probe_it->second,
- lip_filter_builder_map);
+ probe_it->second);
}
}
+
+ // Attach LIPFilterDeployment information to the RelationalOperators.
+ for (const auto &entry : lip_filter_deployment_protos_) {
+ RelationalOperator *relop =
+ execution_plan->getQueryPlanDAGMutable()->getNodePayloadMutable(entry.first);
+ relop->deployLIPFilters(entry.second.first);
+
+// std::cerr << "op_index: " << entry.first << " "
+// << "deployment_index: " << entry.second.first << "\n";
+// std::string str;
+// google::protobuf::TextFormat::PrintToString(*entry.second.second, &str);
+// std::cerr << str << "\n";
+ }
}
void LIPFilterGenerator::deployBuilderInternal(
@@ -101,12 +115,9 @@ void LIPFilterGenerator::deployBuilderInternal(
serialization::QueryContext *query_context_proto,
const physical::PhysicalPtr &builder_node,
const QueryPlan::DAGNodeIndex builder_operator_index,
- const std::vector<physical::LIPFilterBuildInfo> &build_info_vec,
- LIPFilterBuilderMap *lip_filter_builder_map) const {
- const auto lip_deployment_index = query_context_proto->lip_filter_deployments_size();
+ const std::vector<physical::LIPFilterBuildInfo> &build_info_vec) {
auto *lip_filter_deployment_info_proto =
- query_context_proto->add_lip_filter_deployments();
- lip_filter_deployment_info_proto->set_action_type(serialization::LIPFilterActionType::BUILD);
+ getLIPFilterDeploymentProto(builder_operator_index, query_context_proto);
const auto &builder_attribute_map = attribute_map_.at(builder_node);
for (const auto &info : build_info_vec) {
@@ -119,6 +130,7 @@ void LIPFilterGenerator::deployBuilderInternal(
switch (info.filter_type) {
case LIPFilterType::kSingleIdentityHashFilter: {
DCHECK(!attr_type.isVariableLength());
+ DCHECK(!info.is_anti_filter);
lip_filter_proto->set_lip_filter_type(
serialization::LIPFilterType::SINGLE_IDENTITY_HASH_FILTER);
lip_filter_proto->SetExtension(
@@ -127,27 +139,34 @@ void LIPFilterGenerator::deployBuilderInternal(
serialization::SingleIdentityHashFilter::attribute_size, attr_type.minimumByteLength());
break;
}
+ case LIPFilterType::kBitVectorExactFilter: {
+ DCHECK(!attr_type.isVariableLength());
+ lip_filter_proto->set_lip_filter_type(
+ serialization::LIPFilterType::BIT_VECTOR_EXACT_FILTER);
+ lip_filter_proto->SetExtension(
+ serialization::BitVectorExactFilter::filter_cardinality, info.filter_cardinality);
+ lip_filter_proto->SetExtension(
+ serialization::BitVectorExactFilter::attribute_size, attr_type.minimumByteLength());
+ lip_filter_proto->SetExtension(
+ serialization::BitVectorExactFilter::is_anti_filter, info.is_anti_filter);
+ break;
+ }
default:
LOG(FATAL) << "Unsupported LIPFilter type";
break;
}
// Register the builder information which is needed later by the probers.
- lip_filter_builder_map->emplace(
+ lip_filter_builder_map_.emplace(
std::make_pair(info.build_attribute->id(), builder_node),
std::make_pair(lip_filter_id, builder_operator_index));
// Add the builder deployment information into query context.
- auto *lip_filter_entry_proto = lip_filter_deployment_info_proto->add_entries();
+ auto *lip_filter_entry_proto = lip_filter_deployment_info_proto->add_build_entries();
lip_filter_entry_proto->set_lip_filter_id(lip_filter_id);
lip_filter_entry_proto->set_attribute_id(target_attr->getID());
lip_filter_entry_proto->mutable_attribute_type()->CopyFrom(attr_type.getProto());
}
-
- // Attach the LIPFilterDeployment information to the RelationalOperator.
- RelationalOperator *relop =
- execution_plan->getQueryPlanDAGMutable()->getNodePayloadMutable(builder_operator_index);
- relop->deployLIPFilters(lip_deployment_index);
}
void LIPFilterGenerator::deployProberInteral(
@@ -155,23 +174,20 @@ void LIPFilterGenerator::deployProberInteral(
serialization::QueryContext *query_context_proto,
const physical::PhysicalPtr &prober_node,
const QueryPlan::DAGNodeIndex prober_operator_index,
- const std::vector<physical::LIPFilterProbeInfo> &probe_info_vec,
- const LIPFilterBuilderMap &lip_filter_builder_map) const {
- const auto lip_deployment_index = query_context_proto->lip_filter_deployments_size();
+ const std::vector<physical::LIPFilterProbeInfo> &probe_info_vec) {
auto *lip_filter_deployment_info_proto =
- query_context_proto->add_lip_filter_deployments();
- lip_filter_deployment_info_proto->set_action_type(serialization::LIPFilterActionType::PROBE);
+ getLIPFilterDeploymentProto(prober_operator_index, query_context_proto);
const auto &prober_attribute_map = attribute_map_.at(prober_node);
for (const auto &info : probe_info_vec) {
// Find the corresponding builder for the to-be-probed LIPFilter.
const auto &builder_info =
- lip_filter_builder_map.at(
+ lip_filter_builder_map_.at(
std::make_pair(info.build_attribute->id(), info.builder));
const CatalogAttribute *target_attr = prober_attribute_map.at(info.probe_attribute->id());
// Add the prober deployment information into query context.
- auto *lip_filter_entry_proto = lip_filter_deployment_info_proto->add_entries();
+ auto *lip_filter_entry_proto = lip_filter_deployment_info_proto->add_probe_entries();
lip_filter_entry_proto->set_lip_filter_id(builder_info.first);
lip_filter_entry_proto->set_attribute_id(target_attr->getID());
lip_filter_entry_proto->mutable_attribute_type()->CopyFrom(
@@ -183,11 +199,23 @@ void LIPFilterGenerator::deployProberInteral(
builder_info.second,
true /* is_pipeline_breaker */);
}
+}
- // Attach the LIPFilterDeployment information to the RelationalOperator.
- RelationalOperator *relop =
- execution_plan->getQueryPlanDAGMutable()->getNodePayloadMutable(prober_operator_index);
- relop->deployLIPFilters(lip_deployment_index);
+serialization::LIPFilterDeployment* LIPFilterGenerator::getLIPFilterDeploymentProto(
+ const QueryPlan::DAGNodeIndex op_index,
+ serialization::QueryContext *query_context_proto) {
+ const auto proto_it = lip_filter_deployment_protos_.find(op_index);
+ if (proto_it == lip_filter_deployment_protos_.end()) {
+ const int lip_deployment_index =
+ query_context_proto->lip_filter_deployments_size();
+ auto *lip_filter_deployment_proto =
+ query_context_proto->add_lip_filter_deployments();
+ lip_filter_deployment_protos_.emplace(
+ op_index, std::make_pair(lip_deployment_index, lip_filter_deployment_proto));
+ return lip_filter_deployment_proto;
+ } else {
+ return proto_it->second.second;
+ }
}
} // namespace optimizer
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/LIPFilterGenerator.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/LIPFilterGenerator.hpp b/query_optimizer/LIPFilterGenerator.hpp
index 9d191a1..74daf73 100644
--- a/query_optimizer/LIPFilterGenerator.hpp
+++ b/query_optimizer/LIPFilterGenerator.hpp
@@ -30,6 +30,7 @@
#include "query_optimizer/expressions/ExprId.hpp"
#include "query_optimizer/physical/LIPFilterConfiguration.hpp"
#include "query_optimizer/physical/Aggregate.hpp"
+#include "query_optimizer/physical/FilterInjection.hpp"
#include "query_optimizer/physical/HashJoin.hpp"
#include "query_optimizer/physical/Physical.hpp"
#include "query_optimizer/physical/Selection.hpp"
@@ -39,7 +40,12 @@
namespace quickstep {
-namespace serialization { class QueryContext; }
+namespace serialization {
+
+class QueryContext;
+class LIPFilterDeployment;
+
+}
class CatalogAttribute;
@@ -93,6 +99,20 @@ class LIPFilterGenerator {
/**
* @brief Add physical-to-execution mapping information for deploying LIPFilters
+ * to a filter-injection node.
+ *
+ * @param filter_injection A physical FilterInjection node.
+ * @param build_filter_operator_index The index of the BuildLIPFilterOperator
+ * that corresponds to \p filter_injection in the execution plan.
+ */
+ void addFilterInjectionInfo(const physical::FilterInjectionPtr &filter_injection,
+ const QueryPlan::DAGNodeIndex build_filter_operator_index) {
+ builder_infos_.emplace_back(filter_injection, build_filter_operator_index);
+ prober_infos_.emplace_back(filter_injection, build_filter_operator_index);
+ }
+
+ /**
+ * @brief Add physical-to-execution mapping information for deploying LIPFilters
* to a hash-join.
*
* @param hash_join A physical HashJoin node.
@@ -128,7 +148,7 @@ class LIPFilterGenerator {
* @param query_context_proto QueryContext protobuf for the execution plan.
*/
void deployLIPFilters(QueryPlan *execution_plan,
- serialization::QueryContext *query_context_proto) const;
+ serialization::QueryContext *query_context_proto);
private:
/**
@@ -157,24 +177,21 @@ class LIPFilterGenerator {
const QueryPlan::DAGNodeIndex prober_operator_index;
};
- // Maps each LIPFilter's building attribute to the LIPFilter's id in QueryContext
- // as well as the LIPFilter's building relational operator's index.
- typedef std::map<std::pair<expressions::ExprId, physical::PhysicalPtr>,
- std::pair<QueryContext::lip_filter_id, QueryPlan::DAGNodeIndex>> LIPFilterBuilderMap;
-
void deployBuilderInternal(QueryPlan *execution_plan,
serialization::QueryContext *query_context_proto,
const physical::PhysicalPtr &builder_node,
const QueryPlan::DAGNodeIndex builder_operator_index,
- const std::vector<physical::LIPFilterBuildInfo> &build_info_vec,
- LIPFilterBuilderMap *lip_filter_builder_map) const;
+ const std::vector<physical::LIPFilterBuildInfo> &build_info_vec);
void deployProberInteral(QueryPlan *execution_plan,
serialization::QueryContext *query_context_proto,
const physical::PhysicalPtr &prober_node,
const QueryPlan::DAGNodeIndex prober_operator_index,
- const std::vector<physical::LIPFilterProbeInfo> &probe_info_vec,
- const LIPFilterBuilderMap &lip_filter_builder_map) const;
+ const std::vector<physical::LIPFilterProbeInfo> &probe_info_vec);
+
+ serialization::LIPFilterDeployment* getLIPFilterDeploymentProto(
+ const QueryPlan::DAGNodeIndex op_index,
+ serialization::QueryContext *query_context_proto);
const physical::LIPFilterConfigurationPtr lip_filter_configuration_;
@@ -183,6 +200,14 @@ class LIPFilterGenerator {
std::map<physical::PhysicalPtr, std::map<expressions::ExprId, const CatalogAttribute *>> attribute_map_;
+ // Maps each LIPFilter's building attribute to the LIPFilter's id in QueryContext
+ // as well as the LIPFilter's building relational operator's index.
+ std::map<std::pair<expressions::ExprId, physical::PhysicalPtr>,
+ std::pair<QueryContext::lip_filter_id, QueryPlan::DAGNodeIndex>> lip_filter_builder_map_;
+
+ std::map<QueryPlan::DAGNodeIndex,
+ std::pair<int, serialization::LIPFilterDeployment *>> lip_filter_deployment_protos_;
+
DISALLOW_COPY_AND_ASSIGN(LIPFilterGenerator);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/PhysicalGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.cpp b/query_optimizer/PhysicalGenerator.cpp
index 6c792ac..0e1b61e 100644
--- a/query_optimizer/PhysicalGenerator.cpp
+++ b/query_optimizer/PhysicalGenerator.cpp
@@ -30,7 +30,7 @@
#include "query_optimizer/rules/PruneColumns.hpp"
#include "query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp"
#include "query_optimizer/rules/SwapProbeBuild.hpp"
-#include "query_optimizer/rules/TransformFilterJoins.hpp"
+#include "query_optimizer/rules/InjectJoinFilters.hpp"
#include "query_optimizer/strategy/Aggregate.hpp"
#include "query_optimizer/strategy/Join.hpp"
#include "query_optimizer/strategy/OneToOne.hpp"
@@ -51,6 +51,8 @@ DEFINE_bool(reorder_hash_joins, true,
"cardinality and selective tables to be joined first, which is suitable "
"for queries on star-schema tables.");
+DEFINE_bool(inject_join_filters, true, "Transform HashJoin to FilterInjection.");
+
DEFINE_bool(use_lip_filters, true,
"If true, use LIP (Lookahead Information Passing) filters to accelerate "
"query processing. LIP filters are effective for queries on star schema "
@@ -110,7 +112,9 @@ P::PhysicalPtr PhysicalGenerator::optimizePlan() {
} else {
rules.emplace_back(new SwapProbeBuild());
}
- rules.emplace_back(new TransformFilterJoins());
+ if (FLAGS_inject_join_filters) {
+ rules.emplace_back(new InjectJoinFilters());
+ }
if (FLAGS_use_lip_filters) {
rules.emplace_back(new AttachLIPFilters());
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/cost_model/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/CMakeLists.txt b/query_optimizer/cost_model/CMakeLists.txt
index 91428ab..412d2b2 100644
--- a/query_optimizer/cost_model/CMakeLists.txt
+++ b/query_optimizer/cost_model/CMakeLists.txt
@@ -32,6 +32,7 @@ target_link_libraries(quickstep_queryoptimizer_costmodel_SimpleCostModel
quickstep_catalog_CatalogRelation
quickstep_queryoptimizer_costmodel_CostModel
quickstep_queryoptimizer_physical_Aggregate
+ quickstep_queryoptimizer_physical_FilterInjection
quickstep_queryoptimizer_physical_HashJoin
quickstep_queryoptimizer_physical_NestedLoopsJoin
quickstep_queryoptimizer_physical_Physical
@@ -60,6 +61,7 @@ target_link_libraries(quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostMod
quickstep_queryoptimizer_expressions_PatternMatcher
quickstep_queryoptimizer_expressions_Predicate
quickstep_queryoptimizer_physical_Aggregate
+ quickstep_queryoptimizer_physical_FilterInjection
quickstep_queryoptimizer_physical_HashJoin
quickstep_queryoptimizer_physical_NestedLoopsJoin
quickstep_queryoptimizer_physical_PatternMatcher
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/cost_model/SimpleCostModel.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/SimpleCostModel.cpp b/query_optimizer/cost_model/SimpleCostModel.cpp
index 74b62d6..a97e818 100644
--- a/query_optimizer/cost_model/SimpleCostModel.cpp
+++ b/query_optimizer/cost_model/SimpleCostModel.cpp
@@ -25,6 +25,7 @@
#include "catalog/CatalogRelation.hpp"
#include "query_optimizer/physical/Aggregate.hpp"
#include "query_optimizer/physical/NestedLoopsJoin.hpp"
+#include "query_optimizer/physical/FilterInjection.hpp"
#include "query_optimizer/physical/HashJoin.hpp"
#include "query_optimizer/physical/Physical.hpp"
#include "query_optimizer/physical/PhysicalType.hpp"
@@ -59,6 +60,9 @@ std::size_t SimpleCostModel::estimateCardinality(
case P::PhysicalType::kTableGenerator:
return estimateCardinalityForTableGenerator(
std::static_pointer_cast<const P::TableGenerator>(physical_plan));
+ case P::PhysicalType::kFilterInjection:
+ return estimateCardinalityForFilterInjection(
+ std::static_pointer_cast<const P::FilterInjection>(physical_plan));
case P::PhysicalType::kHashJoin:
return estimateCardinalityForHashJoin(
std::static_pointer_cast<const P::HashJoin>(physical_plan));
@@ -112,6 +116,11 @@ std::size_t SimpleCostModel::estimateCardinalityForTableGenerator(
return physical_plan->generator_function_handle()->getEstimatedCardinality();
}
+std::size_t SimpleCostModel::estimateCardinalityForFilterInjection(
+ const P::FilterInjectionPtr &physical_plan) {
+ return estimateCardinality(physical_plan->left());
+}
+
std::size_t SimpleCostModel::estimateCardinalityForHashJoin(
const P::HashJoinPtr &physical_plan) {
return std::max(estimateCardinality(physical_plan->left()),
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/cost_model/SimpleCostModel.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/SimpleCostModel.hpp b/query_optimizer/cost_model/SimpleCostModel.hpp
index 16366cd..1c60e24 100644
--- a/query_optimizer/cost_model/SimpleCostModel.hpp
+++ b/query_optimizer/cost_model/SimpleCostModel.hpp
@@ -26,6 +26,7 @@
#include "query_optimizer/cost_model/CostModel.hpp"
#include "query_optimizer/physical/Aggregate.hpp"
#include "query_optimizer/physical/NestedLoopsJoin.hpp"
+#include "query_optimizer/physical/FilterInjection.hpp"
#include "query_optimizer/physical/HashJoin.hpp"
#include "query_optimizer/physical/Physical.hpp"
#include "query_optimizer/physical/Selection.hpp"
@@ -80,6 +81,10 @@ class SimpleCostModel : public CostModel {
std::size_t estimateCardinalityForSort(
const physical::SortPtr &physical_plan);
+ // Returns the left child's cardinality
+ std::size_t estimateCardinalityForFilterInjection(
+ const physical::FilterInjectionPtr &physical_plan);
+
// Returns the larger value of the estimated cardinalities of two
// input plans.
std::size_t estimateCardinalityForHashJoin(
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
index cba13ff..c81fa96 100644
--- a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
@@ -38,6 +38,7 @@
#include "query_optimizer/expressions/PatternMatcher.hpp"
#include "query_optimizer/physical/Aggregate.hpp"
#include "query_optimizer/physical/NestedLoopsJoin.hpp"
+#include "query_optimizer/physical/FilterInjection.hpp"
#include "query_optimizer/physical/HashJoin.hpp"
#include "query_optimizer/physical/PatternMatcher.hpp"
#include "query_optimizer/physical/Physical.hpp"
@@ -75,6 +76,9 @@ std::size_t StarSchemaSimpleCostModel::estimateCardinality(
case P::PhysicalType::kTableGenerator:
return estimateCardinalityForTableGenerator(
std::static_pointer_cast<const P::TableGenerator>(physical_plan));
+ case P::PhysicalType::kFilterInjection:
+ return estimateCardinalityForFilterInjection(
+ std::static_pointer_cast<const P::FilterInjection>(physical_plan));
case P::PhysicalType::kHashJoin:
return estimateCardinalityForHashJoin(
std::static_pointer_cast<const P::HashJoin>(physical_plan));
@@ -97,7 +101,8 @@ std::size_t StarSchemaSimpleCostModel::estimateCardinality(
return estimateCardinalityForWindowAggregate(
std::static_pointer_cast<const P::WindowAggregate>(physical_plan));
default:
- LOG(FATAL) << "Unsupported physical plan:" << physical_plan->toString();
+ return 1u;
+// LOG(FATAL) << "Unsupported physical plan:" << physical_plan->toString();
}
}
@@ -136,6 +141,13 @@ std::size_t StarSchemaSimpleCostModel::estimateCardinalityForTableGenerator(
return physical_plan->generator_function_handle()->getEstimatedCardinality();
}
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForFilterInjection(
+ const P::FilterInjectionPtr &physical_plan) {
+ 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);
+}
+
std::size_t StarSchemaSimpleCostModel::estimateCardinalityForHashJoin(
const P::HashJoinPtr &physical_plan) {
std::size_t left_cardinality = estimateCardinality(physical_plan->left());
@@ -218,6 +230,18 @@ std::size_t StarSchemaSimpleCostModel::estimateNumDistinctValues(
}
break;
}
+ case P::PhysicalType::kFilterInjection: {
+ const P::FilterInjectionPtr &filter_injection =
+ std::static_pointer_cast<const P::FilterInjection>(physical_plan);
+ if (E::ContainsExprId(filter_injection->left()->getOutputAttributes(), attribute_id)) {
+ std::size_t left_child_num_distinct_values =
+ estimateNumDistinctValues(attribute_id, filter_injection->left());
+ double right_child_selectivity =
+ estimateSelectivity(filter_injection->right());
+ return static_cast<std::size_t>(
+ left_child_num_distinct_values * right_child_selectivity + 0.5);
+ }
+ }
case P::PhysicalType::kHashJoin: {
const P::HashJoinPtr &hash_join =
std::static_pointer_cast<const P::HashJoin>(physical_plan);
@@ -256,6 +280,12 @@ double StarSchemaSimpleCostModel::estimateSelectivity(
double child_selectivity = estimateSelectivity(selection->input());
return filter_selectivity * child_selectivity;
}
+ 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());
+ }
case P::PhysicalType::kHashJoin: {
const P::HashJoinPtr &hash_join =
std::static_pointer_cast<const P::HashJoin>(physical_plan);
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp b/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
index 8899261..85914cd 100644
--- a/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
@@ -29,6 +29,7 @@
#include "query_optimizer/expressions/Predicate.hpp"
#include "query_optimizer/physical/Aggregate.hpp"
#include "query_optimizer/physical/NestedLoopsJoin.hpp"
+#include "query_optimizer/physical/FilterInjection.hpp"
#include "query_optimizer/physical/HashJoin.hpp"
#include "query_optimizer/physical/Physical.hpp"
#include "query_optimizer/physical/Selection.hpp"
@@ -129,6 +130,9 @@ class StarSchemaSimpleCostModel : public CostModel {
std::size_t estimateCardinalityForAggregate(
const physical::AggregatePtr &physical_plan);
+ std::size_t estimateCardinalityForFilterInjection(
+ const physical::FilterInjectionPtr &physical_plan);
+
std::size_t estimateCardinalityForHashJoin(
const physical::HashJoinPtr &physical_plan);
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/CMakeLists.txt b/query_optimizer/physical/CMakeLists.txt
index 853333c..fef701b 100644
--- a/query_optimizer/physical/CMakeLists.txt
+++ b/query_optimizer/physical/CMakeLists.txt
@@ -23,7 +23,7 @@ add_library(quickstep_queryoptimizer_physical_CreateIndex CreateIndex.cpp Create
add_library(quickstep_queryoptimizer_physical_CreateTable CreateTable.cpp CreateTable.hpp)
add_library(quickstep_queryoptimizer_physical_DeleteTuples DeleteTuples.cpp DeleteTuples.hpp)
add_library(quickstep_queryoptimizer_physical_DropTable DropTable.cpp DropTable.hpp)
-add_library(quickstep_queryoptimizer_physical_FilterJoin FilterJoin.cpp FilterJoin.hpp)
+add_library(quickstep_queryoptimizer_physical_FilterInjection FilterInjection.cpp FilterInjection.hpp)
add_library(quickstep_queryoptimizer_physical_HashJoin HashJoin.cpp HashJoin.hpp)
add_library(quickstep_queryoptimizer_physical_InsertSelection InsertSelection.cpp InsertSelection.hpp)
add_library(quickstep_queryoptimizer_physical_InsertTuple InsertTuple.cpp InsertTuple.hpp)
@@ -115,13 +115,12 @@ target_link_libraries(quickstep_queryoptimizer_physical_DropTable
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_physical_PhysicalType
quickstep_utility_Macros)
-target_link_libraries(quickstep_queryoptimizer_physical_FilterJoin
+target_link_libraries(quickstep_queryoptimizer_physical_FilterInjection
glog
quickstep_queryoptimizer_OptimizerTree
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_ExpressionUtil
quickstep_queryoptimizer_expressions_NamedExpression
- quickstep_queryoptimizer_expressions_Predicate
quickstep_queryoptimizer_physical_BinaryJoin
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_physical_PhysicalType
@@ -294,7 +293,7 @@ target_link_libraries(quickstep_queryoptimizer_physical
quickstep_queryoptimizer_physical_CreateTable
quickstep_queryoptimizer_physical_DeleteTuples
quickstep_queryoptimizer_physical_DropTable
- quickstep_queryoptimizer_physical_FilterJoin
+ quickstep_queryoptimizer_physical_FilterInjection
quickstep_queryoptimizer_physical_HashJoin
quickstep_queryoptimizer_physical_InsertSelection
quickstep_queryoptimizer_physical_InsertTuple
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/FilterInjection.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/FilterInjection.cpp b/query_optimizer/physical/FilterInjection.cpp
new file mode 100644
index 0000000..1aa25d1
--- /dev/null
+++ b/query_optimizer/physical/FilterInjection.cpp
@@ -0,0 +1,102 @@
+/**
+ * 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/physical/FilterInjection.hpp"
+
+#include <string>
+#include <vector>
+
+#include "query_optimizer/OptimizerTree.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/expressions/NamedExpression.hpp"
+#include "utility/Cast.hpp"
+
+namespace quickstep {
+namespace optimizer {
+namespace physical {
+
+namespace E = ::quickstep::optimizer::expressions;
+
+std::vector<E::AttributeReferencePtr> FilterInjection::getReferencedAttributes() const {
+ std::vector<E::AttributeReferencePtr> referenced_attributes;
+ for (const auto &project_expression : project_expressions()) {
+ const auto &referenced_attributes_in_expression =
+ project_expression->getReferencedAttributes();
+ referenced_attributes.insert(referenced_attributes.end(),
+ referenced_attributes_in_expression.begin(),
+ referenced_attributes_in_expression.end());
+ }
+ referenced_attributes.insert(referenced_attributes.end(),
+ probe_attributes_.begin(),
+ probe_attributes_.end());
+ referenced_attributes.insert(referenced_attributes.end(),
+ build_attributes_.begin(),
+ build_attributes_.end());
+ return referenced_attributes;
+}
+
+bool FilterInjection::maybeCopyWithPrunedExpressions(
+ const expressions::UnorderedNamedExpressionSet &referenced_expressions,
+ PhysicalPtr *output) const {
+ std::vector<E::NamedExpressionPtr> new_project_expressions;
+ const auto ¤t_project_expressions = project_expressions();
+ for (const auto &project_expression : current_project_expressions) {
+ if (referenced_expressions.find(project_expression) != referenced_expressions.end()) {
+ new_project_expressions.emplace_back(project_expression);
+ }
+ }
+ if (new_project_expressions.size() != current_project_expressions.size()) {
+ *output = Create(left(),
+ right(),
+ probe_attributes_,
+ build_attributes_,
+ new_project_expressions,
+ is_anti_filter_);
+ return true;
+ }
+ return false;
+}
+
+void FilterInjection::getFieldStringItems(
+ std::vector<std::string> *inline_field_names,
+ std::vector<std::string> *inline_field_values,
+ std::vector<std::string> *non_container_child_field_names,
+ std::vector<OptimizerTreeBaseNodePtr> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<OptimizerTreeBaseNodePtr>> *container_child_fields) const {
+ BinaryJoin::getFieldStringItems(inline_field_names,
+ inline_field_values,
+ non_container_child_field_names,
+ non_container_child_fields,
+ container_child_field_names,
+ container_child_fields);
+
+ inline_field_names->push_back("is_anti_filter");
+ inline_field_values->push_back(std::to_string(is_anti_filter_));
+
+ container_child_field_names->push_back("probe_attributes");
+ container_child_fields->push_back(CastSharedPtrVector<OptimizerTreeBase>(probe_attributes_));
+ container_child_field_names->push_back("build_attributes");
+ container_child_fields->push_back(CastSharedPtrVector<OptimizerTreeBase>(build_attributes_));
+}
+
+} // namespace physical
+} // namespace optimizer
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/FilterInjection.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/FilterInjection.hpp b/query_optimizer/physical/FilterInjection.hpp
new file mode 100644
index 0000000..761831b
--- /dev/null
+++ b/query_optimizer/physical/FilterInjection.hpp
@@ -0,0 +1,146 @@
+/**
+ * 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_PHYSICAL_FILTER_INJECTION_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_FILTER_INJECTION_HPP_
+
+#include <cstddef>
+#include <memory>
+#include <string>
+#include <type_traits>
+#include <vector>
+
+#include "query_optimizer/OptimizerTree.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/physical/BinaryJoin.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/PhysicalType.hpp"
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+namespace physical {
+
+/** \addtogroup OptimizerPhysical
+ * @{
+ */
+
+class FilterInjection;
+typedef std::shared_ptr<const FilterInjection> FilterInjectionPtr;
+
+/**
+ * @brief Physical filter injection node.
+ */
+class FilterInjection : public BinaryJoin {
+ public:
+ PhysicalType getPhysicalType() const override { return PhysicalType::kFilterInjection; }
+
+ std::string getName() const override {
+ if (is_anti_filter_) {
+ return "FilterInjection-Anti";
+ } else {
+ return "FilterInjection";
+ }
+ }
+
+ const std::vector<expressions::AttributeReferencePtr>& probe_attributes() const {
+ return probe_attributes_;
+ }
+
+ const std::vector<expressions::AttributeReferencePtr>& build_attributes() const {
+ return build_attributes_;
+ }
+
+ const bool is_anti_filter() const {
+ return is_anti_filter_;
+ }
+
+ PhysicalPtr copyWithNewChildren(
+ const std::vector<PhysicalPtr> &new_children) const override {
+ DCHECK_EQ(children().size(), new_children.size());
+ return Create(new_children[0],
+ new_children[1],
+ probe_attributes_,
+ build_attributes_,
+ project_expressions(),
+ is_anti_filter_);
+ }
+
+ std::vector<expressions::AttributeReferencePtr> getReferencedAttributes() const override;
+
+ bool maybeCopyWithPrunedExpressions(
+ const expressions::UnorderedNamedExpressionSet &referenced_expressions,
+ PhysicalPtr *output) const override;
+
+ static FilterInjectionPtr Create(
+ const PhysicalPtr &probe_child,
+ const PhysicalPtr &build_child,
+ const std::vector<expressions::AttributeReferencePtr> &probe_attributes,
+ const std::vector<expressions::AttributeReferencePtr> &build_attributes,
+ const std::vector<expressions::NamedExpressionPtr> &project_expressions,
+ const bool is_anti_filter) {
+ return FilterInjectionPtr(
+ new FilterInjection(probe_child,
+ build_child,
+ probe_attributes,
+ build_attributes,
+ project_expressions,
+ is_anti_filter));
+ }
+
+ protected:
+ void getFieldStringItems(
+ std::vector<std::string> *inline_field_names,
+ std::vector<std::string> *inline_field_values,
+ std::vector<std::string> *non_container_child_field_names,
+ std::vector<OptimizerTreeBaseNodePtr> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<OptimizerTreeBaseNodePtr>> *container_child_fields) const override;
+
+ private:
+ FilterInjection(
+ const PhysicalPtr &probe_child,
+ const PhysicalPtr &build_child,
+ const std::vector<expressions::AttributeReferencePtr> &probe_attributes,
+ const std::vector<expressions::AttributeReferencePtr> &build_attributes,
+ const std::vector<expressions::NamedExpressionPtr> &project_expressions,
+ const bool is_anti_filter)
+ : BinaryJoin(probe_child, build_child, project_expressions),
+ probe_attributes_(probe_attributes),
+ build_attributes_(build_attributes),
+ is_anti_filter_(is_anti_filter) {
+ }
+
+ std::vector<expressions::AttributeReferencePtr> probe_attributes_;
+ std::vector<expressions::AttributeReferencePtr> build_attributes_;
+ bool is_anti_filter_;
+
+ DISALLOW_COPY_AND_ASSIGN(FilterInjection);
+};
+
+/** @} */
+
+} // namespace physical
+} // namespace optimizer
+} // namespace quickstep
+
+#endif // QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_FILTER_INJECTION_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/FilterJoin.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/FilterJoin.cpp b/query_optimizer/physical/FilterJoin.cpp
deleted file mode 100644
index 0ec3968..0000000
--- a/query_optimizer/physical/FilterJoin.cpp
+++ /dev/null
@@ -1,98 +0,0 @@
-/**
- * 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/physical/FilterJoin.hpp"
-
-#include <string>
-#include <vector>
-
-#include "query_optimizer/OptimizerTree.hpp"
-#include "query_optimizer/expressions/AttributeReference.hpp"
-#include "query_optimizer/expressions/ExpressionUtil.hpp"
-#include "query_optimizer/expressions/NamedExpression.hpp"
-#include "query_optimizer/expressions/Predicate.hpp"
-#include "utility/Cast.hpp"
-
-namespace quickstep {
-namespace optimizer {
-namespace physical {
-
-namespace E = ::quickstep::optimizer::expressions;
-
-std::vector<E::AttributeReferencePtr> FilterJoin::getReferencedAttributes() const {
- std::vector<E::AttributeReferencePtr> referenced_attributes;
- for (const auto &project_expression : project_expressions()) {
- const std::vector<E::AttributeReferencePtr> referenced_attributes_in_expression =
- project_expression->getReferencedAttributes();
- referenced_attributes.insert(referenced_attributes.end(),
- referenced_attributes_in_expression.begin(),
- referenced_attributes_in_expression.end());
- }
- referenced_attributes.insert(referenced_attributes.end(),
- probe_join_attributes_.begin(),
- probe_join_attributes_.end());
- referenced_attributes.insert(referenced_attributes.end(),
- build_join_attributes_.begin(),
- build_join_attributes_.end());
- return referenced_attributes;
-}
-
-bool FilterJoin::maybeCopyWithPrunedExpressions(
- const E::UnorderedNamedExpressionSet &referenced_expressions,
- PhysicalPtr *output) const {
- std::vector<E::NamedExpressionPtr> new_project_expressions;
- const auto ¤t_project_expressions = project_expressions();
- for (const auto &project_expression : current_project_expressions) {
- if (referenced_expressions.find(project_expression) != referenced_expressions.end()) {
- new_project_expressions.emplace_back(project_expression);
- }
- }
- if (new_project_expressions.size() != current_project_expressions.size()) {
- *output = Create(left(),
- right(),
- probe_join_attributes_,
- build_join_attributes_,
- new_project_expressions);
- return true;
- }
- return false;
-}
-
-void FilterJoin::getFieldStringItems(
- std::vector<std::string> *inline_field_names,
- std::vector<std::string> *inline_field_values,
- std::vector<std::string> *non_container_child_field_names,
- std::vector<OptimizerTreeBaseNodePtr> *non_container_child_fields,
- std::vector<std::string> *container_child_field_names,
- std::vector<std::vector<OptimizerTreeBaseNodePtr>> *container_child_fields) const {
- BinaryJoin::getFieldStringItems(inline_field_names,
- inline_field_values,
- non_container_child_field_names,
- non_container_child_fields,
- container_child_field_names,
- container_child_fields);
- container_child_field_names->push_back("probe_join_attributes");
- container_child_fields->push_back(CastSharedPtrVector<OptimizerTreeBase>(probe_join_attributes_));
- container_child_field_names->push_back("build_join_attributes");
- container_child_fields->push_back(CastSharedPtrVector<OptimizerTreeBase>(build_join_attributes_));
-}
-
-} // namespace physical
-} // namespace optimizer
-} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/FilterJoin.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/FilterJoin.hpp b/query_optimizer/physical/FilterJoin.hpp
deleted file mode 100644
index 281b072..0000000
--- a/query_optimizer/physical/FilterJoin.hpp
+++ /dev/null
@@ -1,134 +0,0 @@
-/**
- * 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_PHYSICAL_FILTER_JOIN_HPP_
-#define QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_FILTER_JOIN_HPP_
-
-#include <cstddef>
-#include <memory>
-#include <string>
-#include <type_traits>
-#include <vector>
-
-#include "query_optimizer/OptimizerTree.hpp"
-#include "query_optimizer/expressions/AttributeReference.hpp"
-#include "query_optimizer/expressions/ExpressionUtil.hpp"
-#include "query_optimizer/expressions/NamedExpression.hpp"
-#include "query_optimizer/expressions/Predicate.hpp"
-#include "query_optimizer/physical/BinaryJoin.hpp"
-#include "query_optimizer/physical/Physical.hpp"
-#include "query_optimizer/physical/PhysicalType.hpp"
-#include "utility/Macros.hpp"
-
-#include "glog/logging.h"
-
-namespace quickstep {
-namespace optimizer {
-namespace physical {
-
-/** \addtogroup OptimizerPhysical
- * @{
- */
-
-class FilterJoin;
-typedef std::shared_ptr<const FilterJoin> FilterJoinPtr;
-
-/**
- * @brief Physical filter join node.
- */
-class FilterJoin : public BinaryJoin {
- public:
- PhysicalType getPhysicalType() const override { return PhysicalType::kFilterJoin; }
-
- std::string getName() const override {
- return "FilterJoin";
- }
-
- const std::vector<expressions::AttributeReferencePtr>& probe_join_attributes() const {
- return probe_join_attributes_;
- }
-
- const std::vector<expressions::AttributeReferencePtr>& build_join_attributes() const {
- return build_join_attributes_;
- }
-
- PhysicalPtr copyWithNewChildren(
- const std::vector<PhysicalPtr> &new_children) const override {
- DCHECK_EQ(children().size(), new_children.size());
- return Create(new_children[0],
- new_children[1],
- probe_join_attributes_,
- build_join_attributes_,
- project_expressions());
- }
-
- std::vector<expressions::AttributeReferencePtr> getReferencedAttributes() const override;
-
- bool maybeCopyWithPrunedExpressions(
- const expressions::UnorderedNamedExpressionSet &referenced_expressions,
- PhysicalPtr *output) const override;
-
- static FilterJoinPtr Create(
- const PhysicalPtr &probe_child,
- const PhysicalPtr &build_child,
- const std::vector<expressions::AttributeReferencePtr> &probe_join_attributes,
- const std::vector<expressions::AttributeReferencePtr> &build_join_attributes,
- const std::vector<expressions::NamedExpressionPtr> &project_expressions) {
- return FilterJoinPtr(
- new FilterJoin(probe_child,
- build_child,
- probe_join_attributes,
- build_join_attributes,
- project_expressions));
- }
-
- protected:
- void getFieldStringItems(
- std::vector<std::string> *inline_field_names,
- std::vector<std::string> *inline_field_values,
- std::vector<std::string> *non_container_child_field_names,
- std::vector<OptimizerTreeBaseNodePtr> *non_container_child_fields,
- std::vector<std::string> *container_child_field_names,
- std::vector<std::vector<OptimizerTreeBaseNodePtr>> *container_child_fields) const override;
-
- private:
- FilterJoin(
- const PhysicalPtr &probe_child,
- const PhysicalPtr &build_child,
- const std::vector<expressions::AttributeReferencePtr> &probe_join_attributes,
- const std::vector<expressions::AttributeReferencePtr> &build_join_attributes,
- const std::vector<expressions::NamedExpressionPtr> &project_expressions)
- : BinaryJoin(probe_child, build_child, project_expressions),
- probe_join_attributes_(probe_join_attributes),
- build_join_attributes_(build_join_attributes) {
- }
-
- std::vector<expressions::AttributeReferencePtr> probe_join_attributes_;
- std::vector<expressions::AttributeReferencePtr> build_join_attributes_;
-
- DISALLOW_COPY_AND_ASSIGN(FilterJoin);
-};
-
-/** @} */
-
-} // namespace physical
-} // namespace optimizer
-} // namespace quickstep
-
-#endif /* QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_FILTER_JOIN_HPP_ */
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/LIPFilterConfiguration.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/LIPFilterConfiguration.hpp b/query_optimizer/physical/LIPFilterConfiguration.hpp
index 62a6149..b4ae548 100644
--- a/query_optimizer/physical/LIPFilterConfiguration.hpp
+++ b/query_optimizer/physical/LIPFilterConfiguration.hpp
@@ -50,17 +50,32 @@ struct LIPFilterBuildInfo {
* @param build_attribute_in The attribute to build the LIP filter with.
* @param filter_cardinality_in The LIP filter's cardinality.
* @param filter_type_in The LIP filter's type.
+ * @param is_anti_filter_in Whether this LIPFilter is an anti-filter.
*/
LIPFilterBuildInfo(const expressions::AttributeReferencePtr &build_attribute_in,
const std::size_t filter_cardinality_in,
- const LIPFilterType &filter_type_in)
+ const LIPFilterType &filter_type_in,
+ const bool is_anti_filter_in)
: build_attribute(build_attribute_in),
filter_cardinality(filter_cardinality_in),
- filter_type(filter_type_in) {
- }
+ filter_type(filter_type_in),
+ is_anti_filter(is_anti_filter_in) {}
+
+ /**
+ * @brief Copy constructor.
+ *
+ * @param info The LIPFilter build info to copy.
+ */
+ LIPFilterBuildInfo(const LIPFilterBuildInfo &info)
+ : build_attribute(info.build_attribute),
+ filter_cardinality(info.filter_cardinality),
+ filter_type(info.filter_type),
+ is_anti_filter(info.is_anti_filter) {}
+
const expressions::AttributeReferencePtr build_attribute;
const std::size_t filter_cardinality;
const LIPFilterType filter_type;
+ const bool is_anti_filter;
};
/**
@@ -79,8 +94,18 @@ struct LIPFilterProbeInfo {
const PhysicalPtr &builder_in)
: probe_attribute(probe_attribute_in),
build_attribute(build_attribute_in),
- builder(builder_in) {
- }
+ builder(builder_in) {}
+
+ /**
+ * @brief Copy constructor.
+ *
+ * @param info The LIPFilter probe info to copy.
+ */
+ LIPFilterProbeInfo(const LIPFilterProbeInfo &info)
+ : probe_attribute(info.probe_attribute),
+ build_attribute(info.build_attribute),
+ builder(info.builder) {}
+
const expressions::AttributeReferencePtr probe_attribute;
const expressions::AttributeReferencePtr build_attribute;
const PhysicalPtr builder;
@@ -112,9 +137,10 @@ class LIPFilterConfiguration {
void addBuildInfo(const expressions::AttributeReferencePtr &build_attribute,
const PhysicalPtr &builder,
const std::size_t filter_size,
- const LIPFilterType &filter_type) {
+ const LIPFilterType &filter_type,
+ const bool is_anti_filter) {
build_info_map_[builder].emplace_back(
- build_attribute, filter_size, filter_type);
+ build_attribute, filter_size, filter_type, is_anti_filter);
}
/**
@@ -155,6 +181,31 @@ class LIPFilterConfiguration {
return probe_info_map_;
}
+ /**
+ * @brief Clone a copy of this configuration.
+ *
+ * @return A copy of this confiugration. Caller should take ownership of the
+ * returned object.
+ */
+ LIPFilterConfiguration* clone() const {
+ LIPFilterConfiguration *new_conf = new LIPFilterConfiguration();
+ for (const auto &build_pair : build_info_map_) {
+ auto &new_build_vec = new_conf->build_info_map_[build_pair.first];
+ const auto &build_vec = build_pair.second;
+ for (const auto &info : build_vec) {
+ new_build_vec.emplace_back(info);
+ }
+ }
+ for (const auto &probe_pair : probe_info_map_) {
+ auto &new_probe_vec = new_conf->probe_info_map_[probe_pair.first];
+ const auto &probe_vec = probe_pair.second;
+ for (const auto &info : probe_vec) {
+ new_probe_vec.emplace_back(info);
+ }
+ }
+ return new_conf;
+ }
+
private:
std::map<PhysicalPtr, std::vector<LIPFilterBuildInfo>> build_info_map_;
std::map<PhysicalPtr, std::vector<LIPFilterProbeInfo>> probe_info_map_;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/PatternMatcher.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/PatternMatcher.hpp b/query_optimizer/physical/PatternMatcher.hpp
index 4336767..c675cdb 100644
--- a/query_optimizer/physical/PatternMatcher.hpp
+++ b/query_optimizer/physical/PatternMatcher.hpp
@@ -35,7 +35,7 @@ class CopyFrom;
class CreateTable;
class DeleteTuples;
class DropTable;
-class FilterJoin;
+class FilterInjection;
class HashJoin;
class InsertTuple;
class Join;
@@ -114,7 +114,7 @@ using SomeCopyFrom = SomePhysicalNode<CopyFrom, PhysicalType::kCopyFrom>;
using SomeCreateTable = SomePhysicalNode<CreateTable, PhysicalType::kCreateTable>;
using SomeDeleteTuples = SomePhysicalNode<DeleteTuples, PhysicalType::kDeleteTuples>;
using SomeDropTable = SomePhysicalNode<DropTable, PhysicalType::kDropTable>;
-using SomeFilterJoin = SomePhysicalNode<FilterJoin, PhysicalType::kFilterJoin>;
+using SomeFilterInjection = SomePhysicalNode<FilterInjection, PhysicalType::kFilterInjection>;
using SomeHashJoin = SomePhysicalNode<HashJoin, PhysicalType::kHashJoin>;
using SomeInsertTuple = SomePhysicalNode<InsertTuple, PhysicalType::kInsertTuple>;
using SomeJoin = SomePhysicalNode<Join, PhysicalType::kHashJoin, PhysicalType::kNestedLoopsJoin>;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/PhysicalType.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/PhysicalType.hpp b/query_optimizer/physical/PhysicalType.hpp
index 1da5929..bcf7d22 100644
--- a/query_optimizer/physical/PhysicalType.hpp
+++ b/query_optimizer/physical/PhysicalType.hpp
@@ -38,7 +38,7 @@ enum class PhysicalType {
kCreateTable,
kDeleteTuples,
kDropTable,
- kFilterJoin,
+ kFilterInjection,
kHashJoin,
kInsertSelection,
kInsertTuple,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/physical/TopLevelPlan.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/TopLevelPlan.hpp b/query_optimizer/physical/TopLevelPlan.hpp
index 7dfc2b6..9e567e1 100644
--- a/query_optimizer/physical/TopLevelPlan.hpp
+++ b/query_optimizer/physical/TopLevelPlan.hpp
@@ -126,7 +126,8 @@ class TopLevelPlan : public Physical {
}
return TopLevelPlan::Create(new_children[0],
new_shared_subplans,
- uncorrelated_subquery_map_);
+ uncorrelated_subquery_map_,
+ lip_filter_configuration_);
}
std::vector<expressions::AttributeReferencePtr> getOutputAttributes() const override {
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/rules/AttachLIPFilters.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/AttachLIPFilters.cpp b/query_optimizer/rules/AttachLIPFilters.cpp
index b3c57ab..c4551bc 100644
--- a/query_optimizer/rules/AttachLIPFilters.cpp
+++ b/query_optimizer/rules/AttachLIPFilters.cpp
@@ -55,7 +55,14 @@ P::PhysicalPtr AttachLIPFilters::apply(const P::PhysicalPtr &input) {
cost_model_.reset(
new cost::StarSchemaSimpleCostModel(
top_level_plan->shared_subplans()));
- lip_filter_configuration_.reset(new P::LIPFilterConfiguration());
+
+ const P::LIPFilterConfigurationPtr &existing_configuration =
+ top_level_plan->lip_filter_configuration();
+ if (existing_configuration != nullptr) {
+ lip_filter_configuration_.reset(existing_configuration->clone());
+ } else {
+ lip_filter_configuration_.reset(new P::LIPFilterConfiguration());
+ }
std::set<E::ExprId> already_filtered_attributes;
attachLIPFilters(NodeList(input), &already_filtered_attributes);
@@ -101,7 +108,7 @@ void AttachLIPFilters::attachLIPFilters(
}
if (probe_child != nullptr &&
- cost_model_->estimateCardinality(probe_child) > 10000000) {
+ cost_model_->estimateCardinality(probe_child) >= 100000) {
const auto &candidate_lip_filters = getProbeSideInfo(path.cons(probe_child));
if (!candidate_lip_filters.empty()) {
std::map<E::AttributeReferencePtr, LIPFilterInfoPtr> selected_filters;
@@ -122,7 +129,8 @@ void AttachLIPFilters::attachLIPFilters(
pair.second->source_attribute,
pair.second->source,
pair.second->estimated_cardinality * 8,
- LIPFilterType::kSingleIdentityHashFilter);
+ LIPFilterType::kSingleIdentityHashFilter,
+ false);
lip_filter_configuration_->addProbeInfo(
pair.first,
node,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/rules/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CMakeLists.txt b/query_optimizer/rules/CMakeLists.txt
index 1d5b103..1eeb3a5 100644
--- a/query_optimizer/rules/CMakeLists.txt
+++ b/query_optimizer/rules/CMakeLists.txt
@@ -22,6 +22,7 @@ add_library(quickstep_queryoptimizer_rules_AttachLIPFilters AttachLIPFilters.cpp
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_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)
add_library(quickstep_queryoptimizer_rules_PushDownFilter PushDownFilter.cpp PushDownFilter.hpp)
add_library(quickstep_queryoptimizer_rules_PushDownSemiAntiJoin PushDownSemiAntiJoin.cpp PushDownSemiAntiJoin.hpp)
@@ -32,7 +33,6 @@ add_library(quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
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_TransformFilterJoins TransformFilterJoins.cpp TransformFilterJoins.hpp)
add_library(quickstep_queryoptimizer_rules_UpdateExpression UpdateExpression.cpp UpdateExpression.hpp)
add_library(quickstep_queryoptimizer_rules_UnnestSubqueries UnnestSubqueries.cpp UnnestSubqueries.hpp)
@@ -161,11 +161,13 @@ target_link_libraries(quickstep_queryoptimizer_rules_SwapProbeBuild
target_link_libraries(quickstep_queryoptimizer_rules_TopDownRule
quickstep_queryoptimizer_rules_Rule
quickstep_utility_Macros)
-target_link_libraries(quickstep_queryoptimizer_rules_TransformFilterJoins
+target_link_libraries(quickstep_queryoptimizer_rules_InjectJoinFilters
quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_ExprId
+ quickstep_queryoptimizer_expressions_ExpressionUtil
quickstep_queryoptimizer_physical_Aggregate
+ quickstep_queryoptimizer_physical_FilterInjection
quickstep_queryoptimizer_physical_HashJoin
quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_PatternMatcher
@@ -174,6 +176,8 @@ target_link_libraries(quickstep_queryoptimizer_rules_TransformFilterJoins
quickstep_queryoptimizer_physical_Selection
quickstep_queryoptimizer_physical_TopLevelPlan
quickstep_queryoptimizer_rules_Rule
+ quickstep_queryoptimizer_rules_PruneColumns
+ quickstep_types_TypeID
quickstep_types_TypedValue
quickstep_utility_Macros
quickstep_utility_lipfilter_LIPFilter)
@@ -227,6 +231,7 @@ target_link_libraries(quickstep_queryoptimizer_rules
quickstep_queryoptimizer_rules_BottomUpRule
quickstep_queryoptimizer_rules_CollapseProject
quickstep_queryoptimizer_rules_GenerateJoins
+ quickstep_queryoptimizer_rules_InjectJoinFilters
quickstep_queryoptimizer_rules_PruneColumns
quickstep_queryoptimizer_rules_PushDownFilter
quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
@@ -235,6 +240,5 @@ target_link_libraries(quickstep_queryoptimizer_rules
quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
quickstep_queryoptimizer_rules_SwapProbeBuild
quickstep_queryoptimizer_rules_TopDownRule
- quickstep_queryoptimizer_rules_TransformFilterJoins
quickstep_queryoptimizer_rules_UpdateExpression
quickstep_queryoptimizer_rules_UnnestSubqueries)
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6f941122/query_optimizer/rules/InjectJoinFilters.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/InjectJoinFilters.cpp b/query_optimizer/rules/InjectJoinFilters.cpp
new file mode 100644
index 0000000..6c9c71d
--- /dev/null
+++ b/query_optimizer/rules/InjectJoinFilters.cpp
@@ -0,0 +1,386 @@
+/**
+ * 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/InjectJoinFilters.hpp"
+
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/physical/LIPFilterConfiguration.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
+#include "query_optimizer/physical/FilterInjection.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/Selection.hpp"
+#include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/rules/PruneColumns.hpp"
+#include "types/TypeID.hpp"
+#include "types/TypedValue.hpp"
+#include "utility/lip_filter/LIPFilter.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace P = ::quickstep::optimizer::physical;
+
+P::PhysicalPtr InjectJoinFilters::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()));
+ lip_filter_configuration_.reset(new P::LIPFilterConfiguration());
+
+ P::PhysicalPtr output = transformHashJoinToFilters(input);
+ output = pushDownFilters(output);
+ output = addFilterAnchors(output, false);
+ output = PruneColumns().apply(output);
+
+ concretizeAsLIPFilters(output, nullptr);
+
+ if (!lip_filter_configuration_->getBuildInfoMap().empty() ||
+ !lip_filter_configuration_->getProbeInfoMap().empty()) {
+ output = std::static_pointer_cast<const P::TopLevelPlan>(output)
+ ->copyWithLIPFilterConfiguration(
+ P::LIPFilterConfigurationPtr(lip_filter_configuration_.release()));
+ }
+
+ return output;
+}
+
+bool InjectJoinFilters::isTransformable(
+ const physical::HashJoinPtr &hash_join) const {
+ if (hash_join->residual_predicate() != nullptr) {
+ return false;
+ }
+ if (hash_join->right_join_attributes().size() > 1) {
+ return false;
+ }
+ if (!E::SubsetOfExpressions(hash_join->getOutputAttributes(),
+ hash_join->left()->getOutputAttributes())) {
+ return false;
+ }
+ switch (hash_join->join_type()) {
+ case P::HashJoin::JoinType::kInnerJoin: {
+ if (!cost_model_->impliesUniqueAttributes(hash_join->right(),
+ hash_join->right_join_attributes())) {
+ return false;
+ }
+ break;
+ }
+ case P::HashJoin::JoinType::kLeftSemiJoin: // Fall through
+ case P::HashJoin::JoinType::kLeftAntiJoin:
+ break;
+ default:
+ return false;
+ }
+
+ std::int64_t min_cpp_value;
+ std::int64_t max_cpp_value;
+ const bool has_min_max_stats =
+ findMinMaxValuesForAttributeHelper(hash_join->right(),
+ hash_join->right_join_attributes().front(),
+ &min_cpp_value,
+ &max_cpp_value);
+ if (!has_min_max_stats) {
+ return false;
+ }
+
+ // TODO(jianqiao): implement SimpleHashSetExactFilter to relax this requirement.
+ // 1G bits = 128MB
+ if (min_cpp_value < 0 || max_cpp_value > kMaxFilterSize) {
+ return false;
+ }
+
+ return true;
+}
+
+P::PhysicalPtr InjectJoinFilters::transformHashJoinToFilters(
+ const P::PhysicalPtr &input) const {
+ std::vector<P::PhysicalPtr> new_children;
+ bool has_changed_children = false;
+ for (const P::PhysicalPtr &child : input->children()) {
+ const P::PhysicalPtr new_child = transformHashJoinToFilters(child);
+ if (child != new_child && !has_changed_children) {
+ has_changed_children = true;
+ }
+ new_children.push_back(new_child);
+ }
+
+ P::HashJoinPtr hash_join;
+ if (P::SomeHashJoin::MatchesWithConditionalCast(input, &hash_join) &&
+ isTransformable(hash_join)) {
+ const bool is_anti_join =
+ hash_join->join_type() == P::HashJoin::JoinType::kLeftAntiJoin;
+ return P::FilterInjection::Create(new_children[0],
+ new_children[1],
+ hash_join->left_join_attributes(),
+ hash_join->right_join_attributes(),
+ hash_join->project_expressions(),
+ is_anti_join);
+ }
+
+ if (has_changed_children) {
+ return input->copyWithNewChildren(new_children);
+ } else {
+ return input;
+ }
+}
+
+physical::PhysicalPtr InjectJoinFilters::pushDownFilters(
+ const physical::PhysicalPtr &input) const {
+ std::vector<P::PhysicalPtr> new_children;
+ bool has_changed_children = false;
+ for (const P::PhysicalPtr &child : input->children()) {
+ const P::PhysicalPtr new_child = pushDownFilters(child);
+ if (child != new_child && !has_changed_children) {
+ has_changed_children = true;
+ }
+ new_children.push_back(new_child);
+ }
+
+ P::FilterInjectionPtr filter_injection;
+ if (P::SomeFilterInjection::MatchesWithConditionalCast(input, &filter_injection)) {
+ DCHECK_EQ(2u, new_children.size());
+ return pushDownFiltersInternal(
+ new_children[0], new_children[1], filter_injection);
+ }
+
+ if (has_changed_children) {
+ return input->copyWithNewChildren(new_children);
+ } else {
+ return input;
+ }
+}
+
+physical::PhysicalPtr InjectJoinFilters::pushDownFiltersInternal(
+ const physical::PhysicalPtr &probe_child,
+ const physical::PhysicalPtr &build_child,
+ const physical::FilterInjectionPtr &filter_injection) const {
+ switch (probe_child->getPhysicalType()) {
+ case P::PhysicalType::kAggregate: // Fall through
+ case P::PhysicalType::kHashJoin:
+ case P::PhysicalType::kSample:
+ case P::PhysicalType::kSelection:
+ case P::PhysicalType::kSort:
+ case P::PhysicalType::kWindowAggregate: {
+ DCHECK_GE(probe_child->getNumChildren(), 1u);
+ const P::PhysicalPtr child = probe_child->children()[0];
+ if (E::SubsetOfExpressions(filter_injection->probe_attributes(),
+ child->getOutputAttributes())) {
+ const P::PhysicalPtr new_child =
+ pushDownFiltersInternal(child, build_child, filter_injection);
+ if (new_child != child) {
+ std::vector<P::PhysicalPtr> new_children = probe_child->children();
+ new_children[0] = new_child;
+ return probe_child->copyWithNewChildren(new_children);
+ }
+ }
+ }
+ default:
+ break;
+ }
+
+ if (probe_child != filter_injection->left()) {
+ // TODO(jianqiao): may need to update probe_attributes.
+ return P::FilterInjection::Create(probe_child,
+ build_child,
+ filter_injection->probe_attributes(),
+ filter_injection->build_attributes(),
+ E::ToNamedExpressions(probe_child->getOutputAttributes()),
+ filter_injection->is_anti_filter());
+ } else {
+ return filter_injection;
+ }
+}
+
+
+physical::PhysicalPtr InjectJoinFilters::addFilterAnchors(
+ const physical::PhysicalPtr &input,
+ const bool ancestor_can_anchor_filter) const {
+ std::vector<P::PhysicalPtr> new_children;
+
+ switch (input->getPhysicalType()) {
+ case P::PhysicalType::kAggregate: {
+ const P::AggregatePtr &aggregate =
+ std::static_pointer_cast<const P::Aggregate>(input);
+ new_children.emplace_back(
+ addFilterAnchors(aggregate->input(), true));
+ break;
+ }
+ case P::PhysicalType::kSelection: {
+ const P::SelectionPtr &selection =
+ std::static_pointer_cast<const P::Selection>(input);
+ new_children.emplace_back(
+ addFilterAnchors(selection->input(), true));
+ break;
+ }
+// case P::PhysicalType::kHashJoin: {
+// const P::HashJoinPtr &hash_join =
+// std::static_pointer_cast<const P::HashJoin>(input);
+// new_children.emplace_back(
+// addFilterAnchors(hash_join->left(), true));
+// new_children.emplace_back(
+// addFilterAnchors(hash_join->right(), false));
+// break;
+// }
+ case P::PhysicalType::kFilterInjection: {
+ const P::FilterInjectionPtr &filter_injection =
+ std::static_pointer_cast<const P::FilterInjection>(input);
+ new_children.emplace_back(
+ addFilterAnchors(filter_injection->left(), true));
+ new_children.emplace_back(
+ addFilterAnchors(filter_injection->right(), true));
+ break;
+ }
+ default: {
+ for (const P::PhysicalPtr &child : input->children()) {
+ new_children.emplace_back(addFilterAnchors(child, false));
+ }
+ }
+ }
+
+ DCHECK_EQ(new_children.size(), input->children().size());
+ const P::PhysicalPtr output_with_new_children =
+ new_children == input->children()
+ ? input
+ : input->copyWithNewChildren(new_children);
+
+ if (input->getPhysicalType() == P::PhysicalType::kFilterInjection &&
+ !ancestor_can_anchor_filter) {
+ const P::FilterInjectionPtr &filter_injection =
+ std::static_pointer_cast<const P::FilterInjection>(output_with_new_children);
+ return P::Selection::Create(filter_injection,
+ filter_injection->project_expressions(),
+ nullptr);
+ } else {
+ return output_with_new_children;
+ }
+}
+
+void InjectJoinFilters::concretizeAsLIPFilters(
+ const P::PhysicalPtr &input,
+ const P::PhysicalPtr &anchor_node) const {
+ switch (input->getPhysicalType()) {
+ case P::PhysicalType::kAggregate: {
+ const P::AggregatePtr &aggregate =
+ std::static_pointer_cast<const P::Aggregate>(input);
+ concretizeAsLIPFilters(aggregate->input(), aggregate);
+ break;
+ }
+ case P::PhysicalType::kSelection: {
+ const P::SelectionPtr &selection =
+ std::static_pointer_cast<const P::Selection>(input);
+ concretizeAsLIPFilters(selection->input(), selection);
+ break;
+ }
+// case P::PhysicalType::kHashJoin: {
+// const P::HashJoinPtr &hash_join =
+// std::static_pointer_cast<const P::HashJoin>(input);
+// concretizeAsLIPFilters(hash_join->left(), hash_join);
+// concretizeAsLIPFilters(hash_join->right(), nullptr);
+// break;
+// }
+ case P::PhysicalType::kFilterInjection: {
+ const P::FilterInjectionPtr &filter_injection =
+ std::static_pointer_cast<const P::FilterInjection>(input);
+ DCHECK_EQ(1u, filter_injection->build_attributes().size());
+ const E::AttributeReferencePtr &build_attr =
+ filter_injection->build_attributes().front();
+
+ std::int64_t min_cpp_value;
+ std::int64_t max_cpp_value;
+ const bool has_min_max_stats =
+ findMinMaxValuesForAttributeHelper(filter_injection,
+ build_attr,
+ &min_cpp_value,
+ &max_cpp_value);
+ DCHECK(has_min_max_stats);
+ DCHECK_GE(min_cpp_value, 0);
+ DCHECK_GE(max_cpp_value, 0);
+ DCHECK_LE(max_cpp_value, kMaxFilterSize);
+ CHECK(anchor_node != nullptr);
+
+ lip_filter_configuration_->addBuildInfo(
+ build_attr,
+ filter_injection,
+ static_cast<std::size_t>(max_cpp_value),
+ LIPFilterType::kBitVectorExactFilter,
+ filter_injection->is_anti_filter());
+ lip_filter_configuration_->addProbeInfo(
+ filter_injection->probe_attributes().front(),
+ anchor_node,
+ build_attr,
+ filter_injection);
+
+ concretizeAsLIPFilters(filter_injection->left(), anchor_node);
+ concretizeAsLIPFilters(filter_injection->right(), filter_injection);
+ break;
+ }
+ default: {
+ for (const P::PhysicalPtr &child : input->children()) {
+ concretizeAsLIPFilters(child, nullptr);
+ }
+ }
+ }
+}
+
+bool InjectJoinFilters::findMinMaxValuesForAttributeHelper(
+ const physical::PhysicalPtr &physical_plan,
+ const expressions::AttributeReferencePtr &attribute,
+ std::int64_t *min_cpp_value,
+ std::int64_t *max_cpp_value) const {
+ const TypedValue min_value =
+ cost_model_->findMinValueStat(physical_plan, attribute);
+ const TypedValue max_value =
+ cost_model_->findMaxValueStat(physical_plan, attribute);
+ if (min_value.isNull() || max_value.isNull()) {
+ return false;
+ }
+
+ switch (attribute->getValueType().getTypeID()) {
+ case TypeID::kInt: {
+ *min_cpp_value = min_value.getLiteral<int>();
+ *max_cpp_value = max_value.getLiteral<int>();
+ return true;
+ }
+ case TypeID::kLong: {
+ *min_cpp_value = min_value.getLiteral<std::int64_t>();
+ *max_cpp_value = max_value.getLiteral<std::int64_t>();
+ return true;
+ }
+ default:
+ return false;
+ }
+}
+
+
+} // namespace optimizer
+} // namespace quickstep