The most expensive query is often the one you already answered.

That sounds backwards until the database changes.

You have a dashboard, an alert, a rule engine, a fraud score, a ranking table, a feature store, a recommendation edge list. The thing is not a one-shot query. It is a standing question. Every insert, delete, status flip, or dimension-table edit asks:

what changed in the answer?

Refreshing the whole answer is honest, but sometimes absurd. If one order moves from pending to paid, recomputing a million-row revenue cube is a dramatic way to add three numbers.

The old database phrase is incremental view maintenance. The better mental model is:

the query has a derivative

When the base tables move by \(\Delta R\), the view moves by \(\Delta V\). The interesting engineering object is not only \(V\). It is the program that maps base-table changes to view changes.

A Query With Four Doors

Here is a deliberately ordinary analytic view:

SELECT users.region, products.category, SUM(items.amount) AS revenue
FROM users
JOIN orders   ON orders.user_id = users.id
JOIN items    ON items.order_id = orders.id
JOIN products ON products.sku = items.sku
WHERE orders.paid
GROUP BY users.region, products.category;

There are four kinds of base-table changes:

new item row
order status flips between pending and paid
product moves category
user moves region

They are not equally expensive.

For a new item, the delta is tiny:

look up its order
if paid, look up user and product
add amount to one view cell

For a product-category edit, the delta can be wide. Every paid historical item with that SKU moves from the old category cell to the new category cell. A first-order delta path still has to walk the fanout.

That is where auxiliary views appear. They are not a philosophical flourish. They are stored derivatives:

order -> revenue by category
sku   -> paid revenue by region
user  -> paid revenue by category

Now a status flip can move one order’s category ledger. A product recategorized from tools to ai can move one SKU’s regional ledger. A user-region edit can move one user’s category ledger. The base query and its deltas are both materialized.

The bill is also obvious: more memory, more writes, more invariants.

The Lineage Is Older Than The Branding

Rule engines learned this early. Forgy’s Rete algorithm was built for the many-pattern/many-object match problem in production systems, where pattern matching could dominate execution time.1 Rete compiles patterns into a network and stores partial matches so new working-memory changes can be propagated through the network instead of matching everything against everything again.1

Databases developed the same reflex in their own language. Gupta and Mumick’s survey framed materialized views as stored query results that must be kept consistent with changing base relations, and organized the view-maintenance problem around what information is available and how changes are propagated.2

The modern systems lineage pushes the idea harder. DBToaster’s “viewlet transform” materializes a query and higher-order deltas of the query, so those delta views help maintain one another.3 Differential dataflow generalizes incremental computation to changing, possibly iterative dataflows: collections are represented through differences, and output changes remain sparse when input changes are sparse.4

The recurring move is the same:

do not store only the answer
store enough nearby answers that change has a short path

The Lab

The browser lab below uses the revenue query above. It generates a deterministic synthetic database, applies a batch of base-table changes, recomputes the exact answer after the batch, and compares three maintenance budgets:

full refresh       scan the joined view again
first-order delta  walk affected base rows and join them through indexes
auxiliary delta    use maintained derivative views to shorten fanout

The default case has 180 users, 691 orders, 2,899 items, and 70 products. With an 18-change mixed batch:

full refresh probes       8,697
first-order delta probes  2,497
auxiliary delta probes      204
auxiliary entries         3,472
touched view cells        26 / 30

The important sentence is not “204 is smaller than 8,697.” The important sentence is “204 was purchased by keeping 3,472 auxiliary entries correct.”

Full refresh First-order delta Auxiliary delta Base table

Deterministic browser experiment. Probe counts are a transparent work model, not a database benchmark: they count indexed lookups, affected-row fanout, and aggregate-cell updates needed to keep the materialized view exact after a batch of base-table changes.

Try three moves.

First, set Change mix to sku category edits and raise SKU skew. Hot SKUs make first-order maintenance walk many historical item rows. The auxiliary sku -> paid revenue by region view turns that into a handful of regional moves. With 20 SKU edits and 80% skew in the default database, the lab reports about 4,994 first-order probes versus 242 auxiliary probes.

Second, set Change mix to new items. The auxiliary path loses some of its drama, because an item insert is already local. It still has to update the main view and the auxiliary ledgers. Incrementality is not one trick; it is a menu of maintenance obligations.

Third, push Batch changes toward 80. The batch-sweep panel shows the shape of the trade. Full refresh is almost flat because it pays for the whole current database once. Delta paths grow with the amount of change. If the batch becomes large enough, or if most rows churn every cycle, the Rete caveat returns: remembering state helps when the set of objects changes relatively slowly.1

The Derivative Of A Join

For a two-way join, the delta identity is already enough to explain the flavor:

\[V = R \bowtie S\]

If both sides change:

\[\Delta V = (\Delta R \bowtie S) \cup (R \bowtie \Delta S) \cup (\Delta R \bowtie \Delta S).\]

For aggregates, the signs matter. Inserts add. Deletes subtract. Updates are often a delete plus an insert. In systems with duplicates, counts or multiplicities must be carried through carefully.

The lab’s query is a grouped sum over four relations. Its useful deltas are closer to:

item insert:
  amount -> one (region, category) cell

order status flip:
  sign * orderCategory[order_id] -> one user's region

product category edit:
  skuRegion[sku] moves from old category to new category

user region edit:
  userCategory[user_id] moves from old region to new region

Those auxiliary ledgers are partial derivatives of the query with respect to different base tables. They make some changes cheap because the expensive join work has already been condensed.

The Cost Has Three Names

Incremental systems fail when they talk about only one cost.

Refresh cost is the obvious one: how much work does it take to produce the next correct view?

Maintenance cost is the steady tax: every ordinary insert now updates not only the main view but also whatever auxiliary views might help some future change.

State cost is the memory and correctness burden: indexes, arrangements, partial matches, materialized deltas, compaction, recovery, invalidation, and schema evolution.

Naiad’s timely dataflow paper is useful here because it puts iteration, streaming, and interactive queries into the same systems frame: users want low-latency answers while updates arrive and subcomputations iterate.5 Differential dataflow’s contribution is not merely “cache more.” It is a way to organize differences at logical times so iterative computations can reuse prior work without pretending there is only one current version.4

That sophistication is why the toy lab should not be mistaken for a database. It is a pocket model of the accounting question:

which partial answers are worth keeping fresh?

When Not To Do This

Incremental maintenance is a bet on locality of change.

It is a bad bet when:

most rows change every refresh
the query shape changes constantly
the auxiliary state is larger than the saved work
the update path is harder to make correct than recomputation
late or out-of-order data changes the semantics
the system cannot recover auxiliary state after failure

It is also easy to hide a product decision inside the word “fresh.” Does the dashboard need transactionally current answers? Is a few seconds of lag okay? Can errors be corrected later with retractions? Is the view read often enough to justify eager maintenance?

Lazy maintenance, eager maintenance, micro-batch refresh, and full recomputation are not moral categories. They are contracts about staleness, cost, and operational risk.

The Small Useful Habit

When someone proposes a materialized view, I now ask for its delta plan.

Not just:

what is the query?

but:

what base changes can happen?
what is the fanout of each change?
which partial joins are materialized?
how are deletes represented?
how is auxiliary state recovered?
when does full refresh become cheaper?

A cache stores an answer and hopes the world stays still.

A maintained view admits the world will move, then writes code for the motion.

  1. Charles L. Forgy, “Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem”, Artificial Intelligence 19(1):17-37, 1982. DOI: 10.1016/0004-3702(82)90020-0. ↩ ↩2 ↩3

  2. Ashish Gupta and Inderpal Singh Mumick, “Maintenance of Materialized Views: Problems, Techniques, and Applications”, IEEE Data Engineering Bulletin 18(2):3-18, 1995. ↩

  3. Yanif Ahmad, Oliver Kennedy, Christoph Koch, and Milos Nikolic, “DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views”, Proceedings of the VLDB Endowment 5(10):968-979, 2012. DOI: 10.14778/2336664.2336670. ↩

  4. Frank McSherry, Derek G. Murray, Rebecca Isaacs, and Michael Isard, “Differential Dataflow”, CIDR 2013. Microsoft Research page: Differential dataflow. ↩ ↩2

  5. Derek G. Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, and Martin Abadi, “Naiad: A Timely Dataflow System”, SOSP 2013. DOI: 10.1145/2517349.2522738. ↩