Research-backed calculator guide

Vector Tombstones and Compaction Cost: What Deletes Leave Behind

Estimate the storage, rewrite, and operational cost of vector tombstones instead of treating a logical delete as immediate physical cleanup.

What a vector tombstone costs

A tombstone is not the deleted embedding itself. It is a record that tells reads, merges, or index maintenance that a prior version must no longer be returned. The old embedding may still occupy bytes in an immutable segment, slab, binlog, commit log, or snapshot until a later rewrite can safely discard it. Pinecone’s architecture is one example: writes land in immutable slabs, and background compaction merges slabs while applying tombstones to keep the latest state.^[1]

The same lifecycle appears under different names. Milvus describes compaction as merging segments and cleaning logically deleted data, while its documentation notes that asynchronous compaction can be delayed when a retention window must preserve time-travel behavior. Qdrant documents a vacuum optimizer that marks records deleted first and later permanently removes them while reorganizing storage. Weaviate describes background merging of LSM segments and removal of outdated object versions, while its vector index has a different storage algorithm from its object and inverted stores. These are useful mechanisms to compare, not interchangeable pricing promises.

The economic mistake is to multiply the number of delete API calls by a guessed per-delete price. A delete call may be cheap while the deferred cleanup is expensive. The cost driver is usually the amount of data that remains live in old files, the fraction rewritten during cleanup, the number of replicas or copies, and the resources needed to do the rewrite without violating query or ingestion SLOs.

There is also a compliance distinction. A record being excluded from ordinary search results is not the same as every physical copy being erased. Backups, replicas, logs, exports, and old index versions may follow separate retention rules. A tombstone-cost estimate is therefore not an erasure certificate. It is a capacity and operations estimate unless your provider gives a documented deletion guarantee for the relevant layer.

The four inputs to measure

Live vector footprint. Start with the bytes for a vector, metadata, and index overhead. For a 1,536-dimensional float32 embedding, the raw numeric payload is 1,536 × 4 = 6,144 bytes, or about 6.0 KiB before metadata and index structures. The actual stored footprint can be several times that amount, depending on the ANN method, metadata, compression, WAL, replicas, and provider implementation. Measure the ratio from a representative index rather than assuming raw vector bytes equal billable bytes.

Delete rate. Count deletes and superseding updates separately if possible. An upsert that replaces an existing ID can create the same cleanup pressure as a delete followed by an insert. Use deletes per day or month, and distinguish one-time migrations from steady-state churn. A 30-day rolling average can hide a weekly batch, so also track the largest daily delete burst.

Cleanup lag. Measure the time between logical deletion and the point at which physical size drops, or use a provider-specific compaction metric. If a system reports approximate size, treat it as a signal rather than an invoice-grade number. Pinecone explicitly says its namespace size_bytes is approximate and that recently deleted data may remain counted until compaction rewrites the files.^[2]

Unit costs and operating limits. Record the storage price per GB-month, object-operation or request charges if they apply, compute price per hour, and any separate replica or backup multiplier. A managed service may quote none of these individually. In that case, calculate the extra capacity and compaction work as an internal TCO estimate, not as a provider invoice prediction.

A practical cost model

Let:

• D = deleted or superseded vectors per month.
• B = measured stored bytes per vector, including the vector, metadata, and index allocation.
• L = average fraction of a month that old bytes remain before physical cleanup, from 0 to 1.
• R = replica or retained-copy multiplier.
• S = storage price in dollars per GB-month.
• H = temporary headroom fraction needed while a rewrite overlaps old files.
• C = compaction compute hours per month.
• P = fully loaded compute price in dollars per hour.
• Q = any additional monthly backup, snapshot, or transfer cost attributable to this lifecycle.

The average retained deleted data is approximately:

retained_GB = D × B × L × R ÷ 1,000,000,000

The monthly storage cost of that retained data is:

retained_cost = retained_GB × S

A conservative temporary-headroom estimate is:

headroom_cost = retained_GB × H × S

And the rewrite compute estimate is:

compute_cost = C × P

So the working estimate is:

total_monthly_cost = retained_cost + headroom_cost + compute_cost + Q

This intentionally excludes the base cost of storing vectors that have not been deleted. It also excludes embedding-generation cost, query cost, network cost, and the application work required to identify records. Add those only if the decision is about the full delete workflow rather than tombstone cleanup.

Worked cost example

Assume a RAG collection with 10 million vectors. A measured sample shows that the vector, metadata, and ANN representation average 12 KiB per vector. During a normal month, 2 million IDs are deleted or replaced. The service’s effective storage rate is assumed to be $0.023 per GB-month. That is an input assumption for this example, not a vendor quote. Assume one retained copy (R = 1), an average cleanup lag of 10 days (L = 10/30 = 0.333), 25% rewrite headroom (H = 0.25), and 24 hours of compaction work at an internal fully loaded rate of $4 per hour (P = $4).

The calculation is inspectable in the table below. Decimal gigabytes are used throughout, so 1 GB means 1,000,000,000 bytes.

The result is intentionally counterintuitive: under these assumptions, storage bloat is only about $0.24 per month, while the engineering or compute time to perform cleanup dominates. Change the assumptions and the conclusion changes. At 500 million deleted or replaced vectors per month, the retained storage term scales by 250 times. If the provider bills a high-performance managed tier or keeps three replicas, the storage term also rises. If compaction runs on already-paid capacity, P may be an opportunity cost rather than a separate line item.

A second scenario is useful for capacity planning. Keep the same 12 KiB footprint and 2 million monthly deletes, but let cleanup lag reach 60 days and use three copies. The average retained bytes become 24.576 GB × 2 × 3 = 147.456 GB if a two-month retention approximation is used for a burst-oriented capacity case. At $0.023/GB-month, that is about $3.39/month before headroom. The dollar amount is still not a quote, but the 147 GB matters if the cluster has a tight disk watermark or if compaction needs to write a clean copy beside the old one.

How to reduce the cost without breaking retrieval

First, separate high-churn data from stable data. If a small fraction of the corpus receives most updates, place it in a collection, namespace, or shard whose compaction behavior can be monitored independently. Rebuilding a small hot partition is easier to schedule than rewriting a mostly static corpus.

Second, measure a delete-to-reclaim curve. Record logical delete count, physical bytes, segment count, compaction start and finish, peak disk usage, query latency, and failed or retried operations. Plot bytes against time after a known delete batch. That curve gives you an empirical L and H, which are more useful than a generic tombstone percentage.

Third, batch changes when the provider’s optimizer is designed for batch work. Qdrant’s optimizer documentation explains why reorganizing a segment can remove marked records and improve memory use, while AWS documents force-merge as a way to consolidate vector-index segments; AWS also notes that force-merge is not supported on OpenSearch Serverless collections.^[4] Do not manually force a merge just because the word “compact” sounds beneficial. Check peak disk, concurrency, recovery, and whether the operation competes with queries.

Fourth, budget for temporary duplication. A rewrite may need old files, new files, WAL or delta logs, and snapshots at the same time. Weaviate’s storage documentation illustrates this general issue for snapshot creation: transient disk use can be above the settled index size while new files are assembled. The exact behavior differs by product, but the planning principle is portable.

Fifth, treat complete replacement as a separate option. Google’s Vector Search documentation supports complete overwrite and partial updates for active indexes. For batch indexes, it says datapoint deletion is delayed until compaction and updates can temporarily increase the embedding count; streaming updates are charged at $0.45 per GB used in the documentation checked on 2026-11-02.^[3] That dated vendor price is not a universal compaction price. It is a useful example of why update mode, index type, and provider meter must be modeled explicitly.

Finally, compare cleanup with a rebuild only after adding downtime risk, dual-write or dual-index storage, validation queries, cutover traffic, and rollback capacity. A rebuild can reduce long-lived tombstone bloat while creating a short-lived capacity spike. The cheaper option is the one that meets the retrieval and deletion requirements at the lowest measured total cost, not necessarily the one with the fewest delete API calls.

For a broader workload estimate, start with the RAG, embedding and vector database cost calculator. If compaction competes with self-hosted inference, compare the capacity assumption with the Self-hosted GPU inference cost calculator. Keep provider unit assumptions in a versioned sheet and reconcile actual invoices using the AI API invoice reconciliation calculator; a vector-store estimate should not be mistaken for an invoice match.

FAQ

Does a successful delete immediately reduce vector database storage?

Usually, not necessarily. A successful delete can make an ID unavailable to queries while old bytes remain in immutable files, segments, logs, replicas, or snapshots. Pinecone’s documentation says recently deleted data can remain included in approximate namespace size until compaction rewrites the files.^[2] Google documents the same broad distinction for batch Vector Search indexes by stating that datapoint deletion is delayed until compaction.^[3] Verify the behavior and metric for your provider before assuming the delete reduced billable capacity.

Is a tombstone the same as a deleted embedding?

No. A tombstone is a deletion marker or version signal. It helps readers and compaction work decide that an older record must not win, but it may coexist with the old embedding until a safe rewrite. The retained cost therefore includes both the marker and the old representation, although the old representation is usually the larger term. The exact format depends on the database and index type.

How do I calculate vector tombstone storage bloat?

Use measured stored bytes per vector, the number of deleted or superseded IDs, the average time before physical reclamation, and the number of retained copies. A first estimate is deleted IDs × bytes per stored vector × retention fraction × replica multiplier. Add temporary rewrite headroom separately. Do not use only raw dimensions × 4 bytes unless you explicitly want a lower-bound payload estimate; metadata and ANN structures can materially increase the stored footprint.

Should I force compaction after every delete batch?

No. Frequent forced cleanup can turn a manageable background task into repeated rewrites, increase I/O, and create peak-capacity or latency problems. Use the provider’s thresholds, measure delete ratio and disk pressure, and schedule cleanup when the reclaimed capacity or query benefit exceeds the rewrite risk. AWS’s vector-index force-merge documentation shows that force-merge is a specific index operation with product limitations, not a generic command available across all vector services.^[4]

Does compaction prove that data was erased for compliance?

Not by itself. Compaction may remove a record from the active index while backups, replicas, logs, exports, or snapshots retain it. A cost model can show expected capacity release and cleanup work, but it is not a legal or compliance attestation. Use the provider’s documented deletion and retention controls, identify every copy, and preserve the evidence your policy requires.

When is a rebuild cheaper than waiting for compaction?

A rebuild becomes more attractive when delete or update churn is high, the active index is mostly obsolete, compaction repeatedly approaches a disk watermark, or the provider offers predictable batch rebuild pricing. Compare the full rebuild footprint, parallel old-and-new capacity, validation and cutover work, rollback window, and any temporary query degradation against the ongoing cost of tombstone retention and incremental compaction. Google’s complete-overwrite option is an example of an index lifecycle choice that should be evaluated separately from partial updates.^[3]

Assumptions and limitations

This article uses a vendor-neutral model. The worked example uses assumed storage and compute rates, not a vendor quote. It uses decimal gigabytes, one retained copy, a 30-day month, and a measured 12 KiB stored footprint as illustrative inputs. Replace them with your invoice units, actual replica count, compression mode, metadata size, index type, backup policy, and observed compaction interval.

The model does not infer search volume, ranking, traffic, revenue, or advertising outcomes. It does not assume that every vector service uses tombstones in the same way, and it does not promise that physical deletion happens at a particular time. Provider behavior can change with index generation, deployment mode, retention setting, or product version. Date the inputs that can change; the Google streaming-update price cited above is recorded as observed in the documentation on 2026-11-02, not as a timeless rate.^[3]

Microsoft’s Azure AI Search reference describes a search index as persistent storage for search documents and places upload, merge, delete, and query operations in the context of one index.^[5] That supports the article’s distinction between a logical document operation and the storage lifecycle beneath it; it does not establish a universal tombstone implementation or price.