Beginner

Vector databases separate two things: storing a write durably (the upsert returns success) and making the vector findable by a query (the index has to update). The gap between the two is called the freshness window.

Why it exists. Indexes like HNSW and IVF are not designed for one at-a time updates. Inserting a single vector into a built HNSW graph means walking the graph and stitching the new node in, which is expensive. Production engines batch writes: incoming vectors go into a memtable, a write ahead log, or a small fresh segment. Every so often (milliseconds to minutes, depending on the engine and tier), the engine flushes the buffer or merges the fresh segment into the main index. Only after that step is the vector searchable.

Why 200 ms is well inside that window. Pinecone serverless typically takes seconds, Elasticsearch defaults to a 1-second refresh interval, Milvus has explicit consistency levels with documented staleness. A 200 ms query right after an upsert almost always lands in the gap.

The other options do not match the symptom. Vectors are not silently rejected for normalization; approximation lowers recall a little but does not permanently hide new entries; and the embedding model has nothing to do with index visibility.

The missing word is tombstone.

A tombstone is a marker that says a node is logically deleted but physically still present in the graph. HNSW uses this pattern because physically removing a node would require rewriting incoming neighbor pointers from every other node that references it, which is too expensive to do on every delete.

The term comes from log-structured database systems like Cassandra and RocksDB, where deletes also leave a tombstone in the LSM tree until the next compaction pass merges segments and drops the dead entries. The metaphor is exact: a marker that says something used to be here.

In vector databases, the consequence is that deletes do not free memory immediately and do not speed up search immediately. Background compaction or a periodic rebuild is what actually reclaims the space and the graph-walk cost.

Tombstones are logical deletions. The vector engine marks the node as deleted but does not remove it from the graph, because physically removing it would mean rebuilding every neighbor pointer that points to it.

The symptoms that follow from that mechanism are about presence without visibility:

• Latency creeps up. The graph keeps growing in walk-time terms even when the live data is flat. Search has to traverse dead nodes that contribute nothing to results.
• Memory does not shrink. Deletes return the id to the user but do not free the underlying graph storage. Heap and resident memory hold steady or grow.
• Recall dips in churned regions. When many neighbors of a live node are tombstoned, the live node's effective neighborhood shrinks. The ANN walk loses connectivity, and the candidate set degrades.

The two distractors point at things that are not symptoms of tombstones. Write throughput is not improved by deletes; the write path adds new nodes regardless of how many are tombstoned. Score signs are a function of the metric and the vectors, not of deletion state; cosine over unit-normalized vectors lives in [-1, 1] whether the corpus has tombstones or not.

Production vector search has a handful of canonical failure modes. Each symptom maps to a specific layer of the system.

Missing fresh document points at the write path. Most engines acknowledge a write before it is searchable; the document sits in a memtable or fresh segment until the next flush. The fix is to query the right consistency tier or wait for the flush window.

Recall sag after bulk delete points at tombstones. Deleted nodes still occupy graph memory and still get visited during traversal. The fix is to run compaction or rebuild the affected shards.

Run-to-run nondeterminism points at the read path. Multiple replicas or shards are answering, and their ANN candidate sets differ slightly. The fix is either deterministic routing or accepting that ANN is approximate and pinning the user to a session-stable replica.

Incomparable scores across collections points at config. Different distance metrics (cosine vs dot product vs L2) or different normalization conventions produce numbers that look similar but mean different things.

Filtered results below k points at post-filtering. The ANN layer returned a fixed candidate count, then the filter rejected most of them. The fix is pre-filtering (push the filter into the search) or oversampling.

The workload is bursty: one busy hour at 2,000 QPS, then 23 hours of near-silence. Pick the pricing model whose cost actually tracks that shape.

Dedicated pods rent a fixed amount of capacity around the clock. You pick the size based on peak load, then pay for that size for every minute of every day. With one busy hour, you are paying full price for 23 idle hours, roughly 96% waste.

Serverless usage-based pricing splits the bill into two parts: a small fee for storage (your vectors sitting on object storage) and a per-query or per-read fee that fires only when you actually serve traffic. The busy hour costs whatever 7.2 million queries cost. The 23 idle hours cost only storage, which for a few million vectors is pennies.

GPU clusters and per-seat licensing are not pricing models that fit this shape. GPUs accelerate index build or very high throughput; per-seat licensing is for tools, not for query workloads.

Both SPANN and DiskANN are designed so the bulk of the index lives on cheap storage, not in RAM. They differ in how they read it.

DiskANN builds a navigable graph (Vamana). Each query walks the graph, hopping from node to node, fetching one node's neighbors at a time. Each hop is a separate small read, and the next hop depends on the current node's content, so reads are inherently serial.

SPANN partitions vectors into posting lists, one per cluster centroid. The centroids stay in RAM. A query finds the few nearest centroids, then fetches the corresponding posting lists in one go and scans them.

On local NVMe, each read is fast (~100 microseconds), so DiskANN's chain of hops still finishes inside the budget. On object storage (S3, GCS), each read is tens of milliseconds, and the chain of hops never finishes inside 200 ms. SPANN's few large parallel reads do, because the round-trip cost is paid only a handful of times per query.

The user query does not finish when the first shard answers. It finishes when the slowest shard answers, because the coordinator has to merge results from all of them before returning.

So the right question is not "how often is one shard slow" but "how often is at least one out of sixteen slow." If each shard is fast 99% of the time, then all sixteen are fast only 0.99^16 = 85.1% of the time. That leaves 14.9% of queries where some shard tripped its p99.

A per-shard event that the team thought was rare (1 in 100) becomes a routine user experience (about 1 in 7 queries). This is why teams measure end-to-end latency at the coordinator, not at the shard, and why they add hedging, timeouts, or replica racing to bound the tail.

When p50 stays healthy but p99 triples, the shape of the problem is contention, not algorithmic slowdown.

Why the median is fine. Most queries during the rebuild still find a free CPU core, hit cached vectors, and finish in their normal time. The rebuild is running on some threads, but most query work runs on others, so the typical query path is unaffected.

Why the tail explodes. A fraction of queries arrive at a bad moment. They collide with a build thread for CPU. They miss the page cache because the rebuild just evicted the pages they needed. They queue behind a burst of segment-merge I/O. Each of these adds tens to hundreds of milliseconds of stall to the few unlucky queries, and the tail percentile is exactly what measures unlucky queries.

The other options are wrong for clear reasons. Search does not fall back to brute force during a rebuild; the existing index keeps serving while the new one is being built. Recall and latency are independent axes; a less recall-accurate index can actually be faster, and a more accurate one slower. And dismissing tail metrics during maintenance windows is how SLO breaches reach users.