Introduction
Cardinality estimation (CE)—predicting the number of rows a database query will return—is a fundamental component of query optimization. Inaccurate estimates often lead to suboptimal execution plans, resulting in significant performance degradation. While modern learned estimators like Naru have improved upon traditional statistics, they often struggle with "multilateral dependencies"—complex, non-linear relationships between multiple columns that pairwise correlations cannot capture.
Generative diffusion models, renowned for their success in high-dimensional image synthesis, are theoretically capable of modeling these complex distributions. However, their standard architectures are too computationally expensive and slow for the millisecond-latency requirements of database engines. This paper introduces Accelerated Diffusion Cardest (ADC), a framework designed to "downsize" diffusion models for real-time cardinality estimation.
The ADC Framework
ADC adapts the power of diffusion models to the database context by utilizing a specialized architecture and a hybrid inference strategy. The framework consists of three primary components: a Score Estimator, a Density Estimator, and a Selectivity Estimator.
Core Components
- Score Estimator (QuadNet): Instead of the massive U-Net architectures used in image generation, ADC employs QuadNet, a lightweight network optimized for the moderate dimensionality of database tables (typically 10–30 columns). QuadNet uses a hybrid approach to handle "score blowup," where gradients approach infinity as noise levels decrease.
- Density Estimator: This component calculates probability density at specific points by integrating the score function using the Midpoint Rule and Quasi Monte Carlo integration.
- Selectivity Estimator (GMM-Bayesnet Hybrid): To estimate counts over a range, ADC uses a Gaussian Mixture Model (GMM) as a fast "predictor." The diffusion model then acts as a "corrector," refining the GMM's estimate via importance sampling.
For further optimization, the authors propose ADC+. This variant includes a tiny decision tree classifier that identifies "easy" queries (those with high volume or high selectivity). For these queries, ADC+ bypasses the diffusion correction entirely, relying on the fast GMM estimate to minimize latency.
Experimental Evaluation
The framework was evaluated against state-of-the-art models like Naru on several real-world datasets (Forest, Power, Higgs) and a synthetic benchmark called Modulo. The Modulo dataset was specifically engineered with complex, non-pairwise correlations to test the limits of existing estimators.
Key Results
- Superior Accuracy: On the challenging Modulo dataset, ADC+ demonstrated a 10x improvement in accuracy over Naru at the 95th and 99th percentile Q-errors, proving its ability to capture multilateral dependencies.
- Low Latency and Footprint: ADC+ achieved inference times of 7–10 milliseconds—roughly half the latency of Naru on real-world data. Furthermore, the model is exceptionally compact, requiring less than 350KB of storage.
- Theoretical Grounding: The authors provide asymptotic estimates for score functions, proving that for low-to-moderate dimensions, diffusion models do not require massive parameter counts to remain effective.
Conclusion and Future Work
ADC demonstrates that diffusion models can be successfully downsized for high-speed database tasks without sacrificing their ability to model complex data distributions. While training times remain longer than simpler regression models, the gains in accuracy, storage efficiency, and inference speed make ADC a compelling choice for modern query optimizers. Future work will focus on extending the framework to handle categorical data and high-cardinality strings.
Summary updated