{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T16:04:38Z","timestamp":1787241878478,"version":"build-2736575974"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["III-1910108"],"award-info":[{"award-number":["III-1910108"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Learned database systems address several weaknesses of traditional cost estimation techniques in query optimization: they learn a model of a database instance, e.g., as queries are executed. However, when the database instance has skew and correlation, it is nontrivial to create an effective training set that anticipates workload shifts, where query structure changes and\/or different regions of the data contribute to query answers. Our predictive model may perform poorly with these out-of-distribution inputs. In this paper, we study how the notion of a replay buffer can be managed through online algorithms to build a concise yet representative model of the workload distribution --- allowing for rapid adaptation and effective prediction of cardinalities and costs. We experimentally validate our methods over several data domains.<\/jats:p>","DOI":"10.1145\/3639293","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-27","source":"Crossref","is-referenced-by-count":14,"title":["Modeling Shifting Workloads for Learned Database Systems"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-4765-8733","authenticated-orcid":false,"given":"Peizhi","family":"Wu","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304198"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_3_1","volume-title":"Understanding double descent requires a fine-grained bias-variance decomposition. Advances in neural information processing systems","author":"Adlam Ben","year":"2020","unstructured":"Ben Adlam and Jeffrey Pennington. 2020. Understanding double descent requires a fine-grained bias-variance decomposition. Advances in neural information processing systems, Vol. 33 (2020), 11022--11032."},{"key":"e_1_2_1_4_1","volume-title":"Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems","author":"Allen-Zhu Zeyuan","year":"2019","unstructured":"Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. 2019. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, Vol. 32 (2019)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.17"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363736"},{"key":"e_1_2_1_7_1","volume-title":"Query-driven learning for predictive analytics of data subspace cardinality. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Anagnostopoulos Christos","year":"2017","unstructured":"Christos Anagnostopoulos and Peter Triantafillou. 2017. Query-driven learning for predictive analytics of data subspace cardinality. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 11, 4 (2017), 1--46."},{"key":"e_1_2_1_8_1","volume-title":"Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems. The annals of statistics","author":"Antoniak Charles E","year":"1974","unstructured":"Charles E Antoniak. 1974. Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems. The annals of statistics (1974), 1152--1174."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_10_1","unstructured":"Allan Borodin and Ran El-Yaniv. 2005. Online computation and competitive analysis. cambridge university press."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133039"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564722"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Nicolas Bruno Surajit Chaudhuri and Luis Gravano. 2001. STHoles: a multidimensional workload-aware histogram. In SIGMOD. 211--222.","DOI":"10.1145\/375663.375686"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44503-X_20"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1997.612321"},{"key":"e_1_2_1_16_1","volume-title":"The hardness of k-means clustering. Department of Computer Science and Engineering","author":"Dasgupta Sanjoy","unstructured":"Sanjoy Dasgupta. 2008. The hardness of k-means clustering. Department of Computer Science and Engineering, University of California."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1979.4766909"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1331939.1331940"},{"key":"e_1_2_1_19_1","volume-title":"The 38th Conference on Uncertainty in Artificial Intelligence.","author":"Dinari Or","year":"2022","unstructured":"Or Dinari and Oren Freifeld. 2022. Revisiting DP-Means: Fast Scalable Algorithms via Parallelism and Delayed Cluster Creation. In The 38th Conference on Uncertainty in Artificial Intelligence."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00201"},{"key":"e_1_2_1_22_1","volume-title":"Advances in Neural Information Processing Systems","volume":"31","author":"Du Simon S","year":"2018","unstructured":"Simon S Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Russ R Salakhutdinov, and Aarti Singh. 2018. How many samples are needed to estimate a convolutional neural network? Advances in Neural Information Processing Systems, Vol. 31 (2018)."},{"key":"e_1_2_1_23_1","volume-title":"International Conference on Machine Learning. PMLR, 2280--2290","author":"Ascoli St\u00e9phane","year":"2020","unstructured":"St\u00e9phane d'Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. 2020. Double trouble in double descent: Bias and variance (s) in the lazy regime. In International Conference on Machine Learning. PMLR, 2280--2290."},{"key":"e_1_2_1_24_1","volume-title":"Rethinking importance weighting for deep learning under distribution shift. Advances in neural information processing systems","author":"Fang Tongtong","year":"2020","unstructured":"Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. 2020. Rethinking importance weighting for deep learning under distribution shift. Advances in neural information processing systems, Vol. 33 (2020), 11996--12007."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118787.3119257"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1959045.1959065"},{"key":"e_1_2_1_27_1","volume-title":"On the sample complexity of learning Bayesian networks. arXiv preprint arXiv:1302.3579","author":"Friedman Nir","year":"2013","unstructured":"Nir Friedman and Zohar Yakhini. 2013. On the sample complexity of learning Bayesian networks. arXiv preprint arXiv:1302.3579 (2013)."},{"key":"e_1_2_1_28_1","volume-title":"Conference On Learning Theory. PMLR, 297--299","author":"Golowich Noah","year":"2018","unstructured":"Noah Golowich, Alexander Rakhlin, and Ohad Shamir. 2018. Size-independent sample complexity of neural networks. In Conference On Learning Theory. PMLR, 297--299."},{"key":"e_1_2_1_29_1","volume-title":"NIPS","volume":"27","author":"Goodfellow Ian","year":"2014","unstructured":"Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. NIPS, Vol. 27 (2014)."},{"key":"e_1_2_1_30_1","volume-title":"DeepDB: Learn from Data, not from Queries! VLDB","author":"Hilprecht Benjamin","unstructured":"Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2020. DeepDB: Learn from Data, not from Queries! VLDB, Vol. 13, 7, 992--1005."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1316874.1316892"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115835"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00132"},{"key":"e_1_2_1_34_1","series-title":"SIAM journal on applied mathematics","volume-title":"An algorithmic approach to network location problems. I: The p-centers","author":"Kariv Oded","year":"1979","unstructured":"Oded Kariv and S Louis Hakimi. 1979. An algorithmic approach to network location problems. I: The p-centers. SIAM journal on applied mathematics, Vol. 37, 3 (1979), 513--538."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11651"},{"key":"e_1_2_1_36_1","volume-title":"Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned cardinality estimation: An in-depth study. In Proceedings of the 2022 International Conference on Management of Data. 1214--1227","author":"Kim Kyoungmin","unstructured":"Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned cardinality estimation: An in-depth study. In Proceedings of the 2022 International Conference on Management of Data. 1214--1227."},{"key":"e_1_2_1_37_1","unstructured":"Andreas Kipf Thomas Kipf Bernhard Radke Viktor Leis Peter Boncz and Alfons Kemper. 2019. Learned cardinalities: Estimating correlated joins with deep learning. In CIDR."},{"key":"e_1_2_1_38_1","volume-title":"International Conference on Machine Learning. PMLR, 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. PMLR, 5637--5664."},{"key":"e_1_2_1_39_1","first-page":"83","article-title":"Sulla determinazione empirica di una lgge di distribuzione","volume":"4","author":"Kolmogorov Andrey","year":"1933","unstructured":"Andrey Kolmogorov. 1933. Sulla determinazione empirica di una lgge di distribuzione. Inst. Ital. Attuari, Giorn., Vol. 4 (1933), 83--91.","journal-title":"Inst. Ital. Attuari, Giorn."},{"key":"e_1_2_1_40_1","volume-title":"Revisiting k-means: New algorithms via Bayesian nonparametrics. arXiv preprint arXiv:1111.0352","author":"Kulis Brian","year":"2011","unstructured":"Brian Kulis and Michael I Jordan. 2011. Revisiting k-means: New algorithms via Bayesian nonparametrics. arXiv preprint arXiv:1111.0352 (2011)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588713"},{"key":"e_1_2_1_42_1","volume-title":"Testing statistical hypotheses","author":"Lehmann Erich Leo","unstructured":"Erich Leo Lehmann and EL Lehmann. 1986. Testing statistical hypotheses. Vol. 2. Springer."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526179"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352129"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50040-9"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389768"},{"key":"e_1_2_1_48_1","volume-title":"Proc. 5th Berkeley Symposium on Math., Stat., and Prob. 281","author":"MacQueen J","year":"1965","unstructured":"J MacQueen. 1965. Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symposium on Math., Stat., and Prob. 281."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542703"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_51_1","volume-title":"Plan-structured deep neural network models for query performance prediction. PVLDB","author":"Marcus Ryan","year":"2019","unstructured":"Ryan Marcus and Olga Papaemmanouil. 2019. Plan-structured deep neural network models for query performance prediction. PVLDB (2019)."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.421.0098"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959917"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583164"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46227-1_5"},{"key":"e_1_2_1_57_1","volume-title":"Bayesian Nonparametric Models. Encyclopedia of machine learning","author":"Orbanz Peter","year":"2010","unstructured":"Peter Orbanz and Yee Whye Teh. 2010. Bayesian Nonparametric Models. Encyclopedia of machine learning, Vol. 1 (2010)."},{"key":"e_1_2_1_58_1","volume-title":"A simple and fast algorithm for K-medoids clustering. Expert systems with applications","author":"Park Hae-Sang","year":"2009","unstructured":"Hae-Sang Park and Chi-Hyuck Jun. 2009. A simple and fast algorithm for K-medoids clustering. Expert systems with applications, Vol. 36, 2 (2009), 3336--3341."},{"key":"e_1_2_1_59_1","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Rabanser Stephan","year":"2019","unstructured":"Stephan Rabanser, Stephan G\u00fcnnemann, and Zachary Lipton. 2019. Failing loudly: An empirical study of methods for detecting dataset shift. Advances in Neural Information Processing Systems, Vol. 32 (2019)."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589677"},{"key":"e_1_2_1_61_1","volume-title":"Fast and accurate k-means for large datasets. Advances in neural information processing systems","author":"Shindler Michael","year":"2011","unstructured":"Michael Shindler, Alex Wong, and Adam Meyerson. 2011. Fast and accurate k-means for large datasets. Advances in neural information processing systems, Vol. 24 (2011)."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380584"},{"key":"e_1_2_1_63_1","first-page":"3","article-title":"On the estimation of the discrepancy between empirical curves of distribution for two independent samples","volume":"2","author":"Smirnov Nikolai V","year":"1939","unstructured":"Nikolai V Smirnov. 1939. On the estimation of the discrepancy between empirical curves of distribution for two independent samples. Bull. Math. Univ. Moscou, Vol. 2, 2 (1939), 3--14.","journal-title":"Bull. Math. Univ. Moscou"},{"key":"e_1_2_1_64_1","first-page":"307","article-title":"An end-to-end learning-based cost estimator","volume":"13","author":"Sun Ji","year":"2019","unstructured":"Ji Sun and Guoliang Li. 2019. An end-to-end learning-based cost estimator. VLDB, Vol. 13, 3 (2019), 307--319.","journal-title":"VLDB"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.11.004"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl406"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687761"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064029"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_70_1","first-page":"210","article-title":"Towards a learning optimizer for shared clouds","volume":"12","author":"Wu Chenggang","year":"2018","unstructured":"Chenggang Wu, Alekh Jindal, Saeed Amizadeh, Hiren Patel, Wangchao Le, Shi Qiao, and Sriram Rao. 2018. Towards a learning optimizer for shared clouds. VLDB, Vol. 12, 3 (2018), 210--222.","journal-title":"VLDB"},{"key":"e_1_2_1_71_1","volume-title":"On the convergence properties of the EM algorithm. The Annals of statistics","author":"Jeff Wu CF","year":"1983","unstructured":"CF Jeff Wu. 1983. On the convergence properties of the EM algorithm. The Annals of statistics (1983), 95--103."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452830"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526168"},{"key":"e_1_2_1_74_1","volume-title":"NeuroCard: One Cardinality Estimator for All Tables. PVLDB","author":"Yang Zongheng","year":"2021","unstructured":"Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2021. NeuroCard: One Cardinality Estimator for All Tables. PVLDB (2021)."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300085"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457546"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397238"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639293","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639293","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:17:42Z","timestamp":1755789462000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639293"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":77,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639293"],"URL":"https:\/\/doi.org\/10.1145\/3639293","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}