向量召回过滤优化

背景

目前向量检索中的过滤机制是在遍历到一个向量后，计算filter的结果看当前向量是否满足条件，如果不满足条件则放弃当前节点。因此遍历结束后，所有的向量都是满足过滤条件的。但因为向量检索所扫描的点数是固定的（默认扫描1%的数据），如果满足filter条件的文档非常少，会出现结果数少甚至无结果的情况。为了召回结果，只能调整扫描比例，有时甚至需要扫描全部数据才有结果。但扫描比例提高后，查询耗时会增加很多。

优化原理

为了解决满足过滤条件文档少，向量召回无结果的问题。我们先预估满足filter条件的文档数，如果数量少则直接使用filter的结果再计算向量相似度。如果文档数多，再走一次向量召回。流程如下：

解析：（建立倒排索引 > 解析filter表达式 > 查询优化）

1. 对所有的字段都建了单字段倒排索引（目前不支持text字段）

2. 解析filter表达式，遍历语法数进行倒排处理：

   1. attrName = constValue, 过滤条件为=时，如果左边是属性字段且有倒排，右边是常量，改写为倒排条件：attrName: constValue

   2. AND条件：对AND条件的左右分别进行处理，可以转倒排的转倒排，不能转的部分保留filter

   3. OR条件：如果左右有一个不能转，则整改query转换失败，直接走向量查询

   4. 对部分function函数特别处理：

      1. in/contain：转化为OR索引query

      2. range: 转化为range索引（暂时不支持）

3. 转倒排后，按query和filter条件先查询500个结果（可配置）

   1. 如果结果数少于500，直接使用这些结果，计算向量相似度

   2. 如果结果数大于等于500，对比最后一个结果的docId占所有文档的比例。

      1. 如果最后一个结果的docId覆盖了所有数据的80%（可配置）以上，认为命中的结果数少，接着查询剩余的文档。最后计算相似度。

      2. 否则，使用向量查询召回结果。

示例说明：

假设用户有100w doc，其中满足count=1的有600条，开启优化后，prefetch_size=500，prefetch_coverage=0.8，按如下查询：

{
    "vector": [0.1, 0.2, 0.3],
    "topK": 10,
    "namespace": "123",
    "filter": "count = 1 ",
    "searchParams": "{\"vector_service.search.enable_filter_optimize\":true}"
}

1. 预查询：将count = 1 作为倒排条件，查询出600条，600>500，进入比例计算

2. 比例计算：取满足条件的第500条记录的docid，判断其覆盖了多少比例的数据，若>80% 则继续查询剩余文档，若<80%，则使用向量查询召回结果。

参数介绍

因为转倒排优化需要先查询一次，如果被过滤掉的文档少，会增量查询的耗时，因此设置了开关。

示例：

{
    "vector": [0.1, 0.2, 0.3],
    "topK": 10,
    "namespace": "123",
    "filter": "count = 1 AND tag=\"text\"",
    "searchParams": "{\"vector_service.search.enable_filter_optimize\":true}"
}

filter解析说明

1. AND

count = 1 AND tag = "text"

转换结果（使用query字符串表示，实际为一棵语法树）

QUERY: count:'1' AND tag:'text'
FILTER: 无

2. AND部分

tag = 'text' AND count > 1

转换为

QUERY: tag:'text'
FILTER: count > 1

3. OR

count = 1 OR tag = "text"

转换为

QUERY: count:'1' OR tag:'text'
FILTER: 无

4. OR部分

tag = 'text' OR count > 1

无法转换

5. in/contain

in(tag, 'text|image')

转换为

QUERY: tag:'text' OR tag:'image'