{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:50:14Z","timestamp":1774986614913,"version":"3.50.1"},"reference-count":86,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Recent deployments of learned query optimizers use expensive neural networks and ad-hoc search policies. To address these issues, we introduce LimeQO, a framework for offline query optimization leveraging low-rank learning to efficiently explore alternative query plans with minimal resource usage. By modeling the workload as a partially observed, low-rank matrix, we predict unobserved query plan latencies using purely linear methods, significantly reducing computational overhead compared to neural networks. We formalize offline exploration as an active learning problem, and present simple heuristics that reduces a 3-hour workload to 1.5 hours after just 1.5 hours of exploration. Additionally, we propose a transductive Tree Convolutional Neural Network (TCNN) that, despite higher computational costs, achieves the same workload reduction with only 0.5 hours of exploration. Unlike previous approaches that place expensive neural networks directly in the query processing ''hot'' path, our approach offers a low-overhead solution and a no-regressions guarantee, all without making assumptions about the underlying DBMS.<\/jats:p>","DOI":"10.1145\/3725412","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["Low Rank Learning for Offline Query Optimization"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8015-8486","authenticated-orcid":false,"given":"Zixuan","family":"Yi","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6876-5059","authenticated-orcid":false,"given":"Yao","family":"Tian","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7527-2957","authenticated-orcid":false,"given":"Zachary G.","family":"Ives","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1279-1124","authenticated-orcid":false,"given":"Ryan","family":"Marcus","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2024. PostgreSQL database http:\/\/www.postgresql.org\/. http:\/\/www.postgresql.org\/"},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"E. Anderson Z. Bai C. Bischof S. Blackford J. Demmel J. Dongarra J. Du Croz A. Greenbaum S. Hammarling A. McKenney and D. Sorensen. 1999. LAPACK Users' Guide (third ed.). Society for Industrial and Applied Mathematics Philadelphia PA.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611544"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526045"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190662"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--12637--1_51"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/080738970"},{"key":"e_1_2_2_8_1","volume-title":"Candes and Terence Tao","author":"Emmanuel","year":"2009","unstructured":"Emmanuel J. Candes and Terence Tao. 2009. The Power of Convex Relaxation: Near-Optimal Matrix Completion. http:\/\/arxiv.org\/abs\/0903.1476 arXiv:0903.1476 [cs, math]."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009--9045--5"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.69"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587150"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598597"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132772"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2959100.2959190"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352120"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1309.6830"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","unstructured":"Damjan Gjurovski Angjela Davitkova and Sebastian Michel. 2024. Grid-AR: A Grid-based Booster for Learned Cardinality Estimation and Range Joins. https:\/\/doi.org\/10.48550\/arXiv.2410.07895 arXiv:2410.07895 [cs].","DOI":"10.48550\/arXiv.2410.07895"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/138859.138867"},{"key":"e_1_2_2_20_1","unstructured":"Huifeng Guo Ruiming Tang Yunming Ye Zhenguo Li and Xiuqiang He. 2017. DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. http:\/\/arxiv.org\/abs\/1703.04247 arXiv:1703.04247 [cs]."},{"key":"e_1_2_2_21_1","unstructured":"Trevor Hastie Rahul Mazumder Jason Lee and Reza Zadeh. 2014. Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares. arxiv:1410.2596 [stat.ME]"},{"key":"e_1_2_2_22_1","unstructured":"Xiangnan He Lizi Liao Hanwang Zhang Liqiang Nie Xia Hu and Tat-Seng Chua. 2017. Neural Collaborative Filtering. http:\/\/arxiv.org\/abs\/1708.05031 arXiv:1708.05031 [cs]."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551799"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9597"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3654755"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2401.15210"},{"key":"e_1_2_2_27_1","volume-title":"IJCAI'07 Proceedings of the 20th international joint conference on Artifical intelligence. 877-882","author":"Kapoor Ashish","year":"2007","unstructured":"Ashish Kapoor, Eric Horvitz, and Sumit Basu. 2007. Selective supervision: Guiding supervised learning with decision-theoretic active learning. In IJCAI'07 Proceedings of the 20th international joint conference on Artifical intelligence. 877-882."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639300"},{"key":"e_1_2_2_29_1","volume-title":"Adam: A Method for Stochastic Optimization. In 3rd International Conference for Learning Representations, (ICLR '15)","author":"Diederik","unstructured":"Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference for Learning Representations, (ICLR '15). San Diego, CA. https:\/\/arxiv.org\/abs\/1412.6980"},{"key":"e_1_2_2_30_1","volume-title":"Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research, (CIDR '19)","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research, (CIDR '19). http:\/\/arxiv.org\/abs\/1809.00677"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_2_2_32_1","volume-title":"Learning to Optimize Join Queries With Deep Reinforcement Learning. arXiv:1808.03196 [cs], (Aug","author":"Krishnan Sanjay","year":"2018","unstructured":"Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and Ion Stoica. 2018. Learning to Optimize Join Queries With Deep Reinforcement Learning. arXiv:1808.03196 [cs], (Aug. 2018). http:\/\/arxiv.org\/abs\/1808.03196 arXiv: 1808.03196."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/303568.303704"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3654621.3654625"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3626292.3626302"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682030"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452838"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_2_40_1","volume-title":"Deep Reinforcement Learning for Join Order Enumeration. In First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, (aiDM @ SIGMOD '18)","author":"Marcus Ryan","year":"2018","unstructured":"Ryan Marcus and Olga Papaemmanouil. 2018. Deep Reinforcement Learning for Join Order Enumeration. In First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, (aiDM @ SIGMOD '18). Houston, TX."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/3015812.3016002"},{"key":"e_1_2_2_42_1","first-page":"1049","article-title":"The Making of TPC-DS. In VLDB, (VLDB '06). VLDB Endowment, Seoul","author":"Nambiar Raghunath Othayoth","year":"2006","unstructured":"Raghunath Othayoth Nambiar and Meikel Poess. 2006. The Making of TPC-DS. In VLDB, (VLDB '06). VLDB Endowment, Seoul, Korea, 1049-1058. http:\/\/dl.acm.org\/citation.cfm?id=1182635.1164217","journal-title":"Korea"},{"key":"e_1_2_2_43_1","unstructured":"Maxim Naumov Dheevatsa Mudigere Hao-Jun Michael Shi Jianyu Huang Narayanan Sundaraman Jongsoo Park Xiaodong Wang Udit Gupta Carole-Jean Wu Alisson G. Azzolini Dmytro Dzhulgakov Andrey Mallevich Ilia Cherniavskii Yinghai Lu Raghuraman Krishnamoorthi Ansha Yu Volodymyr Kondratenko Stephanie Pereira Xianjie Chen Wenlin Chen Vijay Rao Bill Jia Liang Xiong and Misha Smelyanskiy. 2019. Deep Learning Recommendation Model for Personalization and Recommendation Systems. http:\/\/arxiv.org\/abs\/1906.00091 arXiv:1906.00091 [cs]."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457568"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583164"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262033589.003.0025"},{"key":"e_1_2_2_48_1","volume-title":"Learning State Representations for Query Optimization with Deep Reinforcement Learning. In 2nd Workshop on Data Managmeent for End-to-End Machine Learning, (DEEM '18)","author":"Ortiz Jennifer","year":"1803","unstructured":"Jennifer Ortiz, Magdalena Balazinska, Johannes Gehrke, and S. Sathiya Keerthi. 2018. Learning State Representations for Query Optimization with Deep Reinforcement Learning. In 2nd Workshop on Data Managmeent for End-to-End Machine Learning, (DEEM '18). https:\/\/arxiv.org\/abs\/1803.08604"},{"key":"e_1_2_2_49_1","unstructured":"Adam Paszke Sam Gross Soumith Chintala Gregory Chanan Edward Yang Zachary DeVito Zeming Lin Alban Desmaison Luca Antiga and Adam Lerer. 2017. Automatic differentiation in PyTorch. In Neural information processing workshops (NIPS-W '17)."},{"key":"e_1_2_2_50_1","unstructured":"PostgreSQL Developers. 2024. PostgreSQL hints https:\/\/www.postgresql.org\/docs\/current\/runtime-config-query.html. https:\/\/www.postgresql.org\/docs\/current\/runtime-config-query.html tex.key= 1."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.26599\/BDMA.2018.9020008"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636229"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472291"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.127"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783259"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3653395"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0--934613--53--8.50038--8"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00196"},{"key":"e_1_2_2_59_1","unstructured":"Burr Settles. 2009. Active learning literature survey. (2009)."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339584"},{"key":"e_1_2_2_61_1","volume-title":"Advances in Neural Information Processing Systems","author":"Srebro Nathan","year":"2004","unstructured":"Nathan Srebro, Jason Rennie, and Tommi Jaakkola. 2004. Maximum-Margin Matrix Factorization. In Advances in Neural Information Processing Systems, Vol. 17. MIT Press. https:\/\/papers.nips.cc\/paper_files\/paper\/2004\/hash\/e0688d13958a19e087e123148555e4b4-Abstract.html"},{"key":"e_1_2_2_62_1","first-page":"1","article-title":"Dropout: a simple way to prevent neural networks from overfitting","volume":"15","author":"Srivastava Nitish","year":"2014","unstructured":"Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, Vol. 15, 1 (Jan. 2014), 1929-1958.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_2_2_63_1","unstructured":"Michael Stillger Guy M. Lohman Volker Markl and Mokhtar Kandil. 2001. LEO - DB2's LEarning Optimizer. In VLDB (VLDB '01). 19-28. http:\/\/dl.acm.org\/citation.cfm?id=645927.672349"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589769"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487627"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2401.12722"},{"key":"e_1_2_2_67_1","unstructured":"Jeffrey Tao Natalie Maus Haydn Jones Yimeng Zeng Jacob R. Gardner and Ryan Marcus. 2025. Learned Offline Query Planning via Bayesian Optimization. arxiv:2502.05256 [cs.DB] https:\/\/arxiv.org\/abs\/2502.05256"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00294"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682031"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682031"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3214306"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/3641204.3641205"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611528"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639293"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3653391"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517885"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3663742.3663974"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565846"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3285029"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526052"},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682007"},{"key":"e_1_2_2_84_1","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675035"},{"key":"e_1_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583160"},{"key":"e_1_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.14778\/3641204.3641209"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:57:54Z","timestamp":1774983474000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":86,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725412"],"URL":"https:\/\/doi.org\/10.1145\/3725412","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}