PaperlayerView exact revision on arXiv

Source-linked AI summary

Survey of Vector Database Management Systems

James Jie Pan, Jianguo Wang, Guoliang Li

arXiv:2310.14021v1cs.DB

TL;DR

Vector database management systems must support reliable, scalable search over large unstructured datasets while handling semantic ambiguity, expensive comparisons, weak partitioning, and hybrid queries. This survey organizes the relevant query, storage, indexing, optimization, and execution techniques, then characterizes systems, benchmarks, and open challenges. It finds a spectrum from high-performance specialized systems to more capable extended systems, while identifying persistent challenges in tree maintenance and hybrid-operator design.

  • Problem

    VDBMSs lack a comprehensive survey of techniques for reliable, secure, fast, and scalable management of large unstructured datasets and vector queries.

  • Method

    The paper surveys vector query processing, storage and indexing, optimization and execution, commercial systems, and benchmarks from a generic VDBMS perspective.

  • Results

    The survey characterizes VDBMSs across design and runtime spectra, from specialized high-performance systems to extended systems offering broader capabilities.

  • Takeaways & Limitations

    Vector data management requires choosing techniques and system designs according to workload needs such as throughput, latency, accuracy, and update intensity.

  • Takeaways & Limitations

    Tree indexes lack an obvious way to rebalance after out-of-distribution insertions, while hybrid operators remain difficult to design and cost-estimate.

Abstract

from arXiv · show

There are now over 20 commercial vector database management systems (VDBMSs), all produced within the past five years. But embedding-based retrieval has been studied for over ten years, and similarity search a staggering half century and more. Driving this shift from algorithms to systems are new data intensive applications, notably large language models, that demand vast stores of unstructured data coupled with reliable, secure, fast, and scalable query processing capability. A variety of new data management techniques now exist for addressing these needs, however there is no comprehensive survey to thoroughly review these techniques and systems. We start by identifying five main obstacles to vector data management, namely vagueness of semantic similarity, large size of vectors, high cost of similarity comparison, lack of natural partitioning that can be used for indexing, and difficulty of efficiently answering hybrid queries that require both attributes and vectors. Overcoming these obstacles has led to new approaches to query processing, storage and indexing, and query optimization and execution. For query processing, a variety of similarity scores and query types are now well understood; for storage and indexing, techniques include vector compression, namely quantization, and partitioning based on randomization, learning partitioning, and navigable partitioning; for query optimization and execution, we describe new operators for hybrid queries, as well as techniques for plan enumeration, plan selection, and hardware accelerated execution. These techniques lead to a variety of VDBMSs across a spectrum of design and runtime characteristics, including native systems specialized for vectors and extended systems that incorporate vector capabilities into existing systems. We then discuss benchmarks, and finally we outline research challenges and point the direction for future work.

1 Introduction

Vector database management systems address the demands of unstructured-data applications by combining similarity search with database capabilities. The survey organizes their obstacles, techniques, system designs, benchmarks, and open problems.

  • Large language models and unstructured-data applications motivate VDBMSs that provide optimization, transactions, scalability, fault tolerance, privacy, and security.
  • Vector management faces five obstacles: vague semantic similarity, O(D) comparisons, large vectors, absent natural ordering, and difficult attribute-vector integration.
  • The survey separates query processing, storage and indexing, and optimization and execution within a generic VDBMS perspective.
  • Storage and Indexing: Storage and indexing techniques include randomized, learned, and navigable partitioning, plus quantization and disk-resident indexes.
  • Optimization and Execution: Optimization and execution techniques address hybrid queries, plan enumeration and selection, hardware acceleration, distributed search, and high-throughput updates.
  • Current Systems: Existing systems span native vector-focused databases, extended data-management systems, and search engines or libraries with varying capabilities and performance.

2 Query Processing

Vector query processing specifies similarity criteria and executes operators over vector collections, supporting multiple scores, query types, and multi-vector searches. However, high-dimensional effects and the absence of principled score-selection methods remain important limitations.

  • Query specifications and execution: VDBMS query processing begins with a similarity score and query type, conveyed through an interface and executed as an operator chain.The basic operator is similarity projection, while index-supported operators address inefficiency.
  • Similarity scores: Similarity scores map vector pairs to scalar values, with larger values indicating greater similarity, while distance functions use smaller values for greater similarity.Supported scores include metric distances and inner-product-based measures.
  • Distance functions: Hamming distance counts differing dimensions, whereas Minkowski distances generalize Euclidean distance through the p-norm and include metric cases for positive integer p.The paper also discusses Mahalanobis distance, which applies a linear transformation to adjust feature-vector proximities.
  • Inner-product scores: Inner products can overweight vector magnitude; normalizing vectors produces cosine similarity, which measures the angle between them.Two identical vectors with larger magnitudes receive larger dot products than identical smaller vectors.
  • Multi-vector search: Multi-vector search aggregates scores across multiple vectors representing one entity, using functions such as the mean or weighted sum.This supports cases where an entity, such as a face, is represented by several feature vectors.
  • Open issues: High dimensionality can make vectors indiscernible, while selecting an appropriate similarity score remains theoretically unresolved and is often based on experience.Alternative Minkowski distances have been explored, but fractional-order results remain inconclusive; score choice also depends on embeddings and query semantics.

2.2 Queries and Operators

Vector search queries operate over embedded collections using similarity-based criteria, with operators ranging from full projection to specialized index-supported execution. Query variants include nearest-neighbor, range, hybrid, batched, and multi-vector searches, evaluated by accuracy and performance measures.

  • Query foundations: A vector collection S contains N D-dimensional vectors, and search queries return subsets whose similarity to query vector q satisfies specified criteria.An embedding model maps real-world entities to feature vectors before storage, while search operates over those vectors.
  • Basic search queries: (c, k)-search queries retrieve exact or approximate neighbors, where c controls approximation degree and k specifies the number of neighbors.ANN returns a k-size subset whose distances are at most c times the distance to the closest point; c = 1 gives exact search.
  • Basic search queries: Range queries use a radius r rather than a requested neighbor count, while MIPS applies nearest-neighbor search to inner products.These are alternative similarity-search formulations alongside (c, k)-search queries.
  • Query variants: Hybrid queries combine vector similarity with boolean predicates over associated attributes, whereas batched queries expose multiple queries simultaneously for flexible execution order.A hybrid k-NN query can require both membership among the k nearest vectors and satisfaction of attr < c.
  • Query variants: Multi-vector queries aggregate scores across multiple query or entity vectors, with support reported for MQSF and SQMF but not MQMF.MQSF uses multiple query vectors with single-vector entities; SQMF uses single-vector queries with multi-vector entities.
  • Operators and evaluation: Full projection answers these queries in O(τN), but τ is typically O(D), so specialized index operators are needed when N and D are large.Accuracy is commonly assessed with precision and recall, while performance uses latency and throughput.

2.3 Query Interfaces

Vector database query interfaces differ by system architecture: native and NoSQL systems commonly expose small APIs, while relational extensions express vector search through SQL syntax.

  • Native and NoSQL interfaces: Native and NoSQL VDBMSs tend to provide small APIs, exemplified by Chroma’s Python interface with nine commands.The commands include add, update, delete, and query.
  • SQL interfaces: Relationally extended VDBMSs use SQL extensions to express k-NN and ANN searches over vector columns.In pgvector, a query orders rows by the distance operator and limits the result count.

3 Indexing

Vector indexing addresses expensive high-dimensional comparisons and the absence of obvious vector ordering by partitioning collections and organizing searchable structures. The survey groups techniques into randomization, learned partitioning, navigable partitioning, compression, and disk-resident designs.

  • Indexing motivation: Brute-force vector search costs O(DN), which is prohibitive when vector dimensionality D and collection size N are large.Indexes instead reduce comparisons by partitioning S and arranging partitions into traversable data structures.
  • Indexing motivation: Vectors lack obvious sort orders or categories, making accurate and efficient index construction difficult compared with structured attributes.This lack of structure motivates specialized partitioning techniques.
  • Partitioning: Randomization amplifies probabilities across independent events, learned partitioning uncovers internal collection structure, and navigable partitioning supports traversal across regions.The survey identifies these as three principal partitioning approaches.
  • Storage techniques: Quantization maps vectors to more space-efficient, usually lossy representations while seeking to minimize information loss and storage cost.Compression addresses the large physical size of vectors.
  • Storage techniques: Disk-resident indexes minimize retrievals in addition to comparisons, while tables, trees, and graphs organize similar vectors as buckets, nested structures, or traversable connections.Data-dependent partitioning can become unbalanced after updates and may require index rebuilding.

3.1 Tables

Table-based indexes partition vectors into buckets using randomized or learned mappings, then scan selected buckets rather than the full collection. Quantization further compresses vectors and can reduce distance-computation costs during bucket scans.

  • Learning to Hash: Learned table indexes include directly learned hash functions and k-means-based assignment to nearest centroids.
  • Locality Sensitive Hashing: LSH offers tunable performance with error guarantees but may increase query and storage costs through redundancy.
  • Locality Sensitive Hashing: LSH hashes vectors into multiple tables, retains colliding vectors as candidates, and reranks them by true distance.Its query complexity is dominated by hash evaluations, O(DN^ρ).
  • Quantization: Quantization partitions vectors into sub-vectors, assigns each to a codebook centroid, and stores the concatenated centroids as a compressed representation.Product quantization uses m subspaces and stores each vector using m log2(D/m) bits.
  • Quantization: O(mN) replaces O(DN) bucket scanning in ADC after centroid-distance preprocessing for IVFADC.The preprocessing computes distances between query sub-vectors and codebook centroids before lookup-based scanning.

3.2 Trees

Tree-based indexes recursively partition vectors, using distance, learned, or randomized splitting strategies to support logarithmic or approximate search. Their maintenance and accuracy depend on dimensionality, traversal policy, and update behavior.

  • Tree-based indexes recursively split the vector collection, with construction complexity characteristically O(DN log N).
  • Distance-based trees work effectively for low-dimensional vectors but suffer from the curse of dimensionality at higher dimensions.
  • Random Trees: High-dimensional trees such as FLANN and ANNOY use randomized splitting combined with learned or random-projection partitioning.
  • Defeatist search returns the vectors in the leaf containing the query without backtracking, achieving O(D log N) complexity for approximate results.
  • Tree insertions cost O(D log N) on average and O(DN) in the worst case, while out-of-distribution insertions lack an obvious rebalancing mechanism.
  • Random Trees: A forest of random trees can improve recall, but RPTree projection vectors add O(DN) storage overhead compared with k-d tree and FLANN.Combining projections across trees can reduce this overhead to O(D log N).

3.3 Graphs

Graph-based indexes overlay edges on vector data and guide search through neighboring nodes, with edge selection determining construction and traversal behavior. They perform well empirically, but connectivity, construction cost, and approximation impose important trade-offs.

  • Graph indexes guide vector search by traversing edges between nodes positioned at the corresponding data vectors.
  • Graph construction differs mainly in edge selection, including nearest-neighbor association, iterative refinement, search trials, and navigability heuristics.
  • Graph-based search performs well in practice and may approach LSH's N^ρ query and N^(1+ρ) storage limits with smaller constant factors.
  • k-Nearest Neighbor Graphs: Approximate KNNG construction can iteratively refine an initial graph, while EFANNA uses randomized k-d trees to obtain higher recall and faster construction.
  • k-Nearest Neighbor Graphs: Disconnected KNNG components require search restarts for high online-query accuracy, whereas connected graphs support a single path from any initial node.
  • Small World Graphs: A navigable small-world graph is likely to achieve logarithmic search complexity even in the worst case.

3.4 Discussion

HNSW combines practical construction, storage, update, and query-speed advantages, explaining its broad commercial adoption. However, index choice remains workload-dependent, with alternatives favored for batching, error guarantees, limited memory, or write-heavy workloads.

  • Index selection: HNSW is easy to construct, has reasonable storage requirements, supports updates, and provides fast queries.Its storage cost can still concern very large vector collections, although compression-based remedies exist.
  • Index selection: KNNGs may suit batched queries because, after construction, they can answer them in O(1) time.KGraph is easy to construct, whereas EFANNA is more adaptable to online queries.
  • Index selection: LSH-based indexes or RPTrees can be considered when error guarantees matter, while SPANN or DiskANN suit limited-memory settings.The passage presents these as workload-dependent alternatives to HNSW.
  • Index selection: Tree-partitioned graph indexes, including NGT, combine an initial tree partition with graph indexes over the resulting leaves.This mixed structure is intended to improve search performance.
  • Index selection: HNSW graphs can also be built over product-quantized vectors, combining graph navigation with vector compression.Weaviate is given as an example of this combination.

4 Query Optimization and Execution

Query optimization and execution for vector systems centers on enumerating and selecting plans, especially for hybrid queries that combine vector search with attribute predicates. Systems use filtering operators, predefined or automatically enumerated plans, rule-based or cost-based selection, and hardware or distributed execution techniques.

  • Hybrid query operators: Hybrid queries introduced block-first and visit-first scans because vector indexes cannot be easily combined with attribute filters.Block-first filters index vectors before scanning, while visit-first checks predicates during index traversal.
  • Hybrid query operators: Pre-filtering applies predicates before search, post-filtering applies them afterward, and single-stage filtering applies them during search.These are the three basic execution placements for predicate evaluation.
  • Hybrid query operators: Visit-first scan can be faster for low-selectivity predicates, but highly selective predicates can cause frequent backtracking while filling the result set.Its advantage comes from avoiding the preliminary blocking step.
  • Plan enumeration: Systems may use predefined plans for simple vector queries, whereas more complex or relationally based systems can enumerate plans automatically.Single plans reduce enumeration and selection overhead but may fit workloads poorly.
  • Plan selection: Plan selection uses handcrafted rules or cost models based on distance calculations, memory and disk retrievals, predicate selectivity, and desired accuracy.Qdrant and Vespa use selectivity-based rules, while AnalyticDB-V and Milvus use linear cost models.
  • Plan selection: Cost estimation remains difficult for graph or tree pre-filtering and visit-first scans because blocking and predicate-failure rates are uncertain.Post-filtering also requires choosing α, which trades search cost against the likelihood of returning k results.
  • Execution: Vector execution can exploit processor caches, SIMD instructions, GPUs, distributed search, and parallel cluster searches to reduce latency or increase throughput.Write-heavy systems may also sacrifice consistency for write throughput through out-of-place updates.

5 Current Systems

Current VDBMSs span native and extended designs, with systems differing in workload focus, query capabilities, indexing, optimization, and storage models. This produces a performance–capability spectrum: specialized native systems favor speed, while extended relational systems offer broader capabilities with potentially lower performance.

  • System taxonomy: Native systems are specialized for vector management, with small query APIs, simple processing flows, and basic storage models.They divide into mostly-vector systems and mostly-mixed systems according to workload focus.
  • Native systems: Mostly-vector systems target fast search over large collections and often use one graph-based index or a single predefined plan.Some omit query parsers, rewriters, and optimizers because their supported query space is narrow.
  • Native systems: Mostly-mixed systems support broader query varieties, including exact, range, predicated, and attribute-only queries.Milvus, Qdrant, and Manu use query optimization, while Weaviate, NucliaDB, and Marqo provide richer data or storage models.
  • Native systems: Milvus and Manu support all three basic query types, multiple indexes, and cost-based optimization, whereas Qdrant uses rule-based optimization with a block-first HNSW index.These examples illustrate different optimization and indexing choices within mostly-mixed systems.
  • Native systems: NucliaDB and Marqo combine sparse keyword vectors with dense feature vectors through aggregate scores for multi-vector search.This supports document-oriented retrieval combining keyword and semantic signals.
  • Extended systems: Extended systems inherit underlying-system capabilities and complexity; nearly all listed systems support the basic query types, multiple indexes, and query optimization.NoSQL and relational systems form the two extended-system subcategories.
  • Discussion: The systems cover a spectrum of performance and capabilities: native mostly-vector systems emphasize performance, while extended relational systems offer the most capabilities but possibly less performance.Native mostly-mixed and extended NoSQL systems occupy an intermediate balance, while relational integration avoids introducing a separate system.

6 Benchmarks

Benchmarking of vector search algorithms and systems remains limited, despite the diversity of methods and implementations. Existing efforts range from controlled algorithm comparisons across many datasets to evaluations of complete VDBMSs under more realistic implementation conditions.

  • Benchmark landscape: Comprehensive cross-disciplinary comparisons of vector search algorithms and systems are scarce because algorithms arise from many fields.The paper identifies two notable benchmarking efforts.
  • Algorithm benchmarks: One benchmark uniformly implements many ANN algorithms and evaluates them across 18 datasets spanning 100 to 4,096 dimensions and up to 10 million vectors.Methods include LSH, L2H, quantization, tree-based, and graph-based techniques.
  • System benchmarks: A second benchmark evaluates full VDBMSs while retaining implementation differences to better reflect real-world conditions.Its datasets are smaller in both size and dimensionality than those of the algorithm-focused benchmark.

7 Challenges and Open Problems

Despite substantial progress in vector data management, important challenges remain in similarity-score selection, hybrid operator design, incremental search, multi-vector search, and security and privacy.

  • Similarity Score Selection: Similarity-score selection lacks rigorous guidance for matching scores to scenarios, leaving the problem largely unexplored beyond limited experimental work.EuclidesDB can experimentally compare scores and embedding models, but broader guidance remains unavailable.
  • Operator Design: Hybrid operator design remains difficult because graph block-first scans can disconnect components, while visit-first scans have unpredictable backtracking costs.Offline blocking is also limited to small numbers of attribute categories, complicating repair and plan selection.
  • Incremental Search: Incremental k-NN search can deliver very large result sets in small increments, but vector indexes do not yet clearly support this access pattern.This pattern is relevant to e-commerce and recommender platforms.
  • Multi-Vector Search: Multi-vector search remains inefficient with aggregate scores, while generic multi-attribute top-k methods are difficult to adapt and MQMF queries lack existing solutions.Aggregate scoring multiplies the number of distance calculations.
  • Security and Privacy: Secure and private high-dimensional vector search requires new techniques as vector search becomes mission-critical, particularly in managed cloud services.The challenge concerns both data security and user privacy.

8 Conclusion

The survey reviews vector database management systems developed for fast and accurate search in applications such as LLMs and e-commerce. It covers query processing, indexing, optimization, execution, commercial systems, and benchmarks.

  • Query Processing: The survey examines query processing, including similarity scores, query types, and basic operators.
  • Vector Search Indexes: It reviews the design, search, and maintenance considerations of vector search indexes.
  • Query Optimization and Execution: It describes query-optimization and execution techniques including plan enumeration, plan selection, hybrid-query operators, and hardware acceleration.
  • Systems and Benchmarks: It discusses commercial vector database systems and benchmarks used for experimental comparisons.
Loading 2310.14021v1…