{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:08Z","timestamp":1773481988395,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"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":[[2023,6,7]]},"abstract":"<jats:p>We study two classes of summary-based cardinality estimators that use statistics about input relations and small-size joins: (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 cardinality estimation graph (CEG), which contains subqueries 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.<\/jats:p>","DOI":"10.1145\/3604437.3604458","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T22:22:01Z","timestamp":1686262921000},"page":"94-102","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs"],"prefix":"10.1145","volume":"52","author":[{"given":"Jeremy","family":"Chen","sequence":"first","affiliation":[{"name":"University of Waterloo"}]},{"given":"Yuqing","family":"Huang","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Mushi","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Semih","family":"Salihoglu","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Kenneth","family":"Salem","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]}],"member":"320","published-online":{"date-parts":[[2023,6,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"PODS","author":"Abo Khamis M.","year":"2016","unstructured":"M. Abo Khamis , H. Q. Ngo , and D. Suciu . Computing Join Queries with Functional Dependencies . In PODS , 2016 . M. Abo Khamis, H. Q. Ngo, and D. Suciu. Computing Join Queries with Functional Dependencies. In PODS, 2016."},{"key":"e_1_2_1_2_1","volume-title":"VLDB","author":"Aboulnaga A.","year":"2001","unstructured":"A. Aboulnaga , A. R. Alameldeen , and J. F. Naughton . Estimating the Selectivity of XML Path Expressions for Internet Scale Applications . In VLDB , 2001 . A. Aboulnaga, A. R. Alameldeen, and J. F. Naughton. Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. In VLDB, 2001."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304198"},{"key":"e_1_2_1_4_1","volume-title":"ISWC","author":"Alu\u00b8c G.","year":"2014","unstructured":"G. Alu\u00b8c , O. Hartig , M. T. \u00a8 Ozsu , and K. Daudjee . Diversified Stress Testing of RDF Data Management Systems . In ISWC , 2014 . G. Alu\u00b8c, O. Hartig, M. T. \u00a8Ozsu, and K. Daudjee. Diversified Stress Testing of RDF Data Management Systems. In ISWC, 2014."},{"key":"e_1_2_1_5_1","volume-title":"Size Bounds and Query Plans for Relational Joins. SICOMP, 42(4)","author":"Atserias A.","year":"2013","unstructured":"A. Atserias , M. Grohe , and D. Marx . Size Bounds and Query Plans for Relational Joins. SICOMP, 42(4) , 2013 . A. Atserias, M. Grohe, and D. Marx. Size Bounds and Query Plans for Relational Joins. SICOMP, 42(4), 2013."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_7_1","volume-title":"https:\/\/github.com\/cetechreport\/CEExperiments","author":"Evaluation Source Code CEG","year":"2022","unstructured":"CEG Evaluation Source Code . https:\/\/github.com\/cetechreport\/CEExperiments , 2022 . CEG Evaluation Source Code. https:\/\/github.com\/cetechreport\/CEExperiments, 2022."},{"key":"e_1_2_1_8_1","volume-title":"January","author":"Chen J.","year":"2022","unstructured":"J. Chen , Y. Huang , W. Mushi , S. Semih , and S. Ken . Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs https:\/\/cs.uwaterloo.ca\/~ssalihog\/papers\/ceglong. pdf. Technical report , January 2022 . J. Chen, Y. Huang, W. Mushi, S. Semih, and S. Ken. Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs https:\/\/cs.uwaterloo.ca\/~ssalihog\/papers\/ceglong. pdf. Technical report, January 2022."},{"key":"e_1_2_1_9_1","volume-title":"Accurate Summary-Based Cardinality Estimation through the Lens of Cardinality Estimation Graphs. PVLDB, 15(8)","author":"Chen J.","year":"2022","unstructured":"J. Chen , Y. Huang , M. Wang , S. Salihoglu , and K. Salem . Accurate Summary-Based Cardinality Estimation through the Lens of Cardinality Estimation Graphs. PVLDB, 15(8) , 2022 . J. Chen, Y. Huang, M. Wang, S. Salihoglu, and K. Salem. Accurate Summary-Based Cardinality Estimation through the Lens of Cardinality Estimation Graphs. PVLDB, 15(8), 2022."},{"key":"e_1_2_1_10_1","volume-title":"ICDT","author":"Chen Y.","year":"2020","unstructured":"Y. Chen and K. Yi . Random Sampling and Size Estimation Over Cyclic Joins . In ICDT , 2020 . Y. Chen and K. Yi. Random Sampling and Size Estimation Over Cyclic Joins. In ICDT, 2020."},{"key":"e_1_2_1_11_1","first-page":"11","volume":"201","unstructured":"DBLP 201 2-- 11 -- 28 Dump. https:\/\/dblp.org\/, 2012. DBLP 2012--11--28 Dump. https:\/\/dblp.org\/, 2012.","journal-title":"DBLP"},{"key":"e_1_2_1_12_1","volume-title":"https: \/\/snap.stanford.edu\/data\/soc-Epinions1.html","year":"2003","unstructured":"Epinions. https: \/\/snap.stanford.edu\/data\/soc-Epinions1.html , 2003 . Epinions. https: \/\/snap.stanford.edu\/data\/soc-Epinions1.html, 2003."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375727"},{"key":"e_1_2_1_14_1","volume-title":"Arun N. Selectivity and Cost Estimation for Joins Based on Random Sampling. JCSS, 52(3)","author":"Naughton J.","year":"1996","unstructured":"Haas, Peter J. and Naughton , Jeffrey F. and Seshadri , S . and Swami , Arun N. Selectivity and Cost Estimation for Joins Based on Random Sampling. JCSS, 52(3) , 1996 . Haas, Peter J. and Naughton, Jeffrey F. and Seshadri, S. and Swami, Arun N. Selectivity and Cost Estimation for Joins Based on Random Sampling. JCSS, 52(3), 1996."},{"key":"e_1_2_1_15_1","volume-title":"https:\/\/het.io\/","year":"2015","unstructured":"Hetionet v1.0. https:\/\/het.io\/ , 2015 . Hetionet v1.0. https:\/\/het.io\/, 2015."},{"key":"e_1_2_1_16_1","volume-title":"It's All a Matter of Degree - Using Degree Information to Optimize Multiway Joins. TOCS, 62(4)","author":"Joglekar M.","year":"2018","unstructured":"M. Joglekar and C. R\u00b4e . It's All a Matter of Degree - Using Degree Information to Optimize Multiway Joins. TOCS, 62(4) , 2018 . M. Joglekar and C. R\u00b4e. It's All a Matter of Degree - Using Degree Information to Optimize Multiway Joins. TOCS, 62(4), 2018."},{"key":"e_1_2_1_17_1","volume-title":"SIGMOD","author":"Kim K.","year":"2021","unstructured":"K. Kim , H. Kim , G. Fletcher , and W.-S. Han . Combining sampling and synopses with worst-case optimal runtime and quality guarantees for graph pattern cardinality estimation . In SIGMOD , 2021 . K. Kim, H. Kim, G. Fletcher, and W.-S. Han. Combining sampling and synopses with worst-case optimal runtime and quality guarantees for graph pattern cardinality estimation. In SIGMOD, 2021."},{"key":"e_1_2_1_18_1","volume-title":"Really? PVLDB, 9(3)","author":"Leis V.","year":"2015","unstructured":"V. Leis , A. Gubichev , A. Mirchev , P. Boncz , A. Kemper , and T. Neumann . How Good Are Query Optimizers , Really? PVLDB, 9(3) , 2015 . V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann. How Good Are Query Optimizers, Really? PVLDB, 9(3), 2015."},{"key":"e_1_2_1_19_1","volume-title":"CIDR","author":"Leis V.","year":"2017","unstructured":"V. Leis , B. Radke , A. Gubichev , A. Kemper , and T. Neumann . Cardinality Estimation Done Right: Index-Based Join Sampling . In CIDR , 2017 . V. Leis, B. Radke, A. Gubichev, A. Kemper, and T. Neumann. Cardinality Estimation Done Right: Index-Based Join Sampling. In CIDR, 2017."},{"key":"e_1_2_1_20_1","volume-title":"Query Optimization Through the Looking Glass, and What We Found Running the Join Order Benchmark. VLDBJ, 27(5)","author":"Leis V.","year":"2018","unstructured":"V. Leis , B. Radke , A. Gubichev , A. Mirchev , P. Boncz , A. Kemper , and T. Neumann . Query Optimization Through the Looking Glass, and What We Found Running the Join Order Benchmark. VLDBJ, 27(5) , 2018 . V. Leis, B. Radke, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann. Query Optimization Through the Looking Glass, and What We Found Running the Join Order Benchmark. VLDBJ, 27(5), 2018."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68234-9_38"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276344"},{"key":"e_1_2_1_24_1","volume-title":"Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins. PVLDB, 12(11)","author":"Mhedhbi A.","year":"2019","unstructured":"A. Mhedhbi and S. Salihoglu . Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins. PVLDB, 12(11) , 2019 . A. Mhedhbi and S. Salihoglu. Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins. PVLDB, 12(11), 2019."},{"key":"e_1_2_1_25_1","volume-title":"SIGMOD","author":"Muralikrishna M.","year":"1988","unstructured":"M. Muralikrishna and D. J. DeWitt . Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries . In SIGMOD , 1988 . M. Muralikrishna and D. J. DeWitt. Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries. In SIGMOD, 1988."},{"key":"e_1_2_1_26_1","volume-title":"ICDEW","author":"Negi P.","year":"2020","unstructured":"P. Negi , R. Marcus , H. Mao , N. Tatbul , T. Kraska , and M. Alizadeh . Cost-guided cardinality estimation: Focus where it matters . In ICDEW , 2020 . P. Negi, R. Marcus, H. Mao, N. Tatbul, T. Kraska, and M. Alizadeh. Cost-guided cardinality estimation: Focus where it matters. In ICDEW, 2020."},{"key":"e_1_2_1_27_1","volume-title":"ICDE","author":"Neumann T.","year":"2011","unstructured":"T. Neumann and G. Moerkotte . Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins . In ICDE , 2011 . T. Neumann and G. Moerkotte. Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins. In ICDE, 2011."},{"key":"e_1_2_1_28_1","volume-title":"SIGMOD","author":"Park Y.","year":"2020","unstructured":"Y. Park , S. Ko , S. S. Bhowmick , K. Kim , K. Hong , and W.-S. Han . G-CARE : A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching . In SIGMOD , 2020 . Y. Park, S. Ko, S. S. Bhowmick, K. Kim, K. Hong, and W.-S. Han. G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching. In SIGMOD, 2020."},{"key":"e_1_2_1_29_1","volume-title":"SIGMOD","author":"Polyzotis N.","year":"2002","unstructured":"N. Polyzotis and M. Garofalakis . Statistical Synopses for Graph-Structured XML Databases . In SIGMOD , 2002 . N. Polyzotis and M. Garofalakis. Statistical Synopses for Graph-Structured XML Databases. In SIGMOD, 2002."},{"key":"e_1_2_1_30_1","volume-title":"VLDB","author":"Poosala V.","year":"1997","unstructured":"V. Poosala and Y. E. Ioannidis . Selectivity Estimation Without the Attribute Value Independence Assumption . In VLDB , 1997 . V. Poosala and Y. E. Ioannidis. Selectivity Estimation Without the Attribute Value Independence Assumption. In VLDB, 1997."},{"key":"e_1_2_1_31_1","volume-title":"WWW","author":"Stefanoni G.","year":"2018","unstructured":"G. Stefanoni , B. Motik , and E. V. Kostylev . Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation . In WWW , 2018 . G. Stefanoni, B. Motik, and E. V. Kostylev. Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation. In WWW, 2018."},{"key":"e_1_2_1_32_1","volume-title":"SIGMOD","author":"Sun W.","year":"1993","unstructured":"W. Sun , Y. Ling , N. Rishe , and Y. Deng . An Instant and Accurate Size Estimation Method for Joins and Selections in a Retrieval-Intensive Environment . In SIGMOD , 1993 . W. Sun, Y. Ling, N. Rishe, and Y. Deng. An Instant and Accurate Size Estimation Method for Joins and Selections in a Retrieval-Intensive Environment. In SIGMOD, 1993."},{"key":"e_1_2_1_33_1","volume-title":"Join Size Estimation Subject to Filter Conditions. PVLDB, 8(12)","author":"Vengerov D.","year":"2015","unstructured":"D. Vengerov , A. C. Menck , M. Zait , and S. P. Chakkappen . Join Size Estimation Subject to Filter Conditions. PVLDB, 8(12) , 2015 . D. Vengerov, A. C. Menck, M. Zait, and S. P. Chakkappen. Join Size Estimation Subject to Filter Conditions. PVLDB, 8(12), 2015."},{"key":"e_1_2_1_34_1","volume-title":"VLDB","author":"Wang W.","year":"2004","unstructured":"W. Wang , H. Jiang , H. Lu , and J. X. Yu . Bloom Histogram: Path Selectivity Estimation for XML Data with Updates . In VLDB , 2004 . W. Wang, H. Jiang, H. Lu, and J. X. Yu. Bloom Histogram: Path Selectivity Estimation for XML Data with Updates. In VLDB, 2004."},{"key":"e_1_2_1_35_1","volume-title":"https:\/\/dsg.uwaterloo.ca\/watdiv\/","year":"2014","unstructured":"WatDiv v.0.6. https:\/\/dsg.uwaterloo.ca\/watdiv\/ , 2014 . WatDiv v.0.6. https:\/\/dsg.uwaterloo.ca\/watdiv\/, 2014."},{"key":"e_1_2_1_36_1","volume-title":"Cardinality estimation with local deep learning models. In aiDM","author":"Woltmann L.","year":"2019","unstructured":"L. Woltmann , C. Hartmann , M. Thiele , D. Habich , and W. Lehner . Cardinality estimation with local deep learning models. In aiDM , 2019 . L. Woltmann, C. Hartmann, M. Thiele, D. Habich, and W. Lehner. Cardinality estimation with local deep learning models. In aiDM, 2019."},{"key":"e_1_2_1_37_1","volume-title":"PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation. PVLDB, 14(12)","author":"Woltmann L.","year":"2021","unstructured":"L. Woltmann , D. Olwig , C. Hartmann , D. Habich , and W. Lehner . PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation. PVLDB, 14(12) , 2021 . L. Woltmann, D. Olwig, C. Hartmann, D. Habich, and W. Lehner. PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation. PVLDB, 14(12), 2021."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882914"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/645340.650212"},{"key":"e_1_2_1_40_1","volume-title":"https:\/\/yago-knowledge.org\/downloads\/yago-1","author":"YAGO","year":"2008","unstructured":"YAGO 1. https:\/\/yago-knowledge.org\/downloads\/yago-1 , 2008 . YAGO 1. https:\/\/yago-knowledge.org\/downloads\/yago-1, 2008."},{"key":"e_1_2_1_41_1","volume-title":"ICDE","author":"Zhang N.","year":"2006","unstructured":"N. Zhang , M. T. Ozsu , A. Aboulnaga , and I. F. Ilyas . XSEED: Accurate and Fast Cardinality Estimation for XPath Queries . In ICDE , 2006 N. Zhang, M. T. Ozsu, A. Aboulnaga, and I. F. Ilyas. XSEED: Accurate and Fast Cardinality Estimation for XPath Queries. In ICDE, 2006"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604458","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604437.3604458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:19Z","timestamp":1750178839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6,7]]}},"alternative-id":["10.1145\/3604437.3604458"],"URL":"https:\/\/doi.org\/10.1145\/3604437.3604458","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"2023-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}