Source-linked AI summary
DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views
Yanif Ahmad, Oliver Kennedy, Christoph Koch, Milos Nikolic
TL;DR
High-rate analytics needs fresh views over changing databases while retaining classical SQL for data whose relevant lifetimes vary. DBToaster recursively materializes queries and higher-order deltas, using optimized incremental maintenance and compilation; experiments report scalable refresh rates and broad query support, with limitations for some workloads and implementation settings.
Problem
High-rate, long-lived dynamic data requires fresh analytics with classical SQL rather than only window semantics.
Method
DBToaster applies the viewlet transform, recursively materializing queries and higher-order deltas, then optimizes and compiles their maintenance triggers.
Results
The approach supports nested subqueries unsupported by commercial IVM and achieves scalable refresh rates, often outperforming existing tools by multiple orders of magnitude.
Takeaways & Limitations
Higher-order IVM provides a basis for continuously fresh views over complex SQL workloads, including automated trading and ETL scenarios.
Takeaways & Limitations
Some inequality-join workloads cannot be incrementally processed below O(n^2) without specialized indexes, and the evaluated runtime is single-core and main-memory based.
Abstract
from arXiv · showhide
Applications ranging from algorithmic trading to scientific data analysis require realtime analytics based on views over databases that change at very high rates. Such views have to be kept fresh at low maintenance cost and latencies. At the same time, these views have to support classical SQL, rather than window semantics, to enable applications that combine current with aged or historical data. In this paper, we present viewlet transforms, a recursive finite differencing technique applied to queries. The viewlet transform materializes a query and a set of its higher-order deltas as views. These views support each other's incremental maintenance, leading to a reduced overall view maintenance cost. The viewlet transform of a query admits efficient evaluation, the elimination of certain expensive query operations, and aggressive parallelization. We develop viewlet transforms into a workable query execution technique, present a heuristic and cost-based optimization framework, and report on experiments with a prototype dynamic data management system that combines viewlet transforms with an optimizing compilation technique. The system supports tens of thousands of complete view refreshes a second for a wide range of queries.
1. INTRODUCTION
DBToaster addresses high-rate, long-lived data by recursively maintaining queries and their deltas, enabling efficient SQL view refreshes without restricting applications to window semantics. Its optimizer and compiler support broad query features and report substantial performance gains for dynamic analytics.
- Motivation: High-rate analytics increasingly requires fresh views over dynamic, stateful data in finance, telecommunications, science, intelligence, and other applications.Algorithmic trading is a motivating case because order-book data changes frequently while some orders remain relevant for long periods.
- Viewlet transform: Higher-order IVM recursively materializes a query, its delta queries, and higher-order deltas until the rewritten query becomes constant with respect to the database.The viewlet transform uses discrete forward differences across multiple derivation levels.
- Viewlet transform: Auxiliary delta views let DBToaster refresh views by adding precomputed deltas rather than recomputing products or joins.In the example, the fourth-order view is constant, and view values can be updated using additions from the preceding row.
- Viewlet transform: For a large SQL fragment, higher-order IVM replaces join processing with summation, because recursive deltas become structurally simpler and eventually database-independent.Inequality joins and nested aggregates are identified as exceptions requiring join processing or special treatment.
- Example: For a sales query with map-valued auxiliary views, recursively maintained deltas reduce single-tuple trigger evaluation from linear time to constant time.The auxiliary maps associate multiplicities with tuples and support indexed updates.
- System and evaluation: The system combines higher-order IVM, heuristic and cost-based materialization choices, and an optimizing compiler; experiments report advantages over existing tools and support for unsupported nested subqueries.The paper reports frequent dominance by multiple orders of magnitude and identifies current systems as unable to sustain required freshness rates on automated trading and ETL workloads.
2. RELATED WORK
The paper situates DBToaster among established approaches to view maintenance, materialization, evaluation, triggers, and stream processing. It distinguishes higher-order recursive incrementalization from these prior techniques and targets classical database semantics for dynamic workloads.
- Incremental maintenance: Prior view-management research covers set and bag relational algebra, classical first-order incremental view maintenance, aggregation, and formal maintenance semantics.The paper states that earlier work did not investigate delta queries for nested and correlated subqueries.
- Materialization and optimization: Materialization research ranges from subquery and partial-materialization methods to multiquery optimization and common-subexpression reuse.Existing approaches use representations such as AND-OR graphs, signatures, and subsumption methods to select reusable views.
- Evaluation strategies: Evaluation strategies for incremental maintenance include eager and lazy evaluation, asynchronous processing, freshness models, Datalog semi-naive evaluation, and DRed.These methods balance update and query workloads or support different view-freshness constraints.
- Triggers and active databases: Trigger and active-database systems provide reactive behavior, but manual conversion of queries into higher-order delta form is described as difficult and error-prone.The paper contrasts this manual burden with automated higher-order incrementalization.
- Data stream processing: Stream-processing systems combine shared incremental processing with approximate sublinear-space techniques, whereas the paper targets dynamic database views with classical query semantics.The related-work discussion notes limited commercial adoption of approximate techniques for workloads that exceed stream rates.
3. QUERIES AND DELTAS
The paper defines a rational-multiplicity query algebra and constructs delta queries that express how query results change under database updates. The algebra supports SQL-like operations, nested aggregates, deletions, and parameterized expressions.
- Data model: Generalized multiset relations assign rational-number multiplicities to tuples, allowing databases, updates, and aggregate results to share one representation.Deletions use negative multiplicities, while aggregate values are stored as multiplicities rather than replacing old tuples.
- Aggregates: Grouping sums place aggregate values in group multiplicities, differing from SQL by not adding a separate aggregate column.This representation also supports multiplicity-preserving projections.
- Query language: The query language includes relation atoms, singleton relations, natural join, union, selection, grouping sum-aggregates, and column renaming.Its operations generalize bag relational algebra and SQL constructs.
- Delta queries: The algebra is closed under deltas: for each query Q, delta query ∆Q expresses the result change caused by update workload ∆D.Delta rules are given compositionally for unions, sums, joins, and selections, and support bulk updates.
- Delta queries: Join deltas contain changes from either input and their interaction, as shown by the three-term delta rule for joins.For single-tuple updates, additional simplifications can produce more efficient refresh code.
- Binding patterns: Binding patterns distinguish input variables, which must be supplied as parameters, from output variables, which form the query-result schema.Correlated nested subqueries use outside variables as inputs, and delta construction adds parameters for updates.
4. THE VIEWLET TRANSFORM
The viewlet transform recursively materializes a query and its delta queries as mutually maintained views, terminating when deltas become update-dependent constants. Its execution model targets efficient, parallel refreshes, especially for single-tuple updates.
- Recursive transformation: The viewlet transform recursively treats each delta query as a query, materializing and maintaining higher-order deltas until the degree-th delta is database-independent.This termination follows from the strict reduction in query degree under delta transformation.
- Trigger construction: For every relation used by Q, the transform creates an update trigger that refreshes Q and recursively processes the corresponding delta query.Only queries with positive degree are materialized because they are incrementally maintained by trigger statements.
- Trigger construction: The resulting triggers maintain the base view and auxiliary views using one another, while reading old view versions in the required statement order.For a degree-two query, triggers update first-order views and second-order delta views.
- Single-tuple optimization: For single-tuple updates, parameter substitutions and distributivity can eliminate loops over irrelevant values and simplify trigger computation.The paper illustrates this by substituting a join variable when the trigger is nonzero only under an equality condition.
- Execution: The transform removes classical large-granularity operators from the remaining workload, leaving regular, data-parallel loops suited to compilation.The approach focuses on single-tuple insertions and deletions, avoiding relation-typed update parameters.
- Scope and optimization: The presented transform is called naive recursive IVM in experiments because many optimizations are deliberately omitted from its initial formulation.Runtime parameter valuation can also be expensive, motivating domain bounding and parameter elimination.
5. OPTIMIZING VIEWLETS
DBToaster optimizes viewlet materialization by rewriting, decomposing, factoring, and selectively materializing query expressions. Heuristics and cost estimates balance incremental maintenance against recomputation, while input-variable and nested-aggregate handling impose important constraints.
- Materialization Decisions: Heuristics and a cost model decide which expressions to materialize, avoiding views with high maintenance cost.The optimizer trades off materialization and lazy evaluation, especially when naive recursive transformation is too aggressive.
- Query Decomposition: Disconnected join graphs are decomposed into independently materialized components, reducing stored values and maintenance work.Delta application can create further disconnected components, making decomposition especially useful for compiled maintenance.
- Polynomial Expansion and Factorization: Queries are expanded into unions of conjunctive queries for decomposition, then factorized by pulling common subexpressions outside unions.The cost-based optimizer explores factorization broadly, while the heuristic optimizer applies it after materialization decisions are finalized.
- Input Variables: Materialized expressions avoid input variables by pulling their dependent operators outward, although cost-based plans may retain finite active-domain portions.Such retained input-variable views behave as incrementally maintained caches and are beneficial only when the active domain is small.
- Nested Aggregates and Decorrelation: Nested aggregates require decorrelation because their naive deltas may reproduce the original query and prevent termination.The resulting rewrite lowers expression degree but adds computation cost when the nested-subquery delta is nonzero; some updates may instead justify full recomputation.
- Cost Estimation: DBToaster estimates projected distinct-tuple counts to guide materialization decisions and compare alternative view sizes.The estimated domain size is defined for selected output variables and for the complete output domain.
6. EXPERIMENTAL RESULTS
The experiments evaluate DBToaster across trading and decision-support workloads, SQL query types, commercial-system comparisons, and scaling scenarios. Results show strong performance across many joins and nested aggregates, with specific limits for inequality-correlated queries and startup costs for Q22.
- Commercial-system comparison: Figure 7 compares DBToaster with commercial DBMS and stream systems using refreshes per second, while DBX and SPY perform full refreshes on each update.SPY lacks incremental view maintenance, and DBX cannot incrementally handle more than half of the tested queries because of unsupported SQL features.
- Equijoins: For equijoins, DBToaster is comparable to first-order IVM on Q11 and improves BSV by representing its materialized delta as a single aggregate value.SSB4 has maximum join width 6, while BSV is a two-way self-join; the BSV update cost becomes constant.
- Nested aggregates and inequijoins: PSP decomposes through polynomial expansion into four parts, whereas MST is a worst case that cannot be incrementally processed below O(n2) without specialized indexes.PSP yields two constant-time and two independent linear-time components; MST compares nested aggregates through inequalities.
- Working-state scalability: With the exception of Q22, performance stays roughly constant as stream length grows across scaling factors from 0.5 to 10.Q22’s cost is concentrated in the first 10% of each stream while Customer is inserted; afterward it returns to 35000 tuples per second regardless of scale.
7. CONCLUSION
The paper concludes that DBToaster makes recursive higher-order IVM viable through aggressive delta simplification and diverse materialization strategies. Its compiler and optimizer support scalable refresh rates across a broad class of SQL queries, including nested subqueries unsupported by current IVM mechanisms.
- DBToaster combines aggressive recursive-delta simplification with multiple materialization strategies to make higher-order IVM viable.
- The compilation method is effective for many select-project-join-aggregate queries, including nested subqueries unsupported by current IVM mechanisms.
- The methods provide scalable view refresh rates, often orders of magnitude above today’s tools, supporting the paper’s dynamic data management vision.
Appendix A. QUERIES
The appendix lists the SQL workloads used in the experiments, covering trading queries, TPC-H-style joins and aggregates, nested subqueries, inequality joins, and self-joins.
- Trading queries: Trading workloads include broker-level joins and aggregates over Bids and Asks, including price-volume computations and inequality-based conditions.
- Join patterns: The query set covers linear joins, star joins, self-joins, and inequality joins with grouped aggregate outputs.
- TPC-H-style queries: The appendix includes TPC-H-style queries over Customer, Orders, Lineitem, Partsupp, Supplier, Nation, and Part relations.
- Nested aggregates: Several queries use nested aggregates, including correlated and uncorrelated subqueries compared through equality or inequality predicates.