Accelerating Queries through Strategic Precomputation and View Rewriting

72 concepts52 papers1 proposal

When a user queries a database, a hidden tension unfolds between data scale and human patience. Performing complex multi-table joins, fine-grained graph traversals, or massive high-cardinality aggregations on the fly requires scanning and processing millions of records. As datasets grow, this dynamic execution model inevitably hits a latency wall.

The core insight behind view-based query optimization is simple yet powerful: shift the computational burden from query runtime to an earlier phase. By strategically precomputing intermediate results, summarizing data streams during ingestion, or even speculatively predicting user actions, database systems can trade background computation and storage for near-instantaneous query responses.


The Mechanics of View Rewriting

To benefit from precomputation without forcing users to manually alter their queries, a system must be able to automatically map a high-level query to existing precomputed structures. This process is known as view rewriting. The database engine determines if a set of precomputed materialized views contains sufficient information to answer a target query, and if so, systematically transforms the execution plan to target those views instead of the raw data.

User Query ───► [ Query Optimizer ] ───► Targets Raw Tables (Slow)
                       │
                       ▼ (Automated View Rewriting)
                 Targets Precomputed Views (Fast)

This optimization is highly effective but theoretically challenging, particularly when queries involve complex logic. For instance, Li et al. established foundational algorithms for finding maximally-contained rewritings when queries include arithmetic comparisons, ensuring correctness even when filtering ranges of data (Rewriting queries using views in the presence of arithmetic comparisons).

As data formats evolve beyond flat relational tables into hierarchical structures like JSON and XML, view rewriting becomes even more intricate. To address this, Pradic et al. demonstrated that query rewritings for nested relations can be automatically synthesized directly from logical proofs (Synthesizing Nested Relational Queries from Implicit Specifications; Synthesizing nested relational queries from implicit specifications: via model theory and via proof theory). This automated synthesis allows complex data warehouses, such as the genomics platform developed by Ji, to transparently swap out raw multi-dataset joins for optimized, pre-calculated tables under the hood (FlyMine: an integrated database for Drosophila and Anopheles genomics).

Furthermore, this paradigm extends to decentralized environments. Abdallah et al. showed that rewriting queries to utilize localized, pre-computed data summaries drastically reduces the computational and communication overhead of retrieving information across distributed peer-to-peer nodes (DL-LITER in the Light of Propositional Logic for Decentralized Data Management).


Ingestion-Time Summarization and Pre-Aggregation

Rather than relying purely on periodic offline batch processes to build views, modern architectures often perform pre-computation continuously as data flows into the system. This is particularly vital for log processing and interactive dashboards, where real-time GROUP BY operations over raw events are notoriously expensive.

Consider the challenge of tracking user sessions from raw web logs. Instead of executing massive group-by queries at analysis time, the system can compress and structure the data immediately upon arrival. As detailed by Lee et al., Twitter adopted this approach by pre-aggregating raw log events into highly compressed "session sequences" during the ingestion pipeline, turning cluster-clogging runtime groupings into rapid string matches (The Unified Logging Infrastructure for Data Analytics at Twitter).

A similar strategy applies to infrastructure monitoring dashboards. Walzthoeni et al. demonstrated that pre-processing raw workload logs into daily summaries avoids the latency spikes associated with parsing and aggregating millions of historical records on the fly (SCAS dashboard: A tool to intuitively and interactivelyanalyze Slurm cluster usage).

Raw Data Stream ──► [ Ingestion Pipeline ] ──► Pre-Aggregated Summaries ──► Low-Latency Dashboard

However, full materialization introduces a strict trade-off: it consumes significant storage and can slow down ingestion if the system tries to maintain perfectly updated views for every possible query dimension. To navigate this, Winter et al. proposed a "split maintenance" strategy (Meet Me Halfway: Split Maintenance of Continuous Views). By executing initial grouping operations immediately during ingestion and deferring expensive joins or sorting until query time, they achieved the high-velocity ingestion typical of stream processing alongside the complex analytical capabilities of traditional databases.

This balance between upfront computation and on-demand finalization is critical for maintaining fluid user experiences across interactive faceted search engines (Ranking, Aggregation, and Reachability in Faceted Search with SemFacet) and massive multidimensional linked datasets (Multi-level Visual Tours of Weather Linked Data).


Offloading Complex Structural Operations

Beyond simple aggregations, precomputation can be applied to complex structural operations like multi-table joins, graph traversals, and sequence alignments. These operations are traditionally the most resource-intensive phases of query execution.

In distributed big data systems, dynamic joins require shuffling massive amounts of data across networks to build runtime hash tables. Jiang addressed this bottleneck by introducing a pre-processing layer that executes multi-table joins before the SQL engine processes the active query, effectively decoupling join execution from the real-time query phase (An efficient Join-Engine to the SQL query based on Hive with Hbase).

Furthermore, Zhang et al. proved that strategically pre-computing intermediate join results can yield massive speedups, demonstrating that the optimal execution plan often involves a deliberate trade-off where increasing network shuffle volume during a background phase drastically simplifies the final computation stage (Fast Distributed Complex Join Processing).

This philosophy of upfront investment for long-term query performance manifests in several other domains:

  • Data Provenance: Tracking the history of data points requires traversing massive, fine-grained graphs. Sun et al. showed that extracting simplified "dependency views" from raw provenance data upfront flattens the growth curve of database accesses during subsequent process analysis (A Query Language of Data Provenance Based on Dependency View for Process Analysis).
  • Sequence Comparison: In tasks like database joins involving strings, standard pairwise comparison algorithms fail to exploit the static nature of the data pool. Goldenberg et al. demonstrated that processing individual sequences independently before a query is made unlocks significantly faster exact and approximate sequence comparisons (Does Preprocessing help in Fast Sequence Comparisons?).
  • Predictive Analytics: Akdere et al. argued that machine learning models can be treated as first-class database citizens, pre-computing and storing predictive inferences within the database structure much like traditional materialized views to provide low-latency inference at query time (The Case for Predictive Database Systems: Opportunities and Challenges).

Speculative Execution for Interactive Interfaces

The ultimate extension of the precomputation paradigm is speculative execution, where the system does not just precompute static summaries, but actively predicts what the user will do next based on real-time interaction signals.

In visual data exploration platforms, users frequently pan, zoom, or adjust sliders to find patterns. Standard query execution models cannot maintain the sub-second latencies required for a fluid user experience during these operations. To bridge this gap, the backend framework proposed by Siddiqui et al. employs speculative execution to pre-calculate potential visualization results before they are explicitly requested by the user (Fast-Forwarding to Desired Visualizations with Zenvisage).

User Hovers Over Control ──► [ UI Signal ] ──► Speculative Query Execution ──► Results Cached ──► Instant Render on Click

Taking this a step further, Spinner demonstrated that user interface signals, such as hovering a cursor over a parameter control, can be used to mask backend query latency (Speculative Execution of Similarity Queries: Real-Time Parameter Optimization through Visual Exploration). While the user is hovering, the system anticipates the impending input and pre-calculates similarity queries for adjacent parameter values. By caching these speculative results in the background, the system completely hides the processing time of complex similarity searches, rendering updates instantly the moment the user commits to a selection.

Key Foundational Work

A Framework for Using Materialized XPath Views in XML Query Processing (2004) — contributed 5 concept elements to this direction.
High-Dimensional OLAP: A Minimal Cubing Approach (2004) — contributed 2 concept elements to this direction.
Algorithms for Rewriting Aggregate Queries Using Views (2000) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_view_based_query_optimization_2f13e23d,
  title = {view-based query optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/view-based-query-optimization/rdr_2f13e23d5826471dba2543fa1416aa1a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_view_based_query_optimization_2f13e23d_v1,
  title = {view-based query optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/view-based-query-optimization/rdr_2f13e23d5826471dba2543fa1416aa1a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake