{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:03:18Z","timestamp":1789434198321,"version":"build-2803163510"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"NSF-BSF","award":["2109922"],"award-info":[{"award-number":["2109922"]}]},{"name":"NSF-IIS","award":["2314527"],"award-info":[{"award-number":["2314527"]}]},{"name":"NSF-SHF","award":["2312195"],"award-info":[{"award-number":["2312195"]}]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["200021-231956"],"award-info":[{"award-number":["200021-231956"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Cardinality estimation is the problem of estimating the size of the output of a query, without actually evaluating the query. The cardinality estimator is a critical piece of a query optimizer, and is often the main culprit when the optimizer chooses a poor plan.<\/jats:p>\n                  <jats:p>\n                    This paper introduces LpBound, a pessimistic cardinality estimator for multi-join queries (acyclic or cyclic) with selection predicates and group-by clauses.\n                    <jats:sc>LpBound<\/jats:sc>\n                    computes a guaranteed upper bound on the size of the query output using simple statistics on the input relations, consisting of \u2113\n                    <jats:sub>p<\/jats:sub>\n                    -norms of degree sequences. The bound is the optimal solution of a linear program whose constraints encode data statistics and Shannon inequalities. We introduce two optimizations that exploit the structure of the query in order to speed up the estimation time and make\n                    <jats:sc>LpBound<\/jats:sc>\n                    practical.\n                  <\/jats:p>\n                  <jats:p>\n                    We experimentally evaluate\n                    <jats:sc>LpBound<\/jats:sc>\n                    against a range of traditional, pessimistic, and machine learning-based estimators on the JOB, STATS, and subgraph matching benchmarks. Our main finding is that\n                    <jats:sc>LpBound<\/jats:sc>\n                    can be orders of magnitude more accurate than traditional estimators used in mainstream open-source and commercial database systems. Yet it has comparable low estimation time and space requirements. When injected the estimates of\n                    <jats:sc>LpBound<\/jats:sc>\n                    , Postgres derives query plans at least as good as those derived using the true cardinalities.\n                  <\/jats:p>","DOI":"10.1145\/3725321","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-27","source":"Crossref","is-referenced-by-count":12,"title":["<scp>LpBound<\/scp>\n                    : Pessimistic Cardinality Estimation Using \u2113\n                    <sub>p<\/sub>\n                    -Norms of Degree Sequences"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0930-1980","authenticated-orcid":false,"given":"Haozhe","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6651-3900","authenticated-orcid":false,"given":"Christoph","family":"Mayer","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3894-6494","authenticated-orcid":false,"given":"Mahmoud","family":"Abo Khamis","sequence":"additional","affiliation":[{"name":"RelationalAI, Berkeley, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4682-7068","authenticated-orcid":false,"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Engineering, University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651597"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","unstructured":"Mahmoud Abo Khamis Hung Q. Ngo and Dan Suciu. 2016. Computing Join Queries with Functional Dependencies. In PODS . 327-342. doi:10.1145\/2902251.2902289","DOI":"10.1145\/2902251.2902289"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529339"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"G. Cormode and K. Yi. 2020. Small Summaries for Big Data. Cambridge University Press. 2020033065 https:\/\/books.google.com\/books?id=6in-DwAAQBAJ","DOI":"10.1017\/9781108769938"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","unstructured":"Kyle Deeds Dan Suciu Magda Balazinska and Walter Cai. 2023b. Degree Sequence Bound for Join Cardinality Estimation. In ICDT . 8:1-8:18. doi:10.4230\/LIPICS.ICDT.2023.8","DOI":"10.4230\/LIPICS.ICDT.2023.8"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588907"},{"key":"e_1_2_2_11_1","volume-title":"Hyperloglog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm. In Analysis of Algorithms. 127--146.","author":"Flajolet Philippe","year":"2007","unstructured":"Philippe Flajolet, \u00c9ric Fusy, Olivier Gandouet, and Fr\u00e9d\u00e9ric Meunier. 2007. Hyperloglog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm. In Analysis of Algorithms. 127--146."},{"key":"e_1_2_2_12_1","volume-title":"Freitag and Thomas Neumann","author":"Michael","year":"2019","unstructured":"Michael J. Freitag and Thomas Neumann. 2019. Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates. In CIDR,. http:\/\/cidrdb.org\/cidr2019\/papers\/p23-freitag-cidr19.pdf"},{"key":"e_1_2_2_13_1","unstructured":"Hector Garcia-Molina Jeffrey D. Ullman and Jennifer Widom. 2009. Database Systems - The Complete Book (2. Ed.). Pearson Education."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_2_16_1","volume-title":"CIDR","author":"Hertzschuch Axel","unstructured":"Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering. In CIDR,. http:\/\/cidrdb.org\/cidr2021\/papers\/cidr2021_paper01.pdf"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/S12532-017-0130--5"},{"key":"e_1_2_2_20_1","volume-title":"Optimizing Polymatroid Functions. CoRR","author":"Im Sungjin","year":"2022","unstructured":"Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs, and Alireza Samadian. 2022. Optimizing Polymatroid Functions. CoRR, Vol. abs\/2211.08381 (2022). arXiv:2211.08381"},{"key":"e_1_2_2_21_1","volume-title":"Worst-case Optimal Binary Join Algorithms under General lp Constraints. CoRR","author":"Mani Jayaraman Sai Vikneshwar","year":"2021","unstructured":"Sai Vikneshwar Mani Jayaraman, Corey Ropell, and Atri Rudra. 2021. Worst-case Optimal Binary Join Algorithms under General lp Constraints. CoRR, Vol. abs\/2112.01003 (2021). arXiv:2112.01003"},{"key":"e_1_2_2_22_1","volume-title":"Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR,. http:\/\/cidrdb.org\/cidr2019\/papers\/p101-kipf-cidr19.pdf"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611494"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480--7"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446980"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_2_28_1","unstructured":"Aarohi Srivastava Abhinav Rastogi Abhishek Rao Abu Awal Md Shoeb Abubakar Abid Adam Fisch Adam R. Brown Adam Santoro Aditya Gupta Adri\u00e0 Garriga-Alonso Agnieszka Kluska Aitor Lewkowycz Akshat Agarwal Alethea Power Alex Ray Alex Warstadt Alexander W. Kocurek Ali Safaya Ali Tazarv Alice Xiang"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588721"},{"key":"e_1_2_2_31_1","volume-title":"BayesCard: A Unified Bayesian Framework for Cardinality Estimation. CoRR","author":"Wu Ziniu","year":"2020","unstructured":"Ziniu Wu and Amir Shaikhha. 2020. BayesCard: A Unified Bayesian Framework for Cardinality Estimation. CoRR, Vol. abs\/2012.14743 (2020). arXiv:2012.14743 https:\/\/arxiv.org\/abs\/2012.14743"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_2_33_1","volume-title":"Information Theory and Network Coding (1 ed.)","author":"Yeung Raymond W.","unstructured":"Raymond W. Yeung. 2008. Information Theory and Network Coding (1 ed.). Springer Publishing Company."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2502.05912"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.681320"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461539"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:52:57Z","timestamp":1774983177000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725321"],"URL":"https:\/\/doi.org\/10.1145\/3725321","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}