Range Reduce

Log-structured merge (LSM) trees are the backbone of modern databases, powering high-ingestion workloads in systems like RocksDB, Cassandra, and LevelDB. However, they suffer from poor range query performance due to high read amplification, redundant merging, and excessive compactions.

Problem: Excessive Reads & Merging

LSM-trees store data in multiple sorted runs across hierarchical levels. While this design optimizes writes, it creates inefficiencies for range queries:

High Read Amplification: Queries must scan and merge multiple sorted runs, leading to excessive disk I/O and CPU usage.
Redundant Work: Repeated queries must reprocess and merge the same data, wasting resources.
Compaction Overhead: Frequent updates and deletes generate “logically invalid” entries, which persist until removed by costly compactions.

Introducing RangeReduce

RangeReduce is a novel optimization that piggybacks on range queries to improve future performance by proactively compacting data. Instead of repeatedly reading and merging duplicate entries, RangeReduce:

Sort-merges data once during a range query.
Writes back only valid entries at a higher level in the LSM-tree.
Reduces read and space amplification for subsequent queries.

By eliminating duplicate entries early and delaying unnecessary compactions, RangeReduce speeds up range queries and reduces database bloat.

The Trade-Off

Writing the merged data back to storage after a range query is not free. Instead of compacting eagerly on every query, RangeReduce runs a lightweight cost-benefit check that decides when a query-driven compaction pays off, so faster range queries never come at the cost of high write amplification. The compactions it performs are work the tree would otherwise do later, which leaves the shallower levels less saturated and means fewer compactions in the future.

Real-World Impact

Implemented on RocksDB, RangeReduce outperforms the state of the art on range-query-intensive workloads, delivering:

up to 18% lower average range-query latency
up to 90% lower compaction debt
12% less overall data movement (reads and writes)
up to 20% lower space amplification

For workloads with frequent updates and deletes, it keeps the storage engine fast and compact.

Conclusion

RangeReduce represents a new approach to LSM-tree optimization, tackling one of its biggest challenges—slow range queries. By leveraging existing reads to optimize future queries, it brings better space utilization, lower read amplification, and fewer compactions to modern storage engines.

For more details, check out:

Log-structured merge (LSM) trees are widely used in the storage layer of modern ingestion-optimized data stores. The high ingestion throughput, however, comes at the cost of sub-optimal range query (RQ) performance. This is because LSM-trees arrange the data as a hierarchical collection of sorted runs, which implies that every RQ must (i) probe all sorted runs to locate the qualifying entries, (ii) scan and merge the entries from all qualifying runs, (iii) filter out the logically invalidated entries by updates and deletes on the fly, and (iv) return the most recent version of each qualifying key. This leads to high read amplification and significant redundant work in terms of superfluous I/Os to storage and wasted CPU cycles, which is exacerbated in the presence of updates and deletes. Additionally, during compactions, the same data is read and written multiple times, further amplifying the read and write amplification. In this paper, we introduce RangeReduce, an RQ-optimized LSM-engine that uses RQs as a hint to compact data that is already read into memory as part of the query, and thereby, improves the overall performance of the storage engine.