{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T16:53:51Z","timestamp":1792515231265,"version":"4.5.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:p>Query driven cardinality estimation models learn from a historical log of queries. They are lightweight, having low storage requirements, fast inference and training, and are easily adaptable for any kind of query. Unfortunately, such models can suffer unpredictably bad performance under workload drift, i.e., if the query pattern or data changes. This makes them unreliable and hard to deploy. We analyze the reasons why models become unpredictable due to workload drift, and introduce modifications to the query representation and neural network training techniques to make query-driven models robust to the effects of workload drift. First, we emulate workload drift in queries involving some unseen tables or columns by randomly masking out some table or column features during training. This forces the model to make predictions with missing query information, relying more on robust features based on up-to-date DBMS statistics that are useful even when query or data drift happens. Second, we introduce join bitmaps, which extends sampling-based features to be consistent across joins using ideas from sideways information passing. Finally, we show how both of these ideas can be adapted to handle data updates.<\/jats:p>\n                  <jats:p>\n                    We show significantly greater generalization than past works across different workloads and databases. For instance, a model trained with our techniques on a simple workload (JOBLight-train), with 40\n                    <jats:italic>k<\/jats:italic>\n                    synthetically generated queries of at most 3 tables each, is able to generalize to the much more complex Join Order Benchmark, which include queries with up to 16 tables, and improve query runtimes by 2\u00d7 over PostgreSQL. We show similar robustness results with data updates, and across other workloads. We discuss the situations where we expect, and see, improvements, as well as more challenging workload drift scenarios where these techniques do not improve much over PostgreSQL. However, even in the most challenging scenarios, our models never perform worse than PostgreSQL, while standard query driven models can get much worse than PostgreSQL.\n                  <\/jats:p>","DOI":"10.14778\/3583140.3583164","type":"journal-article","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T12:45:59Z","timestamp":1681994759000},"page":"1520-1533","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":81,"title":["Robust Query Driven Cardinality Estimation under Changing Workloads"],"prefix":"10.14778","volume":"16","author":[{"given":"Parimarjan","family":"Negi","sequence":"first","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ziniu","family":"Wu","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Kipf","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nesime","family":"Tatbul","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Intel Labs"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"Marcus","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Intel Labs"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sam","family":"Madden","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Kraska","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Alizadeh","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,4,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2018. SQL Server's Join Cardinality Estimation. https:\/\/www.sqlshack.com\/join-estimation-internals\/ [Online;].  2018. SQL Server's Join Cardinality Estimation. https:\/\/www.sqlshack.com\/join-estimation-internals\/ [Online;]."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304581"},{"key":"e_1_2_1_3_1","volume-title":"Understanding dropout. Advances in neural information processing systems 26","author":"Baldi Pierre","year":"2013","unstructured":"Pierre Baldi and Peter J Sadowski . 2013. Understanding dropout. Advances in neural information processing systems 26 ( 2013 ). Pierre Baldi and Peter J Sadowski. 2013. Understanding dropout. Advances in neural information processing systems 26 (2013)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_5_1","volume-title":"Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates. arXiv preprint arXiv:2111.00163","author":"Datta Asoke","year":"2021","unstructured":"Asoke Datta , Yesdaulet Izenov , Brian Tsan , and Florin Rusu . 2021. Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates. arXiv preprint arXiv:2111.00163 ( 2021 ). Asoke Datta, Yesdaulet Izenov, Brian Tsan, and Florin Rusu. 2021. Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates. arXiv preprint arXiv:2111.00163 (2021)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407820"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_8_1","unstructured":"Ergast. 2021. Ergast F1 Database Schema. https:\/\/relational.fit.cvut.cz\/assets\/img\/datasets-generated\/ErgastF1.svg [Online;].  Ergast. 2021. Ergast F1 Database Schema. https:\/\/relational.fit.cvut.cz\/assets\/img\/datasets-generated\/ErgastF1.svg [Online;]."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375727"},{"key":"e_1_2_1_10_1","volume-title":"Selectivity correction with online machine learning. arXiv preprint arXiv:2009.09884","author":"Halford Max","year":"2020","unstructured":"Max Halford , Philippe Saint-Pierre , and Franck Morvan . 2020. Selectivity correction with online machine learning. arXiv preprint arXiv:2009.09884 ( 2020 ). Max Halford, Philippe Saint-Pierre, and Franck Morvan. 2020. Selectivity correction with online machine learning. arXiv preprint arXiv:2009.09884 (2020)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389741"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2020.15"},{"key":"e_1_2_1_14_1","volume-title":"11th Conference on Innovative Data Systems Research, CIDR","author":"Hertzschuch Axel","year":"2021","unstructured":"Axel Hertzschuch , Claudio Hartmann , Dirk Habich , and Wolfgang Lehner . 2021. Simplicity Done Right for Join Ordering . In 11th Conference on Innovative Data Systems Research, CIDR 2021 , Virtual Event, January 11-15, 2021, Online Proceedings . www.cidrdb.org. http:\/\/cidrdb.org\/cidr2021\/papers\/cidr2021_paper01.pdf Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering. In 11th Conference on Innovative Data Systems Research, CIDR 2021, Virtual Event, January 11-15, 2021, Online Proceedings. www.cidrdb.org. http:\/\/cidrdb.org\/cidr2021\/papers\/cidr2021_paper01.pdf"},{"key":"e_1_2_1_15_1","volume-title":"One model to rule them all: towards zero-shot learning for databases. arXiv preprint arXiv:2105.00642","author":"Hilprecht Benjamin","year":"2021","unstructured":"Benjamin Hilprecht and Carsten Binnig . 2021. One model to rule them all: towards zero-shot learning for databases. arXiv preprint arXiv:2105.00642 ( 2021 ). Benjamin Hilprecht and Carsten Binnig. 2021. One model to rule them all: towards zero-shot learning for databases. arXiv preprint arXiv:2105.00642 (2021)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_17_1","unstructured":"Zachary G Ives and Nicholas E Taylor. 2008. Sideways information passing for push-style query processing. (2008).  Zachary G Ives and Nicholas E Taylor. 2008. Sideways information passing for push-style query processing. (2008)."},{"key":"e_1_2_1_18_1","volume-title":"Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned cardinality estimation: An in-depth study. In Proceedings of the 2022 International Conference on Management of Data. 1214--1227","author":"Kim Kyoungmin","unstructured":"Kyoungmin Kim , Jisung Jung , In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned cardinality estimation: An in-depth study. In Proceedings of the 2022 International Conference on Management of Data. 1214--1227 . Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned cardinality estimation: An in-depth study. In Proceedings of the 2022 International Conference on Management of Data. 1214--1227."},{"key":"e_1_2_1_19_1","volume-title":"1st International Workshop on Applied AI for Database Systems and Applications.","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf , Michael Freitag , Dimitri Vorona , Peter Boncz , Thomas Neumann , and Alfons Kemper . 2019 . Estimating filtered group-by queries is hard: Deep learning to the rescue . In 1st International Workshop on Applied AI for Database Systems and Applications. Andreas Kipf, Michael Freitag, Dimitri Vorona, Peter Boncz, Thomas Neumann, and Alfons Kemper. 2019. Estimating filtered group-by queries is hard: Deep learning to the rescue. In 1st International Workshop on Applied AI for Database Systems and Applications."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320218"},{"key":"e_1_2_1_21_1","volume-title":"Captum: A unified and generic model interpretability library for pytorch. arXiv preprint arXiv:2009.07896","author":"Kokhlikyan Narine","year":"2020","unstructured":"Narine Kokhlikyan , Vivek Miglani , Miguel Martin , Edward Wang , Bilal Alsallakh , Jonathan Reynolds , Alexander Melnikov , Natalia Kliushkina , Carlos Araya , Siqi Yan , 2020 . Captum: A unified and generic model interpretability library for pytorch. arXiv preprint arXiv:2009.07896 (2020). Narine Kokhlikyan, Vivek Miglani, Miguel Martin, Edward Wang, Bilal Alsallakh, Jonathan Reynolds, Alexander Melnikov, Natalia Kliushkina, Carlos Araya, Siqi Yan, et al. 2020. Captum: A unified and generic model interpretability library for pytorch. arXiv preprint arXiv:2009.07896 (2020)."},{"key":"e_1_2_1_22_1","volume-title":"VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases","author":"Seetha Lakshmi M.","year":"1998","unstructured":"M. Seetha Lakshmi and Shaoyu Zhou . 1998. Selectivity Estimation in Extensible Databases - A Neural Network Approach . In VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases , August 24-27, 1998 , New York City, New York, USA , Ashish Gupta, Oded Shmueli, and Jennifer Widom (Eds.). Morgan Kaufmann , 623--627. http:\/\/www.vldb.org\/conf\/1998\/p623.pdf M. Seetha Lakshmi and Shaoyu Zhou. 1998. Selectivity Estimation in Extensible Databases - A Neural Network Approach. In VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA, Ashish Gupta, Oded Shmueli, and Jennifer Widom (Eds.). Morgan Kaufmann, 623--627. http:\/\/www.vldb.org\/conf\/1998\/p623.pdf"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526179"},{"key":"e_1_2_1_25_1","volume-title":"3rd International Workshop on Applied AI for Database Systems and Applications (AIDB).","author":"Li Beibin","year":"2021","unstructured":"Beibin Li , Yao Lu , Chi Wang , and Srikanth Kandula . 2021 . Cardinality Estimation: Is Machine Learning a Silver Bullet . In 3rd International Workshop on Applied AI for Database Systems and Applications (AIDB). Beibin Li, Yao Lu, Chi Wang, and Srikanth Kandula. 2021. Cardinality Estimation: Is Machine Learning a Silver Bullet. In 3rd International Workshop on Applied AI for Database Systems and Applications (AIDB)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476254"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542703"},{"key":"e_1_2_1_28_1","volume-title":"Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711","author":"Marcus Ryan","year":"2019","unstructured":"Ryan Marcus , Parimarjan Negi , Hongzi Mao , Chi Zhang , Mohammad Alizadeh , Tim Kraska , Olga Papaemmanouil , and Nesime Tatbul . 2019 . Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711 (2019). Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, and Nesime Tatbul. 2019. Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711 (2019)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_30_1","unstructured":"Parimarjan Negi. 2022. Robust Query Driven Cardinality Estimation under Changing Workloads: Online Appendix. Retrieved 2022 from https:\/\/parimarjan.github.io\/robust_cardinality_appendix.pdf [Online;].  Parimarjan Negi. 2022. Robust Query Driven Cardinality Estimation under Changing Workloads: Online Appendix. Retrieved 2022 from https:\/\/parimarjan.github.io\/robust_cardinality_appendix.pdf [Online;]."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW49219.2020.00034"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_1_33_1","unstructured":"Andreas Kipf Hongzi Mao Nesime Tatbul Tim Kraska Mohammad Alizadeh Parimarjan Negi Ryan Marcus. 2021. Cardinality Estimation Benchmark. https:\/\/github.com\/learnedsystems\/ceb [Online;].  Andreas Kipf Hongzi Mao Nesime Tatbul Tim Kraska Mohammad Alizadeh Parimarjan Negi Ryan Marcus. 2021. Cardinality Estimation Benchmark. https:\/\/github.com\/learnedsystems\/ceb [Online;]."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389727"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436907"},{"key":"e_1_2_1_36_1","volume-title":"VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases","author":"Stillger Michael","year":"2001","unstructured":"Michael Stillger , Guy M. Lohman , Volker Markl , and Mokhtar Kandil . 2001 . LEO - DB2's LEarning Optimizer . In VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases , September 11-14, 2001, Roma, Italy, Peter M. G. Apers, Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Kotagiri Ramamohanarao, and Richard T. Snodgrass (Eds.). Morgan Kaufmann, 19--28. http:\/\/www.vldb.org\/conf\/ 2001\/P019.pdf Michael Stillger, Guy M. Lohman, Volker Markl, and Mokhtar Kandil. 2001. LEO - DB2's LEarning Optimizer. In VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September 11-14, 2001, Roma, Italy, Peter M. G. Apers, Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Kotagiri Ramamohanarao, and Richard T. Snodgrass (Eds.). Morgan Kaufmann, 19--28. http:\/\/www.vldb.org\/conf\/2001\/P019.pdf"},{"key":"e_1_2_1_37_1","volume-title":"International conference on machine learning. PMLR, 3319--3328","author":"Sundararajan Mukund","year":"2017","unstructured":"Mukund Sundararajan , Ankur Taly , and Qiqi Yan . 2017 . Axiomatic attribution for deep networks . In International conference on machine learning. PMLR, 3319--3328 . Mukund Sundararajan, Ankur Taly, and Qiqi Yan. 2017. Axiomatic attribution for deep networks. In International conference on machine learning. PMLR, 3319--3328."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402724"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329859.3329875"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452830"},{"key":"e_1_2_1_42_1","volume-title":"FactorJoin: A New Cardinality Estimation Framework for Join Queries. arXiv preprint arXiv:2212.05526","author":"Wu Ziniu","year":"2022","unstructured":"Ziniu Wu , Parimarjan Negi , Mohammad Alizadeh , Tim Kraska , and Samuel Madden . 2022. FactorJoin: A New Cardinality Estimation Framework for Join Queries. arXiv preprint arXiv:2212.05526 ( 2022 ). Ziniu Wu, Parimarjan Negi, Mohammad Alizadeh, Tim Kraska, and Samuel Madden. 2022. FactorJoin: A New Cardinality Estimation Framework for Join Queries. arXiv preprint arXiv:2212.05526 (2022)."},{"key":"e_1_2_1_43_1","volume-title":"BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv preprint arXiv:2012.14743","author":"Wu Ziniu","year":"2020","unstructured":"Ziniu Wu , Amir Shaikhha , Rong Zhu , Kai Zeng , Yuxing Han , and Jingren Zhou . 2020. BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv preprint arXiv:2012.14743 ( 2020 ). Ziniu Wu, Amir Shaikhha, Rong Zhu, Kai Zeng, Yuxing Han, and Jingren Zhou. 2020. BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv preprint arXiv:2012.14743 (2020)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461539"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3583140.3583164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T12:55:24Z","timestamp":1681995324000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3583140.3583164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2]]},"references-count":46,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.14778\/3583140.3583164"],"URL":"https:\/\/doi.org\/10.14778\/3583140.3583164","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,2]]},"assertion":[{"value":"2023-04-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}