Incremental Indexing: Keeping Your Vector Store Fresh

In the early days of vector databases, the standard operating procedure was simple: ingest all data, build the index, query. If the underlying data changed, you threw away the index and rebuilt it. For small datasets, this linear cost was acceptable. As datasets grow to millions of vectors and update rates increase, full reindexing becomes a prohibitive bottleneck. It creates a "write amplification" problem where every update requires reading, embedding, and re-indexing the entire dataset.

The solution is incremental indexing. This approach treats the vector store as a dynamic system that adapts to change rather than a static artifact. By leveraging Change Data Capture (CDC), upserts, and tombstone handling, engineers can maintain freshness with sub-second latency and constant-time update costs relative to the dataset size.

The Source of Truth: Change Data Capture (CDC)

The foundation of incremental indexing is knowing what changed in the source system. Relying on polling (checking for modified timestamps) is inefficient and error-prone due to race conditions. Instead, you should use Change Data Capture to intercept data modifications at the source. This integration of cdc vector databases relies on standardized logging mechanisms rather than application-level queries.

Most relational databases (PostgreSQL, MySQL) and NoSQL systems (MongoDB) expose a Write-Ahead Log (WAL) or oplog. CDC tools like Debezium or Kafka Connect listen to these logs, parsing binary data into structured events. Each event carries an operation type: INSERT, UPDATE, or DELETE. Standards such as the PostgreSQL WAL specification and Debezium’s connector documentation define these capture mechanisms rigorously, ensuring that the stream of changes accurately reflects the source of truth.

For example, a MongoDB change stream event might look like this:

{
  "operationType": "update",
  "documentKey": { "_id": "doc_123" },
  "fullDocument": {
    "_id": "doc_123",
    "title": "Updated Title",
    "content": "New content here",
    "version": 2
  }
}

This event tells the indexing pipeline exactly which document changed and its current state. The pipeline extracts the content field, sends it to an embedding model, and receives a vector. Crucially, it also knows the _id is the primary key for lookup in the vector store.

The Atomic Write: Upserts

Once the pipeline has the new vector and the document ID, it performs an upsert. These upsert operations are atomic, checking if a vector with that specific ID already exists in the index before deciding whether to insert a new entry or overwrite an existing one.

If the ID exists, the vector is overwritten. If it does not exist, a new vector is inserted. The complexity of this operation depends heavily on the underlying index structure. Flat indexes may offer O(1) insertion if unsorted, but they suffer from O(N) search costs. In contrast, HNSW (Hierarchical Navigable Small World) graphs offer O(log N) insertion and search complexity, making them vastly more efficient for large-scale updates than rebuilding the entire index.

Consider a scenario where a user updates their profile bio. The old vector represents the old bio. The upsert replaces that specific vector in the index with the new one. The surrounding vectors remain untouched. This preserves the local neighborhood structure of the index, which is critical for nearest-neighbor search accuracy.

However, upserts have a caveat: they do not automatically handle schema changes. If the embedding model changes (e.g., from text-embedding-ada-002 to text-embedding-3-large), the vector dimensions change. In this case, an incremental upsert will fail because the new vector cannot be inserted into an index expecting different dimensions. This is a known limitation of incremental indexing; model versioning requires a full rebuild or a dual-index strategy.

From a production perspective, handling concurrent upserts is also critical. Without idempotency keys or strict ordering guarantees from your CDC stream, duplicate events can lead to inconsistent states. Ensuring that your pipeline processes events in the exact order they occurred in the source database is essential to prevent race conditions where an older update overwrites a newer one.

Handling Deletions: Tombstones

Deleting a vector from an index is not as straightforward as overwriting it. Many vector database implementations use approximate nearest neighbor (ANN) algorithms like HNSW or IVF-PQ. These structures are optimized for read speed and space efficiency, not dynamic modification.

When a document is deleted from the source database, the CDC pipeline receives a DELETE event. The vector store must reflect this. However, physically removing a vector from an ANN index can be expensive and may fragment the index graph, degrading search quality.

The common pattern is soft deletion via tombstones. Effective tombstone handling involves marking the vector as deleted rather than removing it immediately. This is typically done by adding a boolean flag or a timestamp in the vector's metadata.

{
  "id": "doc_123",
  "vector": [0.1, 0.2, ...],
  "metadata": {
    "deleted_at": 1715623200,
    "is_deleted": true
  }
}

When a query is executed, the vector store filters out any results where is_deleted is true. In modern vector databases like Pinecone and Weaviate, pre-filtering during the search process is the standard and recommended approach. This ensures correctness and efficiency by excluding tombstoned items before the final ranking occurs. Post-search filtering is a less common, legacy pattern that can lead to inflated result counts and wasted compute.

This approach has a trade-off: storage bloat. Deleted vectors still occupy space in the index. Over time, this can degrade performance. To mitigate this, vector stores often offer "garbage collection" or "purge" operations that physically remove tombstoned vectors after a certain period or when storage thresholds are met. This is a batch operation that runs in the background, separate from the real-time indexing pipeline.

Why Not Full Reindexing?

The argument for full reindexing usually comes down to simplicity. Why build complex CDC pipelines and handle tombstones when you can just rebuild the index every night?

The answer lies in latency and cost. Full reindexing is an O(N) operation. As datasets scale, the linear cost of embedding and indexing every vector becomes operationally unsustainable, creating significant downtime and resource contention. During this window, your search results are stale. If you have 100,000 updates per day, incremental indexing processes only those 100,000 vectors, taking seconds or minutes. This allows you to avoid reindexing the entire dataset for every minor change.

Furthermore, full reindexing causes "search degradation" during the rebuild. As the index is being built, recall may drop, or queries may fail. Incremental indexing maintains a consistent, high-quality index at all times.

Conclusion

Incremental indexing is not a feature; it is a necessity for production-grade vector applications. By leveraging CDC to detect changes, upserts to update vectors atomically, and tombstones to handle deletions gracefully, you can maintain a fresh, accurate, and performant vector store. This approach shifts the cost from a linear, disruptive rebuild to a constant, incremental update, ensuring that your AI-powered features remain responsive and relevant.

Next Steps

To implement this strategy effectively, audit your current vector store rotation policy. Determine if your database supports pre-filtering for metadata and whether your CDC pipeline guarantees exactly-once processing. Start by testing upsert idempotency in a staging environment to ensure your pipeline can handle duplicate events without corrupting the index.