{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T04:06:27Z","timestamp":1790395587500,"version":"4.1.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T00:00:00Z","timestamp":1736726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2025,1,13]]},"abstract":"<jats:p>Cardinality Estimation is to estimate the size of the output of a query without computing it, by using only statistics on the input relations. Existing estimators try to return an unbiased estimate of the cardinality: this is notoriously difficult. A new class of estimators have been proposed recently, called pessimistic estimators, which compute a guaranteed upper bound on the query output. Two recent advances have made pessimistic estimators practical. The first is the recent observation that degree sequences of the input relations can be used to compute query upper bounds. The second is a long line of theoretical results that have developed the use of information theoretic inequalities for query upper bounds. This paper is a short overview of pessimistic cardinality estimators, contrasting them with traditional estimators.<\/jats:p>","DOI":"10.1145\/3712311.3712313","type":"journal-article","created":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T05:18:13Z","timestamp":1736831893000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Pessimistic Cardinality Estimation"],"prefix":"10.1145","volume":"53","author":[{"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"RelationalAI, Inc"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kyle","family":"Deeds","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,1,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"https:\/\/learn.microsoft. com\/en-us\/sql\/relational-databases\/statistics\/ statistics?view=sql-server-ver16","author":"Statistics","year":"2024","unstructured":"Statistics in SQL server. https:\/\/learn.microsoft. com\/en-us\/sql\/relational-databases\/statistics\/ statistics?view=sql-server-ver16, 2024. Accessed: October 2024."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"8","DOI":"10.14778\/3529337.3529339","article-title":"Accurate summary-based cardinality estimation through the lens of cardinality estimation graphs","volume":"15","author":"Chen J.","year":"2022","unstructured":"Chen, J., Huang, Y., Wang, M., Salihoglu, S., and Salem, K. Accurate summary-based cardinality estimation through the lens of cardinality estimation graphs. Proc. VLDB Endow. 15, 8 (2022), 1533--1545.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_6_1","first-page":"759","volume-title":"SIGMOD","author":"Chen Y.","year":"2017","unstructured":"Chen, Y., and Yi, K. Two-level sampling for join size estimation. In SIGMOD (2017), pp. 759--774."},{"key":"e_1_2_1_7_1","first-page":"361","volume-title":"PODS","author":"Cohen E.","year":"2023","unstructured":"Cohen, E. Sampling big ideas in query optimization. In PODS (2023), pp. 361--371."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108769938"},{"key":"e_1_2_1_9_1","volume-title":"Color: A framework for applying graph coloring to subgraph cardinality estimation. CoRR abs\/2405.06767","author":"Deeds K.","year":"2024","unstructured":"Deeds, K., Sabale, D., Kayali, M., and Suciu, D. Color: A framework for applying graph coloring to subgraph cardinality estimation. CoRR abs\/2405.06767 (2024)."},{"key":"e_1_2_1_10_1","first-page":"1","volume-title":"ICDT","author":"Deeds K.","year":"2023","unstructured":"Deeds, K., Suciu, D., Balazinska, M., and Cai, W. Degree sequence bound for join cardinality estimation. In ICDT (2023), pp. 8:1--8:18."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588907"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02780332","article-title":"On the number of copies of one hypergraph in another","volume":"105","author":"Friedgut E.","year":"1998","unstructured":"Friedgut, E., and Kahn, J. On the number of copies of one hypergraph in another. Israel Journal of Mathematics 105, 1 (1998), 251--256.","journal-title":"Israel Journal of Mathematics"},{"key":"e_1_2_1_14_1","volume-title":"Pearson Education","author":"Garcia-Molina H.","year":"2009","unstructured":"Garcia-Molina, H., Ullman, J. D., and Widom, J. Database systems - the complete book (2. ed.). Pearson Education, 2009."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2220357.2220363","article-title":"Size and treewidth bounds for conjunctive queries","volume":"59","author":"Gottlob G.","year":"2012","unstructured":"Gottlob, G., Lee, S. T., Valiant, G., and Valiant, P. Size and treewidth bounds for conjunctive queries. J. ACM 59, 3 (2012), 16:1--16:35.","journal-title":"J. ACM"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109590"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_19_1","volume-title":"CIDR","author":"Hertzschuch A.","year":"2021","unstructured":"Hertzschuch, A., Hartmann, C., Habich, D., and Lehner, W. Simplicity done right for join ordering. In CIDR (2021)."},{"key":"e_1_2_1_20_1","volume-title":"Tractable algorithms for join evaluation and cardinality estimation via the dual-project-dual technique","author":"Im S.","year":"2022","unstructured":"Im, S., Moseley, B., Ngo, H., and Pruhs, K. Tractable algorithms for join evaluation and cardinality estimation via the dual-project-dual technique, 2022. Personal communication."},{"key":"e_1_2_1_21_1","volume-title":"Optimizing polymatroid functions. CoRR abs\/2211.08381","author":"Im S.","year":"2022","unstructured":"Im, S., Moseley, B., Ngo, H. Q., Pruhs, K., and Samadian, A. Optimizing polymatroid functions. CoRR abs\/2211.08381 (2022)."},{"key":"e_1_2_1_22_1","first-page":"1","volume-title":"ICDT","author":"Joglekar M.","year":"2016","unstructured":"Joglekar, M., and R\u00b4e, C. It's all a matter of degree: Using degree information to optimize multiway joins. In ICDT (2016), pp. 11:1--11:17."},{"key":"e_1_2_1_23_1","volume-title":"Join size bounds using lp-norms on degree sequences. CoRR abs\/2306.14075","author":"Khamis M. A.","year":"2023","unstructured":"Khamis, M. A., Nakos, V., Olteanu, D., and Suciu, D. Join size bounds using lp-norms on degree sequences. CoRR abs\/2306.14075 (2023)."},{"key":"e_1_2_1_24_1","first-page":"2","article-title":"Join size bounds using lp-norms on degree sequences","volume":"2","author":"Khamis M. A.","year":"2024","unstructured":"Khamis, M. A., Nakos, V., Olteanu, D., and Suciu, D. Join size bounds using lp-norms on degree sequences. Proc. ACM Manag. Data 2, 2 (2024), 96.","journal-title":"Proc. ACM Manag. Data"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1145\/2902251.2902289","volume-title":"PODS","author":"Khamis M. A.","year":"2016","unstructured":"Khamis, M. A., Ngo, H. Q., and Suciu, D. Computing join queries with functional dependencies. In PODS (2016), pp. 327--342."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_27_1","first-page":"1214","volume-title":"SIGMOD","author":"Kim K.","year":"2022","unstructured":"Kim, K., Jung, J., Seo, I., Han, W., Choi, K., and Chong, J. Learned cardinality estimation: An in-depth study. In SIGMOD (2022), pp. 1214--1227."},{"key":"e_1_2_1_28_1","first-page":"11","article-title":"Analyzing the impact of cardinality estimation on execution plans in microsoft SQL server","volume":"16","author":"Lee K.","year":"2023","unstructured":"Lee, K., Dutt, A., Narasayya, V. R., and Chaudhuri, S. Analyzing the impact of cardinality estimation on execution plans in microsoft SQL server. Proc. VLDB Endow. 16, 11 (2023), 2871--2883.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284551"},{"key":"e_1_2_1_32_1","first-page":"1","article-title":"Consistent selectivity estimation via maximum entropy","volume":"16","author":"Markl V.","year":"2007","unstructured":"Markl, V., Haas, P. J., Kutsch, M., Megiddo, N., Srivastava, U., and Tran, T. M. Consistent selectivity estimation via maximum entropy. VLDB J. 16, 1 (2007), 55--76.","journal-title":"VLDB J."},{"key":"e_1_2_1_33_1","first-page":"1","volume-title":"ICDT","author":"Ngo H. Q.","year":"2022","unstructured":"Ngo, H. Q. On an information theoretic approach to cardinality estimation (invited talk). In ICDT (2022), pp. 1:1--1:21."},{"key":"e_1_2_1_34_1","first-page":"1099","volume-title":"SIGMOD","author":"Park Y.","year":"2020","unstructured":"Park, Y., Ko, S., Bhowmick, S. S., Kim, K., Hong, K., and Han, W. G-CARE: A framework for performance benchmarking of cardinality estimation techniques for subgraph matching. In SIGMOD (2020), pp. 1099--1114."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_36_1","first-page":"1","volume-title":"LICS","author":"Suciu D.","year":"2023","unstructured":"Suciu, D. Applications of information inequalities to database theory problems. In LICS (2023), pp. 1--30."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.14778\/3461535.3461552","article-title":"Are we ready for learned cardinality estimation?","volume":"14","author":"Wang X.","year":"2021","unstructured":"Wang, X., Qu, C., Wu, W., Wang, J., and Zhou, Q. Are we ready for learned cardinality estimation? Proc. VLDB Endow. 14, 9 (2021), 1640--1654.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_38_1","volume-title":"Bayescard: A unified bayesian framework for cardinality estimation. CoRR abs\/2012.14743","author":"Wu Z.","year":"2020","unstructured":"Wu, Z., and Shaikhha, A. Bayescard: A unified bayesian framework for cardinality estimation. CoRR abs\/2012.14743 (2020)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1457455"},{"key":"e_1_2_1_41_1","volume-title":"LpBound: Pessimistic cardinality estimation using lp-norms of degree sequences","author":"Zhang H.","year":"2024","unstructured":"Zhang, H., Mayer, C., Khamis, M. A., Olteanu, D., and Suciu, D. LpBound: Pessimistic cardinality estimation using lp-norms of degree sequences, 2024. technical report."},{"key":"e_1_2_1_42_1","first-page":"4","article-title":"On characterization of entropy function via information inequalities","volume":"44","author":"Zhang Z.","year":"1998","unstructured":"Zhang, Z., and Yeung, R. W. On characterization of entropy function via information inequalities. IEEE Trans. Inf. Theory 44, 4 (1998), 1440--1452.","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712311.3712313","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3712311.3712313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:29Z","timestamp":1750295429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712311.3712313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,13]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,1,13]]}},"alternative-id":["10.1145\/3712311.3712313"],"URL":"https:\/\/doi.org\/10.1145\/3712311.3712313","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2025,1,13]]},"assertion":[{"value":"2025-01-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}