http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/a39ad965/storage/LinearOpenAddressingHashTable.hpp ---------------------------------------------------------------------- diff --git a/storage/LinearOpenAddressingHashTable.hpp b/storage/LinearOpenAddressingHashTable.hpp index e5ca0b0..438a2d1 100644 --- a/storage/LinearOpenAddressingHashTable.hpp +++ b/storage/LinearOpenAddressingHashTable.hpp @@ -151,6 +151,9 @@ class LinearOpenAddressingHashTable : public HashTable<ValueT, const ValueT **value, std::size_t *entry_num) const override; + bool hasKey(const TypedValue &key) const override; + bool hasCompositeKey(const std::vector<TypedValue> &key) const override; + void resize(const std::size_t extra_buckets, const std::size_t extra_variable_storage, const std::size_t retry_num = 0) override; @@ -1099,6 +1102,75 @@ bool LinearOpenAddressingHashTable<ValueT, resizable, serializable, force_key_co return false; } +template <typename ValueT, + bool resizable, + bool serializable, + bool force_key_copy, + bool allow_duplicate_keys> +bool LinearOpenAddressingHashTable<ValueT, resizable, serializable, force_key_copy, allow_duplicate_keys> + ::hasKey(const TypedValue &key) const { + DCHECK_EQ(1u, this->key_types_.size()); + DCHECK(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + + const std::size_t hash_code = this->AdjustHash(key.getHash()); + for (std::size_t bucket_num = hash_code % header_->num_buckets; + bucket_num < header_->num_buckets + header_->num_overflow_buckets; + ++bucket_num) { + const char *bucket = static_cast<const char*>(hash_buckets_) + bucket_num * bucket_size_; + const std::size_t bucket_hash + = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + if (bucket_hash == kEmptyHash) { + // Hit an empty bucket, so the search is finished + // without finding any match. + return false; + } + + // None of the get methods should be called while inserts are still taking + // place. + DCHECK(bucket_hash != kPendingHash); + + if ((bucket_hash == hash_code) && key_manager_.scalarKeyCollisionCheck(key, bucket)) { + // Match located. + return true; + } + } + return false; +} + +template <typename ValueT, + bool resizable, + bool serializable, + bool force_key_copy, + bool allow_duplicate_keys> +bool LinearOpenAddressingHashTable<ValueT, resizable, serializable, force_key_copy, allow_duplicate_keys> + ::hasCompositeKey(const std::vector<TypedValue> &key) const { + DEBUG_ASSERT(this->key_types_.size() == key.size()); + + const std::size_t hash_code = this->AdjustHash(this->hashCompositeKey(key)); + for (std::size_t bucket_num = hash_code % header_->num_buckets; + bucket_num < header_->num_buckets + header_->num_overflow_buckets; + ++bucket_num) { + const char *bucket = static_cast<const char*>(hash_buckets_) + bucket_num * bucket_size_; + const std::size_t bucket_hash + = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + if (bucket_hash == kEmptyHash) { + // Hit an empty bucket, so the search is finished + // without finding any match. + return false; + } + + // None of the get methods should be called while inserts are still taking + // place. + DEBUG_ASSERT(bucket_hash != kPendingHash); + + if ((bucket_hash == hash_code) && key_manager_.compositeKeyCollisionCheck(key, bucket)) { + // Match located. + return true; + } + } + return false; +} + // TODO(chasseur): Smarter heuristics that are more selective about whether // to grow hash buckets, variable-length storage, or both, and to what degree. template <typename ValueT,
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/a39ad965/storage/SeparateChainingHashTable.hpp ---------------------------------------------------------------------- diff --git a/storage/SeparateChainingHashTable.hpp b/storage/SeparateChainingHashTable.hpp index c93e783..c096b1b 100644 --- a/storage/SeparateChainingHashTable.hpp +++ b/storage/SeparateChainingHashTable.hpp @@ -145,6 +145,9 @@ class SeparateChainingHashTable : public HashTable<ValueT, const ValueT **value, std::size_t *entry_num) const override; + bool hasKey(const TypedValue &key) const override; + bool hasCompositeKey(const std::vector<TypedValue> &key) const override; + void resize(const std::size_t extra_buckets, const std::size_t extra_variable_storage, const std::size_t retry_num = 0) override; @@ -1054,6 +1057,57 @@ template <typename ValueT, bool serializable, bool force_key_copy, bool allow_duplicate_keys> +bool SeparateChainingHashTable<ValueT, resizable, serializable, force_key_copy, allow_duplicate_keys> + ::hasKey(const TypedValue &key) const { + DEBUG_ASSERT(this->key_types_.size() == 1); + DEBUG_ASSERT(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + + const std::size_t hash_code = key.getHash(); + std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + while (bucket_ref != 0) { + DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); + const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + bucket + sizeof(std::atomic<std::size_t>)); + if ((bucket_hash == hash_code) && key_manager_.scalarKeyCollisionCheck(key, bucket)) { + // Find a match. + return true; + } + bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + } + return false; +} + +template <typename ValueT, + bool resizable, + bool serializable, + bool force_key_copy, + bool allow_duplicate_keys> +bool SeparateChainingHashTable<ValueT, resizable, serializable, force_key_copy, allow_duplicate_keys> + ::hasCompositeKey(const std::vector<TypedValue> &key) const { + DEBUG_ASSERT(this->key_types_.size() == key.size()); + + const std::size_t hash_code = this->hashCompositeKey(key); + std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + while (bucket_ref != 0) { + DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); + const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + bucket + sizeof(std::atomic<std::size_t>)); + if ((bucket_hash == hash_code) && key_manager_.compositeKeyCollisionCheck(key, bucket)) { + // Find a match. + return true; + } + bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + } + return false; +} + +template <typename ValueT, + bool resizable, + bool serializable, + bool force_key_copy, + bool allow_duplicate_keys> void SeparateChainingHashTable<ValueT, resizable, serializable, force_key_copy, allow_duplicate_keys> ::resize(const std::size_t extra_buckets, const std::size_t extra_variable_storage, http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/a39ad965/storage/SimpleScalarSeparateChainingHashTable.hpp ---------------------------------------------------------------------- diff --git a/storage/SimpleScalarSeparateChainingHashTable.hpp b/storage/SimpleScalarSeparateChainingHashTable.hpp index b2d894d..eda6c86 100644 --- a/storage/SimpleScalarSeparateChainingHashTable.hpp +++ b/storage/SimpleScalarSeparateChainingHashTable.hpp @@ -182,6 +182,12 @@ class SimpleScalarSeparateChainingHashTable : public HashTable<ValueT, return getNextEntryForKey(key.front(), hash_code, value, entry_num); } + bool hasKey(const TypedValue &key) const override; + + bool hasCompositeKey(const std::vector<TypedValue> &key) const override { + return false; + } + void resize(const std::size_t extra_buckets, const std::size_t extra_variable_storage, const std::size_t retry_num = 0) override; @@ -772,6 +778,37 @@ template <typename ValueT, bool serializable, bool force_key_copy, bool allow_duplicate_keys> +bool SimpleScalarSeparateChainingHashTable<ValueT, + resizable, + serializable, + force_key_copy, + allow_duplicate_keys> + ::hasKey(const TypedValue &key) const { + DCHECK_EQ(1u, this->key_types_.size()); + DCHECK(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + + const std::size_t hash_code = key.getHashScalarLiteral(); + std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + while (bucket_ref != 0) { + DCHECK_NE(bucket_ref, std::numeric_limits<std::size_t>::max()); + + const Bucket &bucket = buckets_[bucket_ref - 1]; + if (bucket.hash == hash_code) { + // Match located. + return true; + } + bucket_ref = bucket.next.load(std::memory_order_relaxed); + } + + // Reached the end of the chain and didn't find a match. + return false; +} + +template <typename ValueT, + bool resizable, + bool serializable, + bool force_key_copy, + bool allow_duplicate_keys> void SimpleScalarSeparateChainingHashTable<ValueT, resizable, serializable, http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/a39ad965/storage/StorageBlock.hpp ---------------------------------------------------------------------- diff --git a/storage/StorageBlock.hpp b/storage/StorageBlock.hpp index da3bc70..97813e2 100644 --- a/storage/StorageBlock.hpp +++ b/storage/StorageBlock.hpp @@ -187,6 +187,17 @@ class StorageBlock : public StorageBlockBase { } /** + * @brief Get the flag vector indicating for each IndexSubBlock + * whether it is consistent. + * + * @return The flag vector indicating for each IndexSubBlock + * whether it is consistent. + */ + const std::vector<bool>& getIndicesConsistent() const { + return indices_consistent_; + } + + /** * @brief Get one of this block's IndexSubBlocks. * * @param index_id The ID of the IndexSubBlock. This is simply a serial @@ -201,6 +212,15 @@ class StorageBlock : public StorageBlockBase { } /** + * @brief Get the IndexSubBlock vector. + * + * @return The IndexSubBlock vector. + */ + const PtrVector<IndexSubBlock>& getIndices() const { + return indices_; + } + + /** * @brief Insert a single tuple into this block. * * @param tuple The tuple to insert.
