Vector Tombstone

A vector tombstone represents a logical deletion. The vector's entry remains in the index but is marked as invalid. The actual physical deletion—removing the data from storage and updating the index structure—is deferred. This separation allows for high-throughput delete operations without immediate, costly index reorganization, which is performed later during compaction or garbage collection.

Tombstones are physically cleaned up by a background compaction process. This process:

• Scans index segments for tombstones.
• Creates new, optimized segments excluding the tombstoned data.
• Reclaims storage space. Compaction is triggered based on thresholds like the ratio of tombstones to active vectors or a scheduled maintenance window. This balances write amplification with storage efficiency.

During a similarity search (k-NN or ANN query), the database's query engine must filter out results that point to tombstoned vectors. This adds a small overhead to each query, as the system checks a deletion bitmap or metadata flag. The performance impact is typically minimal compared to the cost of immediate index modification but must be accounted for in latency SLOs if tombstone density becomes very high.

Tombstones ensure query consistency. Once a vector is tombstoned, it is immediately excluded from all subsequent search results, preserving the semantic accuracy of the retrieval system. Without tombstones, a physically deleted vector might temporarily remain in results during an index update, causing incorrect or stale data to be returned, which breaks the system's correctness guarantees.

Common implementation strategies include:

• Deletion Bitmap: A separate, in-memory bitmap where each bit corresponds to a vector ID; a set bit indicates a tombstone.
• Tombstone List: A dedicated, append-only log or list of deleted vector IDs.
• Metadata Flag: A boolean is_deleted flag stored within the vector's metadata record. The chosen pattern affects the speed of delete operations, query filtering overhead, and compaction complexity.

Managing tombstones is crucial for vector database health. Key operational metrics include:

• Tombstone Ratio: The percentage of tombstoned vectors in an index segment. A high ratio (>20-30%) signals that compaction is overdue and is degrading query performance and wasting storage.
• Compaction Lag: The time delta between a logical delete and its physical cleanup. Monitoring this prevents unbounded storage growth. These metrics should be integrated into standard vector telemetry dashboards.