{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:03:12Z","timestamp":1757610192889,"version":"3.44.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:p>Query optimizers in RDBMSs search for execution plans expected to be optimal for given queries. They use parameter estimates, often inaccurate, and make assumptions that may not hold in practice. Consequently, they may select plans that are suboptimal at runtime, if estimates and assumptions are not valid. Therefore, they do not sufficiently support robust query optimization. Using ML to improve data systems has shown promising results for query optimization. Inspired by this, we propose Robust Query Optimizer, (Roq), a holistic framework based on a risk-aware learning approach. Roq includes a novel formalization of the notion of robustness in the context of query optimization and a principled approach for its quantification and measurement based on approximate probabilistic ML. It also includes novel strategies and algorithms for query plan evaluation and selection. Roq includes a novel learned cost model that is designed to predict the cost of query execution and the associated risks and performs query optimization accordingly. We demonstrate that Roq provides significant improvements in robust query optimization compared with the state-of-the-art.<\/jats:p>","DOI":"10.14778\/3742728.3742753","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T13:32:53Z","timestamp":1756906373000},"page":"2626-2638","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Robust Plan Evaluation Based on Approximate Probabilistic Machine Learning"],"prefix":"10.14778","volume":"18","author":[{"given":"Amin","family":"Kamali","sequence":"first","affiliation":[{"name":"University of Ottawa, Ottawa, Canada"}]},{"given":"Verena","family":"Kantere","sequence":"additional","affiliation":[{"name":"University of Ottawa, Ottawa, Canada"}]},{"given":"Calisto","family":"Zuzarte","sequence":"additional","affiliation":[{"name":"IBM Canada Lab, Markham, Canada"}]},{"given":"Vincent","family":"Corvinelli","sequence":"additional","affiliation":[{"name":"IBM Canada Lab, Markham, Canada"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"B. Babcock and S. Chaudhuri. 2005. Towards a robust query optimizer: A principled and practical approach. 119\u2013130. 10.1145\/1066157.1066172","DOI":"10.1145\/1066157.1066172"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Shivnath Babu Pedro Bizarro and David DeWitt. 2005. Proactive re-optimization. In ACM SIGMOD. 107\u2013118.","DOI":"10.1145\/1066157.1066171"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0507-8"},{"key":"e_1_2_1_4_1","first-page":"1777","article-title":"LOGER","volume":"16","author":"Chen Tianyi","year":"2023","unstructured":"Tianyi Chen, Jun Gao, Hedui Chen, and Yaofeng Tu. 2023. LOGER: A Learned Optimizer Towards Generating Efficient and Robust Query Execution Plans. 16, 7 (2023), 1777\u20131789.","journal-title":"A Learned Optimizer Towards Generating Efficient and Robust Query Execution Plans."},{"key":"e_1_2_1_5_1","volume-title":"Implications of certain assumptions in database performance evauation. 9, 2","author":"Christodoulakis S.","year":"1984","unstructured":"S. Christodoulakis. 1984. Implications of certain assumptions in database performance evauation. 9, 2 (1984), 163\u2013186."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Francis Chu Joseph Halpern and Johannes Gehrke. 2002. Least expected cost query optimization: what can we expect?. In ACM PODS. 293\u2013302.","DOI":"10.1145\/543613.543651"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_1_8_1","volume-title":"Haritsa","author":"Dutt Anshuman","year":"2016","unstructured":"Anshuman Dutt and Jayant R. Haritsa. 2016. Plan Bouquets: A Fragrant Approach to Robust Query Processing. 41, 2 (2016), 11:1\u201311:37."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of The 33rd International Conference on Machine Learning (2016-06-11)","author":"Gal Yarin","year":"2016","unstructured":"Yarin Gal and Zoubin Ghahramani. 2016. Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning. In Proceedings of The 33rd International Conference on Machine Learning (2016-06-11). PMLR, 1050\u20131059. ISSN: 1938-7228."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"1513","DOI":"10.1007\/s10462-023-10562-9","article-title":"A survey of uncertainty in deep neural networks","volume":"56","author":"al Gawlikowski Jakob","year":"2023","unstructured":"Jakob et al Gawlikowski. 2023. A survey of uncertainty in deep neural networks. Artificial Intelligence Review 56, 1 (2023), 1513\u20131589.","journal-title":"Artificial Intelligence Review"},{"key":"e_1_2_1_11_1","volume-title":"Robust query processing: mission possible. 13, 12","author":"Haritsa Jayant R.","year":"2020","unstructured":"Jayant R. Haritsa. 2020. Robust query processing: mission possible. 13, 12 (2020), 3425\u20133428."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2021 International Conference on Management of Data","author":"Hertzschuch Axel","year":"2021","unstructured":"Axel Hertzschuch, Guido Moerkotte, Wolfgang Lehner, Norman May, Florian Wolf, and Lars Fricke. 2021. Small Selectivities Matter: Lifting the Burden of Empty Samples. In Proceedings of the 2021 International Conference on Management of Data (New York, NY, USA, 2021-06-09) (SIGMOD '21). Association for Computing Machinery, 697\u2013709."},{"key":"e_1_2_1_13_1","unstructured":"Benjamin Hilprecht and Carsten Binnig. 2022. One Model to Rule them All: Towards Zero-Shot Learning for Databases. In CIDR."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-021-05946-3"},{"key":"e_1_2_1_16_1","unstructured":"Amin Kamali Verena Kantere Calisto Zuzarte and Vincent Corvinelli. 2024. Robust Plan Evaluation based on Approximate Probabilistic Machine Learning. arXiv:2401.15210 [cs.DB]"},{"volume-title":"Platform-independent robust query processing","author":"Karthik Srinivas","key":"e_1_2_1_17_1","unstructured":"Srinivas Karthik, Jayant R. Haritsa, Sreyash Kenkre, and Vinayaka Pandit. 2016. Platform-independent robust query processing. In IEEEICDE. 325\u2013336."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275366.3284964"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994529"},{"key":"e_1_2_1_20_1","volume-title":"International Conference on Neural Information Processing Systems. 5580\u20135590","author":"Kendall Alex","year":"2017","unstructured":"Alex Kendall and Yarin Gal. 2017. What uncertainties do we need in Bayesian deep learning for computer vision?. In International Conference on Neural Information Processing Systems. 5580\u20135590."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Liam Li Kevin Jamieson Afshin Rostamizadeh Ekaterina Gonina Moritz Hardt Benjamin Recht and Ameet Talwalkar. 2020. A System for Massively Parallel Hyperparameter Tuning. arXiv:1810.05934 [cs stat] 10.48550\/arXiv.1810.05934","DOI":"10.48550\/arXiv.1810.05934"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2021 International Conference on Management of Data (2021-06-18)","author":"Marcus Ryan","year":"2024","unstructured":"Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. 2024. Bao: Making Learned Query Optimization Practical. In Proceedings of the 2021 International Conference on Management of Data (2021-06-18) (SIGMOD '21). Association for Computing Machinery, 1275\u20131288."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"1705","DOI":"10.14778\/3342263.3342644","article-title":"Neo: a learned query optimizer","volume":"12","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. Proc. of VLDB Endow. 12, 11 (2019), 1705\u20131718.","journal-title":"Proc. of VLDB Endow."},{"key":"e_1_2_1_25_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\u2013670.","DOI":"10.1145\/1007568.1007642"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence","author":"Mou Lili","year":"2016","unstructured":"Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. 2016. Convolutional neural networks over tree structures for programming language processing. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (Phoenix, Arizona, 2016-02-12) (AAAI'16). AAAI Press, 1287\u20131293."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Chiraz Moumen Franck Morvan and Abdelkader Hameurlain. 2016. Handling Estimation Inaccuracy in Query Optimization. In Web Technologies and Applications (Cham). 355\u2013367.","DOI":"10.1007\/978-3-319-45817-5_28"},{"key":"e_1_2_1_29_1","volume-title":"VLDB","volume":"6","author":"Nambiar Raghunath Othayoth","year":"2006","unstructured":"Raghunath Othayoth Nambiar and Meikel Poess. 2006. The Making of TPC-DS.. In VLDB (2006), Vol. 6. 1049\u20131058."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN'94)","volume":"1","author":"Nix D.A.","year":"1994","unstructured":"D.A. Nix and A.S. Weigend. 1994. Estimating the mean and variance of the target probability distribution. In Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN'94) (1994-06), Vol. 1. 55\u201360 vol.1."},{"key":"e_1_2_1_32_1","unstructured":"Joe Sack. 2019. Introducing Batch Mode Adaptive Joins. https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/introducing-batch-mode-adaptive-joins\/ba-p\/385411"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Yunsheng Shi Zhengjie Huang Shikun Feng Hui Zhong Wenjin Wang and Yu Sun. 2021. Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification. arXiv:2009.03509 [cs stat] 10.48550\/arXiv.2009.03509","DOI":"10.48550\/arXiv.2009.03509"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Tarique Siddiqui Alekh Jindal Shi Qiao Hiren Patel and Wangchao Le. 2020. Cost Models for Big Data Query Processing: Learning Retrofitting and Our Findings. In ACM SIGMOD. 99\u2013113.","DOI":"10.1145\/3318464.3380584"},{"key":"e_1_2_1_35_1","volume-title":"Advances in Neural Information Processing Systems (2017","volume":"30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, \u0141ukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems (2017), Vol. 30. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2017\/hash\/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html"},{"key":"e_1_2_1_36_1","volume-title":"2023 IEEE Sixth International Conference on Artificial Intelligence and Knowledge Engineering (AIKE) (2023-09)","author":"Wang Ning","year":"2023","unstructured":"Ning Wang, Amin Kamali, Verena Kantere, Calisto Zuzate, Vincent Corvinelli, Brandon Frendo, and Steve Donoghue. 2023. A Hybrid Cost Model for Evaluating Query Execution Plans. In 2023 IEEE Sixth International Conference on Artificial Intelligence and Knowledge Engineering (AIKE) (2023-09). 133\u2013138. ISSN: 2831-7203. 10.1109\/AIKE59827.2023.00030"},{"key":"e_1_2_1_37_1","volume-title":"Robustness metrics for relational query execution plans. 11, 11","author":"Wolf Florian","year":"2018","unstructured":"Florian Wolf, Michael Brendle, Norman May, Paul R. Willems, Kai-Uwe Sattler, and Michael Grossniklaus. 2018. Robustness metrics for relational query execution plans. 11, 11 (2018), 1360\u20131372."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 2022 International Conference on Management of Data","author":"Yang Zongheng","year":"2022","unstructured":"Zongheng Yang, Wei-Lin Chiang, Sifei Luan, Gautam Mittal, Michael Luo, and Ion Stoica. 2022. Balsa: Learning a Query Optimizer Without Expert Demonstrations. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD '22). Association for Computing Machinery, New York, NY, USA, 931\u2013944. 10.1145\/3514221.3517885"},{"key":"e_1_2_1_39_1","first-page":"25","article-title":"Robust Query Optimization Methods With Respect to Estimation Errors","volume":"44","author":"Yin Shaoyi","year":"2015","unstructured":"Shaoyi Yin, Abdelkader Hameurlain, and Franck Morvan. 2015. Robust Query Optimization Methods With Respect to Estimation Errors: A Survey. 44, 3 (2015), 25\u201336.","journal-title":"A Survey."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565846"},{"key":"e_1_2_1_41_1","volume-title":"Reinforcement Learning with Tree-LSTM for Join Order Selection. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 1297\u20131308","author":"Yu Xiang","year":"2020","unstructured":"Xiang Yu, Guoliang Li, Chengliang Chai, and Nan Tang. 2020. Reinforcement Learning with Tree-LSTM for Join Order Selection. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 1297\u20131308. 10.1109\/ICDE48307.2020.00116"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611501"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3090163.3090167"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583160"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3742728.3742753","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T13:37:26Z","timestamp":1756906646000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3742728.3742753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4]]},"references-count":44,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["10.14778\/3742728.3742753"],"URL":"https:\/\/doi.org\/10.14778\/3742728.3742753","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,4]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}