Sharding a vector index that does not fit on one node, how is it typically done, and what's the query-time cost?

Short answer·Medium·4.0 · 0·~3 min·Asked atPinecone Qdrant·Relevant atDatabricks Turbopuffer

Attempt it

Describe how managed vector databases shard an index that exceeds single-node RAM, and explain the query-time consequences for QPS and p99 latency.

Free · 2 AI evals / day

When an ANN index outgrows a single machine's RAM (typically past tens of millions of vectors at modern embedding dimensions), the standard fix is sharding: split the corpus across multiple nodes, each holding its own independent index. **The sharding scheme.** Almost universally random or hash based by vector ID. Compute `hash(vector_id) mod N_shards`, that shard owns the vector. Random assignment gives even load and avoids hot spots. **Each shard is its own ANN index.** HNSW or IVF-PQ, built only over the vectors assigned to that shard. The shards do not know about each other. **Query path.** A query comes in to a coordinator. The coordinator broadcasts the query to all shards. Each shard runs its local ANN search and returns its top-K. The coordinator merges the per shard results (a small heap merge over `N_shards * K` candidates) and returns the global top-K. **Replicas.** Each shard is typically replicated 2 or 3 times for availability and to handle higher read traffic. The coordinator picks any replica per shard per query. **The throughput-vs-latency tradeoff.** Sharding multiplies QPS because shards run in parallel. But it does not reduce per query latency, and the p99 latency actually gets worse: every query waits for the slowest shard, and across many shards the chance that at least one is slow grows. This is the 'fan out tail latency' problem and it is the price you pay for horizontal scale.

**Sharding scheme.** Random or hash based by vector ID is the default in Pinecone, Milvus, Weaviate, and Vespa. Each shard holds an independent ANN index (HNSW or IVF-PQ) over its slice of the corpus, with replicas per shard for availability and read scaling. Alternative schemes (cluster based sharding by vector content, tenant based sharding by namespace) exist but introduce skew risk and operational complexity; random sharding is the safe default. **Query path: scatter gather.** A coordinator node receives the query, broadcasts it to all shards in parallel, waits for each shard's local top-K, and merges into the global top-K. The merge is cheap: a heap over `N_shards * K` candidates, O(N_shards * K * log K) which is microseconds. **The consequences for QPS.** QPS scales horizontally. Adding shards adds parallel compute capacity. Adding replicas adds parallel read capacity. A well-sharded system can serve linear in shards QPS. **The consequences for latency.** Per-query latency does NOT decrease with sharding. The total wall clock is `max(shard_latency_i) + merge`, which is dominated by the slowest shard. Worse, the p99 of the maximum across N_shards is higher than the p99 of any individual shard. If a single shard's p99 is 10ms, the system's p99 across 10 shards is roughly 30 to 50ms because there are 10 independent dice rolls for the slow case. **This is the 'fan out tail latency problem'.** Jeff Dean wrote the canonical 2013 paper on it (`The Tail at Scale`). The fix is not to add more shards; it is to make the tail of each shard tighter. **Mitigations in 2026 production vector DBs:** - *Hedged requests.* Send the query to two replicas of each shard; take whichever responds first. Costs roughly 2x replica resources, eliminates most tail latency outliers from JVM GC, queue depth, or cache misses. - *Shard-affine routing.* For multi tenant deployments, route a tenant's queries only to the shards that hold their data.

Quick reference

TL;DR

Random or hash based shard-by-id. Each shard runs its own ANN index. Queries scatter gather to all shards and merge top-K.

Memory aid

Easy to grasp

Imagine your library is too big for one room. So you split the books randomly into ten rooms, with one librarian per room. When someone asks 'find me books like this one', the question is asked to all ten librarians at once. Each librarian searches their own room and brings back their best 10 matches. Then you compare the ten lists and keep the best overall. This is fast when all librarians answer quickly. But on a busy day, if even one librarian is slow, your customer has to wait for them. Adding more rooms means more answers per minute (throughput), but it does not make any single answer faster, and the chance that at least one room is slow goes up with each new room.

Key concepts

Sharding

Detailed answer & concept explanation

~6 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.

Quick scan · 2–4 min

Everything important, quickly.

4 min: random hash sharding + scatter gather query + QPS scales but p99 worsens + tail at scale paper + hedged requests / shard affine routing / timeouts as mitigations + 2026 vendor architectures.

Side-by-side

Property	What sharding gives you	What sharding does not give you
QPS	Linear scaling with shard count	Same per query latency
Memory ceiling	Index larger than one node's RAM	Memory efficiency per vector
Availability	Replicas handle shard loss	Eventual-consistency guarantees by default
p99 latency	Worse with more shards (tail at scale)	Lower per query latency
Tenant isolation	Shard-affine routing if partition keys are used	Free isolation; you must design it in

Real-world examples

Real products, models, and research that use this idea.

Pinecone's pod model shards the corpus across pods of fixed RAM; serverless tier shards across stateless query nodes pulling from object storage. Both use random shard assignment with hedged reads.
Milvus separates the architecture into data, index, query, and coordinator nodes. Sharding is at the segment level; partition keys allow shard affine routing for multi tenant workloads.
Vespa, used at Yahoo and Spotify for over a decade, shards content groups with internal redundancy. Documented tail latency mitigations include hedged requests and timeout bounded queries.
Google's 2013 'Tail at Scale' paper by Jeff Dean and Luiz Barroso is the canonical analysis of fan out tail latency and the techniques (hedged requests, tied requests) used to mitigate it. The patterns transfer directly to vector DB sharding.

Interviewer follow-ups

What an interviewer would ask next. Try answering before peeking at the approach.

QWhy is the maximum of N percentile higher than the individual shards' percentile?

QWhat is the cost of hedged requests, and when is it worth paying?

QHow does the merge step at the coordinator scale?

Don't say this

Red flags and common mistakes that signal junior thinking. Click to expand.

Most common mistake

Believing that adding shards reduces per query latency. It reduces per shard work but not the wall clock time, because the query waits for the slowest shard.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

References

Primary sources. Skim if you want the original framing.