本文对清华大学李国良教授团队论文《Survey of Vector Database Management Systems》进行解读，全文共7074字，预计阅读需要20至30分钟
随着大语言模型（LLMs）和电子商务等领域的发展，向量数据库管理系统（VDBMSs）应运而生，旨在处理大规模非结构化数据的存储和检索需求。这篇论文对向量数据库管理系统进行了全面的综述，探讨了其发展背景、面临的挑战以及相应的解决方案。
向量数据库架构图
向量数据库管理系统在处理向量数据时面临着诸多挑战，这些挑战主要体现在以下五个方面：
1.语义相似性模糊
在向量数据管理中，结构化查询能够借助精确的布尔谓词进行数据检索，然而向量查询所依赖的语义相似性概念却较为模糊。这种模糊性使得准确捕捉和衡量向量之间的相似性变得困难重重。在实际应用中，由于缺乏明确的界定和标准，对于什么样的向量才算是语义相似难以给出精准的判断，进而影响了查询结果的准确性和可靠性。
2.相似性比较成本高
属性谓词在评估时大多可以在常数时间O(1)内完成，这使得结构化查询在处理属性相关的操作时效率较高。然而，向量之间的相似性比较通常需要与向量的维度D成正比的时间O(D)。随着向量维度的不断增加，相似性比较所需的时间也会急剧增长。这意味着在处理大规模向量数据时，相似性比较操作将消耗大量的计算资源，严重影响系统的性能。
3.向量尺寸大
结构化查询通常仅涉及少量属性的访问，因此可以设计出高效的存储结构，如列存储，以提高数据的读取效率。但向量搜索则需要完整的特征向量参与运算。这些向量有时可能会跨越多个数据页，这不仅增加了磁盘检索的成本，因为需要频繁地在磁盘上读取数据，还会给内存带来较大的压力，因为需要将大量的向量数据加载到内存中进行处理。在处理大型图像或视频数据的向量表示时，向量尺寸大的问题尤为突出。
4.缺乏结构
结构化属性往往具有可排序或有序的特性，这使得可以通过数值范围或类别进行分区，从而设计出有效的搜索索引。然而，向量本身并没有明显的排序顺序，也不具备自然的序数属性。这就使得设计既准确又高效的索引变得极为困难。没有合适的索引结构，向量数据的搜索效率将大打折扣，无法快速定位到与查询相关的向量数据。
5.与属性不兼容
在结构化查询中，针对多个属性索引的操作可以使用简单的集操作（如并集或交集）来收集中间结果，最终形成完整的结果集。但向量索引在执行过程中，通常在找到k个最相似的向量后就停止搜索。当需要将向量索引的结果与属性索引扫描的结果相结合时，可能会出现结果数量少于预期的情况。另外，若修改索引扫描操作以考虑属性谓词，又可能会降低索引的性能。
查询处理是向量数据库管理系统的核心环节，该章节主要涵盖相似性分数、查询与操作符、查询接口等方面，详细内容如下：
1.相似性分数
基本分数：常见的相似性分数包括汉明距离、内积、余弦相似度、闵可夫斯基距离和马氏距离等。这些分数各有特点，适用于不同场景，但如何为特定应用选择合适的分数缺乏明确指导。
聚合分数：在多向量搜索场景中，如面部识别中一个实体由多个向量表示时，需要聚合分数来综合评估多个向量与查询向量的相似度。常见的聚合方法有均值聚合和加权求和等。
学习分数：一些研究尝试通过寻找变换矩阵M来改进基于马氏距离的相似性搜索质量，这属于度量学习的范畴，但目前相关技术尚未广泛应用于商业系统。
2.查询和操作符
数据操纵查询：提供插入、更新和删除向量的机制，分为直接和间接操纵。直接操纵允许用户自由修改向量值，但需自行维护模型；间接操纵则对用户隐藏向量，将向量集合视为实体集合，由系统负责模型维护，用户可通过多种方式进行操作。
(c,k)-搜索查询：多数VDBMSs支持 “最近邻” 查询，可分为精确和近似查询，通过c（近似度）和k（邻居数量）参数化。近似k-最近邻（ANN）查询返回在一定半径内的k个向量，常见的有近似最近邻搜索（ANNS）和k-最近邻（k-NN）查询等。
范围查询：由半径参数化，返回距离查询向量小于等于的所有向量。
谓词搜索查询：也称为 “混合” 查询，要求结果集中的每个向量都满足特定的属性值布尔谓词。
批量查询：多个查询同时提交给系统，系统可按任意顺序处理，适用于硬件加速查询处理。
多向量查询：通过聚合分数支持，包括多查询单特征（MQSF）、多查询多特征（MQMF）和单查询多特征（SQMF）三种子类型，但目前仅部分子类型得到支持。
基本操作符：投影是基本操作符，但对于大规模向量数据效率较低，多数VDBMSs依赖基于索引的操作符来提高查询效率。
3.查询接口
原生和NoSQL VDBMSs 倾向于使用小型API，如Chroma提供了包含添加、更新、删除和查询等九个命令的Python API。扩展VDBMSs则利用SQL扩展来实现查询接口，如在pgvector中，k-NN或ANN查询可通过特定的SQL语法表达。
存储和索引是向量数据库管理系统的关键部分，该章节主要探讨了向量索引的结构、相关技术以及不同索引的特点和适用场景，具体内容如下：
1.表结构
局部敏感哈希（LSH）：提供可调性能和错误保证，但可能需要高冗余，从而增加查询和存储成本。
学习哈希（L2H）：直接学习合适的映射，如SPANN中向量通过k-means哈希到最近质心，但这类技术训练时间长且对分布外更新敏感，应用相对受限。
量化：利用k-means质心作为哈希键来压缩向量，减少存储成本，如PQ、IVFSQ和IVFADC等索引基于此技术。产品量化（PQ）通过将向量分割为子空间来降低k-means的计算复杂度。
2.树结构
非随机树：如树及其衍生树，通过特定规则构建，但在高维数据中受维度诅咒影响。
随机树：为克服维度诅咒，采用随机化或结合主成分分析（PCA）的策略，如FLANN和ANNOY。随机树的构造复杂度一般为O(DNlogN)，多数可通过回溯或采用失败主义搜索返回近似结果，但维护成本较高，插入操作平均复杂度为O(DlogN)，最坏情况为O(DN)，且节点分裂策略固定，难以在分布外插入后重新平衡。
3.图结构
k-最近邻图（KNNG）：每个节点连接到其k个最近邻居，可用于精确或近似搜索。精确构建复杂度高，近似构建可通过迭代优化方法（如NN - Descent 和EFANNA）实现，EFANNA使用随机k-d树森林构建初始KNNG，收敛速度更快。
单调搜索网络（MSN）：通过添加特定边缘保证搜索路径单调，可提高搜索效率，但精确构造复杂度高，实际多采用近似方法，如通过搜索试验不断优化图结构，FANNG在固定次数试验后终止构造，NSG和Vamana分别基于近似KNNG和随机图进行构造。
小世界图（SW）：具有对数级的特征路径长度，如NSW通过节点顺序插入构建，HNSW使用随机化分层结构进一步优化，在保持对数搜索复杂度的同时降低了存储成本，支持快速查询和更新，因此被许多商业VDBMSs采用。
查询优化和执行章节主要探讨了如何在向量数据库管理系统中选择最优的查询计划以及高效执行查询，具体内容如下：
1.混合操作符
(1)块优先扫描（Block - First Scan）
在线阻塞：在查询时，使用位掩码等技术高效执行阻塞操作，减少对查询延迟的影响，如AnalyticDBV和Milvus中的实现。
离线阻塞：对于基于图的索引，通过策略性添加边缘防止图因阻塞而断开，如Filtered - DiskANN、Qdrant和Milvus中的方法。在Milvus中，还可预先根据属性对向量集合进行分区，以加速查询执行。
(2)访问优先扫描（Visit - First Scan）
对于低选择性谓词，该方法可能比在线阻塞更快，但对于高选择性谓词，可能因频繁回溯而影响性能。为避免回溯，可将属性信息融入扫描操作，如通过修改最佳优先搜索操作符，通过增强距离函数来实现。
2.计划枚举
（1）预定义计划
单计划：对于特定系统或查询类型，可预先定义单个高效计划，去除计划选择和枚举的开销，但可能不适用于所有工作负载。例如，EuclidesDB为每个数据库实例配置单一搜索索引，Weaviate对所有谓词搜索查询采用预过滤执行。
多计划：非谓词查询可根据不同索引生成多个计划，谓词查询则因过滤方式和索引类型的组合而产生更多可能计划，如AnalyticDB - V 支持多种索引和查询执行方式，允许用户选择不同计划。
（2）自动枚举
部分基于关系系统的VDBMSs利用底层关系优化器进行计划枚举和选择，通过扩展关系语言支持距离函数和向量索引扫描，如pgvector和PASE利用PostgreSQL的扩展功能。
3.计划选择
（1）基于规则
根据谓词选择性等因素制定规则选择计划，如Qdrant和Yahoo Vespa 根据集合大小和谓词选择性选择不同执行方式，Qdrant根据阈值选择暴力扫描、属性索引预过滤或HNSW预过滤，Vespa还可根据选择性估计选择HNSW后过滤或其他方式。
（2）基于成本
使用成本模型选择估计成本最低的计划，如AnalyticDB - V 和Milvus采用线性成本模型，综合考虑操作符成本、谓词选择性和查询准确性等因素。但成本估计面临挑战，如预过滤的扫描成本因阻塞不确定性难以估计，访问优先扫描成本受谓词失败率影响，后过滤可能导致结果集小于k个元素，难以确定最优的α值。
4.查询执行
（1）硬件加速
CPU缓存：利用处理器缓存减少数据读取延迟，如Milvus通过将查询分区为适合缓存的块，按块处理查询，减少缓存缺失，提高查询效率。
单指令多数据（SIMD）：利用SIMD指令并行化计算，如在ADC算法中通过巧妙利用SIMD shuffle 指令并行化表查找操作，减少查询延迟，Faiss实现了相关算法。
图形处理单元（GPU）：GPU的大规模并行计算能力可加速向量搜索，如利用GPU的warp shuffle 操作在寄存器内执行表查找，避免内存检索，但受寄存器大小限制，k值不能过大，Milvus通过多轮k-NN搜索解决此问题。
（2）分布式搜索
许多VDBMSs利用分布式集群扩展到大规模数据集或高工作负载，通过将向量集合分区为分片，在每个分片上构建本地索引，查询时采用分散-聚集模式，将查询分散到各个分片，然后合并结果。这种方式可提高扩展性和吞吐量，部分系统还通过复制分片提供容错能力。
（3）异地更新
副本：通过分区和复制向量集合，在副本上构建索引，当一个副本更新或重建索引时，查询可由其他副本处理，如一些VDBMSs采用此方法，但存储需求会增加，且查询可能因分散-聚集操作产生额外开销。
日志结构合并（LSM）树：将更新流式传输到单独结构，在合适时间与索引合并，如Milvus和Manu在LSM树的每个段上构建向量搜索索引，段满或合并时创建新索引，平衡读写性能。其他系统如Vald和AnalyticDB - V 也采用类似的更新策略，将更新先存储在内存或队列中，再批量应用到索引。
当前系统分类章节对现有的向量数据库管理系统（VDBMSs）进行了全面分类，主要包括原生系统、扩展系统以及其他相关系统，各类系统具有不同特点和适用场景，具体内容如下：
1.原生系统
（1）主要处理向量工作负载
特点：专为向量数据管理设计，具有小型查询API、简单处理流程和基本存储模型，高度专注于向量数据管理，适用于特定向量查询场景。
EuclidesDB：用于管理嵌入模型，允许用户尝试不同模型和相似性分数，通过查询和操纵非向量实体与系统交互，支持多向量空间以提高查询语义准确性。
Vald：是无服务器VDBMS，提供可扩展的非谓词向量搜索，采用分布式架构，跨多个 “代理” 节点存储向量集合，通过代理间的分散 -聚集操作提高吞吐量和降低延迟，每个代理使用NGT图索引进行本地搜索，并支持异地更新。
Vearch：针对电子商务中的图像搜索进行优化，支持谓词查询（通过后过滤执行），采用解耦架构，具有独立的搜索节点，可分别扩展读写能力，无需支持精确查询。
Pinecone：提供类似Vald的可扩展分布式系统，作为托管云服务，更具用户友好性。
Chroma：类似于EuclidesDB的集中式系统，适用于单机环境。
（2）主要处理混合工作负载
特点：支持更复杂多样的查询，包括精确和范围查询，部分系统进行查询优化，具有更复杂的数据和存储模型，以应对多种类型查询需求，如谓词查询和属性-向量混合查询。
Milvus和Manu：Milvus旨在全面支持向量搜索查询，Manu在其基础上增加额外功能。两者支持多种基本查询类型和变体，支持多个搜索索引，并通过成本-基于优化器处理谓词查询。
Qdrant：支持多种搜索查询，对于谓词查询，采用基于规则的优化器和定制的HNSW索引进行块优先扫描。
NucliaDB和Marqo：专注于文档搜索和检索，通过多向量搜索将关键词与向量结合，利用文本特定技术处理非向量关键词查询，生成稀疏词频向量，再与密集特征向量结合进行多向量搜索。
Weaviate：基于图模型进行文档搜索和检索，除支持向量搜索的相似性查询外，还能处理非向量查询，如按作者检索书籍，用户通过GraphQL查询与系统交互。
2.扩展系统
（1）基于NoSQL
特点：继承了NoSQL系统的特性，如无模式存储、分布式架构和最终一致性，与原生系统有一定相似性，但功能更丰富，适用于大规模数据处理和灵活查询需求场景。
Vespa：是可扩展的分布式NoSQL系统，用于大规模数据处理，具有灵活的SQL - 类似查询语言，存储模型简单，由内部文档存储提供支持，采用基于规则的查询优化器。
Cassandra：即将在5.0版本中通过集成HNSW到存储层、实现跨副本的分散-聚集操作和扩展查询语言来支持向量搜索。
其他系统：如基于Spark的Databricks平台预期在未来版本支持向量搜索，包括谓词查询；MongoDB、Cosmos DB 和Redis（结合Redis Stack 搜索扩展）等文档型NoSQL数据库，以及Neo4j（属性图数据库）也在扩展向量搜索能力。
（2）基于关系型
特点：利用关系型系统固有功能，如SQL表达能力，在现有组件基础上紧密集成向量搜索能力，提供丰富功能，但性能可能相对较低，适用于已使用关系型数据库且需要集成向量搜索的场景。
SingleStore：是云原生混合事务和分析（HTAP）数据库，通过原生关系引擎处理向量搜索，扩展了计算点积和欧几里得距离的函数，可直接进行精确k-NN和范围搜索。
PASE：扩展PostgreSQL，引入平面量化索引和HNSW索引支持向量搜索。
pgvector：为PostgreSQL带来向量数据类型和相关函数，支持通过SQL进行向量查询，可利用索引加速查询，查询优化由PostgreSQL的查询优化器完成，支持复制、容错等PostgreSQL的原生功能。
AnalyticDB - V：在AnalyticDB基础上添加向量搜索能力，主要通过引入向量索引（VGPQ和HNSW）和增强成本-基于优化器实现。
ClickHouse和MyScale：ClickHouse是面向快速分析的列式数据库，支持向量查询（使用ANNOY和HNSW）；MyScale是基于ClickHouse的云服务，添加了更多表-基于搜索索引（如flat indexes 和IVFADC），并具有性能更优的专有搜索索引 “多尺度树图”（MSTG）。
3.其他系统
（1）向量搜索引擎和库
通常嵌入到需要向量搜索的应用中，但功能不如完整的VDBMSs。例如，Apache Lucene 是可插拔搜索引擎，通过HNSW支持向量搜索，虽缺乏高级功能，但可与现有基础设施集成，基于Lucene的平台如Elasticsearch、OpenSearch和Solr提供了更多功能。此外，还有直接实现特定索引的库，如KGraph（NN - Descent KNNG 的实现）、Microsoft SPTAG（结合多种技术的可配置索引），以及用于LSH的E2LSH和FALCONN等库，Meta Faiss 提供了多种索引选择。
（2）其他相关系统
Featureform是中间件，用于数据集管理，通过API提供向量搜索端点，可在配置的提供商（如Pinecone）上执行k-NN查询；Activeloop Deep Lake 可直接在张量仓库内执行向量搜索；Nomic Atlas 提供向量空间可视化平台，通过专有降维技术将高维向量投影到二维图上，辅助数据分析。
向量数据库分类
基准测试与挑战章节主要讨论了向量数据库管理系统在评估和发展过程中面临的相关问题，具体内容如下：
（1）基准测试
现有研究概述：目前全面的跨学科向量搜索算法和系统比较相对匮乏。不过，已有一些值得关注的基准测试研究。
（2）具体测试内容
对大量近似最近邻（ANN）算法进行了统一实现和评估，实验涵盖18个数据集，数据规模从几千到1000万向量不等，维度范围为100到4096，数据来源包括图像、文本、视频、音频集合及合成数据。算法评估指标包括查询延迟、结果集质量（基于精度、召回率及其他衍生指标）。后将评估范围扩展到完整的VDBMSs，缩小了数据集的维度和规模，保留了不同系统实现的差异以更贴近实际情况，提供了标准化评估平台和最新基准测试结果。
（3）挑战与开放问题
相似性分数选择：不同相似性分数的语义质量仍难以准确理解，缺乏针对不同场景选择合适分数的严格指导。尽管EuclidesDB等系统可用于实验确定最佳分数和嵌入模型，但该问题整体仍未得到充分探索。
操作符设计：设计高效且有效的混合操作符面临诸多挑战。对于图索引，块优先扫描可能导致图结构断开，需要修复或新的搜索算法应对，但现有离线阻塞技术仅适用于少量属性类别。访问优先扫描中，由于回溯难以预测，导致扫描成本估计困难，进而使计划选择变得复杂。
增量搜索：在电子商务和推荐平台等应用中，增量k-NN搜索需求日益增长，即值很大但以小增量检索结果。然而，如何在向量索引中有效支持这种搜索方式仍不明确。
多向量搜索：多向量搜索在面部识别等应用中非常重要，但现有技术依赖聚合分数，计算效率较低，因为会增加距离计算量。通用的多属性top - k技术难以适配向量索引，且目前尚无关于多查询多特征（MQMF）查询的研究成果。
安全与隐私：随着向量搜索在关键任务中的应用越来越多，数据安全和用户隐私保护变得愈发重要，尤其对于提供托管云服务的VDBMSs。因此，需要新的技术来支持高维向量的私有和安全搜索。
未来的向量数据库管理系统应朝着提供高性能和统一数据管理能力的方向发展，以满足日益增长的应用需求。同时，需要进一步研究解决当前面临的挑战，如相似性分数选择、操作符设计、增量搜索、多向量搜索以及安全与隐私等问题。
作者：
刘思源
13691032906（微信同号）
liusiyuan@caict.ac.cn
刘蔚
13661023626（微信同号）
liuwei11@caict.ac.cn
