Semantic caching: bounded by the cost of deciding a hit

Why is reusing a cached result for a different query bounded by the cost of deciding a hit?

Semantic caching attacks the collapse of λ_eff head-on: let one cached entry serve queries that are not identical to the one that created it. For example, a cached result for "all views in October" can answer "views on 5 October". That requires a subsumption test: is the new query Q_new contained in the cached query Q_cached (written Q_new ⊑ Q_cached)? And the requirement cannot be fully met.

Query containment is NP-complete for conjunctive queries (the Chandra–Merlin result), harder still once inequalities enter, and undecidable in general once you allow negation or recursion. There is no exact test at any price. So every implementation restricts itself to a decidable syntactic fragment and is sound but incomplete: it never reuses an entry wrongly, and it will refuse some reuses that would have been legal. This is the "use a sound approximation" principle at its purest, because here the intractability is proved, not merely expensive.

In practice the test splits into three checks, each with its own limit.

Join-graph equivalence. The cached fragment's relations and join conditions must equal, or be a subset of, those of the new query. Subgraph matching is expensive, so implementations canonicalize and match exactly instead, which throws away most of the legal reuse at once.

Predicate subsumption. The cached predicate must be implied by the new one. This is decidable and cheap for conjunctions of range constraints on the same columns (interval containment: day BETWEEN 5 AND 5 lies inside day BETWEEN 1 AND 31). It is hard as soon as disjunctions (OR), functions or cross-column predicates appear.

Rollup-ability. The new query's grouping must be derivable from the cached one by coarsening (for example daily totals rolled up to monthly), and the aggregate must be re-aggregatable. SUM of SUMs: yes. AVG of AVGs: no (it weights groups of different sizes wrongly). Exact COUNT DISTINCT: no, unless a sketch was stored.

Look at the third check. It is the same algebraic property that decided incremental maintainability for views, doing completely different work. One property, two mechanisms: the algebra decides both whether you can maintain an entry and whether you can reuse it. It is the best argument for asking about the algebra first for any declared derivation, before storage, refresh schedule or indexing. It also shows why sketches and combiners (map-side partial aggregation) are the same idea in three places.

Two failure modes

Partial hits can cost more than misses. When the new query overlaps the cached region without being contained in it, the design serves the intersection from cache and computes a remainder query for the difference. But the remainder carries an anti-predicate, "the part not already cached", which indexes typically cannot serve. One range scan becomes a scan of the complement, sometimes two. The cost did not vanish; it relocated into the remainder, and it can exceed the cost of the original query.

The cache gets worse as it gets bigger. An exact-match result cache is an O(1) hash lookup. A semantic cache costs O(entries) subsumption tests unless the regions are themselves indexed, and the test runs on the critical path, inside the optimizer, for every query. So lookup cost grows with cache size. It is the only mechanism here with an anti-scaling property. This leads to a rule to carry with you:

Together these two failure modes explain why semantic caching in production is confined to curated MV rewriting over a small candidate set, with optimizers explicitly limiting how many views they will consider. The mechanism is limited not by its achievable hit rate but by the cost of deciding a hit. Repeated overlapping queries also fragment the cached space into many small regions that must be merged. Choosing which regions to keep is shaped like set cover (pick the fewest sets that cover everything), which is NP-hard, hence solved greedily. That is a second use of the sound-approximation principle inside the same mechanism.

In one sentence: subsumption is NP-complete at best and undecidable in general, so every semantic cache is sound and incomplete; partial hits can cost more than misses; and the binding constraint is the cost of deciding a hit, which grows with the cache.