{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:09Z","timestamp":1778807829551,"version":"3.51.4"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"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":[[2023,5,26]]},"abstract":"<jats:p>While selecting the execution plan for a given query based on a single estimated cost is a generally-adopted strategy, it is usually error-prone and fails to comprehensively profile the plan performance. In this work, we complement existing plan selection methods by proposing a new approach named ET, which produces execution time distributions for query plans utilizing conformal predictions. We develop dbET, a framework that integrates ET into an existing DBMS, requiring no modification to the DBMS and only incurring minor overhead to query processing. Based on the execution time distribution, we design several intuitive yet fundamental query execution objectives and devise the corresponding plan selection strategies. Our experiments on several widely-adopted benchmarks showcase that our design significantly improves the capability of DBMSs in achieving the designated objectives.<\/jats:p>","DOI":"10.1145\/3588711","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":6,"title":["dbET: Execution Time Distribution-based Plan Selection"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-0658-1094","authenticated-orcid":false,"given":"Yifan","family":"Li","sequence":"first","affiliation":[{"name":"York University, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8170-2327","authenticated-orcid":false,"given":"Xiaohui","family":"Yu","sequence":"additional","affiliation":[{"name":"York University, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5648-0638","authenticated-orcid":false,"given":"Nick","family":"Koudas","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3111-2940","authenticated-orcid":false,"given":"Shu","family":"Lin","sequence":"additional","affiliation":[{"name":"Huawei Technologies Canada, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8521-9170","authenticated-orcid":false,"given":"Calvin","family":"Sun","sequence":"additional","affiliation":[{"name":"Huawei Technologies Canada, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5684-6953","authenticated-orcid":false,"given":"Chong","family":"Chen","sequence":"additional","affiliation":[{"name":"Huawei Technologies Canada, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"David J Aldous. 1985. Exchangeability and related topics. In \u00c9cole d'\u00c9t\u00e9 de Probabilit\u00e9s de Saint-Flour XIII-1983. Springer 1--198.","DOI":"10.1007\/BFb0099421"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066172"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807226"},{"key":"e_1_2_2_5_1","volume-title":"Probability theory: independence, interchangeability, martingales","author":"Chow Yuan Shih","unstructured":"Yuan Shih Chow and Henry Teicher. 2003. Probability theory: independence, interchangeability, martingales. Springer Science & Business Media."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375685"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Anshuman Dutt and Jayant R Haritsa. 2016. Plan bouquets: A fragrant approach to robust query processing. ACM Transactions on Database Systems (TODS) 1--37.","DOI":"10.1145\/2901738"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407820"},{"key":"e_1_2_2_10_1","volume":"202","author":"Barber Rina Foygel","unstructured":"Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. 2021. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 455--482.","journal-title":"Ryan J Tibshirani."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375727"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164145"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Benjamin Hilprecht Andreas Schmidt Moritz Kulessa Alejandro Molina Kristian Kersting and Carsten Binnig. 2020. DeepDB: Learn from Data not from Queries! Proceedings of the VLDB Endowment 992--1005.","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457546"},{"key":"e_1_2_2_15_1","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."},{"key":"e_1_2_2_16_1","volume-title":"Distribution-Free Prediction Intervals for Deep Networks. In The 23rd International Conference on Artificial Intelligence and Statistics. 4346--4356","author":"Kivaranovic Danijel","year":"2020","unstructured":"Danijel Kivaranovic, Kory D. Johnson, and Hannes Leeb. 2020a. Adaptive, Distribution-Free Prediction Intervals for Deep Networks. In The 23rd International Conference on Artificial Intelligence and Statistics. 4346--4356."},{"key":"e_1_2_2_17_1","volume-title":"International Conference on Artificial Intelligence and Statistics. 4346--4356","author":"Kivaranovic Danijel","year":"2020","unstructured":"Danijel Kivaranovic, Kory D Johnson, and Hannes Leeb. 2020b. Adaptive, distribution-free prediction intervals for deep networks. In International Conference on Artificial Intelligence and Statistics. 4346--4356."},{"key":"e_1_2_2_18_1","volume-title":"Auctions: theory and practice","author":"Klemperer Paul","unstructured":"Paul Klemperer. 2004. Auctions: theory and practice. Princeton University Press."},{"key":"e_1_2_2_19_1","volume-title":"International Conference on Machine Learning. 5637--5664","author":"Koh Pang Wei","year":"2021","unstructured":"Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. 2021. Wilds: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning. 5637--5664."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Jing Lei Max G'Sell Alessandro Rinaldo Ryan J Tibshirani and Larry Wasserman. 2018. Distribution-free predictive inference for regression. J. Amer. Statist. Assoc. 1094--1111.","DOI":"10.1080\/01621459.2017.1307116"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Jing Lei and Larry Wasserman. 2014. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 71--96.","DOI":"10.1111\/rssb.12021"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_2_23_1","volume-title":"8th Biennial Conference on Innovative Data Systems Research, CIDR.","author":"Leis Viktor","year":"2017","unstructured":"Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper, and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling.. In 8th Biennial Conference on Innovative Data Systems Research, CIDR."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.93611"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452838"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213882"},{"key":"e_1_2_2_29_1","unstructured":"N\/A. Technical report of \u201cdbET: Execution Time Distribution-based Plan Selection\u201d. https:\/\/drive.google.com\/file\/d\/1S3hsWOsuafeqoPffqE6gKW6-y8e7SFgt\/view."},{"key":"e_1_2_2_30_1","unstructured":"Parimarjan Negi Ryan Marcus Andreas Kipf Hongzi Mao Nesime Tatbul Tim Kraska and Mohammad Alizadeh. 2021. Flow-Loss: learning cardinality estimates that matter. arXiv preprint arXiv:2101.04964."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/369275.369291"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233342"},{"key":"e_1_2_2_33_1","unstructured":"Yaniv Romano Evan Patterson and Emmanuel Candes. 2019. Conformalized quantile regression. Advances in neural information processing systems 3538--3548."},{"key":"e_1_2_2_34_1","volume":"200","author":"Sakr M","unstructured":"M Sakr and J Wardrope. 2000. Casualty, accident and emergency, or emergency medicine, the evolution. Emergency Medicine Journal, 314--319.","journal-title":"J Wardrope."},{"key":"e_1_2_2_35_1","unstructured":"Glenn Shafer and Vladimir Vovk. 2008. A tutorial on conformal prediction. Journal of Machine Learning Research 371--421."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452799"},{"key":"e_1_2_2_37_1","unstructured":"Lukas Steinberger and Hannes Leeb. 2016. Leave-one-out prediction intervals in linear regression models with many variables. arXiv preprint arXiv:1602.05801."},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the VLDB Endowment. 19--28","author":"Stillger Michael","year":"2001","unstructured":"Michael Stillger, Guy M Lohman, Volker Markl, and Mokhtar Kandil. 2001. LEO-DB2's learning optimizer. In Proceedings of the VLDB Endowment. 19--28."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485459"},{"key":"e_1_2_2_41_1","volume-title":"Single-Model Uncertainties for Deep Learning. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems. 6414--6425","author":"Tagasovska Natasa","year":"2019","unstructured":"Natasa Tagasovska and David Lopez-Paz. 2019. Single-Model Uncertainties for Deep Learning. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems. 6414--6425."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/IC2E52221.2021.00030"},{"key":"e_1_2_2_43_1","volume-title":"Prediction Intervals for Learned Cardinality Estimation: An Experimental Evaluation. In 2022 IEEE 38th International Conference on Data Engineering (ICDE).","author":"Thirumuruganathan Saravanan","year":"2022","unstructured":"Saravanan Thirumuruganathan, Suraj Shetiya, Nick Koudas, and Gautam Das. 2022. Prediction Intervals for Learned Cardinality Estimation: An Experimental Evaluation. In 2022 IEEE 38th International Conference on Data Engineering (ICDE)."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850584"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183742"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452830"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489508"},{"key":"e_1_2_2_49_1","volume-title":"2013 IEEE 29th International Conference on Data Engineering (ICDE). 1081--1092","author":"Wu Wentao","year":"2013","unstructured":"Wentao Wu, Yun Chi, Shenghuo Zhu, Junichi Tatemura, Hakan Hacig\u00fcm\u00fcs, and Jeffrey F Naughton. 2013. Predicting query execution time: Are optimizer cost models really unusable?. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). 1081--1092."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882914"},{"key":"e_1_2_2_51_1","volume-title":"Advances in Neural Information Processing Systems","author":"Yang Liu","year":"2011","unstructured":"Liu Yang. 2011. Active learning with a drifting distribution. Advances in Neural Information Processing Systems, 2079--2087."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_2_53_1","volume-title":"Zongyan He, and Hao Zhang.","author":"Zhao Kangfei","year":"2021","unstructured":"Kangfei Zhao, Jeffrey Xu Yu, Zongyan He, and Hao Zhang. 2021. Uncertainty-aware Cardinality Estimation by Neural Network Gaussian Process. arXiv preprint arXiv:2107.08706."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457262"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588711","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588711","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:35Z","timestamp":1750178855000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588711"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588711"],"URL":"https:\/\/doi.org\/10.1145\/3588711","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}