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