{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:16Z","timestamp":1778807896834,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>\n            The effectiveness of a query optimizer relies on the accuracy of selectivity estimates. The execution plan generated by the optimizer can be extremely poor in reality due to uncertainty in these estimates. This paper presents\n            <jats:bold>PARQO<\/jats:bold>\n            (\n            <jats:bold>P<\/jats:bold>\n            enalty-\n            <jats:bold>A<\/jats:bold>\n            ware\n            <jats:bold>R<\/jats:bold>\n            obust Plan Selection in\n            <jats:bold>Q<\/jats:bold>\n            uery\n            <jats:bold>O<\/jats:bold>\n            ptimization), a novel system where users can define powerful robustness metrics that assess the expected penalty of a plan with respect to true optimal plans under uncertain selectivity estimates. PARQO uses workload-informed profiling to build error models, and employs principled sensitivity analysis techniques to identify human-interpretable selectivity dimensions with the largest impact on penalty. Experiments on three benchmarks demonstrate that PARQO finds robust, performant plans, and enables efficient and effective parametric optimization.\n          <\/jats:p>","DOI":"10.14778\/3704965.3704971","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:22:57Z","timestamp":1739899377000},"page":"4627-4640","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["PARQO: Penalty-Aware Robust Plan Selection in Query Optimization"],"prefix":"10.14778","volume":"17","author":[{"given":"Haibo","family":"Xiu","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Yang","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.14778\/1920841.1920983","article-title":"On the stability of plan costs and the costs of plan stability","volume":"3","author":"Abhirama M","year":"2010","unstructured":"M Abhirama, Sourjya Bhaumik, Atreyee Dey, Harsh Shrimal, and Jayant R Haritsa. 2010. On the stability of plan costs and the costs of plan stability. Proceedings of the VLDB Endowment 3, 1-2 (2010), 1137--1148.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.57"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066172"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066171"},{"key":"e_1_2_1_6_1","volume-title":"Dagstuhl Reports","volume":"7","author":"Borovica-Gajic Renata","year":"2017","unstructured":"Renata Borovica-Gajic, Goetz Graefe, and Allison Lee. 2017. Robust performance in database query processing (Dagstuhl seminar 17222). In Dagstuhl Reports, Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AAP1326"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807226"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687739"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303990"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454173"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588963"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588566"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064040"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733036"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1338438.1338530"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50024-X"},{"key":"e_1_2_1_19_1","volume-title":"Dagstuhl Reports","volume":"2","author":"Graefe Goetz","year":"2012","unstructured":"Goetz Graefe, Wey Guy, Harumi Anne Kuno, and Glenn Paullley. 2012. Robust query processing (dagstuhl seminar 12321). In Dagstuhl Reports, Vol. 2. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_20_1","volume-title":"Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, et al.","author":"Han Yuxing","year":"2021","unstructured":"Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, et al. 2021. Cardinality estimation in DBMS: A comprehensive benchmark evaluation. arXiv preprint arXiv:2109.05877 (2021)."},{"key":"e_1_2_1_21_1","unstructured":"D Harish Pooja N Darera and Jayant R Haritsa. 2007. On the production of anorexic plan diagrams. (2007)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00242"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 31st international conference on Very large data bases. VLDB Endowment. 1228--1239","author":"Haritsa Naveen Reddy","year":"2005","unstructured":"Naveen Reddy Jayant R Haritsa. 2005. Analyzing plan diagrams of database query optimizers. In Proceedings of the 31st international conference on Very large data bases. VLDB Endowment. 1228--1239."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452805"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517896"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50023-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050037"},{"key":"e_1_2_1_29_1","volume-title":"VLDB","volume":"24","author":"Darera Jayant Harish D","year":"2008","unstructured":"Harish D Pooja N Darera Jayant and R Haritsa. 2008. Identifying robust plans through plan diagram reduction. In VLDB, Vol. 24."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"2183","DOI":"10.14778\/3275366.3284964","article-title":"A concave path to low-overhead robust query processing","volume":"11","author":"Karthik Srinivas","year":"2018","unstructured":"Srinivas Karthik, Jayant R Haritsa, Sreyash Kenkre, and Vinayaka Pandit. 2018. A concave path to low-overhead robust query processing. Proceedings of the VLDB Endowment 11, 13 (2018), 2183--2195.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_31_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)."},{"key":"e_1_2_1_32_1","volume-title":"Bayesian estimates of equation system parameters: an application of integration by Monte Carlo. Econometrica: Journal of the Econometric Society","author":"Kloek Teun","year":"1978","unstructured":"Teun Kloek and Herman K Van Dijk. 1978. Bayesian estimates of equation system parameters: an application of integration by Monte Carlo. Econometrica: Journal of the Econometric Society (1978), 1--19."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611494"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_35_1","first-page":"1","article-title":"dbET: Execution Time Distribution-based Plan Selection","volume":"1","author":"Li Yifan","year":"2023","unstructured":"Yifan Li, Xiaohui Yu, Nick Koudas, Shu Lin, Calvin Sun, and Chong Chen. 2023. dbET: Execution Time Distribution-based Plan Selection. Proceedings of the ACM on Management of Data 1, 1 (2023), 1--26.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452838"},{"key":"e_1_2_1_37_1","unstructured":"Microsoft. 2023. Monitoring Performance By Using the Query Store. https:\/\/learn.microsoft.com\/en-us\/sql\/relational-databases\/performance\/monitoring-performance-by-using-the-query-store?view=sql-server-ver16. Accessed: 2024-05-28."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1991.10484804"},{"key":"e_1_2_1_39_1","unstructured":"Satoshi Nagayasu. 2023. pg_hint_plan. https:\/\/github.com\/ossc-db\/pg_hint_plan."},{"key":"e_1_2_1_40_1","first-page":"1049","article-title":"The Making of TPC-DS","volume":"6","author":"Nambiar Raghunath Othayoth","year":"2006","unstructured":"Raghunath Othayoth Nambiar and Meikel Poess. 2006. The Making of TPC-DS.. In VLDB, Vol. 6. 1049--1058.","journal-title":"VLDB"},{"key":"e_1_2_1_42_1","volume-title":"Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index. Computer physics communications 181, 2","author":"Saltelli Andrea","year":"2010","unstructured":"Andrea Saltelli, Paola Annoni, Ivano Azzini, Francesca Campolongo, Marco Ratto, and Stefano Tarantola. 2010. Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index. Computer physics communications 181, 2 (2010), 259--270."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263687"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4754(00)00270-6"},{"key":"e_1_2_1_45_1","volume-title":"Introduction to stochastic search and optimization: estimation, simulation, and control","author":"Spall James C","unstructured":"James C Spall. 2005. Introduction to stochastic search and optimization: estimation, simulation, and control. John Wiley & Sons."},{"key":"e_1_2_1_46_1","volume-title":"Proc. 22th Annu. IEEE Int. Conf. Data Eng. 39--39","author":"Srivastava U.","unstructured":"U. Srivastava, P. J. Haas, V. Markl, M. Kutsch, and T. M. Tran. 2006. Isomer: Consistent histogram construction using query feedback. In Proc. 22th Annu. IEEE Int. Conf. Data Eng. 39--39."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554854"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464389"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494126"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cageo.2013.06.006"},{"key":"e_1_2_1_51_1","volume-title":"ARENA: Alternative Relational Query Plan Exploration for Database Education. In Companion of the 2023 International Conference on Management of Data","author":"Wang Hu","year":"2023","unstructured":"Hu Wang, Hui Li, Sourav S Bhowmick, and Baochao Xu. 2023. ARENA: Alternative Relational Query Plan Exploration for Database Education. In Companion of the 2023 International Conference on Management of Data (Seattle, WA, USA) (SIGMOD '23). Association for Computing Machinery, New York, NY, USA, 107--110."},{"key":"e_1_2_1_52_1","volume-title":"Are we ready for learned cardinality estimation? arXiv preprint arXiv:2012.06743","author":"Wang Xiaoying","year":"2020","unstructured":"Xiaoying Wang, Changbo Qu, Weiyuan Wu, Jiannan Wang, and Qingqing Zhou. 2020. Are we ready for learned cardinality estimation? arXiv preprint arXiv:2012.06743 (2020)."},{"key":"e_1_2_1_53_1","first-page":"11","article-title":"Robustness metrics for relational query execution plans","volume":"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. Proc. VLDB Endow. 11, 11 (jul 2018), 1360--1372.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183742"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375724"},{"key":"e_1_2_1_56_1","unstructured":"Haibo Xiu. 2024. GitHub Repository of PARQO. https:\/\/github.com\/Hap-Hugh\/PARQO"},{"key":"e_1_2_1_57_1","unstructured":"Haibo Xiu Pankaj K. Agarwal and Jun Yang. 2024. (Full Version Paper) PARQO: Penalty-Aware Robust Plan Selection in Query Optimization. https:\/\/arxiv.org\/abs\/2406.01526"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854006.2854012"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3704965.3704971","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:33:03Z","timestamp":1739899983000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3704965.3704971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":55,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["10.14778\/3704965.3704971"],"URL":"https:\/\/doi.org\/10.14778\/3704965.3704971","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"2025-02-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}