In database systems, the query optimizer acts as a strategist, deciding the most efficient way to retrieve data. To choose the best plan, it must answer a fundamental question: "How many rows will this query return?" This task, known as cardinality estimation (CardEst), is the engine room of query optimization.
For decades, databases have relied on a simplifying assumption to make this calculation: attribute independence. If a user searches for a "Red Ferrari," the system looks at the probability of a car being red and the probability of a car being a Ferrari, then multiplies them. However, as Johannes Gehrke and others have noted, real-world data is rarely independent. Ferraris are disproportionately likely to be red. When an optimizer ignores these correlations, it produces estimates that are off by orders of magnitude, leading to "catastrophic" execution plans where a millisecond query takes hours.
The Failure of the Independence Assumption
Traditional systems use one-dimensional histograms to track the distribution of values in single columns. While fast, these summaries cannot see the links between columns. Amol Deshpande and his team demonstrated in Lightweight Graphical Models for Selectivity Estimation that this mismatch leads to significant underestimation of intermediate result sizes.
The problem compounds in complex queries. In RDF (graph) data, Eugene Siow showed in PRESTO that assuming independence between specific bound nodes or predicates fails because the underlying data structure—the graph—is inherently defined by relationships. Similarly, Parimarjan Negi argued in the development of Neo that human-engineered heuristics simply cannot capture the high-dimensional correlations present in modern datasets.
Modeling the Joint Distribution
The research direction has shifted toward learning the joint probability distribution of the data. Instead of treating columns as isolated islands, new models treat the entire table as a single, multi-dimensional entity.
- Probabilistic Graphical Models: Early breakthroughs used Bayesian Networks and junction trees. BayesCard leverages these to achieve deep-learning-level accuracy while remaining interpretable. By modeling dependencies as edges in a graph, these systems can "reason" about how a filter on one column affects the expected count in another.
- Deep Autoregressive Models: Zongheng Yang and Eric Liang introduced Naru, which uses deep unsupervised learning to decompose the joint distribution into a chain of conditional probabilities. This allows the model to capture complex, non-linear correlations that traditional histograms miss entirely.
- Diffusion and Copula Models: More recently, researchers have adapted generative AI techniques. Chuan Zhou introduced Accelerated Diffusion Cardest (ADC), which "downsizes" diffusion models to handle multilateral dependencies with tiny storage footprints. Meanwhile, Lankadinee Rathuwadu proposed CoLSE, which uses Copulas—a mathematical tool specifically designed to model the dependency structure between variables independently of their individual distributions.
Scaling to Joins and Dynamic Data
The "holy grail" of this field is extending these correlation-aware models to multi-table joins. Estimating join sizes is notoriously difficult because correlations can span across different tables. Rong Zhu and Andreas Pfadler addressed this in Glue by adaptively merging single-table estimates, while Peizhi Wu explored "data-agnostic" learning in GRASP, which predicts sizes based on previous query workloads rather than the raw data itself.
Furthermore, real-world databases are not static. Pengfei Li developed ALECE, an attention-based estimator that excels on dynamic workloads. By using attention mechanisms, the model can focus on the most relevant parts of a query and adapt as new data is inserted, ensuring that the optimizer's "brain" stays sharp even as the underlying data correlations shift over time.
Why It Works: Intuition over Heuristics
The shift from independence to correlation-aware modeling works because it replaces assumptions with evidence. Traditional CardEst assumes a "uniform and independent" world because it is computationally cheap. Learned models, however, treat the database as a signal to be compressed and understood.
By capturing the "shape" of the data—whether through the conditional chains of Naru, the structural shapes of Shape Statistics by Kashif Rabbani, or the dominant join paths in TKHist—these systems allow the query optimizer to see the data as it actually is, rather than as a collection of unrelated columns.