请问milvus filtering的实现机制？

[xiaobingxia-at]

最近在公司内部部署milvus，内部有提问，从大体量数据 search while filtering的过程中，milvus是如何保证搜索质量和搜索延迟的？
能否简单解释一下这个filtering metadata的机制？是：

1. 从index搜top-n，然后filter，如果不够了，继续搜下一个page的top-n，再filter。直到最后的结果满足了top-n个数据点？
2. 还是其他优化方式？

除此之代，大家也想了解一下，用partition key。通过search filter by partition key and metadata的整个过程。

1. 每个partition key对应的partition有自己的index吗？（尽管很多partition key定义的逻辑partition最终是划在一个物理partition中）
2. partition key定义后的collection，数据分布是怎么样的呢？（比如，一个物理分区下有很多逻辑分区，每个逻辑分区下有自己的segment，每个segment有自己的index？还是其他分布方式）
3. 能不能search by "filtering by multiple partition key values"?
   谢谢。

[xiaobingxia-at]

如果有发表的文章介绍实现机制就最好了。谢谢。

[yhmo]

原理很简单，主要原理是“先过滤，后搜索”，"bitset机制"
https://milvus.io/docs/bitset.md#Overview
https://milvus.io/docs/filtered-search.md#Filtered-Search

假设有5条数据：
{id:1, vector1}
{id:2, vector2}
{id:3, vector3}
{id:4, vector4}
{id:5, vector5}

建立一个具有5个标志位的bitset: [1, 1, 1, 1, 1]
如果你search with filter "id > 3"，那么就把这个bitset设置为 [0, 0, 0, 1, 1]
然后搜索的时候就只计算后边两条，前3条直接skip
如果topk=2，那么就正好两条数据返回。如果topk=3，也只返回两条，因为符合条件的就两条。如果topk=1，那就把两条结果中最近的那条返回。

=======================================================================
partition无非就是把数据从物理上隔离，每个partition的数据放在一个单独的文件夹下
partition key无非就是自动划分partition，搜索时自动找到parititon

每个collection里有若干partiiton，每个partition里有若干个segment，每个segment有单独的index

打个比方，一个collection想当于一个学校，一个partition相当于一个年级，一个segment想当于一个班

==================================================================
"filtering by multiple partition key values" --------------------------- 当然可以，就好比我想从某个学校里的2年级和4年级这两个年级里找到姓刘的小学生。

[liliu-z]

@yhmo @liliu-z 再次感谢各位的详细解答。 最后确认一件事，如果过滤量比较大。假如没有转化为暴搜，还是通过HNSW索引搜索。最差结果只会出现搜不够的情况，不会出现召回率降低的情况（相比没有任何过滤的情况），我的理解对吗？谢谢。

这个recall的ground truth也是过滤之后暴搜的结果，recall会下降。比如搜topk，这k个点都在图的一个角落，entrypoint进去后到这个角落的路径上的点都被过滤了。哪怕选择踩过去，由于ef(size of the candidate list)限制，会导致没到这个角落就返回了，recall为0。 扩大ef有助于缓解

[xiaobingxia-at]

@liliu-z 目前索引转暴力搜索的“比例”是多少？比如filter的数据量达到多少百分比会变成暴力搜索？

哪怕选择踩过去，由于ef(size of the candidate list)限制，会导致没到这个角落就返回了，recall为0。 扩大ef有助于缓解

嗯嗯，我的表达可能不太准确。应该说，要么就是返回的结果不够k个。但一旦返回了，这个返回的结果就应该和正常HNSW无过滤搜索的结果是一致的。对吗？

[xiaofan-luan]

这个是不一定，我们基本能保证k个结果返回，但是结果不一致时很可能的。比如某一个点，所有的邻居都被包围了，就可能会漏结果

[xiaobingxia-at]

@xiaofan-luan 不好意思，我再补充一下。
比如，无过滤用HNSW，返回的结果是1,2,3,4,5
有过滤用HNSW，返回的结果可能是1,2,3 （漏掉了4,5），但是无论怎样不会出现返回6,7,8的情况。这个理解对吗？
然后，提高ef值，可能会从返回1,2,3变成1,2,3,4,5，但是会更慢。

[liliu-z]

@xiaofan-luan 不好意思，我再补充一下。 比如，无过滤用HNSW，返回的结果是1,2,3,4,5 有过滤用HNSW，返回的结果可能是1,2,3 （漏掉了4,5），但是无论怎样不会出现返回6,7,8的情况。这个理解对吗？ 然后，提高ef值，可能会从返回1,2,3变成1,2,3,4,5，但是会更慢。

是的