remix · research · also Range-query-Efficient Multi-table IndeX

REMIX

REMIX is an index that records the merged key order of multiple immutable sorted runs without physically merging their records.

Mechanism: anchor keys, cursor offsets and run selectors support seeking and comparison-free advancement through the indexed view. Rebuilding still costs work. [1]

Implementation: the pinned RemixDB prototype adds optional hash tags, but a tag match still requires full-key verification. This implementation includes changes made after the paper. [2] [3]

Relations

related

Log-structured merge-tree, Sorted run, Tiered compaction, Read amplification, Succinct range filter

Citations

1. Zhong, Chen, Wu and Jiang. REMIX: Efficient Range Query for LSM-trees. FAST 2021, pp. 51-64; sections 3-5. Author-hosted full paper. (accessed 2026-11-10)
2. RemixDB author implementation, pinned README: post-paper compressed keys and hash-tag optimizations. (accessed 2026-11-10)
3. RemixDB pinned sst.c: tagged full-key matching, tombstone-aware iteration and rebuild-path selection. (accessed 2026-11-10)

Further reading

4. Hesela: range filtering versus cached merge order. (accessed 2026-11-10)

JSON: /data/terms/remix.json