You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by hb...@apache.org on 2016/11/01 21:56:58 UTC
[1/6] incubator-quickstep git commit: QUICKSTEP-61 Fixes varlen
insert bug. [Forced Update!]
Repository: incubator-quickstep
Updated Branches:
refs/heads/delay-hashtable-memory-alloc de3f3bad9 -> 161259f33 (forced update)
QUICKSTEP-61 Fixes varlen insert bug.
This change fixes an incorrect estimate for the maximum size of a
tuple. Previously, it was not accounting for the space used by the
fixed length portion of the tuple.
The unit tests were modified because, now, we insert fewer tuples. It's
actually quite hard to test the correct number of tuples which will be
inserted, so this has been left as a TODO.
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/70a3d47c
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/70a3d47c
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/70a3d47c
Branch: refs/heads/delay-hashtable-memory-alloc
Commit: 70a3d47cdcf46bbb8f39b1cc1a0fbd2650a6afa0
Parents: fc898b1
Author: cramja <ma...@gmail.com>
Authored: Tue Nov 1 13:42:04 2016 -0500
Committer: cramja <ma...@gmail.com>
Committed: Tue Nov 1 13:42:04 2016 -0500
----------------------------------------------------------------------
storage/SplitRowStoreTupleStorageSubBlock.cpp | 3 ++-
storage/tests/SplitRowStoreTupleStorageSubBlock_unittest.cpp | 8 ++------
2 files changed, 4 insertions(+), 7 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/70a3d47c/storage/SplitRowStoreTupleStorageSubBlock.cpp
----------------------------------------------------------------------
diff --git a/storage/SplitRowStoreTupleStorageSubBlock.cpp b/storage/SplitRowStoreTupleStorageSubBlock.cpp
index 068e975..1e6f7ff 100644
--- a/storage/SplitRowStoreTupleStorageSubBlock.cpp
+++ b/storage/SplitRowStoreTupleStorageSubBlock.cpp
@@ -334,6 +334,7 @@ tuple_id SplitRowStoreTupleStorageSubBlock::bulkInsertPartialTuplesImpl(
varlen_reserve -= relation_.getAttributeById(
copy_groups.varlen_attrs_[vattr_idx].dst_attr_id_)->getType().maximumByteLength();
}
+ DCHECK_GE(relation_.getMaximumVariableByteLength(), varlen_reserve);
}
InvokeOnAnyValueAccessor(
@@ -392,7 +393,7 @@ tuple_id SplitRowStoreTupleStorageSubBlock::bulkInsertPartialTuplesImpl(
(varlen_heap_offset_orig - varlen_heap_offset));
DCHECK_LE(0, remaining_storage_after_inserts);
std::size_t additional_tuples_insert =
- remaining_storage_after_inserts / this->relation_.getMaximumByteLength();
+ remaining_storage_after_inserts / (tuple_slot_bytes_ + this->relation_.getMaximumByteLength());
// We want to avoid a situation where we have several short insert iterations
// near the end of an insertion cycle.
if (additional_tuples_insert > this->getInsertLowerBoundThreshold()) {
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/70a3d47c/storage/tests/SplitRowStoreTupleStorageSubBlock_unittest.cpp
----------------------------------------------------------------------
diff --git a/storage/tests/SplitRowStoreTupleStorageSubBlock_unittest.cpp b/storage/tests/SplitRowStoreTupleStorageSubBlock_unittest.cpp
index b953854..9270d93 100644
--- a/storage/tests/SplitRowStoreTupleStorageSubBlock_unittest.cpp
+++ b/storage/tests/SplitRowStoreTupleStorageSubBlock_unittest.cpp
@@ -656,9 +656,7 @@ TEST_P(SplitRowStoreTupleStorageSubBlockTest, BulkInsertTest) {
// Actually do the bulk-insert.
accessor.beginIteration();
tuple_id num_inserted = tuple_store_->bulkInsertTuples(&accessor);
- if (testVariableLength()) {
- EXPECT_LE(current_tuple_idx - num_inserted, getInsertLowerBoundThreshold());
- } else {
+ if (!testVariableLength()) {
EXPECT_EQ(current_tuple_idx, num_inserted);
ASSERT_TRUE(accessor.iterationFinished());
// Shouldn't be able to insert any more tuples.
@@ -885,9 +883,7 @@ TEST_P(SplitRowStoreTupleStorageSubBlockTest, BulkInsertWithRemappedAttributesTe
// Actually do the bulk-insert.
accessor.beginIteration();
tuple_id num_inserted = tuple_store_->bulkInsertTuplesWithRemappedAttributes(attribute_map, &accessor);
- if (testVariableLength()) {
- EXPECT_LE(current_tuple_idx - num_inserted, getInsertLowerBoundThreshold());
- } else {
+ if (!testVariableLength()) {
EXPECT_EQ(current_tuple_idx, num_inserted);
ASSERT_TRUE(accessor.iterationFinished());
// Shouldn't be able to insert any more tuples.
[4/6] incubator-quickstep git commit: Add active and inactive
operators in QueryManager
Posted by hb...@apache.org.
Add active and inactive operators in QueryManager
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/13cf3955
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/13cf3955
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/13cf3955
Branch: refs/heads/delay-hashtable-memory-alloc
Commit: 13cf3955d8ad562f8322c5f8c4b9a1a072bc08bd
Parents: 70a3d47
Author: Harshad Deshmukh <hb...@apache.org>
Authored: Mon Oct 31 16:23:03 2016 -0500
Committer: Harshad Deshmukh <hb...@apache.org>
Committed: Tue Nov 1 16:56:38 2016 -0500
----------------------------------------------------------------------
query_execution/QueryManagerSingleNode.cpp | 53 ++++++++++++++++++++-----
query_execution/QueryManagerSingleNode.hpp | 16 ++++++++
2 files changed, 58 insertions(+), 11 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/13cf3955/query_execution/QueryManagerSingleNode.cpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryManagerSingleNode.cpp b/query_execution/QueryManagerSingleNode.cpp
index 237796f..e77600f 100644
--- a/query_execution/QueryManagerSingleNode.cpp
+++ b/query_execution/QueryManagerSingleNode.cpp
@@ -59,11 +59,13 @@ QueryManagerSingleNode::QueryManagerSingleNode(
bus_)),
workorders_container_(
new WorkOrdersContainer(num_operators_in_dag_, num_numa_nodes)) {
- // Collect all the workorders from all the relational operators in the DAG.
+ // Mark the active operators in the DAG.
for (dag_node_index index = 0; index < num_operators_in_dag_; ++index) {
if (checkAllBlockingDependenciesMet(index)) {
- query_dag_->getNodePayloadMutable(index)->informAllBlockingDependenciesMet();
- processOperator(index, false);
+ active_operators_.push_back(index);
+ activateOperator(index);
+ } else {
+ inactive_operators_.push_back(index);
}
}
}
@@ -71,14 +73,44 @@ QueryManagerSingleNode::QueryManagerSingleNode(
WorkerMessage* QueryManagerSingleNode::getNextWorkerMessage(
const dag_node_index start_operator_index, const numa_node_id numa_node) {
// Default policy: Operator with lowest index first.
- WorkOrder *work_order = nullptr;
- size_t num_operators_checked = 0;
- for (dag_node_index index = start_operator_index;
- num_operators_checked < num_operators_in_dag_;
- index = (index + 1) % num_operators_in_dag_, ++num_operators_checked) {
- if (query_exec_state_->hasExecutionFinished(index)) {
- continue;
+ WorkerMessage *worker_message = getNextWorkerMessageFromActiveOperators(numa_node);
+ if (worker_message != nullptr) {
+ return worker_message;
+ }
+ // Check the operators that have finished execution.
+ std::vector<dag_node_index> execution_finished_operator_indexes;
+ for (dag_node_index active_operator_index : active_operators_) {
+ if (query_exec_state_->hasExecutionFinished(active_operator_index)) {
+ execution_finished_operator_indexes.push_back(active_operator_index);
}
+ }
+ // Remove the "done" operators from the list of active operators.
+ for (dag_node_index index : execution_finished_operator_indexes) {
+ auto iter =
+ std::find(active_operators_.begin(), active_operators_.end(), index);
+ DCHECK(iter != active_operators_.end());
+ active_operators_.erase(iter);
+ }
+ // Move some inactive operators to active operators.
+ if (!inactive_operators_.empty()) {
+ for (dag_node_index inactive_op_count = 0;
+ inactive_op_count < execution_finished_operator_indexes.size();
+ ++inactive_op_count) {
+ if (checkAllBlockingDependenciesMet(inactive_operators_.front())) {
+ active_operators_.push_back(inactive_operators_.front());
+ inactive_operators_.pop_front();
+ activateOperator(active_operators_.back());
+ }
+ }
+ }
+ worker_message = getNextWorkerMessageFromActiveOperators(numa_node);
+ return worker_message;
+}
+
+WorkerMessage* QueryManagerSingleNode::getNextWorkerMessageFromActiveOperators(
+ const numa_node_id numa_node) {
+ WorkOrder *work_order = nullptr;
+ for (dag_node_index index : active_operators_) {
if (numa_node != kAnyNUMANodeID) {
// First try to get a normal WorkOrder from the specified NUMA node.
work_order = workorders_container_->getNormalWorkOrderForNUMANode(index, numa_node);
@@ -110,7 +142,6 @@ WorkerMessage* QueryManagerSingleNode::getNextWorkerMessage(
}
}
}
- // No WorkOrders available right now.
return nullptr;
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/13cf3955/query_execution/QueryManagerSingleNode.hpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryManagerSingleNode.hpp b/query_execution/QueryManagerSingleNode.hpp
index dd044a5..c00c31c 100644
--- a/query_execution/QueryManagerSingleNode.hpp
+++ b/query_execution/QueryManagerSingleNode.hpp
@@ -21,7 +21,9 @@
#define QUICKSTEP_QUERY_EXECUTION_QUERY_MANAGER_SINGLE_NODE_HPP_
#include <cstddef>
+#include <deque>
#include <memory>
+#include <vector>
#include "catalog/CatalogTypedefs.hpp"
#include "query_execution/QueryContext.hpp"
@@ -123,6 +125,16 @@ class QueryManagerSingleNode final : public QueryManagerBase {
void getRebuildWorkOrders(const dag_node_index index,
WorkOrdersContainer *container);
+ void activateOperator(const dag_node_index index) {
+ DCHECK(checkAllBlockingDependenciesMet(index));
+ // It is okay to call the line below multiple times.
+ query_dag_->getNodePayloadMutable(index)->informAllBlockingDependenciesMet();
+ processOperator(index, false);
+ }
+
+ WorkerMessage *getNextWorkerMessageFromActiveOperators(
+ const numa_node_id numa_node);
+
const tmb::client_id foreman_client_id_;
StorageManager *storage_manager_;
@@ -132,6 +144,10 @@ class QueryManagerSingleNode final : public QueryManagerBase {
std::unique_ptr<WorkOrdersContainer> workorders_container_;
+ std::vector<dag_node_index> active_operators_;
+
+ std::deque<dag_node_index> inactive_operators_;
+
DISALLOW_COPY_AND_ASSIGN(QueryManagerSingleNode);
};
[6/6] incubator-quickstep git commit: Configurable initial number of
active operators.
Posted by hb...@apache.org.
Configurable initial number of active operators.
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/1d486aef
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/1d486aef
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/1d486aef
Branch: refs/heads/delay-hashtable-memory-alloc
Commit: 1d486aefe1f9a5ffbaf23919923faea010174797
Parents: 13cf395
Author: Harshad Deshmukh <hb...@apache.org>
Authored: Mon Oct 31 23:24:40 2016 -0500
Committer: Harshad Deshmukh <hb...@apache.org>
Committed: Tue Nov 1 16:56:38 2016 -0500
----------------------------------------------------------------------
query_execution/QueryManagerSingleNode.cpp | 41 +++++++++++++++++--------
query_execution/QueryManagerSingleNode.hpp | 3 +-
2 files changed, 30 insertions(+), 14 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/1d486aef/query_execution/QueryManagerSingleNode.cpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryManagerSingleNode.cpp b/query_execution/QueryManagerSingleNode.cpp
index e77600f..1b211a9 100644
--- a/query_execution/QueryManagerSingleNode.cpp
+++ b/query_execution/QueryManagerSingleNode.cpp
@@ -60,8 +60,9 @@ QueryManagerSingleNode::QueryManagerSingleNode(
workorders_container_(
new WorkOrdersContainer(num_operators_in_dag_, num_numa_nodes)) {
// Mark the active operators in the DAG.
+ const std::size_t kNumMaxInitialActiveOperators = 2;
for (dag_node_index index = 0; index < num_operators_in_dag_; ++index) {
- if (checkAllBlockingDependenciesMet(index)) {
+ if (checkAllBlockingDependenciesMet(index) && active_operators_.size() < kNumMaxInitialActiveOperators) {
active_operators_.push_back(index);
activateOperator(index);
} else {
@@ -72,7 +73,6 @@ QueryManagerSingleNode::QueryManagerSingleNode(
WorkerMessage* QueryManagerSingleNode::getNextWorkerMessage(
const dag_node_index start_operator_index, const numa_node_id numa_node) {
- // Default policy: Operator with lowest index first.
WorkerMessage *worker_message = getNextWorkerMessageFromActiveOperators(numa_node);
if (worker_message != nullptr) {
return worker_message;
@@ -91,18 +91,35 @@ WorkerMessage* QueryManagerSingleNode::getNextWorkerMessage(
DCHECK(iter != active_operators_.end());
active_operators_.erase(iter);
}
- // Move some inactive operators to active operators.
- if (!inactive_operators_.empty()) {
- for (dag_node_index inactive_op_count = 0;
- inactive_op_count < execution_finished_operator_indexes.size();
- ++inactive_op_count) {
- if (checkAllBlockingDependenciesMet(inactive_operators_.front())) {
- active_operators_.push_back(inactive_operators_.front());
- inactive_operators_.pop_front();
- activateOperator(active_operators_.back());
- }
+ // Collect the list of "ready to be active" operators.
+ std::vector<dag_node_index> ready_to_be_active_operators;
+ for (dag_node_index index : inactive_operators_) {
+ if (checkAllBlockingDependenciesMet(index)) {
+ ready_to_be_active_operators.push_back(index);
}
}
+ // Move as many inactive operators to active operators, as the size of
+ // execution_finished_operator_indexes.
+ std::size_t num_operators_activated = 0;
+ if (!inactive_operators_.empty() &&
+ !execution_finished_operator_indexes.empty() &&
+ !ready_to_be_active_operators.empty()) {
+ for (; num_operators_activated <
+ std::min(execution_finished_operator_indexes.size(),
+ inactive_operators_.size());
+ ++num_operators_activated) {
+ active_operators_.push_back(ready_to_be_active_operators[num_operators_activated]);
+ activateOperator(active_operators_.back());
+ }
+ }
+ // Remove the newly activated operators.
+ for (std::size_t i = 0; i < num_operators_activated; ++i) {
+ auto iter = std::find(inactive_operators_.begin(),
+ inactive_operators_.end(),
+ ready_to_be_active_operators[i]);
+ DCHECK(iter != inactive_operators_.end());
+ inactive_operators_.erase(iter);
+ }
worker_message = getNextWorkerMessageFromActiveOperators(numa_node);
return worker_message;
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/1d486aef/query_execution/QueryManagerSingleNode.hpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryManagerSingleNode.hpp b/query_execution/QueryManagerSingleNode.hpp
index c00c31c..693684a 100644
--- a/query_execution/QueryManagerSingleNode.hpp
+++ b/query_execution/QueryManagerSingleNode.hpp
@@ -21,7 +21,6 @@
#define QUICKSTEP_QUERY_EXECUTION_QUERY_MANAGER_SINGLE_NODE_HPP_
#include <cstddef>
-#include <deque>
#include <memory>
#include <vector>
@@ -146,7 +145,7 @@ class QueryManagerSingleNode final : public QueryManagerBase {
std::vector<dag_node_index> active_operators_;
- std::deque<dag_node_index> inactive_operators_;
+ std::vector<dag_node_index> inactive_operators_;
DISALLOW_COPY_AND_ASSIGN(QueryManagerSingleNode);
};
[2/6] incubator-quickstep git commit: Method to get hash table memory
size from QueryContext
Posted by hb...@apache.org.
Method to get hash table memory size from QueryContext
- QueryContext now stores list of build hash operator IDs.
- While constructing the QueryContext, we also record the estimated
memory size of each join hash table.
- Given an operator ID of the build hash operator, the QueryContext
class can now provide the esimated memory size of the corresponding
hash table.
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/161259f3
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/161259f3
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/161259f3
Branch: refs/heads/delay-hashtable-memory-alloc
Commit: 161259f33ef5cf7ec19459bef5eee923680dd6ed
Parents: 584461a
Author: Harshad Deshmukh <hb...@apache.org>
Authored: Tue Nov 1 16:55:12 2016 -0500
Committer: Harshad Deshmukh <hb...@apache.org>
Committed: Tue Nov 1 16:56:38 2016 -0500
----------------------------------------------------------------------
query_execution/QueryContext.cpp | 17 +++++++++++++++++
query_execution/QueryContext.hpp | 4 ++++
storage/HashTableFactory.hpp | 19 ++++++++++++++-----
3 files changed, 35 insertions(+), 5 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/161259f3/query_execution/QueryContext.cpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryContext.cpp b/query_execution/QueryContext.cpp
index 0e6636d..154a767 100644
--- a/query_execution/QueryContext.cpp
+++ b/query_execution/QueryContext.cpp
@@ -19,6 +19,8 @@
#include "query_execution/QueryContext.hpp"
+#include <algorithm>
+#include <iterator>
#include <memory>
#include <unordered_map>
#include <utility>
@@ -82,6 +84,9 @@ QueryContext::QueryContext(const serialization::QueryContext &proto,
join_hash_tables_.emplace_back(
JoinHashTableFactory::CreateResizableFromProto(proto.join_hash_tables(i),
storage_manager));
+ join_hash_table_estimated_sizes_.emplace_back(
+ JoinHashTableFactory::GetHashTableEstimatedMemorySize(
+ proto.join_hash_tables(i)));
}
for (int i = 0; i < proto.insert_destinations_size(); ++i) {
@@ -263,4 +268,16 @@ bool QueryContext::ProtoIsValid(const serialization::QueryContext &proto,
return proto.IsInitialized();
}
+std::size_t QueryContext::getHashTableSize(const std::size_t operator_id) {
+ auto iter = std::find(build_hash_operator_ids_.begin(),
+ build_hash_operator_ids_.end(),
+ operator_id);
+ if (iter != build_hash_operator_ids_.end()) {
+ const std::size_t index = std::distance(build_hash_operator_ids_.begin(), iter);
+ DCHECK_LT(index, join_hash_tables_.size());
+ return join_hash_table_estimated_sizes_[index];
+ }
+ return 0;
+}
+
} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/161259f3/query_execution/QueryContext.hpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryContext.hpp b/query_execution/QueryContext.hpp
index 820cbb6..25ac724 100644
--- a/query_execution/QueryContext.hpp
+++ b/query_execution/QueryContext.hpp
@@ -566,6 +566,8 @@ class QueryContext {
return window_aggregation_states_[id].release();
}
+ std::size_t getHashTableSize(const std::size_t operator_id);
+
private:
std::vector<std::unique_ptr<AggregationOperationState>> aggregation_states_;
std::vector<std::unique_ptr<const GeneratorFunctionHandle>> generator_functions_;
@@ -584,6 +586,8 @@ class QueryContext {
// This vector has a 1-1 correspondence with join_hash_tables_ vector.
std::vector<dag_operator_id> build_hash_operator_ids_;
+ std::vector<std::size_t> join_hash_table_estimated_sizes_;
+
DISALLOW_COPY_AND_ASSIGN(QueryContext);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/161259f3/storage/HashTableFactory.hpp
----------------------------------------------------------------------
diff --git a/storage/HashTableFactory.hpp b/storage/HashTableFactory.hpp
index 58c4d82..ccca8e5 100644
--- a/storage/HashTableFactory.hpp
+++ b/storage/HashTableFactory.hpp
@@ -155,9 +155,14 @@ class HashTableFactory {
for (int i = 0; i < proto.key_types_size(); ++i) {
key_types.emplace_back(
&TypeFactory::ReconstructFromProto(proto.key_types(i)));
- } const std::size_t key_start_in_bucket_offset =
- HashTableKeyManager<serializable,
- force_key_copy>::GetKeyStartInBucketOffset();
+ }
+ const std::size_t key_start_in_bucket_offset =
+ LinearOpenAddressingHashTable<
+ ValueT,
+ resizable,
+ serializable,
+ force_key_copy,
+ allow_duplicate_keys>::GetKeyStartInBucketOffset();
std::vector<std::size_t> key_offsets;
const std::size_t fixed_key_size =
HashTableKeyManager<serializable, force_key_copy>::
@@ -178,8 +183,12 @@ class HashTableFactory {
&TypeFactory::ReconstructFromProto(proto.key_types(i)));
}
const std::size_t key_start_in_bucket_offset =
- HashTableKeyManager<serializable,
- force_key_copy>::GetKeyStartInBucketOffset();
+ SeparateChainingHashTable<
+ ValueT,
+ resizable,
+ serializable,
+ force_key_copy,
+ allow_duplicate_keys>::GetKeyStartInBucketOffset();
std::vector<std::size_t> key_offsets;
const std::size_t fixed_key_size =
HashTableKeyManager<serializable, force_key_copy>::
[5/6] incubator-quickstep git commit: Updates
Posted by hb...@apache.org.
Updates
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/584461ab
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/584461ab
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/584461ab
Branch: refs/heads/delay-hashtable-memory-alloc
Commit: 584461ab9539a13c316f928419842b2e60660b34
Parents: f54d1a2
Author: Harshad Deshmukh <hb...@apache.org>
Authored: Tue Nov 1 16:17:03 2016 -0500
Committer: Harshad Deshmukh <hb...@apache.org>
Committed: Tue Nov 1 16:56:38 2016 -0500
----------------------------------------------------------------------
query_execution/QueryContext.hpp | 9 +++++++++
query_execution/QueryContext.proto | 2 ++
query_optimizer/ExecutionGenerator.cpp | 3 +++
3 files changed, 14 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/584461ab/query_execution/QueryContext.hpp
----------------------------------------------------------------------
diff --git a/query_execution/QueryContext.hpp b/query_execution/QueryContext.hpp
index 7ad8fa1..820cbb6 100644
--- a/query_execution/QueryContext.hpp
+++ b/query_execution/QueryContext.hpp
@@ -133,6 +133,11 @@ class QueryContext {
typedef std::uint32_t window_aggregation_state_id;
/**
+ * @brief A unique identifier of a relational operator in the DAG.
+ **/
+ typedef std::uint32_t dag_operator_id;
+
+ /**
* @brief Constructor.
*
* @param proto A serialized Protocol Buffer representation of a
@@ -575,6 +580,10 @@ class QueryContext {
std::vector<std::unordered_map<attribute_id, std::unique_ptr<const Scalar>>> update_groups_;
std::vector<std::unique_ptr<WindowAggregationOperationState>> window_aggregation_states_;
+ // The IDs of the BuildHashOperator nodes in the query plan DAG.
+ // This vector has a 1-1 correspondence with join_hash_tables_ vector.
+ std::vector<dag_operator_id> build_hash_operator_ids_;
+
DISALLOW_COPY_AND_ASSIGN(QueryContext);
};
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/584461ab/query_execution/QueryContext.proto
----------------------------------------------------------------------
diff --git a/query_execution/QueryContext.proto b/query_execution/QueryContext.proto
index ab0f520..f8831db 100644
--- a/query_execution/QueryContext.proto
+++ b/query_execution/QueryContext.proto
@@ -62,4 +62,6 @@ message QueryContext {
repeated WindowAggregationOperationState window_aggregation_states = 12;
required uint64 query_id = 13;
+
+ repeated uint32 build_hash_operator_ids = 14;
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/584461ab/query_optimizer/ExecutionGenerator.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionGenerator.cpp b/query_optimizer/ExecutionGenerator.cpp
index 2e0d8f3..545f539 100644
--- a/query_optimizer/ExecutionGenerator.cpp
+++ b/query_optimizer/ExecutionGenerator.cpp
@@ -729,6 +729,9 @@ void ExecutionGenerator::convertHashJoin(const P::HashJoinPtr &physical_plan) {
any_build_attributes_nullable,
join_hash_table_index));
+ // Add the index of build operator to QueryContext.
+ query_context_proto_->add_build_hash_operator_ids(build_operator_index);
+
// Create InsertDestination proto.
const CatalogRelation *output_relation = nullptr;
const QueryContext::insert_destination_id insert_destination_index =
[3/6] incubator-quickstep git commit: Provide method to get estimated
size of hash table
Posted by hb...@apache.org.
Provide method to get estimated size of hash table
- Static API that doesn't need instantiation of the HashTable object.
- Supports LinearOpenAddressing, SeparateChaining and
SimpleScalarSeparateChaining hash table variants.
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/f54d1a2f
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/f54d1a2f
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/f54d1a2f
Branch: refs/heads/delay-hashtable-memory-alloc
Commit: f54d1a2f126c49a05584ccb616b9c770f019c357
Parents: 1d486ae
Author: Harshad Deshmukh <hb...@apache.org>
Authored: Tue Nov 1 14:42:11 2016 -0500
Committer: Harshad Deshmukh <hb...@apache.org>
Committed: Tue Nov 1 16:56:38 2016 -0500
----------------------------------------------------------------------
storage/HashTableFactory.hpp | 69 +++++++++++++++++
storage/HashTableKeyManager.hpp | 81 ++++++++++++++++++--
storage/LinearOpenAddressingHashTable.hpp | 16 ++--
storage/SeparateChainingHashTable.hpp | 19 +++--
.../SimpleScalarSeparateChainingHashTable.hpp | 4 +
5 files changed, 171 insertions(+), 18 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f54d1a2f/storage/HashTableFactory.hpp
----------------------------------------------------------------------
diff --git a/storage/HashTableFactory.hpp b/storage/HashTableFactory.hpp
index d690557..58c4d82 100644
--- a/storage/HashTableFactory.hpp
+++ b/storage/HashTableFactory.hpp
@@ -139,6 +139,75 @@ template <typename ValueT,
class HashTableFactory {
public:
/**
+ * @brief Find the estimated memory in bytes for the given hash table.
+ *
+ * @param proto A protobuf description of a HashTable.
+ *
+ * @return The estimated memory in bytes for the hash table.
+ **/
+ static std::size_t GetHashTableEstimatedMemorySize(
+ const serialization::HashTable &proto) {
+ auto hash_table_type =
+ HashTableImplTypeFromProto(proto.hash_table_impl_type());
+ switch (hash_table_type) {
+ case HashTableImplType::kLinearOpenAddressing: {
+ std::vector<const Type *> key_types;
+ for (int i = 0; i < proto.key_types_size(); ++i) {
+ key_types.emplace_back(
+ &TypeFactory::ReconstructFromProto(proto.key_types(i)));
+ } const std::size_t key_start_in_bucket_offset =
+ HashTableKeyManager<serializable,
+ force_key_copy>::GetKeyStartInBucketOffset();
+ std::vector<std::size_t> key_offsets;
+ const std::size_t fixed_key_size =
+ HashTableKeyManager<serializable, force_key_copy>::
+ CalculateFixedKeySize(
+ key_types, key_start_in_bucket_offset, &key_offsets);
+ return proto.estimated_num_entries() *
+ LinearOpenAddressingHashTable<
+ ValueT,
+ resizable,
+ serializable,
+ force_key_copy,
+ allow_duplicate_keys>::ComputeBucketSize(fixed_key_size);
+ }
+ case HashTableImplType::kSeparateChaining: {
+ std::vector<const Type*> key_types;
+ for (int i = 0; i < proto.key_types_size(); ++i) {
+ key_types.emplace_back(
+ &TypeFactory::ReconstructFromProto(proto.key_types(i)));
+ }
+ const std::size_t key_start_in_bucket_offset =
+ HashTableKeyManager<serializable,
+ force_key_copy>::GetKeyStartInBucketOffset();
+ std::vector<std::size_t> key_offsets;
+ const std::size_t fixed_key_size =
+ HashTableKeyManager<serializable, force_key_copy>::
+ CalculateFixedKeySize(
+ key_types, key_start_in_bucket_offset, &key_offsets);
+ return proto.estimated_num_entries() *
+ SeparateChainingHashTable<
+ ValueT,
+ resizable,
+ serializable,
+ force_key_copy,
+ allow_duplicate_keys>::ComputeBucketSize(fixed_key_size);
+ }
+ case HashTableImplType::kSimpleScalarSeparateChaining:
+ return proto.estimated_num_entries() *
+ SimpleScalarSeparateChainingHashTable<
+ ValueT,
+ resizable,
+ serializable,
+ force_key_copy,
+ allow_duplicate_keys>::GetBucketSize();
+ default: {
+ LOG(FATAL) << "Unrecognized HashTableImplType in HashTableFactory::createResizable()\n";
+ }
+ }
+ }
+
+ /**
* @brief Create a new resizable HashTable, with the type selected by
* hash_table_type. Other parameters are forwarded to the HashTable's
* constructor.
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f54d1a2f/storage/HashTableKeyManager.hpp
----------------------------------------------------------------------
diff --git a/storage/HashTableKeyManager.hpp b/storage/HashTableKeyManager.hpp
index 0295ad4..db68d98 100644
--- a/storage/HashTableKeyManager.hpp
+++ b/storage/HashTableKeyManager.hpp
@@ -62,6 +62,50 @@ template <bool serializable, bool force_key_copy>
class HashTableKeyManager {
public:
/**
+ * @brief Calculate the fixed key size for the hash table.
+ *
+ * @param key_types A vector of pointers to the Types of key components for
+ * a HashTable.
+ * @param key_start_in_bucket The position in the HashTable's buckets where
+ * storage for keys begins, measured as the number of bytes from the
+ * start of the bucket.
+ * @param key_offsets The offsets of the keys with respect to the beginning.
+ *
+ * @return The fixed key size for the HashTable.
+ **/
+ static std::size_t CalculateFixedKeySize(
+ const std::vector<const Type *> &key_types,
+ const std::size_t key_start_in_bucket,
+ std::vector<std::size_t> *key_offsets) {
+ DCHECK(!key_types.empty());
+ DCHECK_NOTNULL(key_offsets);
+ std::size_t fixed_key_size = 0;
+
+ for (const Type *subkey_type : key_types) {
+ key_offsets->push_back(key_start_in_bucket + fixed_key_size);
+
+ if (force_key_copy) {
+ if (subkey_type->isVariableLength()) {
+ fixed_key_size += sizeof(std::size_t) * 2;
+ } else {
+ fixed_key_size += subkey_type->maximumByteLength();
+ }
+ } else {
+ constexpr std::size_t ptr_size = serializable ? sizeof(std::ptrdiff_t)
+ : sizeof(const void*);
+ if ((!subkey_type->isVariableLength())
+ && (subkey_type->maximumByteLength() <= ptr_size + sizeof(std::size_t))) {
+ fixed_key_size += subkey_type->maximumByteLength();
+ } else {
+ // A pointer to external memory, paired with a length.
+ fixed_key_size += ptr_size + sizeof(std::size_t);
+ }
+ }
+ }
+ return fixed_key_size;
+ }
+
+ /**
* @brief Constructor.
*
* @param key_types A vector of pointers to the Types of key components for
@@ -308,17 +352,44 @@ HashTableKeyManager<serializable, force_key_copy>::HashTableKeyManager(
next_variable_length_key_offset_(0) {
DCHECK(!key_types_.empty());
- for (const Type *subkey_type : key_types_) {
- key_offsets_.push_back(key_start_in_bucket + fixed_key_size_);
+ switch(serializable) {
+ case true:
+ switch(force_key_copy) {
+ case true:
+ fixed_key_size_ =
+ HashTableKeyManager<true, true>::CalculateFixedKeySize(
+ key_types, key_start_in_bucket, &key_offsets_);
+ break;
+ case false:
+ fixed_key_size_ =
+ HashTableKeyManager<true, false>::CalculateFixedKeySize(
+ key_types, key_start_in_bucket, &key_offsets_);
+ break;
+ }
+ break;
+ case false:
+ switch(force_key_copy) {
+ case true:
+ fixed_key_size_ =
+ HashTableKeyManager<false, true>::CalculateFixedKeySize(
+ key_types, key_start_in_bucket, &key_offsets_);
+ break;
+ case false:
+ fixed_key_size_ =
+ HashTableKeyManager<false, false>::CalculateFixedKeySize(
+ key_types, key_start_in_bucket, &key_offsets_);
+ break;
+ }
+ break;
+ }
+ for (const Type *subkey_type : key_types_) {
if (force_key_copy) {
if (subkey_type->isVariableLength()) {
// An offset into the variable length storage region, paired with a length.
- fixed_key_size_ += sizeof(std::size_t) * 2;
estimated_variable_key_size_ += subkey_type->estimateAverageByteLength();
key_inline_.push_back(false);
} else {
- fixed_key_size_ += subkey_type->maximumByteLength();
key_inline_.push_back(true);
}
} else {
@@ -326,11 +397,9 @@ HashTableKeyManager<serializable, force_key_copy>::HashTableKeyManager(
: sizeof(const void*);
if ((!subkey_type->isVariableLength())
&& (subkey_type->maximumByteLength() <= ptr_size + sizeof(std::size_t))) {
- fixed_key_size_ += subkey_type->maximumByteLength();
key_inline_.push_back(true);
} else {
// A pointer to external memory, paired with a length.
- fixed_key_size_ += ptr_size + sizeof(std::size_t);
key_inline_.push_back(false);
}
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f54d1a2f/storage/LinearOpenAddressingHashTable.hpp
----------------------------------------------------------------------
diff --git a/storage/LinearOpenAddressingHashTable.hpp b/storage/LinearOpenAddressingHashTable.hpp
index 4953b4d..4a6d63e 100644
--- a/storage/LinearOpenAddressingHashTable.hpp
+++ b/storage/LinearOpenAddressingHashTable.hpp
@@ -71,6 +71,16 @@ class LinearOpenAddressingHashTable : public HashTable<ValueT,
static constexpr std::size_t kPendingHash
= HashTable<ValueT, resizable, serializable, force_key_copy, allow_duplicate_keys>::kPendingHash;
+ // Round bucket size up to a multiple of kBucketAlignment.
+ static constexpr std::size_t ComputeBucketSize(const std::size_t fixed_key_size) {
+ return (((kValueOffset + sizeof(ValueT) + fixed_key_size - 1) / kBucketAlignment) + 1)
+ * kBucketAlignment;
+ }
+
+ static constexpr std::size_t GetKeyStartInBucketOffset() {
+ return kValueOffset + sizeof(ValueT);
+ }
+
LinearOpenAddressingHashTable(const std::vector<const Type*> &key_types,
const std::size_t num_entries,
StorageManager *storage_manager);
@@ -211,12 +221,6 @@ class LinearOpenAddressingHashTable : public HashTable<ValueT,
static constexpr std::size_t kValueOffset
= (((sizeof(std::atomic<std::size_t>) - 1) / alignof(ValueT)) + 1) * alignof(ValueT);
- // Round bucket size up to a multiple of kBucketAlignment.
- static constexpr std::size_t ComputeBucketSize(const std::size_t fixed_key_size) {
- return (((kValueOffset + sizeof(ValueT) + fixed_key_size - 1) / kBucketAlignment) + 1)
- * kBucketAlignment;
- }
-
// Attempt to find an empty bucket to insert 'hash_code' into, starting from
// '*bucket_num'. Returns true and stores kPendingHash in bucket if an empty
// bucket is found. Returns false if 'allow_duplicate_keys' is false and a
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f54d1a2f/storage/SeparateChainingHashTable.hpp
----------------------------------------------------------------------
diff --git a/storage/SeparateChainingHashTable.hpp b/storage/SeparateChainingHashTable.hpp
index 3ca060d..e696464 100644
--- a/storage/SeparateChainingHashTable.hpp
+++ b/storage/SeparateChainingHashTable.hpp
@@ -63,6 +63,19 @@ class SeparateChainingHashTable : public HashTable<ValueT,
force_key_copy,
allow_duplicate_keys> {
public:
+ // Round bucket size up to a multiple of kBucketAlignment.
+ static constexpr std::size_t ComputeBucketSize(
+ const std::size_t fixed_key_size) {
+ return (((kValueOffset + sizeof(ValueT) + fixed_key_size - 1) /
+ kBucketAlignment) +
+ 1) *
+ kBucketAlignment;
+ }
+
+ static constexpr std::size_t GetKeyStartInBucketOffset() {
+ return kValueOffset + sizeof(ValueT);
+ }
+
SeparateChainingHashTable(const std::vector<const Type*> &key_types,
const std::size_t num_entries,
StorageManager *storage_manager);
@@ -188,12 +201,6 @@ class SeparateChainingHashTable : public HashTable<ValueT,
static constexpr std::size_t kValueOffset
= (((sizeof(std::atomic<std::size_t>) + sizeof(std::size_t) - 1) / alignof(ValueT)) + 1) * alignof(ValueT);
- // Round bucket size up to a multiple of kBucketAlignment.
- static constexpr std::size_t ComputeBucketSize(const std::size_t fixed_key_size) {
- return (((kValueOffset + sizeof(ValueT) + fixed_key_size - 1) / kBucketAlignment) + 1)
- * kBucketAlignment;
- }
-
// If ValueT is not trivially destructible, invoke its destructor for all
// values held in the specified buckets (including those in "empty" buckets
// that were default constructed). If ValueT is trivially destructible, this
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/f54d1a2f/storage/SimpleScalarSeparateChainingHashTable.hpp
----------------------------------------------------------------------
diff --git a/storage/SimpleScalarSeparateChainingHashTable.hpp b/storage/SimpleScalarSeparateChainingHashTable.hpp
index 8448896..d527aeb 100644
--- a/storage/SimpleScalarSeparateChainingHashTable.hpp
+++ b/storage/SimpleScalarSeparateChainingHashTable.hpp
@@ -77,6 +77,10 @@ class SimpleScalarSeparateChainingHashTable : public HashTable<ValueT,
force_key_copy,
allow_duplicate_keys> {
public:
+ static const std::size_t GetBucketSize() {
+ return sizeof(Bucket);
+ }
+
SimpleScalarSeparateChainingHashTable(const std::vector<const Type*> &key_types,
const std::size_t num_entries,
StorageManager *storage_manager);