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/09/20 21:19:38 UTC
incubator-quickstep git commit: Generator updates
Repository: incubator-quickstep
Updated Branches:
refs/heads/lip-refactor 967459e8b -> d4be71eea
Generator updates
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/d4be71ee
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/d4be71ee
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/d4be71ee
Branch: refs/heads/lip-refactor
Commit: d4be71eea4904ef692b220cbcd03e4757e9f00bb
Parents: 967459e
Author: Jianqiao Zhu <ji...@cs.wisc.edu>
Authored: Tue Sep 20 16:19:30 2016 -0500
Committer: Jianqiao Zhu <ji...@cs.wisc.edu>
Committed: Tue Sep 20 16:19:30 2016 -0500
----------------------------------------------------------------------
query_execution/CMakeLists.txt | 7 +-
query_execution/QueryContext.cpp | 30 ++--
query_execution/QueryContext.hpp | 148 ++++++++++++-------
query_execution/QueryContext.proto | 25 ++--
query_optimizer/CMakeLists.txt | 18 ++-
query_optimizer/ExecutionGenerator.cpp | 15 ++
query_optimizer/ExecutionGenerator.hpp | 4 +
query_optimizer/LIPFilterGenerator.cpp | 55 +++++++
query_optimizer/LIPFilterGenerator.hpp | 82 +++++++++-
query_optimizer/physical/CMakeLists.txt | 9 +-
.../physical/LIPFilterConfiguration.hpp | 3 +-
query_optimizer/rules/AttachLIPFilters.cpp | 2 +-
query_optimizer/rules/CMakeLists.txt | 4 +-
utility/CMakeLists.txt | 11 +-
utility/DAG.hpp | 6 +-
utility/LIPFilter.cpp | 24 ---
utility/LIPFilter.hpp | 44 ------
utility/LIPFilterAdapter.hpp | 0
utility/LIPFilterBuilder.hpp | 0
utility/lip_filter/CMakeLists.txt | 49 ++++++
utility/lip_filter/LIPFilter.cpp | 24 +++
utility/lip_filter/LIPFilter.hpp | 57 +++++++
utility/lip_filter/LIPFilter.proto | 53 +++++++
utility/lip_filter/LIPFilterAdaptiveProber.hpp | 87 +++++++++++
utility/lip_filter/LIPFilterBuilder.hpp | 72 +++++++++
utility/lip_filter/LIPFilterDeploymentInfo.hpp | 70 +++++++++
utility/lip_filter/LIPFilterFactory.cpp | 0
utility/lip_filter/LIPFilterFactory.hpp | 47 ++++++
28 files changed, 775 insertions(+), 171 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_execution/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_execution/CMakeLists.txt b/query_execution/CMakeLists.txt
index 1b27194..58e5761 100644
--- a/query_execution/CMakeLists.txt
+++ b/query_execution/CMakeLists.txt
@@ -189,11 +189,11 @@ target_link_libraries(quickstep_queryexecution_QueryContext
quickstep_storage_WindowAggregationOperationState
quickstep_types_TypedValue
quickstep_types_containers_Tuple
- quickstep_utility_BloomFilter
quickstep_utility_Macros
- quickstep_utility_SortConfiguration)
+ quickstep_utility_SortConfiguration
+ quickstep_utility_lipfilter_LIPFilter
+ quickstep_utility_lipfilter_LIPFilterDeploymentInfo)
target_link_libraries(quickstep_queryexecution_QueryContext_proto
- quickstep_utility_BloomFilter_proto
quickstep_expressions_Expressions_proto
quickstep_expressions_tablegenerator_GeneratorFunction_proto
quickstep_storage_AggregationOperationState_proto
@@ -202,6 +202,7 @@ target_link_libraries(quickstep_queryexecution_QueryContext_proto
quickstep_storage_WindowAggregationOperationState_proto
quickstep_types_containers_Tuple_proto
quickstep_utility_SortConfiguration_proto
+ quickstep_utility_lipfilter_LIPFilter_proto
${PROTOBUF_LIBRARY})
target_link_libraries(quickstep_queryexecution_QueryExecutionMessages_proto
quickstep_catalog_Catalog_proto
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_execution/QueryContext.cpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryContext.cpp b/query_execution/QueryContext.cpp
index 2572e18..1a1b296 100644
--- a/query_execution/QueryContext.cpp
+++ b/query_execution/QueryContext.cpp
@@ -39,7 +39,7 @@
#include "storage/InsertDestination.pb.h"
#include "types/TypedValue.hpp"
#include "types/containers/Tuple.hpp"
-#include "utility/BloomFilter.hpp"
+#include "utility/lip_filter/LIPFilter.hpp"
#include "utility/SortConfiguration.hpp"
#include "glog/logging.h"
@@ -68,9 +68,9 @@ QueryContext::QueryContext(const serialization::QueryContext &proto,
storage_manager));
}
- for (int i = 0; i < proto.bloom_filters_size(); ++i) {
- bloom_filters_.emplace_back(new BloomFilter(proto.bloom_filters(i)));
- }
+// for (int i = 0; i < proto.bloom_filters_size(); ++i) {
+// bloom_filters_.emplace_back(new BloomFilter(proto.bloom_filters(i)));
+// }
for (int i = 0; i < proto.generator_functions_size(); ++i) {
const GeneratorFunctionHandle *func_handle =
@@ -80,12 +80,12 @@ QueryContext::QueryContext(const serialization::QueryContext &proto,
std::unique_ptr<const GeneratorFunctionHandle>(func_handle));
}
- for (int i = 0; i < proto.join_hash_tables_size(); ++i) {
- join_hash_tables_.emplace_back(
- JoinHashTableFactory::CreateResizableFromProto(proto.join_hash_tables(i),
- storage_manager,
- bloom_filters_));
- }
+// for (int i = 0; i < proto.join_hash_tables_size(); ++i) {
+// join_hash_tables_.emplace_back(
+// JoinHashTableFactory::CreateResizableFromProto(proto.join_hash_tables(i),
+// storage_manager,
+// bloom_filters_));
+// }
for (int i = 0; i < proto.insert_destinations_size(); ++i) {
const serialization::InsertDestination &insert_destination_proto = proto.insert_destinations(i);
@@ -157,11 +157,11 @@ bool QueryContext::ProtoIsValid(const serialization::QueryContext &proto,
}
}
- for (int i = 0; i < proto.bloom_filters_size(); ++i) {
- if (!BloomFilter::ProtoIsValid(proto.bloom_filters(i))) {
- return false;
- }
- }
+// for (int i = 0; i < proto.bloom_filters_size(); ++i) {
+// if (!BloomFilter::ProtoIsValid(proto.bloom_filters(i))) {
+// return false;
+// }
+// }
// Each GeneratorFunctionHandle object is serialized as a function name with
// a list of arguments. Here checks that the arguments are valid TypedValue's.
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_execution/QueryContext.hpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryContext.hpp b/query_execution/QueryContext.hpp
index 393b55e..3e287c0 100644
--- a/query_execution/QueryContext.hpp
+++ b/query_execution/QueryContext.hpp
@@ -35,7 +35,8 @@
#include "storage/InsertDestination.hpp"
#include "storage/WindowAggregationOperationState.hpp"
#include "types/containers/Tuple.hpp"
-#include "utility/BloomFilter.hpp"
+#include "utility/lip_filter/LIPFilter.hpp"
+#include "utility/lip_filter/LIPFilterDeploymentInfo.hpp"
#include "utility/Macros.hpp"
#include "utility/SortConfiguration.hpp"
@@ -67,11 +68,6 @@ class QueryContext {
typedef std::uint32_t aggregation_state_id;
/**
- * @brief A unique identifier for a BloomFilter per query.
- **/
- typedef std::uint32_t bloom_filter_id;
-
- /**
* @brief A unique identifier for a GeneratorFunctionHandle per query.
**/
typedef std::uint32_t generator_function_id;
@@ -90,6 +86,16 @@ class QueryContext {
typedef std::uint32_t join_hash_table_id;
/**
+ * @brief A unique identifier for a LIPFilter per query.
+ **/
+ typedef std::uint32_t lip_filter_id;
+
+ /**
+ * @brief A unique identifier for a LIPFilterDeploymentInfo per query.
+ **/
+ typedef std::uint32_t lip_filter_deployment_info_id;
+
+ /**
* @brief A unique identifier for a Predicate per query.
*
* @note A negative value indicates a null Predicate.
@@ -193,52 +199,6 @@ class QueryContext {
}
/**
- * @brief Whether the given BloomFilter id is valid.
- *
- * @param id The BloomFilter id.
- *
- * @return True if valid, otherwise false.
- **/
- bool isValidBloomFilterId(const bloom_filter_id id) const {
- return id < bloom_filters_.size();
- }
-
- /**
- * @brief Get a mutable reference to the BloomFilter.
- *
- * @param id The BloomFilter id.
- *
- * @return The BloomFilter, already created in the constructor.
- **/
- inline BloomFilter* getBloomFilterMutable(const bloom_filter_id id) {
- DCHECK_LT(id, bloom_filters_.size());
- return bloom_filters_[id].get();
- }
-
- /**
- * @brief Get a constant pointer to the BloomFilter.
- *
- * @param id The BloomFilter id.
- *
- * @return The constant pointer to BloomFilter that is
- * already created in the constructor.
- **/
- inline const BloomFilter* getBloomFilter(const bloom_filter_id id) const {
- DCHECK_LT(id, bloom_filters_.size());
- return bloom_filters_[id].get();
- }
-
- /**
- * @brief Destory the given BloomFilter.
- *
- * @param id The id of the BloomFilter to destroy.
- **/
- inline void destroyBloomFilter(const bloom_filter_id id) {
- DCHECK_LT(id, bloom_filters_.size());
- bloom_filters_[id].reset();
- }
-
- /**
* @brief Whether the given GeneratorFunctionHandle id is valid.
*
* @param id The GeneratorFunctionHandle id.
@@ -333,6 +293,87 @@ class QueryContext {
}
/**
+ * @brief Whether the given LIPFilter id is valid.
+ *
+ * @param id The LIPFilter id.
+ *
+ * @return True if valid, otherwise false.
+ **/
+ bool isValidLIPFilterId(const lip_filter_id id) const {
+ return id < lip_filters_.size();
+ }
+
+ /**
+ * @brief Get a mutable reference to the LIPFilter.
+ *
+ * @param id The LIPFilter id.
+ *
+ * @return The LIPFilter, already created in the constructor.
+ **/
+ inline LIPFilter* getLIPFilterMutable(const lip_filter_id id) {
+ DCHECK_LT(id, lip_filters_.size());
+ return lip_filters_[id].get();
+ }
+
+ /**
+ * @brief Get a constant pointer to the LIPFilter.
+ *
+ * @param id The LIPFilter id.
+ *
+ * @return The constant pointer to LIPFilter that is
+ * already created in the constructor.
+ **/
+ inline const LIPFilter* getLIPFilter(const lip_filter_id id) const {
+ DCHECK_LT(id, lip_filters_.size());
+ return lip_filters_[id].get();
+ }
+
+ /**
+ * @brief Destory the given LIPFilter.
+ *
+ * @param id The id of the LIPFilter to destroy.
+ **/
+ inline void destroyLIPFilter(const lip_filter_id id) {
+ DCHECK_LT(id, lip_filters_.size());
+ lip_filters_[id].reset();
+ }
+
+ /**
+ * @brief Whether the given LIPFilterDeploymentInfo id is valid.
+ *
+ * @param id The LIPFilterDeploymentInfo id.
+ *
+ * @return True if valid, otherwise false.
+ **/
+ bool isValidLIPFilterDeploymentInfoId(const lip_filter_deployment_info_id id) const {
+ return id < lip_filter_deployment_infos_.size();
+ }
+
+ /**
+ * @brief Get a constant pointer to the LIPFilterDeploymentInfo.
+ *
+ * @param id The LIPFilterDeploymentInfo id.
+ *
+ * @return The constant pointer to LIPFilterDeploymentInfo that is
+ * already created in the constructor.
+ **/
+ inline const LIPFilterDeploymentInfo* getLIPFilterDeploymentInfo(
+ const lip_filter_deployment_info_id id) const {
+ DCHECK_LT(id, lip_filter_deployment_infos_.size());
+ return lip_filter_deployment_infos_[id].get();
+ }
+
+ /**
+ * @brief Destory the given LIPFilterDeploymentInfo.
+ *
+ * @param id The id of the LIPFilterDeploymentInfo to destroy.
+ **/
+ inline void destroyLIPFilterDeploymentInfo(const lip_filter_deployment_info_id id) {
+ DCHECK_LT(id, lip_filter_deployment_infos_.size());
+ lip_filter_deployment_infos_[id].reset();
+ }
+
+ /**
* @brief Whether the given Predicate id is valid or no predicate.
*
* @param id The Predicate id.
@@ -507,10 +548,11 @@ class QueryContext {
private:
std::vector<std::unique_ptr<AggregationOperationState>> aggregation_states_;
- std::vector<std::unique_ptr<BloomFilter>> bloom_filters_;
std::vector<std::unique_ptr<const GeneratorFunctionHandle>> generator_functions_;
std::vector<std::unique_ptr<InsertDestination>> insert_destinations_;
std::vector<std::unique_ptr<JoinHashTable>> join_hash_tables_;
+ std::vector<std::unique_ptr<LIPFilter>> lip_filters_;
+ std::vector<std::unique_ptr<LIPFilterDeploymentInfo>> lip_filter_deployment_infos_;
std::vector<std::unique_ptr<const Predicate>> predicates_;
std::vector<std::vector<std::unique_ptr<const Scalar>>> scalar_groups_;
std::vector<std::unique_ptr<const SortConfiguration>> sort_configs_;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_execution/QueryContext.proto
----------------------------------------------------------------------
diff --git a/query_execution/QueryContext.proto b/query_execution/QueryContext.proto
index 1a586a4..d79b990 100644
--- a/query_execution/QueryContext.proto
+++ b/query_execution/QueryContext.proto
@@ -26,8 +26,8 @@ import "storage/HashTable.proto";
import "storage/InsertDestination.proto";
import "storage/WindowAggregationOperationState.proto";
import "types/containers/Tuple.proto";
-import "utility/BloomFilter.proto";
import "utility/SortConfiguration.proto";
+import "utility/lip_filter/LIPFilter.proto";
message QueryContext {
message ScalarGroup {
@@ -46,19 +46,20 @@ message QueryContext {
}
repeated AggregationOperationState aggregation_states = 1;
- repeated BloomFilter bloom_filters = 2;
- repeated GeneratorFunctionHandle generator_functions = 3;
- repeated HashTable join_hash_tables = 4;
- repeated InsertDestination insert_destinations = 5;
- repeated Predicate predicates = 6;
- repeated ScalarGroup scalar_groups = 7;
- repeated SortConfiguration sort_configs = 8;
- repeated Tuple tuples = 9;
+ repeated GeneratorFunctionHandle generator_functions = 2;
+ repeated HashTable join_hash_tables = 3;
+ repeated InsertDestination insert_destinations = 4;
+ repeated LIPFilter lip_filters = 5;
+ repeated LIPFilterDeploymentInfo lip_filter_deployment_infos = 6;
+ repeated Predicate predicates = 7;
+ repeated ScalarGroup scalar_groups = 8;
+ repeated SortConfiguration sort_configs = 9;
+ repeated Tuple tuples = 10;
// NOTE(zuyu): For UpdateWorkOrder only.
- repeated UpdateGroup update_groups = 10;
+ repeated UpdateGroup update_groups = 11;
- repeated WindowAggregationOperationState window_aggregation_states = 11;
+ repeated WindowAggregationOperationState window_aggregation_states = 12;
- required uint64 query_id = 12;
+ required uint64 query_id = 13;
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index 32eaea3..0cdfe34 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -41,7 +41,7 @@ add_subdirectory(tests)
# Declare micro-libs:
add_library(quickstep_queryoptimizer_ExecutionGenerator ExecutionGenerator.cpp ExecutionGenerator.hpp)
-add_library(quickstep_queryoptimizer_LIPFilterGenerator ../empty_src.cpp LIPFilterGenerator.hpp)
+add_library(quickstep_queryoptimizer_LIPFilterGenerator LIPFilterGenerator.cpp LIPFilterGenerator.hpp)
add_library(quickstep_queryoptimizer_LogicalGenerator LogicalGenerator.cpp LogicalGenerator.hpp)
add_library(quickstep_queryoptimizer_LogicalToPhysicalMapper
../empty_src.cpp
@@ -73,6 +73,7 @@ target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
quickstep_expressions_windowaggregation_WindowAggregateFunction_proto
quickstep_queryexecution_QueryContext
quickstep_queryexecution_QueryContext_proto
+ quickstep_queryoptimizer_LIPFilterGenerator
quickstep_queryoptimizer_OptimizerContext
quickstep_queryoptimizer_QueryHandle
quickstep_queryoptimizer_QueryPlan
@@ -152,8 +153,18 @@ if (ENABLE_DISTRIBUTED)
target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
quickstep_catalog_Catalog_proto)
endif()
-target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
- glog)
+target_link_libraries(quickstep_queryoptimizer_LIPFilterGenerator
+ glog
+ quickstep_catalog_CatalogAttribute
+ quickstep_catalog_CatalogTypeDefs
+ quickstep_queryexecution_QueryContext
+ quickstep_queryexecution_QueryContext_proto
+ quickstep_queryoptimizer_QueryPlan
+ quickstep_queryoptimizer_physical_Aggregate
+ quickstep_queryoptimizer_physical_HashJoin
+ quickstep_queryoptimizer_physical_LIPFilterConfiguration
+ quickstep_queryoptimizer_physical_Physical
+ quickstep_queryoptimizer_physical_Selection)
target_link_libraries(quickstep_queryoptimizer_LogicalGenerator
glog
quickstep_parser_ParseStatement
@@ -227,6 +238,7 @@ target_link_libraries(quickstep_queryoptimizer_Validator
add_library(quickstep_queryoptimizer ../empty_src.cpp QueryOptimizerModule.hpp)
target_link_libraries(quickstep_queryoptimizer
quickstep_queryoptimizer_ExecutionGenerator
+ quickstep_queryoptimizer_LIPFilterGenerator
quickstep_queryoptimizer_LogicalGenerator
quickstep_queryoptimizer_LogicalToPhysicalMapper
quickstep_queryoptimizer_Optimizer
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/ExecutionGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.cpp b/query_optimizer/ExecutionGenerator.cpp
index a9a4401..7bfa949 100644
--- a/query_optimizer/ExecutionGenerator.cpp
+++ b/query_optimizer/ExecutionGenerator.cpp
@@ -54,6 +54,7 @@
#include "expressions/window_aggregation/WindowAggregateFunction.pb.h"
#include "query_execution/QueryContext.hpp"
#include "query_execution/QueryContext.pb.h"
+#include "query_optimizer/LIPFilterGenerator.hpp"
#include "query_optimizer/OptimizerContext.hpp"
#include "query_optimizer/QueryHandle.hpp"
#include "query_optimizer/QueryPlan.hpp"
@@ -164,6 +165,8 @@ void ExecutionGenerator::generatePlan(const P::PhysicalPtr &physical_plan) {
cost_model_.reset(
new cost::SimpleCostModel(top_level_physical_plan_->shared_subplans()));
+ lip_filter_generator_.reset(
+ new LIPFilterGenerator(top_level_physical_plan_->lip_filter_configuration()));
const CatalogRelation *result_relation = nullptr;
@@ -229,6 +232,8 @@ void ExecutionGenerator::generatePlanInternal(
generatePlanInternal(child);
}
+ lip_filter_generator_->registerAttributeMap(physical_plan, attribute_substitution_map_);
+
switch (physical_plan->getPhysicalType()) {
case P::PhysicalType::kAggregate:
return convertAggregate(
@@ -560,6 +565,8 @@ void ExecutionGenerator::convertSelection(
std::forward_as_tuple(select_index,
output_relation));
temporary_relation_info_vec_.emplace_back(select_index, output_relation);
+
+ lip_filter_generator_->addSelectionInfo(physical_selection, select_index);
}
void ExecutionGenerator::convertSharedSubplanReference(const physical::SharedSubplanReferencePtr &physical_plan) {
@@ -819,6 +826,10 @@ void ExecutionGenerator::convertHashJoin(const P::HashJoinPtr &physical_plan) {
std::forward_as_tuple(join_operator_index,
output_relation));
temporary_relation_info_vec_.emplace_back(join_operator_index, output_relation);
+
+ lip_filter_generator_->addHashJoinInfo(physical_plan,
+ build_operator_index,
+ join_operator_index);
}
void ExecutionGenerator::convertNestedLoopsJoin(
@@ -1454,6 +1465,10 @@ void ExecutionGenerator::convertAggregate(
execution_plan_->addDirectDependency(destroy_aggregation_state_operator_index,
finalize_aggregation_operator_index,
true);
+
+ lip_filter_generator_->addAggregateInfo(physical_plan,
+ aggregation_operator_index,
+ aggr_state_index);
}
void ExecutionGenerator::convertSort(const P::SortPtr &physical_sort) {
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/ExecutionGenerator.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.hpp b/query_optimizer/ExecutionGenerator.hpp
index a830e65..a666f6d 100644
--- a/query_optimizer/ExecutionGenerator.hpp
+++ b/query_optimizer/ExecutionGenerator.hpp
@@ -33,6 +33,7 @@
#include "catalog/CatalogTypedefs.hpp"
#include "query_execution/QueryContext.hpp"
#include "query_execution/QueryContext.pb.h"
+#include "query_optimizer/LIPFilterGenerator.hpp"
#include "query_optimizer/QueryHandle.hpp"
#include "query_optimizer/QueryPlan.hpp"
#include "query_optimizer/cost_model/CostModel.hpp"
@@ -423,6 +424,9 @@ class ExecutionGenerator {
physical::TopLevelPlanPtr top_level_physical_plan_;
+ // Sub-generator for deploying LIP (lookahead information passing) filters.
+ std::unique_ptr<LIPFilterGenerator> lip_filter_generator_;
+
DISALLOW_COPY_AND_ASSIGN(ExecutionGenerator);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/LIPFilterGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/LIPFilterGenerator.cpp b/query_optimizer/LIPFilterGenerator.cpp
new file mode 100644
index 0000000..823bd69
--- /dev/null
+++ b/query_optimizer/LIPFilterGenerator.cpp
@@ -0,0 +1,55 @@
+/**
+ * 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/LIPFilterGenerator.hpp"
+
+#include "catalog/CatalogAttribute.hpp"
+#include "catalog/CatalogTypeDefs.hpp"
+
+namespace quickstep {
+namespace optimizer {
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace P = ::quickstep::optimizer::physical;
+
+void LIPFilterGenerator::registerAttributeMap(
+ const P::PhysicalPtr &node,
+ const std::unordered_map<E::ExprId, const CatalogAttribute *> &attribute_substitution_map) {
+ const auto &build_infos = lip_filter_configuration_->getBuildInfo();
+ const auto build_it = build_infos.find(node);
+ if (build_it != build_infos.end()) {
+ auto &map_entry = attribute_map_[node];
+ for (const auto &info : build_it->second) {
+ E::ExprId attr_id = info.build_attribute->id();
+ map_entry.emplace(attr_id, attribute_substitution_map.at(attr_id)->getID());
+ }
+ }
+ const auto &probe_infos = lip_filter_configuration_->getProbeInfo();
+ const auto probe_it = probe_infos.find(node);
+ if (probe_it != probe_infos.end()) {
+ auto &map_entry = attribute_map_[node];
+ for (const auto &info : probe_it->second) {
+ E::ExprId attr_id = info.probe_attribute->id();
+ map_entry.emplace(attr_id, attribute_substitution_map.at(attr_id)->getID());
+ }
+ }
+}
+
+} // namespace optimizer
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/LIPFilterGenerator.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/LIPFilterGenerator.hpp b/query_optimizer/LIPFilterGenerator.hpp
index 4137b98..09f5ac5 100644
--- a/query_optimizer/LIPFilterGenerator.hpp
+++ b/query_optimizer/LIPFilterGenerator.hpp
@@ -20,7 +20,24 @@
#ifndef QUICKSTEP_QUERY_OPTIMIZER_LIP_FILTER_GENERATOR_HPP_
#define QUICKSTEP_QUERY_OPTIMIZER_LIP_FILTER_GENERATOR_HPP_
+#include <map>
+#include <unordered_map>
+
+#include "catalog/CatalogTypeDefs.hpp"
+#include "query_execution/QueryContext.hpp"
+#include "query_execution/QueryContext.pb.h"
+#include "query_optimizer/QueryPlan.hpp"
+#include "query_optimizer/physical/LIPFilterConfiguration.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
+#include "query_optimizer/physical/HashJoin.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/Selection.hpp"
+
+
namespace quickstep {
+
+class CatalogAttribute;
+
namespace optimizer {
/** \addtogroup QueryOptimizer
@@ -29,12 +46,75 @@ namespace optimizer {
class LIPFilterGenerator {
public:
-
+ LIPFilterGenerator(const physical::LIPFilterConfigurationPtr &lip_filter_configuration)
+ : lip_filter_configuration_(lip_filter_configuration) {
+ }
+ void registerAttributeMap(
+ const physical::PhysicalPtr &node,
+ const std::unordered_map<expressions::ExprId, const CatalogAttribute *> &attribute_substitution_map);
+
+ void addAggregateInfo(const physical::AggregatePtr &aggregate,
+ const QueryPlan::DAGNodeIndex aggregate_operator_index,
+ const QueryContext::aggregation_state_id aggregation_state_id) {
+ aggregate_infos_.emplace_back(aggregate, aggregate_operator_index, aggregation_state_id);
+ }
+
+ void addHashJoinInfo(const physical::HashJoinPtr &hash_join,
+ const QueryPlan::DAGNodeIndex build_operator_index,
+ const QueryPlan::DAGNodeIndex join_operator_index) {
+ builder_op_index_map_.emplace(hash_join, build_operator_index);
+ hash_join_infos_.emplace_back(hash_join, build_operator_index, join_operator_index);
+ }
+
+ void addSelectionInfo(const physical::SelectionPtr &selection,
+ const QueryPlan::DAGNodeIndex select_operator_index) {
+ selection_infos_.emplace_back(selection, select_operator_index);
+ }
private:
+ struct AggregateInfo {
+ AggregateInfo(const physical::AggregatePtr &aggregate_in,
+ const QueryPlan::DAGNodeIndex aggregate_operator_index_in,
+ const QueryContext::aggregation_state_id aggregation_state_id_in)
+ : aggregate(aggregate_in),
+ aggregate_operator_index(aggregate_operator_index_in),
+ aggregation_state_id(aggregation_state_id_in) {
+ }
+ const physical::AggregatePtr aggregate;
+ const QueryPlan::DAGNodeIndex aggregate_operator_index;
+ const QueryContext::aggregation_state_id aggregation_state_id;
+ };
+
+ struct HashJoinInfo {
+ HashJoinInfo(const physical::HashJoinPtr &hash_join_in,
+ const QueryPlan::DAGNodeIndex build_operator_index_in,
+ const QueryPlan::DAGNodeIndex join_operator_index_in)
+ : hash_join(hash_join_in),
+ build_operator_index(build_operator_index_in),
+ join_operator_index(join_operator_index_in) {
+ }
+ const physical::HashJoinPtr hash_join;
+ const QueryPlan::DAGNodeIndex build_operator_index;
+ const QueryPlan::DAGNodeIndex join_operator_index;
+ };
+ struct SelectionInfo {
+ SelectionInfo(const physical::SelectionPtr &selection_in,
+ const QueryPlan::DAGNodeIndex select_operator_index_in)
+ : selection(selection_in),
+ select_operator_index(select_operator_index_in) {
+ }
+ const physical::SelectionPtr selection;
+ const QueryPlan::DAGNodeIndex select_operator_index;
+ };
+ const physical::LIPFilterConfigurationPtr lip_filter_configuration_;
+ std::map<physical::PhysicalPtr, std::map<expressions::ExprId, attribute_id>> attribute_map_;
+ std::map<physical::PhysicalPtr, QueryPlan::DAGNodeIndex> builder_op_index_map_;
+ std::vector<AggregateInfo> aggregate_infos_;
+ std::vector<HashJoinInfo> hash_join_infos_;
+ std::vector<SelectionInfo> selection_infos_;
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/physical/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/CMakeLists.txt b/query_optimizer/physical/CMakeLists.txt
index 83682b3..5c2cd0b 100644
--- a/query_optimizer/physical/CMakeLists.txt
+++ b/query_optimizer/physical/CMakeLists.txt
@@ -52,7 +52,6 @@ target_link_libraries(quickstep_queryoptimizer_physical_Aggregate
quickstep_queryoptimizer_expressions_ExpressionUtil
quickstep_queryoptimizer_expressions_NamedExpression
quickstep_queryoptimizer_expressions_Predicate
- quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_physical_PhysicalType
quickstep_utility_Cast
@@ -123,7 +122,6 @@ target_link_libraries(quickstep_queryoptimizer_physical_HashJoin
quickstep_queryoptimizer_expressions_NamedExpression
quickstep_queryoptimizer_expressions_Predicate
quickstep_queryoptimizer_physical_BinaryJoin
- quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_physical_PhysicalType
quickstep_utility_Cast
@@ -155,8 +153,8 @@ target_link_libraries(quickstep_queryoptimizer_physical_Join
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_expressions_AttributeReference
- quickstep_utility_LIPFilter
- quickstep_utility_Macros)
+ quickstep_utility_Macros
+ quickstep_utility_lipfilter_LIPFilter)
target_link_libraries(quickstep_queryoptimizer_physical_NestedLoopsJoin
glog
quickstep_queryoptimizer_OptimizerTree
@@ -174,7 +172,6 @@ target_link_libraries(quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_OptimizerTree
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_ExpressionUtil
- quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_PhysicalType
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_physical_Sample
@@ -195,7 +192,6 @@ target_link_libraries(quickstep_queryoptimizer_physical_Selection
quickstep_queryoptimizer_expressions_LogicalAnd
quickstep_queryoptimizer_expressions_NamedExpression
quickstep_queryoptimizer_expressions_Predicate
- quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_physical_PhysicalType
quickstep_utility_Cast
@@ -246,6 +242,7 @@ target_link_libraries(quickstep_queryoptimizer_physical_TopLevelPlan
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_ExprId
quickstep_queryoptimizer_expressions_ExpressionUtil
+ quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_physical_PhysicalType
quickstep_utility_Cast
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/physical/LIPFilterConfiguration.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/LIPFilterConfiguration.hpp b/query_optimizer/physical/LIPFilterConfiguration.hpp
index 59db2e6..153d677 100644
--- a/query_optimizer/physical/LIPFilterConfiguration.hpp
+++ b/query_optimizer/physical/LIPFilterConfiguration.hpp
@@ -26,7 +26,7 @@
#include <vector>
#include "query_optimizer/expressions/AttributeReference.hpp"
-#include "utility/LIPFilter.hpp"
+#include "utility/lip_filter/LIPFilter.hpp"
#include "utility/Macros.hpp"
#include "glog/logging.h"
@@ -64,7 +64,6 @@ struct LIPFilterProbeInfo {
builder(builder_in) {
}
expressions::AttributeReferencePtr probe_attribute;
- PhysicalPtr target;
expressions::AttributeReferencePtr build_attribute;
PhysicalPtr builder;
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/rules/AttachLIPFilters.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/AttachLIPFilters.cpp b/query_optimizer/rules/AttachLIPFilters.cpp
index 5493e00..e79c883 100644
--- a/query_optimizer/rules/AttachLIPFilters.cpp
+++ b/query_optimizer/rules/AttachLIPFilters.cpp
@@ -39,7 +39,7 @@
#include "query_optimizer/physical/Physical.hpp"
#include "query_optimizer/physical/PhysicalType.hpp"
#include "query_optimizer/physical/TopLevelPlan.hpp"
-#include "utility/LIPFilter.hpp"
+#include "utility/lip_filter/LIPFilter.hpp"
#include "glog/logging.h"
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/query_optimizer/rules/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CMakeLists.txt b/query_optimizer/rules/CMakeLists.txt
index 9dc6118..f042ba8 100644
--- a/query_optimizer/rules/CMakeLists.txt
+++ b/query_optimizer/rules/CMakeLists.txt
@@ -45,12 +45,14 @@ target_link_libraries(quickstep_queryoptimizer_rules_AttachLIPFilters
quickstep_queryoptimizer_expressions_PatternMatcher
quickstep_queryoptimizer_expressions_Predicate
quickstep_queryoptimizer_physical_HashJoin
+ quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_PatternMatcher
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_physical_PhysicalType
quickstep_queryoptimizer_physical_TopLevelPlan
quickstep_queryoptimizer_rules_Rule
- quickstep_utility_Macros)
+ quickstep_utility_Macros
+ quickstep_utility_lipfilter_LIPFilter)
target_link_libraries(quickstep_queryoptimizer_rules_BottomUpRule
glog
quickstep_queryoptimizer_rules_Rule
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/utility/CMakeLists.txt b/utility/CMakeLists.txt
index 8a2c7ae..9025015 100644
--- a/utility/CMakeLists.txt
+++ b/utility/CMakeLists.txt
@@ -156,6 +156,8 @@ QS_PROTOBUF_GENERATE_CPP(quickstep_utility_SortConfiguration_proto_srcs
quickstep_utility_SortConfiguration_proto_hdrs
SortConfiguration.proto)
+add_subdirectory(lip_filter)
+
# Declare micro-libs:
add_library(quickstep_utility_Alignment ../empty_src.cpp Alignment.hpp)
add_library(quickstep_utility_BitManipulation ../empty_src.cpp BitManipulation.hpp)
@@ -174,7 +176,6 @@ add_library(quickstep_utility_ExecutionDAGVisualizer
ExecutionDAGVisualizer.hpp)
add_library(quickstep_utility_Glob Glob.cpp Glob.hpp)
add_library(quickstep_utility_HashPair ../empty_src.cpp HashPair.hpp)
-add_library(quickstep_utility_LIPFilter LIPFilter.cpp LIPFilter.hpp)
add_library(quickstep_utility_Macros ../empty_src.cpp Macros.hpp)
add_library(quickstep_utility_MemStream ../empty_src.cpp MemStream.hpp)
add_library(quickstep_utility_PlanVisualizer PlanVisualizer.cpp PlanVisualizer.hpp)
@@ -245,8 +246,6 @@ target_link_libraries(quickstep_utility_ExecutionDAGVisualizer
quickstep_utility_StringUtil)
target_link_libraries(quickstep_utility_Glob
glog)
-target_link_libraries(quickstep_utility_LIPFilter
- glog)
target_link_libraries(quickstep_utility_MemStream
glog
quickstep_utility_Macros)
@@ -254,11 +253,16 @@ target_link_libraries(quickstep_utility_PrimeNumber
glog)
target_link_libraries(quickstep_utility_PlanVisualizer
quickstep_catalog_CatalogRelation
+ quickstep_catalog_CatalogRelationStatistics
+ quickstep_catalog_CatalogTypedefs
quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
quickstep_queryoptimizer_expressions_AttributeReference
+ quickstep_queryoptimizer_physical_Aggregate
quickstep_queryoptimizer_physical_HashJoin
+ quickstep_queryoptimizer_physical_LIPFilterConfiguration
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_physical_PhysicalType
+ quickstep_queryoptimizer_physical_Selection
quickstep_queryoptimizer_physical_TableReference
quickstep_queryoptimizer_physical_TopLevelPlan
quickstep_utility_Macros
@@ -326,7 +330,6 @@ target_link_libraries(quickstep_utility
quickstep_utility_ExecutionDAGVisualizer
quickstep_utility_Glob
quickstep_utility_HashPair
- quickstep_utility_LIPFilter
quickstep_utility_Macros
quickstep_utility_MemStream
quickstep_utility_PlanVisualizer
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/DAG.hpp
----------------------------------------------------------------------
diff --git a/utility/DAG.hpp b/utility/DAG.hpp
index a1f2619..b35f2b5 100644
--- a/utility/DAG.hpp
+++ b/utility/DAG.hpp
@@ -293,8 +293,10 @@ class DAG {
* node at node_index.
**/
inline void addDependent(const size_type_nodes node_index, const LinkMetadataT &link_metadata) {
- DCHECK(dependents_with_metadata_.find(node_index) == dependents_with_metadata_.end());
- dependents_with_metadata_.emplace(node_index, link_metadata);
+// DCHECK(dependents_with_metadata_.find(node_index) == dependents_with_metadata_.end());
+// dependents_with_metadata_.emplace(node_index, link_metadata);
+ // TODO(jianqiao): implement upsert
+ dependents_with_metadata_[node_index] = link_metadata;
}
/**
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/LIPFilter.cpp
----------------------------------------------------------------------
diff --git a/utility/LIPFilter.cpp b/utility/LIPFilter.cpp
deleted file mode 100644
index f503f4f..0000000
--- a/utility/LIPFilter.cpp
+++ /dev/null
@@ -1,24 +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 "utility/LIPFilter.hpp"
-
-namespace quickstep {
-
-} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/LIPFilter.hpp
----------------------------------------------------------------------
diff --git a/utility/LIPFilter.hpp b/utility/LIPFilter.hpp
deleted file mode 100644
index 12a19d7..0000000
--- a/utility/LIPFilter.hpp
+++ /dev/null
@@ -1,44 +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_UTILITY_LIP_FILTER_HPP_
-#define QUICKSTEP_UTILITY_LIP_FILTER_HPP_
-
-#include <vector>
-
-#include "glog/logging.h"
-
-namespace quickstep {
-
-/** \addtogroup Utility
- * @{
- */
-
-enum class LIPFilterType {
- kBloomFilter,
- kExactFilter,
- kSingleIdentityHashFilter
-};
-
-
-/** @} */
-
-} // namespace quickstep
-
-#endif // QUICKSTEP_UTILITY_LIP_FILTER_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/LIPFilterAdapter.hpp
----------------------------------------------------------------------
diff --git a/utility/LIPFilterAdapter.hpp b/utility/LIPFilterAdapter.hpp
deleted file mode 100644
index e69de29..0000000
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/LIPFilterBuilder.hpp
----------------------------------------------------------------------
diff --git a/utility/LIPFilterBuilder.hpp b/utility/LIPFilterBuilder.hpp
deleted file mode 100644
index e69de29..0000000
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/utility/lip_filter/CMakeLists.txt b/utility/lip_filter/CMakeLists.txt
new file mode 100644
index 0000000..87a58e2
--- /dev/null
+++ b/utility/lip_filter/CMakeLists.txt
@@ -0,0 +1,49 @@
+# 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.
+
+QS_PROTOBUF_GENERATE_CPP(utility_lipfilter_LIPFilter_proto_srcs
+ utility_lipfilter_LIPFilter_proto_hdrs
+ LIPFilter.proto)
+
+# Declare micro-libs:
+add_library(quickstep_utility_lipfilter_LIPFilter LIPFilter.cpp LIPFilter.hpp)
+add_library(quickstep_utility_lipfilter_LIPFilterAdaptiveProber ../../empty_src.cpp LIPFilterAdaptiveProber.hpp)
+add_library(quickstep_utility_lipfilter_LIPFilterBuilder ../../empty_src.cpp LIPFilterBuilder.hpp)
+add_library(quickstep_utility_lipfilter_LIPFilterDeploymentInfo ../../empty_src.cpp LIPFilterDeploymentInfo.hpp)
+add_library(quickstep_utility_lipfilter_LIPFilterFactory LIPFilterFactory.cpp LIPFilterFactory.hpp)
+add_library(quickstep_utility_lipfilter_LIPFilter_proto
+ ${utility_lipfilter_LIPFilter_proto_srcs})
+
+# Link dependencies:
+target_link_libraries(quickstep_utility_lipfilter_LIPFilter
+ quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_lipfilter_LIPFilterAdaptiveProber
+ quickstep_catalog_CatalogTypeDefs
+ quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_lipfilter_LIPFilterBuilder
+ quickstep_catalog_CatalogTypeDefs
+ quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_lipfilter_LIPFilterDeploymentInfo
+ quickstep_catalog_CatalogTypeDefs
+ quickstep_utility_Macros
+ quickstep_utility_lipfilter_LIPFilter)
+target_link_libraries(quickstep_utility_lipfilter_LIPFilterFactory
+ quickstep_utility_lipfilter_LIPFilter_proto
+ quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_lipfilter_LIPFilter_proto
+ ${PROTOBUF_LIBRARY}
+ quickstep_types_Type_proto)
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/LIPFilter.cpp
----------------------------------------------------------------------
diff --git a/utility/lip_filter/LIPFilter.cpp b/utility/lip_filter/LIPFilter.cpp
new file mode 100644
index 0000000..92bfab1
--- /dev/null
+++ b/utility/lip_filter/LIPFilter.cpp
@@ -0,0 +1,24 @@
+/**
+ * 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 "utility/lip_filter/LIPFilter.hpp"
+
+namespace quickstep {
+
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/LIPFilter.hpp
----------------------------------------------------------------------
diff --git a/utility/lip_filter/LIPFilter.hpp b/utility/lip_filter/LIPFilter.hpp
new file mode 100644
index 0000000..c14b526
--- /dev/null
+++ b/utility/lip_filter/LIPFilter.hpp
@@ -0,0 +1,57 @@
+/**
+ * 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_UTILITY_LIP_FILTER_LIP_FILTER_HPP_
+#define QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_HPP_
+
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/** \addtogroup Utility
+ * @{
+ */
+
+enum class LIPFilterType {
+ kBloomFilter,
+ kExactFilter,
+ kSingleIdentityHashFilter
+};
+
+class LIPFilter {
+ public:
+ LIPFilterType getType() const {
+ return type_;
+ }
+
+ private:
+ LIPFilterType type_;
+
+ DISALLOW_COPY_AND_ASSIGN(LIPFilter);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/LIPFilter.proto
----------------------------------------------------------------------
diff --git a/utility/lip_filter/LIPFilter.proto b/utility/lip_filter/LIPFilter.proto
new file mode 100644
index 0000000..2dd095d
--- /dev/null
+++ b/utility/lip_filter/LIPFilter.proto
@@ -0,0 +1,53 @@
+// 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.
+
+syntax = "proto2";
+
+package quickstep.serialization;
+
+import "types/Type.proto";
+
+enum LIPFilterType {
+ BLOOM_FILTER = 1;
+ EXACT_FILTER = 2;
+ SINGLE_IDENTITY_HASH_FILTER = 3;
+}
+
+message LIPFilter {
+ required LIPFilterType lip_filter_type = 1;
+
+ extensions 16 to max;
+}
+
+message SingleIdentityHashFilter {
+ extend LIPFilter {
+ // All required
+ optional uint64 num_bits = 16;
+ }
+}
+
+message LIPFilterDeploymentInfo {
+ enum LIPFilterActionType {
+ BUILD = 1;
+ PROBE = 2;
+ }
+
+ required LIPFilterActionType action_type = 1;
+ required uint32 lip_filter_id = 2;
+ required int32 attribute_id = 3;
+ required Type attribute_type = 4;
+}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/LIPFilterAdaptiveProber.hpp
----------------------------------------------------------------------
diff --git a/utility/lip_filter/LIPFilterAdaptiveProber.hpp b/utility/lip_filter/LIPFilterAdaptiveProber.hpp
new file mode 100644
index 0000000..cf9fa34
--- /dev/null
+++ b/utility/lip_filter/LIPFilterAdaptiveProber.hpp
@@ -0,0 +1,87 @@
+/**
+ * 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_UTILITY_LIP_FILTER_LIP_FILTER_ADAPTIVE_PROBER_HPP_
+#define QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_ADAPTIVE_PROBER_HPP_
+
+#include <vector>
+
+#include "catalog/CatalogTypeDefs.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+
+/** \addtogroup Utility
+ * @{
+ */
+
+class LIPFilterAdaptiveProber {
+ public:
+ LIPFilterAdaptiveProber(const std::vector<const LIPFilter *> &lip_filters,
+ const std::vector<attribute_id> &attr_ids,
+ const std::vector<std::size_t> &attr_sizes) {
+ DCHECK_EQ(lip_filters.size(), attr_ids.size());
+ DCHECK_EQ(lip_filters.size(), attr_sizes.size());
+
+ probe_entries_.reserve(lip_filters.size());
+ for (std::size_t i = 0; i < lip_filters.size(); ++i) {
+ probe_entries_.emplace_back(
+ new ProbeEntry(lip_filters[i], attr_ids[i], attr_sizes[i]));
+ }
+ }
+
+ ~LIPFilterAdaptiveProber() {
+ for (ProbeEntry *entry : probe_entries_) {
+ delete entry;
+ }
+ }
+
+ private:
+ struct ProbeEntry {
+ ProbeEntry(const LIPFilter *lip_filter_in,
+ const attribute_id attr_id_in,
+ const std::size_t attr_size_in)
+ : lip_filter(lip_filter_in),
+ attr_id(attr_id_in),
+ attr_size(attr_size_in),
+ miss(0),
+ cnt(0) {
+ }
+ static bool isBetterThan(const ProbeEntry *a,
+ const ProbeEntry *b) {
+ return a->miss_rate > b->miss_rate;
+ }
+ const LIPFilter *lip_filter;
+ const attribute_id attr_id;
+ const std::size_t attr_size;
+ std::uint32_t miss;
+ std::uint32_t cnt;
+ float miss_rate;
+ };
+
+ std::vector<ProbeEntry *> probe_entries_;
+
+ DISALLOW_COPY_AND_ASSIGN(LIPFilterAdaptiveProber);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_ADAPTIVE_PROBER_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/LIPFilterBuilder.hpp
----------------------------------------------------------------------
diff --git a/utility/lip_filter/LIPFilterBuilder.hpp b/utility/lip_filter/LIPFilterBuilder.hpp
new file mode 100644
index 0000000..34e56b1
--- /dev/null
+++ b/utility/lip_filter/LIPFilterBuilder.hpp
@@ -0,0 +1,72 @@
+/**
+ * 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_UTILITY_LIP_FILTER_LIP_FILTER_BUILDER_HPP_
+#define QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_BUILDER_HPP_
+
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "catalog/CatalogTypeDefs.hpp"
+
+namespace quickstep {
+
+/** \addtogroup Utility
+ * @{
+ */
+
+class LIPFilterBuilder {
+ public:
+ LIPFilterBuilder(const std::vector<LIPFilter *> &lip_filters,
+ const std::vector<attribute_id> &attr_ids,
+ const std::vector<std::size_t> &attr_sizes) {
+ DCHECK_EQ(lip_filters.size(), attr_ids.size());
+ DCHECK_EQ(lip_filters.size(), attr_sizes.size());
+
+ build_entries_.reserve(lip_filters.size());
+ for (std::size_t i = 0; i < lip_filters.size(); ++i) {
+ build_entries_.emplace_back(lip_filters[i], attr_ids[i], attr_sizes[i]);
+ }
+ }
+
+ private:
+ struct BuildEntry {
+ BuildEntry(LIPFilter *lip_filter_in,
+ const attribute_id attr_id_in,
+ const std::size_t attr_size_in)
+ : lip_filter(lip_filter_in),
+ attr_id(attr_id_in),
+ attr_size(attr_size_in) {
+ }
+ LIPFilter *lip_filter;
+ const attribute_id attr_id;
+ const std::size_t attr_size;
+ };
+
+ std::vector<BuildEntry> build_entries_;
+
+ DISALLOW_COPY_AND_ASSIGN(LIPFilterBuilder);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/LIPFilterDeploymentInfo.hpp
----------------------------------------------------------------------
diff --git a/utility/lip_filter/LIPFilterDeploymentInfo.hpp b/utility/lip_filter/LIPFilterDeploymentInfo.hpp
new file mode 100644
index 0000000..aa5371a
--- /dev/null
+++ b/utility/lip_filter/LIPFilterDeploymentInfo.hpp
@@ -0,0 +1,70 @@
+/**
+ * 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_UTILITY_LIP_FILTER_LIP_FILTER_DEPLOYMENT_INFO_HPP_
+#define QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_DEPLOYMENT_INFO_HPP_
+
+#include <vector>
+
+#include "utility/Macros.hpp"
+#include "utility/lip_filter/LIPFilter.hpp"
+
+#include "catalog/CatalogTypeDefs.hpp"
+
+namespace quickstep {
+
+/** \addtogroup Utility
+ * @{
+ */
+
+enum class LIPFilterActionType {
+ kBuild = 0,
+ kProbe
+};
+
+class LIPFilterDeploymentInfo {
+ public:
+ const LIPFilterActionType getActionType() const {
+ return action_type_;
+ }
+
+ const std::vector<LIPFilter*>& lip_filters() const {
+ return lip_filters_;
+ }
+
+ const std::vector<attribute_id>& attr_ids() const {
+ return attr_ids_;
+ }
+
+ const std::vector<const Type*>& attr_types() const {
+ return attr_types_;
+ }
+
+ private:
+ LIPFilterActionType action_type_;
+ std::vector<LIPFilter*> lip_filters_;
+ std::vector<attribute_id> attr_ids_;
+ std::vector<const Type*> attr_types_;
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_DEPLOYMENT_INFO_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/LIPFilterFactory.cpp
----------------------------------------------------------------------
diff --git a/utility/lip_filter/LIPFilterFactory.cpp b/utility/lip_filter/LIPFilterFactory.cpp
new file mode 100644
index 0000000..e69de29
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/d4be71ee/utility/lip_filter/LIPFilterFactory.hpp
----------------------------------------------------------------------
diff --git a/utility/lip_filter/LIPFilterFactory.hpp b/utility/lip_filter/LIPFilterFactory.hpp
new file mode 100644
index 0000000..0567093
--- /dev/null
+++ b/utility/lip_filter/LIPFilterFactory.hpp
@@ -0,0 +1,47 @@
+/**
+ * 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_UTILITY_LIP_FILTER_LIP_FILTER_FACTORY_HPP_
+#define QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_FACTORY_HPP_
+
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/** \addtogroup Utility
+ * @{
+ */
+
+class LIPFilterFactory {
+ public:
+
+ private:
+
+ DISALLOW_COPY_AND_ASSIGN(LIPFilterFactory);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_UTILITY_LIP_FILTER_LIP_FILTER_FACTORY_HPP_