Retractions, upserts and changelog semantics
How is a revised result published, and which computations can be revised from changes alone?
If results can be revised, the output is no longer a stream of facts. It is a stream of edits, and every edit needs two things: a key and an operation. Without a key there is nothing to revise. (This is why Kavya's overwrite fix worked: the sink had a key, (depot, hour).)
There are two common ways to publish an edit:
| Method | Example for one window changing from 5 to 7 | Who holds the state? |
|---|---|---|
| Retraction pair | emit (−5) then (+7) | The consumer needs only a running total: it adds the deltas |
| Upsert (update-or-insert by key) | emit key → 7 | The consumer must look up the previous value to know what changed |
A downstream sum can read ± deltas and keep only a running total. An upsert makes the consumer look up the old value to apply the change. The total cost is the same; the party that pays is different. This is the part of "costs are conserved" that people forget: moving the cost to another party is a legitimate move, and it is usually what has happened when an interface looks suspiciously cheap.
The composability boundary: you need an inverse
Incremental revision works only for operators that have an inverse (a way to undo an input). Having an identity element and being associative is not enough.
- Sum and count form a group: every value has an inverse (to undo +5, add −5). They can be revised from deltas alone.
- Max, min, first, exact distinct count, exact percentiles do not have an inverse. To retract a value from them you must keep all the underlying values (the multiset).
This one test explains two things: which incremental view maintenance (keeping a precomputed query result up to date by processing only changes) is cheap and which silently keeps everything; and which sketches are mergeable (two sketches can be combined into one) but not decrementable (you cannot remove an item from them).
(In algebra words: a monoid has an identity and associativity. A group is a monoid in which every element also has an inverse. Revision needs a group.)