Optimizer changes for the LIPFilter feature.

Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: 
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/03ca4cd3
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/03ca4cd3
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/03ca4cd3

Branch: refs/heads/lip-refactor-optimizer
Commit: 03ca4cd3624571f44f1a055ad40a99cbc20bed32
Parents: 17ffbb0
Author: Jianqiao Zhu <jianq...@cs.wisc.edu>
Authored: Wed Sep 7 13:20:43 2016 -0500
Committer: Jianqiao Zhu <jianq...@cs.wisc.edu>
Committed: Wed Oct 12 16:33:24 2016 -0500

----------------------------------------------------------------------
 query_optimizer/CMakeLists.txt                  |  12 +-
 query_optimizer/ExecutionGenerator.cpp          |  17 -
 query_optimizer/ExecutionGenerator.hpp          |   5 +-
 query_optimizer/ExecutionHeuristics.cpp         | 129 --------
 query_optimizer/ExecutionHeuristics.hpp         | 157 ----------
 query_optimizer/PhysicalGenerator.cpp           |  14 +-
 .../cost_model/StarSchemaSimpleCostModel.cpp    |   2 +-
 query_optimizer/physical/CMakeLists.txt         |   7 +
 .../physical/LIPFilterConfiguration.hpp         | 173 +++++++++++
 query_optimizer/physical/TopLevelPlan.hpp       |  43 ++-
 query_optimizer/rules/AttachLIPFilters.cpp      | 251 +++++++++++++++
 query_optimizer/rules/AttachLIPFilters.hpp      | 159 ++++++++++
 query_optimizer/rules/CMakeLists.txt            |  19 ++
 .../StarSchemaHashJoinOrderOptimization.cpp     | 271 ++++++++++------
 .../StarSchemaHashJoinOrderOptimization.hpp     | 115 +++++--
 query_optimizer/tests/CMakeLists.txt            |  16 -
 .../tests/ExecutionHeuristics_unittest.cpp      | 311 -------------------
 utility/CMakeLists.txt                          |  18 ++
 utility/DisjointTreeForest.hpp                  | 151 +++++++++
 utility/PlanVisualizer.cpp                      |  54 +++-
 utility/PlanVisualizer.hpp                      |   3 +
 utility/lip_filter/CMakeLists.txt               |  19 ++
 utility/lip_filter/LIPFilter.hpp                |  39 +++
 utility/tests/DisjointTreeForest_unittest.cpp   |  97 ++++++
 24 files changed, 1287 insertions(+), 795 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index 988ffd8..fa9141c 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -41,7 +41,6 @@ add_subdirectory(tests)
 
 # Declare micro-libs:
 add_library(quickstep_queryoptimizer_ExecutionGenerator ExecutionGenerator.cpp 
ExecutionGenerator.hpp)
-add_library(quickstep_queryoptimizer_ExecutionHeuristics 
ExecutionHeuristics.cpp ExecutionHeuristics.hpp)
 add_library(quickstep_queryoptimizer_LogicalGenerator LogicalGenerator.cpp 
LogicalGenerator.hpp)
 add_library(quickstep_queryoptimizer_LogicalToPhysicalMapper
             ../empty_src.cpp
@@ -73,7 +72,6 @@ 
target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
                       
quickstep_expressions_windowaggregation_WindowAggregateFunction_proto
                       quickstep_queryexecution_QueryContext
                       quickstep_queryexecution_QueryContext_proto
-                      quickstep_queryoptimizer_ExecutionHeuristics
                       quickstep_queryoptimizer_OptimizerContext
                       quickstep_queryoptimizer_QueryHandle
                       quickstep_queryoptimizer_QueryPlan
@@ -153,14 +151,6 @@ if (ENABLE_DISTRIBUTED)
   target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
                         quickstep_catalog_Catalog_proto)
 endif()
-target_link_libraries(quickstep_queryoptimizer_ExecutionHeuristics
-                      glog
-                      quickstep_catalog_CatalogRelation
-                      quickstep_catalog_CatalogTypedefs
-                      quickstep_queryexecution_QueryContext
-                      quickstep_queryexecution_QueryContext_proto
-                      quickstep_queryoptimizer_QueryPlan
-                      quickstep_utility_Macros)
 target_link_libraries(quickstep_queryoptimizer_LogicalGenerator
                       glog
                       quickstep_parser_ParseStatement
@@ -196,6 +186,7 @@ 
target_link_libraries(quickstep_queryoptimizer_PhysicalGenerator
                       quickstep_queryoptimizer_LogicalToPhysicalMapper
                       quickstep_queryoptimizer_logical_Logical
                       quickstep_queryoptimizer_physical_Physical
+                      quickstep_queryoptimizer_rules_AttachLIPFilters
                       quickstep_queryoptimizer_rules_PruneColumns
                       
quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
                       quickstep_queryoptimizer_rules_SwapProbeBuild
@@ -233,7 +224,6 @@ 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_ExecutionHeuristics
                       quickstep_queryoptimizer_LogicalGenerator
                       quickstep_queryoptimizer_LogicalToPhysicalMapper
                       quickstep_queryoptimizer_Optimizer

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/ExecutionGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.cpp 
b/query_optimizer/ExecutionGenerator.cpp
index 9347c9c..29dec38 100644
--- a/query_optimizer/ExecutionGenerator.cpp
+++ b/query_optimizer/ExecutionGenerator.cpp
@@ -54,7 +54,6 @@
 #include "expressions/window_aggregation/WindowAggregateFunction.pb.h"
 #include "query_execution/QueryContext.hpp"
 #include "query_execution/QueryContext.pb.h"
-#include "query_optimizer/ExecutionHeuristics.hpp"
 #include "query_optimizer/OptimizerContext.hpp"
 #include "query_optimizer/QueryHandle.hpp"
 #include "query_optimizer/QueryPlan.hpp"
@@ -211,11 +210,6 @@ void ExecutionGenerator::generatePlan(const P::PhysicalPtr 
&physical_plan) {
         temporary_relation_info.producer_operator_index);
   }
 
-  // Optimize execution plan based on heuristics captured during execution 
plan generation, if enabled.
-  if (FLAGS_optimize_joins) {
-    execution_heuristics_->optimizeExecutionPlan(execution_plan_, 
query_context_proto_);
-  }
-
 #ifdef QUICKSTEP_DISTRIBUTED
   catalog_database_cache_proto_->set_name(catalog_database_->getName());
 
@@ -828,17 +822,6 @@ 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);
-
-  // Add heuristics for the Hash Join, if enabled.
-  if (FLAGS_optimize_joins && !skip_hash_join_optimization) {
-    execution_heuristics_->addHashJoinInfo(build_operator_index,
-                                           join_operator_index,
-                                           referenced_stored_build_relation,
-                                           referenced_stored_probe_relation,
-                                           
std::move(build_original_attribute_ids),
-                                           
std::move(probe_original_attribute_ids),
-                                           join_hash_table_index);
-  }
 }
 
 void ExecutionGenerator::convertNestedLoopsJoin(

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/ExecutionGenerator.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.hpp 
b/query_optimizer/ExecutionGenerator.hpp
index 2aaf5ab..495955e 100644
--- a/query_optimizer/ExecutionGenerator.hpp
+++ b/query_optimizer/ExecutionGenerator.hpp
@@ -33,7 +33,6 @@
 #include "catalog/CatalogTypedefs.hpp"
 #include "query_execution/QueryContext.hpp"
 #include "query_execution/QueryContext.pb.h"
-#include "query_optimizer/ExecutionHeuristics.hpp"
 #include "query_optimizer/QueryHandle.hpp"
 #include "query_optimizer/QueryPlan.hpp"
 #include "query_optimizer/cost_model/CostModel.hpp"
@@ -102,8 +101,7 @@ class ExecutionGenerator {
       : catalog_database_(DCHECK_NOTNULL(catalog_database)),
         query_handle_(DCHECK_NOTNULL(query_handle)),
         execution_plan_(DCHECK_NOTNULL(query_handle->getQueryPlanMutable())),
-        
query_context_proto_(DCHECK_NOTNULL(query_handle->getQueryContextProtoMutable())),
-        execution_heuristics_(new ExecutionHeuristics()) {
+        
query_context_proto_(DCHECK_NOTNULL(query_handle->getQueryContextProtoMutable()))
 {
     query_context_proto_->set_query_id(query_handle_->query_id());
 #ifdef QUICKSTEP_DISTRIBUTED
     catalog_database_cache_proto_ = 
DCHECK_NOTNULL(query_handle->getCatalogDatabaseCacheProtoMutable());
@@ -386,7 +384,6 @@ class ExecutionGenerator {
   QueryHandle *query_handle_;
   QueryPlan *execution_plan_;  // A part of QueryHandle.
   serialization::QueryContext *query_context_proto_;  // A part of QueryHandle.
-  std::unique_ptr<ExecutionHeuristics> execution_heuristics_;
 
 #ifdef QUICKSTEP_DISTRIBUTED
   serialization::CatalogDatabase *catalog_database_cache_proto_;  // A part of 
QueryHandle.

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/ExecutionHeuristics.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionHeuristics.cpp 
b/query_optimizer/ExecutionHeuristics.cpp
deleted file mode 100644
index 4fd7320..0000000
--- a/query_optimizer/ExecutionHeuristics.cpp
+++ /dev/null
@@ -1,129 +0,0 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- *   http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied.  See the License for the
- * specific language governing permissions and limitations
- * under the License.
- **/
-
-#include "query_optimizer/ExecutionHeuristics.hpp"
-
-#include <cstddef>
-#include <utility>
-#include <unordered_map>
-#include <vector>
-
-#include "catalog/CatalogTypedefs.hpp"
-#include "query_execution/QueryContext.pb.h"
-#include "query_optimizer/QueryPlan.hpp"
-#include "utility/Macros.hpp"
-
-#include "glog/logging.h"
-
-namespace quickstep {
-namespace optimizer {
-
-void ExecutionHeuristics::optimizeExecutionPlan(QueryPlan *query_plan,
-                                                serialization::QueryContext 
*query_context_proto) {
-  // Currently this only optimizes left deep joins using bloom filters.
-  // It uses a simple algorithm to discover the left deep joins.
-  // It starts with the first hash join in the plan and keeps on iterating
-  // over the next hash joins, till a probe on a different relation id is 
found.
-  // The set of hash joins found in this way forms a chain and can be 
recognized
-  // as a left deep join. It becomes a candidate for optimization.
-
-  // The optimization is done by modifying each of the build operators in the 
chain
-  // to generate a bloom filter on the build key during their hash table 
creation.
-  // The leaf-level probe operator is then modified to query all the bloom
-  // filters generated from all the build operators in the chain. These
-  // bloom filters are queried to test the membership of the probe key
-  // just prior to probing the hash table.
-
-  QueryPlan::DAGNodeIndex origin_node = 0;
-  while (origin_node < hash_joins_.size() - 1) {
-    std::vector<std::size_t> chained_nodes;
-    chained_nodes.push_back(origin_node);
-    for (std::size_t i = origin_node + 1; i < hash_joins_.size(); ++i) {
-      const relation_id checked_relation_id = 
hash_joins_[origin_node].referenced_stored_probe_relation_->getID();
-      const relation_id expected_relation_id = 
hash_joins_[i].referenced_stored_probe_relation_->getID();
-      if (checked_relation_id == expected_relation_id) {
-        chained_nodes.push_back(i);
-      } else {
-        break;
-      }
-    }
-
-    // Only chains of length greater than one are suitable candidates for 
semi-join optimization.
-    if (chained_nodes.size() > 1) {
-      std::unordered_map<QueryContext::bloom_filter_id, 
std::vector<attribute_id>> probe_bloom_filter_info;
-      for (const std::size_t node : chained_nodes) {
-        // Provision for a new bloom filter to be used by the build operator.
-        const QueryContext::bloom_filter_id bloom_filter_id =  
query_context_proto->bloom_filters_size();
-        serialization::BloomFilter *bloom_filter_proto = 
query_context_proto->add_bloom_filters();
-
-        // Modify the bloom filter properties based on the statistics of the 
relation.
-        setBloomFilterProperties(bloom_filter_proto, 
hash_joins_[node].referenced_stored_build_relation_);
-
-        // Add build-side bloom filter information to the corresponding hash 
table proto.
-        
query_context_proto->mutable_join_hash_tables(hash_joins_[node].join_hash_table_id_)
-            ->add_build_side_bloom_filter_id(bloom_filter_id);
-
-        probe_bloom_filter_info.insert(std::make_pair(bloom_filter_id, 
hash_joins_[node].probe_attributes_));
-      }
-
-      // Add probe-side bloom filter information to the corresponding hash 
table proto for each build-side bloom filter.
-      for (const std::pair<QueryContext::bloom_filter_id, 
std::vector<attribute_id>>
-               &bloom_filter_info : probe_bloom_filter_info) {
-        auto *probe_side_bloom_filter =
-            
query_context_proto->mutable_join_hash_tables(hash_joins_[origin_node].join_hash_table_id_)
-                                  ->add_probe_side_bloom_filters();
-        
probe_side_bloom_filter->set_probe_side_bloom_filter_id(bloom_filter_info.first);
-        for (const attribute_id &probe_attribute_id : 
bloom_filter_info.second) {
-          probe_side_bloom_filter->add_probe_side_attr_ids(probe_attribute_id);
-        }
-      }
-
-      // Add node dependencies from chained build nodes to origin node probe.
-      for (std::size_t i = 1; i < chained_nodes.size(); ++i) {  // Note: It 
starts from index 1.
-        
query_plan->addDirectDependency(hash_joins_[origin_node].join_operator_index_,
-                                        hash_joins_[origin_node + 
i].build_operator_index_,
-                                        true /* is_pipeline_breaker */);
-      }
-    }
-
-    // Update the origin node.
-    origin_node = chained_nodes.back() + 1;
-  }
-}
-
-void ExecutionHeuristics::setBloomFilterProperties(serialization::BloomFilter 
*bloom_filter_proto,
-                                                   const CatalogRelation 
*relation) {
-  const std::size_t cardinality = relation->estimateTupleCardinality();
-  if (cardinality < kOneThousand) {
-    bloom_filter_proto->set_bloom_filter_size(kOneThousand / 
kCompressionFactor);
-    bloom_filter_proto->set_number_of_hashes(kVeryLowSparsityHash);
-  } else if (cardinality < kTenThousand) {
-    bloom_filter_proto->set_bloom_filter_size(kTenThousand / 
kCompressionFactor);
-    bloom_filter_proto->set_number_of_hashes(kLowSparsityHash);
-  } else if (cardinality < kHundredThousand) {
-    bloom_filter_proto->set_bloom_filter_size(kHundredThousand / 
kCompressionFactor);
-    bloom_filter_proto->set_number_of_hashes(kMediumSparsityHash);
-  } else {
-    bloom_filter_proto->set_bloom_filter_size(kMillion / kCompressionFactor);
-    bloom_filter_proto->set_number_of_hashes(kHighSparsityHash);
-  }
-}
-
-}  // namespace optimizer
-}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/ExecutionHeuristics.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionHeuristics.hpp 
b/query_optimizer/ExecutionHeuristics.hpp
deleted file mode 100644
index 8ad3b7a..0000000
--- a/query_optimizer/ExecutionHeuristics.hpp
+++ /dev/null
@@ -1,157 +0,0 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- *   http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied.  See the License for the
- * specific language governing permissions and limitations
- * under the License.
- **/
-
-#ifndef QUICKSTEP_QUERY_OPTIMIZER_EXECUTION_HEURISTICS_HPP_
-#define QUICKSTEP_QUERY_OPTIMIZER_EXECUTION_HEURISTICS_HPP_
-
-#include <vector>
-
-#include "catalog/CatalogRelation.hpp"
-#include "catalog/CatalogTypedefs.hpp"
-#include "query_execution/QueryContext.hpp"
-#include "query_execution/QueryContext.pb.h"
-#include "query_optimizer/QueryPlan.hpp"
-#include "utility/Macros.hpp"
-
-#include "glog/logging.h"
-
-namespace quickstep {
-namespace optimizer {
-
-/** \addtogroup QueryOptimizer
- *  @{
- */
-
-/**
- * @brief The ExecutionHeuristics compiles certain heuristics for an execution 
plan
- *        as it is being converted to a physical plan. These heuristics can 
then be
- *        used to optimize the execution plan after it has been generated.
- **/
-class ExecutionHeuristics {
- public:
-  static const std::size_t kOneHundred = 100;
-  static const std::size_t kOneThousand = 1000;
-  static const std::size_t kTenThousand = 10000;
-  static const std::size_t kHundredThousand = 100000;
-  static const std::size_t kMillion = 1000000;
-
-  static const std::size_t kCompressionFactor = 10;
-
-  static const std::size_t kVeryLowSparsityHash = 1;
-  static const std::size_t kLowSparsityHash = 2;
-  static const std::size_t kMediumSparsityHash = 5;
-  static const std::size_t kHighSparsityHash = 10;
-
-  /**
-   * @brief A simple internal class that holds information about various
-   *        hash joins within the execution plan for a query.
-   **/
-  struct HashJoinInfo {
-    HashJoinInfo(const QueryPlan::DAGNodeIndex build_operator_index,
-                 const QueryPlan::DAGNodeIndex join_operator_index,
-                 const CatalogRelation *referenced_stored_build_relation,
-                 const CatalogRelation *referenced_stored_probe_relation,
-                 std::vector<attribute_id> &&build_attributes,
-                 std::vector<attribute_id> &&probe_attributes,
-                 const QueryContext::join_hash_table_id join_hash_table_id)
-        : build_operator_index_(build_operator_index),
-          join_operator_index_(join_operator_index),
-          referenced_stored_build_relation_(referenced_stored_build_relation),
-          referenced_stored_probe_relation_(referenced_stored_probe_relation),
-          build_attributes_(std::move(build_attributes)),
-          probe_attributes_(std::move(probe_attributes)),
-          join_hash_table_id_(join_hash_table_id) {
-    }
-
-    const QueryPlan::DAGNodeIndex build_operator_index_;
-    const QueryPlan::DAGNodeIndex join_operator_index_;
-    const CatalogRelation *referenced_stored_build_relation_;
-    const CatalogRelation *referenced_stored_probe_relation_;
-    const std::vector<attribute_id> build_attributes_;
-    const std::vector<attribute_id> probe_attributes_;
-    const QueryContext::join_hash_table_id join_hash_table_id_;
-  };
-
-
-  /**
-   * @brief Constructor.
-   **/
-  ExecutionHeuristics() {}
-
-  /**
-   * @brief Saves information about a hash join used within the execution plan
-   *        for a query.
-   *
-   * @param build_operator_index Index of the build operator of the hash join.
-   * @param join_operator_index Index of the join operator of the hash join.
-   * @param build_relation_id Id of the relation on which hash table is being 
built.
-   * @param probe_relation_id Id of the relation on which hash table is being 
probed.
-   * @param build_attributes List of attributes on which hash table is being 
built.
-   * @param probe_attributes List of attributes on which hash table is being 
probed.
-   * @param join_hash_table_id Id of the hash table which refers to the actual 
hash
-   *        table within the query context.
-   **/
-  inline void addHashJoinInfo(const QueryPlan::DAGNodeIndex 
build_operator_index,
-                              const QueryPlan::DAGNodeIndex 
join_operator_index,
-                              const CatalogRelation 
*referenced_stored_build_relation,
-                              const CatalogRelation 
*referenced_stored_probe_relation,
-                              std::vector<attribute_id> &&build_attributes,
-                              std::vector<attribute_id> &&probe_attributes,
-                              const QueryContext::join_hash_table_id 
join_hash_table_id) {
-    hash_joins_.push_back(HashJoinInfo(build_operator_index,
-                                       join_operator_index,
-                                       referenced_stored_build_relation,
-                                       referenced_stored_probe_relation,
-                                       std::move(build_attributes),
-                                       std::move(probe_attributes),
-                                       join_hash_table_id));
-  }
-
-  /**
-   * @brief Optimize the execution plan based on heuristics generated
-   *        during physical plan to execution plan conversion.
-   *
-   * @param query_plan A mutable reference to the query execution plan.
-   * @param query_context_proto A mutable reference to the protobuf 
representation
-   *        of the query context.
-   **/
-  void optimizeExecutionPlan(QueryPlan *query_plan, 
serialization::QueryContext *query_context_proto);
-
-  /**
-   * @brief Set the properties of the bloom filter proto based on the 
statistics
-   *        of the given relation.
-   *
-   * @param bloom_filter_proto A mutable reference to the bloom filter 
protobuf representation.
-   * @param relation The catalog relation on which bloom filter is being built.
-   **/
-  void setBloomFilterProperties(serialization::BloomFilter *bloom_filter_proto,
-                                const CatalogRelation *relation);
-
- private:
-  std::vector<HashJoinInfo> hash_joins_;
-
-  DISALLOW_COPY_AND_ASSIGN(ExecutionHeuristics);
-};
-
-/** @} */
-
-}  // namespace optimizer
-}  // namespace quickstep
-
-#endif /* QUICKSTEP_QUERY_OPTIMIZER_EXECUTION_HEURISTICS_HPP_ */

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/PhysicalGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.cpp 
b/query_optimizer/PhysicalGenerator.cpp
index 8f19702..8143d5c 100644
--- a/query_optimizer/PhysicalGenerator.cpp
+++ b/query_optimizer/PhysicalGenerator.cpp
@@ -26,6 +26,7 @@
 #include "query_optimizer/Validator.hpp"
 #include "query_optimizer/logical/Logical.hpp"
 #include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/rules/AttachLIPFilters.hpp"
 #include "query_optimizer/rules/PruneColumns.hpp"
 #include "query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp"
 #include "query_optimizer/rules/SwapProbeBuild.hpp"
@@ -49,6 +50,10 @@ DEFINE_bool(reorder_hash_joins, true,
             "cardinality and selective tables to be joined first, which is 
suitable "
             "for queries on star-schema tables.");
 
+DEFINE_bool(use_lip_filters, false,
+            "If true, use LIP (lookahead information passing) filters to 
accelerate "
+            "hash joins.");
+
 DEFINE_bool(visualize_plan, false,
             "If true, visualize the final physical plan into a graph in DOT 
format "
             "(DOT is a plain text graph description language). Then print the "
@@ -95,11 +100,14 @@ P::PhysicalPtr PhysicalGenerator::generateInitialPlan(
 
 P::PhysicalPtr PhysicalGenerator::optimizePlan() {
   std::vector<std::unique_ptr<Rule<P::Physical>>> rules;
+  rules.emplace_back(new PruneColumns());
   if (FLAGS_reorder_hash_joins) {
     rules.emplace_back(new StarSchemaHashJoinOrderOptimization());
+    rules.emplace_back(new PruneColumns());
+  } else {
+    rules.emplace_back(new SwapProbeBuild());
   }
-  rules.emplace_back(new PruneColumns());
-  rules.emplace_back(new SwapProbeBuild());
+  rules.emplace_back(new AttachLIPFilters());
 
   for (std::unique_ptr<Rule<P::Physical>> &rule : rules) {
     physical_plan_ = rule->apply(physical_plan_);
@@ -110,7 +118,7 @@ P::PhysicalPtr PhysicalGenerator::optimizePlan() {
   DVLOG(4) << "Optimized physical plan:\n" << physical_plan_->toString();
 
   if (FLAGS_visualize_plan) {
-  quickstep::PlanVisualizer plan_visualizer;
+    quickstep::PlanVisualizer plan_visualizer;
     std::cerr << "\n" << plan_visualizer.visualize(physical_plan_) << "\n";
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp 
b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
index 8d254fa..1075739 100644
--- a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
@@ -358,7 +358,7 @@ double 
StarSchemaSimpleCostModel::estimateSelectivityForPredicate(
           std::static_pointer_cast<const E::LogicalAnd>(filter_predicate);
       double selectivity = 1.0;
       for (const auto &predicate : logical_and->operands()) {
-        selectivity = selectivity * estimateSelectivityForPredicate(predicate, 
physical_plan);
+        selectivity = std::min(selectivity, 
estimateSelectivityForPredicate(predicate, physical_plan));
       }
       return selectivity;
     }

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/physical/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/CMakeLists.txt 
b/query_optimizer/physical/CMakeLists.txt
index 3b7d3f0..5c2cd0b 100644
--- a/query_optimizer/physical/CMakeLists.txt
+++ b/query_optimizer/physical/CMakeLists.txt
@@ -27,6 +27,7 @@ add_library(quickstep_queryoptimizer_physical_HashJoin 
HashJoin.cpp HashJoin.hpp
 add_library(quickstep_queryoptimizer_physical_InsertSelection 
InsertSelection.cpp InsertSelection.hpp)
 add_library(quickstep_queryoptimizer_physical_InsertTuple InsertTuple.cpp 
InsertTuple.hpp)
 add_library(quickstep_queryoptimizer_physical_Join ../../empty_src.cpp 
Join.hpp)
+add_library(quickstep_queryoptimizer_physical_LIPFilterConfiguration 
../../empty_src.cpp LIPFilterConfiguration.hpp)
 add_library(quickstep_queryoptimizer_physical_NestedLoopsJoin 
NestedLoopsJoin.cpp NestedLoopsJoin.hpp)
 add_library(quickstep_queryoptimizer_physical_PatternMatcher 
../../empty_src.cpp PatternMatcher.hpp)
 add_library(quickstep_queryoptimizer_physical_Physical ../../empty_src.cpp 
Physical.hpp)
@@ -150,6 +151,10 @@ 
target_link_libraries(quickstep_queryoptimizer_physical_Join
                       quickstep_queryoptimizer_expressions_NamedExpression
                       quickstep_queryoptimizer_physical_Physical
                       quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_physical_LIPFilterConfiguration
+                      quickstep_queryoptimizer_expressions_AttributeReference
+                      quickstep_utility_Macros
+                      quickstep_utility_lipfilter_LIPFilter)
 target_link_libraries(quickstep_queryoptimizer_physical_NestedLoopsJoin
                       glog
                       quickstep_queryoptimizer_OptimizerTree
@@ -237,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
@@ -279,6 +285,7 @@ target_link_libraries(quickstep_queryoptimizer_physical
                       quickstep_queryoptimizer_physical_InsertSelection
                       quickstep_queryoptimizer_physical_InsertTuple
                       quickstep_queryoptimizer_physical_Join
+                      quickstep_queryoptimizer_physical_LIPFilterConfiguration
                       quickstep_queryoptimizer_physical_NestedLoopsJoin
                       quickstep_queryoptimizer_physical_PatternMatcher
                       quickstep_queryoptimizer_physical_Physical

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/physical/LIPFilterConfiguration.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/LIPFilterConfiguration.hpp 
b/query_optimizer/physical/LIPFilterConfiguration.hpp
new file mode 100644
index 0000000..93ce318
--- /dev/null
+++ b/query_optimizer/physical/LIPFilterConfiguration.hpp
@@ -0,0 +1,173 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ **/
+
+#ifndef QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_LIP_FILTER_CONFIGURATION_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_LIP_FILTER_CONFIGURATION_HPP_
+
+#include <map>
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "utility/lip_filter/LIPFilter.hpp"
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+namespace physical {
+
+/** \addtogroup OptimizerPhysical
+ *  @{
+ */
+
+class Physical;
+typedef std::shared_ptr<const Physical> PhysicalPtr;
+
+/**
+ * @brief Optimizer information for a LIP filter builder.
+ */
+struct LIPFilterBuildInfo {
+  /**
+   * @brief Constructor.
+   *
+   * @param build_attribute_in The attribute to build the LIP filter with.
+   * @param filter_cardinality_in The LIP filter's cardinality.
+   * @param filter_type_in The LIP filter's type.
+   */
+  LIPFilterBuildInfo(const expressions::AttributeReferencePtr 
&build_attribute_in,
+                     const std::size_t filter_cardinality_in,
+                     const LIPFilterType &filter_type_in)
+      : build_attribute(build_attribute_in),
+        filter_cardinality(filter_cardinality_in),
+        filter_type(filter_type_in) {
+  }
+  const expressions::AttributeReferencePtr build_attribute;
+  const std::size_t filter_cardinality;
+  const LIPFilterType filter_type;
+};
+
+/**
+ * @brief Optimizer information for a LIP filter prober.
+ */
+struct LIPFilterProbeInfo {
+  /**
+   * @brief Constructor.
+   *
+   * @param probe_attribute_in The attribute to probe the LIP filter with.
+   * @param build_attribute_in The attribute that the LIP filter is built with.
+   * @param builder_in The physical node that the LIP filter's builder is 
attached to.
+   */
+  LIPFilterProbeInfo(const expressions::AttributeReferencePtr 
&probe_attribute_in,
+                     const expressions::AttributeReferencePtr 
&build_attribute_in,
+                     const PhysicalPtr &builder_in)
+      : probe_attribute(probe_attribute_in),
+        build_attribute(build_attribute_in),
+        builder(builder_in) {
+  }
+  const expressions::AttributeReferencePtr probe_attribute;
+  const expressions::AttributeReferencePtr build_attribute;
+  const PhysicalPtr builder;
+};
+
+
+class LIPFilterConfiguration;
+typedef std::shared_ptr<const LIPFilterConfiguration> 
LIPFilterConfigurationPtr;
+
+/**
+ * @brief Configuration information of all the LIP filters in a query plan.
+ */
+class LIPFilterConfiguration {
+ public:
+  /**
+   * @brief Constructor.
+   */
+  LIPFilterConfiguration() {
+  }
+
+  /**
+   * @brief Add information for a LIP filter builder.
+   *
+   * @param build_attribute The attribute to build the LIP filter with.
+   * @param builder The physical node to attach the LIP filter builder to.
+   * @param filter_size The LIP filter's cardinality.
+   * @param filter_type The LIP filter's type.
+   */
+  void addBuildInfo(const expressions::AttributeReferencePtr &build_attribute,
+                    const PhysicalPtr &builder,
+                    const std::size_t filter_size,
+                    const LIPFilterType &filter_type) {
+    build_info_map_[builder].emplace_back(
+        build_attribute, filter_size, filter_type);
+  }
+
+  /**
+   * @brief Add information for a LIP filter prober.
+   *
+   * @param probe_attribute The attribute to probe the LIP filter with.
+   * @param prober The physical node to attach the LIP filter prober to.
+   * @param build_attribute The attribute that the LIP filter is built with.
+   * @param builder The physical node that the LIP filter's builder is 
attached to.
+   */
+  void addProbeInfo(const expressions::AttributeReferencePtr &probe_attribute,
+                    const PhysicalPtr &prober,
+                    const expressions::AttributeReferencePtr &build_attribute,
+                    const PhysicalPtr &builder) {
+    probe_info_map_[prober].emplace_back(
+        probe_attribute, build_attribute, builder);
+  }
+
+  /**
+   * @brief Get all the LIP filter builders.
+   *
+   * @return A map where each key is a physical node and each mapped value is
+   *         a vector of all the LIP filter builders that are attached to the
+   *         physical node.
+   */
+  const std::map<PhysicalPtr, std::vector<LIPFilterBuildInfo>>& 
getBuildInfoMap() const {
+    return build_info_map_;
+  }
+
+  /**
+   * @brief Get all the LIP filter probers.
+   *
+   * @return A map where each key is a physical node and each mapped value is
+   *         a vector of all the LIP filter probers that are attached to the
+   *         physical node.
+   */
+  const std::map<PhysicalPtr, std::vector<LIPFilterProbeInfo>>& 
getProbeInfoMap() const {
+    return probe_info_map_;
+  }
+
+ private:
+  std::map<PhysicalPtr, std::vector<LIPFilterBuildInfo>> build_info_map_;
+  std::map<PhysicalPtr, std::vector<LIPFilterProbeInfo>> probe_info_map_;
+
+  DISALLOW_COPY_AND_ASSIGN(LIPFilterConfiguration);
+};
+
+/** @} */
+
+}  // namespace physical
+}  // namespace optimizer
+}  // namespace quickstep
+
+#endif /* QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_LIP_FILTER_CONFIGURATION_HPP_ */

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/physical/TopLevelPlan.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/TopLevelPlan.hpp 
b/query_optimizer/physical/TopLevelPlan.hpp
index 8f07dec..7dfc2b6 100644
--- a/query_optimizer/physical/TopLevelPlan.hpp
+++ b/query_optimizer/physical/TopLevelPlan.hpp
@@ -29,6 +29,7 @@
 #include "query_optimizer/expressions/AttributeReference.hpp"
 #include "query_optimizer/expressions/ExprId.hpp"
 #include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/physical/LIPFilterConfiguration.hpp"
 #include "query_optimizer/physical/Physical.hpp"
 #include "query_optimizer/physical/PhysicalType.hpp"
 #include "utility/Macros.hpp"
@@ -89,6 +90,29 @@ class TopLevelPlan : public Physical {
     return shared_subplans_[index];
   }
 
+  /**
+   * @brief Creates a copy of the TopLevelPlan with lip_filter_configuration_
+   *        replaced by \p new_lip_filter_configuration.
+   *
+   * @param new_lip_filter_configuration The new lip_filter_configuration to be
+   *        substituted for the existing one.
+   * @return A copy of this TopLevelPlan with the new lip_filter_configuration.
+   */
+  TopLevelPlanPtr copyWithLIPFilterConfiguration(
+      const LIPFilterConfigurationPtr &new_lip_filter_configuration) const {
+    return TopLevelPlan::Create(plan_,
+                                shared_subplans_,
+                                uncorrelated_subquery_map_,
+                                new_lip_filter_configuration);
+  }
+
+  /**
+   * @return The LIPFilter configuration information for the overall query 
plan.
+   */
+  const LIPFilterConfigurationPtr& lip_filter_configuration() const {
+    return lip_filter_configuration_;
+  }
+
   PhysicalPtr copyWithNewChildren(
       const std::vector<PhysicalPtr> &new_children) const override {
     DCHECK_EQ(getNumChildren(), new_children.size());
@@ -125,18 +149,22 @@ class TopLevelPlan : public Physical {
    *
    * @param plan The query plan.
    * @param shared_subplans The subplans referenced in the main input plan.
-   * @param Map from the expression ID of an attribute reference to the
-   *        uncorrelated subquery that produces the attribute.
+   * @param uncorrelated_subquery_map Map from the expression ID of an 
attribute
+   *        reference to the uncorrelated subquery that produces the attribute.
+   * @param lip_filter_configuration The LIPFilter configuration information
+   *        for the overall query plan.
    * @return An immutable TopLevelPlan.
    */
   static TopLevelPlanPtr Create(
       const PhysicalPtr &plan,
       const std::vector<PhysicalPtr> &shared_subplans = {},
       const std::unordered_map<expressions::ExprId, int> 
&uncorrelated_subquery_map
-          = std::unordered_map<expressions::ExprId, int>()) {
+          = std::unordered_map<expressions::ExprId, int>(),
+      const LIPFilterConfigurationPtr &lip_filter_configuration = nullptr) {
     return TopLevelPlanPtr(new TopLevelPlan(plan,
                                             shared_subplans,
-                                            uncorrelated_subquery_map));
+                                            uncorrelated_subquery_map,
+                                            lip_filter_configuration));
   }
 
  protected:
@@ -151,10 +179,12 @@ class TopLevelPlan : public Physical {
  private:
   TopLevelPlan(const PhysicalPtr &plan,
                const std::vector<PhysicalPtr> &shared_subplans,
-               const std::unordered_map<expressions::ExprId, int> 
&uncorrelated_subquery_map)
+               const std::unordered_map<expressions::ExprId, int> 
&uncorrelated_subquery_map,
+               const LIPFilterConfigurationPtr &lip_filter_configuration)
       : plan_(plan),
         shared_subplans_(shared_subplans),
-        uncorrelated_subquery_map_(uncorrelated_subquery_map) {
+        uncorrelated_subquery_map_(uncorrelated_subquery_map),
+        lip_filter_configuration_(lip_filter_configuration) {
     addChild(plan);
     for (const PhysicalPtr &shared_subplan : shared_subplans) {
       addChild(shared_subplan);
@@ -165,6 +195,7 @@ class TopLevelPlan : public Physical {
   // Stored in the topological ordering based on dependencies.
   std::vector<PhysicalPtr> shared_subplans_;
   std::unordered_map<expressions::ExprId, int> uncorrelated_subquery_map_;
+  LIPFilterConfigurationPtr lip_filter_configuration_;
 
   DISALLOW_COPY_AND_ASSIGN(TopLevelPlan);
 };

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/rules/AttachLIPFilters.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/AttachLIPFilters.cpp 
b/query_optimizer/rules/AttachLIPFilters.cpp
new file mode 100644
index 0000000..32fc3b7
--- /dev/null
+++ b/query_optimizer/rules/AttachLIPFilters.cpp
@@ -0,0 +1,251 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ **/
+
+#include "query_optimizer/rules/AttachLIPFilters.hpp"
+
+#include <algorithm>
+#include <iterator>
+#include <memory>
+#include <set>
+#include <stack>
+#include <unordered_set>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/NamedExpression.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
+#include "query_optimizer/physical/LIPFilterConfiguration.hpp"
+#include "query_optimizer/physical/HashJoin.hpp"
+#include "query_optimizer/physical/PatternMatcher.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/PhysicalType.hpp"
+#include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "utility/lip_filter/LIPFilter.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace P = ::quickstep::optimizer::physical;
+
+P::PhysicalPtr AttachLIPFilters::apply(const P::PhysicalPtr &input) {
+  DCHECK(input->getPhysicalType() == P::PhysicalType::kTopLevelPlan);
+
+  const P::TopLevelPlanPtr top_level_plan =
+     std::static_pointer_cast<const P::TopLevelPlan>(input);
+  cost_model_.reset(
+      new cost::StarSchemaSimpleCostModel(
+          top_level_plan->shared_subplans()));
+  lip_filter_configuration_.reset(new P::LIPFilterConfiguration());
+
+  std::set<E::ExprId> already_filtered_attributes;
+  attachLIPFilters(NodeList(input), &already_filtered_attributes);
+
+  P::PhysicalPtr output;
+  if (!lip_filter_configuration_->getBuildInfoMap().empty() ||
+      !lip_filter_configuration_->getProbeInfoMap().empty()) {
+    output = top_level_plan->copyWithLIPFilterConfiguration(
+        P::LIPFilterConfigurationPtr(lip_filter_configuration_.release()));
+  } else {
+    output = input;
+  }
+  return output;
+}
+
+void AttachLIPFilters::attachLIPFilters(
+    const NodeList &path,
+    std::set<expressions::ExprId> *already_filtered_attributes) {
+  const P::PhysicalPtr &node = path.node;
+
+  // First process child nodes
+  for (const auto &child : node->children()) {
+    std::set<E::ExprId> child_filtered_attributes;
+    attachLIPFilters(path.cons(child), &child_filtered_attributes);
+    already_filtered_attributes->insert(child_filtered_attributes.begin(),
+                                        child_filtered_attributes.end());
+  }
+
+  // Attach LIP filters to HashJoin/Selection/Aggregate nodes
+  P::PhysicalPtr probe_child = nullptr;
+  switch (node->getPhysicalType()) {
+    case P::PhysicalType::kHashJoin:
+      probe_child = std::static_pointer_cast<const P::HashJoin>(node)->left();
+      break;
+    case P::PhysicalType::kSelection:
+      probe_child = std::static_pointer_cast<const 
P::Selection>(node)->input();
+      break;
+    case P::PhysicalType::kAggregate:
+      probe_child = std::static_pointer_cast<const 
P::Aggregate>(node)->input();
+      break;
+    default:
+      break;
+  }
+
+  if (probe_child != nullptr &&
+      cost_model_->estimateCardinality(probe_child) > 10000000) {
+    const auto &candidate_lip_filters = 
getProbeSideInfo(path.cons(probe_child));
+    if (!candidate_lip_filters.empty()) {
+      std::map<E::AttributeReferencePtr, LIPFilterInfoPtr> selected_filters;
+      for (const auto &info : candidate_lip_filters) {
+        auto it = selected_filters.find(info->attribute);
+        if (it == selected_filters.end()) {
+          selected_filters.emplace(info->attribute, info);
+        } else if (LIPFilterInfo::isBetterThan(*info, *it->second)) {
+          it->second = info;
+        }
+      }
+
+      for (const auto &pair : selected_filters) {
+        const E::ExprId source_attr_id =  pair.second->source_attribute->id();
+        if (already_filtered_attributes->find(source_attr_id)
+                == already_filtered_attributes->end()) {
+          lip_filter_configuration_->addBuildInfo(
+              pair.second->source_attribute,
+              pair.second->source,
+              pair.second->estimated_cardinality * 8,
+              LIPFilterType::kSingleIdentityHashFilter);
+          lip_filter_configuration_->addProbeInfo(
+              pair.first,
+              node,
+              pair.second->source_attribute,
+              pair.second->source);
+          already_filtered_attributes->emplace(source_attr_id);
+        }
+      }
+    }
+  }
+}
+
+const std::vector<AttachLIPFilters::LIPFilterInfoPtr>& AttachLIPFilters
+    ::getBuildSideInfo(const NodeList &path) {
+  const P::PhysicalPtr &node = path.node;
+  if (build_side_info_.find(node) == build_side_info_.end()) {
+    std::vector<LIPFilterInfoPtr> lip_filters;
+
+    // 1. Gather candidate LIP filters propagated from descendant nodes.
+    std::unordered_set<E::ExprId> output_attribute_ids;
+    for (const auto &attr : node->getOutputAttributes()) {
+      output_attribute_ids.emplace(attr->id());
+    }
+    switch (node->getPhysicalType()) {
+      case P::PhysicalType::kAggregate:
+      case P::PhysicalType::kSelection:
+      case P::PhysicalType::kHashJoin: {
+        for (const P::PhysicalPtr &child : node->children()) {
+          for (const LIPFilterInfoPtr &info : 
getBuildSideInfo(path.cons(child))) {
+            lip_filters.emplace_back(info);
+          }
+        }
+        break;
+      }
+      default:
+        break;
+    }
+
+    // 2. Consider the parent physical node. If it is a HashJoin,
+    // then each build-side join attribute is a candidate LIP filter
+    // which can be built by the BuildHashOperator that corresponds
+    // to the parent HashJoin node.
+    P::HashJoinPtr hash_join;
+    if (path.cdr() != nullptr &&
+        P::SomeHashJoin::MatchesWithConditionalCast(path.cdr()->node, 
&hash_join)) {
+      const P::PhysicalPtr &build_node = hash_join->right();
+      // TODO(jianqiao): consider probe-side info to allow cascading 
propagation.
+      double selectivity = cost_model_->estimateSelectivity(build_node);
+      // Only consider attributes that are selective.
+      if (selectivity < 1.0) {
+        std::size_t cardinality = cost_model_->estimateCardinality(build_node);
+        for (const auto &attr : hash_join->right_join_attributes()) {
+          lip_filters.emplace_back(
+              std::make_shared<LIPFilterInfo>(attr,
+                                              path.cdr()->node,
+                                              path.depth,
+                                              selectivity,
+                                              cardinality));
+        }
+      }
+    }
+    build_side_info_.emplace(node, std::move(lip_filters));
+  }
+  return build_side_info_.at(node);
+}
+
+const std::vector<AttachLIPFilters::LIPFilterInfoPtr>& AttachLIPFilters
+    ::getProbeSideInfo(const NodeList &path) {
+  const P::PhysicalPtr &node = path.node;
+  if (probe_side_info_.find(node) == probe_side_info_.end()) {
+    std::vector<LIPFilterInfoPtr> lip_filters;
+    if (path.cdr() != nullptr) {
+      // 1. Gather candidate LIP filters propagated from ancestor nodes.
+      const auto &parent_lip_filters = getProbeSideInfo(*path.cdr());
+      if (!parent_lip_filters.empty()) {
+        std::unordered_set<E::ExprId> output_attribute_ids;
+        for (const auto &attr : node->getOutputAttributes()) {
+          output_attribute_ids.emplace(attr->id());
+        }
+        for (const auto &info : parent_lip_filters) {
+          if (output_attribute_ids.find(info->attribute->id()) != 
output_attribute_ids.end()) {
+            lip_filters.emplace_back(info);
+          }
+        }
+      }
+
+      // 2. Consider the parent physical node. If it is an InnerHashJoin or
+      // LeftSemiHashJoin, then we can propagate the build-side LIP filters
+      // to the probe-side.
+      P::HashJoinPtr hash_join;
+      if (P::SomeHashJoin::MatchesWithConditionalCast(path.cdr()->node, 
&hash_join) &&
+          (hash_join->join_type() == P::HashJoin::JoinType::kInnerJoin ||
+           hash_join->join_type() == P::HashJoin::JoinType::kLeftSemiJoin)) {
+        const P::PhysicalPtr &build_side_child = hash_join->right();
+        std::unordered_map<E::ExprId, E::AttributeReferencePtr> 
join_attribute_pairs;
+        for (std::size_t i = 0; i < hash_join->left_join_attributes().size(); 
++i) {
+          const E::AttributeReferencePtr probe_side_join_attribute =
+              hash_join->left_join_attributes()[i];
+          const E::AttributeReferencePtr build_side_join_attribute =
+              hash_join->right_join_attributes()[i];
+          join_attribute_pairs.emplace(build_side_join_attribute->id(),
+                                       probe_side_join_attribute);
+        }
+        for (const auto &info : 
getBuildSideInfo(path.cdr()->cons(build_side_child))) {
+          const auto pair_it = 
join_attribute_pairs.find(info->attribute->id());
+          if (pair_it != join_attribute_pairs.end()) {
+            lip_filters.emplace_back(
+                std::make_shared<LIPFilterInfo>(pair_it->second,
+                                                info->source,
+                                                info->depth,
+                                                info->estimated_selectivity,
+                                                info->estimated_cardinality,
+                                                info->attribute));
+          }
+        }
+      }
+    }
+    probe_side_info_.emplace(node, std::move(lip_filters));
+  }
+  return probe_side_info_.at(node);
+}
+
+}  // namespace optimizer
+}  // namespace quickstep
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/rules/AttachLIPFilters.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/AttachLIPFilters.hpp 
b/query_optimizer/rules/AttachLIPFilters.hpp
new file mode 100644
index 0000000..74cf885
--- /dev/null
+++ b/query_optimizer/rules/AttachLIPFilters.hpp
@@ -0,0 +1,159 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ **/
+
+#ifndef QUICKSTEP_QUERY_OPTIMIZER_RULES_ATTACH_LIP_FILTERS_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_RULES_ATTACH_LIP_FILTERS_HPP_
+
+#include <cstddef>
+#include <map>
+#include <memory>
+#include <set>
+#include <stack>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/expressions/NamedExpression.hpp"
+#include "query_optimizer/expressions/Predicate.hpp"
+#include "query_optimizer/physical/LIPFilterConfiguration.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/HashJoin.hpp"
+#include "query_optimizer/rules/Rule.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+namespace optimizer {
+
+/** \addtogroup OptimizerRules
+ *  @{
+ */
+
+/**
+ * @brief Rule that applies to a physical plan to attach LIPFilters.
+ */
+class AttachLIPFilters : public Rule<physical::Physical> {
+ public:
+  /**
+   * @brief Constructor.
+   */
+  AttachLIPFilters() {}
+
+  ~AttachLIPFilters() override {}
+
+  std::string getName() const override {
+    return "AttachLIPFilters";
+  }
+
+  physical::PhysicalPtr apply(const physical::PhysicalPtr &input) override;
+
+ private:
+  /**
+   * @brief Internal data structure for passing around LIPFilter information.
+   */
+  struct LIPFilterInfo {
+    LIPFilterInfo(const expressions::AttributeReferencePtr &attribute_in,
+                  const physical::PhysicalPtr &source_in,
+                  const int depth_in,
+                  const double estimated_selectivity_in,
+                  const std::size_t estimated_cardinality_in,
+                  const expressions::AttributeReferencePtr 
&source_attribute_in = nullptr)
+        : attribute(attribute_in),
+          source(source_in),
+          depth(depth_in),
+          estimated_selectivity(estimated_selectivity_in),
+          estimated_cardinality(estimated_cardinality_in),
+          source_attribute(
+              source_attribute_in == nullptr
+                  ? attribute_in
+                  : source_attribute_in) {
+
+    }
+
+    static bool isBetterThan(const LIPFilterInfo &a, const LIPFilterInfo &b) {
+      if (a.estimated_selectivity == b.estimated_selectivity) {
+        return a.depth > b.depth;
+      } else {
+        return a.estimated_selectivity < b.estimated_selectivity;
+      }
+    }
+
+    expressions::AttributeReferencePtr attribute;
+    physical::PhysicalPtr source;
+    int depth;
+    double estimated_selectivity;
+    std::size_t estimated_cardinality;
+    expressions::AttributeReferencePtr source_attribute;
+  };
+
+  typedef std::shared_ptr<const LIPFilterInfo> LIPFilterInfoPtr;
+
+  /**
+   * @brief Functional list data structure for internal use.
+   */
+  struct NodeList {
+    NodeList(const physical::PhysicalPtr &node_in)
+        : node(node_in),
+          next(nullptr),
+          depth(0) {
+    }
+
+    NodeList(const physical::PhysicalPtr &node_in,
+             const NodeList *next_in,
+             const int depth_in)
+        : node(node_in),
+          next(next_in),
+          depth(depth_in) {
+    }
+
+    inline const NodeList *cdr() const {
+      return next;
+    }
+
+    inline const NodeList cons(const physical::PhysicalPtr &new_node) const {
+      return NodeList(new_node, this, depth+1);
+    }
+
+    const physical::PhysicalPtr node;
+    const NodeList *next;
+    const int depth;
+  };
+
+  void attachLIPFilters(const NodeList &path,
+                        std::set<expressions::ExprId> 
*already_filtered_attributes);
+
+  const std::vector<LIPFilterInfoPtr>& getBuildSideInfo(const NodeList &path);
+
+  const std::vector<LIPFilterInfoPtr>& getProbeSideInfo(const NodeList &path);
+
+  std::unique_ptr<cost::StarSchemaSimpleCostModel> cost_model_;
+  std::map<physical::PhysicalPtr, std::vector<LIPFilterInfoPtr>> 
build_side_info_;
+  std::map<physical::PhysicalPtr, std::vector<LIPFilterInfoPtr>> 
probe_side_info_;
+  std::unique_ptr<physical::LIPFilterConfiguration> lip_filter_configuration_;
+
+  DISALLOW_COPY_AND_ASSIGN(AttachLIPFilters);
+};
+
+/** @} */
+
+}  // namespace optimizer
+}  // namespace quickstep
+
+#endif /* QUICKSTEP_QUERY_OPTIMIZER_RULES_ATTACH_LIP_FILTERS_HPP_ */

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/rules/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CMakeLists.txt 
b/query_optimizer/rules/CMakeLists.txt
index d9709ce..944bfd6 100644
--- a/query_optimizer/rules/CMakeLists.txt
+++ b/query_optimizer/rules/CMakeLists.txt
@@ -18,6 +18,7 @@
 add_subdirectory(tests)
 
 # Declare micro-libs:
+add_library(quickstep_queryoptimizer_rules_AttachLIPFilters 
AttachLIPFilters.cpp AttachLIPFilters.hpp)
 add_library(quickstep_queryoptimizer_rules_BottomUpRule ../../empty_src.cpp 
BottomUpRule.hpp)
 add_library(quickstep_queryoptimizer_rules_CollapseProject CollapseProject.cpp 
CollapseProject.hpp)
 add_library(quickstep_queryoptimizer_rules_GenerateJoins GenerateJoins.cpp 
GenerateJoins.hpp)
@@ -36,6 +37,22 @@ add_library(quickstep_queryoptimizer_rules_UnnestSubqueries 
UnnestSubqueries.cpp
 
 
 # Link dependencies:
+target_link_libraries(quickstep_queryoptimizer_rules_AttachLIPFilters
+                      
quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
+                      quickstep_queryoptimizer_expressions_AttributeReference
+                      quickstep_queryoptimizer_expressions_ExprId
+                      quickstep_queryoptimizer_expressions_NamedExpression
+                      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_lipfilter_LIPFilter)
 target_link_libraries(quickstep_queryoptimizer_rules_BottomUpRule
                       glog
                       quickstep_queryoptimizer_rules_Rule
@@ -127,6 +144,7 @@ 
target_link_libraries(quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOpti
                       quickstep_queryoptimizer_physical_PhysicalType
                       quickstep_queryoptimizer_physical_TopLevelPlan
                       quickstep_queryoptimizer_rules_Rule
+                      quickstep_utility_DisjointTreeForest
                       quickstep_utility_Macros)
 target_link_libraries(quickstep_queryoptimizer_rules_SwapProbeBuild
                       quickstep_queryoptimizer_costmodel_SimpleCostModel
@@ -187,6 +205,7 @@ 
target_link_libraries(quickstep_queryoptimizer_rules_UpdateExpression
 # Module all-in-one library:
 add_library(quickstep_queryoptimizer_rules ../../empty_src.cpp 
OptimizerRulesModule.hpp)
 target_link_libraries(quickstep_queryoptimizer_rules
+                      quickstep_queryoptimizer_rules_AttachLIPFilters
                       quickstep_queryoptimizer_rules_BottomUpRule
                       quickstep_queryoptimizer_rules_CollapseProject
                       quickstep_queryoptimizer_rules_GenerateJoins

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp 
b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
index 946d316..2b5adbb 100644
--- a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
+++ b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.cpp
@@ -28,11 +28,13 @@
 #include "query_optimizer/expressions/AttributeReference.hpp"
 #include "query_optimizer/expressions/NamedExpression.hpp"
 #include "query_optimizer/expressions/PatternMatcher.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
 #include "query_optimizer/physical/HashJoin.hpp"
 #include "query_optimizer/physical/PatternMatcher.hpp"
 #include "query_optimizer/physical/Physical.hpp"
 #include "query_optimizer/physical/PhysicalType.hpp"
 #include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "utility/DisjointTreeForest.hpp"
 
 #include "glog/logging.h"
 
@@ -74,6 +76,9 @@ P::PhysicalPtr 
StarSchemaHashJoinOrderOptimization::applyInternal(const P::Physi
     JoinGroupInfo *join_group = nullptr;
     if (parent_join_group == nullptr || !is_valid_cascading_hash_join) {
       new_join_group.reset(new JoinGroupInfo());
+      for (const auto &attr : input->getOutputAttributes()) {
+        new_join_group->referenced_attributes.emplace(attr->id());
+      }
       join_group = new_join_group.get();
     } else {
       join_group = parent_join_group;
@@ -146,7 +151,10 @@ physical::PhysicalPtr 
StarSchemaHashJoinOrderOptimization::generatePlan(
         i,
         tables[i],
         cost_model_->estimateCardinality(tables[i]),
-        cost_model_->estimateSelectivity(tables[i]));
+        cost_model_->estimateSelectivity(tables[i]),
+        CountSharedAttributes(join_group.referenced_attributes,
+                              tables[i]->getOutputAttributes()),
+        tables[i]->getPhysicalType() == physical::PhysicalType::kAggregate);
   }
 
   // Auxiliary mapping info.
@@ -163,9 +171,25 @@ physical::PhysicalPtr 
StarSchemaHashJoinOrderOptimization::generatePlan(
     }
   }
 
-  // Create a join graph where tables are vertices, and add an edge between 
vertices
-  // t1 and t2 for each join predicate t1.x = t2.y
-  std::vector<std::unordered_set<std::size_t>> 
join_graph(table_info_storage.size());
+  // The pool of tables.
+  std::set<TableInfo*> remaining_tables;
+  for (auto &table_info : table_info_storage) {
+    remaining_tables.emplace(&table_info);
+  }
+
+  // The equal-join (e.g. =) operator defines an equivalence relation on the
+  // set of all the attributes. The disjoint set data structure is used to keep
+  // track of the equivalence classes that each attribute belongs to.
+  DisjointTreeForest<E::ExprId> join_attribute_forest;
+  for (const auto &attr_id_pair : join_group.join_attribute_pairs) {
+    join_attribute_forest.makeSet(attr_id_pair.first);
+    join_attribute_forest.makeSet(attr_id_pair.second);
+    join_attribute_forest.merge(attr_id_pair.first, attr_id_pair.second);
+  }
+
+  // Map each equivalence class id to the members (e.g. <table id, attribute 
id>
+  // pairs) in that equivalence class.
+  std::map<std::size_t, std::map<std::size_t, E::ExprId>> 
join_attribute_groups;
   for (const auto &attr_id_pair : join_group.join_attribute_pairs) {
     DCHECK(attribute_id_to_table_info_index_map.find(attr_id_pair.first)
                != attribute_id_to_table_info_index_map.end());
@@ -178,128 +202,148 @@ physical::PhysicalPtr 
StarSchemaHashJoinOrderOptimization::generatePlan(
         attribute_id_to_table_info_index_map[attr_id_pair.second];
     DCHECK_NE(first_table_idx, second_table_idx);
 
-    table_info_storage[first_table_idx].join_attribute_pairs.emplace(
-        attr_id_pair.first, attr_id_pair.second);
-    table_info_storage[second_table_idx].join_attribute_pairs.emplace(
-        attr_id_pair.second, attr_id_pair.first);
-
-    join_graph[first_table_idx].emplace(second_table_idx);
-    join_graph[second_table_idx].emplace(first_table_idx);
-  }
-
-  std::set<TableInfo*, TableInfoPtrLessComparator> 
table_info_ordered_by_priority;
-  for (std::size_t i = 0; i < table_info_storage.size(); ++i) {
-    table_info_ordered_by_priority.emplace(&table_info_storage[i]);
+    DCHECK_EQ(join_attribute_forest.find(attr_id_pair.first),
+              join_attribute_forest.find(attr_id_pair.second));
+    const std::size_t attr_group_id = 
join_attribute_forest.find(attr_id_pair.first);
+    auto &attr_group = join_attribute_groups[attr_group_id];
+    attr_group.emplace(first_table_idx, attr_id_pair.first);
+    attr_group.emplace(second_table_idx, attr_id_pair.second);
   }
 
-  // Contruct hash join tree.
   while (true) {
-    TableInfo *first_table_info = *table_info_ordered_by_priority.begin();
-    table_info_ordered_by_priority.erase(
-        table_info_ordered_by_priority.begin());
-    const std::size_t first_table_info_id = first_table_info->table_info_id;
-
-    TableInfo *second_table_info = nullptr;
-    std::set<TableInfo*, TableInfoPtrLessComparator>::iterator 
second_table_info_it;
-    for (auto candidate_table_info_it = table_info_ordered_by_priority.begin();
-         candidate_table_info_it != table_info_ordered_by_priority.end();
-         ++candidate_table_info_it) {
-      TableInfo *candidate_table_info = *candidate_table_info_it;
-      const std::size_t candidate_table_info_id = 
candidate_table_info->table_info_id;
-
-      if (join_graph[first_table_info_id].find(candidate_table_info_id)
-              == join_graph[first_table_info_id].end() &&
-          join_graph[candidate_table_info_id].find(first_table_info_id)
-              == join_graph[candidate_table_info_id].end()) {
-        continue;
-      } else if (second_table_info == nullptr) {
-        second_table_info = candidate_table_info;
-        second_table_info_it = candidate_table_info_it;
-      }
-
-      bool is_likely_many_to_many_join = false;
-      for (const auto join_attr_pair : first_table_info->join_attribute_pairs) 
{
-        if 
(candidate_table_info->joined_attribute_set.find(join_attr_pair.second)
-                != candidate_table_info->joined_attribute_set.end()) {
-          is_likely_many_to_many_join = true;
-          break;
+    // Find the best probe/build pair out of the remaining tables.
+    // TODO(jianqiao): design better data structure to improve efficiency here.
+    std::unique_ptr<JoinPair> best_join = nullptr;
+    for (TableInfo *probe_table_info : remaining_tables) {
+      for (TableInfo *build_table_info : remaining_tables) {
+        if (probe_table_info != build_table_info) {
+          const std::size_t probe_table_id = probe_table_info->table_info_id;
+          const std::size_t build_table_id = build_table_info->table_info_id;
+          std::size_t num_join_attributes = 0;
+          double build_side_uniqueness = 1.0;
+          for (const auto &attr_group_pair : join_attribute_groups) {
+            const auto &attr_group = attr_group_pair.second;
+            auto probe_it = attr_group.find(probe_table_id);
+            auto build_it = attr_group.find(build_table_id);
+            if (probe_it != attr_group.end() && build_it != attr_group.end()) {
+              ++num_join_attributes;
+              build_side_uniqueness *= std::max(
+                  1uL,
+                  cost_model_->estimateNumDistinctValues(
+                      build_it->second, build_table_info->table));
+            }
+          }
+          build_side_uniqueness /= build_table_info->estimated_cardinality;
+
+          if (num_join_attributes > 0) {
+            std::unique_ptr<JoinPair> new_join(
+                new JoinPair(probe_table_info,
+                             build_table_info,
+                             build_side_uniqueness >= 0.9,
+                             num_join_attributes));
+            if (best_join == nullptr || new_join->isBetterThan(*best_join)) {
+              best_join.reset(new_join.release());
+            }
+          }
         }
       }
-      for (const auto join_attr_pair : 
candidate_table_info->join_attribute_pairs) {
-        if (first_table_info->joined_attribute_set.find(join_attr_pair.second)
-                != first_table_info->joined_attribute_set.end()) {
-          is_likely_many_to_many_join = true;
-          break;
-        }
-      }
-      if (!is_likely_many_to_many_join) {
-        second_table_info = candidate_table_info;
-        second_table_info_it = candidate_table_info_it;
-        break;
+    }
+
+    CHECK(best_join != nullptr);
+
+    TableInfo *selected_probe_table_info = best_join->probe;
+    TableInfo *selected_build_table_info = best_join->build;
+
+    // Swap probe/build sides if:
+    // (1) Build side is an aggregation with large number of groups, so that
+    //     there is a change to push LIPFilters down the aggregation.
+    // (2) Build side's join attributes are not unique, and it has larger
+    //     cardinality than the probe side.
+    const std::size_t probe_num_groups_as_agg =
+        getEstimatedNumGroups(selected_probe_table_info->table);
+    const std::size_t build_num_groups_as_agg =
+        getEstimatedNumGroups(selected_build_table_info->table);
+    if (build_num_groups_as_agg > 1000000 || probe_num_groups_as_agg > 
1000000) {
+      if (build_num_groups_as_agg > probe_num_groups_as_agg) {
+        std::swap(selected_probe_table_info, selected_build_table_info);
       }
+    } else if ((!best_join->build_side_unique || 
best_join->num_join_attributes > 1) &&
+        selected_probe_table_info->estimated_cardinality < 
selected_build_table_info->estimated_cardinality) {
+      std::swap(selected_probe_table_info, selected_build_table_info);
     }
-    DCHECK(second_table_info != nullptr);
-    table_info_ordered_by_priority.erase(second_table_info_it);
 
-    const P::PhysicalPtr &left_child = first_table_info->table;
-    const P::PhysicalPtr &right_child = second_table_info->table;
+    remaining_tables.erase(selected_probe_table_info);
+    remaining_tables.erase(selected_build_table_info);
+
+    // Figure out the output attributes.
+    const P::PhysicalPtr &probe_child = selected_probe_table_info->table;
+    const P::PhysicalPtr &build_child = selected_build_table_info->table;
     std::vector<E::NamedExpressionPtr> output_attributes;
-    for (const E::AttributeReferencePtr &left_attr : 
left_child->getOutputAttributes()) {
-      output_attributes.emplace_back(left_attr);
+    for (const E::AttributeReferencePtr &probe_attr : 
probe_child->getOutputAttributes()) {
+      output_attributes.emplace_back(probe_attr);
     }
-    for (const E::AttributeReferencePtr &right_attr : 
right_child->getOutputAttributes()) {
-      output_attributes.emplace_back(right_attr);
+    for (const E::AttributeReferencePtr &build_attr : 
build_child->getOutputAttributes()) {
+      output_attributes.emplace_back(build_attr);
     }
 
-    std::vector<E::AttributeReferencePtr> left_join_attributes;
-    std::vector<E::AttributeReferencePtr> right_join_attributes;
-    std::unordered_set<expressions::ExprId> new_joined_attribute_set;
-    for (const auto &join_attr_pair : first_table_info->join_attribute_pairs) {
-      if (second_table_info->join_attribute_pairs.find(join_attr_pair.second)
-              != second_table_info->join_attribute_pairs.end()) {
-        left_join_attributes.emplace_back(
-            attribute_id_to_reference_map[join_attr_pair.first]);
-        right_join_attributes.emplace_back(
-            attribute_id_to_reference_map[join_attr_pair.second]);
-
-        new_joined_attribute_set.emplace(join_attr_pair.first);
-        new_joined_attribute_set.emplace(join_attr_pair.second);
+    // Figure out the join attributes.
+    std::vector<E::AttributeReferencePtr> probe_attributes;
+    std::vector<E::AttributeReferencePtr> build_attributes;
+    const std::size_t probe_table_id = 
selected_probe_table_info->table_info_id;
+    const std::size_t build_table_id = 
selected_build_table_info->table_info_id;
+    for (const auto &attr_group_pair : join_attribute_groups) {
+      const auto &attr_group = attr_group_pair.second;
+      auto probe_it = attr_group.find(probe_table_id);
+      auto build_it = attr_group.find(build_table_id);
+      if (probe_it != attr_group.end() && build_it != attr_group.end()) {
+        probe_attributes.emplace_back(
+            attribute_id_to_reference_map.at(probe_it->second));
+        build_attributes.emplace_back(
+            attribute_id_to_reference_map.at(build_it->second));
       }
     }
-    DCHECK_GE(left_join_attributes.size(), static_cast<std::size_t>(1));
 
-    if (table_info_ordered_by_priority.size() > 0) {
+    // Create a hash join from the choosen probe/build pair and put it back to
+    // the table pool. Return the last table in the table pool if there is only
+    // one table left.
+    if (remaining_tables.size() > 0) {
       P::PhysicalPtr output =
-          P::HashJoin::Create(left_child,
-                              right_child,
-                              left_join_attributes,
-                              right_join_attributes,
+          P::HashJoin::Create(probe_child,
+                              build_child,
+                              probe_attributes,
+                              build_attributes,
                               nullptr,
                               output_attributes,
                               P::HashJoin::JoinType::kInnerJoin);
 
-      second_table_info->table = output;
+      selected_probe_table_info->table = output;
 
       // TODO(jianqiao): Cache the estimated cardinality for each plan in cost
       // model to avoid duplicated estimation.
-      second_table_info->estimated_cardinality = 
cost_model_->estimateCardinality(output);
-
-      
second_table_info->join_attribute_pairs.insert(first_table_info->join_attribute_pairs.begin(),
-                                                     
first_table_info->join_attribute_pairs.end());
-      
second_table_info->joined_attribute_set.insert(first_table_info->joined_attribute_set.begin(),
-                                                     
first_table_info->joined_attribute_set.end());
-      
second_table_info->joined_attribute_set.insert(new_joined_attribute_set.begin(),
-                                                     
new_joined_attribute_set.end());
-      table_info_ordered_by_priority.emplace(second_table_info);
-
-      
join_graph[second_table_info->table_info_id].insert(join_graph[first_table_info_id].begin(),
-                                                          
join_graph[first_table_info_id].end());
-
+      selected_probe_table_info->estimated_cardinality = 
cost_model_->estimateCardinality(output);
+      selected_probe_table_info->estimated_selectivity = 
cost_model_->estimateSelectivity(output);
+
+      selected_probe_table_info->estimated_num_output_attributes =
+          CountSharedAttributes(join_group.referenced_attributes,
+                                output->getOutputAttributes());
+
+      remaining_tables.emplace(selected_probe_table_info);
+
+      // Update join attribute groups.
+      for (auto &attr_group_pair : join_attribute_groups) {
+        auto &attr_group = attr_group_pair.second;
+        auto build_it = attr_group.find(build_table_id);
+        if (build_it != attr_group.end()) {
+          const E::ExprId attr_id = build_it->second;
+          attr_group.erase(build_it);
+          attr_group.emplace(probe_table_id, attr_id);
+        }
+      }
     } else {
-      return P::HashJoin::Create(left_child,
-                                 right_child,
-                                 left_join_attributes,
-                                 right_join_attributes,
+      return P::HashJoin::Create(probe_child,
+                                 build_child,
+                                 probe_attributes,
+                                 build_attributes,
                                  residual_predicate,
                                  project_expressions,
                                  P::HashJoin::JoinType::kInnerJoin);
@@ -307,5 +351,28 @@ physical::PhysicalPtr 
StarSchemaHashJoinOrderOptimization::generatePlan(
   }
 }
 
+std::size_t StarSchemaHashJoinOrderOptimization::CountSharedAttributes(
+    const std::unordered_set<expressions::ExprId> &attr_set1,
+    const std::vector<expressions::AttributeReferencePtr> &attr_set2) {
+  std::size_t cnt = 0;
+  for (const auto &attr : attr_set2) {
+    if (attr_set1.find(attr->id()) != attr_set1.end()) {
+      ++cnt;
+    }
+  }
+  return cnt;
+}
+
+std::size_t StarSchemaHashJoinOrderOptimization::getEstimatedNumGroups(
+    const physical::PhysicalPtr &input) {
+  P::AggregatePtr aggregate;
+  if (P::SomeAggregate::MatchesWithConditionalCast(input, &aggregate)) {
+    return cost_model_->estimateNumGroupsForAggregate(aggregate);
+  } else {
+    return 0;
+  }
+}
+
+
 }  // namespace optimizer
 }  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp 
b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp
index c1a7bae..347baf1 100644
--- a/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp
+++ b/query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp
@@ -45,7 +45,11 @@ namespace optimizer {
  */
 
 /**
- * @brief TODO
+ * @brief Rule that applies to a physical plan to optimize hash join orders.
+ *
+ * This optimization applies a greedy algorithm to favor smaller cardinality
+ * and selective tables to be joined first, which is suitable for queries on
+ * star-schema or snowflake-schema tables.
  */
 class StarSchemaHashJoinOrderOptimization : public Rule<physical::Physical> {
  public:
@@ -64,6 +68,7 @@ class StarSchemaHashJoinOrderOptimization : public 
Rule<physical::Physical> {
    * @brief A group of tables to form a hash join tree.
    */
   struct JoinGroupInfo {
+    std::unordered_set<expressions::ExprId> referenced_attributes;
     std::vector<physical::PhysicalPtr> tables;
     std::vector<std::pair<expressions::ExprId, expressions::ExprId>> 
join_attribute_pairs;
   };
@@ -72,49 +77,91 @@ class StarSchemaHashJoinOrderOptimization : public 
Rule<physical::Physical> {
    * @brief Auxiliary information of a table for the optimizer.
    */
   struct TableInfo {
-    TableInfo(const std::size_t in_table_info_id,
-              const physical::PhysicalPtr &in_table,
-              const std::size_t in_estimated_cardinality,
-              const double in_estimated_selectivity)
-        : table_info_id(in_table_info_id),
-          table(in_table),
-          estimated_cardinality(in_estimated_cardinality),
-          estimated_selectivity(in_estimated_selectivity) {
+    TableInfo(const std::size_t table_info_id_in,
+              const physical::PhysicalPtr &table_in,
+              const std::size_t estimated_cardinality_in,
+              const double estimated_selectivity_in,
+              const std::size_t estimated_num_output_attributes_in,
+              const bool is_aggregation_in)
+        : table_info_id(table_info_id_in),
+          table(table_in),
+          estimated_cardinality(estimated_cardinality_in),
+          estimated_selectivity(estimated_selectivity_in),
+          estimated_num_output_attributes(estimated_num_output_attributes_in) {
     }
 
     const std::size_t table_info_id;
     physical::PhysicalPtr table;
     std::size_t estimated_cardinality;
     double estimated_selectivity;
-    std::unordered_multimap<expressions::ExprId, expressions::ExprId> 
join_attribute_pairs;
-    std::unordered_set<expressions::ExprId> joined_attribute_set;
+    std::size_t estimated_num_output_attributes;
   };
 
-  /**
-   * @brief Comparator that compares the join priorities between two tables.
-   */
-  struct TableInfoPtrLessComparator {
-    inline bool operator() (const TableInfo *lhs, const TableInfo *rhs) {
-      bool swapped = false;
-      if (lhs->estimated_cardinality > rhs->estimated_cardinality) {
-        std::swap(lhs, rhs);
-        swapped = true;
+  struct JoinPair {
+    JoinPair(TableInfo *probe_in,
+             TableInfo *build_in,
+             const bool build_side_unique_in,
+             const std::size_t num_join_attributes_in)
+        : probe(probe_in),
+          build(build_in),
+          build_side_unique(build_side_unique_in),
+          num_join_attributes(num_join_attributes_in) {
+    }
+
+    inline bool isBetterThan(const JoinPair &rhs) const {
+      const auto &lhs = *this;
+
+      // Avoid carrying too many output attributes all the way through a long
+      // chain of hash joins.
+      const bool lhs_has_large_output =
+          lhs.build->estimated_num_output_attributes
+              + lhs.probe->estimated_num_output_attributes > 5;
+      const bool rhs_has_large_output =
+          rhs.build->estimated_num_output_attributes
+              + rhs.probe->estimated_num_output_attributes > 5;
+      if (lhs_has_large_output != rhs_has_large_output) {
+        return rhs_has_large_output;
+      }
+
+      // Prefer foreign-key primary-key style hash joins.
+      if (lhs.build_side_unique != rhs.build_side_unique) {
+        return lhs.build_side_unique;
+      }
+
+      // Prefer hash joins where the build side table is small.
+      const bool lhs_has_small_build = lhs.build->estimated_cardinality < 
0x100;
+      const bool rhs_has_small_build = rhs.build->estimated_cardinality < 
0x100;
+      if (lhs_has_small_build != rhs_has_small_build) {
+        return lhs_has_small_build;
       }
 
-      if (lhs->estimated_selectivity < rhs->estimated_selectivity) {
-        return !swapped;
-      } else if (lhs->estimated_cardinality < 100u &&
-                 rhs->estimated_cardinality > 10000u &&
-                 lhs->estimated_selectivity < rhs->estimated_selectivity * 
1.5) {
-        return !swapped;
-      } else if (lhs->estimated_selectivity > rhs->estimated_selectivity) {
-        return swapped;
-      } else if (lhs->estimated_cardinality != rhs->estimated_cardinality) {
-        return !swapped;
+      // Prefer hash joins where the probe side table is small. This is 
effective
+      // for TPCH style (snowflake schema) queries, with the help of 
LIPFilters.
+      if (lhs.probe->estimated_cardinality != 
rhs.probe->estimated_cardinality) {
+        return lhs.probe->estimated_cardinality < 
rhs.probe->estimated_cardinality;
+      }
+
+      // Prefer build side tables with better selectivity. This is effective
+      // for SSB style queries.
+      if (lhs.build->estimated_selectivity != 
rhs.build->estimated_selectivity) {
+        return lhs.build->estimated_selectivity < 
rhs.build->estimated_selectivity;
+      }
+
+      // Residual rules that help provide a total order.
+      if (lhs.build->estimated_cardinality != 
rhs.build->estimated_cardinality) {
+        return lhs.build->estimated_cardinality < 
rhs.build->estimated_cardinality;
+      }
+      if (lhs.probe->table != rhs.probe->table) {
+        return lhs.probe->table < rhs.probe->table;
       } else {
-        return swapped ^ (lhs->table < rhs->table);
+        return lhs.build->table < rhs.build->table;
       }
     }
+
+    TableInfo *probe;
+    TableInfo *build;
+    const bool build_side_unique;
+    const std::size_t num_join_attributes;
   };
 
   physical::PhysicalPtr applyInternal(const physical::PhysicalPtr &input,
@@ -125,6 +172,12 @@ class StarSchemaHashJoinOrderOptimization : public 
Rule<physical::Physical> {
       const expressions::PredicatePtr &residual_predicate,
       const std::vector<expressions::NamedExpressionPtr> &project_expressions);
 
+  std::size_t getEstimatedNumGroups(const physical::PhysicalPtr &input);
+
+  static std::size_t CountSharedAttributes(
+      const std::unordered_set<expressions::ExprId> &attr_set1,
+      const std::vector<expressions::AttributeReferencePtr> &attr_set2);
+
   std::unique_ptr<cost::StarSchemaSimpleCostModel> cost_model_;
 
   DISALLOW_COPY_AND_ASSIGN(StarSchemaHashJoinOrderOptimization);

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/03ca4cd3/query_optimizer/tests/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/CMakeLists.txt 
b/query_optimizer/tests/CMakeLists.txt
index 597dbe0..ac4548a 100644
--- a/query_optimizer/tests/CMakeLists.txt
+++ b/query_optimizer/tests/CMakeLists.txt
@@ -94,22 +94,6 @@ 
add_executable(quickstep_queryoptimizer_tests_ExecutionGeneratorTest
                ExecutionGeneratorTestRunner.hpp
                "${PROJECT_SOURCE_DIR}/utility/textbased_test/TextBasedTest.cpp"
                
"${PROJECT_SOURCE_DIR}/utility/textbased_test/TextBasedTest.hpp")
-add_executable(ExecutionHeuristics_unittest ExecutionHeuristics_unittest.cpp)
-target_link_libraries(ExecutionHeuristics_unittest
-                      gtest
-                      gtest_main
-                      quickstep_catalog_Catalog
-                      quickstep_catalog_CatalogDatabase
-                      quickstep_catalog_CatalogTypedefs
-                      quickstep_queryexecution_QueryContext
-                      quickstep_queryexecution_QueryContext_proto
-                      quickstep_queryoptimizer_ExecutionHeuristics
-                      quickstep_queryoptimizer_QueryPlan
-                      quickstep_relationaloperators_BuildHashOperator
-                      quickstep_relationaloperators_HashJoinOperator
-                      quickstep_utility_Macros)
-add_test(ExecutionHeuristics_unittest ExecutionHeuristics_unittest)
-
 add_executable(quickstep_queryoptimizer_tests_OptimizerTextTest
                OptimizerTextTest.cpp
                OptimizerTextTestRunner.cpp

Reply via email to