Database Paper Browser

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
5706
Venue
SIGMOD
Year
2019
Pagerank
9.4507296e-05
Overall Rank
2,142 | 85.11%
DOI
10.1145/3299869.3319894

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 45 of 45 citing papers.

Rank Citing Paper Year Venue Pagerank
1,638 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00011049779
1,703 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00010836769
1,737 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00010720294
2,783 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 8.1293383e-05
3,001 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 7.7404487e-05
3,499 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 7.0376445e-05
3,511 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.0254052e-05
3,646 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8853079e-05
3,778 A Learned Sketch for Subgraph Counting 2021 SIGMOD 6.7747398e-05
3,885 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.6674822e-05
3,924 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 6.6271553e-05
3,990 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 6.5581983e-05
4,417 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 6.2037371e-05
4,434 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.1929999e-05
4,523 Simplicity Done Right for Join Ordering 2021 CIDR 6.1135504e-05
5,622 Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach 2020 SIGMOD 5.4060403e-05
5,880 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 5.2898074e-05
5,930 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 5.2682075e-05
5,972 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 5.2474768e-05
6,704 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9554912e-05
6,898 Disclosure-Compliant Query Answering 2024 SIGMOD 4.8925595e-05
6,969 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 4.8799937e-05
7,123 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 4.8251036e-05
7,344 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 4.7565607e-05
7,467 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7218691e-05
7,854 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 4.6350172e-05
8,047 Thrifty Query Execution via Incrementability 2020 SIGMOD 4.5983505e-05
8,279 Galley: Modern Query Optimization for Sparse Tensor Programs 2025 SIGMOD 4.5435639e-05
8,576 PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation 2021 VLDB 4.4927989e-05
8,697 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 4.4657888e-05
9,041 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 4.4039656e-05
9,082 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 4.3998984e-05
9,662 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD 4.3097631e-05
9,691 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 4.3035354e-05
9,843 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 4.2721228e-05
9,845 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 4.2721228e-05
9,869 Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections 2022 VLDB 4.2675361e-05
9,877 Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025 VLDB 4.2656547e-05
9,960 An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL 2025 SIGMOD 4.2294678e-05
10,149 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.1945683e-05
10,445 LpBound in Action: Cardinality Estimation with One-Sided Guarantees 2025 SIGMOD 4.1945683e-05
10,488 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 4.1945683e-05
10,632 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.1945683e-05
10,942 Sub-optimal Join Order Identification with L1-error 2024 SIGMOD 4.1945683e-05
10,981 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1945683e-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