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.00010572023
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
981 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012713454
1,065 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012202293
1,155 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011777046
1,735 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7566604e-05
2,583 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.2589842e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1954989e-05
2,824 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9662478e-05
2,844 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9446987e-05
2,975 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7905662e-05
3,053 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.7041081e-05
3,161 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5771609e-05
3,327 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 7.4233639e-05
3,983 Simplicity Done Right for Join Ordering 2021 CIDR 6.8722161e-05
4,459 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.5883555e-05
4,854 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.3775929e-05
5,006 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.3159614e-05
5,129 Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach 2020 SIGMOD 6.2582129e-05
5,224 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 6.2197808e-05
5,236 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 6.2153504e-05
5,500 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.1020763e-05
5,895 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9534254e-05
5,904 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9511271e-05
5,910 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9478947e-05
6,796 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6784895e-05
6,824 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.670071e-05
7,572 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 5.492682e-05
7,653 Disclosure-Compliant Query Answering 2024 SIGMOD 5.4746904e-05
8,042 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.3999898e-05
8,137 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.391109e-05
8,170 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD 5.3827384e-05
8,484 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 5.330748e-05
8,658 PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation 2021 VLDB 5.2923672e-05
8,690 Galley: Modern Query Optimization for Sparse Tensor Programs 2025 SIGMOD 5.2880532e-05
9,489 LpBound in Action: Cardinality Estimation with One-Sided Guarantees 2025 SIGMOD 5.168414e-05
9,958 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 5.1014161e-05
9,983 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 5.1007226e-05
10,186 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.0628015e-05
10,187 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 5.0628015e-05
10,212 Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections 2022 VLDB 5.0579923e-05
10,221 Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025 VLDB 5.0560976e-05
10,343 An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL 2025 SIGMOD 5.0176429e-05
10,377 Size Bound-Adorned Datalog 2026 PODS 4.9769913e-05
10,519 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9769913e-05
10,638 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.9769913e-05
10,909 ANNiE: A Learned Query Cost Estimator for Graph-Based Approximate Nearest Neighbor Search 2026 VLDB 4.9769913e-05
11,294 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.9769913e-05
11,513 Sub-optimal Join Order Identification with L1-error 2024 SIGMOD 4.9769913e-05
11,542 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.9769913e-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