2024年2月3日的FOSDEM会议上，Manticore的联合创始人 Peter Zaitsev 和Manticore的首席执行官 Sergey Nikolaev 进行了关于Manticore向量搜索的演讲。此次活动展示了数据库中向量搜索的最新动态。有关更详细的信息，Zaitsev的演讲录音可在上方找到。下面，您可以看到以文章形式呈现的主题更详细的摘要。

引言

在过去的两到三年中，数据库领域发生了几项关键变化：

• 一种新的“向量数据库”类别出现，包含2019年的Milvus、2020年的Vespa、2021年的Weaviate和2022年的Qdrant等开源平台，以及2019年推出的云解决方案Pinecone。这些数据库专注于向量搜索，侧重于各种机器学习模型的使用。然而，它们可能缺乏传统数据库的功能，如事务、分析、数据复制等。
• Elasticsearch在2019年增加了向量搜索功能。
• 然后，从2022年到2023年，包括Redis、OpenSearch、Cassandra、ClickHouse、Oracle、MongoDB和Manticore Search在内的成熟数据库，以及来自Azure、Amazon AWS和Cloudflare的云服务，开始提供向量搜索功能。
• 其他知名数据库，如MariaDB，正在整合向量搜索功能。
• 对于PostgreSQL用户，有自2021年起实现此功能的“pgvector”扩展。
• 虽然MySQL尚未宣布原生向量搜索功能的计划，但来自PlanetScale和AlibabaCloud等提供商的专有扩展可用。

向量空间和向量相似性

让我们讨论一下为什么最近如此多的数据库启用了向量搜索功能，以及它到底是什么。
让我们从一个具体的例子开始。考虑两种颜色：红色，RGB代码为(255, 0, 0)，和橙色，RGB代码为(255, 200, 152)。为了比较它们，让我们在三维图上绘制它们，其中每个点代表一种不同的颜色，坐标轴对应于颜色的红色、绿色和蓝色分量。然后我们从图的原点绘制向量到代表我们颜色的点。现在我们有两个向量：一个代表红色，另一个代表橙色。

如果我们想找到这两种颜色之间的相似性，一种方法可能是简单地测量向量之间的角度。这个角度可以从0到90度变化，或者如果我们通过取余弦来归一化，它将从0变化到1。然而，这种方法并没有考虑向量的大小，这意味着余弦对于颜色A、A1、A2将产生相同的值，尽管它们代表不同的色调。

为了解决这个问题，我们可以使用余弦相似性公式，它考虑了向量的长度——向量的点积除以它们大小的乘积。

这个概念就是向量搜索的本质。用颜色来可视化是简单的，但现在想象一下，代替三个颜色轴，我们有一个具有数百或数千个维度的空间，其中每个轴代表一个对象的特定特征。虽然我们无法轻易在幻灯片上描绘或完全可视化它，但在数学上是可行的，原则保持不变：您在多维空间中有向量，并计算它们之间的相似性。

还有其他一些公式可以找到向量相似性：例如点积相似性和欧几里得距离，但正如OpenAI API文档所说，它们之间的差异通常并不重要。

Screenshot: https://platform.openai.com/docs/guides/embeddings/which-distance-function-should-i-use

向量特征：稀疏向量

因此，一个对象可能具有各种特征。具有红色、绿色和蓝色分量的颜色是最简单的例子。在现实生活中，它通常更复杂。

例如，在文本搜索中，我们可以将文档表示为高维向量。这使我们引入了“词袋模型”的概念。该模型将文本转换为向量，其中每个维度对应于一个唯一的单词，值可以是单词存在的二进制指示符、出现次数的计数，或基于其频率和逆文档频率（称为TF-IDF）的单词权重，反映了一个单词在文档集合中的重要性。这被称为稀疏向量，因为大多数值为零，因为大多数文档没有很多单词。

在谈论像 Lucene 、 Elasticsearch 和 Manticore Search 这样的库和搜索引擎中的全文搜索时，稀疏向量有助于加快搜索速度。基本上，您可以创建一种特殊的索引，忽略没有搜索词的文档。因此，您不必每次都检查每个文档与您的搜索的匹配。稀疏向量也易于理解，它们在某种意义上可以被逆向工程。每个维度对应于一个特定的清晰特征，因此我们可以从我们的向量表示追溯到原始文本。这个概念已经存在大约50年。

Image: https://www.researchgate.net/figure/Figure4DocumentrepresentationintheVectorSpaceModel22_fig1_312471174

向量特征：密集向量

传统的文本搜索方法，如 TF-IDF ，已经存在了几十年，产生依赖于词频的稀疏词向量。主要问题是什么？它们通常忽视了单词使用的上下文。例如，术语“苹果”可能与水果和科技公司相关联，而没有区别，这可能导致它们在搜索中被相似地排名。

但考虑这个类比：在一个向量空间中，哪两个物体的接近度更高：一只猫和一只狗，还是一只猫和一辆车？生成稀疏向量的传统方法——如下图顶部所示的那种——可能难以提供有意义的答案。稀疏向量通常是高维的，大多数值为零，表示在给定文档或上下文中大多数单词的缺失。

然后，深度学习的革命来了，引入了上下文嵌入。这些是密集的向量表示，如图像下部所示。与可能具有数万维的稀疏向量相比，密集向量的维度较低（如图像中的784维），但充满了捕捉细微语义关系的连续值。这意味着同一个单词可以根据其上下文具有不同的向量表示，而不同的单词如果共享上下文也可以具有相似的向量。像 BERT 和 GPT 这样的技术使用这些密集向量来捕捉复杂的语言特征，包括语义关系，区分同义词和反义词，以及理解讽刺和俚语——这些任务对于早期的方法来说相当具有挑战性。

此外，深度学习不仅限于文本，还能够处理复杂的数据，如图像、音频和视频。这些也可以被转化为密集的向量表示，用于分类、识别和生成等任务。深度学习的兴起与数据可用性和计算能力的爆炸性增长相吻合，使得训练复杂模型成为可能，从而揭示数据中更深层次和更微妙的模式。

图像: https://cdn.sanity.io/images/vr8gru94/production/96a71c0c08ba669c5a5a3af564cbffee81af9c6d-1920x1080.png

嵌入

这些模型提供的向量称为“嵌入”。重要的是要理解，与之前显示的稀疏向量不同，其中每个元素可以代表文档中存在的单词等明确特征，嵌入的每个元素也代表一个特定特征，但在大多数情况下我们甚至不知道这个特征是什么。
例如， Jay Alammar 进行了一项有趣的实验 ，使用 GloVe 模型对维基百科进行向量化，然后用不同的颜色可视化一些单词的值。我们可以在这里看到：

1. 一条一致的红线出现在各种单词中，表示在一个维度上的相似性，尽管它所代表的具体属性仍然未被识别。
2. “女人”和“女孩”或“男人”和“男孩”等术语在多个维度上显示出相似性，暗示相关性。
3. 有趣的是，“男孩”和“女孩”之间的相似性与“女人”和“男人”不同，暗示着一个潜在的青春主题。
4. 除了涉及“水”这个术语的一个实例外，所有分析的单词都与人有关，而“水”则用于区分概念类别。
5. “国王”和“女王”之间的独特相似性与其他术语不同，可能暗示了对王权的抽象表示。

图像: https://jalammar.github.io/illustrated-word2vec/

因此，通过深度学习生成的密集向量嵌入以紧凑的形式捕捉了大量信息。与稀疏向量不同，密集嵌入的每个维度通常都是非零的，并且具有某种语义意义。这种丰富性是有代价的——对于密集嵌入，由于每个维度都密集填充了值，我们不能简单地跳过不包含特定术语的文档。相反，我们面临着将查询向量与数据集中每个文档向量进行比较的计算强度。这是一种自然资源密集型的暴力破解方法。

然而，已经开发出专门针对密集向量的索引。这些索引，如 KD 树、Ball 树或更现代的方法，如 HNSW （分层可导航小世界）图，非常智能，但有时为了快速，它们必须进行一些猜测。这种猜测可能意味着它们并不总是100%正确。数据库采用的最流行的索引是 HNSW，代表分层可导航小世界。它被 pgvector 扩展用于 Postgres、 Lucene 、 Opensearch 、 Redis 、 SOLR 、 Cassandra 、 Manticore Search 和 Elasticsearch 使用。它的算法构建了一个多层图结构。每一层都是一个图，其中每个节点（代表一个数据点）与其最近的邻居相连。底层包含所有节点（数据点），每个上层包含来自下层的节点子集。最上层的节点最少。搜索从上层开始，逐渐向下移动到下层。这种分层方法使搜索过程高效。简而言之，HNSW像其他索引一样，只是预生成了一些快捷方式，您可以使用这些快捷方式来加快查询处理。还有其他向量索引，如 Annoy ，由 Spotify 和其他人维护，每个索引在性能、资源消耗和准确性损失方面都有其优缺点。

Image: https://cdn.sanity.io/images/vr8gru94/production/d6e3a660654d9cb55f7ac137a736539e227296b6-1920x1080.png

K-nearest neighbours

向量搜索实际上是一个总括性术语，包括聚类、分类等各种任务。但通常，数据库为向量搜索添加的第一个特性是“最近邻搜索”（KNN），或其近亲“近似最近邻搜索”（ANN）。它之所以吸引人，是因为它使数据库能够找到与给定文档的向量最相似的文档，从而增强了数据库的强大搜索引擎能力，这是它们之前所缺乏的。

传统搜索引擎如Lucene、Elasticsearch、SOLR和Manticore Search处理各种自然语言处理任务——如形态学、同义词、停用词和例外——所有这些都旨在找到与给定查询匹配的文档。KNN通过不同的方式实现了类似的目标——仅仅比较与表中文档相关的向量，这些向量通常由外部机器学习模型提供。
让我们以 Manticore Search 为例，探索数据库中典型的向量搜索是什么样的。

首先，我们创建一个名为image_vector的列的表：

create table test ( title text, image_vector float_vector knn_type='hnsw' knn_dims='4' hnsw_similarity='l2' );

这个向量是 浮点类型 ，这很重要，因为不支持此数据类型的数据库必须首先添加它，因为稠密向量通常存储在浮点数组中。此时，您通常还需要通过指定向量维度大小、向量索引类型及其属性来配置字段。例如，我们指定要使用HNSW索引，向量的维度为5，相似度函数为l2，即欧几里得距离。

然后，我们向表中插入几条记录：

insert into test values ( 1, 'yellow bag', (0.653448,0.192478,0.017971,0.339821) ), ( 2, 'white bag', (-0.148894,0.748278,0.091892,-0.095406) );

每条记录都有一个标题和一个相应的向量，在现实场景中，这可能是深度学习模型的输出，编码某种形式的高维数据，如图像或声音、文本的嵌入，或来自OpenAI API的其他内容。此操作将数据存储在数据库中，并可能触发重建或调整索引。

接下来， 我们通过利用KNN函数执行向量搜索 ：

select id, knn_dist() from test where knn ( image_vector, 5, (0.286569,-0.031816,0.066684,0.032926) );

+------+------------+
| id   | knn_dist() |
+------+------------+
|    1 | 0.28146550 |
|    2 | 0.81527930 |
+------+------------+
2 rows in set (0.00 sec)

在这里，我们正在查询数据库，以定位与我们指定的输入向量最接近的向量。括号中的数字定义了我们要寻找最近邻的特定向量。此步骤对于任何旨在实现向量搜索功能的数据库至关重要。在此步骤中，数据库可以利用特定的索引方法，如HNSW，或通过将查询向量与表中的每个向量进行比较来执行暴力搜索，以找到最接近的匹配项。

返回的结果显示了与我们的输入向量最接近的向量的标题及其与查询的相应距离。较低的距离值表示与搜索查询的匹配更接近。

Embedding computation

到目前为止，大多数数据库和搜索引擎依赖于外部嵌入。这意味着当您插入文档时，必须事先从外部来源获取其嵌入，并将其与文档的其他字段一起包含。当搜索相似文档时也是如此：如果搜索是针对用户查询而不是现有文档，则需要使用机器学习模型为其计算嵌入，然后将其传递给数据库。此过程可能导致兼容性问题，需要管理额外的数据处理层，并可能在搜索性能上造成低效。这种方法的操作复杂性也高于必要水平。除了数据库，您可能还需要保持另一个服务运行以生成嵌入。

一些搜索引擎如Opensearch、Elasticsearch和Typesense现在通过自动创建嵌入来简化这一过程。它们甚至可以使用其他公司的工具，如OpenAI，来做到这一点。我认为我们很快会看到更多这样的情况。更多的数据库将开始自行生成嵌入，这可能会真正改变我们搜索和分析数据的方式。这一变化意味着数据库将不仅仅是存储数据；它们实际上会理解数据。通过使用机器学习和人工智能，这些数据库将变得更智能，能够预测和适应，并以更先进的方式处理数据。

Hybrid search approaches

一些搜索引擎采用了一种称为混合搜索的方法，它结合了传统的基于关键字的搜索和先进的神经网络技术。混合搜索模型在需要同时进行精确关键字匹配（由传统搜索技术提供）和更广泛的上下文识别（由向量搜索能力提供）的情况下表现出色。这种平衡的方法可以提高搜索结果的准确性。例如， Vespa 通过将其混合搜索的准确性与经典的BM25排名和ColBERT模型单独进行比较来测量 其混合搜索的准确性 。在他们的方法中，他们将经典的BM25作为第一阶段排名模型，并仅对根据BM25模型排名前K的文档计算混合分数。结果发现，混合搜索模式在大多数测试中优于它们各自的表现。

另一种更简单的方法是互惠排名融合（RRF），这是一种结合不同搜索算法排名的技术。RRF根据每个项目在每个列表中的排名计算得分，其中排名越高，得分越好。得分由公式1 / (rank + k)确定，其中'rank'是项目在列表中的位置，而'k'是用于调整较低排名影响的常数。通过对每个来源的这些修改后的互惠排名进行求和，RRF强调了不同系统之间的共识。这种方法融合了各种算法的优点，导致更强大和全面的搜索结果。

表格: https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa-part-two/
公式: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf

结论

向量搜索不仅仅是一个概念或搜索引擎的一个小众功能；它是一个实用工具，正在改变我们检索数据的方式。近年来，数据库领域发生了重大变化，新兴的向量专注数据库和已有的数据库增加了向量搜索功能。这反映了对更先进搜索功能的强烈需求，而向量搜索可以满足这一需求。先进的索引方法，如HNSW，使得向量搜索更快。

展望未来，我们预计数据库不仅仅支持向量搜索；它们可能会自己创建嵌入。这将使数据库更易于使用和更强大，将其从基本存储空间转变为能够理解和分析数据的智能系统。简而言之，向量搜索是数据管理和检索的重大转变，标志着该领域的一个激动人心的发展。