PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Unsupervised Cardinality Estimation

Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M. Hellerstein, Sanjay Krishnan, Ion Stoica

arXiv:1905.04278v2cs.DBcs.LG

TL;DR

Cardinality estimators struggle with high-dimensional relational data because existing methods can incur extreme errors and direct autoregressive likelihood evaluation is prohibitively expensive for range queries. The paper uses deep autoregressive models with progressive-sampling Monte Carlo integration and variance-reduction techniques to estimate selectivities without supervision or independence assumptions. Naru achieves high accuracy across estimator families, including single-digit worst-case error and up to 90× better tail behavior than query-driven methods.

  • Problem

    Existing cardinality estimators can incur 10^4–10^8× errors on queries spanning many attributes, while direct autoregressive evaluation is prohibitively expensive for range predicates.

  • Method

    Naru uses deep autoregressive models with progressive sampling, wildcard-skipping, and information-theoretic column orderings for unsupervised selectivity estimation.

  • Results

    Naru matches or exceeds the best estimator across evaluated settings, achieving single-digit worst-case error and up to 90× better tail behavior than query-driven methods.

  • Takeaways & Limitations

    Learning the underlying data distribution lets Naru support a broad set of future queries and remain robust to query-workload shifts without query feedback.

  • Takeaways & Limitations

    Incremental model updates for statistical changes caused by appends and updates are deferred to future work.

Abstract

from arXiv · show

Cardinality estimation has long been grounded in statistical tools for density estimation. To capture the rich multivariate distributions of relational tables, we propose the use of a new type of high-capacity statistical model: deep autoregressive models. However, direct application of these models leads to a limited estimator that is prohibitively expensive to evaluate for range or wildcard predicates. To produce a truly usable estimator, we develop a Monte Carlo integration scheme on top of autoregressive models that can efficiently handle range queries with dozens of dimensions or more. Like classical synopses, our estimator summarizes the data without supervision. Unlike previous solutions, we approximate the joint data distribution without any independence assumptions. Evaluated on real-world datasets and compared against real systems and dominant families of techniques, our estimator achieves single-digit multiplicative error at tail, an up to 90$\times$ accuracy improvement over the second best method, and is space- and runtime-efficient.

1. INTRODUCTION

Cardinality estimation remains difficult because compact summaries often lose multivariate dependencies, while exact joint distributions are costly to query. Naru uses deep autoregressive models with progressive sampling and related optimizations to provide accurate, unsupervised estimation for diverse predicates.

  • Up to 10^8× errors occur in open-source and commercial DBMSes for queries spanning many attributes.
  • Single-column summaries are cheap but compound errors when they assume independence and discard cross-column information.
  • Deep autoregressive models capture full joint distributions, but naive integration makes range-query evaluation prohibitively expensive.An 11-dimensional range query with 10^10 points would require more than 1,000 hours by naive enumeration.
  • Progressive sampling uses conditional probabilities to sample high-density regions and importance weighting to correct the resulting bias.A thousand samples suffice to accurately estimate the referenced 10^10-point query.
  • Naru approximates the full joint distribution without column-independence assumptions and supports wildcard predicates alongside practical relational encodings.
  • Naru is trained unsupervised from the data distribution and achieves worst-case single-digit multiplicative errors on challenging high-dimensional queries.The evaluation compares it with state-of-the-art unsupervised and supervised techniques.
  • The paper evaluates Naru against 8 baselines across 5 estimator families, reporting space usage of ∼1% of data size and ∼5−10ms estimation latency.

2. PROBLEM FORMULATION

The formulation treats selectivity as integration over a relation’s joint distribution, whose exact representation grows exponentially with dimensionality. Naru uses an exact product-rule factorization implemented through neural conditional models, targeting broad predicate regions without independence assumptions.

  • 2. PROBLEM FORMULATION: Selectivity is the fraction of relation tuples satisfying a predicate θ over attribute domains.
  • 2. PROBLEM FORMULATION: The joint distribution assigns each tuple frequency normalized by relation cardinality, and integrating it over a predicate yields exact selectivity.
  • 2. PROBLEM FORMULATION: For finite relations with finite empirical domains, the integration calculation is performed as summation.
  • 2.1 Approximating the Joint via Factorization: The joint contains ∏_i |A_i| entries, so its size and exact integration cost grow exponentially with the number of attributes.Real-world tables with about a dozen columns can have theoretic joint sizes of 10^20 and upwards.
  • 2.1 Approximating the Joint via Factorization: Classical one-dimensional histograms factor the joint into per-column distributions and assume attribute independence.Their materialized histograms are cheap to construct and store.
  • 2.1 Approximating the Joint via Factorization: Richer Bayesian-network and dependency-based factorizations improve accuracy but retain partial or conditional independence assumptions.Those assumptions compromise the precision of the approximated joint.
  • 2.1 Approximating the Joint via Factorization: Naru uses the product rule, an exact factorization whose conditional factors are computed on demand by a neural network rather than materialized.
  • 2.2 Problem Statement: Queries are conjunctions of single-column predicates over arbitrary column subsets, including equality, inequalities, rectangular ranges, and IN clauses.Disjunctions are supported through inclusion-exclusion, and the region formulation also supports complex predicates.

3. DEEP AUTOREGRESSIVE MODELS

Naru uses deep autoregressive models to approximate relational joint distributions and expose point and conditional densities for selectivity estimation. Information masking enforces autoregressiveness, while maximum likelihood trains the model without query supervision.

  • Model choice: Naru uses deep autoregressive models to approximate a relation’s high-dimensional joint distribution for selectivity estimation.The model produces point densities and conditional densities over relational attributes.
  • Model outputs: Autoregressive models provide point density estimates and the conditional densities required by the product rule.These outputs support both direct point-density access and conditional computation during querying.
  • Architecture and ordering: Naru can use different autoregressive architectures and assumes an attribute ordering when obtaining conditional densities.The paper discusses masked perceptrons, residual variants, Transformers, and heuristic ordering choices.
  • Autoregressive construction: Information masking makes each column’s output depend only on preceding attribute values, yielding distributions such as bP(city), bP(year|city), and bP(stars|city, year).Column-specific encoders transform values before masked networks produce the conditional distributions.
  • Training: Naru trains model outputs with maximum likelihood by minimizing cross entropy between the data distribution and the model estimate.The resulting entropy gap is monitored as a measure of estimator quality.

4. ESTIMATOR CONSTRUCTION

Estimator construction trains Naru from relation tuples, encodes heterogeneous column values, and reduces large-domain output costs through embedding reuse. The workflow is unsupervised, but updates can make the model statistically stale and incremental updating remains future work.

  • Workflow: Naru is built by reading random tuple batches, encoding attributes, and applying gradient updates to an autoregressive model.Training can occur near the data or in a remote process using a saved table snapshot.
  • Training behavior: One pass over the data can achieve high accuracy, while more passes remain beneficial until model convergence.The evaluation reports outperforming real DBMSes by 10−20× in this setting.
  • Operational boundary: Appends and updates may cause statistical staleness, and efficient incremental model updating is deferred to future work.Fine-tuning or per-partition models are described as ways to address updated data.
  • Data encoding: Naru’s preprocessing dictionary-encodes column values losslessly, preserving natural order for numerics and ordered strings.Domains may come from user annotation or a scan of the column.
  • Data encoding: Small-domain columns use one-hot encoding, whereas large-domain columns use learnable h-dimensional embeddings.The default small-domain threshold is 64, and the default embedding dimension is h = 64.
  • Output decoding: Embedding reuse replaces FC(F, |Ai|) with FC(F, h), reducing output-layer cost by a saving ratio of |Ai|/h for large domains.The optimization addresses inefficient output layers such as an id column with |Ai| = 10^4.

5. QUERYING THE ESTIMATOR

Naru computes selectivities by summing or sampling probability mass over query regions. Progressive sampling avoids the exponential cost and high variance of naive approaches by using conditional model distributions, with wildcard-skipping improving wildcard handling.

  • Query evaluation: A query selectivity is the probability mass of the cross-product region defined by per-column points, intervals, or domain subsets.Directly summing this region becomes impractical as the number of dimensions and domain sizes grow.
  • Equality predicates: Equality predicates require one forward pass, after which the relevant conditional probabilities are multiplied.The method evaluates the sequence of conditionals for the specified tuple.
  • Progressive sampling: Progressive sampling steers samples toward high-mass regions using autoregressive conditionals and corrects induced bias with importance weighting.Its stored single-column intermediates form an unbiased estimate of the desired density.
  • Range predicates: Progressive sampling estimates large range-query regions with an unbiased Monte Carlo estimator instead of enumerating their points.The algorithm samples sequentially from conditional distributions restricted to each query range and averages sampled density estimates.
  • Range predicates: Uniform sampling can require exponentially many samples in the number of correlated columns and performed worst among the evaluated baselines.In the skewed example, the expected sample count is 1/0.02^n to hit the high-mass region.
  • Wildcard predicates: Wildcard-skipping restricts wildcard columns to a MASK token that effectively marginalizes them, reducing worst-case error variance by several orders of magnitude in experiments.This avoids sampling through the full domain of each wildcard column.
  • Column ordering: Order-agnostic training is presented as a possible future optimization because preliminary experiments found no significant additional benefit over the existing optimizations.The paper instead discusses heuristic column orderings for variance reduction.

6. EVALUATION

The evaluation compares Naru with diverse estimators on challenging real-world workloads under fixed storage budgets, measuring accuracy, robustness, training cost, latency, and design sensitivity.

  • Evaluation setup: Naru is evaluated against eight baselines spanning heuristics, real DBMSes, sampling, statistical methods, and supervised deep regression.The comparison uses real datasets and fixed storage budgets where applicable.
  • Evaluation setup: The datasets contain 10K–11.6M rows, 11–100 columns, and joint spaces ranging from 10^15 to 10^190.DMV contains 11,591,877 tuples across 11 columns, while Conviva-B has 100 columns and over 10^190 joint-space entries.
  • Estimators: The evaluation includes classical DBMS histograms, independence products, multidimensional histograms, Bayesian networks, sampling, KDE, MSCN, and Naru.The baselines represent multiple modeling assumptions and supervised or unsupervised strategies.
  • Workloads: Workloads use multidimensional queries with randomly placed range and equality filters, grouped into high, medium, and low true-selectivity regimes.Queries use 5–11 non-wildcard filters; low-selectivity queries have true selectivity at most 0.5%.
  • Metrics: Accuracy is reported with multiplicative error, or Q-error, using quantiles with particular attention to the tail.Estimated and actual cardinalities are lower-bounded at 1 to avoid division by zero.

6.2 Estimation Accuracy

Naru achieves the strongest accuracy and robustness across selectivity regimes, especially for difficult low-selectivity queries, while avoiding independence assumptions. It remains best-in-class on a substantially larger joint space, though increased sampling is needed there.

  • Overall accuracy: Up to 90× better tail behavior than query-driven supervised methods, with orders-of-magnitude gains over classical approaches.The comparison covers worst-case errors on low-selectivity queries.
  • DMV: Naru outperforms MHIST by 691×, DBMS-1 by 114×, untuned MSCN by 115×, tuned MSCN by 33×, BayesNet by 70×, Sample by 47×, and KDE-superv by 21× in the DMV tail.Naru achieves the best accuracy and robustness across the selectivity spectrum.
  • Modeling assumptions: Independence-based estimators produce 10^3–10^5× tail errors, whereas Naru avoids this assumption through a more powerful model.The cited estimators include Indep, Postgres, and DBMS-1.
  • Conviva-A: Naru remains best-in-class on Conviva-A, whose substantially larger joint space causes larger errors for most competing estimators.DBMS-1, MHIST, BayesNet, and KDE-superv respectively incur 5×, 14×, 1.8×, and 2.6× worse max error than before.
  • Conviva-A: 4K progressive samples restore Naru’s worst-case error to single-digit levels on the larger joint space, whereas Naru-1000 is insufficient in all cases.The result suggests the approximated joint is sufficiently accurate, while extracting its information is the key challenge.
  • Latency: Naru’s estimation latency is around 5–10ms on a GPU, faster than scanning samples and competitive with DBMS-1.Postgres and DBMS-1 latency figures include producing an entire plan for each query.

6.3 RobustnesstoOut-of-DistributionQueries

Naru is evaluated on out-of-distribution queries, where most queries have zero true cardinality, and its data-distribution model substantially outperforms KDE and MSCN. Supervised MSCN degrades sharply in this setting.

  • OOD workload: 98% of 2,000 OOD DMV queries have true cardinality zero, providing a test of robustness beyond literals drawn from the data.The OOD literals are drawn from the entire joint domain.
  • Results: MSCN-10K’s median error rises to 23× from 1.51× on the OOD workload.The cited passage attributes this degradation to the supervised model’s behavior on OOD queries.
  • Results: Naru outperforms KDE by 40× and MSCN by 10^4× on OOD queries.Because Naru approximates the data distribution, it learns that OOD regions have little or no density mass.

6.4 Training Time vs. Quality

Naru reaches strong estimation quality after few training epochs and can estimate queries in milliseconds on a GPU. Column ordering and wildcard-skipping further affect variance, especially in the extreme tail.

  • Training: No past queries are required for training; Naru only needs a uniform random stream of tuples from the relation.The estimator requires only a few epochs to become sufficiently powerful.
  • Training: 1 epoch suffices for best-baseline accuracy on DMV, while Conviva-A reaches best-in-class quality after 2 epochs and single-digit max error after about 15 epochs.An epoch takes about 75 seconds for DMV and 50 seconds for Conviva-A.
  • Inference: 5–10ms GPU latency makes Naru faster than scanning samples and competitive with DBMS-1.Wildcard-skipping reduces the forward-pass burden of naive progressive sampling.
  • Variance: Almost all random column orderings achieve single-digit errors at the 99th percentile or below, but ordering affects extreme-tail variance.The experiment trains models on 20 random orders and repeats each dataset’s workload 10 times.
  • Variance reduction: Information-theoretic orders reduce variance, while wildcard-skipping lowers max-error variance by up to several orders of magnitude.For MutInfo, the maximum drops from 10^3 to below 10.

6.7 Autoregressive Model Choice and Sizing

Naru’s accuracy depends on density-model quality and progressive sampling, with model choice, entropy gap, dimensionality, and data shifts shaping practical performance. Experiments indicate efficient architectures, tractable sampling at high dimensionality, and reasonable accuracy under ingestion changes.

  • Autoregressive model choice: ResMADE and regular MADE are preferable to similarly sized Transformer and MADE variants because of their efficiency.The authors expect Transformer to excel on larger-scale datasets.
  • Variance reduction: Wildcard-skipping and heuristic orders have lower error variance than random orders.The comparison plots distributions of 10 maximum errors, with whiskers showing minima and maxima and bold bars showing medians.
  • Model entropy gap: 0–2 bits is Naru’s best entropy-gap range, while performance remains competitive through a 10-bit gap.A 0.5-bit-or-lower gap does not substantially improve performance; 0–2 bits corresponds to assigning 25–100% probability mass to empirical data.
  • Scaling progressive sampling: 1000 progressive sample paths provide reasonable worst-case accuracy for up to 100 columns, while additional paths further improve estimates.Increasing dimensionality raises estimate variance, but the sampling budget needed to mitigate it remains tractable.
  • Robustness to data shifts: Naru handles queries on newly ingested data with reasonably good accuracy even without seeing the new partitions.The data-shift experiment compares no model updates with gradient updates after each ingest.

7. RELATED WORK

Related work spans joint-distribution approximations, supervised query-driven estimators, and machine-learning query optimizers. Naru instead uses an unsupervised generative approach to model the relation’s joint distribution and estimate selectivities.

  • Joint approximation estimators: Multidimensional histograms, probabilistic relational models, and dependency-based histograms approximate the joint distribution using coarse or conditional-independence structures.These methods trade modeling detail for tractability by retaining partial structure or factoring the joint.
  • Position relative to prior work: Naru’s progressive-sampling evaluation remains tractable as the joint data space reaches over 10^190 at 100 columns.The figure uses an oracle model and 50 randomly generated queries covering at most 12 columns.
  • Query-driven estimators: Query-driven estimators use past or training queries and feedback to improve histograms, KDEs, regressors, or future cardinality predictions.Examples include ISOMER, STHoles, LEO, CardLearner, query-driven KDEs, and supervised learning regressors.
  • Machine learning in query optimizers: Naru differs from learned query optimizers by providing a generative selectivity estimator rather than predicting cardinalities through query representations or optimizer embeddings.It can serve as a drop-in replacement for the selectivity estimator in ML-enhanced query optimizers.

8. CONCLUSION

The paper concludes that deep autoregressive models can accurately estimate selectivities without independence assumptions. Naru adds Monte Carlo integration and variance reduction for challenging range queries, while remaining an unsupervised neural synopsis suited to broader future workloads.

  • Conclusion: Deep autoregressive models approximate relational data distributions without column-independence assumptions and achieve high selectivity-estimation accuracy.Naru exceeds the state of the art across several estimator families.
  • Conclusion: Monte Carlo integration and variance-reduction techniques let Naru efficiently handle high-dimensional range queries.The authors present these as novel extensions to autoregressive models.
  • Conclusion: Naru trains directly from data without query feedback, enabling efficient training and support for a broader set of future queries.The authors characterize Naru as an unsupervised neural synopsis that is robust to shifts in query workload.
Loading 1905.04278v2…