PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepDB: Learn from Data, not from Queries!

Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, Carsten Binnig

arXiv:1909.00607v1cs.DB

TL;DR

Workload-driven learned DBMS components require expensive query execution for training and repeated retraining as workloads or data change. DeepDB learns a data-driven model of the database that supports multiple tasks and direct updates. The paper reports that this approach outperforms state-of-the-art techniques and generalizes better to unseen queries.

  • Problem

    Workload-driven learned DBMS components require expensive training-data collection and retraining when workloads or database contents change.

  • Method

    DeepDB learns a workload-independent data-driven model of the database that supports multiple tasks and absorbs inserts, updates, and deletes without retraining.

  • Results

    DeepDB outperforms traditional and learned state-of-the-art techniques, often by orders of magnitude, while supporting multiple tasks.

  • Takeaways & Limitations

    The same data-driven approach can support query answering, cardinality estimation, and machine-learning tasks without task-specific workload training.

  • Takeaways & Limitations

    The authors do not present data-driven models as a universal solution and identify combining them with workload-driven models as future work.

Abstract

from arXiv · show

The typical approach for learned DBMS components is to capture the behavior by running a representative set of queries and use the observations to train a machine learning model. This workload-driven approach, however, has two major downsides. First, collecting the training data can be very expensive, since all queries need to be executed on potentially large databases. Second, training data has to be recollected when the workload and the data changes. To overcome these limitations, we take a different route: we propose to learn a pure data-driven model that can be used for different tasks such as query answering or cardinality estimation. This data-driven model also supports ad-hoc queries and updates of the data without the need of full retraining when the workload or data changes. Indeed, one may now expect that this comes at a price of lower accuracy since workload-driven models can make use of more information. However, this is not the case. The results of our empirical evaluation demonstrate that our data-driven approach not only provides better accuracy than state-of-the-art learned components but also generalizes better to unseen queries.

1. INTRODUCTION

Workload-driven learned DBMS components require expensive query execution for training and must be retrained as workloads or data change. DeepDB instead learns from the data itself, supports multiple tasks and updates, and is evaluated against existing approaches.

  • Motivation: Workload-driven models collect observations by executing representative queries over a database before training learned DBMS components.The approach includes learned cost models, query optimizers, and query-processing schemes.
  • Motivation: Hundreds of thousands of query-plan runtimes may be needed for high accuracy, while training corpora often cover only limited query patterns.One cited example covers queries with at most two joins and predicates on a limited number of attributes.
  • Motivation: Training data must be recollected when workloads or databases change, otherwise model accuracy degrades on unseen conditions.MCSN, trained on three-table queries, shows rapidly increasing error on queries with four or more tables.
  • DeepDB: DeepDB learns a data-driven model of joint data distributions, capturing attribute correlations and supporting inserts, updates, and deletes without retraining.The approach is workload-independent and models characteristics of the underlying data.
  • DeepDB: Because its model is workload-independent, DeepDB supports query answering, cardinality estimation, classification, and regression from the same data representation.The paper evaluates the approach against state-of-the-art learned and non-learned workload-aware approaches.
  • Evaluation: DeepDB is presented as a data-driven approach whose evaluation compares it with state-of-the-art learned and non-learned workload-aware techniques.The paper also describes a prototype DBMS architecture and an extensive evaluation.

2. OVERVIEW AND APPLICATIONS

DeepDB augments a database with learned data-distribution models rather than replacing the original data. These models support query answering, cardinality estimation, approximate query processing, and machine-learning tasks through probabilistic query compilation.

  • Overview: DeepDB learns a data distribution that augments the database while standard SQL continues to run over the original data.The model functions similarly to an index by adding query-processing capabilities.
  • Models: Relational Sum Product Networks (RSPNs) capture joint probability distributions and extend SPNs with relational-DBMS algorithms and database-specific handling.The extensions include support for a wider application class and correct NULL-value handling.
  • Models: DeepDB creates an ensemble of RSPNs offline and reuses it at runtime for multiple tasks over the represented database.The same learned representation supports user-facing approximate query answers and machine-learning tasks.
  • Query compilation: Probabilistic query compilation translates supported database queries into operations over RSPN probabilities and expectations.This compilation mechanism is designed to support applications beyond those presented in the paper.
  • Applications: DeepDB estimates cardinalities for arbitrary queries without dedicated query-cardinality training pairs.RSPNs represent the data directly, allowing cardinality estimation for query-optimizer cost and join-order decisions.
  • Applications: DeepDB supports approximate aggregate queries with equi-joins, selection predicates, and group-by clauses.Its query compilation engine combines multiple RSPNs when joins require models for separate tables.
  • Applications: DeepDB can perform regression and classification for database columns using arbitrary sets of columns as features without further learning.These machine-learning tasks use the models already learned for the database.

3. LEARNING A DATA MODEL

DeepDB represents relational data with RSPNs, extending SPNs for updates, database-specific semantics, expectations, and relational dependencies. It builds ensembles by learning joint models when tables are correlated, while the base ensemble captures only pairwise table correlations.

  • SPNs and RSPNs: SPNs learn joint probability distributions and compute probabilities for arbitrary conditions efficiently.Sum nodes represent population clusters, product nodes represent independent variables, and leaves model individual attributes.
  • SPNs and RSPNs: RSPNs were developed because standard SPNs are difficult to update and lack required handling for NULL values, functional dependencies, and extended inference.These limitations matter for database-specific query processing and changing data.
  • RSPN extensions: RSPNs support direct updates by traversing the model and adjusting sum-node weights and leaf distributions.This update procedure accounts for inserts such as additional young European customers.
  • RSPN extensions: RSPNs represent NULL values explicitly and apply SQL three-valued logic when computing conditional probabilities and expectations.This extends SPN inference to database-specific NULL semantics.
  • RSPN extensions: For continuous attributes, RSPNs store individual values and frequencies to represent the data more accurately than generalized leaf distributions.The method switches to another representation when the number of distinct values exceeds a specified limit.
  • RSPN extensions: RSPNs can encode functional dependencies by storing mappings such as A →B instead of forcing the model to split into many small clusters.Users provide these dependencies together with the table schema.
  • RSPN extensions: RSPNs propagate probabilities and expectations through the tree to support aggregate queries such as AVG and SUM with filters.At product nodes, child expectations and probabilities are combined during inference.
  • RSPN ensembles: DeepDB chooses joint RSPNs for correlated tables and separate table models otherwise, using pairwise RDC values computed from a small random sample.For each foreign-key–primary-key relationship, the maximum pairwise RDC is compared with a threshold.

4. PROBABILISTICQUERYCOMPILATION

Probabilistic query compilation translates database queries into inference procedures over an ensemble of RSPNs. DeepDB handles exact matches, larger RSPNs, and combinations of multiple RSPNs for COUNT queries, while extending the same representations to machine-learning tasks.

  • Query compilation: DeepDB translates incoming queries into probability and expectation computations over an ensemble of RSPNs.The compilation targets applications including approximate query processing and cardinality estimation.
  • COUNT queries: COUNT queries are mapped to three cases: an exactly matching RSPN, a larger RSPN covering additional tables, or multiple RSPNs combined.The cases determine how query predicates, tuple factors, and subquery estimates are used.
  • COUNT queries: For an exact table match, a filtered COUNT is computed as N · P(C), where N is the table size and C is the filter predicate.For the CUSTOMER example, the estimate is |C| · E(1c region=’EUROPE’).
  • COUNT queries: When a larger RSPN is used, tuple factors correct duplicate joined tuples so that subset queries count original tuples rather than join multiplicities.The factors are computed for foreign-key relationships and used to normalize estimates from full outer joins.
  • COUNT queries: Multiple RSPNs are combined by estimating subqueries and scaling one result by the ratio between tuples in another RSPN and their overlap.With an empty overlap, the example combines separate Customer and Order estimates; with a nonempty overlap, foreign-key tuple factors are incorporated.
  • Machine-learning tasks: RSPNs also support regression through conditional expectations and classification through most probable explanation algorithms.Their data representation is optimized for approximate query processing and cardinality estimation while retaining generalization for these machine-learning tasks.

5. DEEPDB EXTENSIONS

DeepDB extends RSPN ensembles with confidence intervals, incremental updates, and budgeted additional RSPNs. Updates modify weights and leaf distributions without changing structure, while dependency changes require regeneration.

  • Confidence intervals: DeepDB provides confidence intervals by estimating variances for probability and expectation factors, combining them under independence, and assuming a normal final estimate.The product variance is computed recursively, enabling confidence intervals for probabilistic query results.
  • Support for updates: Incremental inserts and deletes recursively traverse RSPNs, adapting sum-node weights and leaf distributions; an update is represented as a delete followed by an insert.The procedure handles sum, product, and leaf nodes through recursive tuple propagation.
  • Support for updates: The update procedure changes weights and histogram values but not RSPN structure, so newly introduced dependencies are not represented immediately.When dependency changes are detected, affected RSPNs are regenerated, potentially in the background.
  • Additional RSPNs: The base ensemble uses single-table RSPNs or two-table RSPNs for correlated foreign-key pairs, while correlations spanning more than two tables are initially ignored.The extension adds larger RSPNs under a user-specified training-time budget.
  • Additional RSPNs: Table dependencies are measured by the maximum pairwise RDC between attributes, and high mean RDC favors grouping correlated tables into one RSPN.For example, Customer-Order-Orderline has mean RDC 0.6, exceeding the 0.46 value for State-Customer-Order.
  • Additional RSPNs: The additional-ensemble budget is defined relative to base learning cost, with B = 0 producing only the base ensemble and higher B allowing larger RSPNs.Because exact construction costs are difficult to estimate, relative cost is modeled as quadratic in columns and linear in rows.

6. EXPERIMENTAL EVALUATION

DeepDB is evaluated across cardinality estimation, approximate query processing, updates, and machine-learning tasks against learned and non-learned baselines. Across these experiments, it achieves strong accuracy, generalizes to unseen queries, supports efficient updates, and often reduces training or query latency.

  • Evaluation scope: DeepDB outperforms state-of-the-art systems for cardinality estimation and approximate query processing while also supporting updated RSPN ensembles and machine-learning tasks.The evaluation compares DeepDB with learned and non-learned approaches across multiple tasks.
  • Cardinality estimation: 1.23 vs. 1.59 median q-error: DeepDB outperforms the best competitor on JOB-light and reports a 95th-percentile q-error of 3.16 vs. 143 for MCSN.DeepDB outperforms the best competitors at every reported percentile, often by orders of magnitude.
  • Cardinality estimation: Orders-of-magnitude lower median q-errors: DeepDB is more accurate than MCSN for larger joins and generalizes to queries with four to six tables and one to five predicates.MCSN becomes less accurate for queries with fewer selection predicates, whereas DeepDB maintains stronger generalization.
  • Updates: Updated RSPN ensembles retain cardinality accuracy, while sampled updates process up to 55,000 updates per second without changing the RSPN tree structure.Experiments using random and time-based data splits found that q-error did not change significantly after updates.
  • Approximate query processing: 2.6% average relative error: DeepDB beats 15.6% for VerdictDB and 13.6% for TABLESAMPLE on Flights query 11 at 0.5% selectivity.DeepDB also has the lowest average relative error across the Flights queries.
  • Approximate query processing: 31ms maximum latency: DeepDB is faster than TABLESAMPLE and VerdictDB, whose average latencies are between one and two seconds, including queries with several groups.On SSB, DeepDB's average relative errors remain below 6% while several sample-based approaches often exceed 100%.

7. RELATED WORK

Related work spans machine-learning methods for cardinality estimation, approximate query processing, and Sum-Product Networks. DeepDB differs from prior learned cardinality approaches by learning from data rather than executed workloads and by retaining a fixed structure during updates.

  • Machine-learning approaches to single-table cardinality estimation include probabilistic graphical models, neural networks, specialized density models, and lightweight tree-based models.
  • Join cardinality estimation has progressed from simple regression models to end-to-end deep-learning approaches.
  • Prior learned cardinality models generally require workloads to be executed as training data, unlike DeepDB’s data-driven approach.
  • Sum-Product Networks support efficient inference, while DeepDB’s update process changes parameters without changing structure when new tuples are inserted.

8. CONCLUSION AND FUTURE WORK

DeepDB is presented as a general data-driven approach for learned database components. The paper concludes that it supports database and machine-learning tasks effectively while motivating future combinations with other database techniques.

  • DeepDB supports cardinality estimation, approximate query processing, and machine-learning tasks through a shared data-driven approach.
  • DeepDB outperforms traditional and learned state-of-the-art techniques, often by orders of magnitude, while supporting ML tasks with neural-network-competitive accuracy without additional training time.
  • Future work includes combining data-driven and workload-driven models and applying data-driven learning to other database internals.
Loading 1909.00607v1…