Join Size Bounds using l
            p
            -Norms on Degree Sequences

Mahmoud Abo Khamis; Vasileios Nakos; Dan Olteanu; Dan Suciu

doi:10.1145/3651597

journal article Open Access May 10, 2024

Join Size Bounds using l p -Norms on Degree Sequences

Mahmoud Abo Khamis

Vasileios Nakos

Dan Olteanu

Dan Suciu

Proceedings of the ACM on Management of Data Vol. 2 No. 2 pp. 1-24 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/3651597

Abstract

Estimating the output size of a query is a fundamental yet longstanding problem in database query processing. Traditional cardinality estimators used by database systems can routinely underestimate the true output size by orders of magnitude, which leads to significant system performance penalty. Recently, upper bounds have been proposed that are based on information inequalities and incorporate sizes and max-degrees from input relations, yet their main benefit is limited to cyclic queries, because they degenerate to rather trivial formulas on acyclic queries.

We introduce a significant extension of the upper bounds, by incorporating l
p
-norms of the degree sequences of join attributes. Our bounds are significantly lower than previously known bounds, even when applied to acyclic queries. These bounds are also based on information theory, they come with a matching query evaluation algorithm, are computable in exponential time in the query size, and are provably tight when all degrees are ''simple''.

Topics

No keywords indexed for this article. Browse by subject →

References

26

[1]

10.1145/3472391

[2]

10.48550/arxiv.2306.14075

[3]

10.1145/2902251.2902289

[4]

10.1145/3034786.3056105

[5]

Size Bounds and Query Plans for Relational Joins

Albert Atserias, Martin Grohe, Daniel Marx

SIAM Journal on Computing 10.1137/110859440

[6]

Convex Optimization

Stephen Boyd, Lieven Vandenberghe

10.1017/cbo9780511804441

[7]

10.1145/3299869.3319894

[8]

10.14778/3529337.3529339

[9]

10.4230/lipics.icdt.2023.8

[10]

10.1145/3588907

[11]

10.1145/322344.322347

[12]

10.1214/aos/1176349407

[13]

Size and Treewidth Bounds for Conjunctive Queries

Georg Gottlob, Stephanie Tien Lee, Gregory Valiant et al.

Journal of the ACM 10.1145/2220357.2220363

[14]

10.14778/3503585.3503586

[15]

Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering. In CIDR 2021. www.cidrdb.org. http://cidrdb.org/cidr2021/papers/cidr2021_paper01.pdf

[16]

Sai Vikneshwar Mani Jayaraman, Corey Ropell, and Atri Rudra. 2021. Worst-case Optimal Binary Join Algorithms under General $ell_p$ Constraints. CoRR , Vol. abs/2112.01003 (2021). https://arxiv.org/abs/2112.01003

[17]

10.1145/3514221.3526154

[18]

10.1016/j.ejc.2011.03.009

[19]

10.1109/tse.1987.232847

[20]

10.14778/2850583.2850594

[21]

10.1007/s00778-017-0480--7

[22]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.

[23]

10.1145/3180143

[24]

10.1145/2590989.2590991

[25]

Raghu Ramakrishnan and Johannes Gehrke. 2003. Database management systems (3. ed.). McGraw-Hill.

[26]

Doron Zeilberger. 1984. A combinatorial proof of Newton's identities. Discrete mathematics, Vol. 49, 3 (1984).

Cited By

6

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints

Sungjin Im, Benjamin Moseley · 2025

Proceedings of the ACM on Managemen...

Metrics

6

Citations

26

References

Details

Published: May 10, 2024
Vol/Issue: 2(2)
Pages: 1-24
License: View

Authors

M

Mahmoud Abo Khamis

RelationalAI, Inc, Berkeley, CA, USA

V

Vasileios Nakos

RelationalAI, Inc, Berkeley, CA, USA

D

Dan Olteanu

University of Zurich, Zurich, Switzerland

D

Dan Suciu

University of Washington, Seattle, WA, USA

Funding

NSF-BSF Award: 2109922

NSF-IIS Award: 2314527

NSF-SHF Award: 2312195

Simons Program on Logic and Algorithms in Databases and AI

Cite This Article

Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, et al. (2024). Join Size Bounds using l p -Norms on Degree Sequences. Proceedings of the ACM on Management of Data, 2(2), 1-24. https://doi.org/10.1145/3651597

Join Size Bounds using l p -Norms on Degree Sequences

You May Also Like