问题背景

分析型负载涉及全列扫描，需要遍历该列并根据查询条件来获取相应的数据。基于磁盘的列存，在没有任何优化的情况下，需要先从磁盘读取数据然后再计算是否符合查询条件，导致很多查询的瓶颈在I/O。但并不是所有数据都需要被读取和计算， 真正需要的只有查询相关的数据。列存数据以pack粒度组织，如果能减少读取的pack数目，能有效降低I/O并加速查询。我们可以根据查询结果将pack分为三类：

• AC pack：pack内所有数据都符合查询条件
• RE pack：pack内所有数据都不符合查询条件
• PA pack：pack内部分数据符合查询条件

其中RE pack没有必要进行访问。如果在实际访问之前，能够过滤掉RE pack，可以节省这部分pack导致的无效I/O和计算。若RE pack在查询中占比很高，那么过滤RE pack能有效加速查询。为解决这一问题，引入pruner，目的是在访问pack之前利用pruner直接识别并过滤掉RE pack，通过减少访问的pack数目来降低I/O并加速查询。

设计目标

pruner本质上是对pack内部数据的一种描述。目前主流的方法是通过pack的一些统计信息SMA (min/max），histogram，cmap，bloom filter等进行过滤。pruner在设计中需要考虑：

• 类型支持：
  • 查询类型：point query, range query, like
  • 数据类型：int, decimal, date, string
• 空间：pruner的空间代价要尽可能小
• 快速：pruner是引入的额外计算，需要快速做出判断
• 准确：在保证不存在false negative的前提下，false positive rate要尽可能低。当false positive rate为0时，pruner能准确识别所有的RE pack。
• 效果：
  • 实际过滤比例：借助pruner实际过滤掉的pack比例，这是相较于没有pruner的情况下获得的提升。
  • 理论过滤比例：RE pack在所有pack中的占比，同时受数据分布和查询分布影响，这是pruner的理论过滤上限。pruner的实际过滤比越趋近于理论过滤比，pruner的效果越好。

因此一个优秀的pruner应当在空间代价尽量小的情况下，提供快速精确的过滤能力，即能准确识别RE pack，不受数据分布和查询分布的影响。

目前系统支持pack粒度的min-max pruner 和 bloom filter，bloom filter只对点查询过滤有效，因此范围查询只能利用min-max pruner进行过滤。min-max pruner的优点是足够轻量，但它不能提供pack内部具体的数据分布情况，适用范围有限，如果pack内部数据分布比较集中，那么min-max pruner能起到较好的过滤效果。但在更一般的情况下，例如pack内部数据分布较为稀疏或存在outlier，min-max pruner无法识别并过滤RE pack。例如某pack内数据分布集中在3个区间[1-20, 500-600, 990-1000]，查询[50-100]内的数据，min-max pruner无法进行过滤，仍会带来无效IO，不能充分发挥pruner的作用。更为精确的范围过滤可以利用ART等索引结构，但空间代价过大。因此需要一种轻量且准确的pruner来支持范围过滤。

本文尝试将SuRF作为range pruner来支持范围查询过滤。SuRF是一种基于trie的range filter，能够实现准确的范围过滤，同时底层利用succinct编码，空间代价相对较小。本文在不同的数据分布和查询范围下，评估SuRF的过滤效果和空间代价。实验表明，在不同的数据分布和查询范围下，SuRF的实际过滤比例都趋近理论过滤比例，不易受数据分布和查询范围的影响，能够实现准确过滤。

SuRF概述

SuRF（Succinct Range Filter）是一种基于trie的range filter。trie本身提供精确的点查和范围查询。参考下图，假设有"SIGAI", “SIGMOD”, "SIGOPS"三条数据，Full trie存储完整的key。将其用作filter，对于点查key，直接在trie中查找key是否存在，时间复杂度为O(m)，其中m为key的长度；对于范围查询between start_key and end_key，在trie中查找第一个大于等于start_key的key，然后同end_key进行比较，如果key > end_key，则不存在该范围内的值，否则存在。因此无论是点查还是范围查询，full trie都能提供准确的过滤结果。

为进一步降低空间， SuRF对full trie进行裁剪，代价是引入了false positive。不同的裁剪程度对应不同的 false positive rate (FPR)。下图为SuRF的几种不同形式。

• SuRF-base：只保留足以区分不同key的长度，空间占用最小但FPR最高。例如点查"SIGMETRICS"便无法进行过滤。
• SuRF-Hash：在SuRF-base的基础上多存一段hash，主要用于降低点查过滤的FPR，因为它不能提供关于后缀的顺序信息。
• SuRF-Real：在SuRF-base的基础上多存一段后缀，能同时降低点查和范围查询过滤的FPR，可以权衡空间和性能来选择合适的suffix长度，suffix越长，空间大但FPR低，反之空间小但FPR高。

除了通过对full trie裁剪来降低空间，SuRF底层利用Fast Succinct Trie （FST）压缩空间占用。FST是一种succinct data structure，其占用空间接近理论下限。参考下图，左边为trie的表示，右边为对应FST的实现。FST在传统succint编码的基础上，利用分层操作（分为LOUDS-Sparse和LOUDS-Dense）及一系列优化，加速节点的访问。LOUDS-Sparse和LOUDS-Dense都是对trie的succinct编码方法，其中LOUDS-Dense占用空间相对更大但查询性能更好，LOUDS-Sparse空间相对更小但查询性能略差。基于trie上层节点的访问频率要比下层节点更频繁这一前提，FST对上层节点用LOUDS-Dense进行编码，下层节点用LOUDS-Sparse进行编码，并通过调节LOUDS-Sparse和LOUDS-Dense的比例来调整性能和空间之间的权衡。（FST的详细内容可以参考论文原文和https://yuque.antfin.com/db_core_team/internal_docs/surf#rb0toc）

总结来看，SuRF是经过裁剪得到的FST，在较小的空间代价下，保留了trie本身的优势。作为range filter，SuRF满足准确，快速，轻量这三个诉求。

1. 准确：FST本身是trie，无论是点查还是范围查询，trie都能快速得到准确结果。SuRF在FST的基础上进行裁剪，虽然引入了false positive，但不存在false negative，保证了range filter的准确性。
2. 快速：对于长度为m的key，trie的查找时间复杂度为O(m)。同时FST借助一系列优化加速了底层节点的访问。
3. 轻量：FST是一种succinct data structure，其占用空间接近理论下限。SuRF在FST的基础上进行裁剪进一步降低空间代价，这使得SuRF足够轻量。

过滤流程

SuRF构建算法：

1. pack满之后，对pack内数据进行排序，因为pack内部数据无序，而构建trie需要保证顺序性。
2. 对于排序后的key，构建louds-sparse，保证Trie中的所有剪枝后的key与前后的key都能区分开
3. 据内存使用情况确认louds-sparse和louds-dense的分割层
4. 将分割层以上以louds-dense的格式存储
5. 以上构建的louds-sparse和louds-dense都是分层存储在每层的bitset中，需要将所有分层的bitset合并成一个bitset

SuRF过滤算法：

1. 在trie中找到第一个大于start_key（如果包含start_key，则找第一个大于或者等于start_key）的位置
   • 如果start_key的长度小于louds-dense的高度，则在dense中找到第一个大于start_key的位置，然后沿着最左子树找到这条路径
   • 如果start_key的长度大于louds-dense的高度，则需要在louds-sparse中找到第一个大于start_key的位置
2. 将在trie中找到的key和end_key做比较，如果end_key大于key，则range不存在，否则range may contain

空间分析

SuRF的空间由3部分构成 sizeof(SuRF) = sizeof(LOUDS-Dense) + sizeof(LOUDS-Sparse) + sizeof(suffix)。LOUDS-Dense和LOUDS-Sparse是对SuRF中internal node不同的编码方式，LOUDS-Dense每个node占 256*3 bits， LOUDS-Sparse每个node占 10 bits。trie中internal node的具体个数取决于数据分布，LOUDS-Dense和LOUDS-Sparse之间的比例可以通过参数进行调节。suffix空间取决于suffix长度和leaf node个数，leaf node的个数取决于pack内distinct key的个数，suffix长度可以通过参数调节，最小SuRF-base的suffix长度为0。

因此SuRF的空间大小受3个因素影响：

• trie中节点个数：SuRF空间和节点个数成正比，节点个数取决于具体的数据分布。粗略估计，对于一个包含N个distinct key的pack，当构建的trie为满二叉树时，节点个数最多，约为2N个。直观上来看，节点个数可以从两方面进行粗略估计：1）pack内distinct key的个数，因为trie是将每个key都区分开，distinct key的个数决定了trie叶子节点的个数。 2）prefix的长度，因为SuRF会对trie进行裁剪，所以max prefix len决定surf的高度。prefix长度同时受数据分布和数据类型的影响。
• suffix长度：suffix长度越小，空间越小，但FPR会升高
• LOUDS-Dense层数：LOUDS-Dense层数越小，空间越小，但查询速度会变慢

False Positive Rate (FPR)

SuRF的FPR同时受数据分布和查询分布的影响，不存在严格的对应关系。SuRF的FPR通过suffix进行控制，对于相同的数据分布和查询分布，SuRF-base的FPR最高，空间占用最低。随着suffix长度增加，FPR下降但空间上升。当suffix足够长时，SuRF成为full trie，此时FPR为0，可以进行精确过滤，但空间占用最大。

类型支持

目前SuRF prunerr支持 int, decimal, date, string 几种类型。string 类型可以直接构建SuRF，int, decimal, date 都转化为定长的byte sequence来保证顺序，BIGINT转化为8个字节的字符数组，decimal为16字节的字符数组，date为4字节的字符数组。

实验评估

实验主要从空间代价、准确性、过滤效果三个方面对SuRF进行评估。

• **空间代价：**采用空间占比进行衡量 Size ratio = pruner size / pack size。
• 准确性：采用false positive rate 进行衡量 FPR = FP / (FP + TN)，其中 FP为false positive的数目(pack实际为RE但pruner判定为PA)，TN 为true negative的数目(因为不存在false negative, 所以pruner判定为RE的pack均为TN)
• 过滤效果：
  • 实际过滤比例：利用pruner实际过滤掉的pack数目在全表扫描所需pack数目中的占比进行衡量 Prune ratio = # pruned packs / # TOTAL packs。实际过滤比例同时受数据分布、查询分布、pruner自身准确性的影响，这是相较于没有pruner的情况下获得的提升。
  • 理论过滤比例：利用RE pack在所有pack中的占比进行衡量 RE ratio = # RE / # TOTAL PACK。理论过滤比例同时受数据分布和查询分布影响，这是pruner的理论过滤比上限。
  • 为消除数据分布和查询分布对过滤比的影响，采用理论过滤比与实际过滤比的差值来衡量pruner自身的过滤效果。pruner的实际过滤比越趋近于理论过滤比，pruner的效果越好。当实际过滤比和理论过滤比一致时，说明pruner能准确识别所有RE pack。

随机生成数据

为测试数据分布对SuRF的影响，随机生成不同分布的数据，验证在不同数据分布下SuRF的空间代价和过滤效果。实验环境为全内存，数据集为随机生成的不同分布（sequential, uniform, gaussian, pareto）的 64-bit int，每种分布的数据量为100 pack，随机数生成的范围为[0, 64k * # pack]，即[0, 6400k]。查询语句为 select k from table where k between start_key and start_key+range_len，start_key为随机生成（uniform）的数据范围内的查询起点，range_len为查询的长度，取[1, 10, 50, 100, 1000]，来验证不同查询范围下的过滤效果。各pack之间的数据分布类似，pack内部服从不同的分布，查询分布为uniform。

空间代价
下表为不同分布下的SuRF空间占比。其中SuRF-base只保留了足以区分不同key的长度，SuRF-real在SuRF-base的基础上多存了一个字节的后缀。
从不同的分布来看，uniform下的空间占比最高，因为数据分布最分散，随着数据分布更为集中，空间占比会随之下降。从SuRF类型来看，SuRF-base的空间明显小于SuRF-real。

False Positive Rate
SuRF-real在不同数据分布和查询范围下的FPR均为0，可以实现准确过滤。SuRF-base相较于SuRF-real有更高的FPR。从不同的数据分布来看，数据分布越分散，FPR越高，反之FPR越低。从不同的查询范围来看，对于gaussian和pareto，FPR受不同查询范围的影响较小，趋于稳定，对于uniform分布，FPR随查询范围的增大而增大。

过滤效果
实际过滤比和理论过滤比都同时受数据分布和查询分布影响。下图为不同分布和不同查询范围下，SuRF-Base, SuRF-Real, min-max的实际过滤比例及对应的理论过滤比例。图中结果为10次测试取平均。
对比min-max和SuRF的实际过滤比，min-max只在sequential分布下过滤效果和SuRF一样好，但在更一般的分布下，SuRF的过滤效果要明显优于min-max。对比实际过滤比和理论过滤比，SuRF-Real的实际过滤比例同理论过滤比一致，说明SuRF-Real可以准确识别并过滤掉不同数据分布和查询分布下的RE pack；SuRF-Base的实际过滤比例同理论过滤比例的差距较小，且在不同数据分布和查询范围下的表现较为稳定；而对比min-max的实际过滤比，除了在sequential分布下和理论过滤比例一致，其余分布下都有较大的差距，这也进一步验证了min-max pruner只在特定分布下有效。

对于range pruner本身，其作用受数据分布和查询分布制约。下图为不同查询范围和数据分布下的理论过滤比。从查询范围来看，查询范围小的时候RE pack比例高，但随着查询范围增大，RE pack比例变低。从不同的数据分布来看，sequential分布下，各pack之间的数据范围完全没有重叠，因此查询数据只涉及个别pack，RE pack比例高，且受查询范围的影响小。 而在uniform分布下，数据均匀落在各个pack内，一旦查询范围增大，RE pack比例明显下降。

TPC-H

为进一步验证SuRF对不同数据类型的过滤效果和空间代价，利用TPC-H数据集进行测试。实验环境为全内存，生成scale factor = 1的数据，选取lineitem表进行测试，共92pack。考虑到范围查询主要针对 int, decimal, date三种类型，针对这三种类型的列构建SuRF pruner，并测试相应的空间占用和过滤比例。由于TPC-H数据服从uniform分布，依据上文的测试结果，uniform分布下的大范围查询本身RE pack比例很小，pruner的理论过滤比低。因此只选取了数据分布范围较广泛的列进行测试。

int
选取L_PARTKEY进行测试，数据范围[1, 200000]，空间占比 25.7904%，小范围查询下SuRF的实际过滤比接近理论过滤比，说明可以有效过滤，大范围查询下理论过滤比为0。而min-max 无论在小范围还是大范围都无法进行过滤。

decimal
选取L_EXTENDEDPRICE进行测试，数据范围[901.00, 104949.50]，空间占比16.8137%，小范围查询下SuRF的实际过滤比接近理论过滤比，说明可以有效过滤，大范围查询下理论过滤比为0。而min-max 无论在小范围还是大范围都无法进行过滤。

**date **
选取L_SHIPDATE进行测试，数据范围[1992-01-01, 1998-12-31]，空间占比 2.5068%。对时间类型的过滤效果并不好，主要是因为时间的范围很有限，数据分布相对比较集中；同时查询范围比较大，比如一个月或者一年内的数据。对于uniform分布的数据，几乎所有pack都符合查询条件，pruner无法进行过滤。如果数据有序分布，可以直接使用min-max pruner。

总结

SuRF能在较小的空间代价下提供相比于min-max更为准确和通用的range pruner功能。
SuRF优势场景可以归结为：

1. 小范围区间查询：查询同时有上下界(closed range seek)，并且查询范围较小(查询范围的大小是相对的，指查询范围相较于数据分布范围小)。例如pack内数据分布集中在3个区间[1-20, 500-600, 990-1000]查询[50-100]内的数据。对于open range seek，SuRF当然也是支持的，只不过利用min-max pruner也可以达到相同的效果。因此查询多为open range seek时不建议用SuRF。
2. pack内数据分布离散或存在outlier：对于pack内分布集中的数据，e.g. sequential分布，min-max pruner也能够起到很好的过滤效果，没有必要用SuRF。

对比3种pruner类型，bloom filter只对点查过滤有效，min-max和SuRF同时支持点查过滤和范围过滤。min-max空间代价最小，但只对pack内数据分布集中的场景有效。bloom filter和SuRF空间代价相对更大，适用于更一般的数据分布，能提供比min-max更精确的过滤功能。

本文只考虑了pack粒度的pruner，假设各pack之间的数据分布相同，验证不同pack内数据分布下pruner的过滤效果。当pack内数据分布确定时，对于相同的查询，pruner的理论过滤比例是确定的，取决于RE pack的比例，而不同pruner的实际过滤效果的差异取决于其能否准确描述pack内的数据分布。而对于pack间的数据分布，受pack组织方式影响。如果相邻数据集中到同一pack，e.g. 数据有序排列，能进一步降低RE pack的数目，提高pruner的理论过滤比例。