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的字母排序，之后通过倒排索引查询，会比暴力查询效率高很多。