Succinct Range Filters

• Published in: ACM transactions on database systems 2020-07, Vol.45 (2), p.1-31
• Main Authors: Zhang, Huanchen, Lim, Hyeontaek, Leis, Viktor, Andersen, David G., Kaminsky, Michael, Keeton, Kimberly, Pavlo, Andrew
• Format: Article
• Language: English
• ISSN: 0362-5915; 1557-4644
• DOI: 10.1145/3375660

We present the Succinct Range Filter (SuRF), a fast and compact data structure for approximate membership tests. Unlike traditional Bloom filters, SuRF supports both single-key lookups and common range queries: open-range queries, closed-range queries, and range counts. SuRF is based on a new data structure called the Fast Succinct Trie (FST) that matches the point and range query performance of state-of-the-art order-preserving indexes, while consuming only 10 bits per trie node. The false-positive rates in SuRF for both point and range queries are tunable to satisfy different application needs. We evaluate SuRF in RocksDB as a replacement for its Bloom filters to reduce I/O by filtering requests before they access on-disk data structures. Our experiments on a 100-GB dataset show that replacing RocksDB’s Bloom filters with SuRFs speeds up open-seek (without upper-bound) and closed-seek (with upper-bound) queries by up to 1.5× and 5× with a modest cost on the worst-case (all-missing) point query throughput due to slightly higher false-positive rate.