Changelogs and table-stream duality

Why is a stateful operator's output a changelog, and what does retraction demand downstream?

Changelog streams and table-stream duality

The duality claim: a table is the integral of a changelog, and a changelog is the derivative of a table. In plain words:

• A changelog is a stream of changes: "set restaurant 5's count to 41", "delete restaurant 9".
• Apply all the changes in order and you get a table: the latest value for each key.
• Compare two versions of a table and you get the changelog.

Mechanically this is exact. Keyed state is a compacted log (key → latest value), and a compacted log materializes to exactly that table. A compacted log is a log where, for each key, only the newest entry is kept (old ones are removed by background compaction, like in an LSM-tree). Log compaction in a message system and keyed state in a stream job are the same structure with different owners.

Three consequences that are usually treated as separate topics

1. A stateful operator's natural output is a changelog, not an append stream. Any aggregate over incomplete input must be revisable. The count for restaurant 5 changes with every order. So upserts (insert-or-update by key) and retractions (take-back messages) are not an optional mode. They are what the operator has to say.

2. Every downstream operator must handle retraction. That requires each aggregate to be either invertible or recomputable.

• COUNT and SUM retract trivially: subtract.
• MAX and exact distinct count do not: to retract a value you must keep the multiset of contributing values (retractions need an inverse). For a stream job that is a state cost: retract-capable MAX holds O(window contents) where append-only MAX holds one number.

This is where an innocent-looking MAX() in a continuous query becomes an O(window) state operator. (This is Ana's huge state.)

3. Sinks must support upsert-by-key plus delete markers, or the changelog cannot be materialized at all. A sink that only appends turns a changelog into a duplicate-laden mess. (This is Ana's two rows per restaurant.)

The honest boundary

The duality is exact for keyed, deterministic, last-write-wins data. It leaks for unkeyed append-only facts (no key means no compaction, so no table) and for aggregates whose result depends on arrival order.