Deriving a Change Feed from Immutable Snapshots

A table is a sequence of immutable snapshots. Each snapshot is a complete description of the table’s contents, and the difference between consecutive snapshots is exactly the set of rows that appeared and disappeared. That difference is a change feed, and it can be computed from metadata alone: no comparison of full table scans, no triggers, no log of row operations maintained by the writer.

The computation is cheap at the file level and expensive at the row level, and the gap between those two is where every implementation makes its trade.

The file-level difference is free

Snapshot $S_{n-1}$ references a set of data files; $S_n$ references another. Files added in $S_n$ are those present in $S_n$ and absent from $S_{n-1}$. Files removed are the reverse. Both sets are computable by reading the two snapshots’ manifest lists and manifests, which is a metadata operation costing bytes proportional to the number of file entries, not to the data.

For an append-only table, this is the entire change feed. Every row in an added file is an insert, no row is ever deleted, and the feed is a list of files to scan. A downstream consumer that only needs new rows reads the added files and nothing else, which makes incremental consumption proportional to the size of the new data rather than to the table.

For a table with deletes or updates, the file-level difference is not sufficient. A file present in both snapshots may nonetheless have had rows deleted from it via a delete file that appears only in $S_n$. A file replaced by compaction appears as both added and removed even though no logical row changed, so a naive diff reports every row in the partition as deleted and re-inserted. The feed becomes noisy in a way that is technically correct at the file level and useless at the row level.

Row-level change requires three sources

To produce row-level changes, the implementation must combine:

1. Added data files: every row is an insert, read directly.
2. Delete files added in the new snapshot: every ordinal or key they name is a delete, applied against the data files they target.
3. Files removed in the new snapshot: rows in a removed file that were not themselves deleted by a later delete file are deletes; this is where the correctness argument gets delicate, because determining “not themselves deleted” requires knowing which delete files applied to the old snapshot’s version of that file.

The third case is the expensive one. A removed file’s rows are deletes only if they were live in $S_{n-1}$, which means the reader must apply $S_{n-1}$‘s delete files to the removed file’s contents before emitting deletes. Reading the removed file is unavoidable: the metadata knows the file existed, not which rows it contained.

This is why row-level change feeds cost roughly the same I/O as reading the changed files twice: once to determine what was there, once to determine what is there now. There is no metadata structure that records row identity, so row-level diffs are computed, not stored.

-- Conceptual diff between two snapshots. The VERSION AS OF clause is the
-- engine-specific spelling; a real implementation reads manifests rather
-- than querying both snapshots in full.
WITH old AS (SELECT * FROM sales VERSION AS OF 41),
     new AS (SELECT * FROM sales VERSION AS OF 42)
SELECT 'insert' AS op, n.* FROM new n
LEFT JOIN old o ON o.order_id = n.order_id WHERE o.order_id IS NULL
UNION ALL
SELECT 'delete' AS op, o.* FROM old o
LEFT JOIN new n ON n.order_id = o.order_id WHERE n.order_id IS NULL;

The query above is the semantic definition and a poor implementation: it reads both snapshots in full and joins them. Its cost is proportional to table size, not change size, which is precisely what the file-level diff avoids. Real implementations push the diff down to file sets and only read files that differ.

Ordering, and why timestamps are not enough

A change feed must be ordered, because a consumer applying inserts and deletes needs to know which came first when the same key appears in both. Two mechanisms are available: snapshot order, which is a total order given by version numbers, and sequence numbers attached to files, which order operations within a snapshot.

Snapshot order alone is insufficient for merge-on-read tables, because one snapshot can contain a data file added by an earlier commit and a delete file added by a later commit. Both are in the same snapshot, but their logical order matters: the delete applies to the data file, not the other way round. The sequence number records that order. A file’s sequence number is assigned at commit and never changes, so a data file added at sequence 100 and a delete file added at sequence 105 are correctly ordered even though both are visible in snapshot 42.

A feed that emits changes ordered by snapshot only, ignoring sequence numbers, will produce a stream in which a delete sometimes precedes the insert it was meant to remove. A consumer applying the stream to a mirror table ends up with rows that should have been deleted, and the error is invisible unless the mirror is reconciled against the source. This is the most common defect in incremental consumers, and it is a property of the reader rather than of the table.

The second ordering subtlety is the boundary between snapshots. A consumer that reads “changes since version 41” must be told exactly which version the feed ends at, and it must resume from that version rather than from a timestamp. Resuming by timestamp requires mapping a time to a version, and the mapping is many-to-one when commits are close together: two commits within the same millisecond cannot be distinguished by a millisecond-resolution timestamp. Version-based resumption is unambiguous and is the only safe checkpoint.

What the diff cannot report

Updates versus delete-then-insert. A row updated in place appears in the feed as a delete of the old row and an insert of the new one, unless the format records the change type. Nothing in an immutable snapshot distinguishes an update from a genuine delete followed by an unrelated insert with the same key, because both produce the same two row versions. Formats that expose a change feed with an update type do so by comparing the before and after images of the row, which requires reading both, at the same cost as the row-level diff.

Column-level changes. A snapshot diff yields whole rows. Which columns changed requires comparing the before and after values of the row, and the feed carries both images only if the implementation reads them. A feed that carries only the after image is a feed of inserts, and a consumer that treats it as an update stream will overwrite columns that did not change with nulls.

Changes that left no trace in the retained snapshots. If the table’s retention window is shorter than the consumer’s checkpoint interval, the snapshots between the checkpoint and the current version may have been expired, and the feed for that range cannot be computed. The consumer’s only recourse is a full resynchronisation. Retention is therefore a constraint on downstream consumers, not just on storage cost; the reasoning in snapshot expiry and orphan files determines how far behind a consumer may fall.

Changes to files that were compacted away. A compaction that rewrote a partition between two snapshots produces a file-level diff with no logical content. A row-level implementation must either suppress those changes by recognising that the rewrite preserved the row set, or emit them and let the consumer deduplicate by key. Suppression requires reading the rewritten files, which is the cost the compaction was meant to save; emission requires the consumer to hold state. Neither is free, and implementations differ in which they choose.

Cost model and its consequences

The feed’s cost has two regimes.

When the change is an append of new files and nothing else, the cost is proportional to the new bytes. A consumer reading a day of changes reads a day of data.

When the change includes deletes, replacements, or compaction, the cost includes reading the affected files’ contents in addition to the new bytes. A table with heavy compaction produces feeds whose cost is proportional to the compacted volume, not the logical change volume. A consumer whose checkpoint interval spans a compaction run pays for the entire rewritten partition.

The practical consequence is that change-feed consumption and compaction scheduling are coupled. Running compaction immediately after a commit that a consumer has not yet read makes the consumer’s next incremental read expensive, because the files it would have read are gone and the files that replaced them contain the whole partition. Running compaction on a delay longer than the consumer’s interval avoids this, at the cost of leaving small files in place for longer. The two jobs are optimising against each other, and the parameter that reconciles them is the consumer’s checkpoint interval.

A second consequence is that the feed’s stability depends on the retention of the files, not only of the snapshots. A consumer reading snapshot 41’s manifests needs those manifests to exist, which is why the file-retention window must exceed the consumer’s interval by a margin. A consumer that reads a snapshot whose manifests were swept fails at the planning stage, before reading any data, and the failure looks like a missing-table error rather than a retention problem.

Why this is a table-format feature at all

A database with a write-ahead log can stream its log: every change is recorded as it happens, and the consumer reads the log. A table format has no such log. Its commits record which files changed, not which rows, so the row-level feed must be reconstructed from the files.

That reconstruction is possible only because the snapshots are immutable and their metadata is complete. The feed is a derived artefact, not a stored one, and its fidelity is bounded by what the metadata records: file membership, sequence numbers, and delete sets. Anything finer, such as the before image of a row or the set of changed columns, must be read from the data files, and the cost of reading is the reason change feeds are usually implemented as a scheduled job writing a separate stream rather than as a query-time feature.

The design constraint that follows is worth stating directly: if a workload needs a reliable, low-latency, row-level feed, a table format’s snapshot diff is the wrong primitive, and a log-based capture of the source writes is the right one. The snapshot diff is best for periodic reconciliation, audit trails over long intervals, and rebuilding a downstream table where a batch of changes is acceptable. Treating it as a substitute for log capture produces a feed whose latency is the commit interval and whose cost spikes whenever maintenance runs.