| /** |
| * 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 "storage/CompressedBlockBuilder.hpp" |
| |
| #include <algorithm> |
| #include <cstddef> |
| #include <cstdint> |
| #include <limits> |
| #include <memory> |
| #include <unordered_map> |
| #include <unordered_set> |
| #include <utility> |
| #include <vector> |
| |
| #include "catalog/CatalogAttribute.hpp" |
| #include "catalog/CatalogRelationSchema.hpp" |
| #include "catalog/CatalogTypedefs.hpp" |
| #include "compression/CompressionDictionaryBuilder.hpp" |
| #include "storage/StorageBlockInfo.hpp" |
| #include "storage/StorageBlockLayout.pb.h" |
| #include "types/Type.hpp" |
| #include "types/TypedValue.hpp" |
| #include "types/TypeID.hpp" |
| #include "types/containers/Tuple.hpp" |
| #include "types/operations/comparisons/Comparison.hpp" |
| #include "types/operations/comparisons/ComparisonUtil.hpp" |
| #include "utility/BitManipulation.hpp" |
| #include "utility/BitVector.hpp" |
| #include "utility/Macros.hpp" |
| |
| using std::numeric_limits; |
| using std::pair; |
| using std::sort; |
| using std::uint8_t; |
| using std::uint16_t; |
| using std::uint32_t; |
| using std::uint64_t; |
| using std::vector; |
| |
| namespace quickstep { |
| |
| namespace { |
| |
| // Very simple helper function to truncate an integral (either INT or LONG) in |
| // 'value' down to a code. Depending on the actual code length needed, the |
| // returned code may be further truncated down to 8 or 16 bits. |
| inline uint32_t TruncateIntegralValueToCode(const TypedValue &value, |
| const bool value_is_long) { |
| if (value_is_long) { |
| return value.getLiteral<std::int64_t>(); |
| } else { |
| return value.getLiteral<int>(); |
| } |
| } |
| |
| } // namespace |
| |
| CompressedBlockBuilder::CompressedBlockBuilder( |
| const CatalogRelationSchema &relation, |
| const TupleStorageSubBlockDescription &description, |
| const std::size_t block_size) |
| : relation_(relation), |
| block_size_(block_size), |
| sort_attribute_id_(-1), |
| sort_attribute_nullable_(false) { |
| std::unordered_set<attribute_id> compressed_attribute_ids; |
| |
| if (description.sub_block_type() == TupleStorageSubBlockDescription::COMPRESSED_PACKED_ROW_STORE) { |
| for (int compressed_attr_num = 0; |
| compressed_attr_num < description.ExtensionSize( |
| CompressedPackedRowStoreTupleStorageSubBlockDescription::compressed_attribute_id); |
| ++compressed_attr_num) { |
| compressed_attribute_ids.insert( |
| description.GetExtension(CompressedPackedRowStoreTupleStorageSubBlockDescription::compressed_attribute_id, |
| compressed_attr_num)); |
| } |
| } else if (description.sub_block_type() == TupleStorageSubBlockDescription::COMPRESSED_COLUMN_STORE) { |
| if (!description.HasExtension(CompressedColumnStoreTupleStorageSubBlockDescription::sort_attribute_id)) { |
| FATAL_ERROR("Attempted to create a CompressedBlockBuilder with a " |
| "TupleStorageSubBlockDescription that specified a " |
| "sub_block_type of COMPRESSED_COLUMN_STORE, but did not " |
| "specify a sort_attribute_id."); |
| } |
| sort_attribute_id_ = description.GetExtension( |
| CompressedColumnStoreTupleStorageSubBlockDescription::sort_attribute_id); |
| sort_attribute_nullable_ |
| = relation_.getAttributeById(sort_attribute_id_)->getType().isNullable(); |
| |
| for (int compressed_attr_num = 0; |
| compressed_attr_num < description.ExtensionSize( |
| CompressedColumnStoreTupleStorageSubBlockDescription::compressed_attribute_id); |
| ++compressed_attr_num) { |
| compressed_attribute_ids.insert( |
| description.GetExtension(CompressedColumnStoreTupleStorageSubBlockDescription::compressed_attribute_id, |
| compressed_attr_num)); |
| } |
| } else { |
| FATAL_ERROR("Attempted to create a CompressedBlockBuilder with a " |
| "TupleStorageSubBlockDescription that did not specify a " |
| "compressed sub_block_type."); |
| } |
| |
| for (attribute_id attr_num = 0; |
| attr_num <= relation.getMaxAttributeId(); |
| ++attr_num) { |
| compression_info_.add_attribute_size(0); |
| compression_info_.add_dictionary_size(0); |
| compression_info_.add_uncompressed_attribute_has_nulls(false); |
| |
| if (relation_.hasAttributeWithId(attr_num)) { |
| const Type &attr_type = relation_.getAttributeById(attr_num)->getType(); |
| |
| if (compressed_attribute_ids.find(attr_num) != compressed_attribute_ids.end()) { |
| dictionary_builders_.insert(attr_num, new CompressionDictionaryBuilder(attr_type)); |
| if ((attr_type.getTypeID() == kInt) || (attr_type.getTypeID() == kLong)) { |
| maximum_integers_.insert(pair<attribute_id, const TypedValue*>(attr_num, |
| nullptr)); |
| } |
| } |
| |
| if (attr_type.isNullable()) { |
| null_present_.emplace(attr_num, false); |
| } |
| } |
| } |
| |
| compression_info_.set_null_bitmap_bits(0); |
| } |
| |
| bool CompressedBlockBuilder::addTuple(const Tuple &tuple) { |
| Tuple *candidate_tuple = tuple.clone(); |
| candidate_tuple->ensureLiteral(); |
| return addTupleInternal(candidate_tuple); |
| } |
| |
| void CompressedBlockBuilder::buildCompressedPackedRowStoreTupleStorageSubBlock(void *sub_block_memory) { |
| DEBUG_ASSERT(sort_attribute_id_ == -1); |
| DEBUG_ASSERT(computeRequiredStorage(tuples_.size()) <= block_size_); |
| |
| // Build header and any dictionaries, and initialize null bitmap if needed. |
| char *data_ptr = static_cast<char*>(sub_block_memory) |
| + buildTupleStorageSubBlockHeader(sub_block_memory); |
| |
| std::unique_ptr<BitVector<false>> null_bitmap; |
| std::unordered_map<attribute_id, size_t> attribute_null_bitmap_offsets; |
| size_t uncompressed_attributes_with_nulls = 0; |
| if (compression_info_.null_bitmap_bits() > 0) { |
| const size_t null_bitmap_bytes = BitVector<false>::BytesNeeded( |
| compression_info_.null_bitmap_bits()); |
| null_bitmap.reset(new BitVector<false>(data_ptr - null_bitmap_bytes, |
| compression_info_.null_bitmap_bits())); |
| for (attribute_id attr_id = 0; |
| attr_id <= relation_.getMaxAttributeId(); |
| ++attr_id) { |
| if (compression_info_.uncompressed_attribute_has_nulls(attr_id)) { |
| attribute_null_bitmap_offsets[attr_id] = uncompressed_attributes_with_nulls++; |
| } |
| } |
| } |
| |
| for (PtrVector<Tuple>::size_type tuple_idx = 0; |
| tuple_idx < tuples_.size(); |
| ++tuple_idx) { |
| const Tuple &tuple = tuples_[tuple_idx]; |
| for (CatalogRelationSchema::const_iterator attr_it = relation_.begin(); |
| attr_it != relation_.end(); |
| ++attr_it) { |
| const attribute_id attr_id = attr_it->getID(); |
| if (compression_info_.dictionary_size(attr_id) > 0) { |
| // Attribute is dictionary-compressed. |
| PtrMap<attribute_id, CompressionDictionaryBuilder>::const_iterator |
| builder_it = dictionary_builders_.find(attr_id); |
| DEBUG_ASSERT(builder_it != dictionary_builders_.end()); |
| switch (compression_info_.attribute_size(attr_id)) { |
| case 1: |
| *reinterpret_cast<uint8_t*>(data_ptr) |
| = builder_it->second->getCodeForValue(tuple.getAttributeValue(attr_id)); |
| break; |
| case 2: |
| *reinterpret_cast<uint16_t*>(data_ptr) |
| = builder_it->second->getCodeForValue(tuple.getAttributeValue(attr_id)); |
| break; |
| case 4: |
| *reinterpret_cast<uint32_t*>(data_ptr) |
| = builder_it->second->getCodeForValue(tuple.getAttributeValue(attr_id)); |
| break; |
| default: |
| FATAL_ERROR("Dictionary-compressed type had non power-of-two length in " |
| "CompressedBlockBuilder::buildCompressedPackedRowStoreTupleStorageSubBlock()"); |
| } |
| } else if (compression_info_.attribute_size(attr_id) |
| != attr_it->getType().maximumByteLength()) { |
| // Attribute is compressed by truncation. |
| switch (compression_info_.attribute_size(attr_id)) { |
| case 1: |
| *reinterpret_cast<uint8_t*>(data_ptr) |
| = TruncateIntegralValueToCode(tuple.getAttributeValue(attr_id), |
| attr_it->getType().getTypeID() == kLong); |
| break; |
| case 2: |
| *reinterpret_cast<uint16_t*>(data_ptr) |
| = TruncateIntegralValueToCode(tuple.getAttributeValue(attr_id), |
| attr_it->getType().getTypeID() == kLong); |
| break; |
| case 4: |
| *reinterpret_cast<uint32_t*>(data_ptr) |
| = TruncateIntegralValueToCode(tuple.getAttributeValue(attr_id), |
| attr_it->getType().getTypeID() == kLong); |
| break; |
| default: |
| FATAL_ERROR("Truncation-compressed type had non power-of-two length in " |
| "CompressedBlockBuilder::buildCompressedPackedRowStoreupleStorageSubBlock()"); |
| } |
| } else { |
| // Attribute is uncompressed. |
| if (tuple.getAttributeValue(attr_id).isNull()) { |
| null_bitmap->setBit(tuple_idx * uncompressed_attributes_with_nulls |
| + attribute_null_bitmap_offsets[attr_id], |
| true); |
| } else { |
| tuple.getAttributeValue(attr_id).copyInto(data_ptr); |
| } |
| } |
| data_ptr += compression_info_.attribute_size(attr_id); |
| } |
| } |
| } |
| |
| void CompressedBlockBuilder::buildCompressedColumnStoreTupleStorageSubBlock(void *sub_block_memory) { |
| DEBUG_ASSERT(computeRequiredStorage(tuples_.size()) <= block_size_); |
| |
| // Sort tuples according to values of the sort attribute. |
| const Type &sort_attribute_type = relation_.getAttributeById(sort_attribute_id_)->getType(); |
| if (sort_attribute_nullable_) { |
| SortTuples(sort_attribute_id_, |
| sort_attribute_type.getNonNullableVersion(), |
| tuples_with_non_null_sort_value_.begin(), |
| tuples_with_non_null_sort_value_.end()); |
| *(tuples_.getInternalVectorMutable()) = std::move(tuples_with_non_null_sort_value_); |
| tuples_.getInternalVectorMutable()->insert(tuples_.getInternalVectorMutable()->end(), |
| tuples_with_null_sort_value_.begin(), |
| tuples_with_null_sort_value_.end()); |
| } else { |
| SortTuples(sort_attribute_id_, |
| sort_attribute_type, |
| tuples_.getInternalVectorMutable()->begin(), |
| tuples_.getInternalVectorMutable()->end()); |
| } |
| |
| char *current_stripe = static_cast<char*>(sub_block_memory) |
| + buildTupleStorageSubBlockHeader(sub_block_memory); |
| |
| PtrMap<attribute_id, BitVector<false>> null_bitmaps; |
| buildNullBitmapMap(sub_block_memory, &null_bitmaps); |
| |
| size_t tuple_size = 0; |
| size_t total_dictionary_size = 0; |
| for (CatalogRelationSchema::const_iterator attr_it = relation_.begin(); |
| attr_it != relation_.end(); |
| ++attr_it) { |
| tuple_size += compression_info_.attribute_size(attr_it->getID()); |
| total_dictionary_size += compression_info_.dictionary_size(attr_it->getID()); |
| } |
| DEBUG_ASSERT(tuple_size > 0); |
| size_t max_tuples = (block_size_ |
| - (sizeof(tuple_id) + sizeof(int) |
| + compression_info_.ByteSize() |
| + total_dictionary_size |
| + null_bitmaps.size() |
| * BitVector<false>::BytesNeeded(compression_info_.null_bitmap_bits()))) |
| / tuple_size; |
| |
| for (CatalogRelationSchema::const_iterator attr_it = relation_.begin(); |
| attr_it != relation_.end(); |
| ++attr_it) { |
| if (compression_info_.dictionary_size(attr_it->getID()) > 0) { |
| // Attribute is dictionary-compressed. |
| PtrMap<attribute_id, CompressionDictionaryBuilder>::const_iterator |
| builder_it = dictionary_builders_.find(attr_it->getID()); |
| DEBUG_ASSERT(builder_it != dictionary_builders_.end()); |
| buildDictionaryCompressedColumnStripe(attr_it->getID(), |
| *(builder_it->second), |
| current_stripe); |
| } else if (compression_info_.attribute_size(attr_it->getID()) |
| != attr_it->getType().maximumByteLength()) { |
| // Attribute is truncation-compressed. |
| buildTruncationCompressedColumnStripe(attr_it->getID(), |
| attr_it->getType().getTypeID() == kLong, |
| current_stripe); |
| } else { |
| // Attribute is uncompressed. |
| if (compression_info_.uncompressed_attribute_has_nulls(attr_it->getID())) { |
| buildNullableUncompressedColumnStripe(attr_it->getID(), |
| current_stripe, |
| null_bitmaps.find(attr_it->getID())->second); |
| } else { |
| buildUncompressedColumnStripe(attr_it->getID(), |
| current_stripe); |
| } |
| } |
| |
| current_stripe += max_tuples * compression_info_.attribute_size(attr_it->getID()); |
| } |
| } |
| |
| bool CompressedBlockBuilder::addTupleInternal(Tuple *candidate_tuple) { |
| DEBUG_ASSERT(candidate_tuple->size() == relation_.size()); |
| |
| // Ensure that the tuple is the owner of its values. |
| candidate_tuple->ensureLiteral(); |
| |
| // Modify dictionaries and maximum integers to reflect the new tuple's |
| // values. Keep track of what has changed in case a rollback is needed. |
| vector<CompressionDictionaryBuilder*> modified_dictionaries; |
| std::unordered_map<attribute_id, const TypedValue*> previous_maximum_integers; |
| std::unordered_map<attribute_id, bool> previous_null_present(null_present_); |
| |
| CatalogRelationSchema::const_iterator attr_it = relation_.begin(); |
| Tuple::const_iterator value_it = candidate_tuple->begin(); |
| while (attr_it != relation_.end()) { |
| attribute_id attr_id = attr_it->getID(); |
| |
| PtrMap<attribute_id, CompressionDictionaryBuilder>::iterator |
| dictionary_it = dictionary_builders_.find(attr_id); |
| if (dictionary_it != dictionary_builders_.end()) { |
| if (dictionary_it->second->insertEntryByReference(*value_it)) { |
| modified_dictionaries.push_back(dictionary_it->second); |
| } |
| } |
| |
| if (value_it->isNull()) { |
| DEBUG_ASSERT(attr_it->getType().isNullable()); |
| DEBUG_ASSERT(null_present_.find(attr_id) != null_present_.end()); |
| null_present_[attr_id] = true; |
| } |
| |
| std::unordered_map<attribute_id, const TypedValue*>::iterator max_int_it |
| = maximum_integers_.find(attr_id); |
| if (max_int_it != maximum_integers_.end()) { |
| // If the new value is null or less than zero, we can't truncate it. |
| // |
| // TODO(chasseur): With some effort, we could efficiently encode small |
| // negative integers using zigzag encoding (although this would |
| // complicate predicate evaluation). We could also use a null bitmap in |
| // conjunction with truncation to deal with null values. |
| bool value_is_negative_or_null = value_it->isNull(); |
| if (!value_is_negative_or_null) { |
| switch (attr_it->getType().getTypeID()) { |
| case kInt: |
| value_is_negative_or_null = value_it->getLiteral<int>() < 0; |
| break; |
| case kLong: |
| value_is_negative_or_null = value_it->getLiteral<std::int64_t>() < 0; |
| break; |
| default: |
| FATAL_ERROR("Non-integer type encountered in the maximum_integers_ " |
| "map of a CompressedBlockBuilder."); |
| } |
| } |
| |
| if (value_is_negative_or_null) { |
| previous_maximum_integers.emplace(attr_id, max_int_it->second); |
| // Stop counting maximum, since we can no longer compress by truncating. |
| maximum_integers_.erase(max_int_it); |
| } else if (max_int_it->second == nullptr) { |
| // If there was no maximum before, then this is the first value and |
| // automatically becomes the maximum. |
| previous_maximum_integers.emplace(attr_id, nullptr); |
| max_int_it->second = &(*value_it); |
| } else { |
| // Compare with the previous maximum and update as necessary. |
| bool new_maximum; |
| switch (attr_it->getType().getTypeID()) { |
| case kInt: |
| new_maximum = max_int_it->second->getLiteral<int>() |
| < value_it->getLiteral<int>(); |
| break; |
| case kLong: |
| new_maximum = max_int_it->second->getLiteral<std::int64_t>() |
| < value_it->getLiteral<std::int64_t>(); |
| break; |
| default: |
| FATAL_ERROR("Non-integer type encountered in the maximum_integers_ map " |
| "of a CompressedBlockBuilder."); |
| } |
| |
| if (new_maximum) { |
| previous_maximum_integers.emplace(attr_id, max_int_it->second); |
| max_int_it->second = &(*value_it); |
| } |
| } |
| } |
| |
| ++attr_it; |
| ++value_it; |
| } |
| |
| if (computeRequiredStorage(tuples_.size() + 1) > block_size_) { |
| rollbackLastInsert(modified_dictionaries, |
| previous_maximum_integers, |
| std::move(previous_null_present)); |
| delete candidate_tuple; |
| return false; |
| } else { |
| if (sort_attribute_nullable_) { |
| if (candidate_tuple->getAttributeValue(sort_attribute_id_).isNull()) { |
| tuples_with_null_sort_value_.push_back(candidate_tuple); |
| } else { |
| tuples_with_non_null_sort_value_.push_back(candidate_tuple); |
| } |
| } |
| tuples_.push_back(candidate_tuple); |
| return true; |
| } |
| } |
| |
| std::size_t CompressedBlockBuilder::computeRequiredStorage(const std::size_t num_tuples) const { |
| // Start with the size of the header. |
| size_t required_storage = compression_info_.ByteSize() + sizeof(int) + sizeof(tuple_id); |
| |
| // Add required storage attribute-by-attribute. |
| size_t uncompressed_attributes_with_nulls = 0; |
| for (CatalogRelationSchema::const_iterator attr_it = relation_.begin(); |
| attr_it != relation_.end(); |
| ++attr_it) { |
| PtrMap<attribute_id, CompressionDictionaryBuilder>::const_iterator |
| dictionary_it = dictionary_builders_.find(attr_it->getID()); |
| if (dictionary_it == dictionary_builders_.end()) { |
| // This attribute is not compressed. |
| required_storage += num_tuples * attr_it->getType().maximumByteLength(); |
| |
| if (attr_it->getType().isNullable() && null_present_.find(attr_it->getID())->second) { |
| ++uncompressed_attributes_with_nulls; |
| } |
| } else if (attr_it->getType().isVariableLength()) { |
| // Variable-length types MUST use dictionary compression. |
| required_storage += dictionary_it->second->dictionarySizeBytes() |
| + num_tuples * dictionary_it->second->codeLengthPaddedBytes(); |
| } else { |
| // Calculate the number of bytes needed to store all values when |
| // truncating (if possible) or just storing values uncompressed. |
| size_t truncated_bytes = num_tuples * computeTruncatedByteLengthForAttribute(attr_it->getID()); |
| |
| // Compute the number of extra bytes that would be needed for a bitmap of |
| // uncompressed nulls. |
| // |
| // TODO(chasseur): This is precisely accurate for CompressedColumnStore, |
| // but may slightly overestimate required storage for |
| // CompressedPackedRowStore, which uses one shared null bitmap in |
| // row-major order, and therefore only "rounds up" to the nearest size_t |
| // increment *once*, rather than once-per-column. Thus, there may be |
| // some marginal edge cases for CompressedPackedRowStore where this |
| // calculation is slightly biased in favor of compression. |
| size_t null_bitmap_bytes = 0; |
| if (attr_it->getType().isNullable() && null_present_.find(attr_it->getID())->second) { |
| null_bitmap_bytes = BitVector<false>::BytesNeeded(num_tuples); |
| } |
| |
| // Calculate the total number of bytes (including storage for the |
| // dictionary itself) needed to store all values with dictionary |
| // compression. |
| size_t dictionary_bytes = dictionary_it->second->dictionarySizeBytes() |
| + num_tuples * dictionary_it->second->codeLengthPaddedBytes(); |
| |
| // Choose the method that uses space most efficiently. |
| if (truncated_bytes + null_bitmap_bytes < dictionary_bytes) { |
| required_storage += truncated_bytes; |
| if (null_bitmap_bytes != 0) { |
| ++uncompressed_attributes_with_nulls; |
| } |
| } else { |
| required_storage += dictionary_bytes; |
| } |
| } |
| } |
| |
| // Add space for null bitmap(s) for uncompressed attributes, if any. |
| if (uncompressed_attributes_with_nulls > 0) { |
| if (sort_attribute_id_ == -1) { |
| // CompressedPackedRowStore uses a single shared row-major null bitmap. |
| required_storage += BitVector<false>::BytesNeeded(num_tuples * uncompressed_attributes_with_nulls); |
| } else { |
| // CompressedColumnStore uses separate per-column null bitmaps. |
| required_storage += uncompressed_attributes_with_nulls |
| * BitVector<false>::BytesNeeded(num_tuples); |
| } |
| } |
| return required_storage; |
| } |
| |
| std::size_t CompressedBlockBuilder::computeTruncatedByteLengthForAttribute( |
| const attribute_id attr_id) const { |
| DEBUG_ASSERT(relation_.hasAttributeWithId(attr_id)); |
| |
| size_t truncated_bytes = relation_.getAttributeById(attr_id)->getType().maximumByteLength(); |
| |
| // Can't truncate if null values are present. |
| std::unordered_map<attribute_id, bool>::const_iterator null_present_it |
| = null_present_.find(attr_id); |
| if ((null_present_it != null_present_.end()) && null_present_it->second) { |
| return truncated_bytes; |
| } |
| |
| std::unordered_map<attribute_id, const TypedValue*>::const_iterator max_int_it |
| = maximum_integers_.find(attr_id); |
| if ((max_int_it != maximum_integers_.end() && (max_int_it->second != nullptr))) { |
| unsigned int leading_zero_bits; |
| switch (max_int_it->second->getTypeID()) { |
| case kInt: |
| DEBUG_ASSERT(max_int_it->second->getLiteral<int>() >= 0); |
| if (max_int_it->second->getLiteral<int>()) { |
| leading_zero_bits = leading_zero_count<uint32_t>( |
| static_cast<uint32_t>(max_int_it->second->getLiteral<int>())); |
| } else { |
| leading_zero_bits = 32; |
| } |
| break; |
| case kLong: |
| DEBUG_ASSERT(max_int_it->second->getLiteral<std::int64_t>() >= 0); |
| if (max_int_it->second->getLiteral<std::int64_t>()) { |
| // Due to a quirk in predicate evaluation on truncated values, |
| // we shouldn't store UINT32_MAX truncated. |
| if (max_int_it->second->getLiteral<std::int64_t>() == numeric_limits<uint32_t>::max()) { |
| return truncated_bytes; |
| } |
| leading_zero_bits = leading_zero_count<uint64_t>( |
| static_cast<uint64_t>(max_int_it->second->getLiteral<std::int64_t>())); |
| } else { |
| leading_zero_bits = 64; |
| } |
| break; |
| default: |
| FATAL_ERROR("Non-integer type encountered in the maximum_integers_ map " |
| "of a CompressedBlockBuilder."); |
| } |
| |
| unsigned int needed_bits = (truncated_bytes << 3) - leading_zero_bits; |
| if (needed_bits < 9) { |
| truncated_bytes = 1; |
| } else if (needed_bits < 17) { |
| truncated_bytes = 2; |
| } else if (needed_bits < 33) { |
| truncated_bytes = 4; |
| } |
| } |
| |
| return truncated_bytes; |
| } |
| |
| void CompressedBlockBuilder::rollbackLastInsert( |
| const std::vector<CompressionDictionaryBuilder*> &modified_dictionaries, |
| const std::unordered_map<attribute_id, const TypedValue*> &previous_maximum_integers, |
| std::unordered_map<attribute_id, bool> &&previous_null_present) { |
| for (vector<CompressionDictionaryBuilder*>::const_iterator dictionary_it = modified_dictionaries.begin(); |
| dictionary_it != modified_dictionaries.end(); |
| ++dictionary_it) { |
| (*dictionary_it)->undoLastInsert(); |
| } |
| |
| for (std::unordered_map<attribute_id, const TypedValue*>::const_iterator previous_max_it |
| = previous_maximum_integers.begin(); |
| previous_max_it != previous_maximum_integers.end(); |
| ++previous_max_it) { |
| maximum_integers_[previous_max_it->first] = previous_max_it->second; |
| } |
| |
| null_present_ = std::move(previous_null_present); |
| } |
| |
| std::size_t CompressedBlockBuilder::buildTupleStorageSubBlockHeader(void *sub_block_memory) { |
| // Build up the CompressedBlockInfo. |
| size_t uncompressed_attributes_with_nulls = 0; |
| for (CatalogRelationSchema::const_iterator attr_it = relation_.begin(); |
| attr_it != relation_.end(); |
| ++attr_it) { |
| const attribute_id attr_id = attr_it->getID(); |
| const Type &attr_type = attr_it->getType(); |
| const bool attr_has_nulls = attr_type.isNullable() |
| && null_present_[attr_id]; |
| PtrMap<attribute_id, CompressionDictionaryBuilder>::const_iterator dictionary_it |
| = dictionary_builders_.find(attr_id); |
| if (dictionary_it == dictionary_builders_.end()) { |
| // This attribute is not compressed. |
| compression_info_.set_attribute_size(attr_id, |
| attr_type.maximumByteLength()); |
| compression_info_.set_dictionary_size(attr_id, 0); |
| |
| compression_info_.set_uncompressed_attribute_has_nulls(attr_id, |
| attr_has_nulls); |
| uncompressed_attributes_with_nulls += attr_has_nulls; |
| } else if (attr_type.isVariableLength()) { |
| // Variable-length types MUST use dictionary compression. |
| compression_info_.set_attribute_size(attr_id, |
| dictionary_it->second->codeLengthPaddedBytes()); |
| compression_info_.set_dictionary_size(attr_id, |
| dictionary_it->second->dictionarySizeBytes()); |
| compression_info_.set_uncompressed_attribute_has_nulls(attr_id, false); |
| } else { |
| // Calculate the number of bytes needed to store all values when |
| // truncating (if possible) or just storing values uncompressed. |
| size_t truncated_bytes = tuples_.size() * computeTruncatedByteLengthForAttribute(attr_id); |
| |
| // Compute the number of extra bytes that would be needed for a bitmap of |
| // uncompressed nulls. |
| // |
| // NOTE(chasseur): See note in computeRequiredStorage() about edge cases |
| // with CompressedPackedRowStore that are slightly biased in favor of |
| // compression. |
| size_t null_bitmap_bytes = attr_has_nulls ? BitVector<false>::BytesNeeded(tuples_.size()) |
| : 0; |
| |
| // Calculate the total number of bytes (including storage for the |
| // dictionary itself) needed to store all values with dictionary |
| // compression. |
| size_t dictionary_bytes = dictionary_it->second->dictionarySizeBytes() |
| + tuples_.size() * dictionary_it->second->codeLengthPaddedBytes(); |
| |
| // Choose the method that uses space most efficiently. |
| if (truncated_bytes + null_bitmap_bytes < dictionary_bytes) { |
| compression_info_.set_attribute_size(attr_id, |
| computeTruncatedByteLengthForAttribute(attr_id)); |
| compression_info_.set_dictionary_size(attr_id, 0); |
| compression_info_.set_uncompressed_attribute_has_nulls(attr_id, attr_has_nulls); |
| uncompressed_attributes_with_nulls += attr_has_nulls; |
| } else { |
| compression_info_.set_attribute_size(attr_id, |
| dictionary_it->second->codeLengthPaddedBytes()); |
| compression_info_.set_dictionary_size(attr_id, |
| dictionary_it->second->dictionarySizeBytes()); |
| compression_info_.set_uncompressed_attribute_has_nulls(attr_id, false); |
| } |
| } |
| } |
| |
| if (uncompressed_attributes_with_nulls > 0) { |
| if (sort_attribute_id_ == -1) { |
| // CompressedPackedRowStore uses a single shared null bitmap. |
| compression_info_.set_null_bitmap_bits( |
| uncompressed_attributes_with_nulls * tuples_.size()); |
| } else { |
| // CompressedColumnStore uses per-column null bitmaps. |
| compression_info_.set_null_bitmap_bits(tuples_.size()); |
| } |
| } else { |
| compression_info_.set_null_bitmap_bits(0); |
| } |
| |
| // Record the number of tuples. |
| *static_cast<tuple_id*>(sub_block_memory) = tuples_.size(); |
| |
| // Serialize the compression info. |
| *reinterpret_cast<int*>(static_cast<char*>(sub_block_memory) + sizeof(tuple_id)) |
| = compression_info_.ByteSize(); |
| if (!compression_info_.SerializeToArray(static_cast<char*>(sub_block_memory) + sizeof(tuple_id) + sizeof(int), |
| compression_info_.ByteSize())) { |
| FATAL_ERROR("Failed to do binary serialization of CompressedBlockInfo in " |
| "CompressedBlockBuilder::buildTupleStorageSubBlockHeader"); |
| } |
| |
| // Build the physical dictionaries. |
| size_t memory_offset = sizeof(tuple_id) + sizeof(int) + compression_info_.ByteSize(); |
| for (attribute_id attr_id = 0; |
| attr_id <= relation_.getMaxAttributeId(); |
| ++attr_id) { |
| if (compression_info_.dictionary_size(attr_id) > 0) { |
| dictionary_builders_.find(attr_id)->second->buildDictionary( |
| static_cast<char*>(sub_block_memory) + memory_offset); |
| memory_offset += compression_info_.dictionary_size(attr_id); |
| } |
| } |
| |
| // Initialize null bitmap(s), if any. |
| if (uncompressed_attributes_with_nulls > 0) { |
| if (sort_attribute_id_ == -1) { |
| // CompressedPackedRowStore uses a single shared null bitmap. |
| BitVector<false> null_bitmap(static_cast<char*>(sub_block_memory) + memory_offset, |
| compression_info_.null_bitmap_bits()); |
| null_bitmap.clear(); |
| |
| memory_offset += BitVector<false>::BytesNeeded(compression_info_.null_bitmap_bits()); |
| } else { |
| // CompressedColumnStore uses per-column null bitmaps. |
| for (attribute_id attr_id = 0; |
| attr_id <= relation_.getMaxAttributeId(); |
| ++attr_id) { |
| if (compression_info_.uncompressed_attribute_has_nulls(attr_id)) { |
| BitVector<false> null_bitmap(static_cast<char*>(sub_block_memory) + memory_offset, |
| compression_info_.null_bitmap_bits()); |
| null_bitmap.clear(); |
| |
| memory_offset += BitVector<false>::BytesNeeded(compression_info_.null_bitmap_bits()); |
| } |
| } |
| } |
| } |
| |
| return memory_offset; |
| } |
| |
| void CompressedBlockBuilder::buildNullBitmapMap( |
| void *sub_block_memory, |
| PtrMap<attribute_id, BitVector<false>> *null_bitmaps) const { |
| if (compression_info_.null_bitmap_bits() == 0) { |
| return; |
| } |
| |
| char *memory_position = static_cast<char*>(sub_block_memory) |
| + sizeof(int) + sizeof(tuple_id) + compression_info_.ByteSize(); |
| |
| // Advance past all the dictionaries. |
| for (attribute_id attr_id = 0; |
| attr_id < compression_info_.dictionary_size_size(); |
| ++attr_id) { |
| memory_position += compression_info_.dictionary_size(attr_id); |
| } |
| |
| for (attribute_id attr_id = 0; |
| attr_id < compression_info_.dictionary_size_size(); |
| ++attr_id) { |
| if (compression_info_.uncompressed_attribute_has_nulls(attr_id)) { |
| null_bitmaps->insert(attr_id, |
| new BitVector<false>(memory_position, |
| compression_info_.null_bitmap_bits())); |
| memory_position += BitVector<false>::BytesNeeded(compression_info_.null_bitmap_bits()); |
| } |
| } |
| } |
| |
| void CompressedBlockBuilder::buildDictionaryCompressedColumnStripe( |
| const attribute_id attr_id, |
| const CompressionDictionaryBuilder &builder, |
| void *stripe_location) const { |
| switch (compression_info_.attribute_size(attr_id)) { |
| case 1: |
| for (size_t tuple_num = 0; |
| tuple_num < tuples_.size(); |
| ++tuple_num) { |
| reinterpret_cast<uint8_t*>(stripe_location)[tuple_num] |
| = builder.getCodeForValue(tuples_[tuple_num].getAttributeValue(attr_id)); |
| } |
| break; |
| case 2: |
| for (size_t tuple_num = 0; |
| tuple_num < tuples_.size(); |
| ++tuple_num) { |
| reinterpret_cast<uint16_t*>(stripe_location)[tuple_num] |
| = builder.getCodeForValue(tuples_[tuple_num].getAttributeValue(attr_id)); |
| } |
| break; |
| case 4: |
| for (size_t tuple_num = 0; |
| tuple_num < tuples_.size(); |
| ++tuple_num) { |
| reinterpret_cast<uint32_t*>(stripe_location)[tuple_num] |
| = builder.getCodeForValue(tuples_[tuple_num].getAttributeValue(attr_id)); |
| } |
| break; |
| default: |
| FATAL_ERROR("Dictionary-compressed type had non power-of-two length in " |
| "CompressedBlockBuilder::buildDictionaryCompressedColumnStripe()"); |
| } |
| } |
| |
| void CompressedBlockBuilder::buildTruncationCompressedColumnStripe( |
| const attribute_id attr_id, |
| const bool attr_is_long, |
| void *stripe_location) const { |
| switch (compression_info_.attribute_size(attr_id)) { |
| case 1: |
| for (size_t tuple_num = 0; |
| tuple_num < tuples_.size(); |
| ++tuple_num) { |
| reinterpret_cast<uint8_t*>(stripe_location)[tuple_num] |
| = TruncateIntegralValueToCode(tuples_[tuple_num].getAttributeValue(attr_id), |
| attr_is_long); |
| } |
| break; |
| case 2: |
| for (size_t tuple_num = 0; |
| tuple_num < tuples_.size(); |
| ++tuple_num) { |
| reinterpret_cast<uint16_t*>(stripe_location)[tuple_num] |
| = TruncateIntegralValueToCode(tuples_[tuple_num].getAttributeValue(attr_id), |
| attr_is_long); |
| } |
| break; |
| case 4: |
| for (size_t tuple_num = 0; |
| tuple_num < tuples_.size(); |
| ++tuple_num) { |
| reinterpret_cast<uint32_t*>(stripe_location)[tuple_num] |
| = TruncateIntegralValueToCode(tuples_[tuple_num].getAttributeValue(attr_id), |
| attr_is_long); |
| } |
| break; |
| default: |
| FATAL_ERROR("Truncation-compressed type had non power-of-two length in " |
| "CompressedBlockBuilder::buildTruncationCompressedColumnStripe()"); |
| } |
| } |
| |
| void CompressedBlockBuilder::buildUncompressedColumnStripe( |
| const attribute_id attr_id, |
| void *stripe_location) const { |
| char *value_location = static_cast<char*>(stripe_location); |
| const size_t value_length = compression_info_.attribute_size(attr_id); |
| for (PtrVector<Tuple>::const_iterator tuple_it = tuples_.begin(); |
| tuple_it != tuples_.end(); |
| ++tuple_it) { |
| tuple_it->getAttributeValue(attr_id).copyInto(value_location); |
| value_location += value_length; |
| } |
| } |
| |
| void CompressedBlockBuilder::buildNullableUncompressedColumnStripe( |
| const attribute_id attr_id, |
| void *stripe_location, |
| BitVector<false> *null_bitmap) const { |
| const size_t value_length = compression_info_.attribute_size(attr_id); |
| if (value_length == 0) { |
| for (PtrVector<Tuple>::size_type tuple_idx = 0; |
| tuple_idx < tuples_.size(); |
| ++tuple_idx) { |
| const TypedValue &value = tuples_[tuple_idx].getAttributeValue(attr_id); |
| if (value.isNull()) { |
| null_bitmap->setBit(tuple_idx, true); |
| } |
| } |
| } else { |
| char *value_location = static_cast<char*>(stripe_location); |
| TypedValue last_value = GetLastValueForType(relation_.getAttributeById(attr_id)->getType()); |
| for (PtrVector<Tuple>::size_type tuple_idx = 0; |
| tuple_idx < tuples_.size(); |
| ++tuple_idx) { |
| const TypedValue &value = tuples_[tuple_idx].getAttributeValue(attr_id); |
| if (value.isNull()) { |
| null_bitmap->setBit(tuple_idx, true); |
| last_value.copyInto(value_location); |
| } else { |
| value.copyInto(value_location); |
| } |
| value_location += value_length; |
| } |
| } |
| } |
| |
| } // namespace quickstep |
