In the heart of every database management system (DBMS) lies the query optimizer—a complex engine responsible for determining the most efficient way to execute a SQL query. To choose the best execution plan, the optimizer must answer a fundamental question: "How many rows will this operation return?" This task, known as cardinality estimation (CardEst), is the "Achilles' heel" of database systems.
Traditional optimizers rely on simplified statistical summaries, like histograms, and the flawed assumption that data attributes are independent. When these estimates fail, the optimizer chooses disastrously slow execution plans, turning millisecond queries into minute-long bottlenecks. A growing body of research suggests that replacing these 40-year-old heuristics with machine learning can bridge the gap between predicted and actual performance.
The Cost of Inaccuracy
The query optimizer acts as a search algorithm over a space of possible execution plans. As Johannes Gehrke and others have demonstrated, inaccurate cardinality estimates lead to suboptimal join orders and improper data access methods.
The problem is not just the initial error, but how it grows. As Jeremy Chen and Ken Salem explore in their work on Cardinality Estimation Graphs, errors in the initial steps of a query plan compound exponentially as more tables are joined. A small mistake at the base of the execution tree can result in a total cost prediction that is off by several orders of magnitude, leading to what Hongzi Mao calls "tail catastrophes"—queries that take significantly longer than expected.
Modeling Data Distributions with Machine Learning
Learned cardinality estimators work by treating the database's data distribution as a density estimation problem. Instead of assuming independence between columns, these models learn the complex, non-linear correlations inherent in real-world data.
- Deep Learning and Attention: Models like ALECE, developed by Pengfei Li and Rong Zhu, use attention mechanisms to understand the relationships between SQL predicates and the underlying data. This allows the system to adapt to dynamic workloads where data is constantly updated.
- Probabilistic Models: BayesCard leverages Bayesian Networks to provide deep-learning-level accuracy while maintaining the interpretability and update speed of traditional methods.
- Generative Approaches: FLAT and ICE (by Xianglong Liu) repurpose multidimensional index structures or graphical models to serve as generative models, allowing for instant updates and high accuracy in dynamic environments.
Integrating Domain Knowledge and Robustness
A significant hurdle for learned models is their lack of "common sense" regarding database logic. Peizhi Wu and Zachary G. Ives addressed this with CORDON, which integrates primary keys and range logic directly into the training loop. This ensures the model respects fundamental database constraints, reducing the need for massive training datasets.
Furthermore, learned models often struggle with "Out-of-Distribution" (OOD) queries—queries that look nothing like the training data. The CardOOD framework by Jeffrey Xu Yu uses self-supervised learning to enforce logical partial orders between queries, making the estimator more robust when faced with unfamiliar workloads.
From Estimation to Optimization
While some researchers focus on replacing the estimator, others aim to replace the entire optimizer. Parimarjan Negi and Mohammad Alizadeh introduced Neo, an end-to-end neural optimizer that learns directly from execution latencies rather than just row counts.
However, replacing a production-grade optimizer is risky. A middle-ground approach, exemplified by Hongzi Mao’s Bao, uses machine learning to "steer" traditional optimizers. By providing per-query hints, Bao leverages the existing optimizer's strengths while steering it away from known weaknesses in its cost model. Similarly, Ryan Marcus proposes Superoptimization, where machine learning and program synthesis are used to find the absolute best execution strategy for highly repetitive, expensive analytical queries.
Why It Works
The shift toward learned cardinality estimation works because it moves from static heuristics to data-driven adaptation. Traditional models are built on assumptions that are almost always violated in practice (e.g., that a person's age is independent of their salary). ML models, by contrast, treat these correlations as the primary signal. By providing high-fidelity estimates, these models enable optimizers to select execution plans that perform near the theoretical limit of perfect data knowledge, often resulting in query speedups of 2x to 10x in complex, real-world environments.