Many approximate-nearest-neighbor systems assume a static corpus, an in-memory graph, or a specialized vector store that owns its own sharding model. Transactional databases make different promises: data is inserted continuously, indexes must stay fresh, tenants need filtering, ranges rebalance across nodes, and failover cannot require rebuilding a large memory-only structure. C-SPANN adapts partition-based vector search to those distributed SQL constraints.
C-SPANN, short for CockroachDB SPANN, combines ideas from SPANN, SPFresh, ScaNN, and RaBitQ. Its core is a hierarchical k-means partition tree whose partitions are stored as ordinary CockroachDB key-value ranges. Queries descend through centroid partitions, scan a small number of leaf partitions, compute approximate distances with locally quantized vectors, and rerank a candidate set. Inserts and deletes update only local partitions so the index remains fresh.
The transferable lesson is how to co-design an ANN index with the storage engine beneath it. Instead of treating vector search as a separate service bolted onto SQL, C-SPANN makes the index’s partitions match the database’s split, merge, and rebalance mechanics.
Vectors are grouped into partitions, each represented by a centroid. Those centroids are recursively clustered into higher-level partitions, producing a tree. At query time, the search compares the query vector to centroids, descends into the closest partitions, and scans only a small candidate subset at the leaves.
Each C-SPANN partition is stored as a self-contained range of key-value rows. As partitions grow, split, shrink, or move, the database’s existing range machinery can distribute them across nodes. This avoids a separate index-sharding layer and reduces the chance that vector traffic concentrates on one coordinator.
Full embedding vectors are expensive to scan. C-SPANN compresses indexed vectors using RaBitQ, a one-bit-per-dimension quantization method, and stores additional values needed for distance estimation. The CockroachDB article reports a roughly 94% size reduction in common cases, shrinking a 3 KB OpenAI-style embedding to around 200 bytes in the index.
A vector index inside distributed SQL should not require a second distribution system. If ANN partitions are ordinary database ranges, the same split, merge, replication, and rebalancing mechanisms that serve tables can also serve vector search.
A query starts at the root partition. The engine compares the query vector against centroids at the current level, selects a beam of nearby partitions, and descends. At the leaf level, it scans quantized vectors from the selected partitions, estimates distances cheaply, and reranks a shortlist using higher-fidelity data when needed.
def cspann_search(query, root, beam_width, top_k):
frontier = [root]
while not all(node.is_leaf for node in frontier):
candidates = []
for node in frontier:
for child in node.children:
candidates.append((distance(query, child.centroid), child))
frontier = [node for _, node in sorted(candidates)[:beam_width]]
scored = []
for leaf in frontier:
for item in leaf.quantized_vectors:
approx = rabitq_distance(query, item.code, leaf.centroid, item.stats)
scored.append((approx, item.id))
return rerank_with_full_vectors(query, scored, top_k)Inserts are assigned to their nearest suitable partition. Deletes mark or remove vectors from the affected partition. When a partition grows too large, it can split locally; when the data distribution shifts, vectors can be relocated toward nearer partitions. Because quantization is local to a partition, only the affected partition’s vectors need re-quantization after a split or merge.
def insert_vector(vector, row_id):
leaf = find_nearest_leaf(vector)
code, stats = quantize_relative_to_centroid(vector, leaf.centroid)
leaf.append(row_id, code, stats)
if leaf.size > leaf.max_size:
left, right = split_with_local_kmeans(leaf.vectors())
replace_partition(leaf, [left, right])SQL systems often combine vector search with tenant, timestamp, ACL, or metadata filters. C-SPANN’s storage-native layout lets the database plan vector lookup alongside ordinary predicates. From the index’s point of view, one billion vectors globally and many smaller tenant-scoped trees are both combinations of key ranges and partitions.
Customer support, commerce, and internal knowledge systems often need newly inserted records to be searchable immediately. A rebuild-oriented vector index creates a freshness gap. C-SPANN-style incremental partition maintenance fits systems where transactional writes and semantic search share the same freshness contract.
Multi-tenant applications need vector search scoped by account, organization, or access policy. Embedding the index in SQL makes metadata filtering and vector retrieval part of the same data model, reducing the synchronization burden between a primary database and an external vector service.
Serverless databases cannot assume that every vector index is warm in memory. Persisting the tree and partitions in the storage layer reduces cold-start rebuild work and lets the system scale compute independently from durable index storage.
Keep leaf partitions within a configured size range. Small partitions add traversal overhead; oversized partitions make leaf scans expensive and produce hot ranges. Splitting by local k-means preserves search quality without a global rebuild.
Local quantization reduces error because vectors in one partition are already clustered. It also makes maintenance local: when a partition splits, only vectors in that partition need new codes. This is the practical bridge between RaBitQ compression and SPFresh-style incremental maintenance.
Searching only the closest centroid at each level is too brittle. Maintain a beam of candidate partitions so that early approximation error does not permanently prune the true nearest neighbors. The beam width becomes a recall-latency knob.