View expansion and materialized-view rewriting

How can views push a query off the search cliff, and why are materialized views so often unused?

View expansion

View expansion is textually trivial and has a hidden hazard: it inflates the relation count. A query joining three views, each defined over five tables, becomes a 15-table join, which is past the DP cliff. A stack of views does not degrade the plan gradually. It pushes the query off a discontinuity into greedy or genetic search, where the plan becomes both worse and unstable. Views are a plan-space hazard, not a runtime hazard. The symptom is a query that is fine until one more view layer is added and then is inexplicably terrible (Dev's problem in Join order search).

Materialized-view rewriting

A materialized view (MV) is a stored result of a query. MV rewriting solves the subsumption problem: can this query be answered from this stored result? The conditions are provable but restrictive:

The MV's tables must cover the query's tables, or the missing joins must be provably lossless via enforced foreign keys.
The MV's predicate must be weaker than or equal to the query's, so the query's predicate can be applied as a residual filter on the MV's output.
The required columns must be present or derivable, including any column needed to apply the residual filter. That is why MVs that project only a few columns are often unusable.
The MV's grouping must be at equal or finer granularity, and the aggregate must be decomposable.

Example. The MV stores SUM(amount) per store_id, day. The query asks SUM(amount) per store_id, month. The MV grouping is finer (day is finer than month) and SUM rolls up (the sum of daily sums is the monthly sum), so the MV can answer it. The query asking for revenue per customer_id cannot be answered: the MV does not have that column.

Why aggregate algebra decides reusability

Condition 4 shows an important idea in an unexpected place. SUM and COUNT roll up because they are associative (a sum of sums is a sum). AVG does not roll up, unless the MV stored the sum and the count separately: the average of daily averages is not the monthly average if days have different row counts. COUNT(DISTINCT) does not roll up at all, unless the MV stored a mergeable sketch (such as HyperLogLog) rather than a number, because a customer who shopped on two days would be counted twice.

This is the identical algebraic property that makes partial aggregation work in parallel execution (each machine aggregates its share and a final step combines the results), here used for reuse rather than for parallelism. The general statement: the algebra of an aggregate decides whether precomputing it is reusable, which is a stronger requirement than whether computing it is parallelizable.

Why matchers are conservative

The general problem, query containment (is every result of query A also a result of query B?), is undecidable for full SQL and NP-complete even for conjunctive queries. So the "exact test that is too expensive is replaced by a safe approximation" idea appears in its purest form. Every engine implements a restricted, conservative matcher that proves subsumption for a bounded class of patterns, and gives up otherwise. The failure is a missed rewrite, not a wrong answer, and it is silent. That is the mechanical explanation for the most common complaint about materialized views: they exist, they are fresh, they are correct, and queries that could use them do not, because the matcher's pattern class is narrower than the user's SQL.

In one sentence: expansion inflates the relation count and can push a query off the DP cliff; MV matching is a conservative approximation of an undecidable containment test, and its usability depends on whether the aggregate's algebra permits roll-up.

Case, resolvedConstructed case · Ananya at Kiranamart

NOT IN takes 40 minutes, NOT EXISTS 2 seconds

Four pairs of queries with the same meaning ran very differently: NOT IN took 40 minutes against 2 seconds for NOT EXISTS, year(order_ts) = 2024 scanned every partition, a twice-used CTE changed speed across versions, and a fresh materialized view was never used. Where it started: Rewrites →

Ananya can now explain all four pairs.

NOT IN versus NOT EXISTS. refunds.customer_id is nullable. The planner cannot prove the subquery has no NULLs, so it may not turn NOT IN into an anti-join and runs it as a nested loop (a scan of refunds for each customer). NOT EXISTS has no NULL trap and becomes an anti-join. She rewrites the SQL, and also adds NOT NULL to the column since refunds always have a customer. The 40-minute query takes 2 seconds.
year(order_ts) = 2024. The function wraps the column, so the condition is not column op constant. Pruning and the zone maps never see it. She changes the BI tool's date filter to a half-open range (>= '2024-01-01' AND < '2025-01-01').
The CTE. The default switched from always-materialize to inline-by-default between versions. For her case (cheap producer, k = 2, different physical needs) recomputation is better, so she lets the newer default stand and writes MATERIALIZED only for the one CTE with an expensive producer.
The unused MV. The MV stores AVG(amount) per store per day. Dashboards ask for AVG(amount) per month, and AVG does not roll up. She rebuilds the MV to store SUM(amount) and COUNT(*), and the matcher can compute the monthly average as total sum divided by total count. Now it is used.