Downsizing Diffusion Models for Cardinality Estimation

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

Read Downsizing Diffusion Models for Cardinality Estimation by Xinhe Mu, Zhaoqi Zhou, Zaijiu Shang, Chuan Zhou, Gang Fu, Guiying Yan, Guoliang Li, Zhiming Ma (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20681.txt.

Introduction

Xinhe Mu and seven co-authors shrink diffusion models so they can estimate how many rows a database query will return, a count that guides fast query plans. Learned estimators must capture tangled links between columns, and diffusion models excel at rich distributions but run far too slowly for database use.

Their system, ADC, pairs a mixture based selectivity estimator with a score based density estimator in a hybrid design for precise sampling based counts. New theory on score behavior at small and large times lets the model fit mid sized database problems under strict delay limits. Tests against five learned rivals show the downsized design keeps high accuracy while meeting practical speed needs.

Catalog record

CREATORXinhe Mu, Zhaoqi Zhou, Zaijiu Shang, Chuan Zhou, Gang Fu, Guiying Yan, Guoliang Li, Zhiming Ma
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20681

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Downsizing Diffusion Models for Cardinality Estimation Xinhe Mu, Zhaoqi Zhou, Zaijiu Shang, Chuan Zhou, Gang Fu, Guiying Yan, Guoliang Li, Zhiming Ma Abstract . Inspired by the performance of score-based diffusion models ( Song et al. 2021b ) in estimating complex text, video, and image distributions with thousands of dimensions, we introduce Accelerated Diffusion Cardest (ADC), the first joint distribution ( Wang et al. 2021 ) cardinality estimator based on a downsized diffusion model. To calculate the pointwise density value of data distributions, ADC’s density estimator p θ ​ ( x ) p_{\theta}(x) uses a formula ( Song et al. 2021a ) that evaluates log-likelihood by integrating the score function ∇ log ⁡ p t ​ ( x ) \nabla\log p_{t}(x) , a gradient mapping which ADC has learned to efficiently approximate using its lightweight score estimator, s θ ​ ( x , t ) s_{\theta}(x,t) . To answer ranged queries, ADC’s selectivity estimator first predicts their selectivity using a Gaussian Mixture Model (GMM) q ⁡ ( x ) q(x) , then uses importance sampling Monte Carlo to correct its predictions with more accurate pointwise density values { p θ ​ ( x i ) } i = 1 n \{p_{\theta}(x_{i})\}_{i=1}^{n} calculated by the density estimator. ADC+ further trains a decision tree to identify the high-volume, high-selectivity queries that q ⁡ ( x ) q(x) alone can predict very accurately, in which case it skips the correction phase to prevent Monte Carlo from adding more variance. Doing so lowers median Q-error and cuts per-query latency by 25%, making ADC+ usually twice as fast as Naru ( Yang et al. 2019 ) , arguably the state-of-the-art joint distribution cardinality estimator. Numerical experiments 1 1 1 Open-source code for ADC shall be released at https://github.com/XinheMu/ADC-Replication- in Jan. 2026 upon formal submission using well-established benchmarks ( Asuncion et al. 2007 ) ( Wang et al. 2021 ) show that on all real-world datasets tested, ADC+ is capable of rivaling Naru and outperforming MSCN ( Kipf et al. 2018 ) , DeepDB ( Hilprecht et al. 2020 ) , LW-Tree, and LW-NN ( Dutt et al. 2019 ) using around 66% their storage space, being at least 3 × 3\times as accurate as MSCN on 95th and 99th percentile error 2 2 2 We define ”accuracy” as Q-error − 1 -1 as 1 is Q-error’s optimal value . Furthermore, on a synthetic dataset where attributes exhibit complex, multilateral correlations, ADC and ADC+ are considerably robust while almost every other learned model suffered significant accuracy declines. In this case, ADC+ performs better than any other tested model, being 10 × 10\times as accurate as Naru ( Yang et al. 2019 ) on 95th and 99th percentile error. 1. Introduction Score-based Diffusion Models have presented the deep learning community with a very, if not the most, attractive way of acquiring highly local information about a complex high-dimensional probability distribution ( Chen et al. 2023 ) . These models work by training a neural network to approximate the score (gradient of its log function) of an evolving probability density function, which, starting out as the distribution to be learned, is gradually turned into Gaussian noise through a diffusion process. Using the learned score function, score-based diffusion models can then reverse the diffusion process by solving a backward diffusion stochastic differential equation (SDE), and, in doing so, sample from ( Song et al. 2021b ) ( Ramesh et al. 2022 ) ( Dhariwal and Nichol 2021 ) or evaluate ( Song et al. 2021b ) ( Song et al. 2021a ) the underlying distribution at the user’s request. Given their success, one may naturally wonder whether cardinality estimation, a task crucial for the ideal performance of query optimizers, can also benefit from diffusion models. Indeed, several learned cardinality estimation models, such as Naru ( Yang et al. 2019 ) and DQM-D ( Hasan et al. 2020 ) , are already performing cardinality estimation by approximating an underlying probability density function at individual points, then numerically integrating it across the queried region using various Monte Carlo schemes ( Yang et al. 2019 ) ( Lepage 1978 ) . However, simply grabbing a popular score-based diffusion model off the shelf probably won’t work due to the three reasons below. First, while conventional models used for image generation excel at approximating distributions with thousands of dimensions, their sampling process often take up to tens of seconds even with the help of advanced TPUs ( Ho et al. 2020 ) and time-saving techniques like consistency models ( Song et al. 2023 ) or DPM Solver ( Lu et al. 2022 ) , which is often longer than the time it costs to actually execute the query. Second, existing works on diffusion models have never touched on the problem of integrating the probability density function across a given region, a task useless for image generation, yet crucial for cardinality estimation. Most importantly, image generation and cardinality estimation require different magnitudes of precision: while making it five times more likely to generate a specific image gives a generative model its unique art style, predicting five thousand tuples to exist in a region where only one thousand actually does gives a query optimizer an optimization disaster. In this paper, we aim to overcome the aforementioned limitations by presenting Accelerated Diffusion Cardest(ADC), a “downsized” diffusion model much more suited for cardinality estimation, structured according to the framework in Figure 1 . Figure 1 . ADC’s training and inference framework. ADC's training and inference workflow. During training, data points are used to (1) directly train the GMM selectivity estimator using maximum likelihood and (2) generate information for the score function, which is then used to train the score estimator. During inference, the GMM selectivity estimator calculates a rough selectivity prediction and conditionally samples points for further evaluation, while the density estimator, accepting input from the score estimator, corrects that prediction by evaluating the probability density function at sampled points with much more accuracy. Here, our major contributions are: (1) Downsizing Score Matching . We find that for distributions with moderate dimensionality, the inherent structure and properties of diffusion processes can be used to construct much more lightweight score matching networks that achieve the same level of precision. That is, score matching is best done using the data prediction model when t is large, and a modified noise prediction model when t is small. We modify traditional noise prediction models by constructing a neural network with three output modules, normalized using the functions \frac{1}{\sigma^{2}(t)},\frac{1}{\sigma(t)} , and 1 , respectively. This modification is proven to significantly enhance precision and, to the best of our knowledge, has not been proposed in previous works. (2) Simplifying Likelihood Calculation . Existing works studying diffusion models ( Song et al. 2021a ) provide a formula for calculating the pointwise log-density of a probability distribution by integrating its score function across time and space. We convert this formula into a fast, well grounded algorithm which combines Quasi Monte Carlo (for integration across space) with adaptive stepsize Midpoint Rule (for integration across time), enabling accurate estimations in less than 1\text{\,}\mathrm{ms} per point. (3) GMM for Cardinality Estimation . In order to estimate the selectivity of

Read the complete text