Milvus 核心设计(5)--- scalar indexwork mechanism
目录
背景
Scalar index 简介
属性过滤
扫描数据段
相似性搜索
返回结果
举例说明
1. 属性过滤
2. 扫描数据段
3. 相似性搜索
实际应用中的考虑
Scalar Index 方式
Auto indexing
Inverted indexing
背景
继续Milvus的很细设计,前面主要阐述了Milvus 在 vector simalairity 上的处理策略及index 方式。今天主要讲下scalar index。应该说对于所有的 db 实现,scalar index 都是需要的,无论是否是 关系型数据库,还是是否采用 k-v 存储等模式,有的东西是触类旁通的。Milvus 在处理scalar index 时,并不是孤立处理,而是结合了 bitset 提前过滤 + vector similarity 共同应对user query 提出的挑战。下面进入正题。
Scalar index 简介
向量相似性搜索过程中,Milvus 使用了属性过滤条件(expr)来扫描每个数据段(segment),并将过滤结果(bitset,一种位集合,用于高效表示哪些元素满足条件)与查询向量(data)一起应用于相似性搜索中。这种方式可以极大地提高搜索效率,因为它允许Milvus在执行耗时的相似性计算之前,先通过简单的属性过滤快速排除掉大量不满足条件的数据点。
具体来说,过程如下:
属性过滤
用户定义了一个或多个属性过滤条件(expr),这些条件用于筛选数据集中满足特定属性要求的向量。这些条件可以基于向量的元数据(如时间戳、地理位置、分类标签等)来定义。
扫描数据段
Milvus遍历或索引每个数据段,应用这些属性过滤条件。对于每个数据段,它会生成一个bitset,这个bitset中的每一位代表数据段中对应位置的向量是否满足过滤条件。
相似性搜索
在得到过滤后的bitset后,Milvus只针对那些标记为“满足条件”的向量进行相似性搜索。这意味着它不再需要计算所有向量的相似性,而只需计算那些经过初步筛选、更有可能与查询向量相似的向量的相似性。
返回结果
最后,Milvus根据相似性得分对满足条件的向量进行排序,并返回最相似的向量及其相关信息(如ID、相似度分数等)给用户。
这种结合属性过滤和相似性搜索的方法,使得Milvus在处理大规模向量数据集时,能够更加高效和准确地响应用户的查询需求。它特别适用于那些既需要基于内容的相似性搜索,又需要基于属性快速筛选的场景,如推荐系统、图像检索、文档聚类等领域。
这里有一点要说明,你使用milvus,基本决定了你的 collection 世界中,一定是 vector + scalar 共存的case,原因很简单,如果仅有scalar,我相信你使用 mysql,sqlserver,甚至oracle 足以,小的应用你甚至使用sqlite估计也行,因为你的 sql query 足以胜任user 各种需求。你之所以选择向量数据库,肯定是要么有LLM的vector 需求,要么有pic,audio甚至video 的需求。还是那句话,使用场景决定了product 的选择。所以你的collection 多半可能是 一个+多个 vector embeddding + 多个 attibute 的vector 说明。
举例说明
假设我们有一个电商平台,该平台使用Milvus来存储商品的图像特征向量,并希望为用户提供基于图像相似性的商品推荐功能。同时,商品还具有一些属性信息,如价格、品牌、类别等。
1. 属性过滤
用户查询:用户希望找到一款与某张图片相似,但价格不超过5000元,且品牌为“Huawei”的商品。
属性过滤条件:
- 价格 <= 5000
- 品牌 = "Huawei"
在Milvus中,这些属性信息会与图像特征向量一起存储,但它们是分开处理的。当用户发起查询时,Milvus首先会应用这些属性过滤条件来筛选出满足条件的商品。
2. 扫描数据段
数据段扫描:
- Milvus会将存储的商品数据分为多个数据段(segment),每个数据段包含一部分商品的特征向量和属性信息。
- 当属性过滤条件被应用时,Milvus会遍历或索引这些数据段,检查每个商品是否满足过滤条件。
- 对于满足条件的商品,Milvus会生成一个bitset,其中每个位对应一个商品,满足条件的商品对应的位被设置为1,不满足的则被设置为0。
3. 相似性搜索
相似性搜索:
- 在得到过滤后的bitset后,Milvus只针对那些标记为“满足条件”的商品特征向量进行相似性搜索。
- 用户提供的查询图片首先被转换为特征向量。
- Milvus使用适当的相似性度量(如余弦相似度)来计算查询向量与满足条件的商品特征向量之间的相似性。
- 根据相似性得分,Milvus对商品进行排序,并返回最相似的几个商品给用户。
实际应用中的考虑
- 性能优化:Milvus通过高效的索引结构和算法来加速数据段的扫描和相似性搜索过程,确保即使在处理大规模数据集时也能提供快速响应。
- 多模态支持:Milvus不仅支持图像特征向量的存储和检索,还支持文本、音频等多种模态的数据,为跨模态检索提供了可能。
- 可扩展性:Milvus支持分布式部署,可以随着数据量的增长而水平扩展,以满足更高并发和更大存储容量的需求。
Scalar Index 方式
Auto indexing
你不用对你的scalar attribute 做任何辅助说明,Milvus 使用 auto indexing 的方式完成Scalar Indexing 的索引。
实际上你看了Milvus 的源码之后,你会发现,实际上 Auto indexing 就是 底层用的 inverted indexing。这里可能milvus 为了扩展,将inverted indexing 作为了 default 的 scalar indexing 来使用。
所以本质上来说要看下 Inverted indexing。
Inverted indexing
倒排索引,如果你曾经是比较资深的programmmer,你应该不会陌生。我那时候还没有ElasticSearch,用的是Lucene,后来有了ElasticSearch 和 Solr,但是万变不离其宗,其核心还是倒排索引。说直白点就是把一个句子拆分为词组的 tomkenizer 并 标识这些词在哪些句子中出现或是标识出现的概率。Milvus的 inverted indexing 出自一个开源库:Tantivy。应该说 Tantivy 的实现并不是ElasticSerach 或是 Solr,但是其思想有些类似,有兴趣的可以去看下源码。github 地址:
Tantivy Github 源码地址
再次说明了,成功是站在巨人的肩上,其实Milvus 用了不少其他中间件来保证自己的功能特性,前面介绍过的就有:etcd,mysql,rockMQ,pluster etc。现在又看到了 Tantivy。你可能会问为什么Milvus 不使用 ElasticSearch或Solr,那肯定是那啥License等问题,但从技术的角度来说,Tantivy也足够优秀。或许有一天 Tantivy 的知名度会超过 ElasticSearch 也不一定。
我们看个例子:
这就是倒排索引,只不过不同人,不同版本实现时,倒排信息的精度有差别,这里是focus 在句子层面。不过对于 Milvus的使用,足以。
在单个查询,比如上面的例子,品牌=’huawei‘,那根据倒排索引,直接锁定包含’huawei‘品牌attribute的 document 或 segment。
在区间查询,比如还是上面的例子,价格<5000, 那还是根据倒排索引,直接锁定 价格 attribute的document 或segment。
或许区间的例子还不够透彻,因为range 的是数据。你查找的品牌获取不止一种,如果 brand in ['huawei', 'apple'] 首先会经过类似alpha的字母排序,之后通过倒排索引查询,会比暴力查询效率高很多。