在数据分析里，bitmap 是一个非常好用的数据结构——AND / OR / XOR 几下就能把集合运算做完，既快又省。但它有一个天然的能力边界：每个位置只能回答「存在(0)或不存在(1)」。一旦需求变成「每个 key 对应的那个实数是多少」——停留时长、订单金额、某个维度的计数——bitmap 就不够用了。这时候我们需要退化成宽表，而宽表的压缩性能远弱于Bitmap。
这篇博客介绍 ClickHouse 社区最近合入的 NumericIndexedVector。它的目标就是填上这个空白：把一列 (key, value) 数据组织成「以 key 为下标的稀疏向量」——通过 Bitmap 把存储压得紧凑，按 key 做 pointwise 加减乘除和聚合则直接在 Bitmap 上用与或非（AND / OR / NOT）完成，不用先还原回行式 (key, value)。
本文是 NumericIndexedVector 系列的第一篇，把 why / what / how 一次讲清楚——动机、BSI 编码思想、加减乘除与比较的位级算法、以及在 ClickHouse 侧的工程落地。下一篇会接着讲「怎么用好」和「实测效果」。
1. 从 Bitmap 到 RoaringBitmap
Bitmap 的本质很直白——一串连续的二进制位，每一位对应一个整数是否属于这个集合。第 i 位为 1 表示整数 i 在集合里，0 表示不在。
两个 bitmap 就能对两个集合做任意布尔运算：AND 是交集、OR 是并集、XOR 是对称差、ANDNOT 是差集。再配一个 POPCOUNT，就能在 O(n/64)（标量指令）、O(n/256)（AVX2）、O(n/512)（AVX-512）的复杂度下数出集合大小。
在 OLAP 场景下，bitmap 最常见的用法有三种：
- 倒排索引 / 布尔过滤：多个条件
AND起来，就是多个 bitmap 做一次AND——每增加一个过滤条件几乎只增加一次位运算。 - 用户画像 / 标签系统：每个标签维护一个 bitmap（谁有这个标签），人群圈选就是标签 bitmap 的布尔运算。
- uniq 去重计数：把 user-id 塞进一个 bitmap，最后
POPCOUNT出去重基数——不需要排序、不需要 hash 表。
但朴素 bitmap 还有一层更现实的问题：稀疏。拿 UInt32 做 key 就意味着 2³² (≈ 4.3 × 10⁹) 个 bit——哪怕集合里实际只有几千个元素，也要恒定占用 512 MB 的存储。RoaringBitmap 通过 分桶 + 多种 container 自适应的方法避免了这个问题，是目前最高效的实现之一，对于 UInt32 场景 key 的实现具体如下：
- 按 key 的高 16 位分桶，低 16 位在桶内表示；每个桶最多装 2¹⁶ 个元素。
- 每个桶根据当前的基数和分布，从三种 container 里挑一种：
- Array container：基数 ≤ 4096 时用排序数组，存储 = 2 字节 × 基数。
- Bitmap container：基数较大时切到 8 KB 的原始 bitmap，随机访问 O(1)。
- Run container：连续整数区间多时存
(start, length)对，压缩更彻底。
- 所有布尔运算（
AND/OR/ANDNOT/XOR）在每种 container 上都有专门实现，而且走 SIMD，充分利用了向量化能力。
稀疏和稠密场景下都能拿到接近最优的存储，同时保持按位运算能力。RoaringBitmap 有官方站和多语言参考实现；ClickHouse 里大名鼎鼎的 AggregateFunction(groupBitmap, UInt32) 底层就是它。
如果你详细了解 RoaringBitmap，就会发现他的实现性能非常高，包括存储和压缩。 但即便如此，其能力边界依旧清晰：每个位置只能表达「存在 / 不存在」。无法将位置的值扩展到实数域。而数据分析中常见的远不止是否活跃，是否点击这样的 0/1 指标，更多的是消费时长，消费金额等实数域的指标，这种指标，我们如何能利用 RoaringBitmap 的存储性能？再进一步，我们希望这些实数域指标的加减乘除运算也直接基于 RoaringBitmap 的 And/Or/Not/Xor 来做，能做到吗？
NumericIndexedVector 解决了上面的两个问题，其底层使用 RoaringBitmap 存储，因此理解 RoaringBitmap 的原理对用好 NumericIndexedVector 非常有帮助。
2. 数据分析场景抽象
数据分析里有一类非常常见的查询：两张大表按某个 UInt32 key 做 join，再按 key 做 filter / 聚合 / 点运算。key 可以是 user-id、item-id、session-id、device-id……形态不限。
SELECT A.key, f(A.val_a, B.val_b)
FROM A JOIN B ON A.key = B.key;这种查询的典型代价包括：
key基数动辄千万、上亿；比如像微信、抖音这样日活过亿的产品，这类计算每天要吃掉 PB 级 IO 和百万级 CPU 核时。- hash join 要按
key把两张表重分布（shuffle）； - join 之后每行做一次
f，如果后续再按行sum聚合，则全程都是 row-wise 扫表。
一个自然的设想是：如果把要计算的 val_a，val_b 压缩成「以 key 为维度的向量」，那 join 的语义可以被「两个向量同一 position 就是同一 key」的约定消化掉；算术则可以变成「每个 position 做一次」的 pointwise 运算。bitmap 已经在布尔列上做到了这一点——问题是，能不能在实数列上也做到？
答案是可以。这就是 NumericIndexedVector 的核心思想。
3. NumericIndexedVector 核心思想
NumericIndexedVector基于论文 Large-Scale Metric Computation in Online Controlled Experiment Platform 实现，其关键技巧是 Bit-Sliced Index (BSI)。
假设要把一个 (key: UInt32, value: UInt64) 的映射表示成一个向量。value 是 UInt64，最多 64 位，所以准备 64 个 bitmap——记为 。每个 bitmap 对应 value 的一个二进制位：
当且仅当第 个 key 对应的 value 的第 位是 1。
用一个简单的加权和就能把 value() 还原出来：
一个小例子
4 个 key（编号 j = 0, 1, 2, 3），对应的值分别是 5、2、7、0。用 3-bit 表示的话：
key j | value | bit 2 | bit 1 | bit 0 |
|---|---|---|---|---|
| 0 | 5 (101) | 1 | 0 | 1 |
| 1 | 2 (010) | 0 | 1 | 0 |
| 2 | 7 (111) | 1 | 1 | 1 |
| 3 | 0 (000) | 0 | 0 | 0 |
三个 bitmap 分别是：
- （第 0 位为 1 的 key 集合）
校验：C[0] = 1·1 + 0·2 + 1·4 = 5 ✓，C[2] = 1 + 2 + 4 = 7 ✓。
整体视图
- 原始 BSI 定义在非负整数上；
NumericIndexedVector用补码把它扩展到有符号（下一节详述）。 - 通过 定点小数（fixed-point） 进一步扩展到实数域：约定低 位作为小数部分、其余作为整数部分，存储时按 取整。以
UInt64+ 14 位小数为例，最小刻度是 ，单值最大舍入误差 （约 5 位有效十进制小数）；整数部分仍保留 50 位（最大值 ），常见的指标如停留时长这类都够用，对于金额类，一般上游直接乘以一个系数，变成整数比较好，零误差。 - 真正值得记住的是：每个 都是一个独立的 RoaringBitmap。稀疏 key 空间下每个 bitmap 都很紧凑(第二篇文章中还有一些优化方法能让 bitmap 极致紧凑)，所有 bitmap 之间的「按位布尔运算」都可以走 RoaringBitmap 已有的 SIMD 实现。
一个 NumericIndexedVector 就是若干个 RoaringBitmap 的有序堆叠，再加上一点元信息（位宽、是否有符号）。下面看算术和比较是怎么在这种堆叠上做出来的。
4. 位级算法：加 / 减 / 乘 / 除 / 比较
下文统一用 ^ / & / &~ / | 表示 bitmap 的 XOR / AND / ANDNOT / OR； 个 bitmap 从低位到高位排列为 X[0]..X[N-1]、Y[0]..Y[N-1]。本节所有伪代码的都出自论文 Large-Scale Metric Computation in Online Controlled Experiment Platform。
4.1 加法：把全加器搬到 bitmap 层
单比特全加器把两个输入位 、 与前一位进位 Cin 产生和位 与新进位 Cout：
Sᵢ = Xᵢ ^ Yᵢ ^ Cin
Cout = (Xᵢ & Yᵢ) | (Cin & (Xᵢ ^ Yᵢ))把 、 从「第 位的那个比特」替换成「第 个 bitmap」，^ / & / | 直接换成 bitmap 的按位运算，就得到 BSI 上的加法：
input: X[0..N-1], Y[0..N-1]
output: S[0..N-1]
bitmap Cin = empty;
for i in 0..N-1:
S[i] = X[i] ^ Y[i] ^ Cin;
Cin = (X[i] & Y[i]) | (Cin & (X[i] ^ Y[i])); 轮循环、每轮做常数次（约 5 次）bitmap 按位运算；总时间复杂度大致是 ，其中 是一次 bitmap 按位运算的成本（每轮的常数因子被 big-O 吸收）。结果保留同位宽——最高位的 Cout 若非空，那就是溢出，要么按位宽截断，要么工程上用更宽的输出位宽容纳。
4.2 减法：借位代替进位
全减器把进位换成借位 Bin：
Dᵢ = Xᵢ ^ Yᵢ ^ Bin
Bout = ((Yᵢ | Bin) &~ Xᵢ) | (Bin & Yᵢ)bitmap 版本一一对应：
input: X[0..N-1], Y[0..N-1]
output: D[0..N-1]
bitmap Bin = empty;
for i in 0..N-1:
D[i] = X[i] ^ Y[i] ^ Bin;
Bin = ((Y[i] | Bin) &~ X[i]) | (Bin & Y[i]);这里值得注意的是：循环结束时留下的那个借位 Bin，正好是 X < Y 的结果 bitmap——这是比较算子能复用减法路径的原因（下一小节会直接拿来用）。
4.3 乘法：竖式展开 + 加法复用
乘法没法单步闭式，按位展开成竖式——对 Y 的每一位 i，如果 Y[i] 非空，就把 X & Y[i] 当作被加数、左移 i 位加到累加器 M 上：
input: X[0..N-1], Y[0..N-1]
output: M[0..2N-1] // 结果位宽最多 2N
bitmap M[2N] = {empty};
for i in 0..N-1:
if Y[i] is empty: continue;
bitmap S[N];
for j in 0..N-1:
S[j] = X[j] & Y[i];
bitmap Cin = empty, tmp;
for k in i..i+N-1:
tmp = M[k] ^ S[k-i] ^ Cin;
Cin = (M[k] & S[k-i]) | (Cin & (M[k] ^ S[k-i]));
M[k] = tmp;外层看 Y 的每一位，内层是一次 4.1 的加法递推。结果位宽最多 2N；工程实现会按预定位宽截断，下一节讲这种取舍。
⚙️ 实际实现的取舍：上面的位级竖式是数学上最直接的做法，但 BSI 压缩域里”模拟硬件乘法”常数因子很大（每一位都要做一整轮加法递推，总开销 ）。
NumericIndexedVector的实现走另一条路——先把两侧 vector 解码成(key, value)明细数组，按行做 Float64 乘法，再重新编码回 BSI。回路牺牲了”全程在压缩域”的优雅，但常数小很多。具体见AggregateFunctionGroupNumericIndexedVectorDataBSI.h中的pointwiseRawBinaryOperate。
4.4 比较：减法符号位 + 等值判定
有了减法，< / > 几乎是白送的——把 4.2 的递推只保留借位输出 L：
// L = 1 表示 X[j] < Y[j]
bitmap L = empty;
for i in 0..N-1:
L = ((Y[i] | L) &~ X[i]) | (L & Y[i]);> 把 X 和 Y 互换即可。
等值判定走另一条路——存在任一位不同即不等：
// E = 1 表示 X[j] == Y[j]
// U 取 X 或 Y 中较稀疏一侧的非零 key 集作为候选
bitmap E = U;
for i in 0..N-1:
E = E &~ (X[i] ^ Y[i]);!= 在 E 上取反即可；<= / >= 则把 < / > 与 == 的结果 OR 起来：
bitmap L = empty;
bitmap E = U;
for i in 0..N-1:
L = ((Y[i] | L) &~ X[i]) | (L & Y[i]);
E = E &~ (X[i] ^ Y[i]);
LE = L | E;所有比较算子的输出都是一个 value ∈ {0, 1} 的 vector——语义上就是「满足条件的 key 集合」。这个 vector 可以直接喂给 numericIndexedVectorPointwiseMultiply，实现「按条件保留值」的 filter——下一篇会大量使用这个范式。
4.5 除法：移位 + 比较 + 掩码减法的循环
除法没有像加 / 减 / 乘那样直接的位级闭式，但可以借硬件中经典的”恢复型二进制长除法”思路（详见 sistenix 的图解教程）：从最高 quotient 位开始，每一位都是一次 shift → compare → masked subtract——
- 把除数左移 位；
- 这个比较结果就是 quotient 的第 位 （每个 key 上独立一位）；
- 在 的 key 上，把 减去 ，然后继续下一位。
工程实现里因为 NumericIndexedVector 支持定点小数，正式进入循环前会先把被除数 整体左移 decimal_bm_num 位以保留小数精度；被除数和除数 align 到同一位宽与小数位之后再做循环：
input: X[0..N-1], Y[0..N-1] // 被除数 X、除数 Y（已 align 到 N 位）
output: Q[0..N-1] // 商
bitmap Q[N] = {empty};
// 把 Y 整体左移到最高位 —— 后面循环每轮右移 1 位，等价于 (原 Y) << i
Y = shift_left(Y, N);
for i in N-1 .. 0:
Y = shift_right(Y, 1); // 现在 Y 等于 (原 Y) << i
// 比较：a_i = X > Y —— {0,1} bitmap，即 quotient 第 i 位
Q[i] = isGreaterThan(X, Y);
// 掩码减法：仅在 Q[i] = 1 的 key 上把 X 减去 Y
masked_Y[0..N-1] = { Y[j] & Q[i] for j in 0..N-1 };
X = subtract(X, masked_Y);外层 轮，每轮一次比较 + 一次掩码减法——比较走 4.4 的 递推、减法走 4.2 的 递推，整体复杂度大致是 。这也是除法比加 / 减 / 乘明显贵的根本原因：每个 quotient 位都要付出一整轮比较 + 一整轮减法。
工程实现里还有一个剪枝：被除数中存在但除数里不存在的 key 会被先过滤掉（对所有除数 bitmap 求并集再 AND 回被除数），避免”除以空”产生歧义结果。
⚙️ 实际实现的取舍：除法和乘法一样，BSI 域里位级长除法的常数因子也很大（每一位都要 compare + masked subtract，总开销 ）。
NumericIndexedVector的实现走”decode → compute → encode”——把两侧解码成明细，按行做 Float64 除法，再重编码回 BSI，复用 4.3 同一条pointwiseRawBinaryOperate路径。前面的硬件长除法仍然是理解 BSI 域内”如何能做”的最佳模型，只是工程权衡选择了简洁与常数因子。
5. 位宽选择与有符号扩展
位宽在构造时固定
原始 BSI 天然支持变长——数值多大就拿多少个 bitmap。NumericIndexedVector 选择 在构造时就固定位宽 N 和是否有符号，类比 C++ 里的整数类型系统：
- 运算路径更简单：所有循环都是
for i in 0..N-1，不用在运行时推导 bitmap 数量； - 高位未被用上的那些 bitmap 全是空的——既不占存储，也不占计算；
- 两个要做 pointwise 的 vector 必须位宽一致，否则需要先显式转换。
这也解释了一个常被问到的问题——位宽取得宽一点会不会白白吃存储？不会。一个 UInt32 vector 的 32 个 bitmap 里，如果值大多落在 [0, 255]，那么 bit 8 以上的所有 bitmap 都是空的，序列化后只占极小的头部开销。存储代价正比于实际使用的位数，不是声明的位宽。
有符号整数：补码扩展
BSI 原始定义是非负整数；要支持负数，沿用硬件的做法——补码：
- 最高位作为符号位；
- 加法 / 减法的递推公式不变，溢出的
Cout直接丢弃（wrap-around）； - 乘法需要对符号单独处理（或用无符号做完再按异号取负）；
- 比较在符号位上多加一层处理：两侧符号不同时，负的那一侧一定更小。
具体的边界策略（溢出截断 vs 抛异常、除以 0 的定义域）在实现里都有对应分支，想看细节的可以直接读 PR-74193。
实数支持：定点小数的工程默认值
第 3 节里我们已经提过，BSI 可以通过定点小数扩展到实数域。对于 Float32 / Float64 这类输入，NumericIndexedVector 在源码里固化了一组默认配置（BSINumericIndexedVector 的常量）：
| 维度 | 默认值 | 含义 |
|---|---|---|
DEFAULT_INTEGER_BIT_NUM | 40 | 整数部分位宽：有符号下 ，覆盖大多数业务量级（金额、计数、时长） |
DEFAULT_FRACTION_BIT_NUM | 24 | 小数部分位宽：最小刻度 ，约 7 位有效十进制小数 |
MAX_TOTAL_BIT_NUM | 64 | 硬约束 integer_bit_num + fraction_bit_num ≤ 64 |
MAX_FRACTION_BIT_NUM | 24 | 小数位宽上限：超过这个精度对分析意义不大，徒增存储 / 计算成本 |
为什么不是 IEEE 754 的浮点表示？因为浮点的”指数部分变长”打破了 BSI”每层独立 bitmap”的前提——每个 key 的尾数对齐方式不一样，按位切片就没意义了。定点小数把每个 value 强制对齐到同一刻度，这样每一层 bitmap 才能独立做按位运算。
value 为 0 vs key 不存在：zero_indexes 补丁
BSI 自身只有一种”空值”——所有层 bitmap 在某个 key 上全是 0。但分析场景里 “显式 value = 0” 和 “key 完全不存在” 是两种不同的语义（比如”某用户充值额是 0” vs “某用户根本没在表里出现过”）。NumericIndexedVector 用一个独立的 zero_indexes bitmap 专门记下”显式存在但值为 0”的 key：
data_array：64 个 BSI bitmap layer，记所有 value ≠ 0 的(key, value)zero_indexes：单独一个 RoaringBitmap，记所有 value = 0 的 key
这意味着求 cardinality 是 data_array_keys union zero_indexes，按 key 取值时若 BSI 各层全 0 还要再查一次 zero_indexes。这条不在 BSI 论文里、但工程上必须，否则 numericIndexedVectorCardinality 和 numericIndexedVectorGetValue 在 0 值上会和”不存在”撞语义。
6. ClickHouse 落地：类型 + 聚合函数 + 普通 UDF
ClickHouse 侧把 NumericIndexedVector 分三层做出来：
┌───────────────────────────────────────────┐
│ 数据类型 │
│ AggregateFunction( │
│ groupNumericIndexedVector, ...) │
└───────────────────────────────────────────┘
▲ ▲
│ │
┌──────────┴────────┐ ┌────────┴───────────┐
│ 聚合函数 │ │ 普通 UDF │
│ group... 家族 │ │ pointwise / 比较 │
│ (State/Merge/ │ │ / 提取 / 聚合 │
│ Finalize) │ │ │
└───────────────────┘ └────────────────────┘数据类型
复用 ClickHouse 既有的 AggregateFunction(...) 骨架，构造时要指定两个参数（顺序是 key 在前、value 在后）：
- key 类型：目前只支持
UInt8/16/32和对应的Int8/16/32——因为底层 RoaringBitmap 内部用 32 位整数索引；64 位 key 的扩展走”分桶”路径，下一篇会展开。 - 底层数值类型 (value)：决定位宽、符号与是否定点小数；支持
UInt8/16/32/64、对应的Int系列，以及Float32 / Float64。
表达式长这样：
AggregateFunction(groupNumericIndexedVector, UInt32, UInt64)
-- key=UInt32, value=UInt64Float32 / Float64 走的是上一节的 40 + 24 定点编码。
聚合函数：group... 家族
groupNumericIndexedVector(key, value)——GROUP BY下按 key 聚合成一个 vector；语义上等价于「按 key 做 sum 再装进 vector」。groupNumericIndexedVectorState(...)——返回中间 state，和AggregateFunction列配合，供物化视图 / 预聚合表把 vector 持久化（下一篇会展开）。numericIndexedVectorBuild(map)——不走GROUP BY、直接从一个Map构造。
普通 UDF
所有 UDF 都作用在已经构造好的 vector 上，按用途分四类：
点运算算术（两侧都是 vector，或 vector + scalar）：
numericIndexedVectorPointwiseAdd/Subtract/Multiply/Divide
点运算比较（输出 value ∈ {0, 1} 的 vector）：
numericIndexedVectorPointwiseEqual/NotEqualnumericIndexedVectorPointwiseLess/LessEqual/Greater/GreaterEqual
提取：
numericIndexedVectorGetValue(v, key)——按 key 取单个值；numericIndexedVectorToMap(v)——还原成Map(key, value)。
聚合（输出标量）：
numericIndexedVectorAllValueSum(v)——对 vector 内所有 value 求和；numericIndexedVectorCardinality(v)——统计非零 key 的个数。
后续扩展的 numericIndexedVectorPointwiseMin / Max 以及对应的 global min / max（PR-88840）语义上可以用「比较 × 乘法 × 加法」组合出来，但直接实现能省去一次中间 vector。
结语 + 下一篇预告
正文里的 BSI 编码、位级伪代码、定点小数和 zero_indexes 这套补丁——本质上都在回答同一个问题：怎么让一个原本只能存”在不在”的 bitmap 去承载”具体数值”，又不付出宽表化的存储代价。 答案是用一摞 RoaringBitmap 把 value 的二进制位切片，让所有算术都退化成 RoaringBitmap 之间的与或非。这条路径既是 BSI 论文的核心创新，也圈定了它的边界。几条没在正文里直接强调、但用之前最好心里有数的事：
- 数据要稀疏才划算。如果 key 空间 95% 都填满，BSI 的所有层会全部退化成稠密的 bitmap container，存储不省、SIMD 加速也跑不出花来。它真正的甜区是”key 空间几亿、实际几十万到几千万”这种稀疏度。
- 位宽要克制——尤其是小数位。整数位宽多取一点其实不太亏：第 5 节说过，没用到的高位 bitmap 是空的，存储不占、对空 bitmap 做按位运算成本也接近 0（乘法伪代码里都有
if Y[i] is empty: continue;）。但 小数位不一样：定点把每个 value 都对齐到 刻度，绝大多数 value 在小数层都是非空的，每多一位都是实打实的存储 + 计算开销。Float64默认的 24 位小数已经在”分析够用”和”不浪费”之间取了平衡，再往上加意义不大。 - 算子并不全在压缩域。第 4 节容易让人产生”所有运算都在 BSI 域内做”的错觉——其实只有 add / sub / compare 是这样；mul / div 一旦上场就是行式 Float64 的”展开 → 行式算 → 再压”。SQL 上看是一行
numericIndexedVectorPointwiseMultiply，底层是一次完整的 decode → compute → encode 回路。 zero_indexes这个补丁是”分析语义”决定的。算法层面 value=0 和 key 缺失等价，但分析场景里二者必须区分。同样的分裂在物化视图、序列化、SUM 语义里都会反复出现，下一篇会再碰到。
下一篇 把视角换到「怎么用好」——什么样的 workload 值得切、三个 SQL 改写范式（pointwise、join 消除、条件求和）、怎么通过分桶让 RoaringBitmap 最省 + 把 32 位 index 扩到 64 位 key、物化视图与位宽选择的工程实践，以及一份来自论文实测的 benchmark（存储降维、单点计算加速、join 替代、ad-hoc 查询延迟）。