Deletion That Reaches the Vector Index

DELETE FROM chunks WHERE document_id = $1 makes the rows invisible to queries immediately. It does not remove them from the HNSW index, and it does not remove the bytes from disk. For an ordinary application the difference does not matter. For an erasure request it is the whole question, and the honest answer has three parts. Three meanings of deleted | Meaning | Description | |---|---| | Invisible to queries | No query returns the row or anything derived from it. Achieved by DELETE, immediately, through MVCC visibility. This is what an application needs. | | Absent from the index | The vector is no longer a node in the HNSW graph and is not traversed. Achieved by VACUUM, eventually. Until then the row costs you recall and latency. | | Absent from the bytes on disk | The vector is not recoverable from the data files. Requires the pages to be rewritten - REINDEX or VACUUM FULL - and then requires the backups, WAL and replicas to age out. This is what an erasure request means. | Most confusion about deletion in vector databases is two of these being conflated. A system can be entirely correct at the first meaning and entirely non-compliant at the third, and no query you can write will show you the difference. What DELETE actually does Postgres is a multi-version store. DELETE marks the heap tuple with the deleting transaction id; the tuple stays where it is. Any transaction that started before yours can still see it - that is what makes the delete transactional - and it is removed only when no transaction can still need it and vacuum gets to the page. The index entry stays too, and this is the part specific to vectors: an HNSW graph node cannot simply be removed, because other nodes point at it and the graph would lose connectivity. So the entry remains in the graph and continues to be traversed. Queries do not return it, because Postgres checks the heap tuple’s visibility after the index has produced the candidate - but the traversal cost was already paid. The consequence is a form of decay nobody warns you about: Index contains 1,000,000 nodes. You delete 200,000 rows and do not vacuum. Queries still ask for LIMIT 10 with hnsw.ef_search = 40. The scan examines 40 candidates. About 20% of them are deleted rows, discarded after the heap visibility check. Expected survivors: 40 × 0.8 = 32, so ten results still come back - but from a candidate pool of 32 rather than 40, which is the recall of ef_search = 32. Delete 90% and never vacuum, and ef_search = 40 leaves you an effective pool of 4 for a top-10 query: the index cannot return ten rows at all. Which is the same arithmetic as the post-filter cliff in filtering and vector search in one query, with dead tuples playing the part of the filter. A vector index over a table with heavy churn and lazy vacuuming degrades in exactly this way, and it looks like the model getting worse. -- Watch it. SELECT relname, n_live_tup, n_dead_tup, round(100.0 * n_dead_tup / nullif(n_live_tup + n_dead_tup, 0), 1) AS dead_pct, last_vacuum, last_autovacuum FROM pg_stat_user_tables WHERE relname = 'chunk_embeddings'; What VACUUM does to the graph VACUUM removes dead tuples from the heap and asks each index to remove its entries for them. pgvector’s HNSW implementation handles this: it removes the deleted elements and repairs the graph by relinking their neighbours, so connectivity is preserved. VACUUM (VERBOSE, ANALYZE) chunk_embeddings; Two things to know about relying on autovacuum for this. It triggers on a fraction of the table changing - by default around twenty per cent plus a threshold - which for a large vector table means a great many dead entries before it fires. And vacuuming a large HNSW index is not cheap, because repairing the graph is real work. For a table with concentrated deletions, tune the table rather than the cluster: ALTER TABLE chunk_embeddings SET ( autovacuum_vacuum_scale_factor = 0.02, -- 2% instead of 20% autovacuum_vacuum_threshold = 1000, autovacuum_vacuum_cost_delay = 0 -- do not throttle on this table ); After vacuum, the index no longer contains the deleted vectors as reachable nodes and the recall arithmetic above returns to normal. The space is returned to the free space map for reuse - not to the operating system, and this is where the third meaning of deleted starts to matter. Getting the bytes off disk VACUUM marks space reusable within the same file. The bytes of the deleted vector remain in that file until something writes over them, which may be soon, or may be never for a table that is not growing. If the requirement is that the data is gone, you need the pages rewritten: -- Rewrites the index into new files. Does not block writes. REINDEX INDEX CONCURRENTLY chunk_embeddings_hnsw; -- Rewrites the table too. Takes ACCESS EXCLUSIVE - the table is -- unavailable for the duration - and needs free disk equal to the -- table size. On a 300 GB vector table, plan it, do not run it. VACUUM FULL chunk_embeddings; REINDEX INDEX CONCURRENTLY is the practical one: it builds a new index and swaps it, which for an HNSW index means paying the full build cost from the index tuning page - hours, at scale. That is the real cost of making a deletion reach the index files, and it is why erasure requests are batched into a scheduled job rather than serviced individually. And then, unavoidably: the WAL still contains the old page images until it is recycled; streaming replicas hold their own copies until they replay the same operations; and your backups contain the row for the whole of their retention period. None of those are addressable by any statement you can run. The correct response is to document the retention windows and state that erasure completes when the last one expires, which is what supervisory guidance generally expects - not to claim an immediacy the storage layer cannot deliver. Tombstones in other engines Postgres is unusually transparent here. Most dedicated vector databases implement deletion as a tombstone: a bit set in a deleted-mask alongside the index, checked at query time to filter results out of the candidate set. The vector itself remains in the graph or the inverted list until a compaction or segment merge rewrites it. That design is a reasonable engineering choice - it makes deletion O(1) - and it has three consequences worth stating plainly, whichever engine you use: - A tombstoned vector still costs you. It occupies a node, is traversed, and consumes candidate slots. Deletion-heavy workloads degrade until compaction. - “Deleted” in the API is the first meaning only. The vector is filtered from results. It is on disk. Any statement to a customer about erasure needs to be about the compaction schedule, not about the delete call. - You must find out how compaction is triggered - by time, by tombstone ratio, or only by an explicit operation - because that schedule is your actual erasure latency. If the documentation does not say, that is the question to ask before signing anything with a deletion commitment in it. Proving it, and what you cannot prove What you can demonstrate with a query, in increasing strength: -- 1. The row is gone from the table. SELECT count() FROM chunk_embeddings WHERE chunk_id = $1; -- expect 0 -- 2. Nothing derived from the document survives anywhere. SELECT 'chunks' AS t, count() FROM chunks WHERE version_id IN ( SELECT id FROM document_versions WHERE document_id = $doc) UNION ALL SELECT 'embeddings', count() FROM chunk_embeddings e JOIN chunks c ON c.id = e.chunk_id WHERE c.version_id IN ( SELECT id FROM document_versions WHERE document_id = $doc) UNION ALL SELECT 'retrieval_log', count() FROM run_retrievals WHERE document_id = $doc; -- audit rows: see below -- 3. The index no longer returns it, tested at maximum effort: -- use the deleted row's own vector as the probe, which is the -- hardest possible case for the index to hide it. SET LOCAL hnsw.ef_search = 1000; SELECT chunk_id FROM chunk_embeddings ORDER BY embedding $deleted_vector LIMIT 100; -- expect absent -- 4. The index has no dead entries left. SELECT n_dead_tup FROM pg_stat_user_tables WHERE relname = 'chunk_embeddings'; -- expect 0 Test 3 is the good one, and it is worth putting in a test suite: it asks the index the question it is best at answering and requires the answer to be nothing. What you cannot prove with a query: that the bytes are not in a backup, a WAL segment, a replica, a snapshot, or a filesystem block that has not been overwritten. That is a documentation and process claim, backed by retention policies, not a technical one. Write it down as such. The third query above touches run_retrievals , which is an append-only audit table. Deleting from it to satisfy an erasure request destroys the audit trail; keeping it intact retains a reference to the document. The resolution - encrypt the erasable content under a per-subject key and destroy the key, keeping the immutable identifiers - is in an append-only schema for prompts, runs and outputs. Decide this before an erasure request arrives, not after. A deletion procedure that holds up - Soft delete first, synchronously. Set documents.deleted_at in the request. Because the retrieval query joins todocuments and filters on it, the content disappears from every user-facing result within one transaction. That is the part the user experiences and it should be immediate. - Enqueue the hard delete. A durable job, not an in-process task, so it survives a restart. Record the request time - you will need it to demonstrate the interval. - Hard delete in batches. DELETE FROM chunks WHERE version_id = ANY($1) - cascades to chunk_embeddings , a few thousand rows per transaction, checking replication lag between batches as in migrations on a table with 50 million vectors. - Vacuum, explicitly. Do not wait for autovacuum on a deletion you have promised to perform. - Delete the objects. The source file in object storage, and any derived artefacts under the derived/ prefix. Remember that a versioned buc