Tighter Upper Bounds for Join Cardinality Estimates
Summary: Tightens join cardinality upper bounds via data sketching and randomized hashing to help optimizers prune costly multiway plans. Extends to multiway cyclic joins; evaluates tightness on GooglePlus graphs, delivering degree-of-magnitude upper bounds and proposing a new join-statistic for plan selection. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Walter Cai (University of Washington)
BibTeX Citation
@inproceedings{cai_sigmod18,
title = {{Tighter Upper Bounds for Join Cardinality Estimates}},
author = {Cai, Walter},
series = {{SIGMOD} '18},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3183713.3183714},
url = {https://dl.acm.org/doi/10.1145/3183713.3183714},
year = {2018}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 18 | How Good Are Query Optimizers, Really? | 2016 | VLDB | 0.00059284255 |
| 566 | Towards a Robust Query Optimizer: A Principled and Practical Approach | 2005 | SIGMOD | 0.00016436005 |
| 694 | Cardinality Estimation Done Right: Index-Based Join Sampling | 2017 | CIDR | 0.00014911698 |
| 737 | Join Size Estimation Subject to Filter Conditions | 2015 | VLDB | 0.00014490983 |
| 819 | Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters | 2016 | SIGMOD | 0.00013815639 |
| 829 | Proactive Re-Optimization | 2005 | SIGMOD | 0.00013769838 |
| 1,109 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00012142685 |
| 1,664 | Two-Level Sampling for Join Size Estimation | 2017 | SIGMOD | 0.00010070362 |
| 1,969 | PIQL: Success-Tolerant Query Processing in the Cloud | 2012 | VLDB | 9.3749819e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 7,747 | Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries | 2024 | SIGMOD |
| 2 | 904 | Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines | 1990 | VLDB |
| 3 | 3,622 | Robust Join Processing with Diamond Hardened Joins | 2024 | VLDB |
| 4 | 18 | How Good Are Query Optimizers, Really? | 2016 | VLDB |
| 5 | 694 | Cardinality Estimation Done Right: Index-Based Join Sampling | 2017 | CIDR |
| 6 | 1,286 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD |
| 7 | 3,617 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS |
| 8 | 6,257 | Join Size Bounds using l_p-Norms on Degree Sequences | 2024 | PODS |
| 9 | 1,740 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB |
| 10 | 1,499 | Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities | 2019 | SIGMOD |