Lines Matching refs:range
13 Deleting a range of keys is a common pattern in RocksDB. Most systems built on top of
31 one-off features for individual users. The range deletion pattern is common as
37 through the to-be-deleted range, and issue a `Delete` for each key. This is
43 the deleted range(s). This deletes the range asynchronously, so cannot be used
50 range not affect iterators, the user can trigger `CompactRange` on the deleted
51 range. This can involve arbitrarily long waits in the compaction queue, and
52 increases write-amp. By the time it's finished, however, the range is completely
55 `DeleteFilesInRange` can be used prior to compacting the deleted range as long
57 completely contained in the deleted range. That saves write-amp because, in
62 complicated to reason about and implement. In an ideal world, deleting a range
73 We could not think of a good way to do it, however, since the start of a range
82 also has no way to detect when a range tombstone no longer covers anything and
83 is droppable. Further, it'd be possible for keys above a range tombstone to disappear
87 to the manifest approach. That is, we cannot easily detect when a range
89 to go from above a range tombstone to below, i.e., disappearing. The upside is
92 The problems with the second and third solutions indicate a need for range
95 the first solution. So, we introduced a separate meta-block for range tombstones.
96 This resolved the problem of when to obsolete range tombstones, as it's simple:
99 zeroing problem. This approach has the side benefit of constraining the range
100 tombstones seen during reads to ones in a similar key-range.
105 *When there are range tombstones in an SST, they are segregated in a separate meta-block*
111 *Logical range tombstones (left) and their corresponding physical key-value representation (right)*
116 `WriteBatch` stores range tombstones in its buffer which are logged to the WAL and
117 then applied to a dedicated range tombstone memtable during `Write`. Later in
118 the background the range tombstone memtable and its corresponding data memtable
119 are flushed together into a single SST with a range tombstone meta-block. SSTs
120 periodically undergo compaction which rewrites SSTs with point data and range
123 We chose to use a dedicated memtable for range tombstones. The memtable
125 case, which is the memtable contains zero or a small number of range tombstones.
126 The range tombstones are segregated to a separate memtable for the same reason
127 we segregated range tombstones in SSTs. That is, we did not know how to
128 interleave the range tombstone with point data in a way that we would be able to
134 *Lifetime of point keys and range tombstones in RocksDB*
137 During flush and compaction, we chose to write out all non-obsolete range
139 doesn't bring asymptotic improvement to queries over range data. Ideally, we
143 which further complicates the range tombstone meta-block encoding; and (2) even
144 if we implement this, the range tombstone memtable still needs to be linearly
151 In point lookups, we aggregate range tombstones in an unordered vector as we
156 In iterators, we aggregate range tombstones into a skyline as we visit live
157 …mine whether a key is covered. The skyline keeps track of the most recent range tombstone found to…
163 binary-searchable. With overlapping range tombstones, to achieve efficient
174 …ince range tombstones have a dedicated skiplist memtable, the complexity of inserting is O(log(T))…
176 Reading in the presence of v1 range tombstones, however, is much slower than reads
178 range tombstone memtables/meta-blocks.
180 Iterating in a database with v1 range tombstones is usually slower than in a
186 a constant-time operation (excluding edge cases, e.g., many range tombstones
192 root cause is range tombstones are not stored or cached in a format that can be
199 The key idea of the redesign is that, instead of globally collapsing range tombstones,
202 * no range tombstones overlap; and
203 * range tombstones are ordered by start key.
205 Combined, these properties make range tombstones binary searchable. This
207 easily cache many of these range tombstone fragments on the read path.
215 When an SST file is opened, its range tombstones are fragmented and cached. For point
216 lookups, we binary search each file's fragmented range tombstones for one that covers
220 the range tombstone).
222 For range scans, we create iterators over all the fragmented range
223 tombstones and store them in a list, seeking each one to cover the start key of the range
225 advancing range tombstone iterators as necessary. In effect, we implicitly create a skyline.
227 its own range tombstone iterator, querying range tombstones requires key comparisons (and
229 collapsed representation of all range tombstones). As a result, very long range scans may become
230 slower than before, but short range scans are an order of magnitude faster, which are the
231 more common class of range scan.
235 …d the performance of this new design, we used `db_bench` to compare point lookup, short range scan,
236 and long range scan performance across:
242 In these benchmarks, we used a database with 5 million data keys, and 10000 range tombstones (ignor…
244 Writing the range tombstones ensures that most of them are not compacted away, and we have more tom…
249 … from the seek position for short range scans, and advanced up to 1000 keys away from the seek pos…
252 …ughput is due to limited I/Os and little time spent on decompression. The range tombstone blocks a…
277 Note that memtable range tombstones are fragmented every read; for now this is acceptable,
278 since we expect there to be relatively few range tombstones in memtables (and users can
279 enforce this by keeping track of the number of memtable range deletions and manually flushing
281 range tombstones in memory to avoid this work.
283 Another future optimization is to create a new format version that requires range tombstones to