ceph/src/rocksdb/table/block_based/filter_block_reader_common.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6
   7 #include "table/block_based/filter_block_reader_common.h"
   8
   9 #include "monitoring/perf_context_imp.h"
  10 #include "table/block_based/block_based_table_reader.h"
  11 #include "table/block_based/parsed_full_filter_block.h"
  12
  13 namespace ROCKSDB_NAMESPACE {
  14
  15 template <typename TBlocklike>
  16 Status FilterBlockReaderCommon<TBlocklike>::ReadFilterBlock(
  17     const BlockBasedTable* table, FilePrefetchBuffer* prefetch_buffer,
  18     const ReadOptions& read_options, bool use_cache, GetContext* get_context,
  19     BlockCacheLookupContext* lookup_context,
  20     CachableEntry<TBlocklike>* filter_block, BlockType block_type) {
  21   PERF_TIMER_GUARD(read_filter_block_nanos);
  22
  23   assert(table);
  24   assert(filter_block);
  25   assert(filter_block->IsEmpty());
  26
  27   const BlockBasedTable::Rep* const rep = table->get_rep();
  28   assert(rep);
  29
  30   const Status s =
  31       table->RetrieveBlock(prefetch_buffer, read_options, rep->filter_handle,
  32                            UncompressionDict::GetEmptyDict(), filter_block,
  33                            block_type, get_context, lookup_context,
  34                            /* for_compaction */ false, use_cache,
  35                            /* wait_for_cache */ true, /* async_read */ false);
  36
  37   return s;
  38 }
  39
  40 template <typename TBlocklike>
  41 const SliceTransform*
  42 FilterBlockReaderCommon<TBlocklike>::table_prefix_extractor() const {
  43   assert(table_);
  44
  45   const BlockBasedTable::Rep* const rep = table_->get_rep();
  46   assert(rep);
  47
  48   return rep->prefix_filtering ? rep->table_prefix_extractor.get() : nullptr;
  49 }
  50
  51 template <typename TBlocklike>
  52 bool FilterBlockReaderCommon<TBlocklike>::whole_key_filtering() const {
  53   assert(table_);
  54   assert(table_->get_rep());
  55
  56   return table_->get_rep()->whole_key_filtering;
  57 }
  58
  59 template <typename TBlocklike>
  60 bool FilterBlockReaderCommon<TBlocklike>::cache_filter_blocks() const {
  61   assert(table_);
  62   assert(table_->get_rep());
  63
  64   return table_->get_rep()->table_options.cache_index_and_filter_blocks;
  65 }
  66
  67 template <typename TBlocklike>
  68 Status FilterBlockReaderCommon<TBlocklike>::GetOrReadFilterBlock(
  69     bool no_io, GetContext* get_context,
  70     BlockCacheLookupContext* lookup_context,
  71     CachableEntry<TBlocklike>* filter_block, BlockType block_type,
  72     Env::IOPriority rate_limiter_priority) const {
  73   assert(filter_block);
  74
  75   if (!filter_block_.IsEmpty()) {
  76     filter_block->SetUnownedValue(filter_block_.GetValue());
  77     return Status::OK();
  78   }
  79
  80   ReadOptions read_options;
  81   read_options.rate_limiter_priority = rate_limiter_priority;
  82   if (no_io) {
  83     read_options.read_tier = kBlockCacheTier;
  84   }
  85
  86   return ReadFilterBlock(table_, nullptr /* prefetch_buffer */, read_options,
  87                          cache_filter_blocks(), get_context, lookup_context,
  88                          filter_block, block_type);
  89 }
  90
  91 template <typename TBlocklike>
  92 size_t FilterBlockReaderCommon<TBlocklike>::ApproximateFilterBlockMemoryUsage()
  93     const {
  94   assert(!filter_block_.GetOwnValue() || filter_block_.GetValue() != nullptr);
  95   return filter_block_.GetOwnValue()
  96              ? filter_block_.GetValue()->ApproximateMemoryUsage()
  97              : 0;
  98 }
  99
 100 template <typename TBlocklike>
 101 bool FilterBlockReaderCommon<TBlocklike>::RangeMayExist(
 102     const Slice* iterate_upper_bound, const Slice& user_key_without_ts,
 103     const SliceTransform* prefix_extractor, const Comparator* comparator,
 104     const Slice* const const_ikey_ptr, bool* filter_checked,
 105     bool need_upper_bound_check, bool no_io,
 106     BlockCacheLookupContext* lookup_context,
 107     Env::IOPriority rate_limiter_priority) {
 108   if (!prefix_extractor || !prefix_extractor->InDomain(user_key_without_ts)) {
 109     *filter_checked = false;
 110     return true;
 111   }
 112   Slice prefix = prefix_extractor->Transform(user_key_without_ts);
 113   if (need_upper_bound_check &&
 114       !IsFilterCompatible(iterate_upper_bound, prefix, comparator)) {
 115     *filter_checked = false;
 116     return true;
 117   } else {
 118     *filter_checked = true;
 119     return PrefixMayMatch(prefix, no_io, const_ikey_ptr,
 120                           /* get_context */ nullptr, lookup_context,
 121                           rate_limiter_priority);
 122   }
 123 }
 124
 125 template <typename TBlocklike>
 126 bool FilterBlockReaderCommon<TBlocklike>::IsFilterCompatible(
 127     const Slice* iterate_upper_bound, const Slice& prefix,
 128     const Comparator* comparator) const {
 129   // Try to reuse the bloom filter in the SST table if prefix_extractor in
 130   // mutable_cf_options has changed. If range [user_key, upper_bound) all
 131   // share the same prefix then we may still be able to use the bloom filter.
 132   const SliceTransform* const prefix_extractor = table_prefix_extractor();
 133   if (iterate_upper_bound != nullptr && prefix_extractor) {
 134     if (!prefix_extractor->InDomain(*iterate_upper_bound)) {
 135       return false;
 136     }
 137     Slice upper_bound_xform = prefix_extractor->Transform(*iterate_upper_bound);
 138     // first check if user_key and upper_bound all share the same prefix
 139     if (comparator->CompareWithoutTimestamp(prefix, false, upper_bound_xform,
 140                                             false) != 0) {
 141       // second check if user_key's prefix is the immediate predecessor of
 142       // upper_bound and have the same length. If so, we know for sure all
 143       // keys in the range [user_key, upper_bound) share the same prefix.
 144       // Also need to make sure upper_bound are full length to ensure
 145       // correctness
 146       if (!full_length_enabled_ ||
 147           iterate_upper_bound->size() != prefix_extractor_full_length_ ||
 148           !comparator->IsSameLengthImmediateSuccessor(prefix,
 149                                                       *iterate_upper_bound)) {
 150         return false;
 151       }
 152     }
 153     return true;
 154   } else {
 155     return false;
 156   }
 157 }
 158
 159 // Explicitly instantiate templates for both "blocklike" types we use.
 160 // This makes it possible to keep the template definitions in the .cc file.
 161 template class FilterBlockReaderCommon<Block>;
 162 template class FilterBlockReaderCommon<ParsedFullFilterBlock>;
 163
 164 }  // namespace ROCKSDB_NAMESPACE