quickstep-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hbdeshm...@apache.org
Subject [17/50] [abbrv] incubator-quickstep git commit: Change default aggregate_hashtable_type from LinearOpenAddressing to SeparateChaining (#210)
Date Wed, 08 Jun 2016 13:21:17 GMT
Change default aggregate_hashtable_type from LinearOpenAddressing to SeparateChaining  (#210)


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

Branch: refs/heads/query-manager-used-in-foreman
Commit: 6c9108a6d468345baa0bab2f9901cf48b84363fa
Parents: bbaff7a
Author: Jianqiao Zhu <jianqiao@cs.wisc.edu>
Authored: Thu May 5 09:58:45 2016 -0500
Committer: Zuyu Zhang <zzhang@pivotal.io>
Committed: Mon May 30 15:46:17 2016 -0700

----------------------------------------------------------------------
 query_optimizer/ExecutionGenerator.cpp          | 69 ++++++++++++--------
 .../tests/execution_generator/Select.test       | 23 +++----
 storage/AggregationOperationState.cpp           | 28 +++++++-
 storage/AggregationOperationState.hpp           |  5 ++
 storage/AggregationOperationState.proto         |  5 ++
 5 files changed, 90 insertions(+), 40 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6c9108a6/query_optimizer/ExecutionGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.cpp b/query_optimizer/ExecutionGenerator.cpp
index c34f084..077d35d 100644
--- a/query_optimizer/ExecutionGenerator.cpp
+++ b/query_optimizer/ExecutionGenerator.cpp
@@ -135,7 +135,7 @@ static const volatile bool join_hashtable_type_dummy
     = gflags::RegisterFlagValidator(&FLAGS_join_hashtable_type,
                                     &ValidateHashTableImplTypeString);
 
-DEFINE_string(aggregate_hashtable_type, "LinearOpenAddressing",
+DEFINE_string(aggregate_hashtable_type, "SeparateChaining",
               "HashTable implementation to use for aggregates with GROUP BY "
               "(valid options are SeparateChaining or LinearOpenAddressing)");
 static const volatile bool aggregate_hashtable_type_dummy
@@ -1285,6 +1285,35 @@ void ExecutionGenerator::convertAggregate(
       findRelationInfoOutputByPhysical(physical_plan->input());
   aggr_state_proto->set_relation_id(input_relation_info->relation->getID());
 
+  std::vector<const Type*> group_by_types;
+  for (const E::NamedExpressionPtr &grouping_expression : physical_plan->grouping_expressions())
{
+    unique_ptr<const Scalar> execution_group_by_expression;
+    E::AliasPtr alias;
+    if (E::SomeAlias::MatchesWithConditionalCast(grouping_expression, &alias)) {
+      E::ScalarPtr scalar;
+      // NOTE(zuyu): For aggregate expressions, all child expressions of an
+      // Alias should be a Scalar.
+      CHECK(E::SomeScalar::MatchesWithConditionalCast(alias->expression(), &scalar))
+          << alias->toString();
+      execution_group_by_expression.reset(scalar->concretize(attribute_substitution_map_));
+    } else {
+      execution_group_by_expression.reset(
+          grouping_expression->concretize(attribute_substitution_map_));
+    }
+    aggr_state_proto->add_group_by_expressions()->CopyFrom(execution_group_by_expression->getProto());
+    group_by_types.push_back(&execution_group_by_expression->getType());
+  }
+
+  if (!group_by_types.empty()) {
+    // SimplifyHashTableImplTypeProto() switches the hash table implementation
+    // from SeparateChaining to SimpleScalarSeparateChaining when there is a
+    // single scalar key type with a reversible hash function.
+    aggr_state_proto->set_hash_table_impl_type(
+        SimplifyHashTableImplTypeProto(
+            HashTableImplTypeProtoFromString(FLAGS_aggregate_hashtable_type),
+            group_by_types));
+  }
+
   for (const E::AliasPtr &named_aggregate_expression : physical_plan->aggregate_expressions())
{
     const E::AggregateFunctionPtr unnamed_aggregate_expression =
         std::static_pointer_cast<const E::AggregateFunction>(named_aggregate_expression->expression());
@@ -1304,25 +1333,19 @@ void ExecutionGenerator::convertAggregate(
 
     // Set whether it is a DISTINCT aggregation.
     aggr_proto->set_is_distinct(unnamed_aggregate_expression->is_distinct());
-  }
 
-  std::vector<const Type*> group_by_types;
-  for (const E::NamedExpressionPtr &grouping_expression : physical_plan->grouping_expressions())
{
-    unique_ptr<const Scalar> execution_group_by_expression;
-    E::AliasPtr alias;
-    if (E::SomeAlias::MatchesWithConditionalCast(grouping_expression, &alias)) {
-      E::ScalarPtr scalar;
-      // NOTE(zuyu): For aggregate expressions, all child expressions of an
-      // Alias should be a Scalar.
-      CHECK(E::SomeScalar::MatchesWithConditionalCast(alias->expression(), &scalar))
-          << alias->toString();
-      execution_group_by_expression.reset(scalar->concretize(attribute_substitution_map_));
-    } else {
-      execution_group_by_expression.reset(
-          grouping_expression->concretize(attribute_substitution_map_));
+    // Add distinctify hash table impl type if it is a DISTINCT aggregation.
+    if (unnamed_aggregate_expression->is_distinct()) {
+      if (group_by_types.empty()) {
+        aggr_state_proto->add_distinctify_hash_table_impl_types(
+            SimplifyHashTableImplTypeProto(
+                HashTableImplTypeProtoFromString(FLAGS_aggregate_hashtable_type),
+                {&unnamed_aggregate_expression->getValueType()}));
+      } else {
+        aggr_state_proto->add_distinctify_hash_table_impl_types(
+            HashTableImplTypeProtoFromString(FLAGS_aggregate_hashtable_type));
+      }
     }
-    aggr_state_proto->add_group_by_expressions()->CopyFrom(execution_group_by_expression->getProto());
-    group_by_types.push_back(&execution_group_by_expression->getType());
   }
 
   if (physical_plan->filter_predicate() != nullptr) {
@@ -1332,16 +1355,6 @@ void ExecutionGenerator::convertAggregate(
 
   aggr_state_proto->set_estimated_num_entries(cost_model_->estimateCardinality(physical_plan));
 
-  if (!group_by_types.empty()) {
-    // SimplifyHashTableImplTypeProto() switches the hash table implementation
-    // from SeparateChaining to SimpleScalarSeparateChaining when there is a
-    // single scalar key type with a reversible hash function.
-    aggr_state_proto->set_hash_table_impl_type(
-        SimplifyHashTableImplTypeProto(
-            HashTableImplTypeProtoFromString(FLAGS_aggregate_hashtable_type),
-            group_by_types));
-  }
-
   const QueryPlan::DAGNodeIndex aggregation_operator_index =
       execution_plan_->addRelationalOperator(
           new AggregationOperator(

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6c9108a6/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 a08b012..390b7b6 100644
--- a/query_optimizer/tests/execution_generator/Select.test
+++ b/query_optimizer/tests/execution_generator/Select.test
@@ -535,21 +535,12 @@ WHERE int_col = 2;
 
 SELECT int_col
 FROM test
-GROUP BY int_col;
+GROUP BY int_col
+ORDER BY int_col;
 --
 +-----------+
 |int_col    |
 +-----------+
-|          2|
-|          4|
-|          6|
-|          8|
-|         12|
-|         14|
-|         16|
-|         18|
-|         22|
-|         24|
 |        -23|
 |        -21|
 |        -19|
@@ -562,6 +553,16 @@ GROUP BY int_col;
 |         -5|
 |         -3|
 |         -1|
+|          2|
+|          4|
+|          6|
+|          8|
+|         12|
+|         14|
+|         16|
+|         18|
+|         22|
+|         24|
 +-----------+
 ==
 

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6c9108a6/storage/AggregationOperationState.cpp
----------------------------------------------------------------------
diff --git a/storage/AggregationOperationState.cpp b/storage/AggregationOperationState.cpp
index a3a669c..d209ceb 100644
--- a/storage/AggregationOperationState.cpp
+++ b/storage/AggregationOperationState.cpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015-2016 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -64,6 +66,7 @@ AggregationOperationState::AggregationOperationState(
     const Predicate *predicate,
     const std::size_t estimated_num_entries,
     const HashTableImplType hash_table_impl_type,
+    const std::vector<HashTableImplType> &distinctify_hash_table_impl_types,
     StorageManager *storage_manager)
     : input_relation_(input_relation),
       predicate_(predicate),
@@ -101,6 +104,8 @@ AggregationOperationState::AggregationOperationState(
     std::vector<std::vector<std::unique_ptr<const Scalar>>>::const_iterator
args_it
         = arguments_.begin();
     std::vector<bool>::const_iterator is_distinct_it = is_distinct_.begin();
+    std::vector<HashTableImplType>::const_iterator distinctify_hash_table_impl_types_it
+        = distinctify_hash_table_impl_types.begin();
     for (; agg_func_it != aggregate_functions.end(); ++agg_func_it, ++args_it, ++is_distinct_it)
{
       // Get the Types of this aggregate's arguments so that we can create an
       // AggregationHandle.
@@ -161,10 +166,11 @@ AggregationOperationState::AggregationOperationState(
         // query optimization, if it worths.
         distinctify_hashtables_.emplace_back(
             handles_.back()->createDistinctifyHashTable(
-                hash_table_impl_type,
+                *distinctify_hash_table_impl_types_it,
                 key_types,
                 estimated_num_entries,
                 storage_manager));
+        ++distinctify_hash_table_impl_types_it;
       } else {
         distinctify_hashtables_.emplace_back(nullptr);
       }
@@ -182,6 +188,8 @@ AggregationOperationState* AggregationOperationState::ReconstructFromProto(
   std::vector<const AggregateFunction*> aggregate_functions;
   std::vector<std::vector<std::unique_ptr<const Scalar>>> arguments;
   std::vector<bool> is_distinct;
+  std::vector<HashTableImplType> distinctify_hash_table_impl_types;
+  std::size_t distinctify_hash_table_impl_type_index = 0;
   for (int agg_idx = 0; agg_idx < proto.aggregates_size(); ++agg_idx) {
     const serialization::Aggregate &agg_proto = proto.aggregates(agg_idx);
 
@@ -197,6 +205,13 @@ AggregationOperationState* AggregationOperationState::ReconstructFromProto(
     }
 
     is_distinct.emplace_back(agg_proto.is_distinct());
+
+    if (agg_proto.is_distinct()) {
+      distinctify_hash_table_impl_types.emplace_back(
+          HashTableImplTypeFromProto(
+              proto.distinctify_hash_table_impl_types(distinctify_hash_table_impl_type_index)));
+      ++distinctify_hash_table_impl_type_index;
+    }
   }
 
   std::vector<std::unique_ptr<const Scalar>> group_by_expressions;
@@ -223,6 +238,7 @@ AggregationOperationState* AggregationOperationState::ReconstructFromProto(
                                        predicate.release(),
                                        proto.estimated_num_entries(),
                                        HashTableImplTypeFromProto(proto.hash_table_impl_type()),
+                                       distinctify_hash_table_impl_types,
                                        storage_manager);
 }
 
@@ -234,6 +250,8 @@ bool AggregationOperationState::ProtoIsValid(const serialization::AggregationOpe
     return false;
   }
 
+  std::size_t num_distinctify_hash_tables = proto.distinctify_hash_table_impl_types_size();
+  std::size_t distinctify_hash_table_impl_type_index = 0;
   for (int i = 0; i < proto.aggregates_size(); ++i) {
     if (!AggregateFunctionFactory::ProtoIsValid(proto.aggregates(i).function())) {
       return false;
@@ -251,6 +269,14 @@ bool AggregationOperationState::ProtoIsValid(const serialization::AggregationOpe
         return false;
       }
     }
+
+    if (proto.aggregates(i).is_distinct()) {
+      if (distinctify_hash_table_impl_type_index >= num_distinctify_hash_tables ||
+          !serialization::HashTableImplType_IsValid(
+              proto.distinctify_hash_table_impl_types(distinctify_hash_table_impl_type_index)))
{
+        return false;
+      }
+    }
   }
 
   for (int i = 0; i < proto.group_by_expressions_size(); ++i) {

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6c9108a6/storage/AggregationOperationState.hpp
----------------------------------------------------------------------
diff --git a/storage/AggregationOperationState.hpp b/storage/AggregationOperationState.hpp
index b883ed1..c3a1278 100644
--- a/storage/AggregationOperationState.hpp
+++ b/storage/AggregationOperationState.hpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015-2016 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -93,6 +95,8 @@ class AggregationOperationState {
    *        in the input relation.
    * @param hash_table_impl_type The HashTable implementation to use for
    *        GROUP BY. Ignored if group_by is empty.
+   * @param distinctify_hash_table_impl_type The HashTable implementation to use
+   *        for the distinctify phase of each DISTINCT aggregation.
    * @param storage_manager The StorageManager to use for allocating hash
    *        tables. Single aggregation state (when GROUP BY list is not
    *        specified) is not allocated using memory from storage manager.
@@ -105,6 +109,7 @@ class AggregationOperationState {
                             const Predicate *predicate,
                             const std::size_t estimated_num_entries,
                             const HashTableImplType hash_table_impl_type,
+                            const std::vector<HashTableImplType> &distinctify_hash_table_impl_types,
                             StorageManager *storage_manager);
 
   ~AggregationOperationState() {}

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6c9108a6/storage/AggregationOperationState.proto
----------------------------------------------------------------------
diff --git a/storage/AggregationOperationState.proto b/storage/AggregationOperationState.proto
index 031f782..bf78e3a 100644
--- a/storage/AggregationOperationState.proto
+++ b/storage/AggregationOperationState.proto
@@ -1,5 +1,7 @@
 //   Copyright 2011-2015 Quickstep Technologies LLC.
 //   Copyright 2015-2016 Pivotal Software, Inc.
+//   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+//     University of Wisconsin—Madison.
 //
 //   Licensed under the Apache License, Version 2.0 (the "License");
 //   you may not use this file except in compliance with the License.
@@ -37,4 +39,7 @@ message AggregationOperationState {
   // NOTE(chasseur): 'hash_table_impl_type' is marked optional, but it is
   // needed if 'group_by_expressions' is non-empty, and ignored otherwise.
   optional HashTableImplType hash_table_impl_type = 6;
+
+  // Each DISTINCT aggregation has its distinctify hash table impl type.
+  repeated HashTableImplType distinctify_hash_table_impl_types = 7;
 }


Mime
View raw message