QEmbed: A Deep Learning Based Cardinality Estimator for Efficient Query Processing Pooja Rajput1[0009−0009−1753−5056] and Suman Banerjee1[0000−0003−1761−5944]
arXiv:2609.12535v1 [cs.DB] 11 Sep 2026
Indian Institute of Technology Jammu, J & K-181221, India {2023rcs1016,suman.banerjee}@iitjammu.ac.in Abstract. Cardinality estimation is at the core of any commercial database system for efficient query processing. Over the decades, non-learningbased estimation techniques (e.g., histogram-based, sampling-based) have been widely used in both commercial and open-source database platforms. However, these techniques are only effective when the number of columns in a table is small, as they cannot properly capture dependencies between multiple attributes. Recently, learning-based approaches have been shown to perform significantly better than the heuristic methods that have been used for the past three decades. Despite this success, existing learned models often struggle to balance memory efficiency and accuracy when dealing with datasets that mix high and low cardinality attributes. In this paper, we propose a deep learning model formally called QEmbed. Our model is built upon the Masked Autoencoder for Distribution Estimation (MADE) auto-regressive framework to learn joint data distributions for selectivity estimation. To improve data representation and overcome the limitations of using a single encoding method, we design a hybrid encoding scheme that combines one-hot and embedding encodings. This hybrid design enables QEmbed to retain fine-grained attribute information for smaller domains while capturing compact semantic patterns for large, sparse domains. We capture attribute correlations by factoring the joint data distribution into a series of conditional probabilities. This approach naturally accommodates both point and range queries. Through extensive experiments, we show that while QEmbed faces a latency trade-off on extremely wide schemas, it provides highly reliable cardinality estimates overall. A key advantage of our model is that it reduces extreme tail errors (maximum Q-errors), avoiding catastrophic estimation failures on complex, highly correlated workloads. Keywords: Cardinality estimation · Sampling · Histogram · MADE · Encoding .
1
Introduction
Cardinality estimation in database systems refers to estimating the output size of a relational algebra operation [7, 8, 10–12]. This is critical because accurate estimation directly leads to more efficient and relevant query execution plans. Over the past three to four decades, simple data-driven heuristics, such as histograms and sampling, have been widely used in commercial and open-source
2
Pooja Rajput and Suman Banerjee
database systems [9]. However, literature has shown that these predictions are often suboptimal, sometimes resulting in estimation errors exceeding a factor of 10, 000 for complex queries. In the past decade, significant efforts have been made to build and employ machine learning and deep learning models for cardinality estimation. Supervised regression approaches, such as Multi-Set Convolutional Networks (MSCN) [25] and Lightweight XGBoost (LW-XGB) [31], represent queries as feature vectors and train models to directly predict query selectivity [3]. These methods are effective when the training queries are representative of the workload but may struggle with previously unseen queries. Unsupervised approaches focus on modeling the joint probability distribution of relation attributes. Auto-regressive models like MADE, as used in NARU, capture correlations between attributes without relying on query logs and can handle equality and range predicates through techniques such as progressive sampling. DeepDB [15] adopts a hybrid design that combines statistical techniques with neural networks, allowing it to handle high-dimensional datasets more efficiently. Nevertheless, representing the input space remains challenging because real-world datasets often contain a combination of low- and high-cardinality attributes, making it difficult to achieve both compact memory usage and accurate selectivity estimation. Earlier solutions such as NARU relied on deep autoregressive models to estimate the joint probability distribution of data attributes [1]. This solution explored not only the unsupervised problem of density estimation using MADE models but also the supervised problem of selectivity estimation using a querydriven approach. In this study, binary and one-hot encoding schemes were also considered as ways to represent attribute values. Both of these schemes can function well under certain conditions, but each has its shortcomings. In particular, one-hot encoding produces very sparse vectors and requires a heavy computational load when dealing with high-cardinality attributes. However, binary encoding uses space efficiently but lacks detail for low-cardinality attributes. To address these challenges, we present QEmbed with a hybrid encoding scheme used in MADE models. The main contributions of this work are summarized as follows: – We investigate the cardinality estimation problem, which is fundamental to generating efficient query execution plans. – We propose QEmbed, a deep learning model that extends the MADE architecture with a hybrid encoding strategy to effectively represent datasets containing both low- and high-cardinality attributes. – We conduct extensive experiments on multiple real-world datasets and demonstrate that QEmbed achieves competitive cardinality estimation performance across diverse query workloads while substantially reducing extreme estimation errors compared with the Embed model. The rest of the paper is organized as follows. Section 2 formally defines the cardinality estimation problem. Section 3 presents the proposed model. Section 4 describes the experimental evaluation. Finally, Section 5 concludes the paper and discusses future research directions.
QEmbed: Cardinality Estimator for Efficient Query Processing
2
3
Problem Definition
Let R be a relation with m attributes {X1 , X2 , . . . , Xm }. Each attribute Xi is associated with a finite domain Di derived from the distinct values present in the dataset. A selection query Q is defined as a conjunction of d predicates (1 ≤ d ≤ m) on these attributes: Q = θ1 ∧ θ2 ∧ · · · ∧ θd
(1)
Each predicate θi represents an equality condition (Xi = a), a range condition (lb ≤ Xi ≤ ub), or a membership condition (Xi ∈ {a1 , a2 , . . . , ak }). The cardinality of query Q, denoted as Card(Q), is the number of tuples in R that satisfy all predicates simultaneously: Card(Q) = |{t ∈ R : Q(t) = 1}|
(2)
Correspondingly, the selectivity Sel(Q) is the fraction of tuples in R that satisfy the query: Card(Q) (3) Sel(Q) = |R| The main goal of selectivity estimation is to compute Sel(Q) quickly without scanning the entire dataset. Traditional methods, such as histograms and sampling, usually rely on the attribute independence assumption. They approximate the joint probability by assuming that columns do not affect each other: m Y P (X1 , . . . , Xm ) = P (Xi ) (4) i=1
Because this ignores real-world correlations between attributes, these methods often produce large errors for complex multi-attribute queries. To address this limitation, we model the exact joint probability distribution of the attributes. Using the MADE framework [6], we factorize the joint distribution into conditional probabilities: P (X1 , X2 , . . . , Xm ) =
m Y
P (Xi | X1 , X2 . . . , Xi−1 )
(5)
i=1
This allows the model to learn the actual dependencies between attributes directly. In this work, we focus on how different encoding schemes for categorical and numerical features operate within this model. We evaluate how these specific encoding choices impact the final estimation accuracy across different datasets.
3
Proposed Methodology: QEmbed
3.1
Overview of the QEmbed Architecture
To achieve efficient and accurate query selectivity estimation, we introduce QEmbed, an auto-regressive deep learning network that treats cardinality estimation
4
Pooja Rajput and Suman Banerjee
as an unsupervised density estimation problem. As shown in Fig. 1, the model consists of three main stages: Hybrid Encoding, Masked Processing, and Conditional Probability Estimation. Based on the MADE framework, QEmbed uses the probabilistic chain rule to factorize the joint probability of a relational tuple x = (x1 , x2 , . . . , xm ): m Y P (x) = P (xi | x1 , x2 , . . . , xi−1 ) (6) i=1
By conditioning each attribute only on its predecessors, this factorization allows the model to capture complex cross-attribute dependencies.
Fig. 1: QEmbed: Architecture of the proposed model 3.2
Stage 1: Hybrid Encoding and Input Layer
Relational databases contain mixed-type attributes. Encoding high-cardinality attributes with standard one-hot vectors creates massive, sparse vectors that are difficult to train. To solve this, QEmbed uses a dual-channel encoding approach controlled by a configurable cardinality threshold, τ : – Low-Cardinality Route (|Vi | ≤ τ ): Domains with distinct values at or below the threshold use standard one-hot encoding. This preserves exact categorical boundaries for smaller domains. – High-Cardinality Route (|Vi | > τ ): Domains exceeding the threshold bypass one-hot encoding. Instead, they pass through an embedding layer that maps them into a dense continuous vector ei ∈ Rd . Weights used during embedding initialization are drawn from a normal distribution. This hybrid model enables the system to learn semantic relationships for larger sets and preserves a one-to-one mapping for smaller sets. Channels obtained through this are combined to create an input vector h(0) . 3.3 Stage 2: Masked Hidden Layers and Structural Connections The input vector h(0) is passed through a four-layer masked fully-connected neural network with 128 hidden neurons for each layer. This network size is chosen to capture all underlying data patterns while avoiding the high inference latencies
QEmbed: Cardinality Estimator for Efficient Query Processing
5
characteristic of heavier models such as Transformers. The auto-regressive condition P (xi | x<i ) is enforced using binary mask matrices M (ℓ) on the weights. The formula describing feed-forward computation on a hidden layer l is: (7) h(ℓ) = ReLU W(ℓ) ⊙ M(ℓ) h(ℓ−1) + b(ℓ) Here, W (ℓ) denotes the weight matrix, b(ℓ) stands for the bias, and ⊙ denotes the Hadamard product. Masking ensures that the network does not have the opportunity to use future attributes (x≥i ). In addition, shortcuts from the beginning of the network to its end are used in order to make training faster. The input vector h(0) bypasses all layers and goes straight to the output layer without being multiplied by any masks. Network weights are initialized using the Xavier uniform scheme, and biases are set to zero. 3.4
Stage 3: Output and Unsupervised Training
The final layer applies a softmax activation to output the estimated conditional probabilities, P̂ (xi | x1 , x2 , . . . , xi−1 ). We train the network in an unsupervised manner by minimizing the Negative Log-Likelihood (NLL) over the dataset D: m
L(θ) = −
1 XX log P̂ (xi | x1 , , x2 , . . . , xi−1 ; θ) |D| i=1
(8)
x∈D
Categorical attributes use cross-entropy loss, while binary attributes use binary cross-entropy. Because the input embeddings are updated jointly with the hidden layers during training, the model naturally groups highly correlated database values closer together in the latent space. 3.5
Query Inference and Selectivity Estimation
Once trained, QEmbed acts as an in-memory statistical summary of the database. For simple point queries, selectivity is calculated in O(1) time with a single forward pass by multiplying the output probabilities. For complex range queries where computing exact probabilities is too slow, QEmbed uses Progressive Sampling. This approach uses a Monte Carlo sampler to auto-regressively sample valid tuples from the learned distribution: 1 ˆ Sel(Q) ≈ N
N Y m X
(k)
P̂ (xi
(k)
(k)
∈ Qi | x1 , . . . , xi−1 )
(9)
k=1 i=1
By relying entirely on the neural network’s learned distribution, this method completely avoids physical table scans, providing fast and accurate cardinality estimates during query optimization.
4
Experimental Evaluation
In this section, we describe the experimental evaluation of the methodologies. We begin by describing the datasets used.
6
Pooja Rajput and Suman Banerjee
4.1
Datasets
In our experiments, we used the following five datasets: – Forest [21]: A forest cover classification dataset with approximately 581,000 records and 55 categorical attributes, along with several numerical features. The correlated attributes and diverse feature space make it useful for evaluating cardinality estimation methods. – Power [27]: A household electricity consumption dataset with approximately 2.07 million records and 9 attributes. The continuous and highly correlated measurements provide a challenging workload for estimating cardinalities over numerical data. – DMV [20]: A real-world dataset containing approximately 11.6 million New York State vehicle, snowmobile, and boat registration records with 11 attributes. It includes diverse attribute domains and strong correlations, making it a challenging benchmark for cardinality estimation. – Poker Hand [22]: This dataset contains 1,025,010 records with 11 attributes describing five-card poker hands. Strong dependencies among card attributes make it suitable for evaluating estimation accuracy on correlated data. – Census [23]: Based on the 1990 U.S. Census survey, this dataset contains approximately 2.45 million records and 61 demographic and socioeconomic attributes. Its high dimensionality and strong attribute correlations make it a challenging benchmark for cardinality estimation. 4.2
Baseline Methods
In our experimentation, we compared our results with the following methods from the literature: – Sampling: Sampling is a lightweight, widely used heuristic technique for cardinality estimation in query optimization. These techniques avoid scanning the entire dataset [14] by running the query on a small sample of the data, and then scaling up the approximate cardinality estimation for the full dataset. Progressive sampling starts with a small sample and increases it gradually until the estimate becomes stable. This approach is particularly suitable for range queries [13]. – MaxHistDiff: The MaxHistDiff approach generates multi-dimensional histograms to represent the dataset [19]. We use the max-diff partitioning strategy, which identifies the largest difference between adjacent values and splits the data accordingly. During query estimation, MaxHistDiff identifies the relevant histogram buckets and aggregates their frequencies, assigning proportional weight to buckets that partially contribute [26]. – BayesNet: BayesNet represents a probabilistic graphical model-based approach [4]. The main aim of this model is to capture the dependencies among attributes for precise selectivity estimation. These models are used to find the joint distribution of the attributes and generate samples from these distributions to approximate query results [1].
QEmbed: Cardinality Estimator for Efficient Query Processing
7
– BayesCard: This technique is an extended version of Bayesian networks to enhance cardinality estimation in databases. We follow the implementation from [2, 5] which employs Bayesian networks with progressive sampling to find the cardinality of range queries. BayesCard allows us to obtain quick estimates more accurately, especially for complex queries. – Transformer: The Transformer is an auto-regressive model used to approximate the full joint distribution of the data without requiring independence assumptions. By using self-attention, it captures the correlations between attributes and supports both range and point queries [30]. This significantly improves the Q-error of the cardinality estimates [5]. – MADE: MADE is a generative neural network that approximates the joint probability distribution of attributes using a masked auto-regressive architecture [6], where each prediction depends on previous attributes. For point queries, cardinalities are estimated by multiplying conditional probabilities and scaling by the table size; for range queries, the learned distribution guides progressive sampling [1]. – FACE: FACE (Flow-based Auto-regressive Cardinality Estimator) uses normalizing flows to learn the joint probability distribution of relational data. Instead of grouping continuous or high-cardinality attributes into discrete buckets, it models them directly in a continuous space to capture complex data relationships. For range queries, FACE calculates exact probabilities using Cumulative Distribution Functions (CDFs) [28], avoiding the slow execution of Monte Carlo sampling while maintaining highly accurate estimates. 4.3
Details of the Experimentation
Experimental Setup and Hyperparameters: All our experiments were performed on a virtual machine (Ubuntu 20.04 LTS). This machine has an Intel Xeon processor (Cascade Lake with 40 CPU cores), 251 GB of RAM, and an NVIDIA Tesla V100 GPU with 32 GB of VRAM. CUDA version 11.8 was utilized, and PyTorch was used for building the machine learning model. To ensure our results are fully reproducible, we set a fixed random seed of 0 for all operations. Because the objective of our cardinality estimator is to construct an accurate in-memory synopsis of a static database, the models were trained and evaluated on the complete datasets to capture the full underlying joint distributions. All models were trained for 50 epochs using a batch size of 256. We optimized the network using the Adam optimizer with an initial learning rate of 2 × 10−4 , which was dynamically scaled up to 1 × 10−2 during batch processing to speed up model convergence. For the hybrid encoding layer, we set the embedding dimension to d = 32, initialized the embedding weights using a normal distribution with σ = 0.02, and set the default cardinality threshold to τ = 5, though this threshold can be dynamically adjusted depending on the target database. Metrics for Evaluation: We apply the Q-error as the main criterion to evaluate estimation accuracy [15, 19]. The Q-error denotes the multiplicative factor
8
Pooja Rajput and Suman Banerjee
between the estimate and the real value. To avoid division by zero, both the actual and estimated values are lower-bounded by 1. Formally, the Q-error for a particular query Q can be calculated using the following formula: ! [ Card(Q) Card(Q) Q-error = max , (10) Card(Q) Card(Q) [ [ where Card(Q) denotes the actual cardinality and Card(Q) denotes the estimated one. The smaller the value of the Q-error, the more accurate the estimate is. We prefer using Q-error instead of other possible criteria, such as relative error, Mean Absolute Error (MAE), and Mean Squared Error (MSE). Q-error provides symmetrical treatment of under-estimation and over-estimation, does not depend on the size of the dataset, is immune to outliers, and is the standard metric used in the database literature that allows for easy comparison with existing methods. We report the median (50th percentile), 75th, 90th, and 95th percentile Q-errors, along with the mean and maximum Q-error, to evaluate estimation accuracy from both typical and worst-case perspectives. In addition, we report the inference latency of each method to assess its computational efficiency. Query Distribution: To evaluate performance, we generate a workload of random queries using a tuple-sampling method. For each query, the number of target attributes f is chosen randomly, ranging from a minimum of 5 up to the total number of attributes m present in the dataset. These f distinct columns are selected without replacement. The filter values are extracted from a real tuple sampled uniformly at random from the dataset, ensuring that the queries reflect the actual data distribution. For attributes with a domain size of 10 or more, the filter operator is chosen uniformly from {≤, ≥, =}. For attributes with smaller domains, the operator is restricted exclusively to equality (=). Finally, any generated query that results in an actual cardinality of zero is discarded, ensuring the evaluation workload only contains queries with valid matching tuples. Training Model Performance Figure 2 compares the training entropy of the Transformer, Binary, Embed, and QEmbed models on five datasets. Across all datasets, QEmbed consistently achieved the lowest training entropy and reached a low-entropy solution earlier than the other models. For the Forest dataset (Figure 2a), QEmbed reached a final entropy of about 75.29 bits at epoch 49. It finished training in 22,321 seconds, whereas the Binary and Embed models took much longer, requiring 43,120 and 44,710 seconds, respectively. On the Power dataset (Figure 2b), QEmbed maintained the lowest training entropy from start to finish. Although a slight increase in entropy was observed after the initial epochs, it consistently remained lower than that of the competing models, indicating stable optimization. QEmbed trained on DMV in 22,804 seconds and achieved the lowest entropy of any model tested (19.24 bits). Binary and Embed needed over 449,767 and 481,311 seconds respectively to reach only 20.24 and 20.22 bits — roughly 20× slower for a slightly worse result. Looking at the Poker dataset (Figure 2d),
QEmbed: Cardinality Estimator for Efficient Query Processing
9
QEmbed reached a final entropy of 28.51 bits and completed training in just 1,268 seconds. Finally, for the Census dataset (Figure 2e), QEmbed again kept the lowest training entropy and showed stable progress during training.
(a) Forest dataset
(d) Poker dataset
(b) Power dataset
(c) DMV dataset
(e) Census dataset
Fig. 2: Comparison of training entropy gap (in bits) versus epochs for multiple models on the Forest, Power, DMV, Poker and Census datasets. This improved performance comes from our proposed hybrid encoding, which combines dense embeddings with binary encoding. This approach helps the model reach a low-entropy solution more efficiently while maintaining the lowest training entropy across all datasets. Overall, these results show that QEmbed offers a faster, more efficient training method for neural cardinality estimation across all five datasets. Effects of Encoding: In our experiments, we evaluated the impact of different encoding schemes (One-hot, Binary and Embed) on the model’s performance. The results highlight distinct trade-offs: – Space: In the one-hot encoding scheme, the storage requirement is extremely high because each category requires a separate vector dimension, making it infeasible to encode high-cardinality features. Binary encoding uses binary numbers to represent categories; therefore, the dimension increases logarithmically with an increase in the domain space. The embedding technique encodes categories in dense vectors of fixed dimension d. – Training Time: The one hot encoding scheme is known to have very high training times because of the high dimensions of the input space, prolonging training due to the extensive memory overhead and large parameter space. However, Embedding is the most time-efficient method for large and skewed categorical domains.
10
Pooja Rajput and Suman Banerjee
– Query Performance: One-hot encoding works well for small domains due to the explicit representation of each category. However, as domain size increases, sparsity increases, which degrades generalization and slows down inference time. Binary encoding reduces this sparsity, making query execution more efficient for high-cardinality data. Embedding techniques excel by capturing the latent semantic similarity between attributes, which significantly aids in modeling complex data dependencies. – Data Type Suitability: One-hot encoding is best suited for low-cardinality categorical features. Binary encoding is appropriate for medium-to-high cardinality features or skewed data. Embedding is the most flexible approach, efficiently handling both high-cardinality and heavily skewed datasets. 4.4
Experimental Results and Discussion
We evaluate the performance of our proposed QEmbed model across five distinct datasets: Forest, Power, DMV, Poker and Census. The model is compared against multiple baselines, including histogram-based approaches (MaxHistDiff), sampling methods, Bayesian networks (BayesNet, BayesCard), autoregressive models with binary and embedding encodings and Transformer-based models. We report Q-error statistics, including the median, 75th, 90th, 95th percentiles, mean and maximum errors, alongside the inference latency for each method. Tables 1,2, 3, 4 and 5 summarize these comprehensive results. Table 1: Performance comparison on Forest dataset with Q-Error and Latency. Technique Query Med. 75th 90th 95th Mean MaxQE Lat.(ms) Sampling 1K 1.113 1.805 64.100 237.300 42.849 3664 1.471 2K 1.103 2.209 100.000 300.200 53.237 3088 1.002 4K 1.123 2.000 77.100 267.000 44.084 2681 0.910 MaxHistDiff 1K 1.663 14.177 46.697 59.832 14.252 256 832.788 2K 1.848 15.636 45.842 60.656 14.364 482 831.886 4K 1.887 15.509 44.805 59.583 14.615 24142 834.338 BayesNet 1K 1.132 1.735 8.318 24.059 6.550 591.143 1035656 2K 1.135 1.836 8.954 23.667 6.242 567.429 1044465 4K 1.137 1.855 9.138 22.810 6.232 621.286 1036065 Transformer 1K 1.124 1.283 1.785 2.229 1.709 97.833 253.620 2K 1.124 1.285 1.778 2.310 1.695 146.000 254.027 4K 1.124 1.305 1.802 2.375 1.641 146.000 253.912 Binary 1K 1.065 1.173 1.462 2.000 1.207 8.503 55.364 2K 1.063 1.176 1.472 2.000 1.220 24.833 57.408 4K 1.064 1.178 1.500 1.976 1.227 39.500 57.713 Embed 1K 1.097 1.874 88.000 243.350 48.026 3760 0.622 2K 1.098 2.028 102.000 273.350 50.843 290 0.622 4K 1.088 2.026 73.100 244.000 40.812 2840 0.613 FACE 1K 1.090 1.203 1.794 3.396 12.631 3747 275.637 2K 1.091 1.219 2.020 4.316 184.683 219181 275.907 4K 1.092 1.211 1.905 4.893 29.172 56160 276.039 QEmbed 1K 1.064 1.173 1.471 1.826 1.191 9.902 1564.146 2K 1.062 1.165 1.423 1.833 1.195 10.375 1564.443 4K 1.063 1.167 1.429 1.726 1.189 11.000 3745.214
QEmbed: Cardinality Estimator for Efficient Query Processing
11
Forest Dataset: Table 1 shows the results on the Forest dataset. This dataset is difficult for traditional cardinality estimators because its attributes are highly correlated. As a result, methods like Sampling and MaxHistDiff struggle with multi-attribute queries, leading to very large maximum Q-errors. While the baseline Embed model has low inference latency, it fails on complex queries, reaching a maximum Q-error of 2,840. In contrast, QEmbed successfully captures these attribute correlations. By making the embeddings query-aware, QEmbed reduces the maximum Q-error to 11.0 on the 4K workload. It also achieves the lowest 90th percentile, 95th percentile, and mean errors. Although QEmbed incurs a higher latency overhead compared to the basic Embed and Binary models, it remains orders of magnitude faster than BayesNet and prevents the severe worst-case errors seen in the baselines. Table 2: Performance comparison on the Power dataset. Technique Query Med. 75th 90th 95th Mean Max Lat.(ms) Sampling 1K 1.294 4.225 137.000 447.00 66.188 2893 0.730 2K 1.244 3.352 111.500 336.25 58.796 3414 0.733 4K 1.250 3.377 126.500 313.00 57.929 4552 0.744 MaxHistDiff 1K 1.274 3.000 22.000 65.000 15.564 1425 173.100 2K 1.246 2.864 20.716 61.105 14.633 1422 178.123 4K 1.259 2.984 20.849 62.394 14.715 4718 173.879 BayesNet 1K 1.155 1.455 2.251 3.223 1.266 213.932 235470 2K 1.148 1.480 2.371 3.347 1.279 220.622 106974 4K 1.147 1.450 2.305 3.251 1.270 8437 116369 Transformer 1K 1.165 1.395 2.000 2.834 2.123 306.60 356 2K 1.170 1.429 2.000 2.667 2.012 415.12 61 4K 1.175 1.451 2.000 2.721 1.824 415.12 106 Binary 1K 1.085 1.193 1.442 1.775 1.214 8.231 20.432 2K 1.078 1.197 1.440 1.789 1.209 10.000 16.562 4K 1.078 1.194 1.417 1.699 1.196 30.000 14.040 Embed 1K 1.069 1.167 1.400 1.714 1.010 4.000 811.242 2K 1.072 1.174 1.396 1.676 1.118 6.000 879.108 4K 1.075 1.182 1.413 1.700 1.025 6.000 767.168 FACE 1K 1.032 1.062 1.123 1.205 4417 441607 18.207 2K 1.032 1.063 1.119 1.202 1.132 80.035 18.872 4K 1.033 1.064 1.123 1.203 24.644 94231 17.769 QEmbed 1K 1.000 1.010 2.000 2.000 1.009 20.000 2502 2K 1.000 1.059 2.000 2.000 1.025 20.000 2920 4K 1.000 1.053 2.000 2.000 1.017 20.000 2735
Power Dataset: Table 2 presents the results for the Power dataset, which contains continuous and skewed data. On this dataset, Sampling and MaxHistDiff produce large maximum Q-errors. FACE achieves low errors for most queries, with a 95th percentile Q-error of about 1.20. However, its maximum Q-error exceeds 440,000, which increases its mean Q-error. QEmbed records a median Q-error of 1.000 and a maximum Q-error of 200. Although the Embed model records a lower maximum Q-error of 6.000, QEmbed
12
Pooja Rajput and Suman Banerjee
achieves lower 75th percentile and mean Q-errors. BayesNet also records relatively low maximum Q-errors, but it requires more than 100 seconds to evaluate a workload. Table 3: Performance comparison on the DMV dataset. Technique Query Med. 75th 90th 95th Mean MaxQE Lat.(ms) Sampling 1K 1.055 2.985 77.900 228.900 2.000 2825 6.989 2K 1.085 3.000 65.300 227.150 1.983 3192 6.961 4K 1.065 3.000 66.300 229.600 409.500 3824 6.794 MaxHistDiff 1K 2.573 5.092 30.977 107.206 27.133 2361.261 659.599 2K 2.691 5.415 29.000 90.923 25.050 4273.811 655.462 4K 2.706 5.578 30.108 91.161 28.310 6966.790 626.112 BayesNet 1K 1.065 2.576 6.133 9.774 3.591 609.333 53763.610 2K 1.070 2.796 6.209 10.498 4.534 1775.333 53177.841 4K 1.067 2.706 6.224 10.474 4.835 2083.333 52208.821 BayesCard 1K 1.083 1.103 1.510 1.192 103.164 96590 1.214 2K 1.084 1.106 1.611 1.260 102.262 96668 1.248 Transformer 1K 1.041 1.154 2.219 11.352 13.925 804.333 133.067 2K 1.041 1.155 2.301 11.193 12.538 804.333 220.701 4K 1.057 1.234 2.088 10.149 11.069 790.873 319.599 Binary 1K 2.783 5.303 9.697 18.786 5.277 4137.235 1382.518 2K 2.750 5.273 9.682 17.700 5.272 3951.372 1033.804 4K 2.681 5.212 10.113 17.954 5.289 53017.778 1137.221 Embed 1K 1.058 1.440 54.800 252.600 40.807 2129 0.622 2K 1.063 1.523 44.300 199.000 39.984 3041 0.622 4K 1.070 1.544 63.000 254.000 43.528 3057 0.616 QEmbed 1K 1.062 1.153 1.400 1.652 1.143 20 906 2K 1.064 1.159 1.402 1.668 1.137 228 844.125 4K 1.056 1.157 1.385 1.664 1.137 228 1280.178
DMV Dataset: Table 3 presents the results for the DMV dataset, which contains several correlated categorical attributes. On this dataset, Sampling and MaxHistDiff produce large maximum Q-errors. The Embed model has the lowest inference time, requiring less than 1 ms per query, but its 95th percentile Qerror exceeds 250. BayesCard records a maximum Q-error of more than 96,000, resulting in a higher mean Q-error. QEmbed achieves the lowest mean, 90th and 95th percentile Q-errors among the evaluated models. On the 1K workload, it records a maximum Q-error of 29.333. Its inference time is about 1,300 ms, which is higher than that of the faster baseline models. Poker Dataset: Table 4 presents the results for the Poker dataset. This dataset consists of categorical attributes representing card suits and ranks, making it suitable for evaluating models on discrete data with fixed attribute combinations. On this dataset, Sampling and MaxHistDiff produce large maximum Q-errors, reaching up to 50,091. Although FACE achieves low mean Q-errors, its maximum Q-error exceeds 242 on the 2K workload.
QEmbed: Cardinality Estimator for Efficient Query Processing
13
Table 4: Performance comparison on the Poker dataset. Technique Query Med. 75th 90th 95th Mean MaxQE Lat.(ms) Sampling 1K 4.000 35.000 180.100 389.750 71.004 2012 1.447 2K 4.467 39.250 192.050 385.100 74.564 2324 1.490 4K 4.000 37.000 181.000 348.000 66.669 2948 1.447 MaxHistDiff 1K 2.466 6.296 22.403 66.807 21.598 2448.086 70.080 2K 2.674 6.869 24.565 79.943 26.902 3687.324 69.546 4K 2.670 6.903 25.025 80.050 58.574 50091.671 69.657 BayesNet 1K 1.077 1.323 2.000 2.667 1.332 9.000 3658.357 2K 1.079 1.309 2.000 2.508 1.367 82.000 3560.092 4K 1.077 1.314 2.000 3.000 1.349 82.000 3655.274 Transformer 1K 1.127 1.553 2.615 4.131 3.278 301 55.244 2K 1.129 1.575 2.502 6.009 4.023 573 54.166 4K 1.129 1.538 2.600 5.513 3.626 573 54.745 Binary 1K 1.057 1.223 1.667 2.000 1.218 5.000 8.741 2K 1.059 1.232 1.750 2.000 1.217 5.000 8.463 4K 1.058 1.227 1.667 2.000 1.218 5.000 8.730 Embed 1K 1.053 1.224 1.750 2.000 1.225 5.000 660.776 2K 1.053 1.223 1.750 2.000 1.218 5.000 711.218 4K 1.056 1.222 1.667 2.000 1.217 6.000 734.611 FACE 1K 1.117 1.222 1.375 1.506 1.186 6.844 46.585 2K 1.114 1.223 1.391 1.544 1.305 242.411 46.456 4K 1.121 1.224 1.375 1.517 1.194 21.490 46.482 QEmbed 1K 1.078 1.221 1.375 1.500 1.132 4.000 921.178 2K 1.073 1.222 1.391 1.526 1.070 4.000 734.690 4K 1.075 1.230 1.455 1.600 1.070 5.000 749.715
QEmbed achieves the lowest mean Q-errors, ranging from 1.070 to 1.132, and limits the maximum Q-error to 4.000 on both the 1K and 2K workloads. It also records the lowest 90th percentile Q-errors among the evaluated models. The Binary model has the lowest inference time, requiring less than 9 ms, whereas QEmbed requires more execution time. However, its inference time is comparable to the Embed model while providing lower mean and maximum Q-errors. Census Dataset: Table 5 presents the results on the Census dataset, which is the most challenging dataset evaluated in this study due to its large number of categorical attributes and the presence of attributes with substantially larger value domains than those in the other datasets. These characteristics increase the complexity of modeling attribute dependencies and make accurate cardinality estimation more difficult. On this dataset, the Transformer achieves the best overall performance. For the 4K workload, it records the lowest maximum Q-error of 22.531 while maintaining lower inference latency than QEmbed. This suggests that the Transformer is more effective at capturing the complex attribute relationships present in this dataset. Compared with the Transformer and Binary models, QEmbed achieves lower estimation accuracy and higher inference latency on the Census dataset. The large number of attributes, together with attributes having large value domains,
14
Pooja Rajput and Suman Banerjee
Table 5: Performance comparison on the Census dataset. Technique Query Med. 75th 90th 95th Mean MaxQE Lat.(ms) Sampling 1K 1.172 3.000 61.000 224.450 23.500 2705 4.899 2K 1.172 3.000 61.100 197.100 23.147 3214 5.346 4K 1.164 3.000 67.200 227.000 29.000 4319 3.493 MaxHistDiff 1K 4.428 33.917 165.562 319.538 81.671 16700 620 2K 4.826 33.874 170.439 320.853 2027.851 3811796 659 4K 4.719 36.090 176.710 338.361 1062.159 3811796 641 BayesNet 1K 1.246 1.810 5.377 290.150 179.441 13455 97209 2K 1.245 1.869 5.213 448.150 180.521 14137 28327 4K 1.258 1.926 6.275 480.100 207.740 18480 86730 Transformer 1K 1.154 1.221 1.722 1.722 1.212 8.044 8055 2K 1.149 1.217 1.427 1.616 1.206 22.575 463 4K 1.142 1.226 1.435 1.649 1.206 22.531 432 Binary 1K 1.119 1.301 1.670 2.232 1.185 313.482 615 2K 1.119 1.309 1.757 2.340 1.163 313.482 587 4K 1.114 1.298 1.713 2.284 1.225 313.482 591 Embed 1K 1.187 1.458 2.056 2.938 1.028 865.917 1006 2K 1.191 1.456 2.125 3.004 1.026 46669 1309 4K 1.180 1.442 2.026 2.920 1.044 46669 1041 QEmbed 1K 1.160 1.420 1.995 2.641 1.168 100.000 6245 2K 1.157 1.454 1.953 2.589 1.137 2130 6243 4K 1.163 1.449 1.969 2.658 1.223 399.000 6246
increases the complexity of the proposed MADE-based hybrid encoding model, making optimization more challenging and reducing estimation accuracy. Nevertheless, QEmbed remains substantially more robust than the Embed model. On the 4K workload, QEmbed limits the maximum Q-error to 399, whereas the Embed model reaches more than 46,000. These results indicate that the proposed hybrid encoding effectively reduces extreme estimation errors, although the Transformer remains the most suitable model for this particular dataset. Summary of Observations The experimental results highlight the differences among the evaluated models in terms of estimation accuracy, inference time, and model size. – Accuracy: The performance of the baseline methods varies across the datasets. Sampling, MaxHistDiff, and the Embed model perform well on some workloads but produce large estimation errors for others. In comparison, QEmbed provides more consistent results across different datasets and records fewer large estimation errors. – Inference Time: Sampling-based methods and simple neural models have the lowest inference time. In contrast, Bayesian network-based methods require much longer execution time. QEmbed requires more inference time than the faster baseline models, but it provides lower estimation errors on most datasets. – Space Efficiency: The input encoding affects both model size and scalability. One-hot encoding increases the input dimension for columns with many
QEmbed: Cardinality Estimator for Efficient Query Processing
15
distinct values, whereas dense embeddings may not represent low-cardinality columns effectively. QEmbed uses discrete encoding for low-cardinality columns and dense embeddings for high-cardinality columns, which helps reduce the input size while preserving useful feature representations.
5
Concluding Remarks
In this paper, we presented QEmbed, a deep learning-based cardinality estimator for relational query processing. QEmbed combines an autoregressive model with a hybrid encoding scheme that uses discrete encoding for low-cardinality columns and dense embeddings for high-cardinality columns. The proposed model was evaluated on multiple real-world datasets and compared with several learningbased and traditional cardinality estimation methods. The experimental results show that QEmbed achieves competitive estimation accuracy while maintaining a reasonable inference time. For future work, the model can be extended to support dynamic data updates, and its integration with query optimization techniques can be investigated.
References 1. Yang, Z., Liang, E., Kamsetty, A., Wu, C., Duan, Y., Chen, X., Abbeel, P., Hellerstein, J.M., Krishnan, S., Stoica, I.: Deep Unsupervised Cardinality Estimation. Proc. VLDB Endow. 13(3) (2020) 2. Wu, Z., Shaikhha, A., Zhu, R., Zeng, K., Han, Y., Zhou, J.: BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation arXiv preprint arXiv:2012.14743 (2020) 3. Kim, K., et al.: Learned cardinality estimation: An in-depth study. Proceedings of the 2022 International Conference on Management of Data (2022) 4. Getoor, L., Taskar, B., Koller, D.: Selectivity Estimation Using Probabilistic Models. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 461–472 (2001) 5. Tzoumas, K., Deshpande, A., Jensen, C.S.: Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions. Proc. VLDB Endow. 4(11), 852–863 (2011) 6. Germain, M., Gregor, K., Murray, I., Larochelle, H.: MADE: Masked Autoencoder for Distribution Estimation. In: Proceedings of the 32nd International Conference on Machine Learning (ICML), pp. 881–889 (2015) 7. Lohman, G.: Is Query Optimization a “Solved” Problem? In: Proceedings of the Workshop on Database Query Optimization, vol. 13, p. 10 (2014) 8. Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., Neumann, T.: How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9(3), 204–215 (2015) 9. Ioannidis, Y.: The History of Histograms (Abridged). In: Proceedings of the 29th International Conference on Very Large Data Bases (VLDB), pp. 19–30 (2003) 10. Lipton, R.J., Naughton, J.F., Schneider, D.A.: Practical Selectivity Estimation Through Adaptive Sampling. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 1–11 (1990) 11. Olken, F., Rotem, D.: Random Sampling from Database Files: A Survey. In: International Conference on Scientific and Statistical Database Management, pp. 92–111. Springer (1990)
16
Pooja Rajput and Suman Banerjee
12. Wu, W., Naughton, J.F., Singh, H.: Sampling-Based Query Re-optimization. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 1721–1736 (2016) 13. Wu, X., Jampani, K., Xu, X., Jermaine, C.: Random Sampling over Joins Revisited. Proc. VLDB Endow. 11(7), 799–812 (2018) 14. Ioannidis, Y.E., Christodoulakis, S.: On the Propagation of Errors in the Size of Join Results. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 268–277 (1991) 15. Hasan, S., Thirumuruganathan, S., Augustine, J., Koudas, N., Das, G.: Deep Learning Models for Selectivity Estimation of Multi-attribute Queries. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 1035–1050 (2020) 16. Harmouch, H., Naumann, F.: Cardinality Estimation: An Experimental Survey. Proc. VLDB Endow. 11(4), 499–512 (2017) 17. Han, Y., Wu, Z., Wu, P., Zhu, R., Yang, J., Tan, L.W., Zeng, K., Cong, G., Qin, Y., Pfadler, A., et al.: Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. arXiv preprint arXiv:2109.05877 (2021) 18. Yang, Z., Kamsetty, A., Luan, S., Liang, E., Duan, Y., Chen, X., Stoica, I.: NeuroCard: One Cardinality Estimator for All Tables. arXiv preprint arXiv:2006.08109 (2020) 19. Wang, X., Qu, C., Wu, W., Wang, J., Zhou, Q.: Are we ready for learned cardinality estimation? Proceedings of the VLDB Endowment 14(9), 1640–1654 (2021) 20. U.S. Department of Transportation: Vehicle, Snowmobile, and Boat Registrations. https://catalog.data.gov/dataset/vehicle-snowmobile-and-boat-registrations (2025) 21. Blackard, J.A.: Covertype Dataset. UCI Machine Learning Repository. https://archive.ics.uci.edu/ml/datasets/covertype (1998) 22. Cattral, R., Oppacher, F.: Poker Hand Dataset. UCI Machine Learning Repository. https://archive.ics.uci.edu/dataset/158/poker+hand (2002) 23. Meek, C., Thiesson, B., Heckerman, D.: US Census Data (1990) Dataset. UCI Machine Learning Repository. https://archive.ics.uci.edu/dataset/116/us+census+data+1990 (2001) 24. Hilprecht, B., Schmidt, A., Kulessa, M., Molina, A., Kersting, K., Binnig, C.: DeepDB: Learn from Data, Not from Queries! Proceedings of the VLDB Endowment 13(7), 992–1005 (2020) 25. Kipf, A., Kipf, T., Radke, B., Leis, V., Boncz, P., Kemper, A.: Learned Cardinalities: Estimating Correlated Joins with Deep Learning. arXiv preprint arXiv:1809.00677 (2018) 26. Poosala, V., Ioannidis, Y. E.: Selectivity estimation without the attribute value independence assumption. Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB), 486–495 (1997) 27. Hebrail, G., Berard, A.: Individual household electric power consumption data set. UCI Machine Learning Repository (2012) 28. Wang, J., Chai, C., Liu, J., Li, G.: FACE: A normalizing flow based cardinality estimator. Proc. VLDB Endow. 15(1), 72–84 (2021) 29. Moerkotte, G., Neumann, T., Radke, G.: Preventing bad plans by bounding the impact of cardinality estimation errors. Proc. VLDB Endow. 2(1), 982–993 (2009) 30. Zeng, T., et al.: PRICE: A pretrained model for cross-database cardinality estimation. arXiv preprint arXiv:2406.01027 (2024) 31. Zhu, Y., Zhang, J., Li, G., Feng, J.: A Lightweight Learned Cardinality Estimation Model. IEEE Trans. Knowl. Data Eng. (2025)