{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T07:53:35Z","timestamp":1769759615175,"version":"3.49.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T00:00:00Z","timestamp":1769644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/publication-rights-and-licensing-policy"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:p>\n                    We study two classes of summary-based cardinality estimators that use statistics about input relations and joins of a small number of input relations: (i) optimistic estimators, which were defined in the context of graph database management systems, that make uniformity and conditional independence assumptions; and (ii) the recent pessimistic estimators that use information theoretic linear programs (LPs). We show that optimistic estimators can be modeled as picking bottom-to-top paths in a\n                    <jats:italic toggle=\"yes\">cardinality estimation graph<\/jats:italic>\n                    (CEG), which contains sub-queries as nodes and edges whose weights are average degree statistics. We show that existing optimistic estimators have either undefined or fixed choices for picking CEG paths as their estimates and ignore alternative choices. Instead, we outline a space of optimistic estimators to make an estimate on CEGs, which subsumes existing estimators. We show, using an extensive empirical analysis, that effective paths depend on the structure of the queries. We next show that optimistic estimators and seemingly disparate LP-based pessimistic estimators are in fact connected. Specifically, we show that CEGs can also model some recent pessimistic estimators. This connection allows us to provide insights into the pessimistic estimators, such as showing that they have combinatorial solutions.\n                  <\/jats:p>","DOI":"10.1145\/3780104","type":"journal-article","created":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T15:49:32Z","timestamp":1769615372000},"page":"99-109","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Cardinality Estimation Graphs"],"prefix":"10.1145","volume":"69","author":[{"given":"Semih","family":"Saliho\u011flu","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuqing","family":"Huang","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mushi","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ken","family":"Salem","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,1,29]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"crossref","unstructured":"Abo Khamis M. Ngo H.Q. and Suciu D. Computing join queries with functional dependencies. In\u00a0\u00a0Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symp. on Principles of Database Systems\u00a0(2016) \u00a0327-342.","DOI":"10.1145\/2902251.2902289"},{"key":"e_1_3_1_3_2","unstructured":"Aboulnaga A. Alameldeen A.R. and Naughton J.F. Estimating the selectivity of XML path expressions for Internet scale applications. In Proceedings of the Intern. Conf. Very Large Data Bases\u00a0\u00a0(2001)."},{"key":"e_1_3_1_4_2","doi-asserted-by":"crossref","unstructured":"Alu\u00e7 G. Hartig O. \u00d6zsu M.T. and Daudjee K. Diversified stress testing of RDF data management systems. In Proceedings of the 13th Intern. Semantic Web Conf.\u00a0(2014).","DOI":"10.1007\/978-3-319-11964-9_13"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","unstructured":"Cai W. Balazinska M. and Suciu D. Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities. In Proceedings of the Intern. Conf. on Mgmt. of Data\u00a0(2019).","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_3_1_7_2","unstructured":"Github repo of our code datasets and queries\u00a0(2022);\u00a0https:\/\/github.com\/cetechreport\/CEExperiments"},{"issue":"8","key":"e_1_3_1_8_2","article-title":"Accurate summary-based cardinality estimation through the lens of cardinality estimation graphs","volume":"15","author":"Chen J.","year":"2022","unstructured":"Chen, J. et al. Accurate summary-based cardinality estimation through the lens of cardinality estimation graphs. In\u00a0Proceedings of the Intern. Conf. on Very Large Data Bases\u00a015, 8\u00a0(2022).","journal-title":"Proceedings of the Intern. Conf. on Very Large Data Bases"},{"key":"e_1_3_1_9_2","unstructured":"Chen Y. and Yi K. Random sampling and size estimation over cyclic joins. In Proceedings of the Intern. Conf. on Database Theory\u00a0(2020)."},{"key":"e_1_3_1_10_2","doi-asserted-by":"crossref","unstructured":"Getoor L. Taskar B. and Koller D. Selectivity estimation using probabilistic models. In\u00a0Proceedings of the SIGMOD\u00a0(2001).","DOI":"10.1145\/375663.375727"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9811-8"},{"issue":"3","key":"e_1_3_1_13_2","article-title":"How good are query optimizers, really?","volume":"9","author":"Leis V.","year":"2015","unstructured":"Leis, V. et al. How good are query optimizers, really?\u00a0In\u00a0Proceedings of the Intern. Conf. on Very Large Data Bases\u00a09, 3\u00a0(2015).","journal-title":"Proceedings of the Intern. Conf. on Very Large Data Bases"},{"issue":"5","key":"e_1_3_1_14_2","article-title":"Query optimization through the looking glass, and what we found running the join order benchmark","volume":"27","author":"Leis V.","year":"2018","unstructured":"Leis, V. et al. Query optimization through the looking glass, and what we found running the join order benchmark. VLDBJ\u00a027, 5, (2018).","journal-title":"VLDBJ"},{"key":"e_1_3_1_15_2","unstructured":"Maduko A. Anyanwu K. Sheth A. and Schliekelman P. Graph summaries for subgraph frequency estimation. In Proceedings of the European Semantic Web Conf.\u00a0(2008)."},{"key":"e_1_3_1_16_2","doi-asserted-by":"crossref","unstructured":"Matias Y. Vitter J.S. and Wang M. Wavelet-based histograms for selectivity estimation. In Proceedings of the SIGMOD\u00a0(1998).","DOI":"10.1145\/276304.276344"},{"issue":"11","key":"e_1_3_1_17_2","article-title":"Optimizing subgraph queries by combining binary and worst-case optimal joins","volume":"12","author":"Mhedhbi A.","year":"2019","unstructured":"Mhedhbi, A. and Salihoglu, S. Optimizing subgraph queries by combining binary and worst-case optimal joins. In\u00a0Proceedings of the Intern. Conf. Very Large Data Bases\u00a012, 11\u00a0(2019).","journal-title":"Proceedings of the Intern. Conf. Very Large Data Bases"},{"key":"e_1_3_1_18_2","unstructured":"Muralikrishna M. and DeWitt D.J. Equi-depth histograms for estimating selectivity factors for multi-dimensional queries. In Proceedings of SIGMOD\u00a0(1988)."},{"key":"e_1_3_1_19_2","doi-asserted-by":"crossref","unstructured":"Neumann T. and Moerkotte G. Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins. In Proceedings of the Intern. Conf. on Data Engineering\u00a0(2011).","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"e_1_3_1_20_2","doi-asserted-by":"crossref","unstructured":"Park Y. et al. G-CARE: A framework for performance benchmarking of cardinality estimation techniques for subgraph matching. In Proceedings of SIGMOD\u00a0(2020).","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","unstructured":"Stefanoni G. Motik B. and Kostylev E.V. Estimating the cardinality of conjunctive queries over RDF data using graph summarisation. In Proceedings of the World Wide Web Conf.\u00a0(2018).","DOI":"10.1145\/3178876.3186003"},{"issue":"12","key":"e_1_3_1_22_2","article-title":"Join size estimation subject to filter conditions","volume":"8","author":"Vengerov D.","year":"2015","unstructured":"Vengerov, D., Menck, A.C., Zait, M., and Chakkappen, S.P. Join size estimation subject to filter conditions. In\u00a0Proceedings of the Intern. Conf. on Very Large Data Bases\u00a08, 12\u00a0(2015).","journal-title":"Proceedings of the Intern. Conf. on Very Large Data Bases"},{"issue":"12","key":"e_1_3_1_23_2","article-title":"PostCENN: PostgreSQL with machine learning models for cardinality estimation","volume":"14","author":"Woltmann L.","year":"2021","unstructured":"Woltmann, L. et al. PostCENN: PostgreSQL with machine learning models for cardinality estimation. In\u00a0Proceedings of the Intern. Conf. on Very Large Data Bases\u00a014, 12\u00a0(2021).","journal-title":"Proceedings of the Intern. Conf. on Very Large Data Bases"},{"key":"e_1_3_1_24_2","doi-asserted-by":"crossref","unstructured":"Wu W. Naughton J.F. and Singh H. Sampling-based query re-optimization. In Proceedings of SIGMOD\u00a0(2016).","DOI":"10.1145\/2882903.2882914"},{"key":"e_1_3_1_25_2","doi-asserted-by":"crossref","unstructured":"Wu Y. Patel J.M. and Jagadish H.V. Estimating answer sizes for XML queries. In Proceedings of the Intern. Conf. Extending Database Technology\u00a0(2002).","DOI":"10.1007\/3-540-45876-X_37"},{"key":"e_1_3_1_26_2","unstructured":"Zhang N. Ozsu M.T. Aboulnaga A. and Ilyas I.F. XSEED: Accurate and fast cardinality estimation for XPath queries. In Proceedings of the Intern. Conf. on Data Engineering\u00a0(2006)."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3780104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T17:05:11Z","timestamp":1769706311000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3780104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,29]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["10.1145\/3780104"],"URL":"https:\/\/doi.org\/10.1145\/3780104","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,29]]},"assertion":[{"value":"2026-01-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}