论文：Oasis: An Optimal Disjoint Segmented Learned Range Filter
会议：VLDB 2024
作者：Guanduo Chen, Zhenying He, Meng Li, Siqiang Luo
简介：学习增强型数据结构激发了范围过滤器（range filter）的发展，使其相比传统的非学习型范围过滤器在假阳率（FPR）上提高了数个数量级。其核心思想是利用分段线性函数将整个键空间（key space）按顺序均匀映射到位图中。然而，这种将整个键空间均匀映射的方法存在效率低下的问题，并限制了 range filter 的准确性。
基于此，我们提出了全新的学习型范围过滤器 Oasis（Optimal Disjoint Segmented Learned Range Filter），它通过显式排除大量空范围来将键空间划分为不相交的区间，并将剩余的区间以最优的方式映射到压缩位图中。此外，Oasis 可以通过理论分析确定其最优配置。为了增强 Oasis 的适用范围，我们进一步提出了 Oasis+，它整合了学习型和非学习型过滤器的设计空间，在各种工作负载下提供了稳健的性能。我们评估了 Oasis 和 Oasis+ 在键值对存储系统 RocksDB 中的性能，使用了各种真实和合成数据集和工作负载。在 RocksDB 中，与最先进的学习型和非学习型范围过滤器相比，Oasis 和 Oasis+ 的性能提高了最多 1.4 倍和 6.2 倍。
