Downsizing Diffusion Models for Cardinality Estimation

Xinhe Mu, Zhaoqi Zhou, Zaijiu Shang, Chuan Zhou, Gang Fu, Guiying Yan, Guoliang Li, Zhiming MaarXiv 2025 · DOI · arXiv

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.

The ADC/ADC+ architecture showing the interaction between the Score Estimator, Density Estimator, and the GMM-based Predictor.

Core Components

  1. 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.
  2. Density Estimator: This component calculates probability density at specific points by integrating the score function using the Midpoint Rule and Quasi Monte Carlo integration.
  3. 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.

Left: The complex distribution of the Modulo dataset. Right: Loss curves comparing different network architectures against an ideal baseline.

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

Abstract

Learned cardinality estimation requires accurate model designs to capture the local characteristics of probability distributions. However, existing models may fail to accurately capture complex, multilateral dependencies between attributes. Diffusion models, meanwhile, can succeed in estimating image distributions with thousands of dimensions, making them promising candidates, but their heavy weight and high latency prohibit effective implementation. We seek to make diffusion models more lightweight by introducing Accelerated Diffusion Cardest (ADC), the first "downsized" diffusion model framework for efficient, high-precision cardinality estimation. ADC utilizes a hybrid architecture that integrates a Gaussian Mixture-Bayesnet selectivity estimator with a score-based density estimator to perform precise Monte Carlo integration. Addressing the issue of prohibitive inference latencies common in large generative models, we provide theoretical advancements concerning the asymptotic behavior of score functions as time $t$ approaches zero and convergence rate estimates as $t$ increases, enabling the adaptation of score-based diffusion models to the moderate dimensionalities and stringent latency requirements of database systems. Through experiments conducted against five learned estimators, including the state-of-the-art Naru, we demonstrate that ADC offer superior robustness when handling datasets with multilateral dependencies, which cannot be effectively summarized using pairwise or triple-wise correlations. In fact, ADC is 10 times more accurate than Naru on such datasets. Additionally, ADC achieves competitive accuracy comparable to Naru across all tested datasets while maintaining latency half that of Naru's and requiring minimal storage (<350KB) on most datasets.
BibTeX
@misc{mu2025downsizing,
  author = {Xinhe Mu and Zhaoqi Zhou and Zaijiu Shang and Chuan Zhou and Gang Fu and Guiying Yan and Guoliang Li and Zhiming Ma},
  title = {{Downsizing Diffusion Models for Cardinality Estimation}},
  year = {2025},
  eprint = {2510.20681},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.20681},
}
Figure