Handling Updates and Deletes in a Search Index

Search indexes are built to be read. Almost all of them make deletion cheap by not doing it — marking a record dead and reclaiming the space later — and every operational surprise in this area comes from not knowing that.

Why a delete is not a delete

The structures that make search fast are structures that are expensive to modify. An HNSW graph is a set of layered proximity lists where every node may be an entry point for a search path; removing a node means repairing the neighbour lists of everything that pointed at it, and doing that under concurrent reads without degrading recall is a hard problem. An inverted index is a set of immutable posting lists. A quantised index has a codebook trained on the vectors present.

So the universal answer is a tombstone: mark it deleted, filter it out at query time, reclaim the space during a later rebuild or merge. The consequences follow directly and they are all things you should plan for rather than discover.

• Disk does not shrink. Deleting a million vectors frees nothing until a compaction runs. Capacity planning must be on rows ever written, not rows currently live.
• Query cost does not drop. The search still traverses deleted nodes; they are filtered from the results. An index that is half tombstones does roughly twice the work per query.
• Recall can drift. Deleted nodes still act as graph waypoints in some implementations, which is fine, but a heavily deleted graph can also become poorly connected and quietly return worse results.
• The data is still there. A tombstone is not erasure. For a deletion request under a privacy regime this distinction is the whole question.

What each index actually does

The practical rule that falls out: track the tombstone ratio and rebuild or compact on a threshold. Something like 20% deleted is a common trigger; the right number depends on how much query latency you are willing to pay to defer the rebuild.

Schedule the compaction rather than letting it happen. A merge or a rebuild is I/O-heavy and it competes with the queries it is meant to speed up, so the version that runs at four in the morning is consistently better than the version that triggers automatically at the moment of peak churn — which is peak traffic, because churn and traffic have the same cause.

An update is a delete plus an insert

No vector index updates a vector in place, because the vector’s position is what its graph edges encode. Editing it would leave a node whose neighbours are the neighbours of where it used to be. So an update is delete-then-insert, and the interesting question is what a reader sees in between.

Ordering decides which failure you get. Delete first and there is a window with no result at all — the document is invisible. Insert first and there is a window with two — both versions retrievable, which typically means a top-k full of the same passage twice and a model asked to reconcile two versions of the same fact.

For most systems insert-then-delete is the right choice: a duplicate for a few seconds is less damaging than a gap, and it is easy to suppress at the reader with a version filter.

def update_document(doc_id: str, new_text: str) -> None:
    new_version = write_version(doc_id, new_text)      # new rows, new ids
    embed_and_index(new_version)                       # both live now
    mark_current(doc_id, new_version)                  # single-row commit
    retire(previous_version_of(doc_id))                # tombstone the old

# Reader suppresses the overlap without needing a lock:
#   WHERE c.version_id = d.current_version_id

The current_version_id pointer is what turns a multi-step process into a single atomic switch. Every step before it is additive and invisible; the pointer update is one row and it either happened or it did not.

It also gives you a clean answer to the crash case. If the process dies after embedding and before the pointer moves, the new rows are orphans: present, unreferenced, harmless, and cleaned up by a sweep that deletes versions never promoted within a day. Compare that with the ordering where the delete comes first, in which a crash leaves the document absent from the index with nothing recording that it should be there.

Making it atomic for the reader

Three patterns, in ascending order of cost and of guarantee.

Pointer swap at the row level

The code above. Cheap, per-document, and gives you a consistent view of each document individually. It does not give you a consistent view of the whole corpus at a point in time.

Alias swap at the index level

Build a whole new index, verify it, then move an alias that readers resolve. Elasticsearch aliases and equivalents in other stores make this atomic. The cost is double the storage during the build and the time to build. This is the right answer for a full re-embed, and it gives you rollback for free — the previous index is still there.

Snapshot reads

Give every write a monotonically increasing version and let a reader pin one, so a multi-query session sees one consistent corpus. Rarely needed for a chat feature and genuinely needed for an evaluation run, because otherwise a re-index halfway through invalidates the comparison.

Whichever you pick, verification comes before the swap and not after. The corpus-level checks exist precisely to be the gate on a promotion step.

When deletion has to be real

A tombstone hides a record. Under a right-to-erasure request it does not discharge the obligation, and the surface is larger than the index: the raw bytes, the extracted text, the chunk rows, the vectors, any search caches, any semantic cache of past answers, the logs of requests that included the content, and any backups.

Two design choices make this tractable rather than heroic. First, make every derived artefact traceable to a document id — which the schema in the table design does through foreign keys, so a cascade is a query rather than a search. Second, treat backups explicitly: define a retention window, record erasure requests in a durable log, and re-apply that log to any restore. Then the honest answer to “is it gone?” is “from live systems immediately, from backups within N days”, which is a defensible position rather than an evasion. The obligation itself is worth understanding before designing the mechanism.