How AlloyDB ScaNN scales vector search to 10 billion vectors

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.

1. 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 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!