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.00010616242
Overall Rank
1,444 | 90.33%
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 49 of 49 citing papers.

Rank Citing Paper Year Venue Pagerank
983 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012677179
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012181459
1,156 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011759683
1,740 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7289523e-05
2,584 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.2435322e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1795762e-05
2,829 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9469964e-05
2,852 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9201312e-05
2,987 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.767043e-05
3,060 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.6828463e-05
3,105 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.6278115e-05
3,269 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 7.463682e-05
3,995 Simplicity Done Right for Join Ordering 2021 CIDR 6.8530469e-05
4,479 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.5665703e-05
4,882 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.3565046e-05
5,029 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.2952031e-05
5,075 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 6.2721634e-05
5,153 Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach 2020 SIGMOD 6.2375324e-05
5,245 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 6.1995935e-05
5,522 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.0818991e-05
5,717 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 6.0067263e-05
5,911 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9338021e-05
5,925 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9282898e-05
6,812 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6597129e-05
6,840 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.6513231e-05
7,587 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 5.4745198e-05
7,666 Disclosure-Compliant Query Answering 2024 SIGMOD 5.4565877e-05
8,060 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.382134e-05
8,154 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.3732833e-05
8,188 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD 5.3649397e-05
8,499 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 5.3131213e-05
8,675 PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation 2021 VLDB 5.2751633e-05
8,710 Galley: Modern Query Optimization for Sparse Tensor Programs 2025 SIGMOD 5.2705676e-05
9,518 LpBound in Action: Cardinality Estimation with One-Sided Guarantees 2025 SIGMOD 5.151324e-05
9,810 Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025 VLDB 5.112328e-05
9,991 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 5.0845476e-05
10,014 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 5.0838565e-05
10,220 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.0460607e-05
10,221 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 5.0460607e-05
10,249 Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections 2022 VLDB 5.0412674e-05
10,370 An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL 2025 SIGMOD 5.0010514e-05
10,379 Algebraic Subgraph Counting 2027 SIGMOD 4.9605343e-05
10,443 Size Bound-Adorned Datalog 2026 PODS 4.9605343e-05
10,585 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9605343e-05
10,699 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.9605343e-05
10,970 ANNiE: A Learned Query Cost Estimator for Graph-Based Approximate Nearest Neighbor Search 2026 VLDB 4.9605343e-05
11,349 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.9605343e-05
11,564 Sub-optimal Join Order Identification with L1-error 2024 SIGMOD 4.9605343e-05
11,591 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.9605343e-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