Incremental view maintenance
Which views can be updated from the change alone, and why does it come down to an inverse?
The question
Given a view V = f(R) and a change ΔR to the input, when can the new view V′ be computed from V and ΔR alone, in time proportional to ΔR? This is called incremental view maintenance (IVM). The question is algebraic.
Selection, projection, join
-
Selection and projection (
WHERE, choosing columns) are trivially incremental, because they distribute over union: the result for the new rows can be computed on the new rows alone. -
Inner join is incremental, but with a cost you must see to respect:
Δ(R ⋈ S) = ΔR ⋈ S + R ⋈ ΔS + ΔR ⋈ ΔS
The change is small, but the operands it joins against are not. To maintain a join incrementally, you must keep both full relations as indexed state. Incremental compute is bought with full storage: this is the space-versus-time trade-off in its sharpest form.
Aggregation: the load-bearing distinction
Aggregation splits on algebra.
| Aggregate | Structure | Cost under a delete |
|---|---|---|
COUNT, SUM | group (has an inverse) | O(1): subtract |
AVG | group (kept as sum + count) | O(1) |
MIN, MAX | semigroup only (no inverse) | O(n): must re-scan the group |
DISTINCT, quantiles (median, p99) | needs the full multiset | O(state), or approximate |
Plain words: a group is a set of values with an operation that can be undone. Addition can be undone by subtraction, so SUM can absorb a deleted row: new_sum = old_sum − deleted_value. A semigroup has the operation but no undo. MAX can absorb a new row (max(old_max, new)), but if you delete the current maximum, nothing in the old value tells you the second largest.
This is why sketches appear here. A sketch is a small, approximate summary structure (for example a quantile sketch that estimates the median). Many sketches are mergeable, which restores an algebraic property. Trading exactness for an algebraic property is often the only way to make a view maintainable at all.
Recursion and iteration
Recursion and iteration break the naive approach: a single edge deletion in a graph can invalidate an unbounded set of derived paths. A line of research called differential dataflow resolves this. It stamps each change with a timestamp in a partial order and maintains the differences between versions, so recursive fixpoints (computations that repeat until nothing changes) become incrementally maintainable. It is genuine theory, and it works. It is also, honestly, a research-grade capability that most stacks do not have; claiming that your materialized views are "differentially maintained" is usually marketing.
The honest state of practice: IVM is solved for selection, projection, inner join and group-additive aggregates. It is partially solved for outer joins and non-invertible aggregates. It is largely unavailable for recursion outside specialized systems.
In one line: a view is cheaply incremental exactly when its aggregate has an inverse and you can afford to store its join inputs.