Offset-Value Coding

Napa 系统中，排序会被用在 Index Lookup Join, Streaming Agg 和 Hash 的一些对 hash key 的操作中。这篇文章介绍了 RLE 和合并中使用 OVC 的效果。

对于作者来说，他认为 ovc 起到的效果类似 Hash Join 的 Hash Code，也能辅助 Interesting Order。在这里的场景可以当成一个固定 Schema 下的排序，和一种 dynamic 的 poor man’s key。OVC 由:

  1. offset indicates the first difference between them (the first column or the first byte) and the
  2. value indicates the data value at that offset, suitably normalized for ascending vs descending sort
  3. Offset and value are combined into a single order-preserving integer.

在 Napa 中，排序列属性通常比较复杂，比如 20-50列，有的列只有 3-5 的 NDV。下面有一个对应 OVC 的计算例子，即 Table2，假设 Domain 为 100（这个 Domain 我理解可以定义为max(单列的 Domain)）:

  1. 出现区别的是在第三列（以0开始算），所以有 3，为了防止 Negative，所以配置 + 1
  2. Domain 是 100，所以 * 100
  3. 出现区别的列是 44，因为顺序是 ASC，所以这里采用 -44

我们其实可以看到，这里 Fig2 是一个非常非常简化版的 OVC。

img

这里 OVC 的规则非常简单（我写到这里，突然想出一件事，就是这个地方 OVC 是「精确」的），我们可以举例，限免用颜色可以定义出对应的 OVC 的机制。

img

这里合并的时候，比输了需要跨流 Re-compute OVC

img

论文还提到了 Key 的编码相对 OVC 的修改：

img

  1. Low fence keys: 如果 Run 没有初始化，是一个空成员，预留 Run( capacity 个 ID ) 来处理
  2. Current run: 这个意思我当初看的时候理解了好久…最后发现是 Run Generation 的时候那种，比如基于选择的 Run Generation，这个时候 Current run 可能有同一条流有更小（大）的值但不能 flush。因为前面的 id 被 assign 给了 run, 所以 要 ovc + capacity
  3. Next run 就是这个加上 maxuint / 2 + 1
  4. High fence key 是给消耗完的流（但不想调整 LoserTree 的结构）用的

关于 OVC 的计算，可以参考 SIMD 代码 ( listed in paper and generated by ai ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 输入：二进制串A、B；串长度len_A、len_B
// 输出：OVC = (最长公共前缀p, B[p])
function SIMD_Compute_OVC(A, B, len_A, len_B):
    // 1. 初始化核心变量
    min_len = min(len_A, len_B)       // 取最短串长度，避免越界
    offset = 0                        // 全局偏移：已比较的字节数
    block_size = 32                    // SIMD块大小（论文：16/32/64B，对应vec-128/256/512）
    p = 0                              // 最长公共前缀长度（最终结果）

    // 论文规则：短串（＜16字节）直接用标量，避免SIMD开销
    if min_len < 16:
        return Scalar_Compute_OVC(A, B, min_len)

    // 2. SIMD块级比较主循环（批量处理完整块）
    while offset + block_size ≤ min_len:
        // ===================== SIMD核心操作1：加载数据到向量寄存器 =====================
        // 从A的offset位置，加载block_size字节到SIMD向量vec_A
        vec_A = simd_load(A + offset)
        // 从B的offset位置，加载block_size字节到SIMD向量vec_B
        vec_B = simd_load(B + offset)

        // ===================== SIMD核心操作2：向量级逐字节比较 =====================
        // 逐字节比较vec_A和vec_B：相等→0xFF，不等→0x00，存入结果向量vec_C
        vec_C = simd_compare_eq(vec_A, vec_B)

        // ===================== SIMD核心操作3：生成相等掩码 =====================
        // 提取vec_C中每个字节的最高位，拼接为整数掩码mask
        // 掩码规则：字节相等→bit=1，不等→bit=0
        mask = simd_move_mask(vec_C)

        // ===================== SIMD核心操作4：判断当前块是否全相等 =====================
        // mask+1后按block_size位取模，结果为0→全相等，非0→存在不等字节
        if (mask + 1) & ((1 << block_size) - 1) == 0:
            // 当前块全相等，偏移量累加块大小，继续下一块
            offset += block_size
        else:
            // ===================== SIMD核心操作5：找块内首个不同字节 =====================
            // 计算mask末尾连续0的个数 = 块内首个不同字节的位置
            block_pos = count_trailing_zeros(mask)
            // 全局p = 已比较字节数 + 块内位置
            p = offset + block_pos
            return (p, B[p])  // 找到首个不同字节，直接返回OVC

    // 3. 处理剩余不足一个SIMD块的字节（标量收尾）
    while offset < min_len:
        if A[offset] != B[offset]:
            p = offset
            return (p, B[p])
        offset += 1

    // 4. 特殊情况：两个串完全相同，p=最短串长度
    p = min_len
    return (p, B[p] if p < len_B else 0)

// 论文：短串标量实现（＜16字节）
function Scalar_Compute_OVC(A, B, min_len):
    for p from 0 to min_len - 1:
        if A[p] != B[p]:
            return (p, B[p])
    return (min_len, B[min_len] if min_len < len(B) else 0)

好的，上述内容之后你懂了 OVC 吗？实际上这里的性质才刚刚开始

OVC 在败者树中的 Compare

我们需要回到之前的图 Table 4。我们假设:

  1. OVC 流初始化的时候，类似一个最小的空字符串，每条流的第一个值都可以算出 (offset=0, value=value[0]) 的一个 OVC
  2. 假设每条流有一个自己的 OVC（per-stream OVC），和之前一样

img

我们可以按照论文列出一个算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Data: s₁, s₂: strings of length l with offset-value codes relative to the same base row
Result: n ∈ ℤ such that n ≤ 0 ⇔ s₁ ≤ s₂; larger string has OVC w.r.t the smaller one

if s₁.ovc ≠ s₂.ovc then
    return s₁.ovc − s₂.ovc
else
    if s₁.ovc = 0 then
        return 0  /* both strings are duplicates of the base */
    end
    i ← offset(s₁.ovc) + 1
    while i < l do
        if s₁[i] ≠ s₂[i] then
            if s₁[i] < s₂[i] then
                s₂.ovc ← (i, s₂[i])  /* new OVC relative to the winner */
                return −1
            else
                s₁.ovc ← (i, s₁[i])  /* new OVC relative to the winner */
                return 1
            end
        end
        i ← i + 1
    end
    s₂.ovc ← 0  /* new duplicate found */
    return 0
end

和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Data: S₁, S₂: sorted sequences of rows with offset-value codes
Result: S₀: merged sorted sequence of rows with offset-value codes

i₁ ← 0
i₂ ← 0
for i ← 0 to |S₁| + |S₂| − 1 do
    if CmpOVC(S₁[i₁], S₂[i₂]) ≤ 0 then
        S₀[i] ← S₁[i₁]
        i₁ ← i₁ + 1
    else
        S₀[i] ← S₂[i₂]
        i₂ ← i₂ + 1
    end
end

这个地方有两个地方值得注意:

  1. 0 的 061 OVC 向上移动的时候，整条链路上的 OVC 都是和上条流本流的值比较的，如果这条流只比较 OVC 就退出，那么这个地方下一条流对比的值
  2. 另一个比较好理解，i ← offset(s₁.ovc) + 1，这个地方是从 equal 的 OVC offset + 1 开始比较。

我们重点关注 (1)

  1. 假设原来 index 都是 0，那么整条链路已知 OVC(A0, A1), OVC(A0, B0), OVC(A0, C0)
  2. 假设最后 A1 还是新的最小，那么我们希望拿到 OVC(A1, B0)，OVC(A1, C0)
  3. 如果 OVC 相等，那么会找到相等的 OVC Offset 来重算 OVC，这个地方没有问题
  4. 如果 OVC 不相等
    1. 如果 offset 不相等，那么比较失败的应该 offset 还是比较失败的 offset，OVC 保持不变
    2. 如果 offset 相等，比较失败的 value 更小，还是保留

所以如果 A0 最小，那么最后 OVC(A1, B0) = OVC(A0, B0)

实际上，关于别的论文还提到了个 OVC 推论:

$ovc(A, C) = \max(ovc(A, B), ovc(B, C))$