关键词搜索是 Weaviate 的 混合搜索 的一个组成部分，旨在返回 向量和关键词搜索的最佳组合。 混合搜索作为一种用于 RAG 和 Agentic AI 的工具，可以增加从数据集中检索的信息的广度和深度，但它也伴随着自身的挑战。
随着文本语料库的大小越来越大，与向量搜索相比，关键词搜索的执行时间可能会很长。 在这篇博文中，您将了解我们如何改进 Weaviate 的倒排索引，如何避免对包含查询词的所有文档进行评分，如何压缩倒排索引，以及使用 BlockMax WAND 在 Weaviate 中进行改进的更多信息。
BlockMax WAND 算法在 v1.29 中作为 技术预览版 提供。 这意味着该功能仍在开发中，未来版本可能会发生变化，包括潜在的破坏性更改。 目前不建议在生产环境中使用此功能。 有关如何启用它的说明，请在此处查看。
倒排索引和分词
关键词搜索通过将查询中的术语与数据库文档中的术语进行比较，对较少见的术语和在文档中更频繁出现的术语赋予更高的分数来工作。 在关键词搜索的上下文中，这些 术语 称为 tokens，但我们将在本博文中互换使用这些术语。
关键词搜索要求我们首先定义要搜索的术语。 这个过程的一个重要部分是 分词。 它将输入文档拆分为 tokens（即术语、数字或任何其他被认为需要单独搜索的重要内容）。
在这个简单的例子中，考虑一个由三个文档组成的数据集，其中包含一个属性，即标题，由单个句子和一个空格分词器组成，该分词器将文档转换为小写并按空格分割它们。
| 文档 ID | 文档标题 | 分词后的标题 |
|---|---|---|
| 1 | 混合搜索的 Web 开发人员指南 | [“a”，“web”，“developer”，“s”，“guide”，“to”，“hybrid”，“search”] |
| 2 | 释放混合搜索的力量 | [“unlocking”，“the”，“power”，“of”，“hybrid”，“search”] |
| 3 | 向量库与向量数据库 | [“vector”，“library”，“versus”，“vector”，“database”] |
表格：带有分词标题的示例数据集。
现在我们已经将文档转换为 词袋模型，我们可以在句子中找到单个查询词。 但是，必须遍历所有文档才能找到包含查询词的文档，这效率不高。
这就是 倒排索引 的倒序部分由来：与其从文档->术语，创建一个索引，从术语->文档。 它类似于书籍末尾的索引，但我们不是将术语映射到书页，而是使用发布列表将术语映射到文档。
发布列表是一个“发布”列表，其中包含对评分文档所需的信息
- 文档 ID：用于标识哪些文档包含该术语。
- 词频 (tf)，表示该术语在属性中出现的次数。 例如，文档 3 中
tf("vector")为 2，因为它出现了两次。
| 术语 | 发布列表 |
|---|---|
| hybrid | (文档 1，tf：1)；(文档 2，tf：1) |
| search | (文档 1，tf：1)；(文档 2，tf：1) |
| vector | (文档 3，tf：2) |
表格：示例数据集中术语 hybrid、search 和 vector 的发布列表。
当用户搜索查询时，我们以与分词文档相同的方式对查询进行分词。 因此，如果您想搜索 “Hybrid search or Vector search”，我们将得到 tokens ["hybrid", "search", "or", "vector"]。 检查每个 token 的发布列表，我们可以看到文档 1、2 和 3 至少包含一个查询 token。 但我们仍然需要对它们进行评分，以查看哪些文档与查询最相关。
tf-idf 和 BM25
并非所有术语都是一样的。 在我们的例子中，像“hybrid”、“vector”和“database”这样的词比“a”、“to”或“the”更有信息量。 为了有意义地对结果进行排名，我们需要根据以下因素对文档进行评分：idf（逆文档频率）是这种重要性的度量，基于与文档总数相比，术语出现在多少个文档中。 较高的值意味着更稀有的术语，将更多地贡献于文档的分数。 与 tf 结合使用，它就成为了关键词搜索的基石，tf-idf。
BM25 通过应用属性长度和频率饱和度归一化进一步完善了 tf-idf。
详尽搜索
计算 BM25 分数的详尽方法是检查包含至少一个查询词的所有文档并对它们进行评分。
但这需要大量的资源；大多数搜索都是为了找到前 10-100 个结果，即使有分页，对于每个搜索，最多也只有大约 100 个文档会显示给用户。 这意味着如果 100,000 个文档包含至少一个查询词（在包含 100 万个文档的数据库中，常见词的查询很正常），那么这是 0.1% 的文档，其中许多文档与查询完全无关，浪费了大量的 CPU 和 I/O 资源。
WAND
WAND（弱 AND） 采用倒排索引和 idf 来大大减少我们在搜索匹配前 k 个文档时需要检查的文档数量。
它依赖于两步搜索，以避免对顶级 k 搜索进行排名。
- 近似评估查询词发布列表，以识别具有最大影响启发式（基于 idf）的候选文档；
- 有希望的候选文档被完全评估，它们的精确分数被计算出来，如果分数高于最低分数，它们就会被添加到前 k 个结果中。
最大影响是术语可以对分数做出贡献的最大值。
它的上限是 idf，例如，仅包含术语 vector 的文档将具有等于 vector 的 idf 的最大影响。
- 当我们开始排名时，我们添加足够的文档来填充前 k 列表；
- 当我们获得 k 个候选文档时，列表已满，我们有一个要击败的下限，即排名最低文档的分数；
- 当我们前进时，我们可以开始跳过其术语的最大影响之和低于下限的文档。
WAND 是目前 Weaviate 中关键词搜索的基础。 下一节将展示为什么我们很高兴推出 BlockMax WAND。
BlockMax WAND
虽然 WAND 效果很好并且已经能够大大减少我们需要检查的文档数量，但它仍然存在一些限制：它依赖于所有文档的单个全局 idf 值，这依赖于假设可能只有一个文档只包含该术语。
BlockMax WAND (BMW) 是 WAND 的升级版
- 将发布列表划分为具有局部最大影响的块；
- 跳过并避免解码块中的文档 ID。
BMW 可以看作是一种元-WAND，我们使用最大影响（浅层前进）在块级别跳过文档，并使用块中的最大文档 ID 组合来甚至避免从磁盘加载整个块。
此表显示了 BlockMax WAND 输出的示例发布列表。 您可能会注意到，与上面显示的 WAND 的发布列表相比，这包含一些额外的元素。
一个块是一个迷你发布列表（文档 ID 和 tf 列表），具有自己的元数据
- 最大文档 ID：块中出现的最大文档 ID；
- 最大影响：块中文档的最大可能分数； 对于 tf-idf，这代表块内文档的最大 tf（规范 tf 等于 tf/prop 长度）。
| 数据集 | WAND | BlockMax WAND |
|---|---|---|
| MS Marco (8.6M 文档) | 15.1% | 6.7% (-56%) |
| Fever (5.4M 文档) | 20.8% | 8.4% (-60%) |
| Climate Fever (5.4M 文档) | 29.3% | 12.2% (-58%) |
表格：在标准 beir 数据集 上，Weaviate v1.29.0 在没有删除停用词的情况下，平均得分的文档查询词百分比。 详尽搜索始终需要检查至少包含一个查询词的 100% 的文档查询词。
实验结果表明，BlockMax WAND 能够进一步将检查的文档数量从已经很惊人的 15-30% 数量的得分词减少到 5-15%。 但是 BlockMax WAND 在实践中是如何工作的？
BlockMax WAND 演示
在 Weaviate，我们喜欢展示，而不仅仅是讲述。 这就是为什么我们创建了一个演示来向您展示 BlockMax WAND 在实践中是如何工作的！
- 输入您的文档、查询和搜索参数，看看详尽搜索、WAND 和 BlockMax WAND 是如何工作的；
- 获取已评分文档和区块的指标，并查看 BlockMax WAND 与 WAND 和 Exhaustive 搜索的改进之处；
- 与他人分享您的数据集和查询，以展示改进！
Varenc 文档 ID 和词频压缩
对于使用 tf-idf 或 BM25 进行评分，我们需要加载查询中每个词的词频和文档 ID。这需要存储和解码大量信息；
- 对于拥有 100 万个文档，每个文档包含 100 个词，我们需要存储和解码 1 亿个词频和文档 ID；
- 词频通常在 1-100 范围内，没有硬性上限。假设它们可能会增长到
2^32。按原样存储它们将需要 32 位 * 每个词的文档数； - 文档 ID 是 64 位无符号整数，我们需要为包含该词的每个文档存储它们。
分别以 4 和 8 字节为单位，100 000 000 * 12 = 1.2 GB 的数据，还不包括倒排索引结构的开销。我们能压缩这些数据吗？
考虑这组四个词频：12、3、100、1.此发布列表中的最大数字是 100，可以用二进制表示为 floor(log2(100)) + 1 = 7 位，而不是完整的 32 位。如果我们只将这些值存储为 7 位，而不是 32 位，并保留额外的 6 位（足以存储所有可能的位计数）来存储每个值的位计数呢？这个过程可以描述为一种 变长编码，我们称之为 varenc。
| 32 位词频 | 压缩数据 |
|---|---|
| 12, 3, 100, 1 | (7), 12, 3, 1, 3 |
4 * 32 位 = 128 位 | 6 + 4 * 7 位 = 79 位 |
表格：词频压缩示例。
即使有额外的 6 位来存储位计数，我们仍然能够将所需的位数从 128 位减少到 79 位。压缩收益直接转化为更大的列表，但需要注意，单个高值会增加位计数。
如果我们对文档 ID 应用相同的逻辑呢？在 Weaviate 中，文档 ID 实现为 64 位无符号整数，用于唯一标识文档。它们与面向外部的文档 UUID 相关联，并简化了内部数据管理。
文档 ID 是单调递增的；因此，它们与数据的规模处于同一数量级。
考虑从百万级索引中以下文档 ID 集合：1000000、1000003、1000004、1000007。
使用与 tf 相同的逻辑，floor(log2(1000000)) + 1 = 20，这意味着我们需要 20 位来存储这些 ID。按照之前的过程，6 + 4 * 20 = 86 位。
比存储它们未压缩所需的完整 4 * 64 = 256 位 更好，但我们可以利用一些属性来提高压缩效率。
为了使 WAND 和 BlockMax WAND 正常工作，文档 ID 始终按升序存储。此属性意味着我们可以使用 差分编码，并存储连续 ID 之间的差异，而不是 ID 本身。
| 原始数据（64 位文档 ID） | 差分编码 |
|---|---|
| 1000000, 1000003, 1000004, 1000007 | 1000000, (1000003-1000000), (1000004-1000003), (1000007-1000004) = 1000000, 3, 1, 3 |
表格：文档 ID 差分编码示例。
1000000、3、1、3 看起来更易于压缩，但列表的第一个值仍然大于差异。因此，我们将第一个值未压缩地存储为 64 位，并仅使用与之前相同的过程压缩差异值。
| 差分编码 | 压缩数据 |
|---|---|
| 1000000, 3, 1, 3 | 1000000, (2), 3, 1, 3 |
|
|
表格：文档 ID 压缩示例。
即使有额外的 6 位来存储位计数并编码第一个值的完整值，我们仍然能够将所需的位数从 256 位减少到 76 位，这比不使用差分编码的 86 位更好。
更大的列表将具有更好的压缩比，因为存储第一个值所需的位数比例已经考虑在内，并且我们只需要存储压缩的差分。
最后一个效率提升来自块索引：由于发布列表已排序并划分为文档块，我们将避免大多数需要一起编码文档 1 和文档 1000000 的情况，并在此过程中节省大量位。
在 Weaviate 中，这是为 128 个文档的块完成的
- 文档 ID 使用差分编码打包在一起+varenc 压缩；
- 词频 使用 varenc 压缩打包在一起；
- 块元数据（最大影响+最大文档 ID）存储在单独的结构中。在 BlockMax WAND 期间，我们使用此单独的元数据来检查是否需要通过检查最大影响和 ID 从磁盘加载块。如果不需要，我们将避免昂贵的磁盘读取，并提供更高效的内存、CPU 和 I/O 关键字搜索。
结合一种表示已删除文档的新方法和更高效的属性长度存储，我们能够将磁盘上的倒排索引大小减少 50% 到 90%（文件小 2-10 倍），具体取决于数据分布（具有较少唯一术语的较长属性将更好地压缩）。
| 数据集 | WAND | BlockMax WAND |
|---|---|---|
| MS Marco (8.6M 文档) | 10531 MB | 941 MB（-91%） |
| Fever/Climate Fever（5.4M 文档） | 9326 MB | 1175 MB（-87%） |
表格：比较标准 beir 数据集 上的 Weaviate v1.29.0 的 searchable 文件夹的大小。
这些辅助结构和压缩技术意味着我们不能在不更改数据表示方式的情况下充分利用 BlockMax WAND。因此，从 v1.29.0 开始，Weaviate 仅支持为新集合启用适当的环境变量的 BlockMax WAND 搜索。我们正在努力寻找一种透明地迁移现有数据库的方法。
结果
压缩比和减少的已评分文档数量看起来令人印象深刻，但它如何转化为性能？
我们的实验表明，平均 p50（中位数）查询时间减少到原始查询时间的 10-20%。
| 数据集 | WAND | BlockMax WAND |
|---|---|---|
| MS Marco (8.6M 文档) | 136 毫秒 | 27 毫秒（-80%） |
| Fever (5.4M 文档) | 517 毫秒 | 33 毫秒（-94%） |
| Climate Fever (5.4M 文档) | 712 毫秒 | 87 毫秒（-88%） |
表格：在标准 beir 数据集 上使用不进行停用词删除的测试查询，Weaviate v1.29.0 的平均 p50 查询时间（以毫秒为单位）。实验在 Apple M3 Max 36 GB 上执行。在 x86-64 云机器上观察到类似的收益
在内部测试中，使用 100M 文档，我们能够将 QPS 从 1 提高到 50，同时保持 p50 在 100-200 毫秒之间，p99 在 1000 毫秒。
术语表
- 倒排索引： 将术语映射到文档的数据结构
- 发布列表： 包含特定术语的文档列表，以及频率等元数据
- 词频 (tf)： 术语在文档中出现的频率
- 逆文档频率 (idf)： 衡量文档集合中术语的稀有程度
- BM25： 一种通过文档长度归一化增强 tf-idf 的评分算法
- WAND： 一种使用上限分数估计优化前 k 个检索的算法
- BlockMax WAND： 一种增强的 WAND，它将发布列表组织成块，以实现更高效的评分
- 差分编码： 存储连续值之间的差异，而不是绝对值
- 变长编码： 仅使用表示值所需的最小位数
总结
BlockMax WAND 通过优化倒排索引和使用先进的压缩技术，显著提高了 Weaviate 的文档评分速度。它减少了在关键字搜索期间检查的文档数量，从而加快了查询时间并减少了磁盘空间使用。
主要改进包括
- BlockMax WAND： 将发布列表划分为具有局部最大影响的块，从而能够更有效地跳过并避免不必要的加载；
- varenc 压缩： 压缩词频和文档 ID，将存储需求减少 50-90%。差分编码进一步增强了文档 ID 压缩；
- 性能提升： 将 p50 查询时间减少到原始查询时间的 10-20%，并显著提高每秒查询数 (QPS)。
这是使 Weaviate 的混合搜索达到十亿规模的第一个步骤。敬请期待未来的更多改进！这些优化使 Weaviate 中的关键字搜索更快、更高效。
BlockMax WAND 算法在 v1.29 中作为 技术预览版 提供。 这意味着该功能仍在开发中，未来版本可能会发生变化，包括潜在的破坏性更改。 目前不建议在生产环境中使用此功能。 有关如何启用它的说明，请在此处查看。
准备开始构建了吗？
请查看 快速入门教程，或使用 Weaviate Cloud (WCD) 的免费试用版构建令人惊叹的应用程序。