{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T09:01:18Z","timestamp":1775638878015,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>Cardinality estimation is widely believed to be one of the most important causes of poor query plans. Prior studies evaluate the impact of cardinality estimation on plan quality on a set of Select-Project-Join queries on PostgreSQL DBMS. Our empirical study broadens the scope of prior studies in significant ways. First, we include complex SQL queries containing group-by, aggregation, outer joins and sub-queries from real-world workloads and industry benchmarks. We evaluate on both row-oriented and column-oriented physical designs. Our empirical study uses Microsoft SQL Server, an industry-strength DBMS with a state-of-the-art query optimizer that is equipped with techniques to optimize such complex queries. Second, we analyze the sensitivity of plan quality to cardinality errors in two ways by: (a) varying the subset of query sub-expressions for which accurate cardinalities are used, and (b) introducing progressively larger cardinality errors. Third, query processing techniques such as bitmap filtering and adaptive join have the potential to mitigate the impact of cardinality estimation errors by reducing the latency of bad plans. We evaluate the importance of accurate cardinalities in the presence of these techniques.<\/jats:p>","DOI":"10.14778\/3611479.3611494","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"2871-2883","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server"],"prefix":"10.14778","volume":"16","author":[{"given":"Kukjin","family":"Lee","sequence":"first","affiliation":[{"name":"Microsoft Research"}]},{"given":"Anshuman","family":"Dutt","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]},{"given":"Vivek","family":"Narasayya","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]},{"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2011. Understanding parallel query plans. https:\/\/infocenter.sybase.com\/help\/index.jsp?topic=\/com.sybase.infocenter.dc00743.1570\/html\/queryprocessing\/CHDHHIIF.htm. accessed on 07\/25\/2023.  2011. Understanding parallel query plans. https:\/\/infocenter.sybase.com\/help\/index.jsp?topic=\/com.sybase.infocenter.dc00743.1570\/html\/queryprocessing\/CHDHHIIF.htm. accessed on 07\/25\/2023."},{"key":"e_1_2_1_2_1","unstructured":"2016. Program for TPC-H Data Generation with Skew. https:\/\/www.microsoft.com\/en-us\/download\/details.aspx?id=52430. last accessed on 07\/25\/2023.  2016. Program for TPC-H Data Generation with Skew. https:\/\/www.microsoft.com\/en-us\/download\/details.aspx?id=52430. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_3_1","unstructured":"2018. https:\/\/sqlperformance.com\/2018\/02\/sql-plan\/setting-and-identifying-row-goals. last accessed on 07\/25\/2023.  2018. https:\/\/sqlperformance.com\/2018\/02\/sql-plan\/setting-and-identifying-row-goals. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_4_1","unstructured":"2019. Columnstore Index Performance: BatchMode Execution. https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/columnstore-index-performance-batchmode-execution\/ba-p\/385054. last accessed on 07\/25\/2023.  2019. Columnstore Index Performance: BatchMode Execution. https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/columnstore-index-performance-batchmode-execution\/ba-p\/385054. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_5_1","unstructured":"2019. Intro to Query Execution Bitmap Filters. https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/intro-to-query-execution-bitmap-filters\/ba-p\/383175. last accessed on 07\/25\/2023.  2019. Intro to Query Execution Bitmap Filters. https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/intro-to-query-execution-bitmap-filters\/ba-p\/383175. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_6_1","unstructured":"2019. Introducing Batch Mode Adaptive Joins. https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/introducing-batch-mode-adaptive-joins\/ba-p\/385411. last accessed on 07\/25\/2023.  2019. Introducing Batch Mode Adaptive Joins. https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/introducing-batch-mode-adaptive-joins\/ba-p\/385411. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_7_1","volume-title":"Parallel Execution with Oracle Database. (Feb","year":"2019","unstructured":"2019. Parallel Execution with Oracle Database. (Feb 2019 ). https:\/\/www.oracle.com\/technetwork\/database\/bi-datawarehousing\/twp-parallel-execution-fundamentals-133639.pdf last accessed on 07\/25\/2023. 2019. Parallel Execution with Oracle Database. (Feb 2019). https:\/\/www.oracle.com\/technetwork\/database\/bi-datawarehousing\/twp-parallel-execution-fundamentals-133639.pdf last accessed on 07\/25\/2023."},{"key":"e_1_2_1_8_1","unstructured":"2021. Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator. https:\/\/learn.microsoft.com\/en-us\/previous-versions\/dn673537(v=msdn.10)?redirectedfrom=MSDN. last accessed on 07\/25\/2023.  2021. Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator. https:\/\/learn.microsoft.com\/en-us\/previous-versions\/dn673537(v=msdn.10)?redirectedfrom=MSDN. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_9_1","unstructured":"2022. https:\/\/www.erikdarlingdata.com\/a-row-goal-riddle\/. last accessed on 07\/25\/2023.  2022. https:\/\/www.erikdarlingdata.com\/a-row-goal-riddle\/. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_10_1","unstructured":"2022. Parallel Query (PostgreSQL 13). https:\/\/www.postgresql.org\/docs\/13\/parallel-query.html. last accessed on 07\/25\/2023.  2022. Parallel Query (PostgreSQL 13). https:\/\/www.postgresql.org\/docs\/13\/parallel-query.html. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_11_1","unstructured":"2023. DBCC DROPCLEANBUFFERS (Transact-SQL). https:\/\/learn.microsoft.com\/en-us\/sql\/t-sql\/database-console-commands\/dbcc-dropcleanbuffers-transact-sql?view=sql-server-ver16. last accessed on 07\/25\/2023.  2023. DBCC DROPCLEANBUFFERS (Transact-SQL). https:\/\/learn.microsoft.com\/en-us\/sql\/t-sql\/database-console-commands\/dbcc-dropcleanbuffers-transact-sql?view=sql-server-ver16. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_12_1","unstructured":"2023. Query processing architecture guide (Parallel Query Processing). https:\/\/learn.microsoft.com\/en-us\/sql\/relational-databases\/query-processing-architecture-guide?view=sql-server-ver16#parallel-query-processing. last accessed on 07\/25\/2023.  2023. Query processing architecture guide (Parallel Query Processing). https:\/\/learn.microsoft.com\/en-us\/sql\/relational-databases\/query-processing-architecture-guide?view=sql-server-ver16#parallel-query-processing. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_13_1","unstructured":"2023. TPC-DS decision support benchmark. https:\/\/www.tpc.org\/tpcds\/. last accessed on 07\/25\/2023.  2023. TPC-DS decision support benchmark. https:\/\/www.tpc.org\/tpcds\/. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_14_1","unstructured":"2023. TPC-H decision support benchmark. https:\/\/www.tpc.org\/tpch\/. last accessed on 07\/25\/2023.  2023. TPC-H decision support benchmark. https:\/\/www.tpc.org\/tpch\/. last accessed on 07\/25\/2023."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275492"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559955"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"Exact Cardinality Query Optimization for Optimizer Testing","volume":"2","author":"Chaudhuri Surajit","year":"2009","unstructured":"Surajit Chaudhuri , Vivek Narasayya , and Ravi Ramamurthy . 2009 . Exact Cardinality Query Optimization for Optimizer Testing . PVLDB 2 , 1 (aug 2009), 994--1005. Surajit Chaudhuri, Vivek Narasayya, and Ravi Ramamurthy. 2009. Exact Cardinality Query Optimization for Optimizer Testing. PVLDB 2, 1 (aug 2009), 994--1005.","journal-title":"PVLDB"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824074"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Amol Deshpande Zachary Ives Vijayshankar Raman etal 2007. Adaptive query processing. Foundations and Trends\u00ae in Databases 1 1 (2007) 1--140.  Amol Deshpande Zachary Ives Vijayshankar Raman et al. 2007. Adaptive query processing. Foundations and Trends\u00ae in Databases 1 1 (2007) 1--140.","DOI":"10.1561\/1900000001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389769"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_23_1","volume-title":"Moore-Smith","author":"Fraser Campbell","year":"2012","unstructured":"Campbell Fraser , Leo Giakoumakis , Vikas Hamine , and Katherine F . Moore-Smith . 2012 . Testing Cardinality Estimation Models in SQL Server. In DBTest. Article 12. Campbell Fraser, Leo Giakoumakis, Vikas Hamine, and Katherine F. Moore-Smith. 2012. Testing Cardinality Estimation Models in SQL Server. In DBTest. Article 12."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497528"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497528"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_1_27_1","first-page":"19","article-title":"The cascades framework for query optimization","volume":"18","author":"Graefe Goetz","year":"1995","unstructured":"Goetz Graefe . 1995 . The cascades framework for query optimization . IEEE Data Eng. Bull. 18 , 3 (1995), 19 -- 29 . Goetz Graefe. 1995. The cascades framework for query optimization. IEEE Data Eng. Bull. 18, 3 (1995), 19--29.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_29_1","volume-title":"Ioannidis and Stavros Christodoulakis","author":"Yannis","year":"1991","unstructured":"Yannis E. Ioannidis and Stavros Christodoulakis . 1991 . On the Propagation of Errors in the Size of Join Results. In ACM SIGMOD. 268--277. Yannis E. Ioannidis and Stavros Christodoulakis. 1991. On the Propagation of Errors in the Size of Join Results. In ACM SIGMOD. 268--277."},{"key":"e_1_2_1_30_1","volume-title":"Learned cardinalities: Estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677","author":"Kipf Andreas","year":"2018","unstructured":"Andreas Kipf , Thomas Kipf , Bernhard Radke , Viktor Leis , Peter Boncz , and Alfons Kemper . 2018. Learned cardinalities: Estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677 ( 2018 ). Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. Learned cardinalities: Estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677 (2018)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463708"},{"key":"e_1_2_1_32_1","first-page":"15","article-title":"Columnar Storage in SQL Server 2012","volume":"35","author":"Larson Per-\u00c5ke","year":"2012","unstructured":"Per-\u00c5ke Larson , Eric N Hanson , and Susan L Price . 2012 . Columnar Storage in SQL Server 2012 . IEEE Data Eng. Bull. 35 , 1 (2012), 15 -- 20 . Per-\u00c5ke Larson, Eric N Hanson, and Susan L Price. 2012. Columnar Storage in SQL Server 2012. IEEE Data Eng. Bull. 35, 1 (2012), 15--20.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Volker Markl Vijayshankar Raman David Simmen Guy Lohman Hamid Pirahesh and Miso Cilimdzic. 2004. Robust Query Processing through Progressive Optimization. In ACM SIGMOD. 659--670.  Volker Markl Vijayshankar Raman David Simmen Guy Lohman Hamid Pirahesh and Miso Cilimdzic. 2004. Robust Query Processing through Progressive Optimization. In ACM SIGMOD. 659--670.","DOI":"10.1145\/1007568.1007642"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213882"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10424-4_17"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Immanuel Trummer. 2019. Exact Cardinality Query Optimization with Bounded Execution Cost. In ACM SIGMOD. 2--17.  Immanuel Trummer. 2019. Exact Cardinality Query Optimization with Bounded Execution Cost. In ACM SIGMOD. 2--17.","DOI":"10.1145\/3299869.3300087"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:13:40Z","timestamp":1695507220000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611494"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611494","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}