QEmbed: A Deep Learning Based Cardinality Estimator for Efficient Query Processing

Pooja Rajput; Suman Banerjee

Source-linked AI summary

QEmbed: A Deep Learning Based Cardinality Estimator for Efficient Query Processing

Pooja Rajput, Suman Banerjee

arXiv:2609.12535v1Sep 11, 2026cs.DB

TL;DR

Traditional estimators and learned models face challenges with attribute dependencies and mixed-cardinality data, making accurate selectivity estimation difficult. QEmbed combines MADE with hybrid encoding to model joint distributions; on the 4K workload it reports a maximum Q-error of 11.0 while incurring higher latency than basic Embed and Binary models.

Problem
Mixed-cardinality datasets make it difficult for learned estimators to balance compact memory usage and accurate selectivity estimation.
Source: §1 · p. 2
Method
QEmbed extends MADE with discrete encoding for low-cardinality columns and dense embeddings for high-cardinality columns.
Source: §1 · p. 2, Summary of Observations · p. 15
Results
On the 4K workload, QEmbed reduces maximum Q-error to 11.0 and achieves the lowest 90th percentile, 95th percentile, and mean errors.
Source: §4.4 · p. 11
Takeaways & Limitations
QEmbed's query-aware embeddings are associated with preventing severe worst-case errors seen in baselines, though latency is higher than for basic Embed and Binary models.
Source: §4.4 · p. 11
On the Census 4K workload, the Transformer has a lower maximum Q-error of 22.531 and lower inference latency than QEmbed.
Source: §4.4 · p. 13

Abstract

from arXiv · show

Cardinality estimation is at the core of any commercial database system for efficient query processing. Over the decades, non-learning-based 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.

1 Introduction

Cardinality estimation supports efficient query planning, but traditional approaches can fail on complex queries and learned models still face representation challenges on mixed-cardinality data. QEmbed combines MADE with hybrid encoding, and the paper reports competitive performance with fewer extreme errors than Embed.

1 Introduction

Histograms and sampling have been widely used in commercial and open-source database systems over the past three to four decades.Cardinality estimates inform query execution plans.Source: §1 · p. 1
Traditional estimation errors can exceed a factor of 10,000 on complex queries, while supervised query models may struggle on unseen queries.The paper contrasts query-feature regression approaches with unsupervised models of joint attribute distributions.Source: §1 · p. 2
Mixed low- and high-cardinality attributes make it difficult to balance compact memory usage with accurate selectivity estimation.The paper identifies this as a challenge for real-world datasets.Source: §1 · p. 2
One-hot encoding is sparse and computationally costly for high-cardinality attributes, whereas binary encoding lacks detail for low-cardinality attributes.The paper motivates a hybrid scheme to address these encoding trade-offs.Source: §1 · p. 2
QEmbed combines a MADE architecture with hybrid encoding to represent datasets containing both low- and high-cardinality attributes.The paper reports competitive estimation performance across diverse query workloads and substantially reduced extreme errors compared with Embed.Source: §1 · p. 2

2 Problem Definition

The paper defines cardinality and selectivity for conjunctive queries over relational attributes. It motivates modeling attribute dependencies because traditional independence assumptions can miss correlations, and examines encoding choices within a joint-distribution model.

2 Problem Definition

A selection query is a conjunction of predicates on attributes; predicates may specify equality, ranges, or set membership.Each attribute has a finite domain derived from the dataset's distinct values.Source: §2 · p. 3
Card(Q) counts relation tuples satisfying all predicates, while Sel(Q) is the fraction of tuples that satisfy them.The paper frames selectivity estimation as computing that fraction without scanning the full dataset.Source: §2 · p. 3
Traditional histograms and sampling usually assume attribute independence, which ignores correlations and can produce large errors on complex multi-attribute queries.The proposed approach models the joint probability distribution instead.Source: §2 · p. 3
The paper uses MADE to factorize the joint distribution into conditional probabilities and evaluates how encoding choices affect estimation accuracy across datasets.This supports learning attribute dependencies directly.Source: §2 · p. 3

3 Proposed Methodology: QEmbed

QEmbed estimates selectivity by modeling relational data as an autoregressive joint distribution. Its stages combine cardinality-dependent encoding, masked processing, and conditional-probability outputs, with point-query evaluation and progressive sampling for complex ranges.

3.1 Overview of the QEmbed Architecture

QEmbed treats cardinality estimation as unsupervised density estimation and factorizes tuple probability by conditioning each attribute on its predecessors.This autoregressive structure is intended to capture cross-attribute dependencies.Source: §3.1 · pp. 3–4

3.2 Stage 1: Hybrid Encoding and Input Layer

A configurable threshold routes low-cardinality domains to one-hot encoding and high-cardinality domains to dense embeddings.The hybrid preserves exact categorical boundaries for smaller domains while representing larger domains compactly.Source: §3.2 · p. 4

3.3 Stage 2: Masked Hidden Layers and Structural Connections

A four-layer masked fully connected network uses binary masks to enforce the autoregressive condition and prevent access to future attributes.The input also bypasses the hidden layers through a shortcut to the output layer.Source: §3.3 · pp. 4–5

3.4 Stage 3: Output and Unsupervised Training

A softmax layer outputs conditional probabilities, and unsupervised training minimizes negative log-likelihood.Categorical attributes use cross-entropy, while binary attributes use binary cross-entropy; embeddings are updated jointly with hidden layers.Source: §3.4 · p. 5

3.5 Query Inference and Selectivity Estimation

Point-query selectivity uses a single forward pass, while complex range queries use progressive sampling from the learned distribution.The paper states that point-query computation takes O(1) time; progressive sampling draws valid tuples autoregressively.Source: §3.5 · p. 5

4 Experimental Evaluation

The experiments compare QEmbed with established cardinality estimators across five datasets and evaluate estimation accuracy, latency, and training behavior. QEmbed generally reduces large estimation errors, with a latency trade-off and weaker results on the wide Census schema.

4.1 Datasets; 4.2 Baseline Methods; 4.3 Details of the Experimentation

The evaluation uses Forest, Power, DMV, Poker, and Census and compares QEmbed with sampling, histogram, Bayesian-network, autoregressive, and flow-based methods.Queries use randomly selected attributes and tuple-derived filter values; zero-cardinality queries are discarded.Source: §4.1 · p. 6, §4.2 · pp. 6–7, Query Distribution · p. 8

4.3 Details of the Experimentation

QEmbed consistently reaches the lowest training entropy across the five datasets and reaches a low-entropy solution earlier than competing models.On Forest it reaches about 75.29 bits at epoch 49 in 22,321 seconds; on DMV it reaches 19.24 bits in 22,804 seconds, versus over 449,767 seconds for Binary and 481,311 seconds for Embed.Source: Training Model Performance · pp. 8–9, Figure 2 · p. 9

4.4 Experimental Results and Discussion

On Forest, QEmbed reduces maximum Q-error to 11.0 on the 4K workload, versus 2,840 for Embed, while adding latency over Embed and Binary.It also has the lowest 90th, 95th percentile, and mean errors, and remains orders of magnitude faster than BayesNet.Source: Table 1 · p. 10, §4.4 · p. 11
On Power, QEmbed has median Q-error 1.000 and maximum 200; Embed’s maximum is 6.000, but QEmbed has lower 75th-percentile and mean Q-errors.FACE’s 95th-percentile Q-error is about 1.20, but its maximum exceeds 440,000; BayesNet takes more than 100 seconds per workload.Source: §4.4 · pp. 11–12, Table 2 · p. 11
On DMV, QEmbed has the lowest mean, 90th-, and 95th-percentile Q-errors, with maximum Q-error 29.333 on the 1K workload and inference time about 1,300 ms.The Embed model is faster than 1 ms per query but has 95th-percentile Q-error above 250.Source: §4.4 · p. 12, Table 3 · p. 12
On Poker, Sampling and MaxHistDiff reach maximum Q-errors of 50,091, while FACE’s maximum exceeds 242 on the 2K workload despite low mean error.Source: §4.4 · p. 12, Table 4 · p. 13
QEmbed’s mean Q-errors range from 1.070 to 1.132, with maximum Q-error 4.000 on both 1K and 2K workloads; it is slower than Binary but comparable to Embed.Across datasets, QEmbed also provides more consistent estimates and records fewer large errors, while requiring more inference time than faster baselines.Source: §4.4 · p. 13, Summary of Observations · p. 14
On Census, Transformer has the best overall performance; on the 4K workload its maximum Q-error is 22.531 with lower latency than QEmbed.QEmbed nevertheless limits maximum Q-error to 399, versus more than 46,000 for Embed; the dataset’s wide schema and large domains make optimization harder.Source: §4.4 · pp. 13–14, Table 5 · p. 14

5 Concluding Remarks

QEmbed combines an autoregressive model with hybrid encoding and achieves competitive estimation accuracy with reasonable inference time. The paper identifies dynamic updates and query-optimizer integration as future directions.

QEmbed combines an autoregressive model with discrete encoding for low-cardinality columns and dense embeddings for high-cardinality columns.Source: §5 · p. 15
Across multiple real-world datasets, QEmbed achieves competitive estimation accuracy while maintaining reasonable inference time.Source: §5 · p. 15
Future work could extend QEmbed to dynamic data updates and investigate integration with query optimization techniques.Source: §5 · p. 15