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 2016/08/02 21:58:06 UTC
incubator-quickstep git commit: Initial commit
Repository: incubator-quickstep
Updated Branches:
refs/heads/execution-dag-visualizer [created] 06ab173c7
Initial commit
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/06ab173c
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/06ab173c
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/06ab173c
Branch: refs/heads/execution-dag-visualizer
Commit: 06ab173c7bc5e13cd3f2fd8b7ec217676eaade42
Parents: aaecc76
Author: Jianqiao Zhu <ji...@cs.wisc.edu>
Authored: Tue Aug 2 16:57:47 2016 -0500
Committer: Jianqiao Zhu <ji...@cs.wisc.edu>
Committed: Tue Aug 2 16:57:47 2016 -0500
----------------------------------------------------------------------
CMakeLists.txt | 1 +
cli/QuickstepCli.cpp | 19 +-
query_execution/ForemanSingleNode.cpp | 12 +-
query_execution/ForemanSingleNode.hpp | 11 ++
query_execution/PolicyEnforcerBase.cpp | 3 +-
query_execution/PolicyEnforcerBase.hpp | 9 +-
query_execution/QueryExecutionMessages.proto | 10 +-
query_execution/QueryExecutionTypedefs.hpp | 6 +
query_execution/Worker.cpp | 15 +-
.../tests/QueryManagerSingleNode_unittest.cpp | 4 +
relational_operators/AggregationOperator.hpp | 4 +
relational_operators/BuildHashOperator.hpp | 4 +
relational_operators/CreateIndexOperator.hpp | 4 +
relational_operators/CreateTableOperator.hpp | 4 +
relational_operators/DeleteOperator.hpp | 4 +
relational_operators/DestroyHashOperator.hpp | 4 +
relational_operators/DropTableOperator.hpp | 4 +
.../FinalizeAggregationOperator.hpp | 4 +
relational_operators/HashJoinOperator.hpp | 15 ++
relational_operators/InsertOperator.hpp | 4 +
.../NestedLoopsJoinOperator.hpp | 4 +
relational_operators/RelationalOperator.hpp | 16 ++
relational_operators/SampleOperator.hpp | 4 +
relational_operators/SaveBlocksOperator.hpp | 4 +
relational_operators/SelectOperator.hpp | 4 +
relational_operators/SortMergeRunOperator.hpp | 4 +
.../SortRunGenerationOperator.hpp | 4 +
relational_operators/TableGeneratorOperator.hpp | 4 +
relational_operators/TextScanOperator.hpp | 4 +
relational_operators/UpdateOperator.hpp | 4 +
.../WindowAggregationOperator.hpp | 4 +
utility/CMakeLists.txt | 9 +
utility/ExecutionDAGVisualizer.cpp | 183 +++++++++++++++++++
utility/ExecutionDAGVisualizer.hpp | 109 +++++++++++
34 files changed, 480 insertions(+), 18 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 0bbde61..3192713 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -770,6 +770,7 @@ target_link_libraries(quickstep_cli_shell
quickstep_queryoptimizer_QueryProcessor
quickstep_storage_PreloaderThread
quickstep_threading_ThreadIDBasedMap
+ quickstep_utility_ExecutionDAGVisualizer
quickstep_utility_Macros
quickstep_utility_PtrVector
quickstep_utility_SqlError
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/cli/QuickstepCli.cpp
----------------------------------------------------------------------
diff --git a/cli/QuickstepCli.cpp b/cli/QuickstepCli.cpp
index 68a3599..08f11c4 100644
--- a/cli/QuickstepCli.cpp
+++ b/cli/QuickstepCli.cpp
@@ -75,6 +75,7 @@ typedef quickstep::LineReaderDumb LineReaderImpl;
#include "storage/PreloaderThread.hpp"
#include "threading/ThreadIDBasedMap.hpp"
+#include "utility/ExecutionDAGVisualizer.hpp"
#include "utility/Macros.hpp"
#include "utility/PtrVector.hpp"
#include "utility/SqlError.hpp"
@@ -185,6 +186,10 @@ DEFINE_string(profile_file_name, "",
// To put things in perspective, the first run is, in my experiments, about 5-10
// times more expensive than the average run. That means the query needs to be
// run at least a hundred times to make the impact of the first run small (< 5 %).
+DEFINE_bool(visualize_execution_dag, false,
+ "If true, visualize the execution plan DAG into a graph in DOT "
+ "format (DOT is a plain text graph description language) which is "
+ "then printed via stderr.");
} // namespace quickstep
@@ -361,7 +366,7 @@ int main(int argc, char* argv[]) {
query_processor->getStorageManager(),
-1, // Don't pin the Foreman thread.
num_numa_nodes_system,
- quickstep::FLAGS_profile_and_report_workorder_perf);
+ quickstep::FLAGS_profile_and_report_workorder_perf || quickstep::FLAGS_visualize_execution_dag);
// Start the worker threads.
for (Worker &worker : workers) {
@@ -471,6 +476,18 @@ int main(int argc, char* argv[]) {
foreman.printWorkOrderProfilingResults(query_handle->query_id(),
stdout);
}
+ if (quickstep::FLAGS_visualize_execution_dag) {
+ quickstep::ExecutionDAGVisualizer dag_visualizer(
+ *query_handle->getQueryPlanMutable());
+ const auto &profiling_results =
+ foreman.getWorkOrderProfilingResults(query_handle->query_id());
+ const auto overall_start_time =
+ std::chrono::duration_cast<std::chrono::microseconds>(
+ start.time_since_epoch()).count();
+ std::cerr << "\n"
+ << dag_visualizer.toDOT(&profiling_results, overall_start_time)
+ << "\n";
+ }
} catch (const std::exception &e) {
fprintf(stderr, "QUERY EXECUTION ERROR: %s\n", e.what());
break;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/query_execution/ForemanSingleNode.cpp
----------------------------------------------------------------------
diff --git a/query_execution/ForemanSingleNode.cpp b/query_execution/ForemanSingleNode.cpp
index cda02a7..7e6ad99 100644
--- a/query_execution/ForemanSingleNode.cpp
+++ b/query_execution/ForemanSingleNode.cpp
@@ -238,11 +238,15 @@ void ForemanSingleNode::sendWorkerMessage(const size_t worker_thread_index,
<< worker_directory_->getClientID(worker_thread_index);
}
+const std::vector<WorkOrderTimeEntry>& ForemanSingleNode
+ ::getWorkOrderProfilingResults(const std::size_t query_id) const {
+ return policy_enforcer_->getProfilingResults(query_id);
+}
+
void ForemanSingleNode::printWorkOrderProfilingResults(const std::size_t query_id,
std::FILE *out) const {
- const std::vector<
- std::tuple<std::size_t, std::size_t, std::size_t>>
- &recorded_times = policy_enforcer_->getProfilingResults(query_id);
+ const std::vector<WorkOrderTimeEntry> &recorded_times =
+ policy_enforcer_->getProfilingResults(query_id);
fputs("Query ID,Worker ID,NUMA Socket,Operator ID,Time (microseconds)\n", out);
for (auto workorder_entry : recorded_times) {
// Note: Index of the "worker thread index" in the tuple is 0.
@@ -253,7 +257,7 @@ void ForemanSingleNode::printWorkOrderProfilingResults(const std::size_t query_i
worker_id,
worker_directory_->getNUMANode(worker_id),
std::get<1>(workorder_entry), // Operator ID.
- std::get<2>(workorder_entry)); // Time.
+ std::get<3>(workorder_entry) - std::get<2>(workorder_entry)); // Time.
}
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/query_execution/ForemanSingleNode.hpp
----------------------------------------------------------------------
diff --git a/query_execution/ForemanSingleNode.hpp b/query_execution/ForemanSingleNode.hpp
index caef5e0..d999095 100644
--- a/query_execution/ForemanSingleNode.hpp
+++ b/query_execution/ForemanSingleNode.hpp
@@ -76,6 +76,17 @@ class ForemanSingleNode final : public ForemanBase {
~ForemanSingleNode() override {}
+
+ /**
+ * @brief Get the results of profiling individual work orders for a given
+ * query.
+ *
+ * @param query_id The ID of the query for which the results are to be printed.
+ * @return A vector of tuples, each being a single profiling entry.
+ **/
+ const std::vector<WorkOrderTimeEntry>& getWorkOrderProfilingResults(
+ const std::size_t query_id) const;
+
/**
* @brief Print the results of profiling individual work orders for a given
* query.
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/query_execution/PolicyEnforcerBase.cpp
----------------------------------------------------------------------
diff --git a/query_execution/PolicyEnforcerBase.cpp b/query_execution/PolicyEnforcerBase.cpp
index d16a502..1ddfe67 100644
--- a/query_execution/PolicyEnforcerBase.cpp
+++ b/query_execution/PolicyEnforcerBase.cpp
@@ -171,7 +171,8 @@ void PolicyEnforcerBase::recordTimeForWorkOrder(
workorder_time_recorder_[query_id].emplace_back(
proto.worker_thread_index(),
proto.operator_index(),
- proto.execution_time_in_microseconds());
+ proto.execution_start_time(),
+ proto.execution_end_time());
}
} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/query_execution/PolicyEnforcerBase.hpp
----------------------------------------------------------------------
diff --git a/query_execution/PolicyEnforcerBase.hpp b/query_execution/PolicyEnforcerBase.hpp
index 0482ebc..a5180e3 100644
--- a/query_execution/PolicyEnforcerBase.hpp
+++ b/query_execution/PolicyEnforcerBase.hpp
@@ -126,8 +126,8 @@ class PolicyEnforcerBase {
*
* @return A vector of tuples, each being a single profiling entry.
**/
- inline const std::vector<std::tuple<std::size_t, std::size_t, std::size_t>>&
- getProfilingResults(const std::size_t query_id) const {
+ inline const std::vector<WorkOrderTimeEntry>& getProfilingResults(
+ const std::size_t query_id) const {
DCHECK(profile_individual_workorders_);
DCHECK(workorder_time_recorder_.find(query_id) !=
workorder_time_recorder_.end());
@@ -164,10 +164,7 @@ class PolicyEnforcerBase {
// 1st element: Logical worker ID.
// 2nd element: Operator ID.
// 3rd element: Time in microseconds to execute the work order.
- std::unordered_map<
- std::size_t,
- std::vector<std::tuple<std::size_t, std::size_t, std::size_t>>>
- workorder_time_recorder_;
+ WorkOrderTimeRecorder workorder_time_recorder_;
private:
/**
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/query_execution/QueryExecutionMessages.proto
----------------------------------------------------------------------
diff --git a/query_execution/QueryExecutionMessages.proto b/query_execution/QueryExecutionMessages.proto
index 308d736..db94130 100644
--- a/query_execution/QueryExecutionMessages.proto
+++ b/query_execution/QueryExecutionMessages.proto
@@ -42,7 +42,10 @@ message NormalWorkOrderCompletionMessage {
required uint64 operator_index = 1;
required uint64 worker_thread_index = 2;
required uint64 query_id = 3;
- optional uint64 execution_time_in_microseconds = 4;
+
+ // Epoch time in microseconds.
+ optional uint64 execution_start_time = 4;
+ optional uint64 execution_end_time = 5;
}
// A message sent upon completion of a rebuild WorkOrder execution.
@@ -50,7 +53,10 @@ message RebuildWorkOrderCompletionMessage {
required uint64 operator_index = 1;
required uint64 worker_thread_index = 2;
required uint64 query_id = 3;
- optional uint64 execution_time_in_microseconds = 4;
+
+ // Epoch time in microseconds.
+ optional uint64 execution_start_time = 4;
+ optional uint64 execution_end_time = 5;
}
message CatalogRelationNewBlockMessage {
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/query_execution/QueryExecutionTypedefs.hpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryExecutionTypedefs.hpp b/query_execution/QueryExecutionTypedefs.hpp
index b67209f..26ff6fc 100644
--- a/query_execution/QueryExecutionTypedefs.hpp
+++ b/query_execution/QueryExecutionTypedefs.hpp
@@ -98,6 +98,12 @@ enum QueryExecutionMessageType : message_type_id {
#endif
};
+// WorkOrder profiling data structures.
+// A tuple of <Worker ID, Operator ID, Start Time, End Time>
+typedef std::tuple<std::size_t, std::size_t, std::size_t, std::size_t> WorkOrderTimeEntry;
+
+typedef std::unordered_map<std::size_t, std::vector<WorkOrderTimeEntry>> WorkOrderTimeRecorder;
+
/** @} */
} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/query_execution/Worker.cpp
----------------------------------------------------------------------
diff --git a/query_execution/Worker.cpp b/query_execution/Worker.cpp
index 6ba27f1..a582132 100644
--- a/query_execution/Worker.cpp
+++ b/query_execution/Worker.cpp
@@ -120,14 +120,21 @@ void Worker::executeWorkOrderHelper(const TaggedMessage &tagged_message,
worker_message.getWorkOrder()->execute();
end = std::chrono::steady_clock::now();
delete worker_message.getWorkOrder();
- const uint64_t execution_time_microseconds =
- std::chrono::duration_cast<std::chrono::microseconds>(end - start)
- .count();
+
+ // Convert the measured timestamps to epoch times in microseconds.
+ const uint64_t execution_start_time =
+ std::chrono::duration_cast<std::chrono::microseconds>(
+ start.time_since_epoch()).count();
+ const uint64_t execution_end_time =
+ std::chrono::duration_cast<std::chrono::microseconds>(
+ end.time_since_epoch()).count();
+
// Construct the proto message.
proto->set_operator_index(worker_message.getRelationalOpIndex());
proto->set_query_id(query_id_for_workorder);
proto->set_worker_thread_index(worker_thread_index_);
- proto->set_execution_time_in_microseconds(execution_time_microseconds);
+ proto->set_execution_start_time(execution_start_time);
+ proto->set_execution_end_time(execution_end_time);
}
} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/query_execution/tests/QueryManagerSingleNode_unittest.cpp
----------------------------------------------------------------------
diff --git a/query_execution/tests/QueryManagerSingleNode_unittest.cpp b/query_execution/tests/QueryManagerSingleNode_unittest.cpp
index 39ca58c..7c96e7f 100644
--- a/query_execution/tests/QueryManagerSingleNode_unittest.cpp
+++ b/query_execution/tests/QueryManagerSingleNode_unittest.cpp
@@ -104,6 +104,10 @@ class MockOperator: public RelationalOperator {
num_calls_donefeedingblocks_(0) {
}
+ std::string getName() const override {
+ return "MockOperator";
+ }
+
#define MOCK_OP_LOG(x) VLOG(x) << "Op[" << op_index_ << "]: " << __func__ << ": "
// The methods below are used to check whether QueryManager calls the Relational
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/AggregationOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/AggregationOperator.hpp b/relational_operators/AggregationOperator.hpp
index 4bcbcf6..c46ba2c 100644
--- a/relational_operators/AggregationOperator.hpp
+++ b/relational_operators/AggregationOperator.hpp
@@ -77,6 +77,10 @@ class AggregationOperator : public RelationalOperator {
~AggregationOperator() override {}
+ std::string getName() const override {
+ return "AggregationOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/BuildHashOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/BuildHashOperator.hpp b/relational_operators/BuildHashOperator.hpp
index 464bbf8..952c7ac 100644
--- a/relational_operators/BuildHashOperator.hpp
+++ b/relational_operators/BuildHashOperator.hpp
@@ -93,6 +93,10 @@ class BuildHashOperator : public RelationalOperator {
~BuildHashOperator() override {}
+ std::string getName() const override {
+ return "BuildHashOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/CreateIndexOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/CreateIndexOperator.hpp b/relational_operators/CreateIndexOperator.hpp
index 18ca656..4e05448 100644
--- a/relational_operators/CreateIndexOperator.hpp
+++ b/relational_operators/CreateIndexOperator.hpp
@@ -69,6 +69,10 @@ class CreateIndexOperator : public RelationalOperator {
~CreateIndexOperator() override {}
+ std::string getName() const override {
+ return "CreateIndexOperator";
+ }
+
/**
* @note No WorkOrder generated for this operator.
**/
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/CreateTableOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/CreateTableOperator.hpp b/relational_operators/CreateTableOperator.hpp
index 6d91142..b7b707b 100644
--- a/relational_operators/CreateTableOperator.hpp
+++ b/relational_operators/CreateTableOperator.hpp
@@ -66,6 +66,10 @@ class CreateTableOperator : public RelationalOperator {
~CreateTableOperator() override {}
+ std::string getName() const override {
+ return "CreateTableOperator";
+ }
+
/**
* @note No WorkOrder generated for this operator.
**/
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/DeleteOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/DeleteOperator.hpp b/relational_operators/DeleteOperator.hpp
index 74da8c1..abfe4a9 100644
--- a/relational_operators/DeleteOperator.hpp
+++ b/relational_operators/DeleteOperator.hpp
@@ -81,6 +81,10 @@ class DeleteOperator : public RelationalOperator {
~DeleteOperator() override {}
+ std::string getName() const override {
+ return "DeleteOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/DestroyHashOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/DestroyHashOperator.hpp b/relational_operators/DestroyHashOperator.hpp
index 181386f..ae65de5 100644
--- a/relational_operators/DestroyHashOperator.hpp
+++ b/relational_operators/DestroyHashOperator.hpp
@@ -58,6 +58,10 @@ class DestroyHashOperator : public RelationalOperator {
~DestroyHashOperator() override {}
+ std::string getName() const override {
+ return "DestroyHashOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/DropTableOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/DropTableOperator.hpp b/relational_operators/DropTableOperator.hpp
index 6c7fca3..f854b4f 100644
--- a/relational_operators/DropTableOperator.hpp
+++ b/relational_operators/DropTableOperator.hpp
@@ -74,6 +74,10 @@ class DropTableOperator : public RelationalOperator {
~DropTableOperator() override {}
+ std::string getName() const override {
+ return "DropTableOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/FinalizeAggregationOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/FinalizeAggregationOperator.hpp b/relational_operators/FinalizeAggregationOperator.hpp
index 158a637..0dcfc9e 100644
--- a/relational_operators/FinalizeAggregationOperator.hpp
+++ b/relational_operators/FinalizeAggregationOperator.hpp
@@ -74,6 +74,10 @@ class FinalizeAggregationOperator : public RelationalOperator {
~FinalizeAggregationOperator() override {}
+ std::string getName() const override {
+ return "FinalizeAggregationOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/HashJoinOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/HashJoinOperator.hpp b/relational_operators/HashJoinOperator.hpp
index 5d3d7da..15faacb 100644
--- a/relational_operators/HashJoinOperator.hpp
+++ b/relational_operators/HashJoinOperator.hpp
@@ -157,6 +157,21 @@ class HashJoinOperator : public RelationalOperator {
~HashJoinOperator() override {}
+ std::string getName() const override {
+ switch (join_type_) {
+ case JoinType::kInnerJoin:
+ return "HashJoinOperator";
+ case JoinType::kLeftSemiJoin:
+ return "HashJoinOperator(LeftSemi)";
+ case JoinType::kLeftAntiJoin:
+ return "HashJoinOperator(LeftAnti)";
+ case JoinType::kLeftOuterJoin:
+ return "HashJoinOperator(LeftOuter)";
+ default: break;
+ }
+ LOG(FATAL) << "Unknown join type in HashJoinOperator::getName()";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/InsertOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/InsertOperator.hpp b/relational_operators/InsertOperator.hpp
index 78f5199..2c6aca7 100644
--- a/relational_operators/InsertOperator.hpp
+++ b/relational_operators/InsertOperator.hpp
@@ -73,6 +73,10 @@ class InsertOperator : public RelationalOperator {
~InsertOperator() override {}
+ std::string getName() const override {
+ return "InsertOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/NestedLoopsJoinOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/NestedLoopsJoinOperator.hpp b/relational_operators/NestedLoopsJoinOperator.hpp
index 992e76d..cf190fe 100644
--- a/relational_operators/NestedLoopsJoinOperator.hpp
+++ b/relational_operators/NestedLoopsJoinOperator.hpp
@@ -116,6 +116,10 @@ class NestedLoopsJoinOperator : public RelationalOperator {
~NestedLoopsJoinOperator() override {}
+ std::string getName() const override {
+ return "NestedLoopsJoinOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/RelationalOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/RelationalOperator.hpp b/relational_operators/RelationalOperator.hpp
index 116727b..65cd213 100644
--- a/relational_operators/RelationalOperator.hpp
+++ b/relational_operators/RelationalOperator.hpp
@@ -55,6 +55,13 @@ class RelationalOperator {
virtual ~RelationalOperator() {}
/**
+ * @brief Get the name of this relational operator.
+ *
+ * @return The name of this relational operator.
+ */
+ virtual std::string getName() const = 0;
+
+ /**
* @brief Generate all the next WorkOrders for this RelationalOperator.
*
* @note If a RelationalOperator has blocking dependencies, it should not
@@ -226,6 +233,15 @@ class RelationalOperator {
op_index_ = operator_index;
}
+ /**
+ * @brief Get the index of this operator in the query plan DAG.
+ *
+ * @return The index of this operator in the query plan DAG.
+ */
+ std::size_t getOperatorIndex() const {
+ return op_index_;
+ }
+
protected:
/**
* @brief Constructor
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/SampleOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/SampleOperator.hpp b/relational_operators/SampleOperator.hpp
index f8fe5f6..08f08c8 100644
--- a/relational_operators/SampleOperator.hpp
+++ b/relational_operators/SampleOperator.hpp
@@ -93,6 +93,10 @@ class SampleOperator : public RelationalOperator {
~SampleOperator() override {}
+ std::string getName() const override {
+ return "SampleOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/SaveBlocksOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/SaveBlocksOperator.hpp b/relational_operators/SaveBlocksOperator.hpp
index 50032b6..ebc5ffc 100644
--- a/relational_operators/SaveBlocksOperator.hpp
+++ b/relational_operators/SaveBlocksOperator.hpp
@@ -64,6 +64,10 @@ class SaveBlocksOperator : public RelationalOperator {
~SaveBlocksOperator() override {}
+ std::string getName() const override {
+ return "SaveBlocksOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/SelectOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/SelectOperator.hpp b/relational_operators/SelectOperator.hpp
index 0c10686..ee25886 100644
--- a/relational_operators/SelectOperator.hpp
+++ b/relational_operators/SelectOperator.hpp
@@ -189,6 +189,10 @@ class SelectOperator : public RelationalOperator {
~SelectOperator() override {}
+ std::string getName() const override {
+ return "SelectOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/SortMergeRunOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/SortMergeRunOperator.hpp b/relational_operators/SortMergeRunOperator.hpp
index 177836f..9b07ad6 100644
--- a/relational_operators/SortMergeRunOperator.hpp
+++ b/relational_operators/SortMergeRunOperator.hpp
@@ -129,6 +129,10 @@ class SortMergeRunOperator : public RelationalOperator {
**/
~SortMergeRunOperator() {}
+ std::string getName() const override {
+ return "SortMergeRunOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/SortRunGenerationOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/SortRunGenerationOperator.hpp b/relational_operators/SortRunGenerationOperator.hpp
index 96a3ce1..54c7feb 100644
--- a/relational_operators/SortRunGenerationOperator.hpp
+++ b/relational_operators/SortRunGenerationOperator.hpp
@@ -109,6 +109,10 @@ class SortRunGenerationOperator : public RelationalOperator {
~SortRunGenerationOperator() {}
+ std::string getName() const override {
+ return "SortRunGenerationOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/TableGeneratorOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/TableGeneratorOperator.hpp b/relational_operators/TableGeneratorOperator.hpp
index 1b791a6..15e7052 100644
--- a/relational_operators/TableGeneratorOperator.hpp
+++ b/relational_operators/TableGeneratorOperator.hpp
@@ -76,6 +76,10 @@ class TableGeneratorOperator : public RelationalOperator {
~TableGeneratorOperator() override {}
+ std::string getName() const override {
+ return "TableGeneratorOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/TextScanOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/TextScanOperator.hpp b/relational_operators/TextScanOperator.hpp
index 1a62ded..6890d7d 100644
--- a/relational_operators/TextScanOperator.hpp
+++ b/relational_operators/TextScanOperator.hpp
@@ -134,6 +134,10 @@ class TextScanOperator : public RelationalOperator {
~TextScanOperator() override {}
+ std::string getName() const override {
+ return "TextScanOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/UpdateOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/UpdateOperator.hpp b/relational_operators/UpdateOperator.hpp
index 4471a17..d021844 100644
--- a/relational_operators/UpdateOperator.hpp
+++ b/relational_operators/UpdateOperator.hpp
@@ -94,6 +94,10 @@ class UpdateOperator : public RelationalOperator {
~UpdateOperator() override {}
+ std::string getName() const override {
+ return "UpdateOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/relational_operators/WindowAggregationOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/WindowAggregationOperator.hpp b/relational_operators/WindowAggregationOperator.hpp
index bd83248..ee9b9b2 100644
--- a/relational_operators/WindowAggregationOperator.hpp
+++ b/relational_operators/WindowAggregationOperator.hpp
@@ -78,6 +78,10 @@ class WindowAggregationOperator : public RelationalOperator {
~WindowAggregationOperator() override {}
+ std::string getName() const override {
+ return "WindowAggregationOperator";
+ }
+
bool getAllWorkOrders(WorkOrdersContainer *container,
QueryContext *query_context,
StorageManager *storage_manager,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/utility/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/utility/CMakeLists.txt b/utility/CMakeLists.txt
index 2d3db8f..80b4ec7 100644
--- a/utility/CMakeLists.txt
+++ b/utility/CMakeLists.txt
@@ -167,6 +167,9 @@ add_library(quickstep_utility_Cast ../empty_src.cpp Cast.hpp)
add_library(quickstep_utility_CheckSnprintf ../empty_src.cpp CheckSnprintf.hpp)
add_library(quickstep_utility_DAG ../empty_src.cpp DAG.hpp)
add_library(quickstep_utility_EqualsAnyConstant ../empty_src.cpp EqualsAnyConstant.hpp)
+add_library(quickstep_utility_ExecutionDAGVisualizer
+ ExecutionDAGVisualizer.cpp
+ ExecutionDAGVisualizer.hpp)
add_library(quickstep_utility_Glob Glob.cpp Glob.hpp)
add_library(quickstep_utility_HashPair ../empty_src.cpp HashPair.hpp)
add_library(quickstep_utility_Macros ../empty_src.cpp Macros.hpp)
@@ -225,6 +228,11 @@ target_link_libraries(quickstep_utility_CheckSnprintf
target_link_libraries(quickstep_utility_DAG
glog
quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_ExecutionDAGVisualizer
+ quickstep_queryexecution_QueryExecutionTypedefs
+ quickstep_queryoptimizer_QueryPlan
+ quickstep_utility_Macros
+ quickstep_utility_StringUtil)
target_link_libraries(quickstep_utility_Glob
glog)
target_link_libraries(quickstep_utility_MemStream
@@ -303,6 +311,7 @@ target_link_libraries(quickstep_utility
quickstep_utility_CheckSnprintf
quickstep_utility_DAG
quickstep_utility_EqualsAnyConstant
+ quickstep_utility_ExecutionDAGVisualizer
quickstep_utility_Glob
quickstep_utility_HashPair
quickstep_utility_Macros
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/utility/ExecutionDAGVisualizer.cpp
----------------------------------------------------------------------
diff --git a/utility/ExecutionDAGVisualizer.cpp b/utility/ExecutionDAGVisualizer.cpp
new file mode 100644
index 0000000..33dd0d1
--- /dev/null
+++ b/utility/ExecutionDAGVisualizer.cpp
@@ -0,0 +1,183 @@
+/**
+ * Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ * University of Wisconsin\u2014Madison.
+ *
+ * Licensed 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 "utility/ExecutionDAGVisualizer.hpp"
+
+#include <cmath>
+#include <cstddef>
+#include <iomanip>
+#include <memory>
+#include <sstream>
+#include <string>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+#include "query_execution/QueryExecutionTypedefs.hpp"
+#include "query_optimizer/QueryPlan.hpp"
+#include "utility/StringUtil.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+std::string ExecutionDAGVisualizer::toDOT() {
+ return toDOT(nullptr);
+}
+
+std::string ExecutionDAGVisualizer::toDOT(
+ const std::vector<WorkOrderTimeEntry> *execution_time_records,
+ const std::size_t overall_start_time) {
+ // Do not display these relational operators in the graph.
+ std::set<std::string> no_display_op_names =
+ { "DestroyHashOperator", "DropTableOperator" };
+
+ const auto &dag = plan_.getQueryPlanDAG();
+ const std::size_t num_nodes = dag.size();
+
+ // Collect DAG vertices info.
+ std::vector<bool> display_ops(num_nodes, false);
+ for (std::size_t node_index = 0; node_index < num_nodes; ++node_index) {
+ const auto &node = dag.getNodePayload(node_index);
+ const std::string relop_name = node.getName();
+ if (no_display_op_names.find(relop_name) == no_display_op_names.end()) {
+ display_ops[node_index] = true;
+ nodes_.emplace_back();
+ nodes_.back().id = node_index;
+ nodes_.back().labels.emplace_back(
+ "[" + std::to_string(node.getOperatorIndex()) + "] " + relop_name);
+ }
+ }
+
+ // Collect DAG edges info.
+ for (std::size_t node_index = 0; node_index < num_nodes; ++node_index) {
+ if (display_ops[node_index]) {
+ for (const auto &link : dag.getDependents(node_index)) {
+ if (display_ops[link.first]) {
+ edges_.emplace_back();
+ edges_.back().src_node_id = node_index;
+ edges_.back().dst_node_id = link.first;
+ edges_.back().is_pipeline_breaker = link.second;
+ }
+ }
+ }
+ }
+
+ // Attach execution timing stats.
+ if (execution_time_records != nullptr) {
+ std::vector<std::size_t> time_start(num_nodes, std::numeric_limits<double>::max());
+ std::vector<std::size_t> time_end(num_nodes, 0);
+ std::vector<std::size_t> time_elapsed(num_nodes, 0);
+ for (const auto &entry : *execution_time_records) {
+ const std::size_t relop_index = std::get<1>(entry);
+ const std::size_t workorder_start_time = std::get<2>(entry);
+ const std::size_t workorder_end_time = std::get<3>(entry);
+ time_start[relop_index] =
+ std::min(time_start[relop_index], workorder_start_time);
+ time_end[relop_index] =
+ std::max(time_end[relop_index], workorder_end_time);
+ time_elapsed[relop_index] += (workorder_end_time - workorder_start_time);
+ }
+
+ std::vector<double> time_percentage(num_nodes, 0);
+ std::size_t total_time_elapsed = 0;
+ double max_percentage = 0;
+ for (std::size_t i = 0; i < time_elapsed.size(); ++i) {
+ total_time_elapsed += time_elapsed[i];
+ }
+ for (std::size_t i = 0; i < time_elapsed.size(); ++i) {
+ time_percentage[i] = time_elapsed[i] / static_cast<double>(total_time_elapsed);
+ max_percentage = std::max(max_percentage, time_percentage[i]);
+ }
+
+ for (std::size_t node_index = 0; node_index < num_nodes; ++node_index) {
+ if (display_ops[node_index]) {
+ NodeInfo &node_info = nodes_[node_index];
+
+ std::string hue =
+ std::to_string(std::sqrt(time_percentage[node_index] / max_percentage));
+ node_info.color = hue + " " + hue + " 1.0";
+
+ node_info.labels.emplace_back(
+ "total cpu: " +
+ std::to_string(time_elapsed[node_index] / 1000) +
+ "ms (" + FormatPercentage(time_percentage[node_index]) + ")");
+ if (overall_start_time == 0) {
+ node_info.labels.emplace_back(
+ "span: " +
+ std::to_string((time_end[node_index] - time_start[node_index]) / 1000) + "ms");
+ } else {
+ node_info.labels.emplace_back(
+ "span: [" +
+ std::to_string((time_start[node_index] - overall_start_time) / 1000) + "ms, " +
+ std::to_string((time_end[node_index] - overall_start_time) / 1000) + "ms]");
+ }
+ }
+ }
+ }
+
+ // Format output graph
+ std::ostringstream graph_oss;
+ graph_oss << "digraph g {\n";
+ graph_oss << " rankdir=BT\n";
+ graph_oss << " node [penwidth=2]\n";
+ graph_oss << " edge [fontsize=16 fontcolor=gray penwidth=2]\n\n";
+
+ // Format nodes
+ for (const NodeInfo &node_info : nodes_) {
+ graph_oss << " " << node_info.id << " [ ";
+ if (!node_info.labels.empty()) {
+ graph_oss << "label=\""
+ << EscapeSpecialChars(JoinToString(node_info.labels, " "))
+ << "\" ";
+ }
+ if (!node_info.color.empty()) {
+ graph_oss << "style=filled fillcolor=\"" << node_info.color << "\" ";
+ }
+ graph_oss << "]\n";
+ }
+ graph_oss << "\n";
+
+ // Format edges
+ for (const EdgeInfo &edge_info : edges_) {
+ graph_oss << " " << edge_info.src_node_id << " -> "
+ << edge_info.dst_node_id << " [ ";
+ if (edge_info.is_pipeline_breaker) {
+ graph_oss << "style=dashed ";
+ }
+ if (!edge_info.labels.empty()) {
+ graph_oss << "label=\""
+ << EscapeSpecialChars(JoinToString(edge_info.labels, " "))
+ << "\" ";
+ }
+ graph_oss << "]\n";
+ }
+
+ graph_oss << "}\n";
+
+ return graph_oss.str();
+}
+
+std::string ExecutionDAGVisualizer::FormatPercentage(double percentage) {
+ std::ostringstream oss;
+ oss << static_cast<std::uint32_t>(percentage * 100) << ".";
+ int digits = std::lround(percentage * 10000) % 100;
+ oss << digits / 10 << digits % 10 << "%";
+ return oss.str();
+}
+
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/06ab173c/utility/ExecutionDAGVisualizer.hpp
----------------------------------------------------------------------
diff --git a/utility/ExecutionDAGVisualizer.hpp b/utility/ExecutionDAGVisualizer.hpp
new file mode 100644
index 0000000..54db12c
--- /dev/null
+++ b/utility/ExecutionDAGVisualizer.hpp
@@ -0,0 +1,109 @@
+/**
+ * Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ * University of Wisconsin\u2014Madison.
+ *
+ * Licensed 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_UTILITY_EXECUTION_DAG_VISUALIZER_HPP_
+#define QUICKSTEP_UTILITY_EXECUTION_DAG_VISUALIZER_HPP_
+
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include "query_execution/QueryExecutionTypedefs.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+
+class QueryPlan;
+
+/** \addtogroup Utility
+ * @{
+ */
+
+/**
+ * @brief A visualizer that converts an execution plan DAG into a graph in
+ * DOT format. Note that DOT is a plain text graph description language.
+ *
+ * @note This utility tool can be further extended to be more generic.
+ */
+class ExecutionDAGVisualizer {
+ public:
+ ExecutionDAGVisualizer(const QueryPlan &plan)
+ : plan_(plan) {}
+
+ ~ExecutionDAGVisualizer() {}
+
+ /**
+ * @brief Visualize the execution plan into a graph in DOT format (DOT is a plain
+ * text graph description language).
+ *
+ * @return The execution plan graph in DOT format.
+ */
+ std::string toDOT();
+
+ /**
+ * @brief Visualize the execution plan together with the execution timing stats
+ * into a graph in DOT format (DOT is a plain text graph description language).
+ *
+ * @param execution_time_records The profiled timing records of execution.
+ * @param overall_start_time The start time of the overall query execution.
+ * If provided, the graph will display each relational operator's
+ * execution time span with \p overall_start_time as the time origin.
+ * @return The execution plan graph with timing stats in DOT format.
+ */
+ std::string toDOT(const std::vector<WorkOrderTimeEntry> *execution_time_records,
+ const std::size_t overall_start_time = 0);
+
+ private:
+ /**
+ * @brief Format a percentage float value (between 0 and 1) to string
+ * representation.
+ */
+ static std::string FormatPercentage(double percentage);
+
+ /**
+ * @brief Information of a graph node.
+ */
+ struct NodeInfo {
+ std::size_t id;
+ std::vector<std::string> labels;
+ std::string color;
+ };
+
+ /**
+ * @brief Information of a graph edge.
+ */
+ struct EdgeInfo {
+ std::size_t src_node_id;
+ std::size_t dst_node_id;
+ std::vector<std::string> labels;
+ bool is_pipeline_breaker;
+ };
+
+ const QueryPlan &plan_;
+
+ std::vector<NodeInfo> nodes_;
+ std::vector<EdgeInfo> edges_;
+
+ DISALLOW_COPY_AND_ASSIGN(ExecutionDAGVisualizer);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif /* QUICKSTEP_UTILITY_EXECUTION_DAG_VISUALIZER_HPP_ */