quickstep-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jianq...@apache.org
Subject incubator-quickstep git commit: Generator updates
Date Tue, 20 Sep 2016 21:19:38 GMT
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 <jianqiao@cs.wisc.edu>
Authored: Tue Sep 20 16:19:30 2016 -0500
Committer: Jianqiao Zhu <jianqiao@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_


Mime
View raw message