《大规模分布式计算深入解析》7.1 过滤语义:预过滤、后过滤与候选膨胀

标准过滤、迭代过滤和显式后过滤是不同策略;图导航可穿过非匹配节点,选择率不能保证固定倍数一定凑满K。

结果资格不等于导航资格

过滤条件P规定哪些对象可返回。精确子集扫描可以先生成匹配ID集合,只对这些行算距;图检索则可能仍需穿过不匹配节点保持连通,甚至为这些节点算距。因此“预过滤后所有距离只算匹配集”只适用于指定执行算法,不能当通用图索引性质。

链0→1→2,只允许返回2;若禁止展开不匹配的1,2将不可达。本卷HNSW层搜索测试区分导航与结果资格,找到2但不返回1。

三种过滤顺序

Milvus2.5文档区分标准过滤与迭代过滤:前者把条件用于限制ANN结果范围;后者通过迭代候选逐个判断直到达到目标或耗尽。显式后过滤则先取一个固定候选集,再丢不符项。后过滤不足K时不能假装返回完整K。

可枚举的基线

6个一维点0..5,查询1,条件为偶数ID。无标量索引的精确预过滤做6次谓词判断、3次向量距离,结果0/2/4。若先粗排出奇数1/3和偶数0,再后过滤,候选内只剩0。这里谓词、算距、候选和结果是四个计数。

生产的标量索引可直接取得匹配ID,不必扫描全部条件;图导航又有不同距离成本。不要把这些路径混成一张固定10000次距离的表。

候选膨胀是观测,不是保证

全库10%匹配,在相关性与过滤独立的随机假设下可用10倍作为粗略期望,但最近邻区域可能几乎全不匹配。取1000候选不保证一定得到100条。报告选择率、候选中匹配率、实际过量读取和不足率,不能仅用全库比例推导。

旧探针top50中cat0比例22%只是该结果集统计,既不能证明Milvus采用后过滤,也不能证明“候选膨胀显著”的内部执行机制。

架构与流程

flowchart TD
    Q["查询:向量、过滤条件、快照、K"] --> ROUTE["选分片与分区;固定路由版本"]
    ROUTE --> SCALAR["可用标量索引 / 位图 / 条件求值"]
    SCALAR --> PLAN{"选定执行策略"}
    PLAN -->|"精确子集扫描"| FLAT["只对匹配行计算精确距离"]
    PLAN -->|"带过滤图检索"| GRAPH["图导航:导航资格与结果资格分开"]
    PLAN -->|"迭代过滤"| ITER["逐批候选;判断条件;不足则继续"]
    FLAT --> C["各分片实际候选ID与分数"]
    GRAPH --> C
    ITER --> C
    C --> FINE["若有量化粗排,则读取原向量精排"]
    FINE --> LOCAL["各片保留足量有序结果"]
    LOCAL --> GLOBAL["协调者按统一度量归并、去重与并列规则"]
    GLOBAL --> PAGE["先取offset+limit,再返回所需页"]
    PAGE --> RESP["返回实际条数;记录不足原因"]
    ROUTE -.-> METRICS["分别记:分片RPC、谓词次数、算距次数、候选数、IO与返回数"]
    GRAPH -.-> METRICS
    FINE -.-> METRICS
    GLOBAL -.-> METRICS

实现与验证边界

模型执行真实谓词筛选、精确子集与固定候选后过滤,并验证非匹配桥可导航。原生filter的结果正确不等于内部计划已观测;不由结果类别比例推断策略。

下载卷十三实验包 。Java 8入口为 lab.RunAll;本节对应 filter.FilterSuite / hnsw.HnswSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析·向量数据库与 AI 检索内核》 · 目录与学习路径(45 篇)
  2. 《大规模分布式计算深入解析》15.3 自研向量引擎:可执行骨架与工程缺口
  3. 《大规模分布式计算深入解析》14.1 Milvus:组件架构、段管理与检索链路