Incremental view maintenance as the endgame

The Zerodha analytics team has a SQL view that joins the last 24 hours of orders against the holdings table and groups by symbol — the "live PnL by ticker" tile that every retail trader stares at. On the warehouse it is a 90-second query and a ₹0.40 BigQuery slot bill, run every minute by a scheduled refresh, so the dashboard is up to 60 seconds stale and costs ₹17,000/month just to keep that one tile fresh. Every streaming system this curriculum has built — message logs, stream processors, Kappa, Beam, Materialize — has been climbing toward the same goal: write the view in SQL once, have the system update only the rows that changed, pay for work proportional to the change, not the size of the underlying tables. That goal has a name. It is called incremental view maintenance (IVM), and it is the endgame of unified batch and stream.

Incremental view maintenance is the algorithmic problem of keeping a SQL view's answer correct as the base tables change, doing work proportional to the change. Every modern streaming engine — Materialize, Flink SQL, RisingWave, ksqlDB, Snowflake dynamic tables, Databricks materialized views — is a different point on the IVM design space. The endgame for data engineering is when "streaming" becomes invisible: you write SQL, and the runtime decides what to recompute.

What "incremental" actually buys you

A traditional materialized view is a snapshot. You run REFRESH MATERIALIZED VIEW v and the engine recomputes the whole query — every join, every aggregation, every filter — from scratch. If the view is SELECT symbol, SUM(qty * price) FROM orders WHERE ts > now() - interval '24 hour' GROUP BY symbol over 200 million rows, refresh-from-scratch reads 200 million rows even if only 50,000 new orders arrived since the last refresh.

IVM flips this. Given the change to the inputs (50,000 new orders, maybe 100 deletes for cancellations) and the previous answer, the runtime computes the change to the output and applies it. If only 412 distinct symbols saw activity, only 412 rows in the view get updated. The cost is O(Δ) — proportional to the delta — not O(N).

Refresh cost vs IVM costA diagram comparing the cost shape of full refresh, which scales with table size, against IVM, which scales with the size of the change. Refresh cost vs IVM cost — Zerodha live-PnL view Full refresh cost = f(table size) 200M rows scanned 90 s, ₹0.40 / refresh Same cost whether 50k or 50M rows changed. IVM cost = f(change size) 50k Δ 8 ms Cost tracks the rate of change, not the table.
The same view, two cost shapes. Full refresh pays for the table; IVM pays for the change.

Why this is the endgame and not just an optimisation: most production data is only a tiny fraction "fresh" at any moment. UPI processes 100M+ transactions/day, but at any given second the change rate is 1,000–10,000 rows. A 200M-row table has a delta-to-table ratio of 0.005% per second. IVM gives you a constant factor that matches your actual workload, not your historical data.

The catch — and it is a deep catch — is that "compute the change to the output from the change to the input" is easy for some operators (filter, projection, simple sums) and famously hard for others (joins on inserts and deletes, recursive CTEs, window functions, antijoins). The history of IVM is a history of widening the set of SQL operators for which the easy form is possible.

The delta algebra: how IVM views the world

Every IVM system, from 1980s research on relational deltas to today's Materialize, rests on the same idea: represent every change as a typed pair (row, multiplicity) where multiplicity is +1 for an insert and −1 for a delete. An update is a −1 of the old row plus a +1 of the new row. A "stream of changes" is a stream of these pairs. The base table at any time is the cumulative sum of its change stream.

The operators of relational algebra — σ (filter), π (project), ⋈ (join), γ (group-by-aggregate), ∪ (union) — each get a delta rule that says: "given the current state and an incoming delta, here is the delta to emit downstream."

For filter, the rule is trivial: δ(σ_p(R)) = σ_p(δR). The delta of a filtered relation is the filter applied to the delta. New rows that pass the predicate go through; new rows that fail are dropped; deletes that pass go through as −1s.

For join, it is harder but still local: δ(R ⋈ S) = (δR ⋈ S) ∪ (R ⋈ δS) ∪ (δR ⋈ δS). When R changes by δR, the change to R ⋈ S is δR joined against the current S, plus the symmetric term, plus a quadratic correction term. To compute this, the system must keep R and S materialised as indexes (arrangements in Differential Dataflow's vocabulary, state stores in Flink's vocabulary).

For group-by-aggregate, the rule depends on whether the aggregate is invertible. SUM and COUNT are: a delete row contributes −value and −1 and the running aggregate stays correct. MIN and MAX are not invertible without auxiliary state — if you delete the current minimum, you need to know the second-smallest value, which you cannot produce without rescanning.

Delta rules for SQL operatorsA table showing the incremental rule for each SQL operator: filter, project, join, sum, count, min/max, distinct. Delta rules — what changes when the input changes Operator Delta rule State needed σ (filter) δ(σR) = σ(δR) none π (project) δ(πR) = π(δR) none (or distinct cache) ⋈ (join) δR⋈S ∪ R⋈δS ∪ δR⋈δS indexes on both inputs SUM, COUNT δagg = sum(δvalues) running total per group AVG δsum / δcount running sum + count MIN, MAX refresh on delete-of-extreme sorted multiset per group DISTINCT emit when count flips 0↔n multiplicity per row recursive CTE δfix(F) — needs DBSP / DD timestamped multiset trace window functions depends — RANK requires re-scan per-partition sorted run
Each operator has a delta rule and a state requirement. The hard cases (recursion, MIN/MAX, RANK) are why IVM took 30 years to commercialise.

Why this matrix matters for picking a streaming engine: ksqlDB, Flink SQL, Materialize, RisingWave, and Snowflake dynamic tables each support a different subset of these operators with full IVM. Materialize and DBSP-based RisingWave handle the largest set including recursion. Flink SQL handles inserts well but historically struggled with retractions on certain joins. ksqlDB is intentionally limited to the easy cases. The "what SQL works" question is exactly "which delta rules has the engine implemented."

A toy IVM engine in 60 lines of Python

To show that the algebra is implementable, here is a working IVM engine for a single SUM ... GROUP BY view over an inserts-and-deletes stream. It is the kernel of every real system.

from collections import defaultdict
from dataclasses import dataclass
from typing import Iterator

@dataclass(frozen=True)
class Change:
    row: tuple        # the row, e.g. ("RELIANCE", 100, 2480.50)
    diff: int         # +1 for insert, -1 for delete

class GroupBySumView:
    """Maintains SELECT key, SUM(value) FROM input GROUP BY key, incrementally."""
    def __init__(self, key_idx: int, value_idx: int):
        self.key_idx = key_idx
        self.value_idx = value_idx
        self.current = defaultdict(float)   # group -> running sum
        self.counts  = defaultdict(int)     # group -> row count (so we know when to drop a group)

    def feed(self, deltas: list[Change]) -> Iterator[Change]:
        """Consume input deltas, yield deltas to the output view."""
        # Stage 1: compute the change to each group's sum
        group_delta_sum = defaultdict(float)
        group_delta_cnt = defaultdict(int)
        for d in deltas:
            k = d.row[self.key_idx]
            v = d.row[self.value_idx]
            group_delta_sum[k] += d.diff * v
            group_delta_cnt[k] += d.diff

        # Stage 2: convert per-group changes into output deltas
        for k, ds in group_delta_sum.items():
            old_sum = self.current[k]
            old_cnt = self.counts[k]
            new_sum = old_sum + ds
            new_cnt = old_cnt + group_delta_cnt[k]
            if old_cnt > 0:
                yield Change((k, old_sum), -1)            # retract old answer
            if new_cnt > 0:
                yield Change((k, new_sum), +1)            # emit new answer
            if new_cnt == 0:
                self.current.pop(k, None); self.counts.pop(k, None)
            else:
                self.current[k] = new_sum;  self.counts[k] = new_cnt


# --- Demo: live PnL view over Zerodha-style order ticks ---
view = GroupBySumView(key_idx=0, value_idx=1)
batch1 = [
    Change(("RELIANCE", 248050.0), +1),    # buy 100 @ 2480.50
    Change(("TCS",       388900.0), +1),    # buy 100 @ 3889.00
    Change(("RELIANCE",  124200.0), +1),    # buy 50  @ 2484.00
]
print("Output of batch 1:")
for d in view.feed(batch1): print(" ", d)

batch2 = [
    Change(("RELIANCE", 248050.0), -1),    # cancel the first RELIANCE buy
    Change(("INFY",     156500.0), +1),    # new INFY buy
]
print("Output of batch 2:")
for d in view.feed(batch2): print(" ", d)

Output of batch 1:
  Change(row=('RELIANCE', 248050.0), diff=1)
  Change(row=('TCS', 388900.0), diff=1)
  Change(row=('RELIANCE', 248050.0), diff=-1)
  Change(row=('RELIANCE', 372250.0), diff=1)
Output of batch 2:
  Change(row=('RELIANCE', 372250.0), diff=-1)
  Change(row=('RELIANCE', 124200.0), diff=1)
  Change(row=('INFY', 156500.0), diff=1)

A walkthrough of the key lines:

Real systems extend this skeleton along three axes: (1) more operators (joins, recursion, windows), (2) durable arrangements so the state survives restarts, and (3) the timestamp/multiplicity generalisation from Differential Dataflow that lets the system process out-of-order deltas correctly.

Why IVM is the unification of batch and stream

Re-read what the toy engine does. Given a stream of changes, it produces a stream of changes that a downstream consumer can apply to keep its own view in sync. There is no notion of "batch mode" vs "streaming mode" in the engine. If you feed the entire history of a table to it as one big batch of +1s, the output is the same as if you fed the history one row at a time.

This is the property the Dataflow Model (Beam, ch.73), Materialize (ch.76), and DBSP (the formal model behind RisingWave and Feldera) all aim at: a single execution engine that treats batch as a one-time delta and stream as an ongoing one. The query the user writes is the same. The answer the engine maintains is the same. The only difference is whether the input is finite.

IVM unifies batch and streamA diagram showing one IVM engine consuming both a finite historical batch and an ongoing stream, producing an always-current view as output. Historical batch 200M rows as +1 deltas Ongoing stream 10k Δ/sec from CDC IVM engine delta algebra, one path Always-current view (B-tree)
Batch and stream are not different modes — they are different shapes of input to the same engine. The output shape is identical.

This is why the chapter is called "the endgame". When IVM works for the full SQL surface area — joins, aggregations, window functions, recursion — there is no longer a meaningful distinction between "the batch warehouse query" and "the streaming view definition". You write SQL, and the engine decides what to recompute.

Where every modern system sits on the IVM map

The 2020s have produced roughly four design schools:

  1. DBSP / Differential Dataflow line. Materialize, RisingWave, Feldera. Based on the formal calculus of Mihalache, Budiu, McSherry et al. Supports the widest SQL surface — joins, recursion, window functions, EXCEPT, EXISTS — all incrementally. Pays the price in implementation complexity.
  2. Flink SQL line. Incrementality is operator-by-operator with retraction streams. Joins are supported but have memory implications (state growth) the user must reason about. Window functions on event time are first-class.
  3. Snowflake dynamic tables / Databricks materialized views line. Closer to "incremental refresh on a schedule" than continuous IVM. The engine looks at the query and decides whether each operator can be incrementalised; if not, it falls back to full refresh. Pragmatic, less ambitious.
  4. ksqlDB / Kafka Streams line. Limited SQL, mostly stateless transformations and simple aggregations on a single stream. Incrementality is implicit because the model is so restricted.

The trajectory is clear: every vendor is racing toward the DBSP frontier because that is the SQL surface area customers actually want. The bottleneck is engineering, not algorithms — the delta calculus is published.

Common confusions

Going deeper

The DBSP calculus in one paragraph

DBSP (Database Stream Processor) by Budiu, McSherry, Tannen, et al. (2022) generalises Differential Dataflow into a typed calculus over Z-streams — streams of (record, multiplicity) pairs where multiplicity is an integer. Every relational operator is given a derivative operator in this calculus, and a chain rule lets the system compose incremental versions of arbitrary SQL queries automatically. The deep result is that for a wide class of SQL (including recursion via fixed-point operators), the chain rule produces an incremental query that is provably equivalent to running the original query on the cumulative input — and the cost is bounded by the change. The Feldera engine (open-source) is the reference implementation; RisingWave's planner consumes the same theory.

The retraction problem and why some engines emit "rolling" updates

When a SUM-over-GROUP-BY changes, the engine must emit a retraction of the old value and an emission of the new value. Downstream consumers must apply these in order — if the dashboard reads the topic at the wrong moment, it sees a (RELIANCE, 372250) retraction with no new value yet, and shows a flicker. Materialize's SUBSCRIBE and Flink's "changelog stream" mode both expose retraction explicitly. Some engines (ksqlDB, older Snowflake dynamic tables) hide retractions and emit only "the latest answer per key", which is friendlier for naive consumers but loses information about when things changed.

Cost: why IVM beats refresh only when changes are small

The crossover is when |δ| / |table| > some k. If you replace 30% of a table in one shot, IVM does as much work as full refresh — and pays the bookkeeping overhead on top. This is why batch backfills usually bypass IVM (you REFRESH the view fresh) and incremental updates use it. Flipkart's catalogue rebuild during Big Billion Days preparation is a classic case: 14× normal traffic for 4 hours, with full-table reprocessing during prep — they switch off IVM for the prep window, run a full warehouse refresh, then switch IVM back on.

Recursion: PageRank, transitive closure, shortest paths

The hard test for an IVM engine is recursive SQL — WITH RECURSIVE. PageRank is an iterative fixed-point computation: each round of the iteration is a SQL aggregation, the engine runs to convergence. Materialize and Feldera incrementalise this: when an edge is added to the graph, only the affected portion of the fixed point is recomputed. Most other engines reject recursive views entirely or full-refresh them on every input change. This is the operator that separates "streaming SQL" from "real IVM".

Where Indian companies are using this today

Razorpay's fraud team runs Materialize for the live merchant-risk score view (per ch.76). Zerodha's analytics team uses ClickHouse materialized views (a partial-IVM model — incrementally maintained but with limitations on join shape) for trade-tape aggregations. Cred's rewards team uses Snowflake dynamic tables for the daily-spend cohort view. Each picked the engine whose IVM coverage matched their query — a Razorpay-style 4-table join with windowing needs Materialize; a single-table SUM aggregation is fine on dynamic tables.

Where this leads next

References