向量数据库—过滤搜索索引概述

---

概况介绍向量数据库、过滤搜索以及相关索引技术。

---

由于近期的研究都聚焦于向量数据库的过滤搜索（混合搜索），因此较为全面地调查和整理了相关的技术点，以此为契机和大家分享。

向量数据库（Vector Database）作为如今AI时代数据库领域一个较为热门的方向，由于其所管理的向量数据的诸多特点，在系统实现与数据管理方法上相较传统数据库都有很较大的不同，例如针对索引技术，向量数据库的核心问题是近似最近邻搜索（ANNS）以及扩展了标量属性的过滤搜索（Filter Search），围绕此产生了不同与传统数据库的索引技术和搜索策略。

本篇博客首先将介绍向量数据库和近似最近邻搜索这两个概念，之后重点分享混合索引与搜索策略相关技术思考及对目前前沿的混合搜索索引技术的调查。

---

向量数据库

向量数据库是一种专门用于存储、索引和查询向量数据的数据库系统。通俗来讲，就是以向量类型数据作为一等公民进行管理的数据库系统。

图：不同类型向量数据库

我们可以根据其系统设计将其分为基于关系数据库的扩展型向量数据库与原生向量数据库，前者如：Postgre + pgvector、PASE 等，尝试在传统关系数据库架构上整合向量数据管理功能，通过扩展 SQL 语法来实现向量相似性搜索与结构化数据查询的结合；而后者如：Milvus、Qdrant 等，则从底层设计出发，针对向量数据的特点进行优化，在处理混合搜索时采用特定的数据结构和算法来平衡混合搜索的查询效率。这种底层差异也造成了不同系统在不同功能实现上的区别，简单说扩展型向量数据库能够保留和发挥原有关系数据库的优势，而原生向量数据库则完全围绕在向量进行设计和优化，一般来说效率更优。

扩展资料：Pan J J, Wang J, Li G. Survey of vector database management systems[J]. The VLDB Journal, 2024, 33(5): 1591-1615.

---

近似最近邻搜索

近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）是一种用于高维数据检索的技术，目标是在给定查询的情况下，快速找到距离查询点最近的数据点，尽管结果可能并不完全精确。

向量数据具有三个性质：高维、非结构化和含有语义信息，向量之间的距离可以反映语义关系。例如：RAG通过检索内容相似的段落来为LLMs提供额外的信息，推荐系统通过分析用户常浏览的内容，推荐相似产品为用户提供个性化推荐。这个检索相似内容的过程，就是近似最近邻搜索，其是针对精确最近邻算法（KNN）的修改，由于精确计算下开销过大，我们选择放宽约束，通过允许一定程度下牺牲搜索精度来换取搜索效率的提高和搜索成本的下降。

近似最近邻搜索中要使用的向量索引就是指通过某种数学量化模型，对向量构建一种时间和空间都比较高效的数据索引结构，使得我们能够实时地获取跟查询向量尽可能最相近的K个向量。从定义可以看到，要设计一种高效的向量索引模型，应该满足3个基本条件，即：

• 实时查询，支持海量（百亿、千亿级别）规模库量级的实时查询；
• 存储高效，要求构建的向量索引模型数据压缩比高，达到大幅缩减内存使占用的目的；
• 召回精度好，top@K有比较好的召回率，跟暴力搜索（brute-force search）的结果相比；

几乎所有的ANNS方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。可以看到，正是因为缩减了遍历的空间大小范围，从而使得ANNS能够处理大规模数据的索引。根据实现方法的不同，可以将向量索引方法分为四大类：基于树的方法、哈希方法、矢量量化方法、图索引量化方法。其中哈希方法以LSH、矢量量化方法以PQ/OPQ/IVFOPQ、图索引量化方法以HNSW为典型代表。（详细算法原理可参考下面网站链接）

向量索引: link

---

过滤搜索

我们考虑一种场景，电商领域中，用户在搜索商品时，不仅希望通过商品图像或描述的非结构化向量数据找到外观或功能相似的产品，还期望依据价格、品牌等结构化标量数据进行筛选，这就要求搜索既要满足非结构化数据（向量）的最近邻关系，同时还要满足结构化属性的过滤要求，这类搜索就是过滤搜索（Filter Search）/混合搜索（Hybrid Search）。
这实际上是将属性过滤和向量近似查找两个动作的结果进行整合，我们可以很容易想到串行思路，即以此顺序完成两个动作，这就是过滤搜索中的预过滤（Pre-filtering）和后过滤（Post-filtering）：

图：不同搜索策略（图自：CAPS: A Practical Partition Index for Filtered Similarity Search）

预过滤：就是指首先找出所有满足属性过滤条件的数据，然后在结果集合上执行暴力最近邻搜索以获得结果（或在结果集上构建索引进行搜索）。这种方法的一个问题是无法使用全局数据上构建的索引，因为预过滤后的的结果集只是全局数据的子集，而在中间结果集上构建索引再进行搜索尽管一定程度上能够发挥索引的优势，但每次搜索中构建索引开销过大，需要频繁的删除和构建，一般采用的暴力搜索则是无奈之举。特别是在大型数据集下的高选择性谓词这种情况下，该策略效率低下。

后过滤：就是指首先通过近似最近邻搜索获得近邻数据，再在结果集合上拿到满足属性过滤条件最为最终结果。这种方法的一个问题是由于第一步近邻搜索过程中没有考虑谓词条件，得到的中间结果中满足过滤条件的数量可能不足，导致最后得到的结果无法到达要求的Top K，召回率较低。通常会采用在第一步扩大搜索范围的方式来尽可能获得足够的数据，但该方法开销较大，难以确定合适的扩大比例。特别是对于选择性低或与查询向量相关性低的谓词情况下，该策略效率低下。

因此最近几年出现了许多针对过滤搜索场景的索引研究，其中大部分工作基于图索引量化方法进行改进，比较常见的思路是在图构建过程中添加额外的边来处理标量信息，用空间来换时间，力求在搜索过程中能够基于过滤后的数据继续使用索引实现最近邻搜索（思路上比较接近预过滤，但索引可复用）。与此同时还有不少工作通过设计新的数据结构同时处理标量信息与最近邻关系，在搜索过程中并行完成两个动作（思路上也与预过滤较为接近）。而从数据库系统角度出发，可以通过基于数据信息情况在不改变索引结构的情况下提供策略选择方式（基于cost model或启发式），在不同情况下选择预过滤或后过滤，也能获得不错的效果。

在这里和大家分享针对目前前沿研究的汇总和分类。

算法类型区分
图（主流）：NHQ[1]、HQANN[2]、UNG[3]、FilteredVamana[4]、StitchedVamana[4]、ACORN[5]
量化：CAPS[6]、FAISS-IVF[7]
哈希：LSH、PQ

过滤策略区分
pre：UNG
post：NGT[8]
during：FilteredVamana、StitchedVamana、ACORN、NHQ、HQANN、FAISS-IVF、CAPS

向量数据库系统（cost-based or heuristic）
AnalyticDB-V[9]、Milvus[10]、Weaviate[11]、Vearch[12]、Pinecone[13]

查询标签集合区分
|f|=|fq|：NHQ
|f|≠|fq|：FilteredVamana、StitchedVamana（主要关注|fq|=1，更大时表现不好）、ACORN、UNG、CAPS

各方法对比

work	type	base-algorithm	predicate condition	add	search strategy	update
UNG	framework	graph	|f|≠|fq|	支持复杂谓词条件	pre	√
NHQ	framework	graph	|f|=|fq|	仅支持等式，不支持合取	during	×
FilteredVamana、StitchedVamana	algorithm	graph	|f|≠|fq| and |fq|=1	仅支持等式，不支持合取	during	√
ACORN	algorithm	graph	|f|≠|fq|	支持复杂谓词条件	during	√
CAPS	algorithm	Quantization	|f|≠|fq|	支持复杂谓词条件	during	√

后续会针对部分工作分享学习记录。（挖个坑先！）

reference:
[1] Wang M, Lv L, Xu X, et al. An efficient and robust framework for approximate nearest neighbor search with attribute constraint[J]. Advances in Neural Information Processing Systems, 2023, 36: 15738-15751.
[2] Wu W, He J, Qiao Y, et al. HQANN: Efficient and robust similarity search for hybrid queries with structured and unstructured constraints[C]//Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 2022: 4580-4584.
[3] Cai Y, Shi J, Chen Y, et al. Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search[J]. Proceedings of the ACM on Management of Data, 2024, 2(6): 1-27.
[4] Gollapudi S, Karia N, Sivashankar V, et al. Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters[C]//Proceedings of the ACM Web Conference 2023. 2023: 3406-3416.
[5] Patel L, Kraft P, Guestrin C, et al. Acorn: Performant and predicate-agnostic search over vector embeddings and structured data[J]. Proceedings of the ACM on Management of Data, 2024, 2(3): 1-27.
[6] Gupta G, Yi J, Coleman B, et al. Caps: A practical partition index for filtered similarity search[J]. arXiv preprint arXiv:2308.15014, 2023.
[7] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, MariaLomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. (2024). arXiv:2401.08281 [cs.LG]
[8] Yahoo. Nearest neighbor search with neighborhood graph and tree for high-dimensional data.
https://github.com/yahoojapan/NGT, 2016.
[9] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V.Proceedings of the VLDB Endowment (Aug 2020), 3152–3165.https://doi.org/10.14778/3415478.3415541
[10] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD ’21). Association for Computing Machinery, 2614–2627.
[11] Weaviate. 2022. Weaviate – Vector Database. https://weaviate.io/
[12] Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. 2018. The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform. In Proceedings of the 19th International Middleware Conference Industry.https://doi.org/10.1145/3284028.3284030
[13] Pinecone. 2019. The vector database to build knowledgeable AI. https://www.pinecone.io/.