Bitset 如何实现向量搜索的多功能性

作者:糖果
发布时间:2024-04-19 03:08:00 (9天前)
来源:https://milvus.io/blog/2022-2-14-bitset.md

本文由倪安琪转载。

随着Milvus 2.0的发布，提供了矢量数据库的各种新的基本功能。在这些新特性中，时间旅行、属性过滤和删除操作是相互关联的，因为这三个特性是通过一种常见的机制——bitset 来实现的。

因此，本文旨在阐明 Milvus 中 bitset 的概念，并通过三个示例说明它是如何支持删除操作、时间旅行和属性过滤的。

##### 什么是位集？
位集是一组位号（“0”和“1”），可用于表示某些数据信息。使用位集，您可以紧凑而高效地存储某些类型的数据，而不是将它们存储在 Ints、float 或 chars 中。位集在布尔逻辑上工作，根据该逻辑，输出的值是有效还是无效，通常分别用“1”和“0”表示。“1”代表有效，“0”代表无效。由于位集高效且可以节省存储空间，因此它们还可以用于实现属性过滤、删除操作、时间旅行等许多功能。

从 0.7.0 版本开始，Milvus 引入了 bitset 的概念来启用删除功能。更具体地说，bitset 用于标记段中的每一行是否被删除。已删除的实体在相应的位集中标记为“1”，因此，在搜索或查询期间将不会计算已删除的实体。

在 Milvus 2.0 版本中，扩展了 bitset 的应用，使能更多的特性，比如属性过滤和时间旅行。bitset 中的一般原则保持不变。也就是说，如果实体在相应的位集中标记为“1”，则在搜索或查询期间将忽略该实体。Bitsets 用于在 Milvus 中启用 3 个功能：

- 属性过滤
- 数据删除
- 时间旅行查询

##### 在 Milvus 中 bitset 是如何工作的？
以下示例用于说明 bitset 在 Milvus 中的工作原理。

##### 先决条件
假设有一个包含八个实体的段，并且一系列数据操作语言 (DML) 事件按下图所示的顺序发生。

1. primary_keys当时间戳ts等于 100时，插入四个实体，分别为 [1, 2, 3, 4]。
2. 当时间戳等于 200时，插入其余四个实体，primary_keys它们是 [5, 6, 7, 8] 。ts
3. 当时间戳等于 300primary_keys时，删除 [7, 8] 的实体。ts
4. 只有 [1, 3, 5, 7] 的实体primary_keys满足属性过滤条件。

![](/user/files/SmuKT-bqcSgTEeZSKWbdgOkG65Yie_slgbUfbTVWsKM.jpg)
*DML 事件的顺序。*

##### 案例一
假设用户设置的time_travel值为 150。也就是说，用户在ts= 150 时对 Milvus 中存储的数据进行查询。bitset 生成过程如图 1 所示。

在初始过滤阶段，结果filter_bitset应该是 [1, 0, 1, 0, 1, 0, 1, 0] 因为实体 [1, 3, 5, 7] 是有效的过滤结果并标记为“1”在位集中。然而，实体[4,5,6,7]在ts等于150时甚至没有插入向量数据库。因此，无论过滤条件如何，这四个实体都应标记为“0”。现在 bitset 结果应该是 [1, 0, 1, 0, 0, 0, 0, 0]。由于在 Milvus 中，bitset 计算的一般原理是在搜索或查询时忽略 bitset 中标记为“1”的实体，因此需要翻转经过 Time Travel 和属性过滤后的 bitset 结果，以便与删除相结合位图。的翻转结果filter_bitset应该是 [0, 1, 0, 1, 1, 1, 1, 1]。

至于删除bitset del_bitset，初始值应该是[0, 0, 0, 0, 0, 0, 1, 1]。但是，实体 7 和 8 直到ts300 才被删除。因此，当ts150 时，实体 7 和 8 仍然有效。因此，del_bitsetTime Travel 之后的值应该是 [0, 0, 0, 0, 0, 0, 0, 0]。

现在我们在时间旅行和属性过滤之后有两个位集：filter_bitset[0, 1, 0, 1, 1, 1, 1, 1] 和del_bitset[0, 0, 0, 0, 0, 0, 0, 0]。将这两个位集与“或”二元逻辑运算符结合起来。的最终值为result_bitset[0, 1, 0, 1, 1, 1, 1, 1]。也就是说，在接下来的搜索或查询阶段，只会计算实体 1 和实体 3。
![](/user/files/WlEE2bWuMtWn7lg_1Y2kgaJUy2xg5HLvSruAHItCP0o.jpeg)
*图 1. 时间旅行 = 150 的搜索。*

##### 案例二
假设用户设置的time_travel值为 250。也就是说，当ts= 250 时，用户对 Milvus 中存储的数据进行查询。bitset 生成过程如图 2 所示。

与情况一一样，filter_bitset初始属性过滤阶段的结果应该是 [1, 0, 1, 0, 1, 0, 1, 0]。

ts当= 250时，所有实体 [1, 2, 3, 4, 5, 6, 7, 8] 都被插入到向量数据库中。因此，之前的结果filter_bitset保持不变。同样，我们需要翻转 的结果filter_bitset，我们将得到 [0, 1, 0, 1, 0, 1, 0, 1]。

至于删除bitset del_bitset，初始值应该是[0, 0, 0, 0, 0, 0, 1, 1]。ts但是，实体 7 和 8 直到300才被删除。因此，当ts250 时，实体 7 和 8 仍然有效。因此，del_bitsetTime Travel 之后的值应该是 [0, 0, 0, 0, 0, 0, 0, 0]。

现在我们在时间旅行和属性过滤之后有两个位集：filter_bitset[0, 1, 0, 1, 0, 1, 0, 1] 和del_bitset[0, 0, 0, 0, 0, 0, 0, 0]。将这两个位集与“或”二元逻辑运算符结合起来。的最终值为result_bitset[0, 1, 0, 1, 0, 1, 0, 1]。这并不是说，只有实体 [1, 3, 5, 7] 将在接下来的搜索或查询阶段被计算。

![](/user/files/lrPrAEGPxLwvaRIkg4rWA_u8aj4Mu0bJehqzONkAgWI.jpeg)
*图 2. 时间旅行 = 250 的搜索。*

##### 案例三
假设用户设置的time_travel值为 350。也就是说，当ts= 350 时，用户对 Milvus 中存储的数据进行查询。bitset 生成过程如图 3 所示。

与情况一和情况二相同，filter_bitset初始属性过滤阶段的结果是[0, 1, 0, 1, 0, 1, 0, 1]。

ts所有实体 [1, 2, 3, 4, 5, 6, 7, 8] 都在= 350时插入到向量库中，因此最终的翻转结果filter_bitset为 [0, 1, 0, 1, 0, 1 , 0, 1]，与情况二相同。

至于删除 bitset ，由于实体 7 和 8 在=350del_bitset时已经被删除，因此其结果应该是 [0, 0, 0, 0, 0, 0, 1, 1]。tsdel_bitset

现在我们在时间旅行和属性过滤之后有两个位集：filter_bitset[0, 1, 0, 1, 0, 1, 0, 1] 和del_bitset[0, 0, 0, 0, 0, 0, 1, 1]。将这两个位集与“或”二元逻辑运算符结合起来。的最终值为result_bitset[0, 1, 0, 1, 0, 1, 1, 1]。这并不是说，只有实体 [1, 3, 5] 将在接下来的搜索或查询阶段被计算。

![](/user/files/vZjCZkjcU8a74UnmVAGYJo1CD3YyGHFRFCmtQWNvcic.jpeg)
*图 3. 时间旅行 = 350 的搜索。*

##### 下一步是什么？
在本系列博客中，我们之前已经介绍了Milvus 2.0中数据删除的设计。

在本系列的后续文章中，我们将介绍 Milvus 2.0 中数据压缩、动态负载均衡的设计。敬请期待。

1 条回复

动动手指，沙发就是你的了！

登录后才能参与评论