You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by ji...@apache.org on 2017/04/12 19:36:06 UTC
[3/5] incubator-quickstep git commit: Initial commit
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/expressions/scalar/ScalarLiteral.cpp
----------------------------------------------------------------------
diff --git a/expressions/scalar/ScalarLiteral.cpp b/expressions/scalar/ScalarLiteral.cpp
index 48b5574..5cb7776 100644
--- a/expressions/scalar/ScalarLiteral.cpp
+++ b/expressions/scalar/ScalarLiteral.cpp
@@ -47,24 +47,49 @@ Scalar* ScalarLiteral::clone() const {
return new ScalarLiteral(internal_literal_, type_);
}
-ColumnVector* ScalarLiteral::getAllValues(
+ColumnVectorPtr ScalarLiteral::getAllValues(
ValueAccessor *accessor,
- const SubBlocksReference *sub_blocks_ref) const {
- return ColumnVector::MakeVectorOfValue(
- type_,
- internal_literal_,
- accessor->getNumTuplesVirtual());
+ const SubBlocksReference *sub_blocks_ref,
+ ScalarCache *scalar_cache) const {
+ return ColumnVectorPtr(
+ ColumnVector::MakeVectorOfValue(type_,
+ internal_literal_,
+ accessor->getNumTuplesVirtual()));
}
-ColumnVector* ScalarLiteral::getAllValuesForJoin(
+ColumnVectorPtr ScalarLiteral::getAllValuesForJoin(
const relation_id left_relation_id,
ValueAccessor *left_accessor,
const relation_id right_relation_id,
ValueAccessor *right_accessor,
- const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids) const {
- return ColumnVector::MakeVectorOfValue(type_,
- internal_literal_,
- joined_tuple_ids.size());
+ const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
+ ScalarCache *scalar_cache) const {
+ return ColumnVectorPtr(
+ ColumnVector::MakeVectorOfValue(type_,
+ internal_literal_,
+ joined_tuple_ids.size()));
+}
+
+void ScalarLiteral::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<const Expression*> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<const Expression*>> *container_child_fields) const {
+ Scalar::getFieldStringItems(inline_field_names,
+ inline_field_values,
+ non_container_child_field_names,
+ non_container_child_fields,
+ container_child_field_names,
+ container_child_fields);
+
+ inline_field_names->emplace_back("internal_literal");
+ if (internal_literal_.isNull()) {
+ inline_field_values->emplace_back("NULL");
+ } else {
+ inline_field_values->emplace_back(type_.printValueToString(internal_literal_));
+ }
}
} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/expressions/scalar/ScalarLiteral.hpp
----------------------------------------------------------------------
diff --git a/expressions/scalar/ScalarLiteral.hpp b/expressions/scalar/ScalarLiteral.hpp
index c7f5ceb..e81aaf8 100644
--- a/expressions/scalar/ScalarLiteral.hpp
+++ b/expressions/scalar/ScalarLiteral.hpp
@@ -20,6 +20,7 @@
#ifndef QUICKSTEP_EXPRESSIONS_SCALAR_SCALAR_LITERAL_HPP_
#define QUICKSTEP_EXPRESSIONS_SCALAR_SCALAR_LITERAL_HPP_
+#include <string>
#include <utility>
#include <vector>
@@ -28,11 +29,12 @@
#include "expressions/scalar/Scalar.hpp"
#include "storage/StorageBlockInfo.hpp"
#include "types/TypedValue.hpp"
+#include "types/containers/ColumnVector.hpp"
#include "utility/Macros.hpp"
namespace quickstep {
-class ColumnVector;
+class ScalarCache;
class Type;
class ValueAccessor;
@@ -101,15 +103,26 @@ class ScalarLiteral : public Scalar {
return internal_literal_;
}
- ColumnVector* getAllValues(ValueAccessor *accessor,
- const SubBlocksReference *sub_blocks_ref) const override;
+ ColumnVectorPtr getAllValues(ValueAccessor *accessor,
+ const SubBlocksReference *sub_blocks_ref,
+ ScalarCache *scalar_cache) const override;
- ColumnVector* getAllValuesForJoin(
+ ColumnVectorPtr getAllValuesForJoin(
const relation_id left_relation_id,
ValueAccessor *left_accessor,
const relation_id right_relation_id,
ValueAccessor *right_accessor,
- const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids) const override;
+ const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
+ ScalarCache *scalar_cache) const override;
+
+ 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<const Expression*> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<const Expression*>> *container_child_fields) const override;
private:
TypedValue internal_literal_;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/expressions/scalar/ScalarSharedExpression.cpp
----------------------------------------------------------------------
diff --git a/expressions/scalar/ScalarSharedExpression.cpp b/expressions/scalar/ScalarSharedExpression.cpp
new file mode 100644
index 0000000..8dbb3bb
--- /dev/null
+++ b/expressions/scalar/ScalarSharedExpression.cpp
@@ -0,0 +1,141 @@
+/**
+ * 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 "expressions/scalar/ScalarSharedExpression.hpp"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "catalog/CatalogTypedefs.hpp"
+#include "expressions/Expressions.pb.h"
+#include "expressions/scalar/ScalarCache.hpp"
+#include "storage/ValueAccessor.hpp"
+#include "types/TypedValue.hpp"
+#include "types/containers/ColumnVector.hpp"
+
+namespace quickstep {
+
+struct SubBlocksReference;
+
+ScalarSharedExpression::ScalarSharedExpression(const int share_id,
+ Scalar *operand)
+ : Scalar(operand->getType()),
+ share_id_(share_id),
+ operand_(operand) {
+}
+
+serialization::Scalar ScalarSharedExpression::getProto() const {
+ serialization::Scalar proto;
+ proto.set_data_source(serialization::Scalar::SHARED_EXPRESSION);
+ proto.SetExtension(serialization::ScalarSharedExpression::share_id, share_id_);
+ proto.MutableExtension(serialization::ScalarSharedExpression::operand)
+ ->CopyFrom(operand_->getProto());
+
+ return proto;
+}
+
+Scalar* ScalarSharedExpression::clone() const {
+ return new ScalarSharedExpression(share_id_, operand_->clone());
+}
+
+TypedValue ScalarSharedExpression::getValueForSingleTuple(const ValueAccessor &accessor,
+ const tuple_id tuple) const {
+ return operand_->getValueForSingleTuple(accessor, tuple);
+}
+
+TypedValue ScalarSharedExpression::getValueForJoinedTuples(
+ const ValueAccessor &left_accessor,
+ const relation_id left_relation_id,
+ const tuple_id left_tuple_id,
+ const ValueAccessor &right_accessor,
+ const relation_id right_relation_id,
+ const tuple_id right_tuple_id) const {
+ return operand_->getValueForJoinedTuples(left_accessor,
+ left_relation_id,
+ left_tuple_id,
+ right_accessor,
+ right_relation_id,
+ right_tuple_id);
+}
+
+ColumnVectorPtr ScalarSharedExpression::getAllValues(
+ ValueAccessor *accessor,
+ const SubBlocksReference *sub_blocks_ref,
+ ScalarCache *scalar_cache) const {
+ if (scalar_cache == nullptr) {
+ return operand_->getAllValues(accessor, sub_blocks_ref, scalar_cache);
+ } else {
+ ColumnVectorPtr result;
+ if (scalar_cache->has(share_id_)) {
+ result = scalar_cache->get(share_id_);
+ } else {
+ result = operand_->getAllValues(accessor, sub_blocks_ref, scalar_cache);
+ scalar_cache->set(share_id_, result);
+ }
+ return result;
+ }
+}
+
+ColumnVectorPtr ScalarSharedExpression::getAllValuesForJoin(
+ const relation_id left_relation_id,
+ ValueAccessor *left_accessor,
+ const relation_id right_relation_id,
+ ValueAccessor *right_accessor,
+ const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
+ ScalarCache *scalar_cache) const {
+ if (scalar_cache == nullptr) {
+ return operand_->getAllValuesForJoin(left_relation_id,
+ left_accessor,
+ right_relation_id,
+ right_accessor,
+ joined_tuple_ids,
+ scalar_cache);
+ } else {
+ ColumnVectorPtr result;
+ if (scalar_cache->has(share_id_)) {
+ result = scalar_cache->get(share_id_);
+ } else {
+ result = operand_->getAllValuesForJoin(left_relation_id,
+ left_accessor,
+ right_relation_id,
+ right_accessor,
+ joined_tuple_ids,
+ scalar_cache);
+ scalar_cache->set(share_id_, result);
+ }
+ return result;
+ }
+}
+
+void ScalarSharedExpression::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<const Expression*> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<const Expression*>> *container_child_fields) const {
+ inline_field_names->emplace_back("share_id");
+ inline_field_values->emplace_back(std::to_string(share_id_));
+
+ non_container_child_field_names->emplace_back("operand");
+ non_container_child_fields->emplace_back(operand_.get());
+}
+
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/expressions/scalar/ScalarSharedExpression.hpp
----------------------------------------------------------------------
diff --git a/expressions/scalar/ScalarSharedExpression.hpp b/expressions/scalar/ScalarSharedExpression.hpp
new file mode 100644
index 0000000..3262ef1
--- /dev/null
+++ b/expressions/scalar/ScalarSharedExpression.hpp
@@ -0,0 +1,119 @@
+/**
+ * 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_EXPRESSIONS_SCALAR_SCALAR_SHARED_EXPRESSION_HPP_
+#define QUICKSTEP_EXPRESSIONS_SCALAR_SCALAR_SHARED_EXPRESSION_HPP_
+
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "catalog/CatalogTypedefs.hpp"
+#include "expressions/Expressions.pb.h"
+#include "expressions/scalar/Scalar.hpp"
+#include "storage/StorageBlockInfo.hpp"
+#include "types/TypedValue.hpp"
+#include "types/containers/ColumnVector.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+
+class ScalarCache;
+class ValueAccessor;
+
+struct SubBlocksReference;
+
+/** \addtogroup Expressions
+ * @{
+ */
+
+class ScalarSharedExpression : public Scalar {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ScalarSharedExpression(const int shared_id, Scalar *operand);
+
+ /**
+ * @brief Destructor.
+ **/
+ ~ScalarSharedExpression() override {
+ }
+
+ serialization::Scalar getProto() const override;
+
+ Scalar* clone() const override;
+
+ ScalarDataSource getDataSource() const override {
+ return kSharedExpression;
+ }
+
+ TypedValue getValueForSingleTuple(const ValueAccessor &accessor,
+ const tuple_id tuple) const override;
+
+ TypedValue getValueForJoinedTuples(
+ const ValueAccessor &left_accessor,
+ const relation_id left_relation_id,
+ const tuple_id left_tuple_id,
+ const ValueAccessor &right_accessor,
+ const relation_id right_relation_id,
+ const tuple_id right_tuple_id) const override;
+
+ bool hasStaticValue() const override {
+ return operand_->hasStaticValue();
+ }
+
+ const TypedValue& getStaticValue() const override {
+ return operand_->getStaticValue();
+ }
+
+ ColumnVectorPtr getAllValues(ValueAccessor *accessor,
+ const SubBlocksReference *sub_blocks_ref,
+ ScalarCache *scalar_cache) const override;
+
+ ColumnVectorPtr getAllValuesForJoin(
+ const relation_id left_relation_id,
+ ValueAccessor *left_accessor,
+ const relation_id right_relation_id,
+ ValueAccessor *right_accessor,
+ const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
+ ScalarCache *scalar_cache) const override;
+
+ 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<const Expression*> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<const Expression*>> *container_child_fields) const override;
+
+ private:
+ const int share_id_;
+ std::unique_ptr<Scalar> operand_;
+
+ DISALLOW_COPY_AND_ASSIGN(ScalarSharedExpression);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_EXPRESSIONS_SCALAR_SCALAR_SHARED_EXPRESSION_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/expressions/scalar/ScalarUnaryExpression.cpp
----------------------------------------------------------------------
diff --git a/expressions/scalar/ScalarUnaryExpression.cpp b/expressions/scalar/ScalarUnaryExpression.cpp
index 72fdbe1..80d4944 100644
--- a/expressions/scalar/ScalarUnaryExpression.cpp
+++ b/expressions/scalar/ScalarUnaryExpression.cpp
@@ -33,6 +33,7 @@
#include "types/containers/ColumnVector.hpp"
#include "types/operations/Operation.pb.h"
#include "types/operations/unary_operations/UnaryOperation.hpp"
+#include "types/operations/unary_operations/UnaryOperationID.hpp"
#ifdef QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN
#include "glog/logging.h"
@@ -91,36 +92,43 @@ TypedValue ScalarUnaryExpression::getValueForJoinedTuples(
}
}
-ColumnVector* ScalarUnaryExpression::getAllValues(
+ColumnVectorPtr ScalarUnaryExpression::getAllValues(
ValueAccessor *accessor,
- const SubBlocksReference *sub_blocks_ref) const {
+ const SubBlocksReference *sub_blocks_ref,
+ ScalarCache *scalar_cache) const {
if (fast_operator_.get() == nullptr) {
- return ColumnVector::MakeVectorOfValue(getType(),
- static_value_,
- accessor->getNumTuplesVirtual());
+ return ColumnVectorPtr(
+ ColumnVector::MakeVectorOfValue(getType(),
+ static_value_,
+ accessor->getNumTuplesVirtual()));
} else {
#ifdef QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_SELECTION
const attribute_id operand_attr_id = operand_->getAttributeIdForValueAccessor();
if (operand_attr_id != -1) {
- return fast_operator_->applyToValueAccessor(accessor, operand_attr_id);
+ return ColumnVectorPtr(
+ fast_operator_->applyToValueAccessor(accessor, operand_attr_id));
}
#endif // QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_SELECTION
- std::unique_ptr<ColumnVector> operand_result(operand_->getAllValues(accessor, sub_blocks_ref));
- return fast_operator_->applyToColumnVector(*operand_result);
+ ColumnVectorPtr operand_result(
+ operand_->getAllValues(accessor, sub_blocks_ref, scalar_cache));
+ return ColumnVectorPtr(
+ fast_operator_->applyToColumnVector(*operand_result));
}
}
-ColumnVector* ScalarUnaryExpression::getAllValuesForJoin(
+ColumnVectorPtr ScalarUnaryExpression::getAllValuesForJoin(
const relation_id left_relation_id,
ValueAccessor *left_accessor,
const relation_id right_relation_id,
ValueAccessor *right_accessor,
- const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids) const {
+ const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
+ ScalarCache *scalar_cache) const {
if (fast_operator_.get() == nullptr) {
- return ColumnVector::MakeVectorOfValue(getType(),
- static_value_,
- joined_tuple_ids.size());
+ return ColumnVectorPtr(
+ ColumnVector::MakeVectorOfValue(getType(),
+ static_value_,
+ joined_tuple_ids.size()));
} else {
#ifdef QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN
const attribute_id operand_attr_id = operand_->getAttributeIdForValueAccessor();
@@ -132,20 +140,23 @@ ColumnVector* ScalarUnaryExpression::getAllValuesForJoin(
const bool using_left_relation = (operand_relation_id == left_relation_id);
ValueAccessor *operand_accessor = using_left_relation ? left_accessor
: right_accessor;
- return fast_operator_->applyToValueAccessorForJoin(operand_accessor,
- using_left_relation,
- operand_attr_id,
- joined_tuple_ids);
+ return ColumnVectorPtr(
+ fast_operator_->applyToValueAccessorForJoin(operand_accessor,
+ using_left_relation,
+ operand_attr_id,
+ joined_tuple_ids));
}
#endif // QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN
- std::unique_ptr<ColumnVector> operand_result(
+ ColumnVectorPtr operand_result(
operand_->getAllValuesForJoin(left_relation_id,
left_accessor,
right_relation_id,
right_accessor,
- joined_tuple_ids));
- return fast_operator_->applyToColumnVector(*operand_result);
+ joined_tuple_ids,
+ scalar_cache));
+ return ColumnVectorPtr(
+ fast_operator_->applyToColumnVector(*operand_result));
}
}
@@ -166,4 +177,35 @@ void ScalarUnaryExpression::initHelper(bool own_children) {
}
}
+void ScalarUnaryExpression::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<const Expression*> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<const Expression*>> *container_child_fields) const {
+ Scalar::getFieldStringItems(inline_field_names,
+ inline_field_values,
+ non_container_child_field_names,
+ non_container_child_fields,
+ container_child_field_names,
+ container_child_fields);
+
+ if (fast_operator_ == nullptr) {
+ inline_field_names->emplace_back("static_value");
+ if (static_value_.isNull()) {
+ inline_field_values->emplace_back("NULL");
+ } else {
+ inline_field_values->emplace_back(type_.printValueToString(static_value_));
+ }
+ }
+
+ inline_field_names->emplace_back("operation");
+ inline_field_values->emplace_back(
+ kUnaryOperationNames[static_cast<int>(operation_.getUnaryOperationID())]);
+
+ non_container_child_field_names->emplace_back("operand");
+ non_container_child_fields->emplace_back(operand_.get());
+}
+
} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/expressions/scalar/ScalarUnaryExpression.hpp
----------------------------------------------------------------------
diff --git a/expressions/scalar/ScalarUnaryExpression.hpp b/expressions/scalar/ScalarUnaryExpression.hpp
index 608a842..efba14e 100644
--- a/expressions/scalar/ScalarUnaryExpression.hpp
+++ b/expressions/scalar/ScalarUnaryExpression.hpp
@@ -21,6 +21,7 @@
#define QUICKSTEP_EXPRESSIONS_SCALAR_SCALAR_UNARY_EXPRESSION_HPP_
#include <memory>
+#include <string>
#include <utility>
#include <vector>
@@ -29,6 +30,7 @@
#include "expressions/scalar/Scalar.hpp"
#include "storage/StorageBlockInfo.hpp"
#include "types/TypedValue.hpp"
+#include "types/containers/ColumnVector.hpp"
#include "types/operations/unary_operations/UnaryOperation.hpp"
#include "utility/Macros.hpp"
@@ -36,7 +38,7 @@
namespace quickstep {
-class ColumnVector;
+class ScalarCache;
class ValueAccessor;
struct SubBlocksReference;
@@ -93,15 +95,26 @@ class ScalarUnaryExpression : public Scalar {
return static_value_;
}
- ColumnVector* getAllValues(ValueAccessor *accessor,
- const SubBlocksReference *sub_blocks_ref) const override;
+ ColumnVectorPtr getAllValues(ValueAccessor *accessor,
+ const SubBlocksReference *sub_blocks_ref,
+ ScalarCache *scalar_cache) const override;
- ColumnVector* getAllValuesForJoin(
+ ColumnVectorPtr getAllValuesForJoin(
const relation_id left_relation_id,
ValueAccessor *left_accessor,
const relation_id right_relation_id,
ValueAccessor *right_accessor,
- const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids) const override;
+ const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
+ ScalarCache *scalar_cache) const override;
+
+ 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<const Expression*> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<const Expression*>> *container_child_fields) const override;
private:
void initHelper(bool own_children);
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index 08b6467..9e5a2c8 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -214,6 +214,7 @@ target_link_libraries(quickstep_queryoptimizer_PhysicalGenerator
quickstep_queryoptimizer_logical_Logical
quickstep_queryoptimizer_physical_Physical
quickstep_queryoptimizer_rules_AttachLIPFilters
+ quickstep_queryoptimizer_rules_CommonSubexpressionExtraction
quickstep_queryoptimizer_rules_FuseAggregateJoin
quickstep_queryoptimizer_rules_InjectJoinFilters
quickstep_queryoptimizer_rules_PruneColumns
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/PhysicalGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.cpp b/query_optimizer/PhysicalGenerator.cpp
index ac51c31..34deb76 100644
--- a/query_optimizer/PhysicalGenerator.cpp
+++ b/query_optimizer/PhysicalGenerator.cpp
@@ -27,6 +27,7 @@
#include "query_optimizer/logical/Logical.hpp"
#include "query_optimizer/physical/Physical.hpp"
#include "query_optimizer/rules/AttachLIPFilters.hpp"
+#include "query_optimizer/rules/CommonSubexpressionExtraction.hpp"
#include "query_optimizer/rules/FuseAggregateJoin.hpp"
#include "query_optimizer/rules/InjectJoinFilters.hpp"
#include "query_optimizer/rules/PruneColumns.hpp"
@@ -148,6 +149,8 @@ P::PhysicalPtr PhysicalGenerator::optimizePlan() {
rules.emplace_back(new FuseAggregateJoin());
+ rules.emplace_back(new CommonSubexpressionExtraction(optimizer_context_));
+
// NOTE(jianqiao): Adding rules after InjectJoinFilters (or AttachLIPFilters) requires
// extra handling of LIPFilterConfiguration for transformed nodes. So currently it is
// suggested that all the new rules be placed before this point.
@@ -165,7 +168,8 @@ P::PhysicalPtr PhysicalGenerator::optimizePlan() {
<< physical_plan_->toString();
}
- DVLOG(4) << "Optimized physical plan:\n" << physical_plan_->toString();
+// DVLOG(4) << "Optimized physical plan:\n" << physical_plan_->toString();
+ std::cerr << "Optimized physical plan:\n" << physical_plan_->toString();
if (FLAGS_visualize_plan) {
quickstep::PlanVisualizer plan_visualizer;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/AttributeReference.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/AttributeReference.cpp b/query_optimizer/expressions/AttributeReference.cpp
index f0e49d4..5dc59bb 100644
--- a/query_optimizer/expressions/AttributeReference.cpp
+++ b/query_optimizer/expressions/AttributeReference.cpp
@@ -19,6 +19,7 @@
#include "query_optimizer/expressions/AttributeReference.hpp"
+#include <functional>
#include <string>
#include <unordered_map>
#include <vector>
@@ -26,6 +27,7 @@
#include "expressions/scalar/ScalarAttribute.hpp"
#include "query_optimizer/expressions/ExprId.hpp"
#include "query_optimizer/expressions/Expression.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
#include "glog/logging.h"
@@ -57,6 +59,22 @@ std::vector<AttributeReferencePtr> AttributeReference::getReferencedAttributes()
return new ::quickstep::ScalarAttribute(*found_it->second);
}
+std::size_t AttributeReference::computeHash() const {
+ return std::hash<std::size_t>()(static_cast<std::size_t>(id()));
+}
+
+bool AttributeReference::equals(const ScalarPtr &other) const {
+ AttributeReferencePtr attr;
+ if (SomeAttributeReference::MatchesWithConditionalCast(other, &attr)) {
+ if (id() != attr->id()) {
+ return false;
+ }
+ DCHECK(type_.equals(attr->type_));
+ return true;
+ }
+ return false;
+}
+
void AttributeReference::getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/AttributeReference.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/AttributeReference.hpp b/query_optimizer/expressions/AttributeReference.hpp
index f5207b1..27d8bcb 100644
--- a/query_optimizer/expressions/AttributeReference.hpp
+++ b/query_optimizer/expressions/AttributeReference.hpp
@@ -88,6 +88,8 @@ class AttributeReference : public NamedExpression {
::quickstep::Scalar* concretize(
const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+ bool equals(const ScalarPtr &other) const override;
+
/**
* @brief Creates an immutable AttributReference.
*
@@ -114,6 +116,8 @@ class AttributeReference : public NamedExpression {
}
protected:
+ std::size_t computeHash() const override;
+
void getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/BinaryExpression.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/BinaryExpression.cpp b/query_optimizer/expressions/BinaryExpression.cpp
index 446dd55..aac675b 100644
--- a/query_optimizer/expressions/BinaryExpression.cpp
+++ b/query_optimizer/expressions/BinaryExpression.cpp
@@ -31,6 +31,7 @@
#include "query_optimizer/expressions/PatternMatcher.hpp"
#include "types/operations/binary_operations/BinaryOperation.hpp"
#include "types/operations/binary_operations/BinaryOperationID.hpp"
+#include "utility/HashPair.hpp"
#include "glog/logging.h"
@@ -104,6 +105,22 @@ std::vector<AttributeReferencePtr> BinaryExpression::getReferencedAttributes() c
right_->concretize(substitution_map));
}
+std::size_t BinaryExpression::computeHash() const {
+ return CombineHashes(
+ CombineHashes(static_cast<std::size_t>(ExpressionType::kBinaryExpression),
+ static_cast<std::size_t>(operation_.getBinaryOperationID())),
+ CombineHashes(left_->hash(), right_->hash()));
+}
+
+bool BinaryExpression::equals(const ScalarPtr &other) const {
+ BinaryExpressionPtr expr;
+ if (SomeBinaryExpression::MatchesWithConditionalCast(other, &expr)) {
+ return operation_.getBinaryOperationID() == expr->operation_.getBinaryOperationID()
+ && left_->equals(expr->left_) && right_->equals(expr->right_);
+ }
+ return false;
+}
+
void BinaryExpression::getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/BinaryExpression.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/BinaryExpression.hpp b/query_optimizer/expressions/BinaryExpression.hpp
index 9b11ed1..6a37679 100644
--- a/query_optimizer/expressions/BinaryExpression.hpp
+++ b/query_optimizer/expressions/BinaryExpression.hpp
@@ -90,6 +90,8 @@ class BinaryExpression : public Scalar {
::quickstep::Scalar* concretize(
const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+ bool equals(const ScalarPtr &other) const override;
+
static BinaryExpressionPtr Create(const BinaryOperation &operation,
const ScalarPtr &left,
const ScalarPtr &right) {
@@ -97,6 +99,8 @@ class BinaryExpression : public Scalar {
}
protected:
+ std::size_t computeHash() const override;
+
void getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/CMakeLists.txt b/query_optimizer/expressions/CMakeLists.txt
index 35fac90..2a5f610 100644
--- a/query_optimizer/expressions/CMakeLists.txt
+++ b/query_optimizer/expressions/CMakeLists.txt
@@ -21,7 +21,11 @@ add_library(quickstep_queryoptimizer_expressions_Alias Alias.cpp Alias.hpp)
add_library(quickstep_queryoptimizer_expressions_AttributeReference AttributeReference.cpp AttributeReference.hpp)
add_library(quickstep_queryoptimizer_expressions_BinaryExpression BinaryExpression.cpp BinaryExpression.hpp)
add_library(quickstep_queryoptimizer_expressions_Cast Cast.cpp Cast.hpp)
-add_library(quickstep_queryoptimizer_expressions_ComparisonExpression ComparisonExpression.cpp
+add_library(quickstep_queryoptimizer_expressions_CommonSubexpression
+ CommonSubexpression.cpp
+ CommonSubexpression.hpp)
+add_library(quickstep_queryoptimizer_expressions_ComparisonExpression
+ ComparisonExpression.cpp
ComparisonExpression.hpp)
add_library(quickstep_queryoptimizer_expressions_Exists Exists.cpp Exists.hpp)
add_library(quickstep_queryoptimizer_expressions_Expression ../../empty_src.cpp Expression.hpp)
@@ -43,7 +47,9 @@ add_library(quickstep_queryoptimizer_expressions_SearchedCase SearchedCase.cpp S
add_library(quickstep_queryoptimizer_expressions_SimpleCase SimpleCase.cpp SimpleCase.hpp)
add_library(quickstep_queryoptimizer_expressions_SubqueryExpression SubqueryExpression.cpp SubqueryExpression.hpp)
add_library(quickstep_queryoptimizer_expressions_UnaryExpression UnaryExpression.cpp UnaryExpression.hpp)
-add_library(quickstep_queryoptimizer_expressions_WindowAggregateFunction WindowAggregateFunction.cpp WindowAggregateFunction.hpp)
+add_library(quickstep_queryoptimizer_expressions_WindowAggregateFunction
+ WindowAggregateFunction.cpp
+ WindowAggregateFunction.hpp)
# Link dependencies:
target_link_libraries(quickstep_queryoptimizer_expressions_AggregateFunction
@@ -78,6 +84,7 @@ target_link_libraries(quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_Expression
quickstep_queryoptimizer_expressions_ExpressionType
quickstep_queryoptimizer_expressions_NamedExpression
+ quickstep_queryoptimizer_expressions_PatternMatcher
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_expressions_BinaryExpression
glog
@@ -91,6 +98,7 @@ target_link_libraries(quickstep_queryoptimizer_expressions_BinaryExpression
quickstep_queryoptimizer_expressions_Scalar
quickstep_types_operations_binaryoperations_BinaryOperation
quickstep_types_operations_binaryoperations_BinaryOperationID
+ quickstep_utility_HashPair
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_expressions_Cast
glog
@@ -105,6 +113,18 @@ target_link_libraries(quickstep_queryoptimizer_expressions_Cast
quickstep_queryoptimizer_expressions_Scalar
quickstep_types_Type
quickstep_types_operations_unaryoperations_NumericCastOperation
+ quickstep_utility_HashPair
+ quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_expressions_CommonSubexpression
+ glog
+ quickstep_expressions_scalar_ScalarSharedExpression
+ quickstep_queryoptimizer_OptimizerTree
+ quickstep_queryoptimizer_expressions_AttributeReference
+ quickstep_queryoptimizer_expressions_ExprId
+ quickstep_queryoptimizer_expressions_Expression
+ quickstep_queryoptimizer_expressions_ExpressionType
+ quickstep_queryoptimizer_expressions_PatternMatcher
+ quickstep_queryoptimizer_expressions_Scalar
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_expressions_ComparisonExpression
glog
@@ -233,6 +253,7 @@ target_link_libraries(quickstep_queryoptimizer_expressions_Scalar
glog
quickstep_queryoptimizer_expressions_ExprId
quickstep_queryoptimizer_expressions_Expression
+ quickstep_utility_HashError
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_expressions_ScalarLiteral
glog
@@ -242,9 +263,11 @@ target_link_libraries(quickstep_queryoptimizer_expressions_ScalarLiteral
quickstep_queryoptimizer_expressions_ExprId
quickstep_queryoptimizer_expressions_Expression
quickstep_queryoptimizer_expressions_ExpressionType
+ quickstep_queryoptimizer_expressions_PatternMatcher
quickstep_queryoptimizer_expressions_Scalar
quickstep_types_Type
quickstep_types_TypedValue
+ quickstep_utility_HashPair
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_expressions_SearchedCase
quickstep_expressions_predicate_Predicate
@@ -272,12 +295,14 @@ target_link_libraries(quickstep_queryoptimizer_expressions_SimpleCase
quickstep_queryoptimizer_expressions_ExprId
quickstep_queryoptimizer_expressions_Expression
quickstep_queryoptimizer_expressions_ExpressionType
+ quickstep_queryoptimizer_expressions_PatternMatcher
quickstep_queryoptimizer_expressions_Predicate
quickstep_queryoptimizer_expressions_Scalar
quickstep_types_Type
quickstep_types_operations_comparisons_ComparisonFactory
quickstep_types_operations_comparisons_ComparisonID
quickstep_utility_Cast
+ quickstep_utility_HashPair
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_expressions_SubqueryExpression
glog
@@ -301,6 +326,7 @@ target_link_libraries(quickstep_queryoptimizer_expressions_UnaryExpression
quickstep_queryoptimizer_expressions_Scalar
quickstep_types_operations_unaryoperations_UnaryOperation
quickstep_types_operations_unaryoperations_UnaryOperationID
+ quickstep_utility_HashPair
quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_expressions_WindowAggregateFunction
glog
@@ -324,6 +350,7 @@ target_link_libraries(quickstep_queryoptimizer_expressions
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_BinaryExpression
quickstep_queryoptimizer_expressions_Cast
+ quickstep_queryoptimizer_expressions_CommonSubexpression
quickstep_queryoptimizer_expressions_ComparisonExpression
quickstep_queryoptimizer_expressions_Exists
quickstep_queryoptimizer_expressions_Expression
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/Cast.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/Cast.cpp b/query_optimizer/expressions/Cast.cpp
index c0813c5..f4cac8b 100644
--- a/query_optimizer/expressions/Cast.cpp
+++ b/query_optimizer/expressions/Cast.cpp
@@ -33,6 +33,7 @@
#include "query_optimizer/expressions/Scalar.hpp"
#include "types/Type.hpp"
#include "types/operations/unary_operations/NumericCastOperation.hpp"
+#include "utility/HashPair.hpp"
#include "glog/logging.h"
@@ -55,6 +56,21 @@ ExpressionPtr Cast::copyWithNewChildren(
operand_->concretize(substitution_map));
}
+std::size_t Cast::computeHash() const {
+ return CombineHashes(
+ CombineHashes(static_cast<std::size_t>(ExpressionType::kCast),
+ operand_->hash()),
+ static_cast<std::size_t>(target_type_.getTypeID()));
+}
+
+bool Cast::equals(const ScalarPtr &other) const {
+ CastPtr expr;
+ if (SomeCast::MatchesWithConditionalCast(other, &expr)) {
+ return operand_->equals(expr->operand_) && target_type_.equals(expr->target_type_);
+ }
+ return false;
+}
+
void Cast::getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/Cast.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/Cast.hpp b/query_optimizer/expressions/Cast.hpp
index ac5bd02..11be775 100644
--- a/query_optimizer/expressions/Cast.hpp
+++ b/query_optimizer/expressions/Cast.hpp
@@ -78,6 +78,8 @@ class Cast : public Scalar {
::quickstep::Scalar* concretize(
const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+ bool equals(const ScalarPtr &other) const override;
+
/**
* @brief Creates a Cast expression that converts \p operand to \p target_type.
*
@@ -90,6 +92,8 @@ class Cast : public Scalar {
}
protected:
+ std::size_t computeHash() const override;
+
void getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/CommonSubexpression.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/CommonSubexpression.cpp b/query_optimizer/expressions/CommonSubexpression.cpp
new file mode 100644
index 0000000..558b1fa
--- /dev/null
+++ b/query_optimizer/expressions/CommonSubexpression.cpp
@@ -0,0 +1,70 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ **/
+
+#include "query_optimizer/expressions/CommonSubexpression.hpp"
+
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include "expressions/scalar/ScalarSharedExpression.hpp"
+#include "query_optimizer/OptimizerTree.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/expressions/Expression.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
+#include "query_optimizer/expressions/Scalar.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+namespace expressions {
+
+ExpressionPtr CommonSubexpression::copyWithNewChildren(
+ const std::vector<ExpressionPtr> &new_children) const {
+ DCHECK_EQ(new_children.size(), children().size());
+ DCHECK(SomeScalar::Matches(new_children[0]));
+ return CommonSubexpression::Create(
+ common_subexpression_id_,
+ std::static_pointer_cast<const Scalar>(new_children[0]));
+}
+
+::quickstep::Scalar* CommonSubexpression::concretize(
+ const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+ return new ::quickstep::ScalarSharedExpression(
+ common_subexpression_id_, operand_->concretize(substitution_map));
+}
+
+void CommonSubexpression::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 {
+ inline_field_names->push_back("common_subexpression_id");
+ inline_field_values->push_back(std::to_string(common_subexpression_id_));
+
+ non_container_child_field_names->push_back("Operand");
+ non_container_child_fields->push_back(operand_);
+}
+
+} // namespace expressions
+} // namespace optimizer
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/CommonSubexpression.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/CommonSubexpression.hpp b/query_optimizer/expressions/CommonSubexpression.hpp
new file mode 100644
index 0000000..c642996
--- /dev/null
+++ b/query_optimizer/expressions/CommonSubexpression.hpp
@@ -0,0 +1,133 @@
+/**
+ * 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_EXPRESSIONS_COMMON_SUBEXPRESSION_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_EXPRESSIONS_COMMON_SUBEXPRESSION_HPP_
+
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/expressions/Expression.hpp"
+#include "query_optimizer/expressions/ExpressionType.hpp"
+#include "query_optimizer/expressions/Scalar.hpp"
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+class Scalar;
+class Type;
+
+namespace optimizer {
+namespace expressions {
+
+/** \addtogroup OptimizerExpressions
+ * @{
+ */
+
+class CommonSubexpression;
+typedef std::shared_ptr<const CommonSubexpression> CommonSubexpressionPtr;
+
+class CommonSubexpression : public Scalar {
+ public:
+ ExpressionType getExpressionType() const override {
+ return ExpressionType::kCommonSubexpression;
+ }
+
+ std::string getName() const override {
+ return "CommonSubexpression";
+ }
+
+ bool isConstant() const override {
+ return operand_->isConstant();
+ }
+
+ inline ExprId common_subexpression_id() const {
+ return common_subexpression_id_;
+ }
+
+ /**
+ * @return The operand that represents the common subexpression.
+ */
+ const ScalarPtr& operand() const {
+ return operand_;
+ }
+
+ const Type& getValueType() const override {
+ return operand_->getValueType();
+ }
+
+ ExpressionPtr copyWithNewChildren(
+ const std::vector<ExpressionPtr> &new_children) const override;
+
+ std::vector<AttributeReferencePtr> getReferencedAttributes() const override {
+ return operand_->getReferencedAttributes();
+ }
+
+ ::quickstep::Scalar* concretize(
+ const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+
+ /**
+ * @brief Creates an immutable CommonSubexpression.
+ *
+ * @param operand The operand that represents the common subexpression.
+ * @return An immutable CommonSubexpression that is shared among multiple
+ * expressions.
+ */
+ static CommonSubexpressionPtr Create(const ExprId common_subexpression_id,
+ const ScalarPtr &operand) {
+ return CommonSubexpressionPtr(
+ new CommonSubexpression(common_subexpression_id, operand));
+ }
+
+ protected:
+ void getFieldStringItems(
+ std::vector<std::string> *inline_field_names,
+ std::vector<std::string> *inline_field_values,
+ std::vector<std::string> *non_container_child_field_names,
+ std::vector<OptimizerTreeBaseNodePtr> *non_container_child_fields,
+ std::vector<std::string> *container_child_field_names,
+ std::vector<std::vector<OptimizerTreeBaseNodePtr>> *container_child_fields) const override;
+
+ private:
+ CommonSubexpression(const ExprId common_subexpression_id,
+ const ScalarPtr &operand)
+ : common_subexpression_id_(common_subexpression_id),
+ operand_(operand) {
+ addChild(operand);
+ }
+
+ ExprId common_subexpression_id_;
+ ScalarPtr operand_;
+
+ DISALLOW_COPY_AND_ASSIGN(CommonSubexpression);
+};
+
+/** @} */
+
+} // namespace expressions
+} // namespace optimizer
+} // namespace quickstep
+
+#endif // QUICKSTEP_QUERY_OPTIMIZER_EXPRESSIONS_COMMON_SUBEXPRESSION_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/ExpressionType.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/ExpressionType.hpp b/query_optimizer/expressions/ExpressionType.hpp
index 5008f1d..ba7f639 100644
--- a/query_optimizer/expressions/ExpressionType.hpp
+++ b/query_optimizer/expressions/ExpressionType.hpp
@@ -32,11 +32,12 @@ namespace expressions {
* @brief Optimizer expression types.
**/
enum class ExpressionType {
- kAggregateFunction,
+ kAggregateFunction = 0,
kAlias,
kAttributeReference,
kBinaryExpression,
kCast,
+ kCommonSubexpression,
kComparisonExpression,
kExists,
kInTableQuery,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/ExpressionUtil.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/ExpressionUtil.hpp b/query_optimizer/expressions/ExpressionUtil.hpp
index 6b8666e..29d90f0 100644
--- a/query_optimizer/expressions/ExpressionUtil.hpp
+++ b/query_optimizer/expressions/ExpressionUtil.hpp
@@ -85,9 +85,9 @@ template <class NamedExpressionType1, class NamedExpressionType2>
bool ContainsExpression(
const std::vector<std::shared_ptr<const NamedExpressionType1>> &expressions,
const std::shared_ptr<const NamedExpressionType2> &expression_to_check) {
- for (const std::shared_ptr<const NamedExpressionType1> &expression :
- expressions) {
- if (expression->equals(expression_to_check)) {
+ for (const auto &expression : expressions) {
+ if (expression->id() == expression_to_check->id()) {
+ DCHECK(expression->getExpressionType() == expression_to_check->getExpressionType());
return true;
}
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/NamedExpression.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/NamedExpression.cpp b/query_optimizer/expressions/NamedExpression.cpp
index 992a84a..2c2beac 100644
--- a/query_optimizer/expressions/NamedExpression.cpp
+++ b/query_optimizer/expressions/NamedExpression.cpp
@@ -25,6 +25,8 @@
#include "query_optimizer/OptimizerTree.hpp"
#include "types/Type.hpp"
+#include "glog/logging.h"
+
namespace quickstep {
namespace optimizer {
namespace expressions {
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/NamedExpression.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/NamedExpression.hpp b/query_optimizer/expressions/NamedExpression.hpp
index 9de8005..6725567 100644
--- a/query_optimizer/expressions/NamedExpression.hpp
+++ b/query_optimizer/expressions/NamedExpression.hpp
@@ -69,19 +69,6 @@ class NamedExpression : public Scalar {
*/
inline const std::string& relation_name() const { return relation_name_; }
- /**
- * @brief Compares this named expression with \p other. Two named expressions
- * are equal if they have the same ExprId and are both Alias or
- * AttributeReference.
- *
- * @param other Another named expression to compare with.
- * @return True if the named expression is equal to \p other.
- */
- inline bool equals(const NamedExpressionPtr &other) const {
- return getExpressionType() == other->getExpressionType() &&
- id_ == other->id();
- }
-
protected:
/**
* @brief Constructor.
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/PatternMatcher.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/PatternMatcher.hpp b/query_optimizer/expressions/PatternMatcher.hpp
index 18d6b1c..e30a4d9 100644
--- a/query_optimizer/expressions/PatternMatcher.hpp
+++ b/query_optimizer/expressions/PatternMatcher.hpp
@@ -35,6 +35,7 @@ class Avg;
class AttributeReference;
class BinaryExpression;
class Cast;
+class CommonSubexpression;
class ComparisonExpression;
class Count;
class Exists;
@@ -50,6 +51,7 @@ class Predicate;
class PredicateLiteral;
class Scalar;
class ScalarLiteral;
+class SimpleCase;
class Sum;
class UnaryExpression;
class WindowAggregateFunction;
@@ -145,16 +147,13 @@ using SomeScalar = SomeExpressionNode<Scalar,
ExpressionType::kAttributeReference,
ExpressionType::kBinaryExpression,
ExpressionType::kCast,
- ExpressionType::kComparisonExpression,
- ExpressionType::kLogicalAnd,
- ExpressionType::kLogicalNot,
- ExpressionType::kLogicalOr,
- ExpressionType::kPredicateLiteral,
+ ExpressionType::kCommonSubexpression,
ExpressionType::kScalarLiteral,
ExpressionType::kSearchedCase,
ExpressionType::kSimpleCase,
ExpressionType::kUnaryExpression>;
using SomeScalarLiteral = SomeExpressionNode<ScalarLiteral, ExpressionType::kScalarLiteral>;
+using SomeSimpleCase = SomeExpressionNode<SimpleCase, ExpressionType::kSimpleCase>;
using SomeUnaryExpression = SomeExpressionNode<UnaryExpression, ExpressionType::kUnaryExpression>;
using SomeWindowAggregateFunction = SomeExpressionNode<WindowAggregateFunction,
ExpressionType::kWindowAggregateFunction>;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/Scalar.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/Scalar.hpp b/query_optimizer/expressions/Scalar.hpp
index 4870118..36a8de5 100644
--- a/query_optimizer/expressions/Scalar.hpp
+++ b/query_optimizer/expressions/Scalar.hpp
@@ -20,11 +20,13 @@
#ifndef QUICKSTEP_QUERY_OPTIMIZER_EXPRESSIONS_SCALAR_HPP_
#define QUICKSTEP_QUERY_OPTIMIZER_EXPRESSIONS_SCALAR_HPP_
+#include <cstddef>
#include <memory>
#include <unordered_map>
#include "query_optimizer/expressions/Expression.hpp"
#include "query_optimizer/expressions/ExprId.hpp"
+#include "utility/HashError.hpp"
#include "utility/Macros.hpp"
namespace quickstep {
@@ -65,10 +67,27 @@ class Scalar : public Expression {
const std::unordered_map<ExprId, const CatalogAttribute*>& substitution_map)
const = 0;
+ virtual bool equals(const ScalarPtr &other) const {
+ return false;
+ }
+
+ std::size_t hash() const {
+ if (hash_cache_ == nullptr) {
+ hash_cache_ = std::make_unique<std::size_t>(computeHash());
+ }
+ return *hash_cache_;
+ }
+
protected:
Scalar() {}
+ virtual std::size_t computeHash() const {
+ throw HashNotSupported("Unsupported computeHash() in " + getName());
+ }
+
private:
+ mutable std::unique_ptr<std::size_t> hash_cache_;
+
DISALLOW_COPY_AND_ASSIGN(Scalar);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/ScalarLiteral.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/ScalarLiteral.cpp b/query_optimizer/expressions/ScalarLiteral.cpp
index d70c4cf..180d760 100644
--- a/query_optimizer/expressions/ScalarLiteral.cpp
+++ b/query_optimizer/expressions/ScalarLiteral.cpp
@@ -28,7 +28,9 @@
#include "query_optimizer/expressions/AttributeReference.hpp"
#include "query_optimizer/expressions/ExprId.hpp"
#include "query_optimizer/expressions/Expression.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
#include "types/Type.hpp"
+#include "utility/HashPair.hpp"
#include "glog/logging.h"
@@ -51,6 +53,19 @@ ExpressionPtr ScalarLiteral::copyWithNewChildren(
return new ::quickstep::ScalarLiteral(value_, value_type_);
}
+std::size_t ScalarLiteral::computeHash() const {
+ return CombineHashes(static_cast<std::size_t>(ExpressionType::kScalarLiteral),
+ value_.getHash());
+}
+
+bool ScalarLiteral::equals(const ScalarPtr &other) const {
+ ScalarLiteralPtr lit;
+ if (SomeScalarLiteral::MatchesWithConditionalCast(other, &lit)) {
+ return value_type_.equals(lit->getValueType()) && value_.fastEqualCheck(lit->value());
+ }
+ return false;
+}
+
void ScalarLiteral::getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/ScalarLiteral.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/ScalarLiteral.hpp b/query_optimizer/expressions/ScalarLiteral.hpp
index 8ebc41c..8a73405 100644
--- a/query_optimizer/expressions/ScalarLiteral.hpp
+++ b/query_optimizer/expressions/ScalarLiteral.hpp
@@ -81,6 +81,8 @@ class ScalarLiteral : public Scalar {
::quickstep::Scalar* concretize(
const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+ bool equals(const ScalarPtr &other) const override;
+
/**
* @brief Creates an immutable ScalarLiteral.
* @param literal_value The literal value.
@@ -92,6 +94,8 @@ class ScalarLiteral : public Scalar {
}
protected:
+ std::size_t computeHash() const override;
+
void getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/SimpleCase.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/SimpleCase.cpp b/query_optimizer/expressions/SimpleCase.cpp
index 454d7b9..ccdd8e5 100644
--- a/query_optimizer/expressions/SimpleCase.cpp
+++ b/query_optimizer/expressions/SimpleCase.cpp
@@ -31,12 +31,14 @@
#include "query_optimizer/expressions/AttributeReference.hpp"
#include "query_optimizer/expressions/ComparisonExpression.hpp"
#include "query_optimizer/expressions/Expression.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
#include "query_optimizer/expressions/Predicate.hpp"
#include "query_optimizer/expressions/Scalar.hpp"
#include "types/Type.hpp"
#include "types/operations/comparisons/ComparisonID.hpp"
#include "types/operations/comparisons/ComparisonFactory.hpp"
#include "utility/Cast.hpp"
+#include "utility/HashPair.hpp"
#include "glog/logging.h"
@@ -161,6 +163,50 @@ ExpressionPtr SimpleCase::copyWithNewChildren(const std::vector<ExpressionPtr> &
else_result_expression.release());
}
+std::size_t SimpleCase::computeHash() const {
+ std::size_t hash_code =
+ CombineHashes(static_cast<std::size_t>(ExpressionType::kSimpleCase),
+ case_operand_->hash());
+ for (std::size_t i = 0; i < condition_operands_.size(); ++i) {
+ hash_code = CombineHashes(hash_code, condition_operands_[i]->hash());
+ hash_code = CombineHashes(hash_code, conditional_result_expressions_[i]->hash());
+ }
+ if (else_result_expression_ != nullptr) {
+ hash_code = CombineHashes(hash_code, else_result_expression_->hash());
+ }
+ return hash_code;
+}
+
+bool SimpleCase::equals(const ScalarPtr &other) const {
+ SimpleCasePtr expr;
+ if (!SomeSimpleCase::MatchesWithConditionalCast(other, &expr)) {
+ return false;
+ }
+ if (!case_operand_->equals(expr->case_operand_)) {
+ return false;
+ }
+ if (condition_operands_.size() != expr->condition_operands_.size()) {
+ return false;
+ }
+ for (std::size_t i = 0; i < condition_operands_.size(); ++i) {
+ if (!condition_operands_[i]->equals(expr->condition_operands_[i])
+ || !conditional_result_expressions_[i]->equals(
+ expr->conditional_result_expressions_[i])) {
+ return false;
+ }
+ }
+ if ((else_result_expression_ == nullptr
+ || expr->else_result_expression_ == nullptr)
+ && else_result_expression_ != expr->else_result_expression_) {
+ return false;
+ }
+ if (!else_result_expression_->equals(expr->else_result_expression_)) {
+ return false;
+ }
+ DCHECK(value_type_.equals(expr->value_type_));
+ return true;
+}
+
void SimpleCase::getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/SimpleCase.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/SimpleCase.hpp b/query_optimizer/expressions/SimpleCase.hpp
index 897d87f..bf3decd 100644
--- a/query_optimizer/expressions/SimpleCase.hpp
+++ b/query_optimizer/expressions/SimpleCase.hpp
@@ -110,6 +110,8 @@ class SimpleCase : public Scalar {
::quickstep::Scalar* concretize(
const std::unordered_map<ExprId, const CatalogAttribute*>& substitution_map) const override;
+ bool equals(const ScalarPtr &other) const override;
+
/**
* @brief Creates an immutable SimpleCase.
*
@@ -136,6 +138,8 @@ class SimpleCase : public Scalar {
}
protected:
+ std::size_t computeHash() const override;
+
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,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/UnaryExpression.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/UnaryExpression.cpp b/query_optimizer/expressions/UnaryExpression.cpp
index b0fff62..06a2ee1 100644
--- a/query_optimizer/expressions/UnaryExpression.cpp
+++ b/query_optimizer/expressions/UnaryExpression.cpp
@@ -31,6 +31,7 @@
#include "query_optimizer/expressions/Scalar.hpp"
#include "types/operations/unary_operations/UnaryOperation.hpp"
#include "types/operations/unary_operations/UnaryOperationID.hpp"
+#include "utility/HashPair.hpp"
#include "glog/logging.h"
@@ -56,6 +57,22 @@ ExpressionPtr UnaryExpression::copyWithNewChildren(
operation_, operand_->concretize(substitution_map));
}
+std::size_t UnaryExpression::computeHash() const {
+ return CombineHashes(
+ CombineHashes(static_cast<std::size_t>(ExpressionType::kUnaryExpression),
+ static_cast<std::size_t>(operation_.getUnaryOperationID())),
+ operand_->hash());
+}
+
+bool UnaryExpression::equals(const ScalarPtr &other) const {
+ UnaryExpressionPtr expr;
+ if (SomeUnaryExpression::MatchesWithConditionalCast(other, &expr)) {
+ return operation_.getUnaryOperationID() == expr->operation_.getUnaryOperationID()
+ && operand_->equals(expr->operand_);
+ }
+ return false;
+}
+
void UnaryExpression::getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/expressions/UnaryExpression.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/expressions/UnaryExpression.hpp b/query_optimizer/expressions/UnaryExpression.hpp
index c4542d0..2a9e97e 100644
--- a/query_optimizer/expressions/UnaryExpression.hpp
+++ b/query_optimizer/expressions/UnaryExpression.hpp
@@ -29,8 +29,10 @@
#include "query_optimizer/expressions/ExprId.hpp"
#include "query_optimizer/expressions/Expression.hpp"
#include "query_optimizer/expressions/ExpressionType.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
#include "query_optimizer/expressions/Scalar.hpp"
#include "types/operations/unary_operations/UnaryOperation.hpp"
+#include "utility/HashPair.hpp"
#include "utility/Macros.hpp"
#include "glog/logging.h"
@@ -85,6 +87,8 @@ class UnaryExpression : public Scalar {
::quickstep::Scalar* concretize(
const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+ bool equals(const ScalarPtr &other) const override;
+
/**
* @brief Creates an immutable UnaryExpression.
*
@@ -99,6 +103,8 @@ class UnaryExpression : public Scalar {
}
protected:
+ std::size_t computeHash() const override;
+
void getFieldStringItems(
std::vector<std::string> *inline_field_names,
std::vector<std::string> *inline_field_values,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/rules/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CMakeLists.txt b/query_optimizer/rules/CMakeLists.txt
index 6847951..b2d0f90 100644
--- a/query_optimizer/rules/CMakeLists.txt
+++ b/query_optimizer/rules/CMakeLists.txt
@@ -21,6 +21,9 @@ add_subdirectory(tests)
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_CommonSubexpressionExtraction
+ CommonSubexpressionExtraction.cpp
+ CommonSubexpressionExtraction.hpp)
add_library(quickstep_queryoptimizer_rules_FuseAggregateJoin FuseAggregateJoin.cpp FuseAggregateJoin.hpp)
add_library(quickstep_queryoptimizer_rules_GenerateJoins GenerateJoins.cpp GenerateJoins.hpp)
add_library(quickstep_queryoptimizer_rules_InjectJoinFilters InjectJoinFilters.cpp InjectJoinFilters.hpp)
@@ -77,6 +80,23 @@ target_link_libraries(quickstep_queryoptimizer_rules_CollapseProject
quickstep_queryoptimizer_rules_Rule
quickstep_queryoptimizer_rules_RuleHelper
quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_rules_CommonSubexpressionExtraction
+ glog
+ quickstep_queryoptimizer_OptimizerContext
+ quickstep_queryoptimizer_expressions_Alias
+ quickstep_queryoptimizer_expressions_CommonSubexpression
+ quickstep_queryoptimizer_expressions_Expression
+ quickstep_queryoptimizer_expressions_ExpressionType
+ quickstep_queryoptimizer_expressions_NamedExpression
+ quickstep_queryoptimizer_expressions_PatternMatcher
+ quickstep_queryoptimizer_expressions_Scalar
+ quickstep_queryoptimizer_physical_Aggregate
+ quickstep_queryoptimizer_physical_Physical
+ quickstep_queryoptimizer_physical_PhysicalType
+ quickstep_queryoptimizer_physical_Selection
+ quickstep_queryoptimizer_rules_Rule
+ quickstep_utility_HashError
+ quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_rules_FuseAggregateJoin
quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
quickstep_queryoptimizer_expressions_AggregateFunction
@@ -311,6 +331,7 @@ target_link_libraries(quickstep_queryoptimizer_rules
quickstep_queryoptimizer_rules_AttachLIPFilters
quickstep_queryoptimizer_rules_BottomUpRule
quickstep_queryoptimizer_rules_CollapseProject
+ quickstep_queryoptimizer_rules_CommonSubexpressionExtraction
quickstep_queryoptimizer_rules_FuseAggregateJoin
quickstep_queryoptimizer_rules_GenerateJoins
quickstep_queryoptimizer_rules_InjectJoinFilters
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/rules/CommonSubexpressionExtraction.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CommonSubexpressionExtraction.cpp b/query_optimizer/rules/CommonSubexpressionExtraction.cpp
new file mode 100644
index 0000000..b06d9fc
--- /dev/null
+++ b/query_optimizer/rules/CommonSubexpressionExtraction.cpp
@@ -0,0 +1,264 @@
+/**
+ * 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/CommonSubexpressionExtraction.hpp"
+
+#include <memory>
+#include <unordered_set>
+#include <vector>
+
+#include "query_optimizer/OptimizerContext.hpp"
+#include "query_optimizer/expressions/Alias.hpp"
+#include "query_optimizer/expressions/CommonSubexpression.hpp"
+#include "query_optimizer/expressions/ExpressionType.hpp"
+#include "query_optimizer/expressions/NamedExpression.hpp"
+#include "query_optimizer/expressions/PatternMatcher.hpp"
+#include "query_optimizer/expressions/Scalar.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/PhysicalType.hpp"
+#include "query_optimizer/physical/Selection.hpp"
+#include "utility/HashError.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace P = ::quickstep::optimizer::physical;
+
+CommonSubexpressionExtraction::CommonSubexpressionExtraction(
+ OptimizerContext *optimizer_context)
+ : optimizer_context_(optimizer_context) {
+ const std::vector<E::ExpressionType> whitelist = {
+ E::ExpressionType::kAlias,
+ E::ExpressionType::kAttributeReference,
+ E::ExpressionType::kAggregateFunction,
+ E::ExpressionType::kBinaryExpression,
+ E::ExpressionType::kCast,
+ E::ExpressionType::kCommonSubexpression,
+ E::ExpressionType::kScalarLiteral,
+ E::ExpressionType::kUnaryExpression
+ };
+
+ for (const auto &expr_type : whitelist) {
+ homogeneous_whitelist_.emplace(static_cast<int>(expr_type));
+ }
+}
+
+P::PhysicalPtr CommonSubexpressionExtraction::apply(const P::PhysicalPtr &input) {
+ DCHECK(input->getPhysicalType() == P::PhysicalType::kTopLevelPlan);
+
+ return applyInternal(input);
+}
+
+P::PhysicalPtr CommonSubexpressionExtraction::applyInternal(
+ const P::PhysicalPtr &input) {
+ std::vector<P::PhysicalPtr> new_children;
+ for (const auto &child : input->children()) {
+ new_children.emplace_back(applyInternal(child));
+ }
+
+ const P::PhysicalPtr node =
+ new_children == input->children()
+ ? input
+ : input->copyWithNewChildren(new_children);
+
+ switch (node->getPhysicalType()) {
+ case P::PhysicalType::kSelection: {
+ const P::SelectionPtr selection =
+ std::static_pointer_cast<const P::Selection>(node);
+
+ const std::vector<E::NamedExpressionPtr> new_expressions =
+ DownCast<E::NamedExpression>(
+ transformExpressions(UpCast(selection->project_expressions())));
+
+ if (new_expressions != selection->project_expressions()) {
+ return P::Selection::Create(selection->input(),
+ new_expressions,
+ selection->filter_predicate());
+ }
+ break;
+ }
+ case P::PhysicalType::kAggregate: {
+ const P::AggregatePtr aggregate =
+ std::static_pointer_cast<const P::Aggregate>(node);
+ std::vector<E::ExpressionPtr> expressions =
+ UpCast(aggregate->aggregate_expressions());
+ for (const auto &expr : aggregate->grouping_expressions()) {
+ expressions.emplace_back(expr);
+ }
+
+ const std::vector<E::ExpressionPtr> new_expressions =
+ transformExpressions(expressions);
+
+ if (new_expressions != expressions) {
+ std::vector<E::AliasPtr> new_aggregate_expressions;
+ std::vector<E::NamedExpressionPtr> new_grouping_expressions;
+ const std::size_t num_aggrs = aggregate->aggregate_expressions().size();
+
+ for (std::size_t i = 0; i < num_aggrs; ++i) {
+ DCHECK(E::SomeAlias::Matches(new_expressions[i]));
+ new_aggregate_expressions.emplace_back(
+ std::static_pointer_cast<const E::Alias>(new_expressions[i]));
+ }
+ for (std::size_t i = num_aggrs; i < new_expressions.size(); ++i) {
+ DCHECK(E::SomeNamedExpression::Matches(new_expressions[i]));
+ new_grouping_expressions.emplace_back(
+ std::static_pointer_cast<const E::NamedExpression>(new_expressions[i]));
+ }
+ return P::Aggregate::Create(aggregate->input(),
+ new_grouping_expressions,
+ new_aggregate_expressions,
+ aggregate->filter_predicate());
+ }
+ break;
+ }
+ default:
+ break;
+ }
+
+ return node;
+}
+
+std::vector<E::ExpressionPtr> CommonSubexpressionExtraction::transformExpressions(
+ const std::vector<E::ExpressionPtr> &expressions) {
+ ScalarCounter counter;
+ ScalarHashable hashable;
+ for (const auto &expr : expressions) {
+ visitAndCount(expr, &counter, &hashable);
+ }
+
+ ScalarMap substitution_map;
+ std::vector<E::ExpressionPtr> new_expressions;
+ for (const auto &expr : expressions) {
+ new_expressions.emplace_back(
+ visitAndTransform(expr, 1, counter, hashable, &substitution_map));
+ }
+ return new_expressions;
+}
+
+E::ExpressionPtr CommonSubexpressionExtraction::transformExpression(
+ const E::ExpressionPtr &expression) {
+ return transformExpressions({expression}).front();
+}
+
+bool CommonSubexpressionExtraction::visitAndCount(
+ const E::ExpressionPtr &expression,
+ ScalarCounter *counter,
+ ScalarHashable *hashable) {
+ bool children_hashable = true;
+
+ const auto homogeneous_whitelist_it =
+ homogeneous_whitelist_.find(static_cast<int>(expression->getExpressionType()));
+ if (homogeneous_whitelist_it != homogeneous_whitelist_.end()) {
+ for (const auto &child : expression->children()) {
+ children_hashable &= visitAndCount(child, counter, hashable);
+ }
+ }
+
+ E::ScalarPtr scalar;
+ if (children_hashable &&
+ E::SomeScalar::MatchesWithConditionalCast(expression, &scalar)) {
+ try {
+ ++(*counter)[scalar];
+ } catch (const HashNotSupported &e) {
+ return false;
+ }
+ hashable->emplace(scalar);
+ return true;
+ }
+ return false;
+}
+
+E::ExpressionPtr CommonSubexpressionExtraction::visitAndTransform(
+ const E::ExpressionPtr &expression,
+ const std::size_t max_reference_count,
+ const ScalarCounter &counter,
+ const ScalarHashable &hashable,
+ ScalarMap *substitution_map) {
+ // TODO: figure out whether it is beneficial.
+ if (expression->getExpressionType() == E::ExpressionType::kScalarLiteral ||
+ expression->getExpressionType() == E::ExpressionType::kAttributeReference) {
+ return expression;
+ }
+
+ E::ScalarPtr scalar;
+ const bool is_hashable =
+ E::SomeScalar::MatchesWithConditionalCast(expression, &scalar)
+ && hashable.find(scalar) != hashable.end();
+
+ std::size_t new_max_reference_count;
+ if (is_hashable) {
+ // CommonSubexpression node already generated.
+ const auto substitution_map_it = substitution_map->find(scalar);
+ if (substitution_map_it != substitution_map->end()) {
+ return substitution_map_it->second;
+ }
+
+ const auto counter_it = counter.find(scalar);
+ DCHECK(counter_it != counter.end());
+ DCHECK_LE(max_reference_count, counter_it->second);
+ new_max_reference_count = counter_it->second;
+ } else {
+ new_max_reference_count = max_reference_count;
+ }
+
+ std::vector<E::ExpressionPtr> new_children;
+ const auto homogeneous_whitelist_it =
+ homogeneous_whitelist_.find(static_cast<int>(expression->getExpressionType()));
+ if (homogeneous_whitelist_it == homogeneous_whitelist_.end()) {
+ for (const auto &child : expression->children()) {
+ new_children.emplace_back(transformExpression(child));
+ }
+ } else {
+ for (const auto &child : expression->children()) {
+ new_children.emplace_back(
+ visitAndTransform(child,
+ new_max_reference_count,
+ counter,
+ hashable,
+ substitution_map));
+ }
+ }
+
+ E::ExpressionPtr output;
+ if (new_children == expression->children()) {
+ output = expression;
+ } else {
+ output = std::static_pointer_cast<const E::Scalar>(
+ expression->copyWithNewChildren(new_children));
+ }
+
+ if (is_hashable && new_max_reference_count > max_reference_count) {
+ DCHECK(E::SomeScalar::Matches(output));
+ const E::CommonSubexpressionPtr common_subexpression =
+ E::CommonSubexpression::Create(
+ optimizer_context_->nextExprId(),
+ std::static_pointer_cast<const E::Scalar>(output));
+ substitution_map->emplace(scalar, common_subexpression);
+ output = common_subexpression;
+ }
+
+ return output;
+}
+
+} // namespace optimizer
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/query_optimizer/rules/CommonSubexpressionExtraction.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CommonSubexpressionExtraction.hpp b/query_optimizer/rules/CommonSubexpressionExtraction.hpp
new file mode 100644
index 0000000..121552c
--- /dev/null
+++ b/query_optimizer/rules/CommonSubexpressionExtraction.hpp
@@ -0,0 +1,135 @@
+/**
+ * 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_COMMON_SUBEXPRESSION_EXTRACTION_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_RULES_COMMON_SUBEXPRESSION_EXTRACTION_HPP_
+
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+
+#include "query_optimizer/expressions/CommonSubexpression.hpp"
+#include "query_optimizer/expressions/Expression.hpp"
+#include "query_optimizer/expressions/Scalar.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/rules/Rule.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+namespace optimizer {
+
+class OptimizerContext;
+
+/** \addtogroup OptimizerRules
+ * @{
+ */
+
+class CommonSubexpressionExtraction : public Rule<physical::Physical> {
+ public:
+ /**
+ * @brief Constructor.
+ */
+ CommonSubexpressionExtraction(OptimizerContext *optimizer_context);
+
+ ~CommonSubexpressionExtraction() override {}
+
+ std::string getName() const override {
+ return "CommonSubexpressionExtraction";
+ }
+
+ physical::PhysicalPtr apply(const physical::PhysicalPtr &input) override;
+
+ private:
+ physical::PhysicalPtr applyInternal(const physical::PhysicalPtr &input);
+
+ struct ScalarHash {
+ inline std::size_t operator()(const expressions::ScalarPtr &scalar) const {
+ return scalar->hash();
+ }
+ };
+
+ struct ScalarEqual {
+ inline bool operator()(const expressions::ScalarPtr &lhs,
+ const expressions::ScalarPtr &rhs) const {
+ return lhs->equals(rhs);
+ }
+ };
+
+ using ScalarCounter =
+ std::unordered_map<expressions::ScalarPtr, std::size_t, ScalarHash, ScalarEqual>;
+
+ using ScalarMap =
+ std::unordered_map<expressions::ScalarPtr,
+ expressions::CommonSubexpressionPtr,
+ ScalarHash,
+ ScalarEqual>;
+
+ using ScalarHashable = std::unordered_set<expressions::ScalarPtr>;
+
+ std::vector<expressions::ExpressionPtr> transformExpressions(
+ const std::vector<expressions::ExpressionPtr> &expressions);
+
+ expressions::ExpressionPtr transformExpression(
+ const expressions::ExpressionPtr &expression);
+
+ bool visitAndCount(
+ const expressions::ExpressionPtr &expression,
+ ScalarCounter *counter,
+ ScalarHashable *hashable);
+
+ expressions::ExpressionPtr visitAndTransform(
+ const expressions::ExpressionPtr &expression,
+ const std::size_t max_reference_count,
+ const ScalarCounter &counter,
+ const ScalarHashable &hashable,
+ ScalarMap *substitution_map);
+
+ template <typename ScalarSubclassT>
+ static std::vector<expressions::ExpressionPtr> UpCast(
+ const std::vector<std::shared_ptr<const ScalarSubclassT>> &expressions) {
+ std::vector<expressions::ExpressionPtr> output;
+ for (const auto &expr : expressions) {
+ output.emplace_back(expr);
+ }
+ return output;
+ }
+
+ template <typename ScalarSubclassT>
+ static std::vector<std::shared_ptr<const ScalarSubclassT>> DownCast(
+ const std::vector<expressions::ExpressionPtr> &expressions) {
+ std::vector<std::shared_ptr<const ScalarSubclassT>> output;
+ for (const auto &expr : expressions) {
+ output.emplace_back(std::static_pointer_cast<const ScalarSubclassT>(expr));
+ }
+ return output;
+ }
+
+ OptimizerContext *optimizer_context_;
+ std::unordered_set<int> homogeneous_whitelist_;
+
+ DISALLOW_COPY_AND_ASSIGN(CommonSubexpressionExtraction);
+};
+
+/** @} */
+
+} // namespace optimizer
+} // namespace quickstep
+
+#endif // QUICKSTEP_QUERY_OPTIMIZER_RULES_COMMON_SUBEXPRESSION_EXTRACTION_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/cd01af24/relational_operators/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/relational_operators/CMakeLists.txt b/relational_operators/CMakeLists.txt
index 4ea809b..b93ec49 100644
--- a/relational_operators/CMakeLists.txt
+++ b/relational_operators/CMakeLists.txt
@@ -262,6 +262,7 @@ target_link_libraries(quickstep_relationaloperators_HashJoinOperator
quickstep_expressions_predicate_Predicate
quickstep_expressions_scalar_Scalar
quickstep_expressions_scalar_ScalarAttribute
+ quickstep_expressions_scalar_ScalarCache
quickstep_queryexecution_QueryContext
quickstep_queryexecution_WorkOrderProtosContainer
quickstep_queryexecution_WorkOrdersContainer
@@ -318,6 +319,7 @@ target_link_libraries(quickstep_relationaloperators_NestedLoopsJoinOperator
quickstep_catalog_CatalogTypedefs
quickstep_expressions_predicate_Predicate
quickstep_expressions_scalar_Scalar
+ quickstep_expressions_scalar_ScalarCache
quickstep_queryexecution_QueryContext
quickstep_queryexecution_WorkOrderProtosContainer
quickstep_queryexecution_WorkOrdersContainer