最近学习了一篇2018 SIGMOD会议上的best paper, 无奈, 谁让我入了database的坑呢.

论文: “SuRF: Practical Range Query Filtering with Fast Succinct Tries”

我们知道Bloom filter由于采用hash实现, 对single-key查询效率高, 但对range query就无能为力了. 虽然有支持range query的prefix Bloom filter存在, 但还是不够通用. 而Succinct Range Filter (SuRF)是基于一种新的数据结构Fast Succinct Trie (FST), 不仅支持point query还支持range query. 除了速度快之外, 还非常节省空间.

SuRF的一些特点:

  • 支持point & range query.
  • One-sided error, 即跟Bloom filter一样, 仅有false positive, 不会出现false negative. 也就是说若结果返回true, 但可能该key实际不存在; 若key实际存在, 则一定返回true. 并且误报率(FP)可以根据trie的空间大小作调整.
  • 基于Fast Succinct Trie实现.
  • Space-efficient, 每个trie结点只占用10个bits, 接近信息编码的下界.
  • Fast (1.5x ~ 5x), cache-friendly, 降低I/O开销.
  • 是一种静态结构, 若要插入新结点, 需要rebuild整个trie. 论文附录有讨论一些改进方法.

Level-Ordered Unary Degree Sequence (LOUDS)

在介绍Fast Succinct Trie数据结构之前, 我们先来看如何以一种节省空间的方式来表示一棵任意的树.

1989年, 论文“Space-efficient Static Trees and Graphs”提出了用Level-Ordered Unary Degree Sequence (LOUDS)来编码一棵树.

其方法是: 对树进行按层遍历, 并用01编码方式来记录每个结点与其直接孩子结点的连接情况.

比如, 下图左边这棵树的node 0, 有三个孩子, 故用三个1加末尾一个0来表示结束, 即”1110”. 对树进行按层遍历, 最后会得到右边所示的一个01序列. 通过这个序列, 我们也很容易将树的原有结构还原出来.

为了对这种编码形式的树进行遍历等操作, 定义两个基本操作rank & select.

  • $rank_1(i)$: 返回 positin $[0, i]$ 中1的个数;
  • $select_1(j)$: 返回第 $j$ 个1所在的 position.

相应的还有rank0和select0, 即统计的是0的个数或位置.

以刚才那棵树为例, 下表展示了rank & select的结果:

rank & select到底有什么实际作用呢? -> 可以实现树的上下遍历操作.

若我们把树按层遍历进行标号, 则有:

  • $ node\_num = rank_1(i) $
  • $ i = select_1(node\_num) $

可能看到这里就有些懵了…

rank1得到的是1的个数, 怎么又成node_num了?

select1传入的参数怎么又变成node_num了??

因为我们是把所有nodes按层编号的(以0开始), 假设我们也把边按层编号(以1开始), 那么每条边跟其下面连接的结点是一一对应的. rank1计算的是1的个数, 也就是边的条数, 那么该edge_num就有一个与之对应的node_num. 需要注意的是, 这里的node_num并不是位置$i$ 所对应的结点编号X, 而是结点X的某个孩子的编号.

废话那么多, 不如举个例子.

右图树序列中, 第8个位置中的1(红色标注), 对其求rank1结果是6. 也就是结点3下面的第二个孩子结点6. 因为该红色的1是结点3序列中的第二个1, 也就对应了第二个子孩子的编号. 反过来, 若对结点6求select1, 结果是8. 也就是红色1的位置.

因此, 根据rank&select这两个操作, 我们就能对这个01序列进行树的相关操作了.

我们可以看到, 相对于pointer-based, 这种方式都是在array上去look-up的. 所以 cache-friendly !

rank & select 优化

这里只介绍rank&select操作的优化, 其它看论文吧.

给定一个bit-vector, 如何实现常数时间的rank&select?

利用 look-up table (LUT).

其思想是将bit-vector划分为长度固定的blocks, 假定固定长度为B个bits. 对于rank操作, LUT存的是该block位置前的1的个数. 比如, rank LUT中第三个元素存的是7, 表示前两个blocks中共有7个1.

那么如何根据LUT计算$rank_1(i)$呢? 假定B=5, 求$rank_1(12)$.

$rank_1(12)$ = LUT[$\left \lfloor 12/5 \right \rfloor$] + 2 = 7 + 2 = 9. 其中2是位置[10, 12]区间统计出的1的个数.

对于select操作, 其思想是类似的. select LUT存的是每S个1所在的位置. 比如第三个元素8, 表示的是前(2*S)个1所在的位置是8.

Fast Succinct Tries (FST)

上面讲的是如何对一棵任意树编码成01序列. 其编码方式只是其中一种, 重要的是思想, 以及rank&select.

好, 接下来从tree转移到trie.

对于一棵字典树, 通常上层结点数少, 但访问频繁; 下层结点数多, 访问频率相对少. 因此SuRF将trie分为两层, 并将上层和下层分别采用两种不同的编码机制: LOUDS-Dense & LOUDS-Sparse. LOUDS-Dense的特点是相对LOUDS-Sparse占用空间多一些, 但访问速度快. LOUDS-Sparse的特点是占用空间少.

下图是论文里给的示例. 对于左边的trie, SuRF会按序将每个结点根据两种编码方式编码成右边所示的bit/byte序列.

LOUDS-Dense

LOUDS-Dense将每个trie node编码为三个bitmaps (其大小为256 bits), 以及一个byte序列$D\text{-}Values$来保存所有的values (可以是key对应的value或指向value的pointer).

这三个bitmaps:

  • $D\text{-}Labels$: 记录每个结点的分支情况. 按ASCII码置1.

    如上图中的根节点有三个分支f, s, t, 则将相应的bit位置1.

  • $D\text{-}HasChild$: 记录某分支是sub-trie还是terminate. 按ASCII码置1.

  • $D\text{-}IsPrefixKey$: 记录该prefix是否为key.

    如上图 level-1中的prefix “f”, 由于”f”属于keys中, 故将其置1.

在LOUDS-Dense层, 如何对trie进行遍历操作呢?

记$rank_1(bs, i)$表示求序列$bs$中, 位置 $[0, i]$ 包含的1的个数. $select_1(bs, i)$同理.

  • To traverse down the trie:

D-ChildNodePos($pos$) = $256 \times rank_1(D\text{-}HasChild, pos)$

  • To move up the trie:

D-ParentNodePos($pos$) = $256 \times select_1(D\text{-}HasChild, \left \lfloor pos/256 \right \rfloor)$

  • To access values:

D-ValuePos($pos$) = $rank_1(D\text{-}Labels, pos) - rank_1(D\text{-}HasChild, pos) + rank_1(D\text{-}IsPrefixKey, \left \lfloor pos/256 \right \rfloor) - 1$

LOUDS-Sparse

LOUDS-Sparse将每个trie node编码为四个bit/byte序列:

  • $S\text{-}Labels$ (byte序列): 记录结点的每个分支所对应的label.

    如上图 level-2中的第一个非叶子结点有三个分支r, s, t, 则将r, s, t按顺序存在$S\text{-}Labels$中.

    注意的是, 若一个prefix同时也是key, 则用一个$分支来表示. 比如 level-3处的prefix “fas”已经属于keys, 故添加一个$到$S\text{-}Labels$中. (此情况下, 在LOUDS-Dense层, 利用的是$D\text{-}IsPrefixKey$)

  • $S\text{-}HasChild$ (bit序列): 记录某分支是sub-trie还是terminate.

  • $S\text{-}LOUDS$ (bit序列): 记录每个结点的边界.

  • $S\text{-}Values$ (byte序列): 同D-Values.

在LOUDS-Sparse层, 如何对trie进行遍历操作呢?

(需要指明的是, 以下公式是针对整棵trie都用LOUDS-Sparse编码情况所成立的. 若对LOUDS-DS, 则还需加上一个node count.)

  • To traverse down the trie:

S-ChildNodePos($pos$) = $select_1(S\text{-}LOUDS, rank_1(S\text{-}HasChild, pos) + 1)$

  • To move up the trie:

S-ParentNodePos($pos$) = $select_1(S\text{-}HasChild, rank_1(S\text{-}LOUDS, pos) - 1)$

  • To access values:

S-ValuePos($pos$) = $pos - rank_1(S\text{-}HasChild, pos) - 1$

LOUDS-DS

对于一棵trie, 我们将上层结点按照LOUDS-Dense编码, 下层结点按照LOUDS-Sparse编码, 并把这种混编方式称为LOUDS-DS.

在LOUDS-DS上, 支持三个高效的操作:

  • ExactKeySearch(key): 若key存在则返回key所对应的value; 否则返回NULL.
  • LowerBound(key): 返回满足$k \geq key$并且字典序最小的(k, v)的迭代器.
  • MoveToNext(iter): 移动迭代器iter到下一个key-value对.

对于一个point query, 首先在LOUDS-Dense上搜索, 若没找到, 再在LOUDS-Sparse上搜索.

对于一个range query (如SQL中的where关键字), 利用的是LowerBound, 搜索方法跟在树上操作差不多.

性能

刚才已经说了, cache-friendly. 另外树的遍历操作通过rank & select, 也能做到常数级别.

空间方面, LOUDS-Sparse编码中, 对于每个结点, $S\text{-}Labels$占8 bits, $S\text{-}HasChild$和$S\text{-}LOUDS$各占用1 bits, 故一个结点共占10 bits. 又由于trie的下层结点占了大多数, 因此可以说, 每个trie结点只需占用10个bits.

Succinct Range Filter (SuRF)

如果我们对一棵完整的trie做查询等操作, 必然是100%的准确率. 但这样的字典树内存是存不下的, 即便我们用到了上述的01序列来编码, 占用的空间还是太大了. 因此, 我们需要在空间和准确率上做balance.

一个想法是将FST进行裁剪. 不存完整的keys, 而是存keys间的公共前缀, 外加一些suffix bits, 以此来区分每个keys.

由此论文介绍了四个版本的SuRF.

(1) SuRF-Base. 其结构是: 公共前缀 + 一个额外的byte. 也就是仅存能区分所有keys的最小prefixs.

比如 keys={SIGAI, SIGMOD, SIGOPS},

SuRF-Base的好处是节省空间, 但误报率高. 比如现在查询”SIGMETRICS”是否在keys中, 返回Yes. 但实际上该单词并不存在于keys中.

为了减少FPR, 又引入了两个版本: SuRF-Hash & SuRF-Real. 其都是在SuRF-Base的基础上, 又额外添加某些suffix bits来减少FPR.

(2) SuRF-Hash. 其结构是: SuRF-Base + hash bits.

(3) SuRF-Real. 其结构是: SuRF-Base + n bits.

SuRF-Hash的好处是FPR低, 但对range query没帮助. SuRF-Real的好处是有助于range query, 但FPR比SuRF-Hash的高. 由此有了SuRF-Mixed.

(4) SuRF-Mixed. 其结构是: SuRF-Base + hash bits + n bits.

看作者给的demo是直接将hash bits跟n bits简单拼接来作为suffix bits.


参考:

SuRF源码: github

论文作者给的 demo website.

2018 SIGMOD论文之SQL领域解读

SuRF: 一个优化的 Fast Succinct Tries