AlloyDB ScaNN 如何将向量搜索扩展到 100 亿向量
AlloyDB 的 ScaNN 索引现已支持超过 100 亿向量的规模，通过全新的四层树架构（预览版）实现，将查询复杂度从 O(N^1/2) 降至 O(N^1/4)。内部测试中，该架构在 100 亿向量规模下可实现 p95 延迟不超过 51 毫秒、召回率达 95%。该功能可通过快速入门指南部署，新用户可享受 30 天免费试用。
四层树把搜索复杂度从 O(N^1/2) 逐级降到 O(N^1/4)，配合内存优化让向量索引扩到百亿规模，这会影响依赖大规模向量检索的 RAG 应用在做容量规划时的性能假设。
To satisfy the demands of enterprise-grade agentic AI applications, underlying vector databases often struggle to scale effectively as modern use cases can scale to billions of vectors.
As a fully managed PostgreSQL-compatible database service, AlloyDB is engineered to handle demanding enterprise workloads. Combining Google's infrastructure with the reliability of commercial databases, it delivers high availability, scalability, and includes a cutting-edge analytical engine, optimal for agentic AI use cases. A key part of this is its ScaNN index, which now operates efficiently at a scale of 10 billion vectors. This was achieved through a major architectural enhancement: an innovative four-level tree (preview) paired with efficient memory usage.
The 10 billion vector scale challenge
Scaling to a 10 billion vector workload presents significant memory and computational challenges. Previous AlloyDB ScaNN tree-based index was limited to two- or three-level tree configurations, and attempting to scale those structures led to several bottlenecks:
-
Increased compute intensity: Larger tree structures demand significantly more operations for both index construction and query traversal.
-
Memory constraints: The sampling processes required for 10 billion vectors can easily exceed the system's available memory capacity.
Solution: Four-level architecture
The introduction of a four-level tree (preview) is the primary innovation in the recent AlloyDB ScaNN release. This architecture, illustrated in Figure 1, employs a top-down strategy to optimize the balance between accuracy and build efficiency. To maintain high performance and mitigate recall loss, the system integrates key enhancements such as Top-K branch, SOAR, centroid adjustment and balanced tree shape.
Figure 1. AlloyDB ScaNN four-level tree architecture
This design has two primary benefits:
1. Reduced compute intensity via hierarchical partitioning
The four-level architecture drastically reduces compute intensity by using hierarchical partitioning to restrict the volume of vectors scanned during a query. Instead of traversing a flat or poorly segmented space, the multi-layered hierarchy narrows down the search path exponentially. Figure 2 illustrates the search spaces across different tree levels, demonstrating how structural layering optimizes traversal efficiency:
Figure 2. Search space for two-, three- and four-level trees
-
Two-level: Utilizes coarse partitioning to guide queries, resulting in a basic search complexity of O(N1/2).
-
Three-level: Introduces an intermediate layer to further subdivide clusters, narrowing exploration to O(N1/3).
-
Four-level: Implements refined, highly granular partitions that optimize traversal efficiency down to O(N1/4), sufficiently allowing for more than 10-billion vectors.
By dynamically expanding hierarchical layers as the dataset expands, AlloyDB ScaNN maintains ultra-low query latency and avoids computational scale walls from impacting performance.
2. Efficient memory usage
Achieving a 10 billion vector scale requires high memory efficiency. AlloyDB ScaNN uses these strategies to maximize memory management performance:
-
Balanced tree shape construction: The four-level tree utilizes a balanced configuration to circumvent memory limitations that restrict the size of training datasets. This balanced architecture effectively leverages reduced sampling sizes to construct high-fidelity tree partitions.
-
Sampling optimization: When the system encounters memory limitations, it generates a condensed sampling set that considers performance and accuracy.
Performance test results
By leveraging the innovative four-level tree architecture in our internal tests, we are able to achieve the following performance results:
-
AlloyDB can scale to over 10 billion vectors with its ScaNN index.
-
AlloyDB can deliver <= 51 ms p95 latency and 95% recall at 10 billion vectors with its ScaNN index.
Get started today
Experience AlloyDB ScaNN's four-level tree (preview) architecture today. You can deploy ScaNN for AlloyDB by following our quickstart guide to set up an instance. For optimized, high-speed vector search, refer to the official ScaNN documentation. New users can also explore AlloyDB through our 30-day free trial program. We can’t wait to hear about what you build!
Posted in
来源：Google Cloud：Databases（RSS） · cloud.google.com