PaperlayerView exact revision on arXiv

Source-linked AI summary

Are We Ready For Learned Cardinality Estimation?

Xiaoying Wang, Changbo Qu, Weiyuan Wu, Jiannan Wang, Qingqing Zhou

arXiv:2012.06743v4cs.DBcs.LG

TL;DR

The paper asks whether learned cardinality estimators are ready for production, then evaluates their accuracy, costs, and behavior across static and dynamic settings. Learned methods are more accurate but remain costly, difficult to update and interpret, and therefore are not yet ready for real DBMS deployment.

  • Problem

    Cardinality estimation is a fundamental query-optimization problem, and the paper examines whether reported learned-model accuracy is sufficient for production deployment.

  • Method

    The study surveys learned methods and conducts unified experiments on static and dynamic environments, then analyzes when learned models fail and why.

  • Results

    Learned methods are more accurate than traditional methods, but often require high training and inference costs, struggle with frequent updates, and behave opaquely or unpredictably.

  • Takeaways & Limitations

    Current learned cardinality estimators are not ready for deployment in real database systems; future work should control their costs and improve trustworthiness.

  • Takeaways & Limitations

    Existing evaluations lacked direct method comparisons, standardized datasets and workloads, and extensive dynamic-environment testing.

Abstract

from arXiv · show

Cardinality estimation is a fundamental but long unresolved problem in query optimization. Recently, multiple papers from different research groups consistently report that learned models have the potential to replace existing cardinality estimators. In this paper, we ask a forward-thinking question: Are we ready to deploy these learned cardinality models in production? Our study consists of three main parts. Firstly, we focus on the static environment (i.e., no data updates) and compare five new learned methods with eight traditional methods on four real-world datasets under a unified workload setting. The results show that learned models are indeed more accurate than traditional methods, but they often suffer from high training and inference costs. Secondly, we explore whether these learned models are ready for dynamic environments (i.e., frequent data updates). We find that they cannot catch up with fast data up-dates and return large errors for different reasons. For less frequent updates, they can perform better but there is no clear winner among themselves. Thirdly, we take a deeper look into learned models and explore when they may go wrong. Our results show that the performance of learned methods can be greatly affected by the changes in correlation, skewness, or domain size. More importantly, their behaviors are much harder to interpret and often unpredictable. Based on these findings, we identify two promising research directions (control the cost of learned models and make learned models trustworthy) and suggest a number of research opportunities. We hope that our study can guide researchers and practitioners to work together to eventually push learned cardinality estimators into real database systems.

1 INTRODUCTION

The paper asks whether learned cardinality estimators are ready for production, addressing a fundamental query-optimization problem whose errors can severely degrade execution plans. It evaluates their accuracy, costs, dynamic behavior, and production risks.

  • Cardinality estimation predicts how many tuples satisfy query predicates, and inaccurate estimates can make query plans orders of magnitude slower.
  • Existing studies report improved accuracy but lack comprehensive comparisons, standardized workloads, and extensive evaluation under data updates.
  • The study compares five learned methods with nine traditional methods on four real-world datasets using unified datasets and workloads in static environments.
  • Learned methods provide promising accuracy, but most require 10 − 1000× more training and inference time than existing database systems, plus hyper-parameter tuning.
  • Under frequent updates, learned methods cannot keep up and produce large errors; under less frequent updates, no learned method consistently wins.
  • The paper identifies controlling learned-model costs and making them trustworthy as future research directions.

2 LEARNED CARDINALITY ESTIMATION

Learned cardinality estimation includes regression and joint-distribution approaches that use increasingly complex models to capture query-result relationships and data dependencies. Existing evaluations remain difficult to compare because methods, datasets, workloads, and update settings differ.

  • Cardinality estimation computes the number or percentage of tuples satisfying conjunctive query predicates.
  • New learned methods include advanced neural networks, gradient-boosted trees, sum-product networks, and deep autoregressive models.
  • Regression methods map query feature vectors to cardinality results, while joint-distribution methods construct a table distribution and estimate cardinalities from it.
  • Regression: Regression workflows train on featurized queries and labels, with features optionally enriched by data statistics such as samples.
  • Joint Distribution: Joint-distribution methods transform table data for training, answer queries through model requests, and update or retrain models after data changes.
  • Limitations of Existing Experiments: Existing studies lack direct method comparisons, standardized datasets and workloads, and comparable dynamic-environment evaluations.

3 EXPERIMENTAL SETUP

The experimental setup evaluates learned cardinality estimators with q-error across datasets and implementations designed for comparable single-table experiments. It combines a relative-error metric with released implementations and specified hardware platforms.

  • Q-error measures the factor by which an estimated cardinality differs from the actual cardinality.
  • The study uses datasets with varying sizes, categorical-to-numerical column ratios, and domain characteristics.
  • Q-error is symmetric, penalizes relative overestimates and underestimates equally, and is related to query-optimization plan quality.
  • The evaluation uses author-released implementations with modifications for experiments, including a single-table adaptation of MSCN.
  • Experiments run on a 16-CPU server, with selected neural models evaluated on both CPU and NVIDIA Tesla P100 GPU.

4 ARE LEARNED METHODS READY FOR STATIC ENVIRONMENTS?

In static environments, learned cardinality estimators generally improve accuracy over traditional methods, but their training, inference, and tuning costs often hinder production readiness. The evaluation uses unified workloads across real-world datasets to compare accuracy and operational costs.

  • 4.1 Setup: The study compares learned and traditional cardinality estimators using unified workloads and real-world datasets, evaluating both accuracy and production-related costs.The setup includes query-center and range-width variation, model tuning, accuracy tests, and measurements of training and inference time.
  • 4.2 Are Learned Methods More Accurate?: Learned methods are more accurate than traditional methods in almost all scenarios, with the best learned method achieving up to 14× better max q-error.Against three real database systems, the improvements are 28× on Census, 51× on Forest, 938× on Power, and 1758× on DMV.
  • 4.2 Are Learned Methods More Accurate?: Increasing the number of predicates degrades both methods’ performance, yet Best Learned consistently outperforms Best Traditional across predicate counts and operator types.The paper attributes degradation to lower selectivity and more complex attribute correlations.
  • 4.2 Are Learned Methods More Accurate?: Naru is the most robust and accurate learned method, while query-driven methods struggle when individually selective predicates combine into a very small conjunctive selectivity.LW-XGB and LW-NN lack features that capture this pattern well, whereas MSCN handles it better, possibly because of its input sample.
  • 4.3 What Is the Cost For High Accuracy?: Database systems collect statistics in seconds, whereas learned methods generally require minutes or hours for training; only some regression-based methods approach DBMS inference latency.Naru and DeepDB have much longer inference times, while MSCN and LW-XGB/NN can be competitive with database systems.
  • 4.3 What Is the Cost For High Accuracy?: Hyper-parameter tuning adds substantial cost: models with different settings can differ by up to 10^5 in max q-error, and tuning five Naru models on DMV can exceed 20 hours.Reducing Naru training time by 80% on DMV causes only slight degradation, but even one GPU epoch remains slower than database systems.

5 ARE LEARNED METHODS READY FOR DYNAMIC ENVIRONMENTS?

In dynamic environments, learned cardinality estimators must balance update time against accuracy, and their performance varies substantially with update frequency, dataset, and method. Experiments show that fast updates remain difficult, with no universally best learned method or consistently sufficient GPU remedy.

  • 5.1 Setup: Dynamic evaluation models stale and updated estimators across a time window, measuring 99th-percentile q-error while varying update frequency.Queries arriving during model updates use the stale model; later queries use the updated model.
  • 5.2 Which Method Performs the Best in Dynamic Environments?: DBMSs remain more stable as update frequency varies because their short update times leave almost all queries using updated statistics.When T=50 minutes on DMV, DBMS-A outperforms DeepDB by about 100× because DeepDB fails to capture correlation change well.
  • 5.3 What Is the Trade-off Between Updating Time and Accuracy?: Longer updating time increases the share of queries handled by stale models, creating a trade-off between update accuracy and overall dynamic accuracy.For Naru on Forest, “Dynamic” performance first improves and then worsens as epochs increase; more epochs improve the updated model but can hurt overall performance.
  • 5.2 Which Method Performs the Best in Dynamic Environments?: Method-specific failures arise from insufficient epochs, sampled labels, or unchanged-correlation assumptions that become inaccurate after updates.DeepDB’s assumption that underlying correlation remains unchanged can hurt when correlation changes.
  • 5.4 How Much Does GPU Help?: GPU improves some learned methods but does not uniformly solve dynamic updating costs or accuracy problems.GPU improves LW-NN by around 10× on Forest and 2× on DMV, and Naru by 2× on DMV, but not Naru on Forest.
  • 5.2 Which Method Performs the Best in Dynamic Environments?: Learned methods cannot keep up with fast updates, and no learned method wins consistently across datasets or update frequencies.LW-XGB is often best or comparable; Naru is stronger with infrequent updates, while LW-XGB performs better in more dynamic settings.

6 WHEN DO LEARNED METHODS GO WRONG?

Learned estimators can fail under changes in correlation, skewness, and domain size, while their opaque behavior can violate intuitive rules and complicate production deployment.

  • Correlation: All estimators produce larger q-errors as column correlation increases, with a dramatic 10–100× rise when columns become functionally dependent.This pattern holds across tested distribution and domain-size settings.
  • Distribution: Methods react differently to skewness: Naru’s maximum q-error increases for s > 1.0, whereas MSCN, LW-XGB/NN, and DeepDB show the opposite pattern.The authors relate this contrast to differences in model building blocks, including sampling and one-dimensional histograms.
  • Domain Size: Except for LW-NN, all methods incur larger errors on larger domains; Naru degrades 100× from domain size 1K to 10K, while MSCN and DeepDB degrade around 10× from 10 to 10K.The authors attribute Naru’s degradation partly to its embedding matrix consuming model capacity.
  • Production Implications: Black-box learned estimators create production challenges in debuggability, explainability, predictability, and reproducibility.Large errors are difficult to distinguish from bugs, and model upgrades are hard to explain to database users.
  • Logical Behavior: All new learned models except DeepDB violate at least one of five proposed cardinality-estimation rules.The rules concern stability, monotonicity, and consistency among other logical behaviors.

7 RESEARCH OPPORTUNITY

The paper identifies high cost and non-transparency as major deployment challenges and proposes controlling efficiency–accuracy tradeoffs and interpreting learned estimators as research directions.

  • High cost and non-transparency are identified as the two main challenges to applying learned cardinality estimators in DBMSs.
  • Balance the Efficiency-Accuracy Tradeoff: Efficiency–accuracy research should jointly consider model accuracy, training or updating time, and inference latency.Suggested approaches include sampling, incremental updates, early stopping, and model compression.
  • Balance the Efficiency-Accuracy Tradeoff: Hyper-parameter tuning should consider training and updating time rather than optimizing accuracy or loss alone.
  • Interpret Learned Estimators: Interpretability techniques such as surrogate models, saliency maps, influence functions, decision sets, rule summaries, and feature attribution could help explain black-box cardinality estimators.

8 MULTI-TABLE SCENARIO

Multi-table cardinality estimation extends existing learned methods but introduces challenges from table correlations, updates, exponentially many plans, and the accuracy–efficiency tradeoff.

  • Extend to Multi-table Scenarios: MSCN and DeepDB support joins natively or conditionally, while NeuroCard and materialized-view approaches extend Naru and LW-XGB/NN to multi-table estimation.
  • Additional Challenges: Training multi-table methods must capture correlations across joined tables and handle updates affecting one or more tables.The update problem also requires balancing update time against model accuracy.
  • Additional Challenges: The number of candidate query plans grows exponentially with the number of joins, making brute-force inference potentially unacceptably slow.Inferring only base-table cardinalities may propagate errors and reduce accuracy.
  • Additional Challenges: Multi-table inference therefore needs an intelligent budget-allocation strategy to balance accuracy and efficiency.

9 RELATED WORK

Related work spans traditional and learned single-table cardinality estimation, end-to-end query optimization, re-optimization, and methods for avoiding poor plans.

  • Single Table Cardinality Estimation: Histograms are the most common single-table cardinality-estimation approach, while sampling-based methods support more complex predicates than range predicates.
  • Single Table Cardinality Estimation: Some methods re-optimize difficult queries during inference to correct large errors, while others estimate upper bounds on intermediate join cardinalities to avoid poor plans.
  • End-to-End Query Optimization: End-to-end query-optimization research includes learning-based cost estimation, reinforcement learning for join ordering, direct plan generation, and open-source systems.

10 CONCLUSION

The paper finds that learned cardinality estimators are more accurate than traditional methods, but current systems remain unsuitable for real DBMS deployment because important practical and trust-related issues remain unresolved.

  • The paper identifies promising research opportunities to address the unresolved deployment challenges.
  • Learned cardinality estimation methods achieve higher accuracy than traditional methods.
  • Deployment remains blocked by low training and inference speed, hyper-parameter tuning, black-box behavior, illogical behavior, and frequent-update handling.
Loading 2012.06743v4…