How CockroachDB Built Distributed Vector Indexing at Scale
Inside C-SPANN, CockroachDB's distributed vector index stored as ordinary table rows to achieve fresh, transactional vector search without memory blowup.
On this page
Embedding-based retrieval has become a table-stakes requirement for modern enterprise software. However, running vector search inside a distributed SQL database presents a formidable engineering challenge: how do you provide Approximate Nearest Neighbor (ANN) search while preserving distributed ACID transactions, tenant isolation, and horizontal scalability?
Specialized standalone vector databases typically rely on in-memory graphs like HNSW (Hierarchical Navigable Small World). But in a distributed database managing hundreds of terabytes, pinning full vector graphs in RAM across dozens of nodes is economically unviable and fundamentally conflicts with disk-oriented storage engines.
To solve this, CockroachDB engineered C-SPANN, a distributed vector index stored directly as ordinary SQL table data across the database’s native Raft consensus ranges.
The Flaws of Traditional ANN in Distributed SQL
Standard ANN algorithms break key distributed database principles:
- HNSW Memory Footprint: HNSW requires maintaining dense multi-layer graphs entirely in memory. When databases exceed millions of vectors, RAM consumption balloons, competing directly with relational buffer pools.
- Cluster Topology and Coordinator Bottlenecks: Centralized vector indexes force all queries through single coordinator nodes, creating severe hot spots and violating shared-nothing distributed principles.
- Write Stalls and Transactional Isolation: Re-balancing vector graphs during concurrent SQL
INSERTandUPDATEstatements causes lock contention and compromises snapshot isolation guarantees.
CockroachDB required an indexing structure that behaves like any standard relational secondary index: sharded by key, replicated via Raft, cached dynamically in disk buffers, and transactionally consistent.
Architecture of C-SPANN (Cockroach SPANN)
C-SPANN adapts the SPANN (Space-Partitioned Approximate Nearest Neighbor) algorithm to CockroachDB’s distributed Key-Value layer.
+-----------------------------------------------------------------------+
| CockroachDB C-SPANN Architecture |
+-----------------------------------------------------------------------+
| |
| [ Distributed SQL Layer (pgwire) ] |
| | |
| v |
| [ Centroid Directory (Memory Cached) ] |
| | (Partitions vector space into Voronoi cells) |
| v |
| [ Query Vector -> Match Nearest Centroid IDs: C_12, C_45 ] |
| | |
| v |
| +-----------------------------------------------------------------+ |
| | CockroachDB Distributed KV / Raft Ranges | |
| | | |
| | Range 1 (Raft Group A) Range 2 (Raft Group B) | |
| | [Centroid C_12 Postings] [Centroid C_45 Postings] | |
| | - Vector ID 101, emb... - Vector ID 308, emb... | |
| | - Vector ID 102, emb... - Vector ID 309, emb... | |
| | (Stored as KV Rows) (Stored as KV Rows) | |
| +-----------------------------------------------------------------+ |
| | |
| v |
| [ RocksDB / Pebble LSM Engine Disk Block Fetch ] |
| | |
| v |
| [ Vector Similarity Scoring & Top-K Reranking ] |
+-----------------------------------------------------------------------+
1. Two-Tier Hierarchical Space Partitioning
C-SPANN splits vector indexing into two components:
- Centroid Directory: A lightweight clustered index of centroid vectors generated via k-means clustering. Because the centroid set is tiny (thousands of vectors representing millions of data points), it easily fits in memory on every node.
- Posting Lists Stored as Rows: Each centroid corresponds to a posting list containing the actual high-dimensional vectors assigned to its Voronoi cell. Crucially, these posting lists are stored as ordinary CockroachDB rows in the database’s underlying distributed LSM storage engine (Pebble).
2. Native Raft Sharding and Colocation
Because posting lists are regular table rows, they naturally inherit all of CockroachDB’s distributed resilience:
- Posting lists automatically split across Raft ranges when they grow.
- Replicas are distributed geographically according to table locality policies.
- Writes participate in standard multi-version concurrency control (MVCC) and two-phase commits. An inserted vector is immediately visible to transactions without waiting for periodic background rebuilds.
3. Sub-Hop Query Execution
When an incoming query executes a vector similarity search:
- The local node compares the query vector against the in-memory centroid directory to identify the top-m nearest centroids.
- The query planner issues parallel point lookups for the posting list rows associated with those specific centroid IDs.
- The posting list rows are streamed from local or remote Raft range leases into memory, where SIMD-accelerated distance functions (such as cosine or Euclidean distance) score the candidate vectors.
- The top-k candidates are merged and returned with full transactional freshness.
Performance and Operational Trade-Offs
Storing vector indexes on disk inside a distributed relational engine introduces clear trade-offs compared to dedicated in-memory vector databases:
+--------------------------+-----------------------+------------------------+
| Metric | Dedicated Vector DB | CockroachDB C-SPANN |
+--------------------------+-----------------------+------------------------+
| Query Latency (p99) | 2ms - 8ms | 10ms - 25ms |
| Memory Consumption | 100% of vectors in RAM| Centroids only (~1%) |
| ACID Consistency | Eventual / None | Full Snapshot / Serial |
| Horizontal Rebalancing | Complex re-sharding | Automatic via Raft |
| Multi-table Joins | Requires app glue | Native SQL JOIN |
+--------------------------+-----------------------+------------------------+
While dedicated vector databases deliver slightly lower latency for pure similarity lookups, C-SPANN eliminates the need for external sync pipelines, background reconciliation jobs, and dual-system consistency bugs.
Key Engineering Takeaways
- Don’t force in-memory graphs into disk engines: HNSW fails at massive scale on relational storage. Partitioning space via hierarchical centroids (SPANN) aligns with LSM-tree row layouts.
- Transactional vector search simplifies architectures: Being able to query vectors and relational metadata in a single transactional SQL query eliminates fragile dual-write synchronization pipelines.
- Centroids belong in memory, posting lists on disk: C-SPANN achieves sub-25ms latency with 95% less RAM consumption by keeping only partition centroids in cache while fetching posting vectors on demand.
/* Comments */
Comments are offline right now — we reconnect automatically, nothing is lost.