Endee向量数据库元数据过滤深度解析：RoaringBitmap预过滤如何让检索快10倍

Endee是一个高性能开源向量数据库（vector database），目标是让单节点承载多达 10 亿向量。在 RAG 检索、商品搜索等场景中，你几乎总需要带着元数据条件做查询，例如「City = NY 且 Age ∈ [18,25]」。Endee 的过滤系统采用RoaringBitmap 预过滤（Pre-Filtering）架构：先用位图集合运算算出合法 ID 集合，再自适应选择暴力搜索或过滤版 HNSW 图搜索。在高选择性过滤条件下，相比"先搜后滤"，这条路径的检索延迟可以缩短一个数量级（约 10 倍）。下面从执行流程、优化技巧到存储设计，带你完整看懂它的实现。

后过滤的困境：top-k 结果被过滤"打穿"

传统的**后过滤（Post-Filtering）**思路是：先让 HNSW 返回 top-k，再逐个检查是否满足条件。问题在于——如果 100 条结果里只有 2 条符合条件，系统被迫扩大ef参数重新搜索，图遍历开销成倍增加，最终召回的候选数量可能远超你需要计算距离的数量。

预过滤（Pre-Filtering）则反转了这个顺序：先确定"哪些 ID 有资格参与比较"，再在这个候选集上做距离计算。Endee 的官方设计文档 docs/filter.md 明确将这一策略列为全局执行主线：

The system prioritizesPre-Filteringfollowed by an adaptive search execution path.

RoaringBitmap 预过滤：一次过滤查询的三步执行流程

Endee 的所有元数据索引都以 RoaringBitmap 作为统一的中间表示——它压缩存储 ID 集合，并让AND交集、OR并集、contains()成员判断都是接近 O(1) 或 O(n/64) 的位运算。一次带过滤的查询会经历三个阶段（核心实现在 src/filter/filter.hpp#L209-L377 的computeFilterBitmap）：

第 1 步：解析条件并估计基数（Cardinality）

过滤条件使用类 MongoDB 的 JSON 语法，支持三种操作符：

每个原子条件先被翻译成一个位图，同时位图的cardinality()（元素个数）给出了该条件结果集的规模估计。

第 2 步：最便宜优先——小集合先交集，空集立即终止

这是整套设计中最精妙的一处优化。多个条件（AND语义）的位图会先按基数从小到大排序，再依次求交集：

// src/filter/filter.hpp — 按基数排序后逐个 AND std::sort(partial_results.begin(), partial_results.end(), [](const ndd::RoaringBitmap& a, const ndd::RoaringBitmap& b) { return a.cardinality() < b.cardinality(); });

（见 src/filter/filter.hpp#L361-L374）

背后的直觉很简单：City = "NY"可能只剩 500 个 ID，而Age ∈ [18,25]还有 1 万个，先交小的那个，中间结果会迅速"瘦身"。更妙的是早期终止——一旦中间交集变空，直接返回，剩余条件根本不用算。对于"不可能同时满足"的组合查询，这一步就能把成本压到接近零。

第 3 步：自适应搜索路径——暴力还是 HNSW？

得到最终的合法 ID 位图后，Endee 并不会无脑走 HNSW，而是根据位图规模在两条路径之间切换（决策逻辑在 src/core/ndd.hpp#L1564-L1614）：

阈值由常量PREFILTER_CARDINALITY_THRESHOLD定义（默认 10,000，见 src/utils/settings.hpp#L104），并可通过查询参数prefilter_threshold按请求调整（见 src/main.cpp#L932-L933）。

两条搜索路径的底层实现

策略 A：小规模暴力搜索。直接遍历位图中的 ID，批量从向量存储中取出向量，调用hnswlib::searchKnnSubset在子集上计算距离。因为候选集只有几千个，全量计算距离比走图更快——跳过了图的建边、邻域展开等一切固定开销。

策略 B：过滤版 HNSW。位图被封装成一个判断器，挂到 HNSW 的searchKnn搜索循环上（定义见 src/filter/filter.hpp#L48-L55）：

class BitMapFilterFunctor : public hnswlib::BaseFilterFunctor { bool operator()(ndd::idInt id) override { return bitmap_.contains(id); // 位图成员判断，近乎 O(1) } };

图搜索每扩展到一个节点，就用位图判断它是否"有资格"，不合格的直接跳过、继续前进。距离计算只发生在合法节点上，这就是"快 10 倍"的主要来源——被过滤掉的向量连距离都不用算。

三类元数据索引：为不同字段选对"数据结构"

预过滤能快，前提是"条件 → 位图"这一步本身要快。Endee 按字段类型提供了三套存储设计（完整方案见 docs/filter.md）：

数值索引：混合桶 B+ 树，为范围查询而生

数值字段（如 Age、Price）走的是 src/filter/numeric_index.hpp 中的"混合桶"结构：

• LMDB 充当粗粒度 B+ 树：键是[字段ID] + [32位基值]。浮点数先通过位翻转技巧映射为字典序与数值序一致的整数（float_to_sortable，见 src/filter/numeric_index.hpp#L34-L41），这样一次范围扫描就能覆盖整个区间；
• 桶内压缩存储：每个桶最多 1024 个值，用uint16_t增量（相对基值的差值）存储，大幅压缩空间；
• 桶级 Summary Bitmap：每个桶预存了一份"桶内所有 ID 的并集位图"。范围查询完全覆盖的中间桶直接取这份位图，零数组访问，O(1) 拿结果；只有部分重叠的边缘桶才需要逐值扫描。

类别索引：倒排索引，为精确匹配而生

类别字段（如 City）用文本键倒排索引（src/filter/category_index.hpp）：键为字段名:值（如City:NY），值就是序列化的 RoaringBitmap。精确匹配是一次键查找；$in查询则是多次查找后做位图并集。这个设计还天然支持前缀扫描，为后续 faceting（分面统计）留了余地。

布尔索引：双键设计，排在最后处理

布尔字段（如is_active）是类别索引的特例，只有两个键：is_active:0和is_active:1。由于布尔条件通常选中约 50% 的数据（选择性低），Endee 把它放在交集链的最后处理，避免用大而"松散"的位图拖累前面的交集运算。

实用调优清单：让你的过滤检索更快

1. 给条件排序不是必须的了：引擎会自动按基数排序执行，但你在业务上把最挑剔的条件写进过滤表达式，依然能受益于"空集早期终止"；
2. 调prefilter_threshold：如果你的过滤结果普遍在几千以内，调低阈值可以让更多查询走"暴力小集合"路径，跳过图开销；反之若过滤很宽松，调高阈值避免小图搜索退化成全量扫描；
3. 字段类型首写定终身：Endee 采用 First-Write Wins 的类型绑定（见 docs/filter.md#L88-L95），某字段第一次被索引的类型（数值/类别/布尔）会永久生效，后续类型不匹配的写入会被拒绝。设计数据模型时先定好字段类型，能避免索引腐坏；
4. 过滤字段别太长：类别值上限 255 字节，超长会直接报错；
5. 混合检索同样受益：带过滤的查询中，稀疏检索与稠密检索并行执行，两者都接收同一份过滤位图，最终用 RRF 融合（见 src/core/ndd.hpp#L1617-L1658）。

关键源码路径速查

小结

Endee 元数据过滤的速度秘密，可以浓缩成三句话：用 RoaringBitmap 把"记录检查"升级为"位图集合运算"；按基数从小到大求交集，并尽早终止；在暴力小集合搜索与过滤版 HNSW 之间自适应切换。预过滤不是单纯的一个技巧，而是一套"存储结构 + 集合运算 + 执行路径"协同设计的结果——这正是它能在一亿级向量上依然保持毫秒级过滤检索的原因。想动手验证的话，tests/filter_test.cpp 中的用例覆盖了从简单精确匹配到多条件混合逻辑的完整链路，是最好的入门路径。