学习增强型数据结构推动了范围过滤器的发展，使其相较于传统的非学习型范围过滤器，显著降低了误判率（FPR）。其核心思想是采用分段线性函数，将整个键空间均匀地映射到位图上。然而，这种均匀映射导致空间利用率低下，从而影响FPR。那么如何在空间占用和FPR之间达到更好的权衡呢？本次为大家带来数据库领域顶级会议VLDB的论文：《Oasis: An Optimal Disjoint Segmented Learned Range Filter》范围过滤器的重要性：范围查询是数据库中的基本操作，它从键集D中检索位于指定查询范围l, r内的所有记录。范围查询有着广泛的应用场景，例如时间序列数据中的相似性搜索和异常检测。然而，范围查询也是I/O开销非常高的操作，通常需要扫描整个数据集以识别所有符合条件的记录。为了解决这个问题，学者们提出了范围过滤器，其可以快速判断在给定查询范围内是否有记录。范围过滤器可能会有假阳性，但可以保证没有假阴性。一旦范围过滤器确认在范围内不存在记录，整个范围查询就可以立即安全地终止，而无需访问磁盘。这样提前终止操作避免了不必要的数据扫描，大大提高了查询效率。现有范围过滤器：最先进的范围过滤器可以分为两类：基于前缀的范围过滤器和基于学习的范围过滤器。其中SNARF为首个基于学习的范围过滤器，相比最先进的基于前缀的过滤器，它将误判率（FPR）降低了一个数量级以上。SNARF的基本思想是基于学习的范围编码：（1）将整个键空间划分为多个相邻的区间，每个区间包含相同数量的键；（2）为每个区间分配一个固定长度的位图；（3）为每个区间训练一个线性函数，将区间内的每个键映射到对应位图中的一个特定位，并将该位设置为1。这种方法将两个相邻键之间的空范围映射到位图段中一系列连续的零位。在范围查询过程中，查询的左/右边界被映射到位图中的某个位，接着检查这两个映射位之间是否存在任何非零位。然而，在处理大范围查询时，SNARF的空间利用率十分低下。如图1所示，SNARF将整个键空间划分成了[0, 1100]以及[1100, 1500]两个区间，并为每个区间均匀分配了一个40位的位图以及一个用于将区间内的键映射到对应位图位置中的学习模型。在这个例子中，SNARF将大范围的空区间（20, 1000）编码为一个35位的位图，从第1位到第35位，占用了将近一半的空间预算。因此，在内存预算固定的情况下，其他相对较小的空区间只能分配较短的位图。当查询落在这些小范围内时，将会带来很高的FPR。因此，论文提出了以下三个改进点： 1）记录代替编码：为了避免大范围空区间造成过多的内存消耗，论文提出直接记录区间边界，而不是将整个区间编码为长位图段。例如，在图1中，SNARF分配了过多的位来编码从20到1000的空区间。而论文通过明确记录这些空区间的边界（称为空间修剪策略），避免对它们进行编码。如图1(A)所示，键空间被分割为两个不相交的区间：[0, 20]和[1000, 1500]。此时，范围查询[4, 6]被映射到第4至第6个位，它们全为零，因此返回空。查询[24, 26]因为落在被修剪的区间内，因此返回空。然而，记录边界可能会引入额外的空间开销，因此如何在编码和记录之间平衡以获得理想的查询性能，是一个需要面对的挑战。2）位图分配策略：在修剪掉那些大范围空区间后，剩余的键空间将被划分为多个不相交的区间，这引发了另一个问题：如何为每个区间的位图分配内存预算。一个简单的方法是按照每个区间内键的数量成比例地分配位图位数。然而，当不同区间的长度差异显著时，这种策略可能不够理想。例如，在图1(A)中，第一个小区间[0, 20]包含三个键，而第二个大25倍的区间[1000, 1500]则只有六个键。因此，第二个区间中的每个位需要覆盖比第一个区间大的多的空间，导致位的利用不平衡。为了解决这个问题，论文引入了一个名为BsR的度量指标，以及一种优化整体BsR的方法。BsR表示在一个区间内每个位所覆盖的平均范围长度，计算方法是区间长度除以其位图中的位数。较低的BsR意味着更好的查询性能（即更低的FPR）。为了实现全局最优的查询性能，论文提出了一种位图分配方法，称为罗宾汉分配法，它从BsR较低的区间中“抢”位分配给BsR较高的区间。例如，在图1(B)中，通过从第一个区间重新分配位给第二个区间，可以准确回答前三个查询。为了实现理想的性能，挑战在于如何通过罗宾汉分配方法在区间之间实现最佳的位图分配。3）结合基于学习的方法和基于前缀的方法。论文注意到目前缺乏对这两类方法在各种键分布下性能的全面比较。为填补这一空白，论文开发了一个分析框架，能够估算给定键分布下两种编码方法的假阳性率（FPR）。初步发现表明，基于学习的方法更适合密集的键分布，而基于前缀的方法更适合稀疏的键分布。稀疏分布意味着在固定长度的范围内键的数量较少，而密集分布则意味着在相同范围内键的数量较多。如图 1(B) 所示，第一个区间[0, 20]为密集分布，而第二个区间[1000, 1500]为稀疏分布。在此基础上，论文提出将基于前缀的方法和基于学习的方法结合，以实现更强的查询性能。挑战在于如何为每个区间选择合适的编码方法。Oasis：基于上述优化，论文提出了Oasis（Optimal Disjoint Segmented Learned Range Filter），这是一种新颖的学习型范围过滤器，其结合了空间修剪和罗宾汉分配法。Oasis+：Oasis+提供了一种全新的视角，通过结合前缀编码和基于学习的编码来提升查询性能。Oasis+采用了一种两层嵌套循环构建方法，代价是略微增加了构建时间，但在不同的空间预算下都能达到较优的FPR。如图2所示，Oasis由一个模型数组和压缩位图组成。模型数组负责记录每个区间对应的模型，数组中的每个模型为一个线性函数，将在之后介绍，其将不相交的键区间映射到未压缩位图上的唯一段。同时，压缩位图利用压缩技术高效存储位图中为1的位的位置。
图2 Oasis框架模型数组：Oasis首先将键空间划分为不相交的区间，每个区间都有一个独特的线性模型，将键投影到相应的位图段。如公式1所示，每个模型model𝑖将给定的键𝑢映射到对应位图段的一个位上。该位相对于位图起点的偏移量，即model𝑖(𝑢)，由三个参数决定：比例大小𝛼𝑖以及区间边界beg𝑖和end𝑖。其中，model𝑖(𝑢)=𝛼𝑖*(𝑢–beg𝑖)/(end𝑖–beg𝑖)。模型数组根据区间的左边界按升序排列所有模型，从而在查询过程中便于定位模型。 压缩位图：受SNARF的启发，Oasis将位图中的𝛽个连续1的位置组织为批次，并使用Elias-Fano编码技术压缩每个批次。Oasis使用了一个名为batch_list的数组存储这些压缩批次。数组batch_offset来记录每个批次相对于位图起点的偏移量。batch_offset中的第𝑖个元素表示第𝑖个批次的第一个位的位置。由于每个批次中的键数量是固定的，并且其范围信息可以从batch_offset中获取，因此无需记录每个批次的元数据。因此，这种分块压缩方法的内存开销是可以接受的。首先分别介绍查询处理过程中Oasis每个组件的操作。随后介绍Oasis的整体范围查询过程。查询模型数组：模型数组的查询过程包含四个步骤，如图2的右上角所示。1）通过区间边界找到查询所属的区间；2）检查查询是否跨越了多个区间或落在被修剪的区间内；3）将落在被修建的区间内的查询剪枝；4）计算查询对应的位图位置。查询压缩位图。压缩位图的查询过程详述于算法2中。该过程首先检查查询是否超出位图的范围（第2-3行）。如果查询不在位图范围内，则立即返回False。否则，在batch_offset上使用二分查找来识别查询左边界所属的批次（第4行）。一旦确定查询左边界的批次索引，就会检查查询的右边界是否落在当前批次内（第5行）。如果结果为真，表示查询跨越多个批次，确认在查询范围内存在数据。因此，该过程直接返回True。相反，将计算两个边界的偏移量（第7-8行），然后解压与查询对应的批次，并在指定边界内检查是否有位为1。 查询Oasis：首先，Oasis使用模型数组来确定查询的左边界和右边界对应的位图位置。接着，Oasis检查模型数组的返回结果，判断是否需要进一步处理（如果跨越多个区间或者被修剪了，直接返回模型数组返回的结果）。如果需要进一步处理，则使用压缩位图来确定查询对应的范围内是否存在数据。根据分析（具体过程请参考原论文），最小化Oasis的FPR可以转换成寻找分区个数m以及每个分区对应的边界，知道这些参数后，每个区间需要分配的bit位数也可以确定。然而，朴素的暴力搜索复杂度很高。因此，作者提出搜索Oasis的近似最优配置。作者假设工作负载均匀分布，即查询的左边界在键空间中的任意位置出现的概率相等。因此，查询落在某个区间的概率与该区间的范围大小成正比。此时，在固定m的情况下，选择top-m的相邻键（即m对距离最小的相邻键），其它键作为区间的边界即可得到m个区间。Oasis+的核心思路是在稀疏区间的编码方法上，用基于前缀的编码取代了基于学习的编码方法。具体来说，Oasis+使用Oasis来编码密集区间，并使用Proteus（一种基于前缀的范围过滤器）来编码稀疏区间。如图3所示，Oasis+框架与Oasis非常相似，包含一个位图和一个模型数组，但它在以下几个方面有所不同：1）Oasis+通过将位图划分为两个相邻的部分来实现这一点，而对应的空间分配基于每种范围过滤器类型存储的键数量。2）与 Oasis类似，Oasis+将键空间划分为不相交的区间，并存储它们的左、右边界。为了识别每个区间使用的范围过滤器类型，Oasis+引入了一个额外的位图来判断该区间是学习型范围过滤器还是前缀型范围过滤器。进行范围查询时，Oasis+与Oasis相似，在查询位图之前与Oasis过程基本一致，而在查询位图时是根据区间类型判断是使用Oasis还是Proteus。与 Oasis类似，Oasis+的构建策略决定了其性能的上限。然而，与Oasis的分区策略相比，Oasis+的构建策略有一个关键区别。在Oasis中，目标是找到最佳的区间设置，而在Oasis+的构建过程中，还需要进一步寻找每个区间的最佳过滤器类型。记Oasis的FPR为FPRLRF，Proteus的FPR为FPRPro。则整体的FPR为其中，It (i)为1表示采用Oasis，为0表示采用Proteus。由于基于学习的范围编码更适合密集键分布的区间，而基于前缀的编码更适合稀疏区间。Oasis+提出了一种基于贪心策略的构建算法。首先假设所有区间都采用基于学习的方法进行编码。然后，算法从最稀疏到最密集的区间依次遍历，并尝试在每次迭代中替换编码方式以减少整体FPR。如果替换无法降低FPR，算法会恢复之前的配置。实验平台：CPU：Intel(R) Xeon(R) Gold 5215 CPU @ 2.50GHz；内存：62GB；编程语言：C++；数据集：1）Unif：从范围[0, 264−1]中均匀生成的键；2）Norm：来自均值为263,标准差为0.01×264的正态分布；3）amzn：8000万 Amazon图书流行度数据，键值范围为 [0, 263]。4）face：2 亿Facebook用户 ID，键值范围为[0, 264−1]。对比方案：5个最新的基于前缀的范围过滤器：SURF，Proteus，Rosetta，REncoder，bloomRF，以及基于学习的范围过滤器SNARF。图4显示了 Oasis 和 Oasis+ 在不同数据集和工作负载下的FPR比较。图中的每一行对应一个数据集，不同列则代表不同的工作负载类型，包括点查询、短范围查询（[2, 32]）、长范围查询（[2, 512]）、以及非常长的范围查询（[2, 1024]）与点查询的组合。从中可以得出：SuRF在长范围查询上表现出色，但由于后缀截断，它在短范围查询和点查询中的FPR较高。Rosetta通过将不同长度的前缀存储在不同的布隆过滤器中，优化了短查询性能，但在长范围查询中FPR较高。REncoder和bloomRF尽管在短前缀布隆过滤器位图中包含了后缀信息，但在点查询负载中，其FPR高于 Rosetta。Proteus 通过 CPFPR模型，优化了前缀型过滤器的设计空间，在所有情况下的表现都超过或至少与其他范围过滤器相当。SNARF在处理均匀数据集时表现优异，尤其是在均匀工作负载下（如 face和 Unif）。其均匀范围编码策略在归一化分布数据集上表现尤为出色，在这些情况下 SNARF的FPR显著低于 Proteus。
图4 总体表现在均匀工作负载 下，Oasis的FPR总是优于现有的范围过滤器。具体而言，Oasis在大多数均匀工作负载下的FPR优于SNARF和其他过滤器，改进量在1.5×到3.2×之间。在normal工作负载的密集区间中，Oasis的线性模型能有效区分真正负查询，而SNARF的模型数量过多导致空间浪费和整体性能下降。相反，Oasis通过其分割算法减少了模型数量，并利用节省的空间预算提高了准确性，从而实现了更优的 FPR 性能。在face数据集 上，尽管SNARF在空间预算较大时表现优秀，但Oasis通过空间修剪策略有效地排除了大空白区间，减少了元数据开销，使得FPR在空间预算超过14时降至 1.3× 10⁻⁵或更低。尽管Proteus在短查询负载下表现优越，但随着查询范围的增加，Oasis的表现超过了Proteus和其他范围过滤器，显示出更好的扩展性和性能。Oasis+ 则能够在学习型和前缀型过滤器之间有效地导航最优设计空间。在几乎所有情况下，Oasis+的FPR表现都与最优范围过滤器相当或显著优于其他范围过滤器。这些结果表明，Oasis 和 Oasis+ 在各种数据集和查询负载下均表现出了强劲的性能。在这一部分中，论文将Oasis和 Oasis+集成到RocksDB v6.20.3中，展示它们在提升 RocksDB端到端查询性能方面的能力。作者为每个SST文件创建一个范围过滤器实例，并维护一个字典来存储每个运行的过滤器。在RocksDB的只读工作负载中，查询期间访问SST文件是延迟的主要来源。因此，降低FPR可以减少整体系统延迟，如图5所示，查询延迟趋势与FPR趋势高度一致。在每种情况下，Oasis和Oasis+的延迟始终低于其他基准，与Proteus和SNARF相比，最高可提升1.8倍和1.4倍的性能。本文介绍了Oasis，一种新型的学习型范围过滤器，在点查询和范围查询中都能实现极低的FPR。Oasis通过以下三个关键策略实现这一目标：1）修剪大面积的空区间，2）自适应地分配空间预算，3）利用分段算法进行优化配置。此外，Oasis+将学习型和前缀型范围过滤器的设计空间相结合进一步优化了Oasis，以在各种工作负载中实现稳健的性能。 | 重庆大学计算机科学与技术专业2022级读硕士生，重庆大学Start Lab团队成员。 | 
|
重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有3~5名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
图文｜何翔
编辑｜朱明辉
审核｜李瑞远
审核｜杨广超
