hesela.devSecondary range delete
A secondary range delete selects records by an interval on an attribute other than the storage structure's sort key.
Illustration: records sorted by document ID can have timestamps 3, 9 and 4 in ID order. Deleting timestamps below 5 selects the first and third records, not one contiguous ID interval. A small result set can therefore occupy many pages.
RocksDB DeleteRange accepts a range in the column family's key order. It does not turn an arbitrary value predicate into that range; application-side key discovery or a different layout is a separate step. [1]
Lethe separates scheduling deletion with FADE from arranging data for secondary predicates with KiWi. Within a delete tile, pages follow the delete attribute while entries inside each page retain sort-key order. Fully qualifying pages can be dropped; mixed boundary pages still require inspection and rewriting. [2]
The 2023 Lethe+ extension uses KiWi+ to tune tile size per level. Larger tiles can favor secondary deletion while increasing point or short-range lookup work. This is a workload-dependent layout trade-off, not a general claim that secondary deletes are free. [3]
Relations
Limitations
- Removing database pages does not certify erasure of replicas, backups or remapped flash. [5]
Citations
- Madan and Kryczka. DeleteRange: A New Native RocksDB Operation (2018).
- Boston University. Lethe: Enabling Efficient Deletes in LSMs; FADE and KiWi.
- Sarkar et al. Enabling Timely and Persistent Deletion in LSM-Engines. ACM TODS 48(3), Article 8 (2023), sections 4.2-4.3.
- Hesela. LSM tombstones: deleted is not yet reclaimed.
Further reading
Sources & caveats
- The three-record example is a constructed illustration, not an engine trace or benchmark.
- The 2020 project explains KiWi; the 2023 journal extension adds per-level KiWi+. Their results are not treated as independent replications.
- The operation category is broader than either research implementation; the status field describes the layouts discussed here.