R5.5 · LESSON 5 OF 6

Updates and deletes

Design a retrieval record and explain filtering, indexing, partitioning, updates and consistency.

THE IDEA

Updates and deletes

Most vector indexes are much better at adding than removing. A delete usually writes a tombstone that search must skip, and cleanup (compaction) happens later. A re-embedding of a changed document writes new vectors and retires the old ones. Without a complete update path, a deleted document can remain searchable because its vector is still in the index.

Six chunks in an index. Click a chunk to delete it (it becomes a tombstone). Compaction physically removes tombstones.

entries stored: 6 live: 6 dead: 0 dead fraction 0 search ignores tombstones; until compaction they still take space and can slow scans re-embedding a document = write the new vectors + retire the old ones (8 + 8 = 16 operations for 8 chunks)

If the update path misses the index, a removed document can stay searchable: its text is gone but its vector still matches. Define when deletes become visible and when cleanup runs.

Delete chunks, then compact.

Predict first. Can a removed document remain in a stale search index?

Chapter context

A vector index solves similarity lookup; a retrieval application also needs durable records, metadata, permissions and updates. Database behavior determines which vectors are eligible and which version of a document an answer uses.

TRY IT YOURSELF

Part 1. Do it hands-on

Count tombstones and re-embedding work by hand, then build a small store with upsert, delete, compact and stats.

Six chunks in an index. Click a chunk to delete it (it becomes a tombstone). Compaction physically removes tombstones.

If the update path misses the index, a removed document can stay searchable: its text is gone but its vector still matches. Define when deletes become visible and when cleanup runs.

live fraction (800 of 10,000 dead) operations to re-embed 8 chunks seconds for 100,000 chunks at 500/s removed doc can stay searchable? (yes/no)

To do: An index holds 10,000 entries, 800 of them tombstoned (deleted but not yet removed). Live fraction?
To do: Re-embedding one 8-chunk document: you write 8 new vectors and must retire the 8 old ones. Total index operations?
To do: Re-embedding a corpus of 100,000 chunks at 500 chunks per second takes how many seconds?
To do: Can a removed document remain searchable if the index update path is incomplete? Type yes or no

Part 2. Do it in code

class VectorStore with self.entries (a list of dicts {"id", "vec", "dead"}):
upsert(id, vec): mark any live entry with that id dead, then append a new live entry.
delete(id): mark live entries with that id dead (a tombstone); return True if one was found, else False.
search(q, k): the ids of the k nearest LIVE entries (squared L2, ties: smaller id).
compact(): physically remove dead entries and return how many were removed.
stats(): {"live": ..., "dead": ..., "dead_fraction": dead / total (0 if empty)}.
needs_compaction(threshold): True if dead_fraction is strictly greater than the threshold.

class VectorStore:
    def __init__(self):
        self.entries = []

    def upsert(self, id, vec):
        pass

    def delete(self, id):
        pass

    def search(self, q, k):
        pass

    def compact(self):
        pass

    def stats(self):
        pass

    def needs_compaction(self, threshold):
        pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can a removed document remain in a stale search index?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

Raw vector storage is $M=Ndb$ for N vectors of dimension d and b bytes per coordinate. If a postfilter independently accepts fraction f of an initial k candidates, the expected survivor count is kf; this is an expectation, not a guarantee.

Worked example

Ten million vectors of dimension 768 in float32 require 10,000,000×768×4=30,720,000,000 bytes, or 30.72 decimal GB, before IDs, text, indexes and replicas. If a postfilter accepts 20% of ten candidates under a simplifying independence assumption, the expected survivor count is only two.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
bytes_used=10_000_000*768*4
assert bytes_used == 30_720_000_000
assert isclose(bytes_used/1_000_000_000,30.72)
assert 10*.2 == 2

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Filter selectivity and ANN candidate recall interact. Replication adds storage. Matching vector dimension does not establish matching embedding space.