DB 论文阅读：关系型数据库在 ANNS 上为什么慢？

本文是 Are There Fundamental Limitations in Supporting Vector Data Management in Relational Databases? A Case Study of PostgreSQL 的论文阅读记录，感兴趣的读者请参阅原论文了解更多细节。

该论文的通讯作者是 Jianguo Wang @ Purdue ，刚好也是 Milvus SIGMOD 论文的一作。根据主页信息来看，Milvus 这篇 SIGMOD 论文是 Prof. Wang 与 Zilliz 远程合作的项目。值得一提的是，Prof. Wang 从 2021 年进入学术界开始，已经稳定地在 SIGMOD、VLDB、ICDE 等顶级学术会议期刊上发表论文了，是数据库领域冉冉升起的学术新星。本文要介绍的论文，就发表于 ICDE 2024。

八卦结束，开始聊一聊这篇论文。正如标题所示，该论文旨在回答一个问题：关系型数据库在支持向量近似最近邻检索（ANNS）上，是否存在根本性的限制？具体地，该论文以 PASE 和 Faiss 分别作为关系型数据库和向量数据库的代表（实际上 Faiss 不能称得上是向量数据库，而是一个向量检索 library。不过其作为 ANNS 的代表性库，有不少专用向量数据库都基于 Faiss 构建，包括 Milvus。因此，本文后续仍称 Faiss 为向量数据库），比较二者在 ANNS 的索引构建时间、索引大小、查询耗时等指标上的差异，并分析 PASE 作为基于 PostgreSQL 的通用向量数据库，为什么在一些指标上成倍地逊于 Faiss 这一专用向量数据库。

幸运地是，尽管基于关系型数据库 PostgreSQL 构建的 PASE 在很多指标上都逊于 Faiss，但是导致这些问题的原因并非无法克服。该论文总结了 7 点 PASE 逊于 Faiss 的原因和相应的解决方案。我们跟随论文来逐一介绍。

1. 引言

目前提供向量 ANNS 功能的数据库可以分为两类：

通用向量数据库：已有数据库新增对向量数据存储与检索的支持。
专用向量数据库：为向量数据存储、索引与检索专门设计与优化的数据库。

一般认为（该论文的实验也证实了），通用向量数据库（如：PASE、pgvector、AnalyticDB-V 等基于 PostgreSQL 的向量数据库）的性能要逊于专用向量数据库（如：Faiss、Milvus 和 Pinecone）。

那么问题来了：通用向量数据库的性能为什么逊于专用向量数据库？究竟是什么原因导致了通用向量数据库性能较差？是实现上的问题？还是说关系型数据库在支持向量 ANNS 时存在根本性的缺陷与限制？

该论文就是为了回答这一问题。具体地，该论文选取了基于 PostgreSQL 的通用向量数据库 PASE 与专用向量数据库 Faiss 作为两类数据库的典型代表，对二者进行相关实验，比较性能差距和导致性能问题的原因。

确定了实验选取的数据库后，还有个因素需要确定，就是：选取哪种 ANNS 索引作为加速向量近似最近邻查询的索引结构？

考虑到哪些索引最常用、性能较好、在 PASE 和 Faiss 中都得到了实现等因素，该论文最终选取了以下三种索引作为实验研究的索引结构：

IVF_FLAT：基于聚类与码本思想的 ANNS 索引，首先使用 K-means 算法计算出若干个聚类中心，然后将每个向量划分到距离其最近的中心，构成一个聚类，每个聚类称为一个 bucket。搜索时，选取距离聚类中心最近的若干个 bucket，在这些 bucket 内进行穷尽搜索并返回最终结果。
IVF_PQ：与 IVF_FLAT 类似，首先将向量分解为子向量，在同一组中的子向量上进行聚类，相比 IVF_FLAT 可以降低索引大小。更多信息可参考本人博客：DB 论文阅读：Product Quantization for Nearest Neighbor Search - arcsin2 的个人博客。
HNSW：基于图的、性能最好的、最常用的 ANNS 索引之一，其核心思想是贪心+概率。更多信息可参考本人博客：DB 论文阅读：Approximate nearest neighbor algorithm based on navigable small world graphs - arcsin2 的个人博客。

至此，我们确定了选取哪些 ANNS 索引、哪两个典型向量数据库进行实验对比。下面，我们来看实验具体是如何开展的。

2. 实验设置

实验关注点：

首先，我们要搞清楚该论文的实验关注什么场景，不讨论什么场景：

该只考虑单节点场景，不考虑分布式场景；
只考虑在 CPU 上进行执行，不考虑 GPU 加速的场景；
只考虑索引大小不超过内存大小，不考虑面向磁盘存储的索引（PASE 虽然是基于面向磁盘的关系型数据库 PostgreSQL 的，但是论文实验中索引大小不超过内存，且使用内存文件系统 tmpfs 实验结果并无明显变化）。
如果不单独说明，实验设置都是单线程，不考虑线程间并发加速情况。

数据集与超参数：

实验选取的数据集是 SIFT1M、GIST1M、Deep1M 等 ANNS 领域常用数据集；不同的 ANNS 索引会有超参数的设置问题，在进行实验时都保持 PASE 与 Faiss 超参数设置相同。

评价指标：

该论文关注的问题是：通用向量数据库为什么比专用向量数据库慢，因此更多关注索引构建耗时、查询耗时、索引大小等因素，而不关心 ANNS 领域关注的召回率指标。

3. 实验结果

介绍完实验背景与设置后，我们正式来看实验结果，以及通用向量数据库为什么慢？

3.1 索引构建耗时

3.1.1 IVF_FLAT

实验结果如下图所示：

PASE 在构建 IVF_FLAT 索引时比 Faiss 慢 35 ~ 84.8 倍。

经过 Perf 等工具分析，发现 PASE 时间大部分花费在欧氏距离计算上，也就是 fvec_L2sqr_ref 函数。经过查看源码，发现 Faiss 使用了 BLAS 库中的 SGEMM (Single Precision General Matrix Multiplication) 函数。构建 IVF_FLAT 索引的 adding 阶段是指：在计算出若干个聚类中心后，需要计算每个向量与所有聚类中心的聚类，并将向量分配给距离最近的聚类中心。PASE 使用了朴素的算法实现，而 Faiss 将这一问题转换为矩阵乘法，并使用 SGEMM 算法加速这一过程。这里其实就是一点简单的线性代数知识，但是懒得打公式了，感兴趣的读者请参阅原论文第 5 页最后一段。SGEMM 算法这里暂不讨论，可参考：CUDA SGEMM矩阵乘法优化笔记——从入门到cublas - 知乎 (zhihu.com)。总而言之，Faiss 通过数学上的技巧消除了冗余运算，且使用了 SGEMM 算法加速矩阵乘法，从而得到了比 PASE 快几十倍的性能。

在手动 disable Faiss 的 SGEMM 算法后，得到新的实验结果：

可以看出，此时 PASE 与 Faiss 性能差异基本消除。

IVF_PQ 索引的构建时间 PASE 同样慢于 Faiss，且由相同的原因导致，这里不再详细介绍。

3.1.2 HNSW

索引构建时间如下：

注意图片的纵坐标为指数，因此 PASE 的索引构建速度在不同数据集上仍慢于 Faiss 1.6 ~ 8.7 倍不等。

使用 Perf 分析性能瓶颈，得到以下表格：

可以看到，SearchNbToAdd 函数耗时比例最大。该函数为新插入的向量搜索邻居来构造 HNSW。该函数的耗时可进一步分解为下图：

可以看到，PASE 花费了大量时间来访问元组。这是因为 PASE 基于 PostgreSQL，需要提供 page id 和 tuple id 通过 buffer pool 访问元组；而在 Faiss 中仅需要通过内存指针来定位并访问元组。这一原因可总结为 PASE 中继承自 PostgreSQL 的内存管理导致了较大的开销。

3.1.3 并行性的影响

本小节研究多线程对索引构建速度的影响。由于 PASE 不支持多线程索引构建，且 HNSW 是基于图结构的索引，不易进行多线程加速，Faiss 也并不支持，因此仅考虑 Faiss 多线程构建 IVF_FLAT 和 IVF_PQ 索引。

下图展示了是否开启 SGEMM，IVF_FLAT 和 IVF_PQ 索引在不同线程下的构建时间区别：

从图中可以看出，除了使用 SGEMM 的 IVF_FLAT (图 9a)，其他情况索引构建性能都可以很好地随线程数缩放。这一结果说明了对并行性的支持，也是 PASE 慢于 Faiss 的重要原因之一。

3.2 索引大小

3.2.1 IVF_FLAT 与 IVF_PQ

这两个索引，PASE 与 Faiss 索引大小基本相同。相关图片这里不再展示。

3.2.2 HNSW

实验结果如下图所示：

可以看出，PASE 的 HNSW 索引大小要比 Faiss 大 2.9 ~ 13.3 倍。这实际上是因为 PostgreSQL 的页面式存储结构：PASE 中存储 HNSW 的邻接表时，每个邻接表占据一个新的页面。而一个顶点的邻接表往往很小，这导致了 page 内部大量的空间浪费（类似于内存管理中的内部碎片）。PostgreSQL 页面默认大小为 8 KB，在将这一参数调整为 4 KB 后，HNSW 索引大小变化如下表所示：

这一结果证明了上面的结论。

3.3 查询耗时

3.3.1 IVF_FLAT

PASE 与 Faiss 的 IVF_FLAT 索引在不同数据集上查询耗时如下图所示：

PASE 比 Faiss 慢 2 ~ 3.4 倍不等。

PASE 在 IVF_FLAT 上的性能问题由以下原因导致：

PASE 与 Faiss 的 K-means 算法实现不同，导致后续搜索时耗时的区别。
进行 Top-k ANNS 时，PASE 在维护 Top-k 结果时使用的优先队列大小为 bucket 内元素数量，而不是通常较小的 k，导致了 PASE 查询慢于 Faiss。（个人认为这实际上可以看作 bug 了）

3.3.2 IVF_PQ

实验结果如下图所示：

PASE 比 Faiss 慢 3.9 ~ 11.2 倍不等。这是因为 PASE IVF_PQ 使用直接的实现来计算预计算表，而 Faiss 使用优化的解决方案，将任务分为计算 L2 范数和内积（预计算表是 IVF_PQ 中用于存储分块后的子向量与质心点之间的距离的表，以消除重复计算）。

3.3.3 HNSW

PASE 的 HNSW 搜索速度同样慢于 Faiss，原因同样是元组访问。这里不再赘述。

3.3.4 并行性的影响

本小节关注查询内并行性，即：使用多个线程来回答一个查询。由于 PASE 与 Faiss 均不支持 HNSW 索引的查询内并行，因此仅关注它们在 IVF_FLAT 和 IVF_PQ 索引上的查询内并行性。实验结果如下图所示：

由图片可知，Faiss IVF_FLAT 和 IVF_PQ 可以很好地随着线程的数量扩展，而 PASE IVF_FLAT 和 IVF_PQ 则不能，尽管它们使用相同的思想：分配多个线程来搜索不同的桶。这是因为：Faiss 在不同线程内使用局部变量维护 Top-k 结果，最后进行 merge 过程；而 PASE 线程间共享变量，锁争用导致了 PASE 慢于 Faiss。

4. 总结

经过上文的实验与分析，我们可以得出结论：关系型数据库在 ANNS 上不存在根本性的缺陷和限制。尽管 PASE 明显慢于 Faiss，但都是因为实现上的问题。只要付出工程上的努力，通用向量数据库的性能是可以与专用向量数据库相当的。原论文总结了关系型数据库在 ANNS 任务上慢的原因，这些原因都在前文中用加粗字体显示了，这里就简单罗列下，不再详细介绍：