]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae FG |
5 | // |
6 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
9 | ||
10 | #pragma once | |
11 | #include <cstdint> | |
12 | #include <functional> | |
13 | #include <limits> | |
14 | #include <vector> | |
f67539c2 | 15 | #include "memory/arena.h" |
7c673cae | 16 | #include "port/port.h" |
7c673cae FG |
17 | #include "util/autovector.h" |
18 | ||
f67539c2 | 19 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
20 | |
21 | class Comparator; | |
22 | struct FileMetaData; | |
23 | struct FdWithKeyRange; | |
24 | struct FileLevel; | |
25 | ||
26 | // The file tree structure in Version is prebuilt and the range of each file | |
27 | // is known. On Version::Get(), it uses binary search to find a potential file | |
28 | // and then check if a target key can be found in the file by comparing the key | |
29 | // to each file's smallest and largest key. The results of these comparisons | |
30 | // can be reused beyond checking if a key falls into a file's range. | |
31 | // With some pre-calculated knowledge, each key comparison that has been done | |
32 | // can serve as a hint to narrow down further searches: if a key compared to | |
33 | // be smaller than a file's smallest or largest, that comparison can be used | |
34 | // to find out the right bound of next binary search. Similarly, if a key | |
35 | // compared to be larger than a file's smallest or largest, it can be utilized | |
36 | // to find out the left bound of next binary search. | |
37 | // With these hints: it can greatly reduce the range of binary search, | |
38 | // especially for bottom levels, given that one file most likely overlaps with | |
39 | // only N files from level below (where N is max_bytes_for_level_multiplier). | |
40 | // So on level L, we will only look at ~N files instead of N^L files on the | |
41 | // naive approach. | |
42 | class FileIndexer { | |
43 | public: | |
44 | explicit FileIndexer(const Comparator* ucmp); | |
45 | ||
46 | size_t NumLevelIndex() const; | |
47 | ||
48 | size_t LevelIndexSize(size_t level) const; | |
49 | ||
50 | // Return a file index range in the next level to search for a key based on | |
51 | // smallest and largest key comparison for the current file specified by | |
52 | // level and file_index. When *left_index < *right_index, both index should | |
53 | // be valid and fit in the vector size. | |
54 | void GetNextLevelIndex(const size_t level, const size_t file_index, | |
55 | const int cmp_smallest, const int cmp_largest, | |
56 | int32_t* left_bound, int32_t* right_bound) const; | |
57 | ||
58 | void UpdateIndex(Arena* arena, const size_t num_levels, | |
59 | std::vector<FileMetaData*>* const files); | |
60 | ||
61 | enum { | |
62 | // MSVC version 1800 still does not have constexpr for ::max() | |
f67539c2 | 63 | kLevelMaxIndex = ROCKSDB_NAMESPACE::port::kMaxInt32 |
7c673cae FG |
64 | }; |
65 | ||
66 | private: | |
67 | size_t num_levels_; | |
68 | const Comparator* ucmp_; | |
69 | ||
70 | struct IndexUnit { | |
71 | IndexUnit() | |
72 | : smallest_lb(0), largest_lb(0), smallest_rb(-1), largest_rb(-1) {} | |
73 | // During file search, a key is compared against smallest and largest | |
74 | // from a FileMetaData. It can have 3 possible outcomes: | |
75 | // (1) key is smaller than smallest, implying it is also smaller than | |
76 | // larger. Precalculated index based on "smallest < smallest" can | |
77 | // be used to provide right bound. | |
78 | // (2) key is in between smallest and largest. | |
79 | // Precalculated index based on "smallest > greatest" can be used to | |
80 | // provide left bound. | |
81 | // Precalculated index based on "largest < smallest" can be used to | |
82 | // provide right bound. | |
83 | // (3) key is larger than largest, implying it is also larger than smallest. | |
84 | // Precalculated index based on "largest > largest" can be used to | |
85 | // provide left bound. | |
86 | // | |
87 | // As a result, we will need to do: | |
88 | // Compare smallest (<=) and largest keys from upper level file with | |
89 | // smallest key from lower level to get a right bound. | |
90 | // Compare smallest (>=) and largest keys from upper level file with | |
91 | // largest key from lower level to get a left bound. | |
92 | // | |
93 | // Example: | |
94 | // level 1: [50 - 60] | |
95 | // level 2: [1 - 40], [45 - 55], [58 - 80] | |
96 | // A key 35, compared to be less than 50, 3rd file on level 2 can be | |
97 | // skipped according to rule (1). LB = 0, RB = 1. | |
98 | // A key 53, sits in the middle 50 and 60. 1st file on level 2 can be | |
99 | // skipped according to rule (2)-a, but the 3rd file cannot be skipped | |
100 | // because 60 is greater than 58. LB = 1, RB = 2. | |
101 | // A key 70, compared to be larger than 60. 1st and 2nd file can be skipped | |
102 | // according to rule (3). LB = 2, RB = 2. | |
103 | // | |
104 | // Point to a left most file in a lower level that may contain a key, | |
105 | // which compares greater than smallest of a FileMetaData (upper level) | |
106 | int32_t smallest_lb; | |
107 | // Point to a left most file in a lower level that may contain a key, | |
108 | // which compares greater than largest of a FileMetaData (upper level) | |
109 | int32_t largest_lb; | |
110 | // Point to a right most file in a lower level that may contain a key, | |
111 | // which compares smaller than smallest of a FileMetaData (upper level) | |
112 | int32_t smallest_rb; | |
113 | // Point to a right most file in a lower level that may contain a key, | |
114 | // which compares smaller than largest of a FileMetaData (upper level) | |
115 | int32_t largest_rb; | |
116 | }; | |
117 | ||
118 | // Data structure to store IndexUnits in a whole level | |
119 | struct IndexLevel { | |
120 | size_t num_index; | |
121 | IndexUnit* index_units; | |
122 | ||
123 | IndexLevel() : num_index(0), index_units(nullptr) {} | |
124 | }; | |
125 | ||
126 | void CalculateLB( | |
127 | const std::vector<FileMetaData*>& upper_files, | |
128 | const std::vector<FileMetaData*>& lower_files, IndexLevel* index_level, | |
129 | std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op, | |
130 | std::function<void(IndexUnit*, int32_t)> set_index); | |
131 | ||
132 | void CalculateRB( | |
133 | const std::vector<FileMetaData*>& upper_files, | |
134 | const std::vector<FileMetaData*>& lower_files, IndexLevel* index_level, | |
135 | std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op, | |
136 | std::function<void(IndexUnit*, int32_t)> set_index); | |
137 | ||
138 | autovector<IndexLevel> next_level_index_; | |
139 | int32_t* level_rb_; | |
140 | }; | |
141 | ||
f67539c2 | 142 | } // namespace ROCKSDB_NAMESPACE |