rosetta-range-filter · research · also Rosetta

Rosetta range filter

Rosetta is a probabilistic range filter that represents binary key prefixes in a hierarchy of Bloom filters.

A query is split into aligned power-of-two intervals, each represented by a binary prefix. A positive prefix can trigger deeper checks, called doubting, before the filter accepts the range as possibly nonempty. [1]

The paper's storage integration rebuilds a filter for each output SST after compaction. Its tuning trades probe work against false positives under a memory budget. [1]

For unsigned four-bit integers, inclusive [5,10] decomposes into [5,5], [6,7], [8,9] and [10,10]. These four cover blocks are not a count of recursive probes; [5,5] alone needs one block. [2]

Relations

related
Succinct range filter, Bloom filter, Prefix Bloom filter, Sorted string table

Limitations

  • A possibly nonempty result still requires checking stored data. [1]

Citations

  1. Luo et al. Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. SIGMOD 2020, sections 2-5. DOI: 10.1145/3318464.3389731. (accessed 2026-11-08)
  2. Hesela: exact dyadic-cover examples and exhaustive tests (CC0) (accessed 2026-11-08)

Further reading

  1. Hesela: cover intervals versus recursive filter probes (accessed 2026-11-08)
Sources & caveats
  • The SIGMOD 2020 study uses RocksDB 6.3.6 and empty-query workloads; it is not a current-engine performance guarantee. [1]
  • The accompanying code checks integer interval geometry, not Rosetta or a Bloom implementation. [2]

JSON: /data/terms/rosetta-range-filter.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Rosetta range filter. Hesela. 2026-11-08. https://hesela.dev/terms/rosetta-range-filter/