Aeris Filter: A Strongly and Monotonically Adaptive Range Filter

Range filters are probabilistic data structures used to efficiently perform range emptiness queries, with applications in databases, big data analytics, and key-value stores. Modern range filters are compact and can guarantee a bounded false positive rate irrespective of the spatial skew in queries. However, existing range filters are still susceptible to temporal skew: in skewed workloads where a few queries are repeated disproportionately more often, the false positive rate of a range filter may be unbounded. We introduce the Aeris filter, an adaptive expandable range filter that guarantees a robust false positive rate irrespective of spatial or temporal skew. The Aeris filter achieves this by dynamically resolving and adapting to false positives. More specifically, the Aeris filter is monotonic adaptive, i.e., it never forgets a previously encountered false positive. The Aeris filter introduces a novel encoding scheme to implement adaptivity in a range filter with no additional space or operational overhead. Furthermore, the Aeris filter deamortizes the I/O cost to expand monotonic adaptive filters by utilizing on-disk adaptivity structures, resulting in fewer system disruptions. Experimental results demonstrate that the Aeris filter achieves up to a 10× reduction in false positive rates on skewed query distributions compared to other non-adaptive range filters. When integrated into a database, the Aeris filter delivers 1.5-8× higher throughput for adversarial workloads, and is able to deliver this high throughput using a cache of smaller size. The Aeris filter also reduces expansion overhead by up to 3× compared to the Memento filter, a spatially-robust expandable range filter. These improvements ensure scalable, efficient, and adaptive range query handling in dynamic environments.