# Vector search in old and modern databases

This article delves into the transformative world of vector search technology, charting its evolution and widespread adoption across both new and established database platforms.

{{< youtube sHwUgxztcqs >}}

2024年2月3日的FOSDEM会议上，Manticore联合创始人[Peter Zaitsev](https://peterzaitsev.com/)和Manticore首席执行官[Sergey Nikolaev](https://www.linkedin.com/in/snikolaev/)展示了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用户，有一个名为'pgvector'的扩展，自2021年以来实现了此功能。
* 虽然MySQL尚未宣布原生向量搜索功能的计划，但PlanetScale和阿里云等供应商提供了专有扩展。

![Alt text](./vector-search-in-databases/Vector_search_slide2.png)

### 向量空间与向量相似性

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

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

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

![Alt text](./vector-search-in-databases/Vector_search_slide4.png)

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

还有一些其他公式可以找到向量相似性：例如点积相似性和欧几里得距离，但正如OpenAI API文档所说，它们之间的差异通常并不重要。
![截图：https://platform.openai.com/docs/guides/embeddings/which-distance-function-should-i-use](./vector-search-in-databases/OpenAI.png "截图：https://platform.openai.com/docs/guides/embeddings/which-distance-function-should-i-use")

*截图：https://platform.openai.com/docs/guides/embeddings/which-distance-function-should-i-use*

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

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

在讨论图书馆和搜索引擎如[Lucene](https://lucene.apache.org/)、[Elasticsearch](https://github.com/elastic/elasticsearch)和[Manticore Search](https://manticoresearch.com/)中的全文搜索时，稀疏向量有助于加快搜索速度。基本上，你可以创建一种特殊的索引，忽略没有搜索词的文档。因此，你不需要每次都将所有文档与搜索进行比较。稀疏向量也易于理解，它们在某种程度上可以被逆向工程。每个维度对应一个特定的清晰特征，因此我们可以从向量表示追溯到原始文本。这个概念已经存在大约50年了。


![Alt text](./vector-search-in-databases/VectorSpaceMode.png)
*图片：https://www.researchgate.net/figure/Figure4DocumentrepresentationintheVectorSpaceModel22_fig1_312471174*

### 向量特征：密集向量

传统文本搜索方法如 [TF-IDF](https://manticoresearch.com/blog/tf-idf-in-a-nutshell/)，已有数十年历史，它们生成依赖于词频的稀疏词向量。主要问题？它们通常会忽略词语使用的上下文。例如，“apple”这个词可能与水果和科技公司相关，但没有区分，这可能导致在搜索中将它们排名相近。

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

随后，深度学习的革命引入了**上下文嵌入**。这些是密集向量表示，如图片底部所示。与可能有数万个维度的稀疏向量不同，密集向量的维度较低（如图片中的784维），但包含捕捉细微语义关系的连续值。这意味着，同一个词在不同上下文中可能有不同的向量表示，而不同词如果共享上下文也可能有相似的向量。像 [BERT](https://en.wikipedia.org/wiki/BERT_(language_model)) 和 [GPT](https://en.wikipedia.org/wiki/GPT-3) 这样的技术使用这些密集向量来捕捉复杂的语言特征，包括语义关系、区分同义词和反义词，以及理解讽刺和俚语——这些任务对早期方法来说相当具有挑战性。

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

![Alt text](./vector-search-in-databases/sparse_dense.png)
*图片：https://cdn.sanity.io/images/vr8gru94/production/96a71c0c08ba669c5a5a3af564cbffee81af9c6d-1920x1080.png*

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

1. 一条一致的红色线出现在各种词语中，表明在某一维度上存在相似性，尽管该维度具体代表什么属性仍未确定。
2. “woman”和“girl”或“man”和“boy”等词语在多个维度上显示相似性，表明它们相关。
3. 有趣的是，“boy”和“girl”之间的相似性与“woman”和“man”不同，暗示了一个关于青春的潜在主题。
4. 除了一个涉及“water”一词的例外，所有分析的词语都与人有关，“water”用于区分概念类别。
5. “king”和“queen”之间的独特相似性可能表明了对王权的抽象表示。

![Alt text](./vector-search-in-databases/Vector_search_slide8.png)
*图片：https://jalammar.github.io/illustrated-word2vec/*

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

然而，已经开发出专门针对密集向量的索引。这些索引，如 KD 树、Ball 树或更现代的方法如 [HNSW](https://arxiv.org/abs/1603.09320)（分层可导航小世界）图，相当智能，但有时为了速度必须进行一些猜测。这种猜测意味着它们并不总是能100%准确。数据库最流行的索引是 HNSW，全称是分层可导航小世界。它被 [pgvector](https://github.com/pgvector/pgvector) 扩展用于 Postgres，[Lucene](https://lucene.apache.org/)，[Opensearch](https://github.com/opensearch-project)，[Redis](https://github.com/redis/redis)，[SOLR](https://github.com/apache/solr)，[Cassandra](https://cassandra.apache.org/)，[Manticore Search](https://manticoresearch.com/) 和 [Elasticsearch](https://github.com/elastic/elasticsearch) 采用。其算法构建了一个多层图结构。每一层都是一个图，其中每个节点（代表一个数据点）连接到其最近的邻居。最底层包含所有节点（数据点），每一层上层包含下层节点的子集。最顶层的节点最少。搜索从上层开始，逐渐向下层移动。这种分层方法使搜索过程高效。简而言之，HNSW 像任何其他索引一样，只是预先生成了一些快捷方式，然后可以用于更快的查询处理。还有其他向量索引，如由 Spotify 等维护的 [Annoy](https://github.com/spotify/annoy)，每种都有其在性能、资源消耗和准确性损失方面的优缺点。

![替代文本](./vector-search-in-databases/HNSW.png)
*图片: https://cdn.sanity.io/images/vr8gru94/production/d6e3a660654d9cb55f7ac137a736539e227296b6-1920x1080.png*

### K近邻算法

向量搜索实际上是一个包含聚类、分类等任务的总称。但通常，数据库为向量搜索添加的第一个功能是“K近邻搜索”（KNN），或其近亲“近似最近邻搜索”（ANN）。它具有吸引力，因为它使数据库能够找到与给定文档向量最相似的文档，从而赋予数据库搜索引擎的强大功能，这是它们之前所缺乏的。

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

首先，我们创建一个带有名为`image_vector`的列的表：
```sql
create table test ( title text, image_vector float_vector knn_type='hnsw' knn_dims='4' hnsw_similarity='l2' );
```


这个向量是[浮点类型](https://manual.manticoresearch.com/Creating_a_table/Data_types#Float-vector)，这一点很重要，因为不支持此数据类型的数据库必须首先添加它，因为密集向量通常存储在浮点数组中。此时，你通常通过指定向量维度大小、向量索引类型及其属性来配置该字段。例如，我们指定要使用HNSW索引，向量的维度为5，相似度函数为`l2`，即欧几里得距离。

然后，我们将一些记录插入表中：
```sql
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函数执行向量搜索](https://manual.manticoresearch.com/Searching/KNN#KNN-vector-search)：
```sql
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），或者通过将查询向量与表中的每个向量进行比较来执行暴力搜索，以找到最接近的匹配。

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

![替代文本](./vector-search-in-databases/Vector_search_slide11.png)

### 嵌入计算

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

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

### 混合搜索方法

一些搜索引擎采用了称为混合搜索的方法，将传统的基于关键字的搜索与先进的神经网络技术相结合。混合搜索模型在需要同时进行精确关键字匹配（由传统搜索技术提供）和更广泛的情境识别（由向量搜索功能提供）的情况下表现出色。这种平衡的方法可以提高搜索结果的准确性。例如，[Vespa](https://github.com/vespa-engine/vespa)通过将其与经典的BM25排名和ColBERT模型分别进行比较，[测量了其混合搜索的准确性](https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa-part-two/)。在他们的方法中，他们使用经典的BM25作为第一阶段的排名模型，并仅对根据BM25模型排名前K的文档计算混合分数。结果发现，混合搜索模式在大多数测试中都优于其中的每一个。

另一种更简单的方法是倒数排名融合（RRF），这是一种结合不同搜索算法排名的技术。RRF根据每个项目在每个列表中的排名计算其得分，排名越高得分越好。得分由公式 1 / (rank + k) 确定，其中 'rank' 是项目在列表中的位置，'k' 是一个用于调整较低排名影响力的常数。通过将每个来源的修改后的倒数排名相加，RRF强调了不同系统之间的一致性。这种方法结合了各种算法的优势，从而产生更强大且全面的搜索结果。

![Alt text](./vector-search-in-databases/Vector_search_slide13.png)
*表格：https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa-part-two/
公式：https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf*

### 结论

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

展望未来，我们预计数据库将不仅仅支持向量搜索，它们很可能会自行生成嵌入。这将使数据库更易于使用且功能更强大，使其从基本的存储空间转变为能够理解和分析数据的智能系统。简而言之，向量搜索是数据管理和检索领域的重要转变，标志着该领域令人兴奋的发展。