How AlloyDB ScaNN scales vector search to 10 billion vectors

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.

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:

• Two-level: Utilizes coarse partitioning to guide queries, resulting in a basic search complexity of O(N^1/2).

• Three-level: Introduces an intermediate layer to further subdivide clusters, narrowing exploration to O(N^1/3).

• Four-level: Implements refined, highly granular partitions that optimize traversal efficiency down to O(N^1/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!