Mitigating Cardinality Estimation Errors in Database Query Optimizers

331 concepts227 papers1 proposal

In database systems, the query optimizer acts as a navigator, selecting the most efficient execution plan from a vast space of possibilities. To make this choice, it relies on cardinality estimation—the task of predicting how many rows will be returned by various parts of a query. Despite its importance, cardinality estimation is often described as the "Achilles Heel" of query optimization by Leis et al., because even minor inaccuracies can lead to catastrophic performance degradation.

The Failure of the Uniformity Assumption

Traditional optimizers typically rely on simple statistics like histograms and the "uniformity assumption," which posits that data values are spread evenly across a range. However, Belussi et al. argue that real-world data is almost always "clumpy" or fractal in nature. When an optimizer assumes uniformity for skewed data, it fails to capture the true density of records, leading to estimates that can be off by orders of magnitude.

This problem is exacerbated by the "independence assumption," where the optimizer assumes that filters on different columns (e.g., City='New York' and ZipCode='10001') are unrelated. As Rabbani et al. and Li et al. point out, these correlations are common in complex datasets, and ignoring them causes the optimizer to significantly underestimate the size of intermediate results.

The Compounding Effect of Join Errors

The most dangerous aspect of estimation error is how it propagates. In a multi-table join, the output of one join becomes the input for the next. Li et al. and Wu et al. observe that small errors in early stages compound exponentially as more tables are added.

Underestimation is particularly damaging. As Wu et al. explain, if the optimizer believes a join will produce only a few rows, it might choose a nested-loop join or a memory-constrained hash join. If the actual row count is millions, the system may suffer from unmodeled disk spills, as noted by Carra et al., or fail to trigger more efficient multi-way join strategies described by Freitag et al..

From Heuristics to Learned Models

To move beyond flawed heuristics, recent research has turned to data-driven approaches. Marcus et al. and Zhong et al. have proposed using Deep Reinforcement Learning to either replace or "fix" traditional optimizers by learning from actual execution costs. Similarly, Ozcan et al. suggest that Large Language Models (LLMs) can serve as foundation models for cardinality estimation, capturing complex reasoning about data distributions that traditional statistics miss.

Other approaches focus on specialized structures. Wu et al. introduced FactorJoin, which treats joins as an inference problem on a factor graph to maintain accuracy in high-dimensional spaces. Yan proposed DistJoin, which decouples table models to handle both equi and non-equi joins efficiently.

Prioritizing Robustness Over Perfection

Given that perfect estimation is often infeasible, a parallel research direction focuses on robustness. Instead of searching for the single "optimal" plan based on a potentially wrong estimate, robust optimizers look for plans that perform well across a range of possible cardinalities.

Agarwal et al. and Xiu et al. developed frameworks like PARQO and PAR2QO, which use "plan-penalty profiles" to select strategies that are resilient to estimation errors. When the system is uncertain, it might choose a slightly more expensive plan that has a predictable execution time rather than a "risky" plan that could be 100x slower if the estimate is wrong.

Alternatively, some systems embrace re-optimization. Perron et al. argue that instead of chasing perfect pre-execution estimates, databases should detect estimation errors at runtime and re-plan the query dynamically. This "stop and fix" approach can recover significant performance lost to the "long tail" of complex, poorly estimated queries.

Bypassing the Cost Model

Finally, some researchers argue for bypassing the fallible cost model entirely for certain tasks. Perera et al. demonstrate that for index tuning, using Multi-Armed Bandits to learn from direct performance observations is more reliable than trusting an optimizer's internal estimates. By observing how long queries actually take, these "self-driving" systems avoid the pitfalls of the uniformity and independence assumptions altogether.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 225 papers
  2. Version 1 · 2026-10-04 · 206 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_cardinality_estimation_error_cbf0e9e8,
  title = {cardinality estimation error},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cardinality-estimation-error/rdr_cbf0e9e899eb4036a8e8be086a0a65d2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_cardinality_estimation_error_cbf0e9e8_v2,
  title = {cardinality estimation error},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cardinality-estimation-error/rdr_cbf0e9e899eb4036a8e8be086a0a65d2/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake