You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by zu...@apache.org on 2017/02/03 07:01:35 UTC
[1/2] incubator-quickstep git commit: Simplified the SelectOperator
w/ partitions. [Forced Update!]
Repository: incubator-quickstep
Updated Branches:
refs/heads/reduce-group-by-attrs 47e03182b -> 022787a1f (forced update)
Simplified the SelectOperator w/ partitions.
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/929e5f1d
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/929e5f1d
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/929e5f1d
Branch: refs/heads/reduce-group-by-attrs
Commit: 929e5f1dd178538725eac1644712828e9dc5843d
Parents: 7727e77
Author: Zuyu Zhang <zu...@apache.org>
Authored: Mon Jan 30 00:35:12 2017 -0800
Committer: Zuyu Zhang <zu...@apache.org>
Committed: Thu Feb 2 19:13:30 2017 -0800
----------------------------------------------------------------------
query_optimizer/ExecutionGenerator.cpp | 30 +++++++---
relational_operators/SelectOperator.cpp | 84 +++++++++++-----------------
relational_operators/SelectOperator.hpp | 67 ++++++++++------------
3 files changed, 84 insertions(+), 97 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/929e5f1d/query_optimizer/ExecutionGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.cpp b/query_optimizer/ExecutionGenerator.cpp
index ce1452e..b73de39 100644
--- a/query_optimizer/ExecutionGenerator.cpp
+++ b/query_optimizer/ExecutionGenerator.cpp
@@ -551,6 +551,13 @@ void ExecutionGenerator::convertSelection(
const CatalogRelationInfo *input_relation_info =
findRelationInfoOutputByPhysical(physical_selection->input());
DCHECK(input_relation_info != nullptr);
+ const CatalogRelation &input_relation = *input_relation_info->relation;
+ const PartitionScheme *input_partition_scheme = input_relation.getPartitionScheme();
+
+ const std::size_t num_partitions =
+ input_partition_scheme
+ ? input_partition_scheme->getPartitionSchemeHeader().getNumPartitions()
+ : 1u;
// Use the "simple" form of the selection operator (a pure projection that
// doesn't require any expression evaluation or intermediate copies) if
@@ -559,19 +566,21 @@ void ExecutionGenerator::convertSelection(
SelectOperator *op =
convertSimpleProjection(project_expressions_group_index, &attributes)
? new SelectOperator(query_handle_->query_id(),
- *input_relation_info->relation,
+ input_relation,
*output_relation,
insert_destination_index,
execution_predicate_index,
move(attributes),
- input_relation_info->isStoredRelation())
+ input_relation_info->isStoredRelation(),
+ num_partitions)
: new SelectOperator(query_handle_->query_id(),
- *input_relation_info->relation,
+ input_relation,
*output_relation,
insert_destination_index,
execution_predicate_index,
project_expressions_group_index,
- input_relation_info->isStoredRelation());
+ input_relation_info->isStoredRelation(),
+ num_partitions);
const QueryPlan::DAGNodeIndex select_index =
execution_plan_->addRelationalOperator(op);
@@ -1310,7 +1319,13 @@ void ExecutionGenerator::convertInsertSelection(
const CatalogRelationInfo *selection_relation_info =
findRelationInfoOutputByPhysical(physical_plan->selection());
- const CatalogRelation *selection_relation = selection_relation_info->relation;
+ const CatalogRelation &selection_relation = *selection_relation_info->relation;
+ const PartitionScheme *selection_partition_scheme = selection_relation.getPartitionScheme();
+
+ const std::size_t num_partitions =
+ selection_partition_scheme
+ ? selection_partition_scheme->getPartitionSchemeHeader().getNumPartitions()
+ : 1u;
// Prepare the attributes, which are output columns of the selection relation.
std::vector<attribute_id> attributes;
@@ -1331,12 +1346,13 @@ void ExecutionGenerator::convertInsertSelection(
// physical plan by modifying class Physical.
SelectOperator *insert_selection_op =
new SelectOperator(query_handle_->query_id(),
- *selection_relation,
+ selection_relation,
destination_relation,
insert_destination_index,
QueryContext::kInvalidPredicateId,
move(attributes),
- selection_relation_info->isStoredRelation());
+ selection_relation_info->isStoredRelation(),
+ num_partitions);
const QueryPlan::DAGNodeIndex insert_selection_index =
execution_plan_->addRelationalOperator(insert_selection_op);
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/929e5f1d/relational_operators/SelectOperator.cpp
----------------------------------------------------------------------
diff --git a/relational_operators/SelectOperator.cpp b/relational_operators/SelectOperator.cpp
index 5419cf8..b63f0be 100644
--- a/relational_operators/SelectOperator.cpp
+++ b/relational_operators/SelectOperator.cpp
@@ -66,64 +66,40 @@ bool SelectOperator::getAllWorkOrders(
return true;
}
- if (input_relation_.hasPartitionScheme()) {
- for (std::size_t part_id = 0; part_id < num_partitions_; ++part_id) {
- for (const block_id input_block_id : input_relation_block_ids_in_partition_[part_id]) {
- numa_node_id numa_node = 0;
+ for (std::size_t part_id = 0; part_id < num_partitions_; ++part_id) {
+ for (const block_id input_block_id : input_relation_block_ids_[part_id]) {
+ numa_node_id numa_node = 0;
#ifdef QUICKSTEP_HAVE_LIBNUMA
- if (input_relation_.hasNUMAPlacementScheme()) {
- numa_node = placement_scheme_->getNUMANodeForBlock(input_block_id);
- }
-#endif // QUICKSTEP_HAVE_LIBNUMA
- container->addNormalWorkOrder(
- new SelectWorkOrder(query_id_, input_relation_, input_block_id, predicate, simple_projection_,
- simple_selection_, selection, output_destination, storage_manager,
- CreateLIPFilterAdaptiveProberHelper(lip_deployment_index_, query_context), numa_node),
- op_index_);
+ if (input_relation_.hasNUMAPlacementScheme()) {
+ numa_node = placement_scheme_->getNUMANodeForBlock(input_block_id);
}
- }
- } else {
- for (const block_id input_block_id : input_relation_block_ids_) {
+#endif // QUICKSTEP_HAVE_LIBNUMA
container->addNormalWorkOrder(
new SelectWorkOrder(query_id_, input_relation_, input_block_id, predicate, simple_projection_,
simple_selection_, selection, output_destination, storage_manager,
- CreateLIPFilterAdaptiveProberHelper(lip_deployment_index_, query_context)),
+ CreateLIPFilterAdaptiveProberHelper(lip_deployment_index_, query_context), numa_node),
op_index_);
}
}
started_ = true;
return true;
} else {
- if (input_relation_.hasPartitionScheme()) {
- for (std::size_t part_id = 0; part_id < num_partitions_; ++part_id) {
- while (num_workorders_generated_in_partition_[part_id] <
- input_relation_block_ids_in_partition_[part_id].size()) {
- const block_id block_in_partition
- = input_relation_block_ids_in_partition_[part_id][num_workorders_generated_in_partition_[part_id]];
-
- numa_node_id numa_node = 0;
+ for (std::size_t part_id = 0; part_id < num_partitions_; ++part_id) {
+ while (num_workorders_generated_[part_id] < input_relation_block_ids_[part_id].size()) {
+ const block_id block = input_relation_block_ids_[part_id][num_workorders_generated_[part_id]];
+
+ numa_node_id numa_node = 0;
#ifdef QUICKSTEP_HAVE_LIBNUMA
- if (input_relation_.hasNUMAPlacementScheme()) {
- numa_node = placement_scheme_->getNUMANodeForBlock(block_in_partition);
- }
-#endif // QUICKSTEP_HAVE_LIBNUMA
- container->addNormalWorkOrder(
- new SelectWorkOrder(query_id_, input_relation_, block_in_partition, predicate, simple_projection_,
- simple_selection_, selection, output_destination, storage_manager,
- CreateLIPFilterAdaptiveProberHelper(lip_deployment_index_, query_context), numa_node),
- op_index_);
- ++num_workorders_generated_in_partition_[part_id];
+ if (input_relation_.hasNUMAPlacementScheme()) {
+ numa_node = placement_scheme_->getNUMANodeForBlock(block);
}
- }
- } else {
- while (num_workorders_generated_ < input_relation_block_ids_.size()) {
+#endif // QUICKSTEP_HAVE_LIBNUMA
container->addNormalWorkOrder(
- new SelectWorkOrder(query_id_, input_relation_, input_relation_block_ids_[num_workorders_generated_],
- predicate, simple_projection_, simple_selection_, selection, output_destination,
- storage_manager,
- CreateLIPFilterAdaptiveProberHelper(lip_deployment_index_, query_context)),
+ new SelectWorkOrder(query_id_, input_relation_, block, predicate, simple_projection_,
+ simple_selection_, selection, output_destination, storage_manager,
+ CreateLIPFilterAdaptiveProberHelper(lip_deployment_index_, query_context), numa_node),
op_index_);
- ++num_workorders_generated_;
+ ++num_workorders_generated_[part_id];
}
}
return done_feeding_input_relation_;
@@ -132,19 +108,25 @@ bool SelectOperator::getAllWorkOrders(
bool SelectOperator::getAllWorkOrderProtos(WorkOrderProtosContainer *container) {
if (input_relation_is_stored_) {
- if (!started_) {
- for (const block_id input_block_id : input_relation_block_ids_) {
+ if (started_) {
+ return true;
+ }
+
+ for (std::size_t part_id = 0; part_id < num_partitions_; ++part_id) {
+ for (const block_id input_block_id : input_relation_block_ids_[part_id]) {
container->addWorkOrderProto(createWorkOrderProto(input_block_id), op_index_);
}
- started_ = true;
}
+ started_ = true;
return true;
} else {
- while (num_workorders_generated_ < input_relation_block_ids_.size()) {
- container->addWorkOrderProto(
- createWorkOrderProto(input_relation_block_ids_[num_workorders_generated_]),
- op_index_);
- ++num_workorders_generated_;
+ for (std::size_t part_id = 0; part_id < num_partitions_; ++part_id) {
+ while (num_workorders_generated_[part_id] < input_relation_block_ids_[part_id].size()) {
+ container->addWorkOrderProto(
+ createWorkOrderProto(input_relation_block_ids_[part_id][num_workorders_generated_[part_id]]),
+ op_index_);
+ ++num_workorders_generated_[part_id];
+ }
}
return done_feeding_input_relation_;
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/929e5f1d/relational_operators/SelectOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/SelectOperator.hpp b/relational_operators/SelectOperator.hpp
index 79ab37f..b9a4d49 100644
--- a/relational_operators/SelectOperator.hpp
+++ b/relational_operators/SelectOperator.hpp
@@ -85,6 +85,8 @@ class SelectOperator : public RelationalOperator {
* @param input_relation_is_stored If input_relation is a stored relation and
* is fully available to the operator before it can start generating
* workorders.
+ * @param num_partitions The number of partitions in 'input_relation'.
+ * If no partitions, it is one.
**/
SelectOperator(
const std::size_t query_id,
@@ -93,36 +95,33 @@ class SelectOperator : public RelationalOperator {
const QueryContext::insert_destination_id output_destination_index,
const QueryContext::predicate_id predicate_index,
const QueryContext::scalar_group_id selection_index,
- const bool input_relation_is_stored)
+ const bool input_relation_is_stored,
+ const std::size_t num_partitions)
: RelationalOperator(query_id),
input_relation_(input_relation),
output_relation_(output_relation),
output_destination_index_(output_destination_index),
predicate_index_(predicate_index),
selection_index_(selection_index),
- num_workorders_generated_(0),
+ num_partitions_(num_partitions),
+ input_relation_block_ids_(num_partitions),
+ num_workorders_generated_(num_partitions),
simple_projection_(false),
input_relation_is_stored_(input_relation_is_stored),
started_(false) {
#ifdef QUICKSTEP_HAVE_LIBNUMA
placement_scheme_ = input_relation.getNUMAPlacementSchemePtr();
#endif
- if (input_relation.hasPartitionScheme()) {
- const PartitionScheme &part_scheme = *input_relation.getPartitionScheme();
- num_partitions_ = part_scheme.getPartitionSchemeHeader().getNumPartitions();
+ if (input_relation_is_stored) {
+ if (input_relation.hasPartitionScheme()) {
+ const PartitionScheme &part_scheme = *input_relation.getPartitionScheme();
- num_workorders_generated_in_partition_.resize(num_partitions_);
-
- if (input_relation_is_stored) {
for (std::size_t part_id = 0; part_id < num_partitions_; ++part_id) {
- input_relation_block_ids_in_partition_.push_back(
- part_scheme.getBlocksInPartition(part_id));
+ input_relation_block_ids_[part_id] = part_scheme.getBlocksInPartition(part_id);
}
} else {
- input_relation_block_ids_in_partition_.resize(num_partitions_);
+ input_relation_block_ids_[0] = input_relation.getBlocksSnapshot();
}
- } else if (input_relation_is_stored) {
- input_relation_block_ids_ = input_relation.getBlocksSnapshot();
}
}
@@ -144,6 +143,8 @@ class SelectOperator : public RelationalOperator {
* @param input_relation_is_stored If input_relation is a stored relation and
* is fully available to the operator before it can start generating
* workorders.
+ * @param num_partitions The number of partitions in 'input_relation'.
+ * If no partitions, it is one.
**/
SelectOperator(
const std::size_t query_id,
@@ -152,7 +153,8 @@ class SelectOperator : public RelationalOperator {
const QueryContext::insert_destination_id output_destination_index,
const QueryContext::predicate_id predicate_index,
std::vector<attribute_id> &&selection,
- const bool input_relation_is_stored)
+ const bool input_relation_is_stored,
+ const std::size_t num_partitions)
: RelationalOperator(query_id),
input_relation_(input_relation),
output_relation_(output_relation),
@@ -160,29 +162,25 @@ class SelectOperator : public RelationalOperator {
predicate_index_(predicate_index),
selection_index_(QueryContext::kInvalidScalarGroupId),
simple_selection_(std::move(selection)),
- num_workorders_generated_(0),
+ num_partitions_(num_partitions),
+ input_relation_block_ids_(num_partitions),
+ num_workorders_generated_(num_partitions),
simple_projection_(true),
input_relation_is_stored_(input_relation_is_stored),
started_(false) {
#ifdef QUICKSTEP_HAVE_LIBNUMA
placement_scheme_ = input_relation.getNUMAPlacementSchemePtr();
#endif
- if (input_relation.hasPartitionScheme()) {
- const PartitionScheme &part_scheme = *input_relation.getPartitionScheme();
- num_partitions_ = part_scheme.getPartitionSchemeHeader().getNumPartitions();
-
- num_workorders_generated_in_partition_.resize(num_partitions_);
+ if (input_relation_is_stored) {
+ if (input_relation.hasPartitionScheme()) {
+ const PartitionScheme &part_scheme = *input_relation.getPartitionScheme();
- if (input_relation_is_stored) {
for (std::size_t part_id = 0; part_id < num_partitions_; ++part_id) {
- input_relation_block_ids_in_partition_.push_back(
- part_scheme.getBlocksInPartition(part_id));
+ input_relation_block_ids_[part_id] = part_scheme.getBlocksInPartition(part_id);
}
} else {
- input_relation_block_ids_in_partition_.resize(num_partitions_);
+ input_relation_block_ids_[0] = input_relation.getBlocksSnapshot();
}
- } else if (input_relation_is_stored) {
- input_relation_block_ids_ = input_relation.getBlocksSnapshot();
}
}
@@ -206,11 +204,7 @@ class SelectOperator : public RelationalOperator {
void feedInputBlock(const block_id input_block_id, const relation_id input_relation_id,
const partition_id part_id) override {
- if (input_relation_.hasPartitionScheme()) {
- input_relation_block_ids_in_partition_[part_id].push_back(input_block_id);
- } else {
- input_relation_block_ids_.push_back(input_block_id);
- }
+ input_relation_block_ids_[part_id].push_back(input_block_id);
}
QueryContext::insert_destination_id getInsertDestinationID() const override {
@@ -237,17 +231,12 @@ class SelectOperator : public RelationalOperator {
const QueryContext::scalar_group_id selection_index_;
const std::vector<attribute_id> simple_selection_;
- std::vector<block_id> input_relation_block_ids_;
- // A single workorder is generated for each block of input relation.
- std::vector<block_id>::size_type num_workorders_generated_;
-
- // Used for the partition case only.
+ const std::size_t num_partitions_;
// A vector of vectors V where V[i] indicates the list of block IDs of the
// input relation that belong to the partition i.
- std::vector<std::vector<block_id>> input_relation_block_ids_in_partition_;
+ std::vector<std::vector<block_id>> input_relation_block_ids_;
// A single workorder is generated for each block in each partition of input relation.
- std::vector<std::size_t> num_workorders_generated_in_partition_;
- std::size_t num_partitions_;
+ std::vector<std::size_t> num_workorders_generated_;
const bool simple_projection_;
const bool input_relation_is_stored_;
[2/2] incubator-quickstep git commit: Reduce the number of group-by
attributes by pulling tables up aggregations
Posted by zu...@apache.org.
Reduce the number of group-by attributes by pulling tables up aggregations
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/022787a1
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/022787a1
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/022787a1
Branch: refs/heads/reduce-group-by-attrs
Commit: 022787a1fd41b90bfe4ad9b01040537ca3edf966
Parents: 929e5f1
Author: Jianqiao Zhu <ji...@cs.wisc.edu>
Authored: Sun Jan 29 18:36:14 2017 -0600
Committer: Zuyu Zhang <zu...@apache.org>
Committed: Thu Feb 2 23:01:19 2017 -0800
----------------------------------------------------------------------
query_optimizer/CMakeLists.txt | 1 +
query_optimizer/Optimizer.cpp | 3 +-
query_optimizer/Optimizer.hpp | 2 -
query_optimizer/PhysicalGenerator.cpp | 3 +
query_optimizer/PhysicalGenerator.hpp | 11 +-
query_optimizer/rules/CMakeLists.txt | 23 ++
.../rules/ReduceGroupByAttributes.cpp | 217 +++++++++++++++++++
.../rules/ReduceGroupByAttributes.hpp | 143 ++++++++++++
query_optimizer/tests/OptimizerTest.cpp | 2 +-
.../tests/OptimizerTextTestRunner.cpp | 7 +-
.../tests/OptimizerTextTestRunner.hpp | 3 +-
third_party/src/iwyu/iwyu_helper.py | 14 +-
12 files changed, 412 insertions(+), 17 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/CMakeLists.txt b/query_optimizer/CMakeLists.txt
index 7f90e11..bc9a52f 100644
--- a/query_optimizer/CMakeLists.txt
+++ b/query_optimizer/CMakeLists.txt
@@ -212,6 +212,7 @@ target_link_libraries(quickstep_queryoptimizer_PhysicalGenerator
quickstep_queryoptimizer_rules_InjectJoinFilters
quickstep_queryoptimizer_rules_PruneColumns
quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
+ quickstep_queryoptimizer_rules_ReduceGroupByAttributes
quickstep_queryoptimizer_rules_ReorderColumns
quickstep_queryoptimizer_rules_StarSchemaHashJoinOrderOptimization
quickstep_queryoptimizer_rules_SwapProbeBuild
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/Optimizer.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/Optimizer.cpp b/query_optimizer/Optimizer.cpp
index b14c938..1b91574 100644
--- a/query_optimizer/Optimizer.cpp
+++ b/query_optimizer/Optimizer.cpp
@@ -30,10 +30,11 @@ void Optimizer::generateQueryHandle(const ParseStatement &parse_statement,
OptimizerContext *optimizer_context,
QueryHandle *query_handle) {
LogicalGenerator logical_generator(optimizer_context);
+ PhysicalGenerator physical_generator(optimizer_context);
ExecutionGenerator execution_generator(catalog_database, query_handle);
execution_generator.generatePlan(
- physical_generator_.generatePlan(
+ physical_generator.generatePlan(
logical_generator.generatePlan(*catalog_database, parse_statement)));
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/Optimizer.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/Optimizer.hpp b/query_optimizer/Optimizer.hpp
index 36f956a..227dd04 100644
--- a/query_optimizer/Optimizer.hpp
+++ b/query_optimizer/Optimizer.hpp
@@ -70,8 +70,6 @@ class Optimizer {
QueryHandle *query_handle);
private:
- PhysicalGenerator physical_generator_;
-
DISALLOW_COPY_AND_ASSIGN(Optimizer);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/PhysicalGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.cpp b/query_optimizer/PhysicalGenerator.cpp
index 5dc0ffb..1b68f49 100644
--- a/query_optimizer/PhysicalGenerator.cpp
+++ b/query_optimizer/PhysicalGenerator.cpp
@@ -30,6 +30,7 @@
#include "query_optimizer/rules/InjectJoinFilters.hpp"
#include "query_optimizer/rules/PruneColumns.hpp"
#include "query_optimizer/rules/PushDownLowCostDisjunctivePredicate.hpp"
+#include "query_optimizer/rules/ReduceGroupByAttributes.hpp"
#include "query_optimizer/rules/ReorderColumns.hpp"
#include "query_optimizer/rules/StarSchemaHashJoinOrderOptimization.hpp"
#include "query_optimizer/rules/SwapProbeBuild.hpp"
@@ -127,6 +128,8 @@ P::PhysicalPtr PhysicalGenerator::optimizePlan() {
// general FusePhysical optimization) in the future.
rules.emplace_back(new PushDownLowCostDisjunctivePredicate());
+ rules.emplace_back(new ReduceGroupByAttributes(optimizer_context_));
+
if (FLAGS_reorder_hash_joins) {
rules.emplace_back(new StarSchemaHashJoinOrderOptimization());
rules.emplace_back(new PruneColumns());
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/PhysicalGenerator.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/PhysicalGenerator.hpp b/query_optimizer/PhysicalGenerator.hpp
index 886a173..42fea86 100644
--- a/query_optimizer/PhysicalGenerator.hpp
+++ b/query_optimizer/PhysicalGenerator.hpp
@@ -33,6 +33,8 @@
namespace quickstep {
namespace optimizer {
+class OptimizerContext;
+
/** \addtogroup QueryOptimizer
* @{
*/
@@ -43,9 +45,12 @@ namespace optimizer {
class PhysicalGenerator : public LogicalToPhysicalMapper {
public:
/**
- * @brief Constructor
+ * @brief Constructor.
+ *
+ * @param optimizer_context The optimizer context.
*/
- PhysicalGenerator() {
+ explicit PhysicalGenerator(OptimizerContext *optimizer_context)
+ : optimizer_context_(optimizer_context) {
createStrategies();
}
@@ -125,6 +130,8 @@ class PhysicalGenerator : public LogicalToPhysicalMapper {
*/
std::unordered_map<logical::LogicalPtr, physical::PhysicalPtr> logical_to_physical_map_;
+ OptimizerContext *optimizer_context_;
+
/**
* @brief The complete physical plan.
*/
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/rules/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/CMakeLists.txt b/query_optimizer/rules/CMakeLists.txt
index 223c78c..029d816 100644
--- a/query_optimizer/rules/CMakeLists.txt
+++ b/query_optimizer/rules/CMakeLists.txt
@@ -29,6 +29,9 @@ add_library(quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
PushDownLowCostDisjunctivePredicate.cpp
PushDownLowCostDisjunctivePredicate.hpp)
add_library(quickstep_queryoptimizer_rules_PushDownSemiAntiJoin PushDownSemiAntiJoin.cpp PushDownSemiAntiJoin.hpp)
+add_library(quickstep_queryoptimizer_rules_ReduceGroupByAttributes
+ ReduceGroupByAttributes.cpp
+ ReduceGroupByAttributes.hpp)
add_library(quickstep_queryoptimizer_rules_ReorderColumns ReorderColumns.cpp ReorderColumns.hpp)
add_library(quickstep_queryoptimizer_rules_Rule ../../empty_src.cpp Rule.hpp)
add_library(quickstep_queryoptimizer_rules_RuleHelper RuleHelper.cpp RuleHelper.hpp)
@@ -143,6 +146,25 @@ target_link_libraries(quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
quickstep_queryoptimizer_logical_PatternMatcher
quickstep_queryoptimizer_rules_TopDownRule
quickstep_utility_Macros)
+target_link_libraries(quickstep_queryoptimizer_rules_ReduceGroupByAttributes
+ ${GFLAGS_LIB_NAME}
+ quickstep_catalog_CatalogRelation
+ quickstep_queryoptimizer_OptimizerContext
+ quickstep_queryoptimizer_costmodel_StarSchemaSimpleCostModel
+ quickstep_queryoptimizer_expressions_AttributeReference
+ quickstep_queryoptimizer_expressions_ExprId
+ quickstep_queryoptimizer_expressions_ExpressionUtil
+ quickstep_queryoptimizer_expressions_NamedExpression
+ quickstep_queryoptimizer_physical_Aggregate
+ quickstep_queryoptimizer_physical_HashJoin
+ quickstep_queryoptimizer_physical_PatternMatcher
+ quickstep_queryoptimizer_physical_Physical
+ quickstep_queryoptimizer_physical_PhysicalType
+ quickstep_queryoptimizer_physical_TableReference
+ quickstep_queryoptimizer_physical_TopLevelPlan
+ quickstep_queryoptimizer_rules_PruneColumns
+ quickstep_queryoptimizer_rules_Rule
+ quickstep_utility_Macros)
target_link_libraries(quickstep_queryoptimizer_rules_ReorderColumns
quickstep_queryoptimizer_expressions_AttributeReference
quickstep_queryoptimizer_expressions_ExprId
@@ -272,6 +294,7 @@ target_link_libraries(quickstep_queryoptimizer_rules
quickstep_queryoptimizer_rules_PushDownFilter
quickstep_queryoptimizer_rules_PushDownLowCostDisjunctivePredicate
quickstep_queryoptimizer_rules_PushDownSemiAntiJoin
+ quickstep_queryoptimizer_rules_ReduceGroupByAttributes
quickstep_queryoptimizer_rules_ReorderColumns
quickstep_queryoptimizer_rules_Rule
quickstep_queryoptimizer_rules_RuleHelper
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/rules/ReduceGroupByAttributes.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/ReduceGroupByAttributes.cpp b/query_optimizer/rules/ReduceGroupByAttributes.cpp
new file mode 100644
index 0000000..dcdd27a
--- /dev/null
+++ b/query_optimizer/rules/ReduceGroupByAttributes.cpp
@@ -0,0 +1,217 @@
+/**
+ * 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/ReduceGroupByAttributes.hpp"
+
+#include <algorithm>
+#include <map>
+#include <vector>
+#include <unordered_set>
+#include <utility>
+
+#include "catalog/CatalogRelation.hpp"
+#include "query_optimizer/OptimizerContext.hpp"
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/expressions/ExpressionUtil.hpp"
+#include "query_optimizer/expressions/NamedExpression.hpp"
+#include "query_optimizer/physical/Aggregate.hpp"
+#include "query_optimizer/physical/HashJoin.hpp"
+#include "query_optimizer/physical/PatternMatcher.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/PhysicalType.hpp"
+#include "query_optimizer/physical/TableReference.hpp"
+#include "query_optimizer/physical/TopLevelPlan.hpp"
+#include "query_optimizer/rules/PruneColumns.hpp"
+
+#include "gflags/gflags.h"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace optimizer {
+
+DEFINE_uint64(reduce_group_by_attributes_threshold, 3u,
+ "The threshold for a stored relation's number of attributes in a "
+ "group-by clause for the ReduceGroupByAttributes optimization "
+ "rule to pull the stored relation up the aggregation");
+
+namespace E = ::quickstep::optimizer::expressions;
+namespace P = ::quickstep::optimizer::physical;
+
+P::PhysicalPtr ReduceGroupByAttributes::apply(const P::PhysicalPtr &input) {
+ DCHECK(input->getPhysicalType() == P::PhysicalType::kTopLevelPlan);
+ cost_model_.reset(new cost::StarSchemaSimpleCostModel(
+ std::static_pointer_cast<const P::TopLevelPlan>(input)->shared_subplans()));
+
+ P::PhysicalPtr output = applyInternal(input);
+ if (output != input) {
+ output = PruneColumns().apply(output);
+ }
+ return output;
+}
+
+P::PhysicalPtr ReduceGroupByAttributes::applyInternal(const P::PhysicalPtr &input) {
+ std::vector<P::PhysicalPtr> new_children;
+ for (const P::PhysicalPtr &child : input->children()) {
+ new_children.push_back(applyInternal(child));
+ }
+
+ if (new_children != input->children()) {
+ return applyToNode(input->copyWithNewChildren(new_children));
+ } else {
+ return applyToNode(input);
+ }
+}
+
+P::PhysicalPtr ReduceGroupByAttributes::applyToNode(const P::PhysicalPtr &input) {
+ P::TableReferencePtr table_reference;
+ if (P::SomeTableReference::MatchesWithConditionalCast(input, &table_reference)) {
+ // Collect the attributes-to-TableReference mapping info.
+ for (const auto &attr : table_reference->attribute_list()) {
+ source_.emplace(attr->id(), std::make_pair(table_reference, attr));
+ }
+ return input;
+ }
+
+ P::AggregatePtr aggregate;
+ if (!P::SomeAggregate::MatchesWithConditionalCast(input, &aggregate) ||
+ aggregate->grouping_expressions().size() <= 1u) {
+ return input;
+ }
+
+ // Divide the group-by attributes into groups based on their source table.
+ std::map<P::TableReferencePtr, std::vector<E::AttributeReferencePtr>> table_attributes;
+ for (const auto &expr : aggregate->grouping_expressions()) {
+ const auto source_it = source_.find(expr->id());
+ if (source_it != source_.end()) {
+ table_attributes[source_it->second.first].emplace_back(source_it->second.second);
+ }
+ }
+
+ std::unordered_set<E::ExprId> erased_grouping_attr_ids;
+ std::vector<std::pair<P::TableReferencePtr, E::AttributeReferencePtr>> hoisted_tables;
+
+ // For each group (i.e. each source table), if it is profitable then we pull
+ // the table up the aggregation.
+ for (const auto &pair : table_attributes) {
+ const P::TableReferencePtr table = pair.first;
+ const std::vector<E::AttributeReferencePtr> &attributes = pair.second;
+ // TODO(jianqiao): find a cost-based metic instead of hard-coding the threshold
+ // number of group-by attributes.
+ if (attributes.size() <= FLAGS_reduce_group_by_attributes_threshold) {
+ continue;
+ }
+
+ std::vector<AttributeInfo> attr_infos;
+ for (const auto &attr : attributes) {
+ attr_infos.emplace_back(attr,
+ cost_model_->impliesUniqueAttributes(table, {attr}),
+ !attr->getValueType().isVariableLength(),
+ attr->getValueType().maximumByteLength());
+ }
+
+ std::vector<const AttributeInfo *> attr_info_refs;
+ for (const auto &info : attr_infos) {
+ attr_info_refs.emplace_back(&info);
+ }
+ std::sort(attr_info_refs.begin(),
+ attr_info_refs.end(),
+ AttributeInfo::IsBetterThan);
+
+ const AttributeInfo &best_candidate = *attr_info_refs.front();
+ if (!best_candidate.is_unique) {
+ // Cannot find a key attribute. Give up pulling this table up.
+ continue;
+ }
+
+ const E::AttributeReferencePtr key_attribute = best_candidate.attribute;
+ hoisted_tables.emplace_back(table, key_attribute);
+
+ for (const auto &attr : attributes) {
+ if (attr->id() != key_attribute->id()) {
+ erased_grouping_attr_ids.emplace(attr->id());
+ }
+ }
+ }
+
+ if (erased_grouping_attr_ids.empty()) {
+ return input;
+ }
+
+ // Reconstuct the Aggregate node with reduced group-by attributes and then
+ // construct HashJoin nodes on top of the Aggregate.
+ std::vector<E::NamedExpressionPtr> reduced_grouping_expressions;
+ for (const auto &expr : aggregate->grouping_expressions()) {
+ if (erased_grouping_attr_ids.find(expr->id()) == erased_grouping_attr_ids.end()) {
+ reduced_grouping_expressions.emplace_back(expr);
+ }
+ }
+
+ const P::AggregatePtr new_aggregate =
+ P::Aggregate::Create(aggregate->input(),
+ reduced_grouping_expressions,
+ aggregate->aggregate_expressions(),
+ aggregate->filter_predicate());
+
+ P::PhysicalPtr output = new_aggregate;
+ std::vector<E::NamedExpressionPtr> project_expressions =
+ E::ToNamedExpressions(output->getOutputAttributes());
+ for (const auto &pair : hoisted_tables) {
+ const P::TableReferencePtr &source_table = pair.first;
+ const E::AttributeReferencePtr &probe_attribute = pair.second;
+
+ E::AttributeReferencePtr build_attribute;
+ std::vector<E::AttributeReferencePtr> new_attribute_list;
+ for (const auto &attr : source_table->attribute_list()) {
+ if (attr->id() == probe_attribute->id()) {
+ build_attribute =
+ E::AttributeReference::Create(optimizer_context_->nextExprId(),
+ attr->attribute_name(),
+ attr->attribute_alias(),
+ attr->relation_name(),
+ attr->getValueType(),
+ E::AttributeReferenceScope::kLocal);
+ new_attribute_list.emplace_back(build_attribute);
+ } else {
+ new_attribute_list.emplace_back(attr);
+ project_expressions.emplace_back(attr);
+ }
+ }
+
+ DCHECK(build_attribute != nullptr);
+ const P::TableReferencePtr build_side_table =
+ P::TableReference::Create(source_table->relation(),
+ source_table->relation()->getName(),
+ new_attribute_list);
+ output = P::HashJoin::Create(output,
+ build_side_table,
+ {probe_attribute},
+ {build_attribute},
+ nullptr,
+ project_expressions,
+ P::HashJoin::JoinType::kInnerJoin);
+ }
+
+ return output;
+}
+
+} // namespace optimizer
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/rules/ReduceGroupByAttributes.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/rules/ReduceGroupByAttributes.hpp b/query_optimizer/rules/ReduceGroupByAttributes.hpp
new file mode 100644
index 0000000..5a1f295
--- /dev/null
+++ b/query_optimizer/rules/ReduceGroupByAttributes.hpp
@@ -0,0 +1,143 @@
+/**
+ * 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_REDUCE_GROUP_BY_ATTRIBUTES_HPP_
+#define QUICKSTEP_QUERY_OPTIMIZER_RULES_REDUCE_GROUP_BY_ATTRIBUTES_HPP_
+
+#include <cstddef>
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <utility>
+
+#include "query_optimizer/cost_model/StarSchemaSimpleCostModel.hpp"
+#include "query_optimizer/expressions/AttributeReference.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
+#include "query_optimizer/physical/Physical.hpp"
+#include "query_optimizer/physical/TableReference.hpp"
+#include "query_optimizer/rules/Rule.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+namespace optimizer {
+
+class OptimizerContext;
+
+/**
+ * @brief Rule that applies to a physical plan to reduce the number of group-by
+ * attributes for Aggregate nodes (to improve performance) by pulling
+ * joins up the aggregations.
+ *
+ * For example, let R be a relation with PRIMARY KEY x and attributes y, z. Let
+ * S be a relation with FOREIGN KEY u refering to R(x) and attribute v. Then the
+ * optimization rule will transform the physical plan:
+ * Aggregate(
+ * [input relation]: HashJoin(
+ * [probe relation]: S
+ * [build relation]: R
+ * [join expression]: S.u = R.x
+ * [project attributes]: v, x, y, z
+ * )
+ * [aggregate expression]: SUM(v) AS sum_v
+ * [group-by attributes]: x, y, z
+ * )
+ *
+ * into:
+ * HashJoin(
+ * [probe relation]: Aggregate(
+ * [input relation]: S
+ * [aggregate expression]: SUM(v) AS sum_v
+ * [group-by attribute]: u
+ * ) AS T
+ * [build relation]: R
+ * [join expression]: T.u = R.x
+ * [project attributes]: sum_v, x, y, z
+ * )
+ */
+class ReduceGroupByAttributes : public Rule<physical::Physical> {
+ public:
+ /**
+ * @brief Constructor.
+ *
+ * @param optimizer_context The optimizer context.
+ */
+ explicit ReduceGroupByAttributes(OptimizerContext *optimizer_context)
+ : optimizer_context_(optimizer_context) {}
+
+ ~ReduceGroupByAttributes() override {}
+
+ std::string getName() const override {
+ return "ReduceGroupByAttributes";
+ }
+
+ physical::PhysicalPtr apply(const physical::PhysicalPtr &input) override;
+
+ private:
+ struct AttributeInfo {
+ AttributeInfo(const expressions::AttributeReferencePtr &attribute_in,
+ const bool is_unique_in,
+ const bool is_fixed_length_in,
+ const std::size_t maximum_size_in)
+ : attribute(attribute_in),
+ is_unique(is_unique_in),
+ is_fixed_length(is_fixed_length_in),
+ maximum_size(maximum_size_in) {}
+
+ // In the situation that there are multiple attributes that can serve as the
+ // group-by key, we define an ordering based on aggregation performance (e.g.
+ // it is faster to do aggregation with a fix-length attribute as the group-by
+ // key than with a variable-length attribute).
+ inline static bool IsBetterThan(const AttributeInfo *lhs,
+ const AttributeInfo *rhs) {
+ if (lhs->is_unique != rhs->is_unique) {
+ return lhs->is_unique;
+ }
+ if (lhs->is_fixed_length != rhs->is_fixed_length) {
+ return lhs->is_fixed_length;
+ }
+ if (lhs->maximum_size != rhs->maximum_size) {
+ return lhs->maximum_size < rhs->maximum_size;
+ }
+ return lhs->attribute->id() < rhs->attribute->id();
+ }
+
+ const expressions::AttributeReferencePtr attribute;
+ const bool is_unique;
+ const bool is_fixed_length;
+ const std::size_t maximum_size;
+ };
+
+ physical::PhysicalPtr applyInternal(const physical::PhysicalPtr &input);
+ physical::PhysicalPtr applyToNode(const physical::PhysicalPtr &input);
+
+ OptimizerContext *optimizer_context_;
+ std::unique_ptr<cost::StarSchemaSimpleCostModel> cost_model_;
+
+ // Maps an attribute's id to the TableReference that generates the attribute.
+ std::unordered_map<expressions::ExprId,
+ std::pair<physical::TableReferencePtr,
+ expressions::AttributeReferencePtr>> source_;
+
+ DISALLOW_COPY_AND_ASSIGN(ReduceGroupByAttributes);
+};
+
+} // namespace optimizer
+} // namespace quickstep
+
+#endif // QUICKSTEP_QUERY_OPTIMIZER_RULES_REDUCE_GROUP_BY_ATTRIBUTES_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/tests/OptimizerTest.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/OptimizerTest.cpp b/query_optimizer/tests/OptimizerTest.cpp
index 3838638..7eb7a11 100644
--- a/query_optimizer/tests/OptimizerTest.cpp
+++ b/query_optimizer/tests/OptimizerTest.cpp
@@ -62,7 +62,7 @@ OptimizerTest::OptimizerTest()
catalog_database_(
new CatalogDatabase(catalog_.get(), "TestDatabase" /* name */, 0)),
optimizer_context_(new OptimizerContext),
- physical_generator_(new PhysicalGenerator()) {}
+ physical_generator_(new PhysicalGenerator(optimizer_context_.get())) {}
E::AliasPtr OptimizerTest::createAlias(const E::ExpressionPtr &expression,
const std::string &attribute_name,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/tests/OptimizerTextTestRunner.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/OptimizerTextTestRunner.cpp b/query_optimizer/tests/OptimizerTextTestRunner.cpp
index b9238c9..cb8f153 100644
--- a/query_optimizer/tests/OptimizerTextTestRunner.cpp
+++ b/query_optimizer/tests/OptimizerTextTestRunner.cpp
@@ -80,7 +80,7 @@ void OptimizerTextTestRunner::runTestCase(const std::string &input,
}
if (output_physical_plan) {
physical_plan =
- generatePhysicalPlan(optimized_logical_plan);
+ generatePhysicalPlan(optimized_logical_plan, &optimizer_context);
++num_options;
}
@@ -126,8 +126,9 @@ logical::LogicalPtr OptimizerTextTestRunner::generateLogicalPlan(
}
physical::PhysicalPtr OptimizerTextTestRunner::generatePhysicalPlan(
- const logical::LogicalPtr &logical_plan) {
- PhysicalGenerator physical_generator;
+ const logical::LogicalPtr &logical_plan,
+ OptimizerContext *optimizer_context) {
+ PhysicalGenerator physical_generator(optimizer_context);
return physical_generator.generatePlan(logical_plan);
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/query_optimizer/tests/OptimizerTextTestRunner.hpp
----------------------------------------------------------------------
diff --git a/query_optimizer/tests/OptimizerTextTestRunner.hpp b/query_optimizer/tests/OptimizerTextTestRunner.hpp
index 27fa14f..d8f604b 100644
--- a/query_optimizer/tests/OptimizerTextTestRunner.hpp
+++ b/query_optimizer/tests/OptimizerTextTestRunner.hpp
@@ -73,7 +73,8 @@ class OptimizerTextTestRunner : public TextBasedTestRunner {
OptimizerContext *optimizer_context);
physical::PhysicalPtr generatePhysicalPlan(
- const logical::LogicalPtr &logical_plan);
+ const logical::LogicalPtr &logical_plan,
+ OptimizerContext *optimizer_context);
SqlParserWrapper sql_parser_;
TestDatabaseLoader test_database_loader_;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/022787a1/third_party/src/iwyu/iwyu_helper.py
----------------------------------------------------------------------
diff --git a/third_party/src/iwyu/iwyu_helper.py b/third_party/src/iwyu/iwyu_helper.py
index dff4d55..93ddbae 100755
--- a/third_party/src/iwyu/iwyu_helper.py
+++ b/third_party/src/iwyu/iwyu_helper.py
@@ -22,15 +22,15 @@ QUICKSTEP_INCLUDES = [ '.',
'./build/third_party/gflags/include',
'./build/third_party/protobuf/include',
'./build/third_party/tmb/include',
- './third_party/benchmark/include',
- './third_party/glog/src',
- './third_party/googletest/googletest/include',
- './third_party/protobuf/src',
- './third_party/re2',
- './third_party/tmb/include']
+ './third_party/src/benchmark/include',
+ './third_party/src/glog/src',
+ './third_party/src/googletest/googletest/include',
+ './third_party/src/protobuf/src',
+ './third_party/src/re2',
+ './third_party/src/tmb/include']
QUICKSTEP_DEFINES = [ '-DQUICKSTEP_DEBUG',
'-DQUICKSTEP_ENABLE_VECTOR_COPY_ELISION_SELECTION', ]
-CLANG_FLAGS = [ '-std=c++14', '-x', 'c++', ]
+CLANG_FLAGS = [ '-std=c++14', '-x', 'c++', '-ferror-limit=-1' ]
# Custom configuration filenames.
CUSTOM_IWYU_MAPPINGS = '.iwyu.imp'