DBScholar

Back to papers

Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities

Summary: New pessimistic upper bounds for multi-join cardinalities using randomized hashing and data sketches; these bounds feed a cost-based optimizer to prune expensive plans. Partition budgeting enforces monotonicity amid non-monotone tightness, delivering 1.7x–10x runtime gains on JOB and GooglePlus with/without foreign keys. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h155d677849a72580
Venue
SIGMOD
Year
2019
Pagerank
0.00010576304
Overall Rank
1,465 | 90.16%
DOI
10.1145/3299869.3319894

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{cai_sigmod19,
        title = {{Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities}},
        author = {Cai, Walter and Balazinska, Magdalena and Suciu, Dan},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319894},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319894},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 48 of 48 citing papers.

Rank Citing Paper Year Venue Pagerank
982 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012714044
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012202282
1,156 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011777105
1,734 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7545773e-05
2,583 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.2589758e-05
2,634 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1993804e-05
2,824 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9698957e-05
2,846 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9453616e-05
2,974 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7938744e-05
3,052 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.7052471e-05
3,160 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5807496e-05
3,327 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 7.4207879e-05
3,982 Simplicity Done Right for Join Ordering 2021 CIDR 6.8750228e-05
4,457 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.5913732e-05
4,852 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.3806134e-05
5,003 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.3188773e-05
5,126 Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach 2020 SIGMOD 6.261175e-05
5,219 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 6.222726e-05
5,241 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 6.2154384e-05
5,496 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.1049663e-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
5,902 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9536872e-05
5,918 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9481539e-05
6,791 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6811782e-05
6,818 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.672718e-05
7,566 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 5.4952834e-05
7,647 Disclosure-Compliant Query Answering 2024 SIGMOD 5.4772833e-05
8,035 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.4025473e-05
8,131 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.3936608e-05
8,164 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD 5.3852872e-05
8,477 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 5.3332727e-05
8,650 PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation 2021 VLDB 5.2948655e-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
9,950 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 5.1038322e-05
9,976 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 5.1031384e-05
10,182 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.0651993e-05
10,184 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 5.0651993e-05
10,205 Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections 2022 VLDB 5.0603873e-05
10,215 Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025 VLDB 5.0584922e-05
10,336 An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL 2025 SIGMOD 5.0200193e-05
10,365 Size Bound-Adorned Datalog 2026 PODS 4.9793485e-05
10,508 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9793485e-05
10,627 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.9793485e-05
10,900 ANNiE: A Learned Query Cost Estimator for Graph-Based Approximate Nearest Neighbor Search 2026 VLDB 4.9793485e-05
11,286 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.9793485e-05
11,507 Sub-optimal Join Order Identification with L1-error 2024 SIGMOD 4.9793485e-05
11,536 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Previous Page 1 / 1 Next

Semantically Similar Papers