You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by ji...@apache.org on 2017/12/11 22:07:45 UTC
[06/11] incubator-quickstep git commit: Initialize updates for
transitive closure
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/relational_operators/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/relational_operators/CMakeLists.txt b/relational_operators/CMakeLists.txt
index 7b9ed96..6cc7f08 100644
--- a/relational_operators/CMakeLists.txt
+++ b/relational_operators/CMakeLists.txt
@@ -38,6 +38,9 @@ add_library(quickstep_relationaloperators_BuildAggregationExistenceMapOperator
BuildAggregationExistenceMapOperator.hpp)
add_library(quickstep_relationaloperators_BuildHashOperator BuildHashOperator.cpp BuildHashOperator.hpp)
add_library(quickstep_relationaloperators_BuildLIPFilterOperator BuildLIPFilterOperator.cpp BuildLIPFilterOperator.hpp)
+add_library(quickstep_relationaloperators_BuildTransitiveClosureOperator
+ BuildTransitiveClosureOperator.cpp
+ BuildTransitiveClosureOperator.hpp)
add_library(quickstep_relationaloperators_CreateIndexOperator ../empty_src.cpp CreateIndexOperator.hpp)
add_library(quickstep_relationaloperators_CreateTableOperator ../empty_src.cpp CreateTableOperator.hpp)
add_library(quickstep_relationaloperators_DestroyAggregationStateOperator
@@ -53,6 +56,9 @@ add_library(quickstep_relationaloperators_HashJoinOperator HashJoinOperator.cpp
add_library(quickstep_relationaloperators_InitializeAggregationOperator
InitializeAggregationOperator.cpp
InitializeAggregationOperator.hpp)
+add_library(quickstep_relationaloperators_InitializeTransitiveClosureOperator
+ InitializeTransitiveClosureOperator.cpp
+ InitializeTransitiveClosureOperator.hpp)
add_library(quickstep_relationaloperators_InsertOperator InsertOperator.cpp InsertOperator.hpp)
add_library(quickstep_relationaloperators_NestedLoopsJoinOperator
NestedLoopsJoinOperator.cpp
@@ -73,6 +79,9 @@ add_library(quickstep_relationaloperators_SortRunGenerationOperator SortRunGener
SortRunGenerationOperator.hpp)
add_library(quickstep_relationaloperators_TableExportOperator TableExportOperator.cpp TableExportOperator.hpp)
add_library(quickstep_relationaloperators_TableGeneratorOperator TableGeneratorOperator.cpp TableGeneratorOperator.hpp)
+add_library(quickstep_relationaloperators_TransitiveClosureOperator
+ TransitiveClosureOperator.cpp
+ TransitiveClosureOperator.hpp)
add_library(quickstep_relationaloperators_TextScanOperator TextScanOperator.cpp TextScanOperator.hpp)
add_library(quickstep_relationaloperators_UnionAllOperator UnionAllOperator.cpp UnionAllOperator.hpp)
add_library(quickstep_relationaloperators_UpdateOperator UpdateOperator.cpp UpdateOperator.hpp)
@@ -171,6 +180,28 @@ target_link_libraries(quickstep_relationaloperators_BuildLIPFilterOperator
quickstep_utility_lipfilter_LIPFilterBuilder
quickstep_utility_lipfilter_LIPFilterUtil
tmb)
+target_link_libraries(quickstep_relationaloperators_BuildTransitiveClosureOperator
+ glog
+ quickstep_catalog_CatalogRelation
+ quickstep_catalog_CatalogTypedefs
+ quickstep_cli_Flags
+ quickstep_queryexecution_QueryContext
+ quickstep_queryexecution_WorkOrderProtosContainer
+ quickstep_queryexecution_WorkOrdersContainer
+ quickstep_relationaloperators_RelationalOperator
+ quickstep_relationaloperators_WorkOrder
+ quickstep_relationaloperators_WorkOrder_proto
+ quickstep_storage_StorageBlock
+ quickstep_storage_StorageBlockInfo
+ quickstep_storage_StorageManager
+ quickstep_storage_TransitiveClosureState
+ quickstep_storage_TupleStorageSubBlock
+ quickstep_storage_ValueAccessor
+ quickstep_storage_ValueAccessorUtil
+ quickstep_utility_BlockIDStream
+ quickstep_utility_Macros
+ quickstep_utility_Range
+ tmb)
target_link_libraries(quickstep_relationaloperators_CreateIndexOperator
glog
quickstep_catalog_CatalogRelation
@@ -304,6 +335,20 @@ target_link_libraries(quickstep_relationaloperators_InitializeAggregationOperato
quickstep_storage_AggregationOperationState
quickstep_utility_Macros
tmb)
+target_link_libraries(quickstep_relationaloperators_InitializeTransitiveClosureOperator
+ glog
+ quickstep_cli_Flags
+ quickstep_queryexecution_QueryContext
+ quickstep_queryexecution_WorkOrderProtosContainer
+ quickstep_queryexecution_WorkOrdersContainer
+ quickstep_relationaloperators_RelationalOperator
+ quickstep_relationaloperators_WorkOrder
+ quickstep_relationaloperators_WorkOrder_proto
+ quickstep_storage_StorageBlockInfo
+ quickstep_storage_TransitiveClosureState
+ quickstep_utility_Macros
+ quickstep_utility_Range
+ tmb)
target_link_libraries(quickstep_relationaloperators_InsertOperator
glog
quickstep_catalog_CatalogRelation
@@ -537,6 +582,17 @@ if (QUICKSTEP_HAVE_FILE_MANAGER_HDFS)
target_link_libraries(quickstep_relationaloperators_TextScanOperator
${LIBHDFS3_LIBRARIES})
endif(QUICKSTEP_HAVE_FILE_MANAGER_HDFS)
+target_link_libraries(quickstep_relationaloperators_TransitiveClosureOperator
+ glog
+ quickstep_catalog_CatalogRelation
+ quickstep_queryexecution_QueryContext
+ quickstep_relationaloperators_RelationalOperator
+ quickstep_relationaloperators_WorkOrder
+ quickstep_storage_StorageBlockInfo
+ quickstep_storage_TransitiveClosureState
+ quickstep_utility_Macros
+ quickstep_utility_Range
+ tmb)
target_link_libraries(quickstep_relationaloperators_UnionAllOperator
glog
quickstep_catalog_CatalogRelation
@@ -639,6 +695,7 @@ target_link_libraries(quickstep_relationaloperators
quickstep_relationaloperators_BuildAggregationExistenceMapOperator
quickstep_relationaloperators_BuildLIPFilterOperator
quickstep_relationaloperators_BuildHashOperator
+ quickstep_relationaloperators_BuildTransitiveClosureOperator
quickstep_relationaloperators_CreateIndexOperator
quickstep_relationaloperators_CreateTableOperator
quickstep_relationaloperators_DeleteOperator
@@ -648,6 +705,7 @@ target_link_libraries(quickstep_relationaloperators
quickstep_relationaloperators_FinalizeAggregationOperator
quickstep_relationaloperators_HashJoinOperator
quickstep_relationaloperators_InitializeAggregationOperator
+ quickstep_relationaloperators_InitializeTransitiveClosureOperator
quickstep_relationaloperators_InsertOperator
quickstep_relationaloperators_NestedLoopsJoinOperator
quickstep_relationaloperators_RebuildWorkOrder
@@ -662,6 +720,7 @@ target_link_libraries(quickstep_relationaloperators
quickstep_relationaloperators_TableExportOperator
quickstep_relationaloperators_TableGeneratorOperator
quickstep_relationaloperators_TextScanOperator
+ quickstep_relationaloperators_TransitiveClosureOperator
quickstep_relationaloperators_UnionAllOperator
quickstep_relationaloperators_UpdateOperator
quickstep_relationaloperators_WindowAggregationOperator
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/relational_operators/InitializeTransitiveClosureOperator.cpp
----------------------------------------------------------------------
diff --git a/relational_operators/InitializeTransitiveClosureOperator.cpp b/relational_operators/InitializeTransitiveClosureOperator.cpp
new file mode 100644
index 0000000..a6ffe6f
--- /dev/null
+++ b/relational_operators/InitializeTransitiveClosureOperator.cpp
@@ -0,0 +1,87 @@
+/**
+ * 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 "relational_operators/InitializeTransitiveClosureOperator.hpp"
+
+#include <algorithm>
+#include <cstddef>
+
+#include "cli/Flags.hpp"
+#include "query_execution/QueryContext.hpp"
+#include "query_execution/WorkOrderProtosContainer.hpp"
+#include "query_execution/WorkOrdersContainer.hpp"
+#include "relational_operators/WorkOrder.pb.h"
+#include "storage/TransitiveClosureState.hpp"
+#include "utility/Range.hpp"
+
+#include "glog/logging.h"
+
+#include "tmb/id_typedefs.h"
+
+namespace quickstep {
+
+bool InitializeTransitiveClosureOperator::getAllWorkOrders(
+ WorkOrdersContainer *container,
+ QueryContext *query_context,
+ StorageManager *storage_manager,
+ const tmb::client_id scheduler_client_id,
+ tmb::MessageBus *bus) {
+ if (started_) {
+ return true;
+ }
+
+ TransitiveClosureState *state =
+ query_context->getTransitiveClosureState(transitive_closure_context_index_);
+
+ constexpr std::size_t kMinBatchSize = 1024ul * 1024ul * 4ul;
+ const std::size_t range = state->range();
+ const std::size_t num_batches =
+ std::max(1ul, std::min(range * range / kMinBatchSize,
+ static_cast<std::size_t>(FLAGS_num_workers)));
+
+ const RangeSplitter splitter =
+ RangeSplitter::CreateWithNumPartitions(0, range, num_batches);
+
+ for (std::size_t i = 0; i < splitter.getNumPartitions(); ++i) {
+ container->addNormalWorkOrder(
+ new InitializeTransitiveClosureWorkOrder(query_id_,
+ splitter.getPartition(i),
+ state),
+ op_index_);
+ }
+
+ started_ = true;
+ return true;
+}
+
+bool InitializeTransitiveClosureOperator::getAllWorkOrderProtos(
+ WorkOrderProtosContainer *container) {
+ LOG(FATAL) << "Not supported";
+}
+
+void InitializeTransitiveClosureWorkOrder::execute() {
+ if (range_.begin() == 0) {
+ state_->initializeStart();
+ }
+ for (std::size_t i = range_.begin(); i < range_.end(); ++i) {
+ state_->initializeEdgeComponent(i);
+ }
+}
+
+} // namespace quickstep
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/relational_operators/InitializeTransitiveClosureOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/InitializeTransitiveClosureOperator.hpp b/relational_operators/InitializeTransitiveClosureOperator.hpp
new file mode 100644
index 0000000..1694620
--- /dev/null
+++ b/relational_operators/InitializeTransitiveClosureOperator.hpp
@@ -0,0 +1,109 @@
+/**
+ * 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_RELATIONAL_OPERATORS_INITIALIZE_TRANSITIVE_CLOSURE_OPERATOR_HPP_
+#define QUICKSTEP_RELATIONAL_OPERATORS_INITIALIZE_TRANSITIVE_CLOSURE_OPERATOR_HPP_
+
+#include <cstddef>
+#include <string>
+#include <vector>
+
+#include "query_execution/QueryContext.hpp"
+#include "relational_operators/RelationalOperator.hpp"
+#include "relational_operators/WorkOrder.hpp"
+#include "storage/StorageBlockInfo.hpp"
+#include "storage/TransitiveClosureState.hpp"
+#include "utility/Macros.hpp"
+#include "utility/Range.hpp"
+
+#include "glog/logging.h"
+
+#include "tmb/id_typedefs.h"
+
+namespace tmb { class MessageBus; }
+
+namespace quickstep {
+
+class StorageManager;
+class WorkOrderProtosContainer;
+class WorkOrdersContainer;
+
+/** \addtogroup RelationalOperators
+ * @{
+ */
+
+class InitializeTransitiveClosureOperator : public RelationalOperator {
+ public:
+ InitializeTransitiveClosureOperator(const std::size_t query_id,
+ const std::size_t transitive_closure_context_index)
+ : RelationalOperator(query_id, 1u),
+ transitive_closure_context_index_(transitive_closure_context_index),
+ started_(false) {
+ }
+
+ ~InitializeTransitiveClosureOperator() override {}
+
+ OperatorType getOperatorType() const override {
+ return kInitializeTransitiveClosure;
+ }
+
+ std::string getName() const override {
+ return "InitializeTransitiveClosureOperator";
+ }
+
+ bool getAllWorkOrders(WorkOrdersContainer *container,
+ QueryContext *query_context,
+ StorageManager *storage_manager,
+ const tmb::client_id scheduler_client_id,
+ tmb::MessageBus *bus) override;
+
+ bool getAllWorkOrderProtos(WorkOrderProtosContainer *container) override;
+
+ private:
+ const std::size_t transitive_closure_context_index_;
+ bool started_;
+
+ DISALLOW_COPY_AND_ASSIGN(InitializeTransitiveClosureOperator);
+};
+
+class InitializeTransitiveClosureWorkOrder : public WorkOrder {
+ public:
+ InitializeTransitiveClosureWorkOrder(const std::size_t query_id,
+ const Range &range,
+ TransitiveClosureState *state)
+ : WorkOrder(query_id, 1u),
+ range_(range),
+ state_(state) {}
+
+ ~InitializeTransitiveClosureWorkOrder() override {}
+
+ void execute() override;
+
+ private:
+ const Range range_;
+ TransitiveClosureState *state_;
+
+ DISALLOW_COPY_AND_ASSIGN(InitializeTransitiveClosureWorkOrder);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_RELATIONAL_OPERATORS_INITIALIZE_TRANSITIVE_CLOSURE_OPERATOR_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/relational_operators/RelationalOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/RelationalOperator.hpp b/relational_operators/RelationalOperator.hpp
index 8eb59f0..d0c7c50 100644
--- a/relational_operators/RelationalOperator.hpp
+++ b/relational_operators/RelationalOperator.hpp
@@ -67,6 +67,7 @@ class RelationalOperator {
kBuildAggregationExistenceMap,
kBuildHash,
kBuildLIPFilter,
+ kBuildTransitiveClosure,
kCreateIndex,
kCreateTable,
kDelete,
@@ -75,6 +76,7 @@ class RelationalOperator {
kDropTable,
kFinalizeAggregation,
kInitializeAggregation,
+ kInitializeTransitiveClosure,
kInnerJoin,
kInsert,
kLeftAntiJoin,
@@ -89,6 +91,7 @@ class RelationalOperator {
kTableExport,
kTableGenerator,
kTextScan,
+ kTransitiveClosure,
kUnionAll,
kUpdate,
kWindowAggregation,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/relational_operators/TransitiveClosureOperator.cpp
----------------------------------------------------------------------
diff --git a/relational_operators/TransitiveClosureOperator.cpp b/relational_operators/TransitiveClosureOperator.cpp
new file mode 100644
index 0000000..e69de29
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/relational_operators/TransitiveClosureOperator.hpp
----------------------------------------------------------------------
diff --git a/relational_operators/TransitiveClosureOperator.hpp b/relational_operators/TransitiveClosureOperator.hpp
new file mode 100644
index 0000000..f983a4a
--- /dev/null
+++ b/relational_operators/TransitiveClosureOperator.hpp
@@ -0,0 +1,57 @@
+/**
+ * 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_RELATIONAL_OPERATORS_TRANSITIVE_CLOSURE_OPERATOR_HPP_
+#define QUICKSTEP_RELATIONAL_OPERATORS_TRANSITIVE_CLOSURE_OPERATOR_HPP_
+
+#include <cstddef>
+#include <string>
+#include <vector>
+
+#include "catalog/CatalogRelation.hpp"
+#include "query_execution/QueryContext.hpp"
+#include "relational_operators/RelationalOperator.hpp"
+#include "relational_operators/WorkOrder.hpp"
+#include "storage/StorageBlockInfo.hpp"
+#include "storage/TransitiveClosureState.hpp"
+#include "utility/Macros.hpp"
+#include "utility/Range.hpp"
+
+#include "glog/logging.h"
+
+#include "tmb/id_typedefs.h"
+
+namespace tmb { class MessageBus; }
+
+namespace quickstep {
+
+class StorageManager;
+class WorkOrderProtosContainer;
+class WorkOrdersContainer;
+
+/** \addtogroup RelationalOperators
+ * @{
+ */
+
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_RELATIONAL_OPERATORS_INITIALIZE_TRANSITIVE_CLOSURE_OPERATOR_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/storage/AggregationOperationState.hpp
----------------------------------------------------------------------
diff --git a/storage/AggregationOperationState.hpp b/storage/AggregationOperationState.hpp
index ae14dd1..ee782cc 100644
--- a/storage/AggregationOperationState.hpp
+++ b/storage/AggregationOperationState.hpp
@@ -17,8 +17,8 @@
* under the License.
**/
-#ifndef QUICKSTEP_RELATIONAL_OPERATORS_AGGREGATION_OPERATION_HPP_
-#define QUICKSTEP_RELATIONAL_OPERATORS_AGGREGATION_OPERATION_HPP_
+#ifndef QUICKSTEP_STORAGE_AGGREGATION_OPERATION_STATE_HPP_
+#define QUICKSTEP_STORAGE_AGGREGATION_OPERATION_STATE_HPP_
#include <cstddef>
#include <memory>
@@ -334,4 +334,4 @@ class AggregationOperationState {
} // namespace quickstep
-#endif // QUICKSTEP_RELATIONAL_OPERATORS_AGGREGATION_OPERATION_HPP_
+#endif // QUICKSTEP_STORAGE_AGGREGATION_OPERATION_STATE_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/storage/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/storage/CMakeLists.txt b/storage/CMakeLists.txt
index 8ac7285..4699244 100644
--- a/storage/CMakeLists.txt
+++ b/storage/CMakeLists.txt
@@ -256,6 +256,7 @@ add_library(quickstep_storage_SubBlocksReference ../empty_src.cpp SubBlocksRefer
add_library(quickstep_storage_ThreadPrivateCompactKeyHashTable
ThreadPrivateCompactKeyHashTable.cpp
ThreadPrivateCompactKeyHashTable.hpp)
+add_library(quickstep_storage_TransitiveClosureState TransitiveClosureState.cpp TransitiveClosureState.hpp)
add_library(quickstep_storage_TupleIdSequence ../empty_src.cpp TupleIdSequence.hpp)
add_library(quickstep_storage_TupleReference ../empty_src.cpp TupleReference.hpp)
add_library(quickstep_storage_TupleStorageSubBlock TupleStorageSubBlock.cpp TupleStorageSubBlock.hpp)
@@ -1087,6 +1088,9 @@ target_link_libraries(quickstep_storage_ThreadPrivateCompactKeyHashTable
quickstep_types_containers_ColumnVectorsValueAccessor
quickstep_utility_Macros
quickstep_utility_ScopedBuffer)
+target_link_libraries(quickstep_storage_TransitiveClosureState
+ quickstep_utility_BarrieredReadWriteConcurrentBitVector
+ quickstep_utility_Macros)
target_link_libraries(quickstep_storage_TupleIdSequence
glog
quickstep_storage_StorageBlockInfo
@@ -1215,6 +1219,7 @@ target_link_libraries(quickstep_storage
quickstep_storage_SubBlockTypeRegistryMacros
quickstep_storage_SubBlocksReference
quickstep_storage_ThreadPrivateCompactKeyHashTable
+ quickstep_storage_TransitiveClosureState
quickstep_storage_TupleIdSequence
quickstep_storage_TupleReference
quickstep_storage_TupleStorageSubBlock
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/storage/TransitiveClosureState.cpp
----------------------------------------------------------------------
diff --git a/storage/TransitiveClosureState.cpp b/storage/TransitiveClosureState.cpp
new file mode 100644
index 0000000..e69de29
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/storage/TransitiveClosureState.hpp
----------------------------------------------------------------------
diff --git a/storage/TransitiveClosureState.hpp b/storage/TransitiveClosureState.hpp
new file mode 100644
index 0000000..852972a
--- /dev/null
+++ b/storage/TransitiveClosureState.hpp
@@ -0,0 +1,82 @@
+/**
+ * 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_STORAGE_TRANSITIVE_CLOSURE_STATE_HPP_
+#define QUICKSTEP_STORAGE_TRANSITIVE_CLOSURE_STATE_HPP_
+
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <vector>
+
+#include "utility/BarrieredReadWriteConcurrentBitVector.hpp"
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/** \addtogroup Storage
+ * @{
+ */
+
+class TransitiveClosureState {
+ public:
+ explicit TransitiveClosureState(const int range)
+ : range_(range),
+ edges_(range_) {
+ }
+
+ int range() const {
+ return range_;
+ }
+
+ void initializeStart() {
+ DCHECK(starts_ == nullptr);
+ starts_ = std::make_unique<BarrieredReadWriteConcurrentBitVector>(range_);
+ }
+
+ void initializeEdgeComponent(const int source) {
+ DCHECK(edges_[source] == nullptr);
+ edges_[source] = std::make_unique<BarrieredReadWriteConcurrentBitVector>(range_);
+ }
+
+ inline void addStart(const int value) {
+ if (value < range_) {
+ starts_->setBit(value);
+ }
+ }
+
+ inline void addEdge(const int source, const int destination) {
+ DCHECK_LT(source, range_);
+ DCHECK_LT(destination, range_);
+ edges_[source]->setBit(destination);
+ }
+
+ private:
+ const int range_;
+ std::unique_ptr<BarrieredReadWriteConcurrentBitVector> starts_;
+ std::vector<std::unique_ptr<BarrieredReadWriteConcurrentBitVector>> edges_;
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_STORAGE_TRANSITIVE_CLOSURE_STATE_HPP_
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/utility/BarrieredReadWriteConcurrentBitVector.hpp
----------------------------------------------------------------------
diff --git a/utility/BarrieredReadWriteConcurrentBitVector.hpp b/utility/BarrieredReadWriteConcurrentBitVector.hpp
index 0086c7f..1dcb58e 100644
--- a/utility/BarrieredReadWriteConcurrentBitVector.hpp
+++ b/utility/BarrieredReadWriteConcurrentBitVector.hpp
@@ -131,6 +131,7 @@ class BarrieredReadWriteConcurrentBitVector {
* @return The value of the bit at bit_num.
**/
inline bool getBit(const std::size_t bit_num) const {
+ DCHECK_LT(bit_num, num_bits_);
const std::size_t data_value =
data_array_[bit_num >> kHigherOrderShift].load(std::memory_order_relaxed);
return (data_value << (bit_num & kLowerOrderMask)) & kTopBit;
@@ -143,6 +144,7 @@ class BarrieredReadWriteConcurrentBitVector {
* @param value The new value to set for the bit at bit_num.
**/
inline void setBit(const std::size_t bit_num) const {
+ DCHECK_LT(bit_num, num_bits_);
data_array_[bit_num >> kHigherOrderShift].fetch_or(
kTopBit >> (bit_num & kLowerOrderMask), std::memory_order_relaxed);
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/utility/BlockIDStream.hpp
----------------------------------------------------------------------
diff --git a/utility/BlockIDStream.hpp b/utility/BlockIDStream.hpp
new file mode 100644
index 0000000..20205cc
--- /dev/null
+++ b/utility/BlockIDStream.hpp
@@ -0,0 +1,83 @@
+/**
+ * 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_UTILITY_BLOCK_ID_STREAM_HPP_
+#define QUICKSTEP_UTILITY_BLOCK_ID_STREAM_HPP_
+
+#include <cstddef>
+#include <vector>
+
+#include "catalog/CatalogRelation.hpp"
+#include "storage/StorageBlockInfo.hpp"
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/** \addtogroup Utility
+ * @{
+ */
+
+class BlockIDStream {
+ public:
+ BlockIDStream(const CatalogRelation &relation,
+ const bool relation_is_stored,
+ const bool &done_feeding_blocks)
+ : relation_is_stored_(relation_is_stored),
+ done_feeding_blocks_(done_feeding_blocks),
+ current_position_(0) {
+ if (relation_is_stored_) {
+ block_ids_ = relation.getBlocksSnapshot();
+ }
+ }
+
+ inline void append(const block_id block) {
+ block_ids_.emplace_back(block);
+ }
+
+ inline bool hasNext() const {
+ return current_position_ < block_ids_.size();
+ }
+
+ inline block_id getNext() {
+ DCHECK(current_position_ < block_ids_.size());
+ return block_ids_[current_position_++];
+ }
+
+ bool isEndOfStream() const {
+ return (!hasNext()) && (relation_is_stored_ || done_feeding_blocks_);
+ }
+
+ private:
+ const bool relation_is_stored_;
+ const bool &done_feeding_blocks_;
+
+ std::vector<block_id> block_ids_;
+ std::size_t current_position_;
+
+ DISALLOW_COPY_AND_ASSIGN(BlockIDStream);
+};
+
+/** @} */
+
+} // namespace quickstep
+
+#endif // QUICKSTEP_UTILITY_BLOCK_ID_STREAM_HPP_
+
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/utility/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/utility/CMakeLists.txt b/utility/CMakeLists.txt
index c78ec59..2193315 100644
--- a/utility/CMakeLists.txt
+++ b/utility/CMakeLists.txt
@@ -177,6 +177,7 @@ add_library(quickstep_utility_CompositeHash ../empty_src.cpp CompositeHash.hpp)
add_library(quickstep_utility_BarrieredReadWriteConcurrentBitVector
../empty_src.cpp
BarrieredReadWriteConcurrentBitVector.hpp)
+add_library(quickstep_utility_BlockIDStream ../empty_src.cpp BlockIDStream.hpp)
add_library(quickstep_utility_DAG ../empty_src.cpp DAG.hpp)
add_library(quickstep_utility_DisjointTreeForest ../empty_src.cpp DisjointTreeForest.hpp)
add_library(quickstep_utility_EqualsAnyConstant ../empty_src.cpp EqualsAnyConstant.hpp)
@@ -253,6 +254,10 @@ target_link_libraries(quickstep_utility_CompositeHash
target_link_libraries(quickstep_utility_BarrieredReadWriteConcurrentBitVector
quickstep_utility_BitManipulation
quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_BlockIDStream
+ quickstep_catalog_CatalogRelation
+ quickstep_storage_StorageBlockInfo
+ quickstep_utility_Macros)
target_link_libraries(quickstep_utility_BulkIoConfiguration
quickstep_utility_Macros)
target_link_libraries(quickstep_utility_DAG
@@ -365,6 +370,7 @@ target_link_libraries(quickstep_utility
quickstep_utility_BarrieredReadWriteConcurrentBitVector
quickstep_utility_BitManipulation
quickstep_utility_BitVector
+ quickstep_utility_BlockIDStream
quickstep_utility_BloomFilter
quickstep_utility_BloomFilter_proto
quickstep_utility_BulkIoConfiguration
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/utility/TransitiveClosureContext.cpp
----------------------------------------------------------------------
diff --git a/utility/TransitiveClosureContext.cpp b/utility/TransitiveClosureContext.cpp
new file mode 100644
index 0000000..e69de29
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/734ddc1e/utility/TransitiveClosureContext.hpp
----------------------------------------------------------------------
diff --git a/utility/TransitiveClosureContext.hpp b/utility/TransitiveClosureContext.hpp
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/utility/TransitiveClosureContext.hpp
@@ -0,0 +1 @@
+