{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:20:29Z","timestamp":1789435229416,"version":"build-2803163510"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>We present a non-intrusive approach to robust query processing that can be used on top of any SQL execution engine. To reduce the risk of selecting highly sub-optimal query plans, we execute multiple plans in parallel. Query processing finishes once the first of these plans finishes execution.<\/jats:p>\n          <jats:p>Plans are selected to be complementary in terms of the intermediate results they generate. This increases robustness to cardinality estimation errors, making cost prediction hard, that concern a subset of candidate results. We present multiple cost-based approaches to selecting plans for robust execution. The first approach uses a simple cost model, based on diversity of intermediate results. The second approach features a probabilistic model, approximating expected execution overheads, given uncertainty on true intermediate result sizes. We present greedy and exhaustive algorithms to select optimal plans according to those cost models. The experiments demonstrate that executing multiple plans in parallel is preferable over executing single plans that are occasionally sub-optimal, as well as over several baselines.<\/jats:p>","DOI":"10.1145\/3654973","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-25","source":"Crossref","is-referenced-by-count":5,"title":["ROME: Robust Query Optimization via Parallel Multi-Plan Execution"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-4525-9246","authenticated-orcid":false,"given":"Ziyun","family":"Wei","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7203-2349","authenticated-orcid":false,"given":"Immanuel","family":"Trummer","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Ron Avnur and Jm Hellerstein. 2000. Eddies: continuously adaptive query processing. In SIGMOD. 261--272. https:\/\/doi.org\/10.1145\/342009.335420","DOI":"10.1145\/342009.335420"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Brian Babcock and S Chaudhuri. 2005. Towards a robust query optimizer: a principled and practical approach. In SIGMOD. 119--130. http:\/\/dl.acm.org\/citation.cfm?id=1066172","DOI":"10.1145\/1066157.1066172"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Shivnath Babu Pedro Bizarro and David DeWitt. 2005. Proactive re-optimization. In SIGMOD. 107--118. https:\/\/doi.org\/10.1145\/1066157.1066171","DOI":"10.1145\/1066157.1066171"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Paul Beame Paraschos Koutris and Dan Suciu. 2014. Skew in parallel query processing. In PODS. 212--223. https:\/\/doi.org\/10.1145\/2594538.2594558 arxiv: arXiv:1401.1872v1","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.160"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--72401-0_8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276343"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543651"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303990"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Sophie Cluet and Guido Moerkotte. 1995. On the complexity of generating optimal left-deep processing trees with cross products. In ICDT. 54--67.","DOI":"10.1007\/3-540-58907-4_6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588963"},{"key":"e_1_2_1_12_1","first-page":"5","article-title":"QUEST : An exploratory approach to robust query processing","volume":"7","author":"Dutt Anshuman","year":"2014","unstructured":"Anshuman Dutt. 2014. QUEST : An exploratory approach to robust query processing. PVLDB, Vol. 7, 13 (2014), 5--8.","journal-title":"PVLDB"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Anshuman Dutt and Jayant Haritsa. 2014. Plan bouquets: query processing without selectivity estimation. In SIGMOD. 1039--1050. https:\/\/doi.org\/10.1145\/2588555.2588566","DOI":"10.1145\/2588555.2588566"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/DEXA.2000.875090"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Wook-Shin Han Wooseong Kwak Jinsoo Lee Guy M. Lohman and Volker Markl. 2008. Parallelizing query optimization. In VLDB. 188--200. https:\/\/doi.org\/10.14778\/1453856.1453882","DOI":"10.14778\/1453856.1453882"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2007.03.088"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_18_1","unstructured":"Bhaskar Himatsingka J Srivastava and TM Niccum. 2007. Tradeoffs in Parallel Query Processing and its Implications for Query Optimization. Technical Report. 1--33 pages. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.38.2043&rep=rep1&type=pdf"},{"key":"e_1_2_1_19_1","unstructured":"Arvind Hulgeri. 2004. Parametric Query Optimization. Ph. D. Dissertation. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.33.696&rep=rep1&type=pdf"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Arvind Hulgeri and S Sudarshan. 2003. AniPQO: almost non-intrusive parametric query optimization for nonlinear cost functions. In VLDB. 766--777. http:\/\/dl.acm.org\/citation.cfm?id=1315517","DOI":"10.1016\/B978-012722442-8\/50073-2"},{"key":"e_1_2_1_21_1","volume-title":"Adaptive cardinality estimation. arXiv preprint arXiv:1711.08330","author":"Ivanov Oleg","year":"2017","unstructured":"Oleg Ivanov and Sergey Bartunov. 2017. Adaptive cardinality estimation. arXiv preprint arXiv:1711.08330 (2017)."},{"key":"e_1_2_1_22_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. Citeseer, 25."},{"key":"e_1_2_1_23_1","unstructured":"H. V. Kgadish Nick Koudas S Muthukrishnan Viswanath Poosala Ken Sevcik and Torsten Suel. 1998. Optimal histograms with quality guarantees. In PVLDB. 275 -- 286."},{"key":"e_1_2_1_24_1","volume-title":"CIDR. 1--8. arxiv","author":"Kipf Andreas","year":"1809","unstructured":"Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. Learned cardinalities: estimating correlated joins with deep learning. In CIDR. 1--8. arxiv: 1809.00677 http:\/\/arxiv.org\/abs\/1809.00677"},{"key":"e_1_2_1_25_1","unstructured":"M Kremer J Gryz and Others. 1999. A survey of query optimization in parallel databases. Technical Report. Citeseer."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Ju-Hong Lee Deok-Hwan Kim and Chin-Wan Chung. 1999. Multi-dimensional selectivity estimation using compressed histogram information. In SIGMOD. 205--214. https:\/\/doi.org\/10.1145\/304181.304200","DOI":"10.1145\/304181.304200"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_28_1","volume-title":"Poisson Distribution","author":"LePine Mike","unstructured":"Mike LePine. 2022. Poisson Distribution. In College Statistics."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588711"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452838"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542702"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425882"},{"key":"e_1_2_1_34_1","volume-title":"Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research","author":"Nemhauser George L","year":"1978","unstructured":"George L Nemhauser and Laurence A Wolsey. 1978. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, Vol. 3, 3 (1978), 177--188."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389727"},{"key":"e_1_2_1_36_1","unstructured":"PostgreSQL. 2022. Group The PostgreSQL Global Development. https:\/\/www.postgresql.org. Accessed: 2023-09-07."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Li Quanzhong Shao Minglong Volker Markl Kevin Beyer Latha Colby and Guy Lohman. 2007. Adaptively Reordering Joins During Query Execution. bibinfonumpages26--35 pages. https:\/\/doi.org\/10.1109\/ICDE.2007.367848","DOI":"10.1109\/ICDE.2007.367848"},{"key":"e_1_2_1_38_1","unstructured":"Michael Stillger Guy M Lohman Volker Markl and Mokhtar Kandil. 2001. LEO - DB2's LEarning Optimizer. In PVLDB. 19--28."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2947618.2947622"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464389"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559938"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Lucas Woltmann Claudio Hartmann Maik Thiele and Dirk Habich. 2019. Cardinality estimation with local deep learning models. In aiDM. 1--8.","DOI":"10.1145\/3329859.3329875"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882914"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654973","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654973","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:38:14Z","timestamp":1755787094000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654973"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654973"],"URL":"https:\/\/doi.org\/10.1145\/3654973","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}