DBScholar

Back to papers

Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs

Summary: Analyzes two classes of summary-based cardinality estimators for graph DBMS: optimistic estimators with precomputed statistics and pessimistic LP-based estimators. Using Cardinality Estimation Graphs (CEGs), demonstrates that path choice (max vs min weight) depends on query structure, unifying optimistic and pessimistic approaches for cross-optimization. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
12846
Venue
VLDB
Year
2022
Pagerank
7.7900444e-05
Overall Rank
3,070 | 78.94%
DOI
10.14778/3529337.3529339

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{chen_vldb22,
        title = {{Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs}},
        author = {Chen, Jeremy and Huang, Yuqing and Wang, Mushi and Salihoglu, Semih and Salem, Ken},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {8},
        pages = {1533--1545},
        doi = {10.14778/3529337.3529339},
        url = {https://doi.org/10.14778/3529337.3529339},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
1,876 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.5717543e-05
3,622 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.2465862e-05
5,576 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 6.1663946e-05
5,639 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.1385102e-05
6,257 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9397944e-05
7,386 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6273882e-05
8,232 Adaptive Factorization Using Linear-Chained Hash Tables 2025 CIDR 5.4612012e-05
8,513 Galley: Modern Query Optimization for Sparse Tensor Programs 2025 SIGMOD 5.4119882e-05
9,867 SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning 2025 SIGMOD 5.2043672e-05
9,996 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 5.1814573e-05
10,394 Query Optimization for Database-Returning Queries 2026 SIGMOD 5.093636e-05
10,653 Soft and Constrained Hypertree Width 2025 PODS 5.093636e-05
10,726 LpBound in Action: Cardinality Estimation with One-Sided Guarantees 2025 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
18 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059284255
101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00034376651
118 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031922279
168 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027541029
280 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022454217
448 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00018292618
593 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00016027871
694 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014911698
737 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014490983
809 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00013874588
901 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00013334162
944 RDF-3X: a RISC-style Engine for RDF 2008 VLDB 0.00013067088
1,172 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00011825923
1,256 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011457194
1,499 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010564536
2,326 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 8.748172e-05
2,940 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9381573e-05
3,180 Approximate XML Query Answers 2004 SIGMOD 7.6599179e-05
5,459 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 6.2108888e-05
6,325 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9125893e-05
6,672 Computing Join Queries with Functional Dependencies 2016 PODS 5.8070233e-05
8,581 PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation 2021 VLDB 5.4082749e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,994 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS
2 7,495 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD
3 10,438 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD
4 10,726 LpBound in Action: Cardinality Estimation with One-Sided Guarantees 2025 SIGMOD
5 566 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD
6 5,860 Understanding Cardinality Estimation using Entropy Maximization 2010 PODS
7 3,309 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD
8 6,543 Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation 2023 SIGMOD
9 1,122 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB
10 5,639 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD