PaperlayerView exact revision on arXiv

Source-linked AI summary

Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation

Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, Bin Cui

arXiv:2109.05877v3cs.DBcs.AI

TL;DR

The paper asks how much advanced CardEst methods improve query optimizers in real-world DBMS settings, where prior evidence is limited. It builds a realistic benchmark and integrates representative methods into PostgreSQL for end-to-end evaluation. The results identify practical method families and show that P-Error better reflects query execution performance than Q-Error.

  • Problem

    Prior studies do not systematically establish how advanced CardEst methods improve query optimizer performance in real-world settings, especially beyond algorithm-level metrics and simplified workloads.

  • Method

    The paper constructs the STATS and STATS-CEB benchmark, integrates representative CardEst methods into PostgreSQL, and evaluates end-to-end performance and practicality.

  • Results

    ML-based data-driven methods, particularly PGM-based methods, can improve end-to-end performance, while query-driven methods provide little improvement and are impractical for frequent-update databases.

  • Takeaways & Limitations

    P-Error provides a potential alternative to Q-Error because it better corresponds to query execution time and query plan quality.

  • Takeaways & Limitations

    The evaluation excludes LIKE queries on string attributes and focuses on numerical and categorical selection queries.

Abstract

from arXiv · show

Cardinality estimation (CardEst) plays a significant role in generating high-quality query plans for a query optimizer in DBMS. In the last decade, an increasing number of advanced CardEst methods (especially ML-based) have been proposed with outstanding estimation accuracy and inference latency. However, there exists no study that systematically evaluates the quality of these methods and answer the fundamental problem: to what extent can these methods improve the performance of query optimizer in real-world settings, which is the ultimate goal of a CardEst method. In this paper, we comprehensively and systematically compare the effectiveness of CardEst methods in a real DBMS. We establish a new benchmark for CardEst, which contains a new complex real-world dataset STATS and a diverse query workload STATS-CEB. We integrate multiple most representative CardEst methods into an open-source database system PostgreSQL, and comprehensively evaluate their true effectiveness in improving query plan quality, and other important aspects affecting their applicability, ranging from inference latency, model size, and training time, to update efficiency and accuracy. We obtain a number of key findings for the CardEst methods, under different data and query settings. Furthermore, we find that the widely used estimation accuracy metric(Q-Error) cannot distinguish the importance of different sub-plan queries during query optimization and thus cannot truly reflect the query plan quality generated by CardEst methods. Therefore, we propose a new metric P-Error to evaluate the performance of CardEst methods, which overcomes the limitation of Q-Error and is able to reflect the overall end-to-end performance of CardEst methods. We have made all of the benchmark data and evaluation code publicly available at https://github.com/Nathaniel-Han/End-to-End-CardEst-Benchmark.

1 INTRODUCTION

The paper addresses whether advanced CardEst methods improve query optimization in real-world DBMS settings. It introduces a realistic benchmark, evaluates methods end to end in PostgreSQL, and proposes P-Error to better capture plan quality than Q-Error.

  • Research Gap: Existing evaluations do not adequately represent complex real-world data or diverse multi-table query workloads.Prior workloads often use limited attributes, single-table settings, or star joins, missing skewness, correlations, and varied join forms.
  • Research Gap: End-to-end evaluation is needed because estimation accuracy and inference latency alone do not determine query execution time.Query plan quality and CardEst inference cost both affect end-to-end performance in a real DBMS.
  • Contributions: The benchmark combines the complex real-world STATS dataset with the diverse multi-table STATS-CEB query workload.STATS includes skewness, correlations, many attributes, and complicated joins; STATS-CEB varies table counts, cardinalities, and join types.
  • Contributions: The evaluation integrates representative traditional and ML-based CardEst methods into PostgreSQL and measures query time alongside applicability factors.The platform supports end-to-end comparison in a real open-source DBMS, including inference and other practical considerations.
  • Findings: ML-based data-driven methods can markedly improve numerical and categorical workloads, while most other methods barely improve the PostgreSQL baseline.Among data-driven methods, probabilistic graphical models outperform deep models in end-to-end query time and practicality.
  • Findings: P-Error relates sub-plan estimation accuracy to query plan quality and correlates more closely with end-to-end query time than Q-Error.The paper proposes P-Error as a potential substitute for Q-Error and a better optimization objective for learned CardEst methods.

2 PRELIMINARIES AND BACKGROUND

The paper frames CardEst as estimating filtered result sizes over relational or joined tables. Its scope focuses on numerical and categorical selection queries, excluding LIKE queries for stated evaluation reasons.

  • CardEst Definition: CardEst estimates the exact number of records satisfying all predicates in a selection query without executing the query.Queries are represented by attribute-specific constraint regions over categorical or continuous domains.
  • CardEst Definition: The paper treats each attribute as categorical or continuous and allows the underlying table to be single or joined.An unconstrained attribute uses its full domain as the constraint region.
  • Evaluation Scope: The evaluation concentrates on selection queries over numerical and categorical attributes.LIKE queries on string attributes are excluded because commercial methods often use uninformative magic numbers and statistical solutions differ in focus.

CardEst Algorithms:

CardEst methods span traditional histograms and sampling, query-driven ML models, and data-driven probabilistic models. Existing benchmarks often simplify data distributions, schemas, or workloads, limiting comprehensive evaluation.

  • Method classes: CardEst methods are classified into traditional, ML-based query-driven, and ML-based data-driven approaches.Traditional approaches include histograms and sampling; learned approaches model query cardinalities directly or represent table distributions.
  • Benchmark limitations: Synthetic benchmarks simplify attribute distributions through assumptions such as uniformity and independence, unlike skewed and correlated real-world data.This makes them less suitable for evaluating CardEst methods under realistic distributional challenges.
  • Benchmark limitations: JOB-LIGHT uses only eight numerical or categorical attributes across six tables with star joins, limiting coverage of complex multi-table estimation.Its workload also omits broader join forms and conditions found in practical settings.
  • Benchmark limitations: Existing CardEst benchmarks are insufficient for comprehensively evaluating the performance of the growing range of statistical-model-based algorithms.Some newer evaluations are restricted to single-table scenarios, which do not reflect practical multi-table settings.

3 OUR NEW BENCHMARK

The benchmark combines the real-world STATS dataset with the hand-picked STATS-CEB workload to represent complex data and diverse multi-table queries. Compared with simplified IMDB and JOB-LIGHT settings, it expands distributional complexity, join diversity, query space, and cardinality range.

  • Dataset: STATS is an anonymized Stack Exchange dump with 8 tables, 71 numerical or categorical attributes, and 658MB of storage.Its full outer join size is four orders of magnitude larger than the simplified IMDB dataset.
  • Dataset: STATS has stronger distribution skewness and attribute correlation than simplified IMDB, with 3× more attributes and larger domain sizes.These properties make its joint probability distribution harder to model.
  • Join settings: STATS supports 2-to-8-table joins with chain, star, and mixed forms, including both PK-FK and FK-FK join keys.This is richer than simplified IMDB, which contains only five primary-key–foreign-key star-join relations.
  • Workload construction: STATS-CEB contains 146 hand-picked queries derived from 70 representative join templates, using predicates designed to reflect real-world semantics.Cyclic and non-equal joins are excluded because many evaluated methods do not support them or process them like many-to-many joins.
  • Workload diversity: STATS-CEB has twice as many queries as JOB-LIGHT and 3× more join templates, covering wider joined-table counts and more diverse query structures.It includes chain and mixed joins plus many-to-many FK-FK joins, whereas JOB-LIGHT contains only star and one-to-many PK-FK joins.
  • Workload scale: STATS-CEB reaches 16 distinct filter predicates and a true cardinality of 20 billion, expanding the workload beyond JOB-LIGHT.The predicate count is 4× larger and the largest query cardinality is 3× larger than JOB-LIGHT; the overall cardinality range is an order of magnitude larger.

4 EVALUATION PLAN

The evaluation integrates representative CardEst methods from three classes into PostgreSQL and examines their behavior across estimation, planning, and practical deployment dimensions. It emphasizes end-to-end query time because sub-plan estimates affect physical plan choices and inference cost also matters.

  • Methods: The evaluation selects twelve representative CardEst algorithms spanning traditional, ML-based query-driven, and ML-based data-driven classes.The methods are chosen to represent different statistical models and state-of-the-art performance within their model categories.
  • Traditional methods: PostgreSQL provides the traditional baselines: one-dimensional PostgreSQL histograms, MultiHist, UniSample, WJSample, and PessEst.These cover histogram-based, sampling-based, and other traditional estimation directions.
  • ML-based methods: The learned methods include query-driven neural and regression models and data-driven models such as NeuroCard, BayesCard, DeepDB, and FLAT.Query-driven models map featurized queries to cardinalities, while data-driven methods model the joint distribution of table attributes.
  • ML-based methods: NeuroCard models the joint distribution with a 4-layer DNN and estimates query probabilities through progressive sampling with a sampling size of 8,000.All tables are learned together using a single masked auto-encoder.
  • Integration: The planner evaluates cardinalities over the sub-plan query space, where estimates influence scan choices, join orders, and join methods.For a multi-table query, sub-plans cover subsets of tables; their estimates determine the final execution plan.
  • Evaluation metrics: End-to-end time includes query plan generation and physical execution, with TrueCard injecting true sub-plan cardinalities as a baseline.This measures the combined effects of query plan quality and CardEst inference cost.

5 HOW GOOD ARE THE CARDEST METHODS?

End-to-end evaluation shows that CardEst effectiveness depends on method family, workload, query structure, and the relative importance of estimation errors. Data-driven methods often improve PostgreSQL, but scalability, workload shift, and physical-operation choices limit reliable gains.

  • Overall End-to-End Performance: Most ML-based data-driven methods outperform PostgreSQL, while traditional and query-driven methods generally provide little or unstable end-to-end improvement.BayesCard, DeepDB, and FLAT benefit from modeling data distributions; histogram and sampling methods can perform worse than PostgreSQL, whereas PessEst is significantly better.
  • Overall End-to-End Performance: Query-driven methods remain comparable to PostgreSQL: MSCN is 4.6% faster on JOB-LIGHT and 19.7% faster on STATS-CEB, while LW-XGB is slower.The paper attributes their unsatisfactory performance to complex join-distribution modeling, limited training queries, and workload shift between training and testing.
  • Overall End-to-End Performance: 7−13% improvement over PostgreSQL is achieved by BayesCard, NeuroCard_E, DeepDB, and FLAT on JOB-LIGHT.On STATS-CEB, BayesCard, DeepDB, and FLAT improve PostgreSQL by 37−48%, whereas NeuroCard_E does not show the same advantage.
  • Overall End-to-End Performance: Data-driven methods significantly outperform PostgreSQL when divide-and-conquer models capture correlations within subsets of joined tables without modeling the full outer join.This design balances richer within-subset correlation modeling with lower complexity than constructing a model over all tables.
  • Different Query Settings: Improvement gaps increase with the number of join tables, and BayesCard achieves near-optimal gains through five tables but little improvement from six tables onward.The results indicate that estimation quality declines for queries involving more joined tables.
  • Different Query Settings: Accurate estimates for large-cardinality sub-plans and correct physical operations can matter more than globally accurate estimates or optimal join order.For Q57, FLAT selects a hash join roughly twice as fast as BayesCard’s merge join; one sub-optimal physical operation is 68% slower, whereas a sub-optimal plan is only 1% slower.

6 WHAT OTHER ASPECTS OF CARDEST METHODS MATTER?

Beyond execution-time gains, CardEst methods must balance inference latency, model size, training time, and update efficiency and accuracy for practical DBMS deployment. The evaluation finds strong differences across methods, workloads, and database structures.

  • Inference Latency: Inference latency can determine end-to-end performance on OLTP workloads because planning time may offset faster query execution.On OLAP workloads, the impact of inference latency is trivial, whereas slow inference by NeuroCardᴱ, DeepDB, and FLAT worsens OLTP end-to-end performance.
  • Model Size and Training Time: BayesCard provides the strongest deployment practicality through fast inference, lightweight models, and short training time.Its Bayesian-network construction is roughly 100 times faster than the other three data-driven methods, and conditional independence reduces model redundancy.
  • Model Size and Training Time: Model size and training time rank as BayesCard << FLAT/DeepDB < NeuroCardᴱ on STATS-CEB.FLAT and DeepDB become less stable on highly correlated or high-attribute datasets, while NeuroCardᴱ is especially costly for the non-tree STATS schema.
  • Model Update: Query-driven CardEst methods are impractical for dynamic databases because updates require repeatedly collecting and executing workload queries.Generating the 146 STATS-CEB queries already takes more than ten hours, making frequent retraining difficult when data or workloads change.
  • Model Update: BayesCard takes 12s to update after insertion and updates more than 20 times faster than the other compared methods.The update experiment trains stale models on pre-2014 data, inserts the remaining data, and evaluates updated-model end-to-end query performance.
  • Model Update: BayesCard ranks first in both update speed and update accuracy, followed by DeepDB, FLAT, and NeuroCardᴱ.BayesCard incrementally updates compact model parameters, preserving original accuracy after insertion; larger learned structures update more slowly and may extrapolate poorly.

7 IS CURRENT METRIC GOOD ENOUGH?

The paper finds that Q-Error is insufficient as a standalone CardEst objective because it treats all sub-plan estimation errors equally, despite their different effects on query plans. It proposes P-Error, a plan-cost-level metric that better corresponds to end-to-end query execution time.

  • Problems with Q-Error: Smaller Q-Error does not necessarily produce shorter query execution time.The authors analyze Q-Error distributions and their relationship with execution time across JOB-LIGHT and STATS-CEB.
  • Problems with Q-Error: Q-Error treats estimation errors for all sub-plan queries equally, although their effects on the final query plan differ.Errors on large-cardinality sub-plans can matter more than errors on small-cardinality sub-plans.
  • An Alternative Metric: P-Error: P-Error provides a single plan-cost-level value, whereas Q-Error produces one value for each sub-plan query.The authors present P-Error as a potential substitute for Q-Error and a better optimization objective for learned CardEst methods.
  • An Alternative Metric: P-Error: P-Error measures CardEst effectiveness at the plan-cost level by comparing the cost of a plan generated from estimated cardinalities with a reference plan using true cardinalities.The metric uses DBMS cost estimates and can be computed quickly when true sub-plan cardinalities are precomputed.
  • An Alternative Metric: P-Error: P-Error comparisons remain possible when PostgreSQL’s cost model is inaccurate because the reference cost is identical across CardEst methods.On STATS, the true-cardinality plan is optimal for more than 98% of queries under PostgreSQL’s default cost model.
  • An Alternative Metric: P-Error: P-Error is more highly correlated with query execution time than Q-Error on the STATS-CEB workload.The reported correlations are 0.036 and 0.037 for Q-Error versus 0.810 and 0.838 for P-Error across the 50%–90% percentile range.

8 CONCLUSIONS AND FUTURE WORK

The paper concludes that CardEst evaluation should reflect end-to-end query optimization and practical deployment conditions, not estimation accuracy alone. It identifies benefits and limits of different method families and proposes directions for improving scope, adaptability, and scalability.

  • Conclusions: A new benchmark combines the complex real-world STATS dataset with the diverse STATS-CEB query workload.The benchmark is intended to reveal the advantages and disadvantages of different CardEst methods in realistic settings.
  • Conclusions: ML-based data-driven methods such as FLAT, DeepDB, and BayesCard can improve end-to-end query optimization by balancing estimation accuracy and inference time.The paper attributes this balance to tuning the strictness of independence assumptions.
  • Conclusions: Traditional methods and methods such as PessEst and BayesCard can support dynamic databases when their update speeds track rapid data changes.Existing ML-based query-driven methods are described as impractical for databases with frequent updates.
  • Challenges for multi-table join queries: Learning one large data-driven model over the full outer join of many tables has poor scalability and low accuracy.Data-driven CardEst performance also degrades as the number of joined tables increases.
  • Importance of different queries: Optimizing Q-Error alone does not always produce high-quality query plans because errors on different sub-plan queries have unequal importance.Accurate estimation of large-cardinality queries can matter more than accurate estimation of small-cardinality queries.
  • Future work: Future directions include supporting LIKE predicates and cyclic joins, combining models for different workload settings, and designing better join factorization methods.The proposed directions target broader query coverage, adjustable accuracy–cost trade-offs, and improved training/inference efficiency.
Loading 2109.05877v3…