Introduction

Goetz哥最近出了一本新书: More Modern Btree Techniques，里面多次提到了有关Btree/排序结构的压缩技术，比较关键的一个就是offset value encoding，并且也提到了Google的Napa/F1 Query使用了这种技术来加速查询。这篇文章就来介绍一下offset value encoding具体是怎么做的，以及这个技术如何能够加速查询。

在介绍Offset Value Encoding之前，先大概了解一下他的基本思路，Goetz哥在老版本的Modern Btree Techniques中的Prefix B-trees中提到了这个技术，属于Prefix Truncation的一种，其基本思路是，在Btree这样的排序结构中，一个节点中的排序键的LowerBound/UpperBound可能会有共享的前缀，在查询/比较的时候，我们可以删掉这些前缀来得到更高的查询性能以及更好的压缩率。更进一步，我们通过重新编码来把原本（可能数据量大，比较性能差）的排序键转化成一些具有紧凑结构的编码（比如一个int64）来进一步提高性能。

一些类似的技术，尤其是在压缩技术中，比如一些order-preserving compression，delta encoding，可以看到相似的思想。之前介绍过的在WiredTiger中使用的列存技术，也有类似技术的应用，具体思路是一个Btree的节点内，Page上只存储一个start record id，剩下所有数据的key，都是通过start record id + offset来计算得到的。另外Trie，MassTree也是一些应用Prefix Truncation思想的结构。

简单想，在不修改Btree对外暴露的接口的前提下，这种技术可以增加压缩率，提高Page内查找的效率。然而Goetz哥做的更好的是，不仅在索引结构中使用了这个技术，同时还打通到了计算引擎中，在计算引擎中直接使用索引结构给出的编码，来加速查询的性能。

Offset Value Encoding

这一节介绍一下具体的Offset Value Encoding是怎么做的，比如他的一些性质，编码规则等。

为了简单起见，我们针对使用offset value encoding的目标场景是通用的任意列作为排序键，排序使用的是递增序。并且为了实现简单（Goetz哥也提到了），这里会用Normalized Key的方式，把任意列的排序键转化成一个可以直接比较大小的一段binary（有的地方也叫MemComparable的格式）。

Offset Value Encoding一听名字就是和Offset相关，和其他Prefix Truncation/Compression的技术类似，他也需要一个基准的值来进行编码。比如在Btree中，一个节点中的一种编码方式是每一行都相对于fence key去做offset value encoding（后面简称OVC）。

具体来说，OVC就是由offset和value两个值进行编码的，我们会先计算出两行中第一个值不相同的位置，也就是offset，以及编码行在这个offset上对应的value。在计算递增序需要的OVC的时候，会用ovc = (arity - offset) * range + value的方式来计算编码，其中arity是排序键的总行数。

这个公式的核心目的是，在比较两个行A，B相对于同一行C得到的OVC的时候，如果OVC(A) < OVC(B)，那么A的排序键一定比B更小。首先肯定是具有更大的shared prefix的一方，也就是offset更大的一方，排序键更小。当offset相同的时候，对应offset上值更小的一方，排序键更小，自然就得到了这个公式。

上图是原文中的一个例子，展示了每一行相对于前一行的offset value encoding的编码值。

这里我给了几个对应上面各种case的例子：
* A和B比较，对应的是具有更大的offset的OVC更小的这个规则
* A和C比较，对应的是相同offset下，更小的value具有更小的OVC的规则
* A和D的比较，则说明了OVC作为一种压缩技术，无法做到只用OVC就处理所有的比较情况，我们还需要在OVC无法比较大小的时候，fallback到下一个offset上去比较。

再具体一点，对应我上面说的通用的Normalized Key的情况，一段binary的每一个字节就相当于一列，这一列的值域就是256，那么在做OVC的时候，我们只需要把value作为低8位，offset取反后作为高位，就可以使用一个int32或者一个int64来编码OVC了。这时候对应的offset的长度的范围是2^24或者2^56（其实我感觉对于排序键，用int16已经够了）。

至此，我们已经可以将OVC技术直接应用到一些排序的结构中，通过OVC来加速查询了。

接下来形式化一点，我们会介绍一些OVC比较有意思的性质，方便在后面进行计算的时候，利用这些性质进行加速。

• pre(A, B)来代表A和B的最长共享的前缀，也就是前面计算的offset
• val(A, i)代表A在offset i处的值
• val(A, B)代表val(B, pre(A, B))，也就是在计算B对A的OVC的时候的value
• ovc(A, B)就是B对A的OVC，通过pre(A, B)和val(A, B)计算出来

一些相关的性质：
* 对于key A < B < C，ovc(A, C) = max(ovc(A, B), ovc(B, C))
* 证明：
* 如果pre(A, B) > pre(B, C)，那么pre(A, C) = pre(B, C)。那么val(A, C) = val(B, C)，所以ovc(A, C) = ovc(B, C)，因为pre和val都相同。
* 如果pre(A, B) < pre(B, C)，那么pre(A, C) = pre(A, B)，val(A, C) = val(A, B)，这里是因为pre(B, C)更大，所以在offset相同，并且小于pre(B, C)的时候，val是相同的
* 如果都相同的话，那么pre(A, C) = pre(B, C)，val也相同，和case1一样
* 对于key A < B < C, 如果ovc(A, B) < ovc(A, C)，那么ovc(B, C) = ovc(A, C)
* 根据上面的理论，ovc(A, C)是max(ovc(A, B), ovc(B, C))，目前已知不是ovc(A, B)，那就一定是ovc(B, C)了
* 应用：在进行比较的时候，ovc(A, B)和ovc(A, C)比较结束后，如果B更小，那么我们可以直接用ovc(A, C)做为ovc(B, C)，而不需要重新计算ovc(B, C)进行下一轮比较。具体的例子在做排序的时候会看到
* 对于一段排序的流数据， X0 < X1 < ... < Xn-1 < Xn。那么ovc(X0, Xn) = max(Xi - 1, Xi)(i = 1..n)
* 应用：在输出的排序流数据的时候，如果我们每一次输出的OVC都是当前值相对于上一个值的OVC，我们可以使用上面的公式直接计算当前值相对于第一个值X0的OVC

Merge

这一节介绍一下如何利用OVC，以及败者树做通用的k路归并。合并k个有序的数据流为1个，并得到他们的OVC。

首先需要知道败者树是怎么做k路归并的：

* 初始化流程：
* 败者树的每一个叶子节点都代表一个有序的数据流，一般叫做run。初始化时叶子节点会存储数据流的第一个元素。
* 每一个非叶节点存储的是两个子节点的值的较大值（也就是在排序中的败者）
* 两个子节点的较小值，也就是排序中的胜者会参与到父节点的比较中。递归的运用上述流程，最终会得到k路数据流中的最小元素。
* 比如上图中的最小值是"061"，放到了根节点
* 归并流程：
* 把根节点作为本轮的输出结果，然后从根节点对应的run（上图例子中是第9个run）中取出下一个元素
* 比较当前元素和父节点元素（也就是上一次的败者）进行比较，得到新一轮的败者。胜者则继续向上比较，直到计算出新的最小值。
* 在上图的例子中，"092"作为新的元素出现，先和父节点"503"比较，胜出。然后和"087"比较，落败。"087"向上，和"154"比较，胜出。则得到新一轮的胜者是“087”

OVC在败者树上的应用，就是利用OVC来加速元素之间的比较，并利用败者树的性质高效的计算新的OVC。

图中是利用败者树高效维护OVC的示例：
* 初始阶段，败者树的初始化流程不变。在每次比较后，我们不仅会在节点上存败者的值，也会存储败者相对于胜者的OVC。比如上面例子中，A是最终的胜者，那么A到root这条链路上所有的败者都会计算他们相对于A的OVC。比如OVC(A, B), OVC(A, C)
* PopA之后，进入新的元素A2，这里我们假设原本排序的数据流中已经有每一个元素相对于他前一个元素的OVC了，这里A2就自带一个OVC(A, A2)。
* 按照败者树的维护流程，我们会把A2和B进行比较，因为A2和B中存储的OVC都是相对于A的，那么他们可以直接进行比较，得到A2和B的大小关系。
* 根据规则，我们需要在败者的身上存储败者相对于胜者的OVC。
* 如果B是胜者，那么B上提，A2留下，并需要计算A2相对于B的OVC。根据之前介绍的OVC的性质，可以得到OVC(B, A2) = OVC(A, A2)，所以可以直接使用A2自己的OVC，而不需要重新计算。
* 如果A2是胜者，也是同理，我们不需要重新计算OVC，而是可以直接得到OVC(B, A2) = OVC(A, B)
* 继续败者树的维护流程，最终就得到了新一轮的胜者，同时也把路径上的败者的OVC进行了更新。

之所以可以这样维护败者树，一个直观的想法就是在新的元素进来的时候，路径上的所有元素都有他们对前一次胜者的OVC，即便是新的元素输了留下来了，原本的老节点也一定带有对前一次胜者的OVC，那么这个路径上的比较就可以全用OVC来加速了。

需要注意的是，上面的讨论中，并没有讨论OVC失效的情况，也就是OVC相等的情况。这个时候需要把原始的value拿出来继续比较，不过因为当OVC相等的时候，说明两行数据一定有公共的前缀，那么此时只需要从第一个不同的offset开始比较即可。
* 一个关键的特性是，这种OVC失效重新比较的次数是有上限的，这是因为对于一次比较，要么两行有和前一个胜者相同的公共前缀，那么进行下一个offset的比较，要么没有和前一个胜者相同的公共前缀，那么直接比较OVC即可。所以对于败者树上残留的元素，每一个元素最多比较k次，其中k为sort column的数量。那么对于一个数据集为N的请求，我们最多进行k * N次原始数据的比较。比N * LogN * K的一般排序算法有更好的上界保证。

Query Processing

OVC主要用在排序的数据上，所以和计算相关的优化也都是针对排序相关的。因为我个人不是非常熟悉一些计算引擎的细节，这里就简单列举一些OVC可以加速的基础的查询。

• MergeJoin: 和上面的MergeSort是一样的，在进行了MergeSort之后，输出的数据流中包含了每一个元素对前一个元素的OVC，我们只需要看其中的offset是不是超过了join的列，就可以确定是不是可以做Join了。相当于使用offset加速等值查询。
• Group/Aggregation: 其实也是用offset加速等值查询，通过OVC可以快速判断当前行是否和前一行是在一个组中。
• Filter: 因为输出的数据流包含每个元素对前一个元素的OVC，如果我们在做一些filter的时候，会过滤掉一些元素，此时为了保证输出数据流仍然满足上述性质，需要做一些处理：
  • 具体来说，因为OVC存在性质，如果A < B < C，那么OVC(C, A) = max(OVC(B, C), OVC(A, B))。所以假设我们过滤掉了B，只需要在计算OVC(C, A)的时候，和B的OVC取一个max即可。
• Scan：Goetz哥在一篇paper中提过，我们可以很高效的把prefix truncate + row store的数据转化成RLE + column store的格式。个人认为这种在一些场景上还是比较有用的，比如存储格式是Btree上的row store + OVC，可以直接转化成column store + RLE吐给计算引擎。

OVC的好处个人感觉有这么几点：
* 可以把多列的比较压缩成一个简单的数字，加速两行比较的性能。比哈希的优势就是可以比较大小。
* 是一种前缀压缩技术，存储格式上可以使用它来优化存储空间。（当然内存中也可以用来优化内存效率）
* 可以给计算引擎直接使用，基本上计算引擎的各个算子都可以接受OVC作为输入，以及输出OVC给下游，从而使OVC优化整个计算过程
* 实现简单
* OVC的这些特性可能还有可以发挥的空间，期待探索和创新