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
5707
Venue
SIGMOD
Year
2019
Pagerank
9.4437798e-05
Overall Rank
2,143 | 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.00011050093
1,699 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00010848882
1,727 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00010731889
2,781 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 8.1282042e-05
2,988 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 7.7752463e-05
3,492 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 7.0435484e-05
3,516 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.018912e-05
3,644 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8842065e-05
3,781 A Learned Sketch for Subgraph Counting 2021 SIGMOD 6.7691344e-05
3,886 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.6610704e-05
3,924 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 6.6227223e-05
3,992 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 6.5519369e-05
4,413 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 6.1989918e-05
4,431 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.1870601e-05
4,526 Simplicity Done Right for Join Ordering 2021 CIDR 6.1079584e-05
5,630 Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach 2020 SIGMOD 5.4010111e-05
5,886 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 5.2847297e-05
5,931 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 5.2632167e-05
5,978 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 5.2424396e-05
6,705 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9507418e-05
6,901 Disclosure-Compliant Query Answering 2024 SIGMOD 4.8878659e-05
6,967 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 4.875312e-05
7,118 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 4.8204951e-05
7,337 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 4.7532633e-05
7,465 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7186055e-05
7,854 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 4.6306186e-05
8,049 Thrifty Query Execution via Incrementability 2020 SIGMOD 4.5939412e-05
8,274 Galley: Modern Query Optimization for Sparse Tensor Programs 2025 SIGMOD 4.5392079e-05
8,573 PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation 2021 VLDB 4.4885745e-05
8,695 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 4.461508e-05
9,041 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 4.3997447e-05
9,079 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 4.3956812e-05
9,662 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD 4.3056334e-05
9,690 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 4.2994116e-05
9,843 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 4.2680295e-05
9,845 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 4.2680295e-05
9,868 Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections 2022 VLDB 4.2634472e-05
9,876 Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025 VLDB 4.2615675e-05
9,959 An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL 2025 SIGMOD 4.2254157e-05
10,149 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.1905499e-05
10,455 LpBound in Action: Cardinality Estimation with One-Sided Guarantees 2025 SIGMOD 4.1905499e-05
10,498 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 4.1905499e-05
10,640 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.1905499e-05
10,945 Sub-optimal Join Order Identification with L1-error 2024 SIGMOD 4.1905499e-05
10,984 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1905499e-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