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: h83f2f5e8e93d9c79
Venue: VLDB
Year: 2022
Pagerank: 7.7938744e-05
Overall Rank: 2,974 | 80.01%
DOI: 10.14778/3529337.3529339

Incoming Non-self Citations Over Time

Authors

1. Jeremy Chen (University of Waterloo)
2. Yuqing Huang (University of Waterloo)
3. Mushi Wang (University of Waterloo)
4. Semih Salihoglu (University of Waterloo)
5. Ken Salem (University of Waterloo)

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 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,734	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7545773e-05
3,153	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.5883271e-05
4,852	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	6.3806134e-05
5,219	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD	6.222726e-05
5,918	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	5.9481539e-05
6,805	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6780394e-05
7,774	Adaptive Factorization Using Linear-Chained Hash Tables	2025	CIDR	5.4549846e-05
8,682	Galley: Modern Query Optimization for Sparse Tensor Programs	2025	SIGMOD	5.2905577e-05
9,478	LpBound in Action: Cardinality Estimation with One-Sided Guarantees	2025	SIGMOD	5.1708619e-05
10,057	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	5.0875952e-05
10,184	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	5.0651993e-05
10,590	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.9793485e-05
10,842	The Data World Is Not Flat: Efficient Factorized Execution for Relational Systems	2026	VLDB	4.9793485e-05
11,096	Soft and Constrained Hypertree Width	2025	PODS	4.9793485e-05

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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.0002211981
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017962189
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015785583
688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014753664
712	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00014578373
750	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014265196
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013083677
954	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.00012867202
1,184	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00011611937
1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011310561
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010576304
2,368	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.5622073e-05
2,824	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9698957e-05
3,246	Approximate XML Query Answers	2004	SIGMOD	7.4946879e-05
5,580	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.0769576e-05
5,901	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	5.9539374e-05
6,739	Computing Join Queries with Functional Dependencies	2016	PODS	5.6917027e-05
8,650	PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation	2021	VLDB	5.2948655e-05

Semantically Similar Papers

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