quickstep-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hakanmemiso...@apache.org
Subject [08/11] incubator-quickstep git commit: Implement optimizer and execution layers for UNION and INTERSECT.
Date Tue, 02 May 2017 05:13:20 GMT
Implement optimizer and execution layers for UNION and INTERSECT.


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

Branch: refs/heads/frontend-backend
Commit: f1434eb9a4ecf43039445fbecf2d8d1d7802b20b
Parents: 46e4113
Author: Tianrun <Tianrun@node-0.tianrun-qv23700.quickstep-pg0.wisc.cloudlab.us>
Authored: Mon Apr 10 10:21:11 2017 -0600
Committer: Hakan Memisoglu <hakanmemisoglu@apache.org>
Committed: Tue May 2 00:12:54 2017 -0500

----------------------------------------------------------------------
 query_optimizer/CMakeLists.txt                  |   2 +
 query_optimizer/ExecutionGenerator.cpp          |  68 +++++
 query_optimizer/ExecutionGenerator.hpp          |   8 +
 query_optimizer/cost_model/CMakeLists.txt       |   2 +
 query_optimizer/cost_model/SimpleCostModel.cpp  |  13 +
 query_optimizer/cost_model/SimpleCostModel.hpp  |   6 +
 .../cost_model/StarSchemaSimpleCostModel.cpp    |  12 +
 .../cost_model/StarSchemaSimpleCostModel.hpp    |   6 +-
 query_optimizer/physical/CMakeLists.txt         |  10 +
 query_optimizer/physical/PhysicalType.hpp       |   1 +
 query_optimizer/physical/UnionAll.hpp           | 188 +++++++++++++
 query_optimizer/resolver/Resolver.cpp           |   6 +-
 query_optimizer/strategy/CMakeLists.txt         |   5 +
 query_optimizer/strategy/Join.cpp               |  42 +++
 query_optimizer/strategy/OneToOne.cpp           |  30 ++
 .../tests/execution_generator/Select.test       |  86 ++++++
 .../tests/physical_generator/Select.test        | 280 +++++++++++++++++++
 query_optimizer/tests/resolver/CMakeLists.txt   |   4 +
 .../tests/resolver/SetOperation.test            | 185 ++++++++++++
 relational_operators/CMakeLists.txt             |  16 ++
 relational_operators/RelationalOperator.hpp     |   1 +
 relational_operators/UnionAllOperator.cpp       | 144 ++++++++++
 relational_operators/UnionAllOperator.hpp       | 228 +++++++++++++++
 23 files changed, 1339 insertions(+), 4 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index 79710fb..176b071 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -121,6 +121,7 @@ target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
                       quickstep_queryoptimizer_physical_TableGenerator
                       quickstep_queryoptimizer_physical_TableReference
                       quickstep_queryoptimizer_physical_TopLevelPlan
+                      quickstep_queryoptimizer_physical_UnionAll
                       quickstep_queryoptimizer_physical_UpdateTable
                       quickstep_queryoptimizer_physical_WindowAggregate
                       quickstep_relationaloperators_AggregationOperator
@@ -146,6 +147,7 @@ target_link_libraries(quickstep_queryoptimizer_ExecutionGenerator
                       quickstep_relationaloperators_SortRunGenerationOperator
                       quickstep_relationaloperators_TableGeneratorOperator
                       quickstep_relationaloperators_TextScanOperator
+                      quickstep_relationaloperators_UnionAllOperator
                       quickstep_relationaloperators_UpdateOperator
                       quickstep_relationaloperators_WindowAggregationOperator
                       quickstep_storage_AggregationOperationState_proto

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/ExecutionGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.cpp b/query_optimizer/ExecutionGenerator.cpp
index 2878918..36015a9 100644
--- a/query_optimizer/ExecutionGenerator.cpp
+++ b/query_optimizer/ExecutionGenerator.cpp
@@ -94,6 +94,7 @@
 #include "query_optimizer/physical/TableGenerator.hpp"
 #include "query_optimizer/physical/TableReference.hpp"
 #include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/physical/UnionAll.hpp"
 #include "query_optimizer/physical/UpdateTable.hpp"
 #include "query_optimizer/physical/WindowAggregate.hpp"
 #include "relational_operators/AggregationOperator.hpp"
@@ -119,6 +120,7 @@
 #include "relational_operators/SortRunGenerationOperator.hpp"
 #include "relational_operators/TableGeneratorOperator.hpp"
 #include "relational_operators/TextScanOperator.hpp"
+#include "relational_operators/UnionAllOperator.hpp"
 #include "relational_operators/UpdateOperator.hpp"
 #include "relational_operators/WindowAggregationOperator.hpp"
 #include "storage/AggregationOperationState.pb.h"
@@ -315,6 +317,9 @@ void ExecutionGenerator::generatePlanInternal(
     case P::PhysicalType::kTableReference:
       return convertTableReference(
           std::static_pointer_cast<const P::TableReference>(physical_plan));
+    case P::PhysicalType::kUnionAll:
+      return convertUnionAll(
+          std::static_pointer_cast<const P::UnionAll>(physical_plan));
     case P::PhysicalType::kUpdateTable:
       return convertUpdateTable(
           std::static_pointer_cast<const P::UpdateTable>(physical_plan));
@@ -1388,6 +1393,69 @@ void ExecutionGenerator::convertInsertSelection(
                                        false /* is_pipeline_breaker */);
 }
 
+void ExecutionGenerator::convertUnionAll(
+    const P::UnionAllPtr &physical_unionall) {
+  const CatalogRelation *output_relation = nullptr;
+  const QueryContext::insert_destination_id insert_destination_index =
+      query_context_proto_->insert_destinations_size();
+  S::InsertDestination *insert_destination_proto =
+      query_context_proto_->add_insert_destinations();
+  createTemporaryCatalogRelation(physical_unionall,
+                                 &output_relation,
+                                 insert_destination_proto);
+
+  const std::vector<P::PhysicalPtr> &operands = physical_unionall->operands();
+  std::vector<const CatalogRelation*> input_relations;
+  std::vector<bool> is_stored_relation;
+  std::vector<std::vector<attribute_id>> select_attribute_ids;
+  std::vector<QueryPlan::DAGNodeIndex> dependency_operator_index;
+
+  for (const auto &operand : operands) {
+    const CatalogRelationInfo *input_relation_info =
+        findRelationInfoOutputByPhysical(operand);
+    DCHECK(input_relation_info != nullptr);
+    input_relations.push_back(input_relation_info->relation);
+    is_stored_relation.push_back(input_relation_info->isStoredRelation());
+    dependency_operator_index.push_back(input_relation_info->producer_operator_index);
+
+    const QueryContext::scalar_group_id project_expressions_group_index =
+        query_context_proto_->scalar_groups_size();
+    convertNamedExpressions(
+        E::ToNamedExpressions(operand->getOutputAttributes()),
+        query_context_proto_->add_scalar_groups());
+    std::vector<attribute_id> select_attribute_id;
+    convertSimpleProjection(project_expressions_group_index, &select_attribute_id);
+    select_attribute_ids.push_back(std::move(select_attribute_id));
+  }
+
+  UnionAllOperator *union_all =
+      new UnionAllOperator(query_handle_->query_id(),
+                           input_relations,
+                           *output_relation,
+                           insert_destination_index,
+                           is_stored_relation,
+                           select_attribute_ids);
+
+  const QueryPlan::DAGNodeIndex union_all_index =
+      execution_plan_->addRelationalOperator(union_all);
+  insert_destination_proto->set_relational_op_index(union_all_index);
+
+  for (std::size_t relation_id = 0; relation_id < is_stored_relation.size(); ++relation_id) {
+    if (!is_stored_relation[relation_id]) {
+      execution_plan_->addDirectDependency(union_all_index,
+                                           dependency_operator_index[relation_id],
+                                           false /* is_pipeline_breaker */);
+    }
+  }
+
+  physical_to_output_relation_map_.emplace(
+      std::piecewise_construct,
+      std::forward_as_tuple(physical_unionall),
+      std::forward_as_tuple(union_all_index,
+                            output_relation));
+  temporary_relation_info_vec_.emplace_back(union_all_index, output_relation);
+}
+
 void ExecutionGenerator::convertUpdateTable(
     const P::UpdateTablePtr &physical_plan) {
   // UpdateTable is converted to an Update and a SaveBlocks.

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/ExecutionGenerator.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.hpp b/query_optimizer/ExecutionGenerator.hpp
index 86f7264..3b257a8 100644
--- a/query_optimizer/ExecutionGenerator.hpp
+++ b/query_optimizer/ExecutionGenerator.hpp
@@ -62,6 +62,7 @@
 #include "query_optimizer/physical/TableGenerator.hpp"
 #include "query_optimizer/physical/TableReference.hpp"
 #include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/physical/UnionAll.hpp"
 #include "query_optimizer/physical/UpdateTable.hpp"
 #include "query_optimizer/physical/WindowAggregate.hpp"
 #include "utility/Macros.hpp"
@@ -328,6 +329,13 @@ class ExecutionGenerator {
   void convertInsertTuple(const physical::InsertTuplePtr &physical_plan);
 
   /**
+   * @brief Converts a physical UnionAll to an UnionAll operator.
+   *
+   * @param physical_plan The UnionAll to be converted.
+   */
+  void convertUnionAll(const physical::UnionAllPtr &physical_plan);
+
+  /**
    * @brief Converts an UpdateTable to an Update and a SaveBlocks.
    *
    * @param physical_plan The UpdateTable to be converted.

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/cost_model/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/CMakeLists.txt b/query_optimizer/cost_model/CMakeLists.txt
index 4042915..3d4ee93 100644
--- a/query_optimizer/cost_model/CMakeLists.txt
+++ b/query_optimizer/cost_model/CMakeLists.txt
@@ -45,6 +45,7 @@ target_link_libraries(quickstep_queryoptimizer_costmodel_SimpleCostModel
                       quickstep_queryoptimizer_physical_TableGenerator
                       quickstep_queryoptimizer_physical_TableReference
                       quickstep_queryoptimizer_physical_TopLevelPlan
+                      quickstep_queryoptimizer_physical_UnionAll
                       quickstep_queryoptimizer_physical_WindowAggregate
                       quickstep_utility_Macros)
 target_link_libraries(quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
@@ -79,6 +80,7 @@ target_link_libraries(quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostMod
                       quickstep_queryoptimizer_physical_TableGenerator
                       quickstep_queryoptimizer_physical_TableReference
                       quickstep_queryoptimizer_physical_TopLevelPlan
+                      quickstep_queryoptimizer_physical_UnionAll
                       quickstep_queryoptimizer_physical_WindowAggregate
                       quickstep_types_NullType
                       quickstep_types_Type

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/cost_model/SimpleCostModel.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/SimpleCostModel.cpp b/query_optimizer/cost_model/SimpleCostModel.cpp
index cfd8a75..cc46c00 100644
--- a/query_optimizer/cost_model/SimpleCostModel.cpp
+++ b/query_optimizer/cost_model/SimpleCostModel.cpp
@@ -38,6 +38,7 @@
 #include "query_optimizer/physical/TableGenerator.hpp"
 #include "query_optimizer/physical/TableReference.hpp"
 #include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/physical/UnionAll.hpp"
 #include "query_optimizer/physical/WindowAggregate.hpp"
 
 #include "glog/logging.h"
@@ -90,6 +91,9 @@ std::size_t SimpleCostModel::estimateCardinality(
     case P::PhysicalType::kWindowAggregate:
       return estimateCardinalityForWindowAggregate(
           std::static_pointer_cast<const P::WindowAggregate>(physical_plan));
+    case P::PhysicalType::kUnionAll:
+      return estimateCardinalityForUnionAll(
+          std::static_pointer_cast<const P::UnionAll>(physical_plan));
     default:
       throw UnsupportedPhysicalPlan(physical_plan);
   }
@@ -163,6 +167,15 @@ std::size_t SimpleCostModel::estimateCardinalityForWindowAggregate(
   return estimateCardinality(physical_plan->input());
 }
 
+std::size_t SimpleCostModel::estimateCardinalityForUnionAll(
+    const physical::UnionAllPtr &physical_plan) {
+  std::size_t cardinality = 0;
+  for (const P::PhysicalPtr &operand : physical_plan->operands()) {
+    cardinality += estimateCardinality(operand);
+  }
+  return cardinality;
+}
+
 }  // namespace cost
 }  // namespace optimizer
 }  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/cost_model/SimpleCostModel.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/SimpleCostModel.hpp b/query_optimizer/cost_model/SimpleCostModel.hpp
index 0660c37..653e115 100644
--- a/query_optimizer/cost_model/SimpleCostModel.hpp
+++ b/query_optimizer/cost_model/SimpleCostModel.hpp
@@ -35,6 +35,7 @@
 #include "query_optimizer/physical/TableGenerator.hpp"
 #include "query_optimizer/physical/TableReference.hpp"
 #include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/physical/UnionAll.hpp"
 #include "query_optimizer/physical/WindowAggregate.hpp"
 #include "utility/Macros.hpp"
 
@@ -109,6 +110,11 @@ class SimpleCostModel : public CostModel {
   std::size_t estimateCardinalityForWindowAggregate(
       const physical::WindowAggregatePtr &physical_plan);
 
+  // Return the estimated cardinality of union all operation,
+  // which is the sum of the cardinality of all children operators.
+  std::size_t estimateCardinalityForUnionAll(
+      const physical::UnionAllPtr &physical_plan);
+
   const std::vector<physical::PhysicalPtr> &shared_subplans_;
 
   DISALLOW_COPY_AND_ASSIGN(SimpleCostModel);

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
index fc775c7..b17fac0 100644
--- a/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.cpp
@@ -55,6 +55,7 @@
 #include "query_optimizer/physical/TableGenerator.hpp"
 #include "query_optimizer/physical/TableReference.hpp"
 #include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/physical/UnionAll.hpp"
 #include "types/Type.hpp"
 #include "types/TypeID.hpp"
 #include "types/TypedValue.hpp"
@@ -118,6 +119,9 @@ std::size_t StarSchemaSimpleCostModel::estimateCardinality(
     case P::PhysicalType::kWindowAggregate:
       return estimateCardinalityForWindowAggregate(
           std::static_pointer_cast<const P::WindowAggregate>(physical_plan));
+    case P::PhysicalType::kUnionAll:
+      return estimateCardinalityForUnionAll(
+          std::static_pointer_cast<const P::UnionAll>(physical_plan));
     default:
       throw UnsupportedPhysicalPlan(physical_plan);
   }
@@ -203,6 +207,14 @@ std::size_t StarSchemaSimpleCostModel::estimateCardinalityForWindowAggregate(
   return estimateCardinality(physical_plan->input());
 }
 
+std::size_t StarSchemaSimpleCostModel::estimateCardinalityForUnionAll(
+    const P::UnionAllPtr &physical_plan) {
+  std::size_t cardinality = 0;
+  for (const P::PhysicalPtr &operand : physical_plan->operands()) {
+    cardinality += estimateCardinality(operand);
+  }
+  return cardinality;
+}
 
 std::size_t StarSchemaSimpleCostModel::estimateNumGroupsForAggregate(
     const physical::AggregatePtr &aggregate) {

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp b/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
index afb2ef9..0461077 100644
--- a/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
+++ b/query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp
@@ -39,6 +39,7 @@
 #include "query_optimizer/physical/TableGenerator.hpp"
 #include "query_optimizer/physical/TableReference.hpp"
 #include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/physical/UnionAll.hpp"
 #include "query_optimizer/physical/WindowAggregate.hpp"
 #include "types/TypedValue.hpp"
 #include "utility/Macros.hpp"
@@ -82,7 +83,7 @@ class StarSchemaSimpleCostModel : public CostModel {
 
   /**
    * @brief Estimate the number of distinct values of an attribute in a relation.
-   * 
+   *
    * @param attribute_id The expression id of the target attribute.
    * @param physical_plan The physical plan of the attribute's relation.
    * @return The estimated number of distinct values for the attribute.
@@ -217,6 +218,9 @@ class StarSchemaSimpleCostModel : public CostModel {
   std::size_t estimateCardinalityForWindowAggregate(
       const physical::WindowAggregatePtr &physical_plan);
 
+  std::size_t estimateCardinalityForUnionAll(
+      const physical::UnionAllPtr &physical_plan);
+
   double estimateSelectivityForPredicate(
       const expressions::PredicatePtr &filter_predicate,
       const physical::PhysicalPtr &physical_plan);

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/physical/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/CMakeLists.txt b/query_optimizer/physical/CMakeLists.txt
index 77ae75e..2751c6e 100644
--- a/query_optimizer/physical/CMakeLists.txt
+++ b/query_optimizer/physical/CMakeLists.txt
@@ -45,6 +45,7 @@ add_library(quickstep_queryoptimizer_physical_Sort Sort.cpp Sort.hpp)
 add_library(quickstep_queryoptimizer_physical_TableGenerator ../../empty_src.cpp TableGenerator.hpp)
 add_library(quickstep_queryoptimizer_physical_TableReference TableReference.cpp TableReference.hpp)
 add_library(quickstep_queryoptimizer_physical_TopLevelPlan TopLevelPlan.cpp TopLevelPlan.hpp)
+add_library(quickstep_queryoptimizer_physical_UnionAll ../../empty_src.cpp UnionAll.hpp)
 add_library(quickstep_queryoptimizer_physical_UpdateTable UpdateTable.cpp UpdateTable.hpp)
 add_library(quickstep_queryoptimizer_physical_WindowAggregate WindowAggregate.cpp WindowAggregate.hpp)
 
@@ -274,6 +275,14 @@ target_link_libraries(quickstep_queryoptimizer_physical_TopLevelPlan
                       quickstep_queryoptimizer_physical_PhysicalType
                       quickstep_utility_Cast
                       quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_physical_UnionAll
+                      quickstep_queryoptimizer_OptimizerTree
+                      quickstep_queryoptimizer_expressions_AttributeReference
+                      quickstep_queryoptimizer_expressions_ExpressionUtil
+                      quickstep_queryoptimizer_physical_Physical
+                      quickstep_queryoptimizer_physical_PhysicalType
+                      quickstep_utility_Cast
+                      quickstep_utility_Macros)
 target_link_libraries(quickstep_queryoptimizer_physical_UpdateTable
                       glog
                       quickstep_queryoptimizer_OptimizerTree
@@ -326,5 +335,6 @@ target_link_libraries(quickstep_queryoptimizer_physical
                       quickstep_queryoptimizer_physical_TableGenerator
                       quickstep_queryoptimizer_physical_TableReference
                       quickstep_queryoptimizer_physical_TopLevelPlan
+                      quickstep_queryoptimizer_physical_UnionAll
                       quickstep_queryoptimizer_physical_UpdateTable
                       quickstep_queryoptimizer_physical_WindowAggregate)

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/physical/PhysicalType.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/PhysicalType.hpp b/query_optimizer/physical/PhysicalType.hpp
index 077bd54..47db7ec 100644
--- a/query_optimizer/physical/PhysicalType.hpp
+++ b/query_optimizer/physical/PhysicalType.hpp
@@ -51,6 +51,7 @@ enum class PhysicalType {
   kTableGenerator,
   kTableReference,
   kTopLevelPlan,
+  kUnionAll,
   kUpdateTable,
   kWindowAggregate
 };

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/physical/UnionAll.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/physical/UnionAll.hpp b/query_optimizer/physical/UnionAll.hpp
new file mode 100644
index 0000000..939249f
--- /dev/null
+++ b/query_optimizer/physical/UnionAll.hpp
@@ -0,0 +1,188 @@
+/**
+ * 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_UNION_ALL_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_UNION_ALL_HPP_
+
+#include <cstddef>
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "query_optimizer/OptimizerTree.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/PhysicalType.hpp"
+#include "utility/Cast.hpp"
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+namespace optimizer {
+namespace physical {
+
+/** \addtogroup OptimizerPhysical
+ *  @{
+ */
+
+class UnionAll;
+typedef std::shared_ptr<const UnionAll> UnionAllPtr;
+
+/**
+ * @brief Perform Union All operation on query results.
+ */
+class UnionAll : public Physical {
+ public:
+  ~UnionAll() override {}
+
+  PhysicalType getPhysicalType() const override {
+    return PhysicalType::kUnionAll;
+  }
+
+  std::string getName() const override {
+    return "UnionAll";
+  }
+
+  /**
+   * @return The operands for the UnionALl operator.
+   */
+  const std::vector<PhysicalPtr>& operands() const {
+    return operands_;
+  }
+
+  PhysicalPtr copyWithNewChildren(
+      const std::vector<PhysicalPtr> &new_children) const override {
+    return Create(new_children, project_attributes_);
+  }
+
+  std::vector<expressions::AttributeReferencePtr> getOutputAttributes() const override {
+    return project_attributes_;
+  }
+
+  std::vector<expressions::AttributeReferencePtr> getReferencedAttributes() const override {
+    std::vector<expressions::AttributeReferencePtr> referenced_attributes;
+    for (const PhysicalPtr &operand : operands_) {
+      const std::vector<expressions::AttributeReferencePtr> reference =
+          operand->getOutputAttributes();
+      referenced_attributes.insert(referenced_attributes.end(),
+                                   reference.begin(),
+                                   reference.end());
+    }
+    return referenced_attributes;
+  }
+
+  bool maybeCopyWithPrunedExpressions(
+      const expressions::UnorderedNamedExpressionSet &referenced_expressions,
+      PhysicalPtr *output) const override {
+    std::vector<std::size_t> expression_index;
+    for (std::size_t i = 0; i < project_attributes_.size(); ++i) {
+      if (referenced_expressions.find(project_attributes_[i]) != referenced_expressions.end()) {
+        expression_index.push_back(i);
+      }
+    }
+
+    if (expression_index.size() == project_attributes_.size()) {
+      return false;
+    }
+
+    std::vector<PhysicalPtr> new_operands;
+    for (std::size_t i = 0; i < operands_.size(); ++i) {
+      // Currently only prune when all children are select.
+      if (operands_[i]->getPhysicalType() != PhysicalType::kSelection) {
+        return false;
+      }
+
+      const auto child_output_attrs = operands_[i]->getOutputAttributes();
+      expressions::UnorderedNamedExpressionSet child_referenced_attrs;
+      for (const std::size_t idx : expression_index) {
+        child_referenced_attrs.emplace(child_output_attrs[idx]);
+      }
+      PhysicalPtr new_operand;
+      if (!operands_[i]->maybeCopyWithPrunedExpressions(
+              child_referenced_attrs, &new_operand)) {
+          return false;
+      }
+      DCHECK_EQ(expression_index.size(), new_operand->getOutputAttributes().size());
+      new_operands.push_back(new_operand);
+    }
+    std::vector<expressions::AttributeReferencePtr> new_project_attributes;
+    for (const std::size_t idx : expression_index) {
+      new_project_attributes.emplace_back(project_attributes_[idx]);
+    }
+    *output = Create(new_operands, new_project_attributes);
+    return true;
+  }
+
+  /**
+   * @brief Creates the physical node of UnionAll.
+   *
+   * @param operands The children physical nodes of UnionAll.
+   * @param project_attributes The project attributes of this UnionAll.
+   * @return An immutable UnionAll node.
+   */
+  static UnionAllPtr Create(
+      const std::vector<PhysicalPtr> &operands,
+      const std::vector<expressions::AttributeReferencePtr> &project_attributes) {
+    return UnionAllPtr(
+        new UnionAll(operands, project_attributes));
+  }
+
+ protected:
+  void getFieldStringItems(
+      std::vector<std::string> *inline_field_names,
+      std::vector<std::string> *inline_field_values,
+      std::vector<std::string> *non_container_child_field_names,
+      std::vector<OptimizerTreeBaseNodePtr> *non_container_child_fields,
+      std::vector<std::string> *container_child_field_names,
+      std::vector<std::vector<OptimizerTreeBaseNodePtr>> *container_child_fields) const override {
+    container_child_field_names->emplace_back("operands");
+    container_child_fields->emplace_back(
+        CastSharedPtrVector<OptimizerTreeBase>(operands_));
+
+    container_child_field_names->emplace_back("project_attributes");
+    container_child_fields->emplace_back(
+        CastSharedPtrVector<OptimizerTreeBase>(project_attributes_));
+  }
+
+ private:
+  UnionAll(const std::vector<PhysicalPtr> &operands,
+           const std::vector<expressions::AttributeReferencePtr> &project_attributes)
+      : operands_(operands),
+        project_attributes_(project_attributes) {
+    for (const PhysicalPtr &operand : operands) {
+      addChild(operand);
+    }
+  }
+
+  const std::vector<PhysicalPtr> operands_;
+  const std::vector<expressions::AttributeReferencePtr> project_attributes_;
+
+  DISALLOW_COPY_AND_ASSIGN(UnionAll);
+};
+
+/** @} */
+
+}  // namespace physical
+}  // namespace optimizer
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_QUERY_OPTIMIZER_PHYSICAL_UNION_ALL_HPP_

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/resolver/Resolver.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/resolver/Resolver.cpp b/query_optimizer/resolver/Resolver.cpp
index 2d3a06b..0f65255 100644
--- a/query_optimizer/resolver/Resolver.cpp
+++ b/query_optimizer/resolver/Resolver.cpp
@@ -1416,13 +1416,13 @@ L::LogicalPtr Resolver::resolveSetOperations(
             THROW_SQL_ERROR_AT(&parse_set_operations)
                 << "There is not a safely coerce between "
                 << current_type.getName()
-                << "and " << possible_type.getName();
+                << " and " << possible_type.getName();
           }
         } else {
           THROW_SQL_ERROR_AT(&parse_set_operations)
-              << "Does not support cast operation between non-numeric types"
+              << "Does not support cast operation with non-numeric types "
               << current_type.getName()
-              << "and " << possible_type.getName();
+              << " and " << possible_type.getName();
         }
       }
     }

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/strategy/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/strategy/CMakeLists.txt b/query_optimizer/strategy/CMakeLists.txt
index 002fa9b..e3e6d76 100644
--- a/query_optimizer/strategy/CMakeLists.txt
+++ b/query_optimizer/strategy/CMakeLists.txt
@@ -59,6 +59,8 @@ target_link_libraries(quickstep_queryoptimizer_strategy_Join
                       quickstep_queryoptimizer_logical_NestedLoopsJoin
                       quickstep_queryoptimizer_logical_PatternMatcher
                       quickstep_queryoptimizer_logical_Project
+                      quickstep_queryoptimizer_logical_SetOperation
+                      quickstep_queryoptimizer_physical_Aggregate
                       quickstep_queryoptimizer_physical_HashJoin
                       quickstep_queryoptimizer_physical_NestedLoopsJoin
                       quickstep_queryoptimizer_physical_PatternMatcher
@@ -83,6 +85,7 @@ target_link_libraries(quickstep_queryoptimizer_strategy_OneToOne
                       quickstep_queryoptimizer_logical_Logical
                       quickstep_queryoptimizer_logical_LogicalType
                       quickstep_queryoptimizer_logical_Sample
+                      quickstep_queryoptimizer_logical_SetOperation
                       quickstep_queryoptimizer_logical_SharedSubplanReference
                       quickstep_queryoptimizer_logical_Sort
                       quickstep_queryoptimizer_logical_TableGenerator
@@ -90,6 +93,7 @@ target_link_libraries(quickstep_queryoptimizer_strategy_OneToOne
                       quickstep_queryoptimizer_logical_TopLevelPlan
                       quickstep_queryoptimizer_logical_UpdateTable
                       quickstep_queryoptimizer_logical_WindowAggregate
+                      quickstep_queryoptimizer_physical_Aggregate
                       quickstep_queryoptimizer_physical_CopyFrom
                       quickstep_queryoptimizer_physical_CreateIndex
                       quickstep_queryoptimizer_physical_CreateTable
@@ -104,6 +108,7 @@ target_link_libraries(quickstep_queryoptimizer_strategy_OneToOne
                       quickstep_queryoptimizer_physical_TableGenerator
                       quickstep_queryoptimizer_physical_TableReference
                       quickstep_queryoptimizer_physical_TopLevelPlan
+                      quickstep_queryoptimizer_physical_UnionAll
                       quickstep_queryoptimizer_physical_UpdateTable
                       quickstep_queryoptimizer_physical_WindowAggregate
                       quickstep_queryoptimizer_strategy_Strategy

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/strategy/Join.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/strategy/Join.cpp b/query_optimizer/strategy/Join.cpp
index cd01bd1..f7d6d24 100644
--- a/query_optimizer/strategy/Join.cpp
+++ b/query_optimizer/strategy/Join.cpp
@@ -37,6 +37,8 @@
 #include "query_optimizer/logical/NestedLoopsJoin.hpp"
 #include "query_optimizer/logical/PatternMatcher.hpp"
 #include "query_optimizer/logical/Project.hpp"
+#include "query_optimizer/logical/SetOperation.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
 #include "query_optimizer/physical/HashJoin.hpp"
 #include "query_optimizer/physical/NestedLoopsJoin.hpp"
 #include "query_optimizer/physical/PatternMatcher.hpp"
@@ -61,6 +63,7 @@ bool Join::generatePlan(const L::LogicalPtr &logical_input,
   L::FilterPtr logical_filter;
   L::HashJoinPtr logical_hash_join;
   L::NestedLoopsJoinPtr logical_nested_loops_join;
+  L::SetOperationPtr logical_set_operation;
 
   // Collapse project-join.
   if (L::SomeProject::MatchesWithConditionalCast(logical_input, &logical_project)) {
@@ -137,6 +140,45 @@ bool Join::generatePlan(const L::LogicalPtr &logical_input,
     }
   }
 
+  // Convert set operations.
+  if (L::SomeSetOperation::MatchesWithConditionalCast(logical_input, &logical_set_operation)) {
+    if (logical_set_operation->getSetOperationType() !=  L::SetOperation::kIntersect) {
+      // Union and UnionAll operations are in OneToOne.cpp.
+      return false;
+    }
+
+    // For Intersect operation, convert it into a physical hash semi join.
+    const std::vector<L::LogicalPtr> &operands = logical_set_operation->getOperands();
+
+    DCHECK_GE(operands.size(), 2u);
+    L::LogicalPtr intermediate = operands[0];
+    for (std::size_t i = 1; i < operands.size(); ++i) {
+      intermediate = L::HashJoin::Create(intermediate,
+                                         operands[i],
+                                         intermediate->getOutputAttributes(),
+                                         operands[i]->getOutputAttributes(),
+                                         nullptr /* residual_predicate */,
+                                         L::HashJoin::JoinType::kLeftSemiJoin);
+    }
+
+    const std::vector<E::NamedExpressionPtr> project_expressions =
+        E::ToNamedExpressions(operands[0]->getOutputAttributes());
+    logical_project = L::Project::Create(intermediate,
+                                         project_expressions);
+
+    P::PhysicalPtr physical_hash_join;
+    addHashJoin(logical_project,
+                nullptr /* logical_filter */,
+                std::static_pointer_cast<const L::HashJoin>(intermediate),
+                &physical_hash_join);
+
+    *physical_output = P::Aggregate::Create(physical_hash_join,
+                                            project_expressions,
+                                            {} /* aggregate_expressions */,
+                                            nullptr /* filter_predicate */);
+    return true;
+  }
+
   // Convert a single binary join.
   if (L::SomeHashJoin::MatchesWithConditionalCast(logical_input, &logical_hash_join)) {
     addHashJoin(nullptr /* logical_project */,

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/strategy/OneToOne.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/strategy/OneToOne.cpp b/query_optimizer/strategy/OneToOne.cpp
index 7d0c4cb..af4e150 100644
--- a/query_optimizer/strategy/OneToOne.cpp
+++ b/query_optimizer/strategy/OneToOne.cpp
@@ -35,6 +35,7 @@
 #include "query_optimizer/logical/InsertTuple.hpp"
 #include "query_optimizer/logical/LogicalType.hpp"
 #include "query_optimizer/logical/Sample.hpp"
+#include "query_optimizer/logical/SetOperation.hpp"
 #include "query_optimizer/logical/SharedSubplanReference.hpp"
 #include "query_optimizer/logical/Sort.hpp"
 #include "query_optimizer/logical/TableGenerator.hpp"
@@ -42,6 +43,7 @@
 #include "query_optimizer/logical/TopLevelPlan.hpp"
 #include "query_optimizer/logical/UpdateTable.hpp"
 #include "query_optimizer/logical/WindowAggregate.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
 #include "query_optimizer/physical/CopyFrom.hpp"
 #include "query_optimizer/physical/CreateIndex.hpp"
 #include "query_optimizer/physical/CreateTable.hpp"
@@ -55,6 +57,7 @@
 #include "query_optimizer/physical/TableGenerator.hpp"
 #include "query_optimizer/physical/TableReference.hpp"
 #include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/physical/UnionAll.hpp"
 #include "query_optimizer/physical/UpdateTable.hpp"
 #include "query_optimizer/physical/WindowAggregate.hpp"
 
@@ -164,6 +167,33 @@ bool OneToOne::generatePlan(const L::LogicalPtr &logical_input,
           sample->percentage());
       return true;
     }
+    case L::LogicalType::kSetOperation: {
+      const L::SetOperationPtr set_operation =
+          std::static_pointer_cast<const L::SetOperation>(logical_input);
+      std::vector<P::PhysicalPtr> physical_operands;
+      for (const L::LogicalPtr &logical : set_operation->getOperands()) {
+        physical_operands.push_back(physical_mapper_->createOrGetPhysicalFromLogical(logical));
+      }
+      if (set_operation->getSetOperationType() == L::SetOperation::kUnionAll) {
+        // For UnionAll operation, convert it into a physical UnionAll.
+        *physical_output = P::UnionAll::Create(physical_operands,
+                                               set_operation->getOutputAttributes());
+        return true;
+      } else if (set_operation->getSetOperationType() == L::SetOperation::kUnion) {
+        // For Union operation, convert it into a physical UnionAll followed by an Aggregate.
+        P::PhysicalPtr union_all = P::UnionAll::Create(physical_operands,
+                                                       set_operation->getOutputAttributes());
+        *physical_output = P::Aggregate::Create(
+            union_all,
+            E::ToNamedExpressions(set_operation->getOutputAttributes()),
+            {} /* aggregate_expression */,
+            nullptr /* filter_predicate */);
+        return true;
+      } else {
+        // INTERSECT is in Join.cpp
+        return false;
+      }
+    }
     case L::LogicalType::kSort: {
       const L::Sort *sort =
           static_cast<const L::Sort*>(logical_input.get());

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/tests/execution_generator/Select.test
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/execution_generator/Select.test b/query_optimizer/tests/execution_generator/Select.test
index 494e759..b3aaaa9 100644
--- a/query_optimizer/tests/execution_generator/Select.test
+++ b/query_optimizer/tests/execution_generator/Select.test
@@ -1072,3 +1072,89 @@ WINDOW w AS
 +------------------------+
 |                     -18|
 +------------------------+
+==
+
+SELECT int_col AS result FROM test
+WHERE int_col < 5
+UNION
+SELECT int_col + 3 AS result FROM test
+WHERE int_col < 5;
+--
++-----------+
+|result     |
++-----------+
+|         -1|
+|          2|
+|         -3|
+|          4|
+|         -5|
+|         -7|
+|         -9|
+|        -11|
+|        -13|
+|        -15|
+|        -17|
+|        -19|
+|        -21|
+|        -23|
+|          5|
+|          0|
+|          7|
+|         -2|
+|         -4|
+|         -6|
+|         -8|
+|        -10|
+|        -12|
+|        -14|
+|        -16|
+|        -18|
+|        -20|
++-----------+
+==
+
+SELECT i + 1 AS result
+FROM generate_series(1, 5) AS gs(i)
+INTERSECT
+SELECT i * 2 AS result
+FROM generate_series(1, 5) AS gs(i)
+--
++-----------+
+|result     |
++-----------+
+|          2|
+|          4|
+|          6|
++-----------+
+==
+
+SELECT float_col FROM test
+WHERE int_col < 5
+ORDER BY int_col DESC
+LIMIT 5
+UNION ALL
+SELECT float_col FROM test
+WHERE int_col < 5
+ORDER BY int_col DESC
+LIMIT 10
+--
++---------------+
+|float_col      |
++---------------+
+|              2|
+|     1.41421354|
+|              1|
+|     1.73205078|
+|     2.23606801|
+|              2|
+|     1.41421354|
+|              1|
+|     1.73205078|
+|     2.23606801|
+|     2.64575124|
+|              3|
+|     3.31662488|
+|     3.60555124|
+|     3.87298346|
++---------------+
+==

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/tests/physical_generator/Select.test
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/physical_generator/Select.test b/query_optimizer/tests/physical_generator/Select.test
index f81cad8..f7de922 100644
--- a/query_optimizer/tests/physical_generator/Select.test
+++ b/query_optimizer/tests/physical_generator/Select.test
@@ -3140,3 +3140,283 @@ TopLevelPlan
   +-AttributeReference[id=7,name=,alias=sum(avg(int_col)),relation=,
     type=Double NULL]
 ==
+
+SELECT int_col FROM test
+UNION
+SELECT int_col FROM test
+--
+[Optimized Logical Plan]
+TopLevelPlan
++-plan=Union[set_operation_type=Union]
+| +-operands=
+| | +-Project
+| | | +-input=TableReference[relation_name=Test,relation_alias=test]
+| | | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | | +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | | |   type=VarChar(20) NULL]
+| | | +-project_list=
+| | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-Project
+| |   +-input=TableReference[relation_name=Test,relation_alias=test]
+| |   | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |   | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| |   | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| |   | +-AttributeReference[id=9,name=double_col,relation=test,type=Double NULL]
+| |   | +-AttributeReference[id=10,name=char_col,relation=test,type=Char(20)]
+| |   | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| |   |   type=VarChar(20) NULL]
+| |   +-project_list=
+| |     +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| +-project_attributes=
+|   +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
++-output_attributes=
+  +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
+[Physical Plan]
+TopLevelPlan
++-plan=Aggregate
+| +-input=UnionAll
+| | +-operands=
+| | | +-Selection
+| | | | +-input=TableReference[relation=Test,alias=test]
+| | | | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | | | +-AttributeReference[id=3,name=double_col,relation=test,
+| | | | | | type=Double NULL]
+| | | | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | | | |   type=VarChar(20) NULL]
+| | | | +-project_expressions=
+| | | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | +-Selection
+| | |   +-input=TableReference[relation=Test,alias=test]
+| | |   | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| | |   | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| | |   | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| | |   | +-AttributeReference[id=9,name=double_col,relation=test,
+| | |   | | type=Double NULL]
+| | |   | +-AttributeReference[id=10,name=char_col,relation=test,type=Char(20)]
+| | |   | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| | |   |   type=VarChar(20) NULL]
+| | |   +-project_expressions=
+| | |     +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| | +-project_attributes=
+| |   +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
+| +-grouping_expressions=
+| | +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
+| +-aggregate_expressions=
+|   +-[]
++-output_attributes=
+  +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
+==
+
+SELECT intv FROM
+  (SELECT int_col, double_col FROM test
+   UNION ALL
+   SELECT int_col, double_col FROM test
+  ) AS temp(intv, doublev)
+--
+[Optimized Logical Plan]
+TopLevelPlan
++-plan=Project
+| +-input=UnionAll[set_operation_type=UnionAll]
+| | +-operands=
+| | | +-Project
+| | | | +-input=TableReference[relation_name=Test,relation_alias=test]
+| | | | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | | | +-AttributeReference[id=3,name=double_col,relation=test,
+| | | | | | type=Double NULL]
+| | | | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | | | |   type=VarChar(20) NULL]
+| | | | +-project_list=
+| | | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | |   +-AttributeReference[id=3,name=double_col,relation=test,
+| | | |     type=Double NULL]
+| | | +-Project
+| | |   +-input=TableReference[relation_name=Test,relation_alias=test]
+| | |   | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| | |   | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| | |   | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| | |   | +-AttributeReference[id=9,name=double_col,relation=test,
+| | |   | | type=Double NULL]
+| | |   | +-AttributeReference[id=10,name=char_col,relation=test,type=Char(20)]
+| | |   | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| | |   |   type=VarChar(20) NULL]
+| | |   +-project_list=
+| | |     +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| | |     +-AttributeReference[id=9,name=double_col,relation=test,
+| | |       type=Double NULL]
+| | +-project_attributes=
+| |   +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
+| |   +-AttributeReference[id=13,name=double_col,relation=,type=Double NULL]
+| +-project_list=
+|   +-Alias[id=14,name=intv,relation=,type=Int NULL]
+|     +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
++-output_attributes=
+  +-AttributeReference[id=14,name=intv,relation=,type=Int NULL]
+[Physical Plan]
+TopLevelPlan
++-plan=Selection
+| +-input=UnionAll
+| | +-operands=
+| | | +-Selection
+| | | | +-input=TableReference[relation=Test,alias=test]
+| | | | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | | | +-AttributeReference[id=3,name=double_col,relation=test,
+| | | | | | type=Double NULL]
+| | | | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | | | |   type=VarChar(20) NULL]
+| | | | +-project_expressions=
+| | | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | +-Selection
+| | |   +-input=TableReference[relation=Test,alias=test]
+| | |   | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| | |   | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| | |   | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| | |   | +-AttributeReference[id=9,name=double_col,relation=test,
+| | |   | | type=Double NULL]
+| | |   | +-AttributeReference[id=10,name=char_col,relation=test,type=Char(20)]
+| | |   | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| | |   |   type=VarChar(20) NULL]
+| | |   +-project_expressions=
+| | |     +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| | +-project_attributes=
+| |   +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
+| +-project_expressions=
+|   +-Alias[id=14,name=intv,relation=,type=Int NULL]
+|     +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
++-output_attributes=
+  +-AttributeReference[id=14,name=intv,relation=,type=Int NULL]
+==
+
+SELECT int_col FROM test
+INTERSECT
+SELECT intv FROM
+  (SELECT int_col, double_col FROM test
+   UNION ALL
+   SELECT int_col, double_col FROM test
+  ) AS temp(intv, doublev)
+--
+[Optimized Logical Plan]
+TopLevelPlan
++-plan=Intersect[set_operation_type=Intersect]
+| +-operands=
+| | +-Project
+| | | +-input=TableReference[relation_name=Test,relation_alias=test]
+| | | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | | +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | | |   type=VarChar(20) NULL]
+| | | +-project_list=
+| | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-Project
+| |   +-input=UnionAll[set_operation_type=UnionAll]
+| |   | +-operands=
+| |   | | +-Project
+| |   | | | +-input=TableReference[relation_name=Test,relation_alias=test]
+| |   | | | | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |   | | | | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| |   | | | | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| |   | | | | +-AttributeReference[id=9,name=double_col,relation=test,
+| |   | | | | | type=Double NULL]
+| |   | | | | +-AttributeReference[id=10,name=char_col,relation=test,
+| |   | | | | | type=Char(20)]
+| |   | | | | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| |   | | | |   type=VarChar(20) NULL]
+| |   | | | +-project_list=
+| |   | | |   +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |   | | |   +-AttributeReference[id=9,name=double_col,relation=test,
+| |   | | |     type=Double NULL]
+| |   | | +-Project
+| |   | |   +-input=TableReference[relation_name=Test,relation_alias=test]
+| |   | |   | +-AttributeReference[id=12,name=int_col,relation=test,
+| |   | |   | | type=Int NULL]
+| |   | |   | +-AttributeReference[id=13,name=long_col,relation=test,type=Long]
+| |   | |   | +-AttributeReference[id=14,name=float_col,relation=test,type=Float]
+| |   | |   | +-AttributeReference[id=15,name=double_col,relation=test,
+| |   | |   | | type=Double NULL]
+| |   | |   | +-AttributeReference[id=16,name=char_col,relation=test,
+| |   | |   | | type=Char(20)]
+| |   | |   | +-AttributeReference[id=17,name=vchar_col,relation=test,
+| |   | |   |   type=VarChar(20) NULL]
+| |   | |   +-project_list=
+| |   | |     +-AttributeReference[id=12,name=int_col,relation=test,
+| |   | |     | type=Int NULL]
+| |   | |     +-AttributeReference[id=15,name=double_col,relation=test,
+| |   | |       type=Double NULL]
+| |   | +-project_attributes=
+| |   |   +-AttributeReference[id=18,name=int_col,relation=,type=Int NULL]
+| |   |   +-AttributeReference[id=19,name=double_col,relation=,type=Double NULL]
+| |   +-project_list=
+| |     +-Alias[id=20,name=intv,relation=,type=Int NULL]
+| |       +-AttributeReference[id=18,name=int_col,relation=,type=Int NULL]
+| +-project_attributes=
+|   +-AttributeReference[id=22,name=int_col,relation=,type=Int NULL]
++-output_attributes=
+  +-AttributeReference[id=22,name=int_col,relation=,type=Int NULL]
+[Physical Plan]
+TopLevelPlan
++-plan=Aggregate
+| +-input=HashLeftSemiJoin
+| | +-left=TableReference[relation=Test,alias=test]
+| | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | |   type=VarChar(20) NULL]
+| | +-right=UnionAll
+| | | +-operands=
+| | | | +-Selection
+| | | | | +-input=TableReference[relation=Test,alias=test]
+| | | | | | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| | | | | | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| | | | | | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| | | | | | +-AttributeReference[id=9,name=double_col,relation=test,
+| | | | | | | type=Double NULL]
+| | | | | | +-AttributeReference[id=10,name=char_col,relation=test,type=Char(20)]
+| | | | | | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| | | | | |   type=VarChar(20) NULL]
+| | | | | +-project_expressions=
+| | | | |   +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| | | | +-Selection
+| | | |   +-input=TableReference[relation=Test,alias=test]
+| | | |   | +-AttributeReference[id=12,name=int_col,relation=test,type=Int NULL]
+| | | |   | +-AttributeReference[id=13,name=long_col,relation=test,type=Long]
+| | | |   | +-AttributeReference[id=14,name=float_col,relation=test,type=Float]
+| | | |   | +-AttributeReference[id=15,name=double_col,relation=test,
+| | | |   | | type=Double NULL]
+| | | |   | +-AttributeReference[id=16,name=char_col,relation=test,type=Char(20)]
+| | | |   | +-AttributeReference[id=17,name=vchar_col,relation=test,
+| | | |   |   type=VarChar(20) NULL]
+| | | |   +-project_expressions=
+| | | |     +-AttributeReference[id=12,name=int_col,relation=test,type=Int NULL]
+| | | +-project_attributes=
+| | |   +-AttributeReference[id=18,name=int_col,relation=,type=Int NULL]
+| | +-project_expressions=
+| | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-left_join_attributes=
+| | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-right_join_attributes=
+| |   +-AttributeReference[id=18,name=int_col,relation=,type=Int NULL]
+| +-grouping_expressions=
+| | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| +-aggregate_expressions=
+|   +-[]
++-output_attributes=
+  +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+==

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/tests/resolver/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/resolver/CMakeLists.txt b/query_optimizer/tests/resolver/CMakeLists.txt
index 3101b43..5350543 100644
--- a/query_optimizer/tests/resolver/CMakeLists.txt
+++ b/query_optimizer/tests/resolver/CMakeLists.txt
@@ -51,6 +51,10 @@ add_test(quickstep_queryoptimizer_tests_resolver_select
          "../quickstep_queryoptimizer_tests_OptimizerTextTest"
          "${CMAKE_CURRENT_SOURCE_DIR}/Select.test"
          "${CMAKE_CURRENT_BINARY_DIR}/Select.test")
+add_test(quickstep_queryoptimizer_tests_resolver_setoperation
+         "../quickstep_queryoptimizer_tests_OptimizerTextTest"
+         "${CMAKE_CURRENT_SOURCE_DIR}/SetOperation.test"
+         "${CMAKE_CURRENT_BINARY_DIR}/SetOperation.test")
 add_test(quickstep_queryoptimizer_tests_resolver_update
          "../quickstep_queryoptimizer_tests_OptimizerTextTest"
          "${CMAKE_CURRENT_SOURCE_DIR}/Update.test"

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/query_optimizer/tests/resolver/SetOperation.test
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/resolver/SetOperation.test b/query_optimizer/tests/resolver/SetOperation.test
new file mode 100644
index 0000000..f4bff6d
--- /dev/null
+++ b/query_optimizer/tests/resolver/SetOperation.test
@@ -0,0 +1,185 @@
+# 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.
+
+[default initial_logical_plan]
+SELECT int_col FROM test
+UNION
+SELECT int_col FROM test
+--
+TopLevelPlan
++-plan=Union[set_operation_type=Union]
+| +-operands=
+| | +-Project
+| | | +-input=Project
+| | | | +-input=TableReference[relation_name=Test,relation_alias=test]
+| | | | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | | | +-AttributeReference[id=3,name=double_col,relation=test,
+| | | | | | type=Double NULL]
+| | | | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | | | |   type=VarChar(20) NULL]
+| | | | +-project_list=
+| | | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | +-project_list=
+| | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-Project
+| |   +-input=TableReference[relation_name=Test,relation_alias=test]
+| |   | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |   | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| |   | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| |   | +-AttributeReference[id=9,name=double_col,relation=test,type=Double NULL]
+| |   | +-AttributeReference[id=10,name=char_col,relation=test,type=Char(20)]
+| |   | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| |   |   type=VarChar(20) NULL]
+| |   +-project_list=
+| |     +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| +-project_attributes=
+|   +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
++-output_attributes=
+  +-AttributeReference[id=12,name=int_col,relation=,type=Int NULL]
+==
+
+SELECT double_col FROM test
+UNION ALL
+SELECT int_col FROM test
+--
+TopLevelPlan
++-plan=UnionAll[set_operation_type=UnionAll]
+| +-operands=
+| | +-Project
+| | | +-input=Project
+| | | | +-input=TableReference[relation_name=Test,relation_alias=test]
+| | | | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | | | +-AttributeReference[id=3,name=double_col,relation=test,
+| | | | | | type=Double NULL]
+| | | | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | | | |   type=VarChar(20) NULL]
+| | | | +-project_list=
+| | | |   +-AttributeReference[id=3,name=double_col,relation=test,
+| | | |     type=Double NULL]
+| | | +-project_list=
+| | |   +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | +-Project
+| |   +-input=TableReference[relation_name=Test,relation_alias=test]
+| |   | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |   | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| |   | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| |   | +-AttributeReference[id=9,name=double_col,relation=test,type=Double NULL]
+| |   | +-AttributeReference[id=10,name=char_col,relation=test,type=Char(20)]
+| |   | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| |   |   type=VarChar(20) NULL]
+| |   +-project_list=
+| |     +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| +-project_attributes=
+|   +-AttributeReference[id=12,name=double_col,relation=,type=Double NULL]
++-output_attributes=
+  +-AttributeReference[id=12,name=double_col,relation=,type=Double NULL]
+==
+
+SELECT int_col, double_col FROM test
+UNION
+SELECT int_col, int_col FROM test
+--
+TopLevelPlan
++-plan=Union[set_operation_type=Union]
+| +-operands=
+| | +-Project
+| | | +-input=Project
+| | | | +-input=TableReference[relation_name=Test,relation_alias=test]
+| | | | | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | | | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | | | | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | | | | +-AttributeReference[id=3,name=double_col,relation=test,
+| | | | | | type=Double NULL]
+| | | | | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | | | | +-AttributeReference[id=5,name=vchar_col,relation=test,
+| | | | |   type=VarChar(20) NULL]
+| | | | +-project_list=
+| | | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | | |   +-AttributeReference[id=3,name=double_col,relation=test,
+| | | |     type=Double NULL]
+| | | +-project_list=
+| | |   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | |   +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | +-Project
+| |   +-input=Project
+| |   | +-input=TableReference[relation_name=Test,relation_alias=test]
+| |   | | +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |   | | +-AttributeReference[id=7,name=long_col,relation=test,type=Long]
+| |   | | +-AttributeReference[id=8,name=float_col,relation=test,type=Float]
+| |   | | +-AttributeReference[id=9,name=double_col,relation=test,
+| |   | | | type=Double NULL]
+| |   | | +-AttributeReference[id=10,name=char_col,relation=test,type=Char(20)]
+| |   | | +-AttributeReference[id=11,name=vchar_col,relation=test,
+| |   | |   type=VarChar(20) NULL]
+| |   | +-project_list=
+| |   |   +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |   |   +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |   +-project_list=
+| |     +-AttributeReference[id=6,name=int_col,relation=test,type=Int NULL]
+| |     +-Alias[id=12,name=int_col,relation=,type=Double NULL]
+| |       +-Cast[target_type=Double NULL]
+| |         +-operand=AttributeReference[id=6,name=int_col,relation=test,
+| |           type=Int NULL]
+| +-project_attributes=
+|   +-AttributeReference[id=13,name=int_col,relation=,type=Int NULL]
+|   +-AttributeReference[id=14,name=double_col,relation=,type=Double NULL]
++-output_attributes=
+  +-AttributeReference[id=13,name=int_col,relation=,type=Int NULL]
+  +-AttributeReference[id=14,name=double_col,relation=,type=Double NULL]
+==
+
+SELECT float_col FROM test
+INTERSECT
+SELECT long_col FROM test
+--
+ERROR: There is not a safely coerce between Long and Float (1 : 1)
+SELECT float_col FROM test
+^
+==
+
+SELECT int_col FROM test
+UNION ALL
+SELECT float_col FROM test
+--
+ERROR: There is not a safely coerce between Float and Int NULL (1 : 1)
+SELECT int_col FROM test
+^
+==
+
+SELECT int_col FROM test
+INTERSECT
+SELECT vchar_col FROM test
+--
+ERROR: Does not support cast operation with non-numeric types VarChar(20) NULL and Int NULL (1 : 1)
+SELECT int_col FROM test
+^
+==
+
+SELECT int_col, double_col FROM test
+UNION ALL
+SELECT double_col, vchar_col FROM test
+--
+ERROR: Does not support cast operation with non-numeric types VarChar(20) NULL and Double NULL (1 : 1)
+SELECT int_col, double_col FRO...
+^
+==

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/relational_operators/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/relational_operators/CMakeLists.txt b/relational_operators/CMakeLists.txt
index c25c17e..667b700 100644
--- a/relational_operators/CMakeLists.txt
+++ b/relational_operators/CMakeLists.txt
@@ -79,6 +79,7 @@ add_library(quickstep_relationaloperators_SortRunGenerationOperator SortRunGener
             SortRunGenerationOperator.hpp)
 add_library(quickstep_relationaloperators_TableGeneratorOperator TableGeneratorOperator.cpp TableGeneratorOperator.hpp)
 add_library(quickstep_relationaloperators_TextScanOperator TextScanOperator.cpp TextScanOperator.hpp)
+add_library(quickstep_relationaloperators_UnionAllOperator UnionAllOperator.cpp UnionAllOperator.hpp)
 add_library(quickstep_relationaloperators_UpdateOperator UpdateOperator.cpp UpdateOperator.hpp)
 add_library(quickstep_relationaloperators_WindowAggregationOperator WindowAggregationOperator.cpp WindowAggregationOperator.hpp)
 add_library(quickstep_relationaloperators_WorkOrder ../empty_src.cpp WorkOrder.hpp)
@@ -511,6 +512,20 @@ if (QUICKSTEP_HAVE_FILE_MANAGER_HDFS)
   target_link_libraries(quickstep_relationaloperators_TextScanOperator
                         ${LIBHDFS3_LIBRARIES})
 endif(QUICKSTEP_HAVE_FILE_MANAGER_HDFS)
+target_link_libraries(quickstep_relationaloperators_UnionAllOperator
+                      glog
+                      quickstep_catalog_CatalogRelation
+                      quickstep_catalog_CatalogTypedefs
+                      quickstep_queryexecution_QueryContext
+                      quickstep_queryexecution_WorkOrderProtosContainer
+                      quickstep_queryexecution_WorkOrdersContainer
+                      quickstep_relationaloperators_RelationalOperator
+                      quickstep_storage_InsertDestination
+                      quickstep_storage_StorageBlock
+                      quickstep_storage_StorageBlockInfo
+                      quickstep_storage_StorageManager
+                      quickstep_utility_Macros
+                      tmb)
 target_link_libraries(quickstep_relationaloperators_UpdateOperator
                       glog
                       quickstep_catalog_CatalogRelation
@@ -617,6 +632,7 @@ target_link_libraries(quickstep_relationaloperators
                       quickstep_relationaloperators_SortRunGenerationOperator
                       quickstep_relationaloperators_TableGeneratorOperator
                       quickstep_relationaloperators_TextScanOperator
+                      quickstep_relationaloperators_UnionAllOperator
                       quickstep_relationaloperators_UpdateOperator
                       quickstep_relationaloperators_WindowAggregationOperator
                       quickstep_relationaloperators_WorkOrder

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/relational_operators/RelationalOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/RelationalOperator.hpp b/relational_operators/RelationalOperator.hpp
index 0aeb4c9..c568654 100644
--- a/relational_operators/RelationalOperator.hpp
+++ b/relational_operators/RelationalOperator.hpp
@@ -86,6 +86,7 @@ class RelationalOperator {
     kSortRunGeneration,
     kTableGenerator,
     kTextScan,
+    kUnionAll,
     kUpdate,
     kWindowAggregation,
     kMockOperator

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/relational_operators/UnionAllOperator.cpp
----------------------------------------------------------------------
diff --git a/relational_operators/UnionAllOperator.cpp b/relational_operators/UnionAllOperator.cpp
new file mode 100644
index 0000000..141b3cf
--- /dev/null
+++ b/relational_operators/UnionAllOperator.cpp
@@ -0,0 +1,144 @@
+/**
+ * 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 "relational_operators/UnionAllOperator.hpp"
+
+#include <cstddef>
+#include <vector>
+
+#include "catalog/CatalogTypedefs.hpp"
+#include "query_execution/QueryContext.hpp"
+#include "query_execution/WorkOrderProtosContainer.hpp"
+#include "query_execution/WorkOrdersContainer.hpp"
+#include "storage/InsertDestination.hpp"
+#include "storage/StorageBlock.hpp"
+#include "storage/StorageBlockInfo.hpp"
+#include "storage/StorageManager.hpp"
+
+#include "glog/logging.h"
+
+#include "tmb/id_typedefs.h"
+
+namespace quickstep {
+
+void UnionAllOperator::feedInputBlock(const block_id input_block_id,
+                                      const relation_id input_relation_id,
+                                      const partition_id part_id) {
+  std::size_t index = relation_id_to_index_.at(input_relation_id);
+  input_relations_block_ids_[index].push_back(input_block_id);
+}
+
+void UnionAllOperator::doneFeedingInputBlocks(const relation_id rel_id) {
+  std::size_t relation_index = relation_id_to_index_.at(rel_id);
+  DCHECK(still_feeding_.find(relation_index) != still_feeding_.end());
+  still_feeding_.erase(relation_index);
+  if (still_feeding_.size() == 0) {
+    done_feeding_input_relation_ = true;
+  }
+}
+
+void UnionAllOperator::addWorkOrdersSingleRelation(
+    WorkOrdersContainer *container,
+    QueryContext *query_context,
+    StorageManager *storage_manager,
+    InsertDestination *output_destination,
+    const std::size_t relation_index) {
+  if (input_relations_are_stored_[relation_index]) {
+    const std::vector<block_id> &all_blocks = input_relations_block_ids_.at(relation_index);
+    for (const block_id input_block_id : all_blocks) {
+      container->addNormalWorkOrder(
+          new UnionAllWorkOrder(
+              query_id_,
+              input_relations_[relation_index],
+              input_block_id,
+              select_attribute_ids_[relation_index],
+              output_destination,
+              storage_manager),
+          op_index_);
+    }
+  } else {
+    std::size_t num_generated = num_workorders_generated_[relation_index];
+    const std::vector<block_id> &all_blocks = input_relations_block_ids_[relation_index];
+    while (num_generated < all_blocks .size()) {
+      container->addNormalWorkOrder(
+          new UnionAllWorkOrder(
+              query_id_,
+              input_relations_[relation_index],
+              all_blocks[num_generated],
+              select_attribute_ids_[relation_index],
+              output_destination,
+              storage_manager),
+          op_index_);
+      ++num_generated;
+    }
+    num_workorders_generated_[relation_index] = num_generated;
+  }
+}
+
+bool UnionAllOperator::getAllWorkOrders(
+    WorkOrdersContainer *container,
+    QueryContext *query_context,
+    StorageManager *storage_manager,
+    const tmb::client_id scheduler_client_id,
+    tmb::MessageBus *bus) {
+  DCHECK(query_context != nullptr);
+
+  InsertDestination *output_destination =
+      query_context->getInsertDestination(output_destination_index_);
+
+  if (!stored_generated_) {
+    for (std::size_t relation_index = 0; relation_index < input_relations_.size(); ++relation_index) {
+      if (input_relations_are_stored_[relation_index]) {
+        addWorkOrdersSingleRelation(container,
+                                    query_context,
+                                    storage_manager,
+                                    output_destination,
+                                    relation_index);
+      }
+    }
+    stored_generated_ = true;
+  }
+
+  for (std::size_t relation_index = 0; relation_index < input_relations_.size(); ++relation_index) {
+    if (!input_relations_are_stored_[relation_index]) {
+       addWorkOrdersSingleRelation(container,
+                                   query_context,
+                                   storage_manager,
+                                   output_destination,
+                                   relation_index);
+    }
+  }
+  return stored_generated_ && done_feeding_input_relation_;
+}
+
+bool UnionAllOperator::getAllWorkOrderProtos(WorkOrderProtosContainer* container) {
+  // TODO(tianrun): Add protobuf for UnionAllWorkOrder to support distributed mode.
+  LOG(FATAL) << "UnionAllOperator is not supported in distributed mode yet.";
+  return true;
+}
+
+void UnionAllWorkOrder::execute() {
+  BlockReference block(
+      storage_manager_->getBlock(input_block_id_, *input_relation_));
+  block->selectSimple(select_attribute_id_,
+                      nullptr,
+                      output_destination_);
+}
+
+}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f1434eb9/relational_operators/UnionAllOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/UnionAllOperator.hpp b/relational_operators/UnionAllOperator.hpp
new file mode 100644
index 0000000..3bfed82
--- /dev/null
+++ b/relational_operators/UnionAllOperator.hpp
@@ -0,0 +1,228 @@
+/**
+ * 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_RELATIONAL_OPERATORS_UNION_ALL_OPERATOR_HPP_
+#define QUICKSTEP_RELATIONAL_OPERATORS_UNION_ALL_OPERATOR_HPP_
+
+#include <cstddef>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+#include "catalog/CatalogRelation.hpp"
+#include "catalog/CatalogTypedefs.hpp"
+#include "query_execution/QueryContext.hpp"
+#include "relational_operators/RelationalOperator.hpp"
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+#include "tmb/id_typedefs.h"
+
+namespace tmb { class MessageBus; }
+
+namespace quickstep {
+
+class InsertDestination;
+class StorageManager;
+class WorkOrderProtosContainer;
+class WorkOrdersContainer;
+
+/** \addtogroup RelationalOperators
+ *  @{
+ */
+
+/**
+ * @brief An operator which performs UNION ALL operation to relational tables.
+ **/
+class UnionAllOperator : public RelationalOperator {
+ public:
+  /**
+   * @brief Constructor.
+   *
+   * @param query_id The ID of the query to which this operator belongs.
+   * @param input_relations The input relations to this UnionAll operator.
+   * @param output_relation The output relation.
+   * @param output_destination_index The index of the InsertDestination in the
+   *        QueryContext to insert the results.
+   * @param input_relations_are_stored A boolean vector indicating whether each
+   *        input relation is a stored relation and is fully availabie to the
+   *        operator before it can start generating workorders.
+   * @param select_attribute_ids The attributes for all input relations.
+   **/
+  UnionAllOperator(const std::size_t query_id,
+                   const std::vector<const CatalogRelation*> &input_relations,
+                   const CatalogRelation &output_relation,
+                   const QueryContext::insert_destination_id output_destination_index,
+                   const std::vector<bool> &input_relations_are_stored,
+                   const std::vector<std::vector<attribute_id>> &select_attribute_ids)
+      : RelationalOperator(query_id),
+        input_relations_(input_relations),
+        input_relations_are_stored_(input_relations_are_stored),
+        output_relation_(output_relation),
+        output_destination_index_(output_destination_index),
+        select_attribute_ids_(select_attribute_ids),
+        stored_generated_(false) {
+    // For every input relation, initialize the UnionAll data structure.
+    for (std::size_t i = 0; i < input_relations.size(); i++) {
+      relation_id_to_index_.emplace(input_relations[i]->getID(), i);
+      if (input_relations_are_stored[i]) {
+        input_relations_block_ids_.emplace_back(
+            input_relations[i]->getBlocksSnapshot());
+      } else {
+        input_relations_block_ids_.emplace_back();
+        still_feeding_.insert(i);
+      }
+
+      num_workorders_generated_.push_back(0);
+    }
+  }
+
+  ~UnionAllOperator() override {}
+
+  OperatorType getOperatorType() const override {
+    return kUnionAll;
+  }
+
+  std::string getName() const override {
+    return "UnionAll";
+  }
+
+  QueryContext::insert_destination_id getInsertDestinationID() const override {
+    return output_destination_index_;
+  }
+
+  /**
+   * @return The input relations to this UnionAll operator.
+   */
+  const std::vector<const CatalogRelation*>& input_relations() const {
+    return input_relations_;
+  }
+
+  /**
+   * @return The output relation to this UnionAll operator.
+   */
+  const CatalogRelation& output_relation() const {
+    return output_relation_;
+  }
+
+  const relation_id getOutputRelationID() const override {
+    return output_relation_.getID();
+  }
+
+  void feedInputBlock(const block_id input_block_id,
+                      const relation_id input_relation_id,
+                      const partition_id part_id) override;
+
+  void doneFeedingInputBlocks(const relation_id rel_id) override;
+
+  bool getAllWorkOrders(WorkOrdersContainer *container,
+                        QueryContext *query_context,
+                        StorageManager *storage_manager,
+                        const tmb::client_id scheduler_client_id,
+                        tmb::MessageBus *bus) override;
+
+  bool getAllWorkOrderProtos(WorkOrderProtosContainer *container) override;
+
+ private:
+  // Add work orders for a single relation.
+  void addWorkOrdersSingleRelation(WorkOrdersContainer *container,
+                                   QueryContext *query_context,
+                                   StorageManager *storage_manager,
+                                   InsertDestination *output_destination,
+                                   const std::size_t relation_index);
+
+  const std::vector<const CatalogRelation*> input_relations_;
+  const std::vector<bool> input_relations_are_stored_;
+
+  const CatalogRelation &output_relation_;
+  const QueryContext::insert_destination_id output_destination_index_;
+
+  const std::vector<std::vector<attribute_id>> select_attribute_ids_;
+
+  // For input_relation_[i],
+  // its block ids are in input_relations_block_ids_[i],
+  // its number of generated work orders is in num_workorders_generated_[i].
+  std::vector<std::vector<block_id>> input_relations_block_ids_;
+  std::vector<std::size_t> num_workorders_generated_;
+
+  // Relation indices that are not stored, and are still feeding.
+  std::unordered_set<std::size_t> still_feeding_;
+
+  // Map from relation_id to index in vector.
+  std::unordered_map<relation_id, std::size_t> relation_id_to_index_;
+
+  // If all the stored relations are generated.
+  bool stored_generated_;
+
+  DISALLOW_COPY_AND_ASSIGN(UnionAllOperator);
+};
+
+
+/**
+ * @brief A work order produced by UnionAllOperator.
+ */
+class UnionAllWorkOrder : public WorkOrder {
+ public:
+  /**
+   * @brief Constructor.
+   *
+   * @param query_id The ID of the query to which this WorkOrder belongs.
+   * @param input_relation The relation to perform UnionAll over.
+   * @param input_block_id The block id.
+   * @param select_attribute_id The ids of the attributes to select from
+   *        the input relation.
+   * @param output_destination The InsertDestination to insert the UnionAll
+   *        result.
+   * @param storage_manager The StorageManager to use.
+   */
+  UnionAllWorkOrder(const std::size_t query_id,
+                    const CatalogRelationSchema *input_relation,
+                    const block_id input_block_id,
+                    const std::vector<attribute_id> &select_attribute_id,
+                    InsertDestination *output_destination,
+                    StorageManager *storage_manager)
+      : WorkOrder(query_id),
+        input_relation_(input_relation),
+        input_block_id_(input_block_id),
+        select_attribute_id_(select_attribute_id),
+        output_destination_(output_destination),
+        storage_manager_(storage_manager) {}
+
+  ~UnionAllWorkOrder() override {}
+
+  void execute() override;
+
+ private:
+  const CatalogRelationSchema *input_relation_;
+  const block_id input_block_id_;
+  const std::vector<attribute_id> select_attribute_id_;
+
+  InsertDestination *output_destination_;
+  StorageManager* storage_manager_;
+
+  DISALLOW_COPY_AND_ASSIGN(UnionAllWorkOrder);
+};
+
+/** @} */
+
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_RELATIONAL_OPERATORS_UNION_ALL_OPERATOR_HPP_


Mime
View raw message