A Program Optimization for Automatic Database Result Caching

Abstract

📜 Abstract

Most popular Web applications rely on persistent databases based on languages like SQL for declarative specification of data models and the operations that read and modify them. As applications scale up in user base, they often face challenges responding quickly enough to the high volume of requests. A common aid is caching of database results in the application’s memory space, taking advantage of program-specific knowledge of which caching schemes are sound and useful, embodied in handwritten modifications that make the program less maintainable. These modifications also require nontrivial reasoning about the read-write dependencies across operations. In this paper, we present a compiler optimization that automatically adds sound SQL caching to Web applications coded in the Ur/Web domain-specific functional language, with no modifications required to source code. We use a custom cache implementation that supports concurrent operations without compromising the transactional semantics of the database abstraction. Through experiments with microbenchmarks and production Ur/Web applications, we show that our optimization in many cases enables an easy doubling or more of an application’s throughput, requiring nothing more than passing an extra command-line flag to the compiler.

Description

✨ Summary

The paper presents Sqlcache, a compiler optimization that automatically adds sound caching to database-backed Ur/Web applications. Its objective is to eliminate the manual cache-management code normally required to maintain query-result caches while preserving the database abstraction’s transactional behavior.

Ur/Web represents SQL queries as parsed and type-checked abstract syntax trees rather than arbitrary strings. This gives the compiler sufficient structural information to analyze database dependencies without performing general string or pointer analysis. Sqlcache uses this representation to:

identify query-dependent computations that can be cached, including derived HTML or response text rather than only raw database rows;
use the free Ur/Web variables in a computation as cache keys;
compare every relevant query-update pair in the whole program;
formulate conditions under which an update can change a query result; and
simplify those conditions using a congruence-closure-style procedure to derive cache-invalidation recipes.

For updates, the analysis considers rows entering a query result, leaving a query result, or remaining in the result while changing in selected fields. The resulting invalidations can be precise: for example, an update may invalidate only cache entries associated with an old and new key rather than flushing an entire cache.

The runtime cache is implemented as a hash-table-backed prefix tree. Storage timestamps are associated with cached leaves, while invalidation timestamps are associated with prefix nodes. This permits invalidation in time independent of the number of cached entries, although checks and stores take time proportional to the statically fixed number of keys. When an invalidation does not specify a prefix, the implementation conservatively invalidates a larger set of entries.

Transactional behavior is maintained with transaction locks and data locks. Stores are delayed until a transaction commits successfully, preventing aborted or restarted transactions from publishing invalid results. The design also handles concurrent checks and stores, including a race in which multiple transactions compute the same value concurrently. Runtime monitoring disables caches whose hit-to-invalidation ratios are too low, reducing overhead and lock contention for workloads where caching is ineffective.

Sqlcache initially identifies individual query computations, then attempts to cache larger enclosing expressions. This allows it to reuse complete response fragments or pages when their effects are limited to database reads and response output. The implementation supports caching output-writing effects, but conservatively avoids expressions with other effects, including database updates.

The analysis supports a substantial subset of SQL, including joins, unions, nested queries in FROM, grouping, aggregation, ordering, limits, and offsets through conservative approximations. Cascading triggers and several advanced query constructs are not modeled precisely, which can prevent caching or cause unnecessary invalidation.

Experiments compare the compiler-generated cache with an alternative called Dyncache, which caches raw query results and invalidates entries at table granularity but does not provide Sqlcache’s fine-grained invalidation or caching of derived computations. On the reported TechEmpower workloads, Sqlcache produced speedups ranging from roughly fourfold to more than eightfold for several read-oriented tests, and more than fivefold for the Fortunes benchmark. In the write-heavy data-updates test, runtime monitoring deactivated ineffective caches, leaving performance close to the baseline.

On the Dinners production application, Sqlcache improved throughput by approximately 30× over the baseline, while Dyncache produced a much smaller improvement. On the Course Management application, Sqlcache achieved about a twofold advantage at higher concurrency and retained a substantial lead under moderate write loads. These results support the paper’s central claim that compiler-inferred caching can provide large performance improvements without source-code changes or programmer-written invalidation logic.

The implementation is sound only for a single application server; distributed cache coherence is left for future work. Compile-time analysis can also become expensive for large applications, and unsupported SQL features, time-dependent queries, and side effects limit cache coverage. The work’s main technical significance is the combination of static query/update dependency analysis, automatically generated invalidation, response-level caching, and concurrency control that preserves transactional semantics.

The paper is cited as an example of language-assisted and compiler-based database caching in later work. Incremental Relational Lenses distinguishes its incremental recomputation approach from Sqlcache, noting that Sqlcache caches query results and derived data but generally recomputes results from scratch after invalidation. (researchgate.net) A later system and thesis on Cachematic discusses SQLCache as a closely related design and uses it as part of the context for automatic invalidation in application-level caching. (odr.chalmers.se) A survey of application-level caching likewise identifies Sqlcache as a compiler optimization that generates caching logic for database queries, while noting its specific implementation in Ur/Web. (researchgate.net)

The implementation was integrated into the open-source Ur/Web distribution, and contemporary reporting described its use as a compiler/runtime modification that could be enabled by recompiling applications rather than changing application source code. (adam.chlipala.net) The available evidence supports influence primarily as a research reference and implemented Ur/Web technology; it does not establish broad adoption as a general-purpose industry caching system.