| /** |
| * 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/BloomFilterIndexSubBlock.hpp" |
| |
| #include <cstdint> |
| |
| #include "catalog/CatalogAttribute.hpp" |
| #include "catalog/CatalogRelationSchema.hpp" |
| #include "catalog/CatalogTypedefs.hpp" |
| #include "expressions/predicate/ComparisonPredicate.hpp" |
| #include "expressions/predicate/PredicateCost.hpp" |
| #include "expressions/scalar/Scalar.hpp" |
| #include "expressions/scalar/ScalarAttribute.hpp" |
| #include "expressions/scalar/ScalarLiteral.hpp" |
| #include "storage/StorageBlockLayout.pb.h" |
| #include "storage/StorageConstants.hpp" |
| #include "storage/SubBlockTypeRegistry.hpp" |
| #include "storage/TupleIdSequence.hpp" |
| #include "storage/TupleStorageSubBlock.hpp" |
| #include "types/TypedValue.hpp" |
| #include "types/operations/comparisons/Comparison.hpp" |
| #include "types/operations/comparisons/ComparisonID.hpp" |
| #include "utility/BloomFilter.hpp" |
| |
| #include "glog/logging.h" |
| |
| namespace quickstep { |
| |
| QUICKSTEP_REGISTER_INDEX(BloomFilterIndexSubBlock, BLOOM_FILTER); |
| |
| BloomFilterIndexSubBlock::BloomFilterIndexSubBlock(const TupleStorageSubBlock &tuple_store, |
| const IndexSubBlockDescription &description, |
| const bool is_new_block, |
| void *sub_block_memory, |
| const std::size_t sub_block_memory_size) |
| : IndexSubBlock(tuple_store, |
| description, |
| is_new_block, |
| sub_block_memory, |
| sub_block_memory_size), |
| is_initialized_(false), |
| is_consistent_(false), |
| random_seed_(kBloomFilterSeed), |
| bit_array_size_in_bytes_(description.GetExtension( |
| BloomFilterIndexSubBlockDescription::bloom_filter_size)) { |
| CHECK(DescriptionIsValid(relation_, description_)) |
| << "Attempted to construct an BloomFilterIndexSubBlock from an invalid description."; |
| |
| // Store the attribute ids that are being indexed. |
| indexed_attribute_ids_.reserve(description.indexed_attribute_ids_size()); |
| for (int i = 0; i < description.indexed_attribute_ids_size(); ++i) { |
| indexed_attribute_ids_.push_back(description.indexed_attribute_ids(i)); |
| } |
| |
| // Make the bit_array_ point to sub_block_memory. |
| bit_array_.reset(static_cast<std::uint8_t*>(sub_block_memory)); |
| |
| bool is_bloom_filter_initialized = !is_new_block; |
| const std::uint32_t salt_count = description.GetExtension(BloomFilterIndexSubBlockDescription::number_of_hashes); |
| |
| // Initialize the bloom_filter_ data structure to operate on bit_array. |
| bloom_filter_.reset(new BloomFilter(random_seed_, |
| salt_count, |
| bit_array_size_in_bytes_, |
| bit_array_.get(), |
| is_bloom_filter_initialized)); |
| is_initialized_ = true; |
| is_consistent_ = true; |
| } |
| |
| BloomFilterIndexSubBlock::~BloomFilterIndexSubBlock() { |
| bit_array_.release(); // De-allocation of bit_array_ is handled by StorageBlock. |
| } |
| |
| bool BloomFilterIndexSubBlock::DescriptionIsValid(const CatalogRelationSchema &relation, |
| const IndexSubBlockDescription &description) { |
| if (!description.IsInitialized()) { |
| return false; |
| } |
| |
| if (description.sub_block_type() != IndexSubBlockDescription::BLOOM_FILTER) { |
| return false; |
| } |
| |
| // Check that all the specified index attributes are valid. |
| for (int i = 0; i < description.indexed_attribute_ids_size(); ++i) { |
| const attribute_id indexed_attribute_id = description.indexed_attribute_ids(i); |
| if (!relation.hasAttributeWithId(indexed_attribute_id)) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| std::size_t BloomFilterIndexSubBlock::EstimateBytesPerTuple(const CatalogRelationSchema &relation, |
| const IndexSubBlockDescription &description) { |
| DCHECK(DescriptionIsValid(relation, description)); |
| // Note: Returning zero here causes EstimteBytesPerBlock() to be invoked for size computation. |
| return kZeroSize; |
| } |
| |
| std::size_t BloomFilterIndexSubBlock::EstimateBytesPerBlock(const CatalogRelationSchema &relation, |
| const IndexSubBlockDescription &description) { |
| // Note: This function is only invoked when EstimateBytesPerTuple() returns zero. |
| DCHECK(DescriptionIsValid(relation, description)); |
| return description.GetExtension(BloomFilterIndexSubBlockDescription::bloom_filter_size); |
| } |
| |
| bool BloomFilterIndexSubBlock::addEntry(const tuple_id tuple) { |
| DCHECK(is_initialized_); |
| if (!is_consistent_) { |
| return false; |
| } |
| if (!tuple_store_.hasTupleWithID(tuple)) { |
| return false; |
| } |
| for (std::size_t i = 0; i < indexed_attribute_ids_.size(); ++i) { |
| const attribute_id indexed_attribute_id = indexed_attribute_ids_[i]; |
| const TypedValue tuple_value = tuple_store_.getAttributeValueTyped(tuple, indexed_attribute_id); |
| const std::uint8_t *data = static_cast<const std::uint8_t*>(tuple_value.getDataPtr()); |
| const std::size_t data_size = tuple_value.getDataSize(); |
| if (!tuple_value.isNull()) { |
| bloom_filter_->insert(data, data_size); |
| } |
| } |
| return true; |
| } |
| |
| bool BloomFilterIndexSubBlock::bulkAddEntries(const TupleIdSequence &tuples) { |
| DCHECK(is_initialized_); |
| if (!is_consistent_) { |
| return false; |
| } |
| bool didAllSucceed = true; |
| for (const tuple_id &tuple : tuples) { |
| didAllSucceed = didAllSucceed && addEntry(tuple); |
| } |
| return didAllSucceed; |
| } |
| |
| void BloomFilterIndexSubBlock::removeEntry(const tuple_id tuple) { |
| is_consistent_ = false; |
| } |
| |
| void BloomFilterIndexSubBlock::bulkRemoveEntries(const TupleIdSequence &tuples) { |
| is_consistent_ = false; |
| } |
| |
| predicate_cost_t BloomFilterIndexSubBlock::estimatePredicateEvaluationCost( |
| const ComparisonPredicate &predicate) const { |
| DCHECK(is_initialized_); |
| BloomFilterSelectivity selectivity = getSelectivityForPredicate(predicate); |
| // Note: A Bloomfilter index is only useful when it gives a zero selectivity |
| // in which case a block can be skipped entirely. |
| if (selectivity == BloomFilterSelectivity::kSelectivityNone) { |
| // Return minimum cost so that this block can be skipped altogether. |
| return predicate_cost::kConstantTime; |
| } else { |
| // Return maximum cost because this is as worse as doing a full scan of the block. |
| return predicate_cost::kInfinite; |
| } |
| } |
| |
| TupleIdSequence* BloomFilterIndexSubBlock::getMatchesForPredicate( |
| const ComparisonPredicate &predicate, |
| const TupleIdSequence *filter) const { |
| DCHECK(is_initialized_); |
| if (filter != nullptr) { |
| LOG(FATAL) << "BloomFilterIndex does not support filter evaluation with predicate."; |
| } |
| BloomFilterSelectivity selectivity = getSelectivityForPredicate(predicate); |
| if (selectivity == BloomFilterSelectivity::kSelectivityNone) { |
| // This path is invoked when there is a BloomFilter miss (true negative) |
| // and a BloomFilter index allows to skip this block entirely. |
| // A new tuple ID sequence is initialized to false for all values. |
| return new TupleIdSequence(tuple_store_.numTuples()); |
| } else if (selectivity == BloomFilterSelectivity::kSelectivityAll) { |
| // This path is invoked when there is a BloomFilter hit (possibly false positive) |
| // and a BloomFilter index does not provide much information. |
| // Note: If estimatePredicateEvaluationCost() is used by optimizer to evaluate |
| // the cost of using BloomFilter index for a BloomFilter hit, |
| // getMatchesForPredicate() will not be called in the first place itself |
| // and this path will never be taken. |
| TupleIdSequence* tuple_sequence = new TupleIdSequence(tuple_store_.numTuples()); |
| // Set all existing tuples to true, selected. |
| if (tuple_store_.isPacked()) { |
| tuple_sequence->setRange(0, tuple_store_.numTuples(), true); |
| } else { |
| for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| if (tuple_store_.hasTupleWithID(tid)) { |
| tuple_sequence->set(tid); |
| } |
| } |
| } |
| return tuple_sequence; |
| } else { |
| LOG(FATAL) << "BloomFilterIndex should never have been called."; |
| return nullptr; |
| } |
| } |
| |
| BloomFilterIndexSubBlock::BloomFilterSelectivity |
| BloomFilterIndexSubBlock::getSelectivityForPredicate(const ComparisonPredicate &predicate) const { |
| DCHECK(is_initialized_); |
| if (!is_consistent_) { |
| return BloomFilterSelectivity::kSelectivityUnknown; |
| } |
| // Bloom filter index can be currently only used to evaluate |
| // equality matching comparison predicates with static values as the right operand. |
| if (predicate.getComparison().getComparisonID() == ComparisonID::kEqual |
| && predicate.getRightOperand().hasStaticValue()) { |
| const ScalarAttribute *left_operand = static_cast<const ScalarAttribute*>(&predicate.getLeftOperand()); |
| const attribute_id attr_id_checked = left_operand->getAttribute().getID(); |
| |
| // Check if the specified attribute in the predicate is actually indexed or not. |
| bool is_attribute_indexed = false; |
| for (const attribute_id &attr_id_expected : indexed_attribute_ids_) { |
| if (attr_id_expected == attr_id_checked) { |
| is_attribute_indexed = true; |
| break; |
| } |
| } |
| if (!is_attribute_indexed) { |
| // Specified attribute not indexed, this index provides no useful information. |
| return BloomFilterSelectivity::kSelectivityUnknown; |
| } |
| |
| const ScalarLiteral *right_operand = static_cast<const ScalarLiteral*>(&predicate.getRightOperand()); |
| const std::uint8_t *test_data = static_cast<const std::uint8_t*>(right_operand->getStaticValue().getDataPtr()); |
| const std::size_t test_data_size = right_operand->getStaticValue().getDataSize(); |
| bool is_contained = bloom_filter_->contains(test_data, test_data_size); |
| |
| if (is_contained) { |
| // Bloom filter hit. Can be a false positive, a scan is required here. |
| return BloomFilterSelectivity::kSelectivityAll; |
| } else { |
| // Bloom filter miss. Definitely a true negative. Selectivity is zero. |
| return BloomFilterSelectivity::kSelectivityNone; |
| } |
| } |
| return BloomFilterSelectivity::kSelectivityUnknown; |
| } |
| |
| bool BloomFilterIndexSubBlock::rebuild() { |
| DCHECK(is_initialized_); |
| bloom_filter_->reset(); |
| bool didSucceed = true; |
| if (tuple_store_.isPacked()) { |
| for (tuple_id tid = 0; didSucceed && tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| didSucceed = addEntry(tid); |
| } |
| } else { |
| for (tuple_id tid = 0; didSucceed && tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| if (tuple_store_.hasTupleWithID(tid)) { |
| didSucceed = addEntry(tid); |
| } |
| } |
| } |
| is_consistent_ = true; |
| return didSucceed; |
| } |
| |
| } // namespace quickstep |
