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 |
|---|---|---|---|---|
| 15 | How Good Are Query Optimizers, Really? | 2016 | VLDB | 0.00061066921 |
| 569 | Towards a Robust Query Optimizer: A Principled and Practical Approach | 2005 | SIGMOD | 0.00016245271 |
| 688 | Cardinality Estimation Done Right: Index-Based Join Sampling | 2017 | CIDR | 0.00014753664 |
| 750 | Join Size Estimation Subject to Filter Conditions | 2015 | VLDB | 0.00014265196 |
| 836 | Proactive Re-Optimization | 2005 | SIGMOD | 0.00013557047 |
| 840 | Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters | 2016 | SIGMOD | 0.0001354605 |
| 1,091 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00012074152 |
| 1,678 | Two-Level Sampling for Join Size Estimation | 2017 | SIGMOD | 9.9088372e-05 |
| 2,008 | PIQL: Success-Tolerant Query Processing in the Cloud | 2012 | VLDB | 9.1988831e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 7,608 | On the Complexity of Join Predicates | 2001 | PODS |
| 2 | 920 | Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines | 1990 | VLDB |
| 3 | 3,153 | Robust Join Processing with Diamond Hardened Joins | 2024 | VLDB |
| 4 | 15 | How Good Are Query Optimizers, Really? | 2016 | VLDB |
| 5 | 688 | Cardinality Estimation Done Right: Index-Based Join Sampling | 2017 | CIDR |
| 6 | 1,186 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD |
| 7 | 3,660 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS |
| 8 | 5,918 | Join Size Bounds using l_p-Norms on Degree Sequences | 2024 | PODS |
| 9 | 1,596 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB |
| 10 | 1,465 | Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities | 2019 | SIGMOD |