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 #pragma once 7 8 #include <list> 9 #include <string> 10 #include <unordered_map> 11 #include "db/dbformat.h" 12 #include "index_builder.h" 13 #include "rocksdb/options.h" 14 #include "rocksdb/slice.h" 15 #include "rocksdb/slice_transform.h" 16 #include "table/block_based/block.h" 17 #include "table/block_based/filter_block_reader_common.h" 18 #include "table/block_based/full_filter_block.h" 19 #include "util/autovector.h" 20 21 namespace ROCKSDB_NAMESPACE { 22 23 class PartitionedFilterBlockBuilder : public FullFilterBlockBuilder { 24 public: 25 explicit PartitionedFilterBlockBuilder( 26 const SliceTransform* prefix_extractor, bool whole_key_filtering, 27 FilterBitsBuilder* filter_bits_builder, int index_block_restart_interval, 28 const bool use_value_delta_encoding, 29 PartitionedIndexBuilder* const p_index_builder, 30 const uint32_t partition_size); 31 32 virtual ~PartitionedFilterBlockBuilder(); 33 34 void AddKey(const Slice& key) override; 35 void Add(const Slice& key) override; 36 37 virtual Slice Finish(const BlockHandle& last_partition_block_handle, 38 Status* status) override; 39 40 private: 41 // Filter data 42 BlockBuilder index_on_filter_block_builder_; // top-level index builder 43 BlockBuilder 44 index_on_filter_block_builder_without_seq_; // same for user keys 45 struct FilterEntry { 46 std::string key; 47 Slice filter; 48 }; 49 std::list<FilterEntry> filters; // list of partitioned indexes and their keys 50 std::unique_ptr<IndexBuilder> value; 51 std::vector<std::unique_ptr<const char[]>> filter_gc; 52 bool finishing_filters = 53 false; // true if Finish is called once but not complete yet. 54 // The policy of when cut a filter block and Finish it 55 void MaybeCutAFilterBlock(const Slice* next_key); 56 // Currently we keep the same number of partitions for filters and indexes. 57 // This would allow for some potentioal optimizations in future. If such 58 // optimizations did not realize we can use different number of partitions and 59 // eliminate p_index_builder_ 60 PartitionedIndexBuilder* const p_index_builder_; 61 // The desired number of keys per partition 62 uint32_t keys_per_partition_; 63 // The number of keys added to the last partition so far 64 uint32_t keys_added_to_partition_; 65 BlockHandle last_encoded_handle_; 66 }; 67 68 class PartitionedFilterBlockReader : public FilterBlockReaderCommon<Block> { 69 public: 70 PartitionedFilterBlockReader(const BlockBasedTable* t, 71 CachableEntry<Block>&& filter_block); 72 73 static std::unique_ptr<FilterBlockReader> Create( 74 const BlockBasedTable* table, FilePrefetchBuffer* prefetch_buffer, 75 bool use_cache, bool prefetch, bool pin, 76 BlockCacheLookupContext* lookup_context); 77 IsBlockBased()78 bool IsBlockBased() override { return false; } 79 bool KeyMayMatch(const Slice& key, const SliceTransform* prefix_extractor, 80 uint64_t block_offset, const bool no_io, 81 const Slice* const const_ikey_ptr, GetContext* get_context, 82 BlockCacheLookupContext* lookup_context) override; 83 bool PrefixMayMatch(const Slice& prefix, 84 const SliceTransform* prefix_extractor, 85 uint64_t block_offset, const bool no_io, 86 const Slice* const const_ikey_ptr, 87 GetContext* get_context, 88 BlockCacheLookupContext* lookup_context) override; 89 90 size_t ApproximateMemoryUsage() const override; 91 92 private: 93 BlockHandle GetFilterPartitionHandle(const CachableEntry<Block>& filter_block, 94 const Slice& entry) const; 95 Status GetFilterPartitionBlock( 96 FilePrefetchBuffer* prefetch_buffer, const BlockHandle& handle, 97 bool no_io, GetContext* get_context, 98 BlockCacheLookupContext* lookup_context, 99 CachableEntry<ParsedFullFilterBlock>* filter_block) const; 100 101 using FilterFunction = bool (FullFilterBlockReader::*)( 102 const Slice& slice, const SliceTransform* prefix_extractor, 103 uint64_t block_offset, const bool no_io, 104 const Slice* const const_ikey_ptr, GetContext* get_context, 105 BlockCacheLookupContext* lookup_context); 106 bool MayMatch(const Slice& slice, const SliceTransform* prefix_extractor, 107 uint64_t block_offset, bool no_io, const Slice* const_ikey_ptr, 108 GetContext* get_context, 109 BlockCacheLookupContext* lookup_context, 110 FilterFunction filter_function) const; 111 void CacheDependencies(bool pin) override; 112 113 const InternalKeyComparator* internal_comparator() const; 114 bool index_key_includes_seq() const; 115 bool index_value_is_full() const; 116 117 protected: 118 std::unordered_map<uint64_t, CachableEntry<ParsedFullFilterBlock>> 119 filter_map_; 120 }; 121 122 } // namespace ROCKSDB_NAMESPACE 123