{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:56:08Z","timestamp":1767855368907,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T00:00:00Z","timestamp":1703203200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T00:00:00Z","timestamp":1703203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_178894\/1"],"award-info":[{"award-number":["200021_178894\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Analytical engines rely on in-memory data caching to avoid storage accesses and provide timely responses by keeping the most frequently accessed data in memory. Purely frequency- and time-based caching decisions, however, are a proxy of the expected query execution speedup only when storage accesses are significantly slower than in-memory query processing. On the other hand, fast storage offers loading times that approach fully in-memory query response times, rendering purely frequency-based statistics incapable of capturing the impact of a caching decision on query execution. For example, caching the input of a frequent query that spends most of its time processing joins is less beneficial than caching a page for a slightly less frequent but scan-heavy query. Thus, existing caching policies waste valuable memory space to cache input data that offer little-to-no acceleration for analytics. This paper proposes HPCache, a buffer management policy that enables fast analytics on high-bandwidth storage by efficiently using the available in-memory space. HPCache caches data based on the speedup potential instead of relying on frequency-based statistics. We show that, with fast storage, the benefit of in-memory caching varies significantly across queries; therefore, we quantify the efficiency of caching decisions and formulate an optimization problem. We implement HPCache in Proteus and show that (i) estimating speedup potential improves memory space utilization, and (ii) simple runtime statistics suffice to infer speedup. We show that HPCache achieves up to a 1.75x speed-up over frequency-based caching policies by caching column proportions and automatically tuning them. Overall, HPCache enables efficient use of the in-memory space for input caching in the presence of fast storage, without requiring workload predictions.<\/jats:p>","DOI":"10.1007\/s00778-023-00828-7","type":"journal-article","created":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T18:01:24Z","timestamp":1703268084000},"page":"1775-1791","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["HPCache: memory-efficient OLAP through proportional caching revisited"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0306-3253","authenticated-orcid":false,"given":"Hamish","family":"Nicholson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0194-708X","authenticated-orcid":false,"given":"Periklis","family":"Chrysogelos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9949-3639","authenticated-orcid":false,"given":"Anastasia","family":"Ailamaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,22]]},"reference":[{"key":"828_CR1","unstructured":"Exponential smoothing. https:\/\/en.wikipedia.org\/wiki\/Exponential_smoothing"},{"issue":"1","key":"828_CR2","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1080\/23307706.2017.1397554","volume":"5","author":"A Agrawal","year":"2018","unstructured":"Agrawal, A., Verschueren, R., Diamond, S., Boyd, S.: A rewriting system for convex optimization problems. J. Control Decis. 5(1), 42\u201360 (2018)","journal-title":"J. Control Decis."},{"issue":"13","key":"828_CR3","doi-asserted-by":"publisher","first-page":"2393","DOI":"10.14778\/3358701.3358707","volume":"12","author":"M Athanassoulis","year":"2019","unstructured":"Athanassoulis, M., B\u00f8gh, K.S., Idreos, S.: Optimal column layout for hybrid workloads. Proc. VLDB Endow. 12(13), 2393\u20132407 (2019). https:\/\/doi.org\/10.14778\/3358701.3358707","journal-title":"Proc. VLDB Endow."},{"key":"828_CR4","unstructured":"Axboe, J.: Fio (2022). https:\/\/github.com\/axboe\/fio. Original-date: 2012-10-22T08:20:41Z"},{"key":"828_CR5","doi-asserted-by":"publisher","unstructured":"Bandle, M., Giceva, J., Neumann, T.: To partition, or not to partition, that is the join question in a real system. In: Li, G., Li, Z., Idreos, S., Srivastava, D. (eds.) SIGMOD \u201921: International Conference on Management of Data, Virtual Event, China, June 20\u201325, 2021, pp. 168\u2013180. ACM (2021). https:\/\/doi.org\/10.1145\/3448016.3452831","DOI":"10.1145\/3448016.3452831"},{"key":"828_CR6","doi-asserted-by":"publisher","unstructured":"Blanas, S., Li, Y., Patel, J.M.: Design and evaluation of main memory hash join algorithms for multi-core cpus. In: Sellis, T.K., Miller, R.J., Kementsietsidis, A., Velegrakis, Y. (eds.) Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011, pp. 37\u201348. ACM (2011). https:\/\/doi.org\/10.1145\/1989323.1989328","DOI":"10.1145\/1989323.1989328"},{"issue":"12","key":"828_CR7","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/1409360.1409380","volume":"51","author":"PA Boncz","year":"2008","unstructured":"Boncz, P.A., Kersten, M.L., Manegold, S.: Breaking the memory wall in MonetDB. Commun. ACM 51(12), 77\u201385 (2008). https:\/\/doi.org\/10.1145\/1409360.1409380","journal-title":"Commun. ACM"},{"key":"828_CR8","unstructured":"Boncz, P.A., Manegold, S., Kersten, M.L.: Database architecture optimized for the new bottleneck: Memory access. In: Atkinson, M.P., Orlowska, M.E., Valduriez, P., Zdonik, S.B., Brodie, M.L. (eds.) VLDB\u201999, proceedings of 25th international conference on very large data bases, september 7-10, 1999, edinburgh, scotland, UK, pp. 54\u201365. Morgan Kaufmann (1999). http:\/\/www.vldb.org\/conf\/1999\/P5.pdf. Tex.bibsource: dblp computer science bibliography, https:\/\/dblp.org tex.biburl: https:\/\/dblp.org\/rec\/conf\/vldb\/BonczMK99.bib tex.timestamp: Wed, 11 May 2022 08:53:25 +0200"},{"key":"828_CR9","unstructured":"Boncz, P.A., Zukowski, M., Nes, N.: Monetdb\/x100: Hyper-pipelining query execution. In: Second Biennial Conference on Innovative Data Systems Research, CIDR 2005, Asilomar, CA, USA, January 4-7, 2005, Online Proceedings, pp. 225\u2013237. www.cidrdb.org (2005). http:\/\/cidrdb.org\/cidr2005\/papers\/P19.pdf"},{"issue":"12","key":"828_CR10","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.14778\/2994509.2994521","volume":"9","author":"R Borovica-Gajic","year":"2016","unstructured":"Borovica-Gajic, R., Appuswamy, R., Ailamaki, A.: Cheap data analytics using cold storage devices. Proc. VLDB Endow. 9(12), 1029\u20131040 (2016). https:\/\/doi.org\/10.14778\/2994509.2994521","journal-title":"Proc. VLDB Endow."},{"issue":"2","key":"828_CR11","doi-asserted-by":"publisher","first-page":"1435","DOI":"10.14778\/1920841.1921017","volume":"3","author":"M Canim","year":"2010","unstructured":"Canim, M., Mihaila, G.A., Bhattacharjee, B., Ross, K.A., Lang, C.A.: SSD bufferpool extensions for database systems. Proc. VLDB Endow. 3(2), 1435\u20131446 (2010). https:\/\/doi.org\/10.14778\/1920841.1921017","journal-title":"Proc. VLDB Endow."},{"issue":"3","key":"828_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF01840450","volume":"1","author":"H Chou","year":"1986","unstructured":"Chou, H., DeWitt, D.J.: An evaluation of buffer management strategies for relational database systems. Algorithmica 1(3), 311\u2013336 (1986). https:\/\/doi.org\/10.1007\/BF01840450","journal-title":"Algorithmica"},{"issue":"5","key":"828_CR13","doi-asserted-by":"publisher","first-page":"544","DOI":"10.14778\/3303753.3303760","volume":"12","author":"P Chrysogelos","year":"2019","unstructured":"Chrysogelos, P., Karpathiotakis, M., Appuswamy, R., Ailamaki, A.: HetExchange: encapsulating heterogeneous CPU-GPU parallelism in JIT compiled engines. Proc. VLDB Endow. 12(5), 544\u2013556 (2019). https:\/\/doi.org\/10.14778\/3303753.3303760","journal-title":"Proc. VLDB Endow."},{"key":"828_CR14","unstructured":"Crotty, A., Leis, V., Pavlo, A.: Are You Sure You Want to Use MMAP in Your Database Management System? In: {CIDR} 2022, Conference on Innovative Data Systems Research, p.\u00a07 (2022)"},{"key":"828_CR15","unstructured":"Devices, A.M.: Amd epyc$$^{\\text{TM}}$$ 7003 series data sheet (2021). https:\/\/www.amd.com\/system\/files\/documents\/amd-epyc-7003-series-datasheet.pdf"},{"issue":"83","key":"828_CR16","first-page":"1","volume":"17","author":"S Diamond","year":"2016","unstructured":"Diamond, S., Boyd, S.: CVXPY: a Python-embedded modeling language for convex optimization. J. Mach. Learn. Res. 17(83), 1\u20135 (2016)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"828_CR17","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s00778-020-00648-z","volume":"30","author":"J Do","year":"2021","unstructured":"Do, J., Picoli, I.L., Lomet, D.B., Bonnet, P.: Better database cost\/performance via batched I\/O on programmable SSD. VLDB J. 30(3), 403\u2013424 (2021). https:\/\/doi.org\/10.1007\/s00778-020-00648-z","journal-title":"VLDB J."},{"issue":"3","key":"828_CR18","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/MM.2012.17","volume":"32","author":"H Esmaeilzadeh","year":"2012","unstructured":"Esmaeilzadeh, H., Blem, E.R., Amant, R.S., Sankaralingam, K., Burger, D.: Dark silicon and the end of multicore scaling. IEEE Micro 32(3), 122\u2013134 (2012). https:\/\/doi.org\/10.1109\/MM.2012.17","journal-title":"IEEE Micro"},{"issue":"1","key":"828_CR19","doi-asserted-by":"publisher","first-page":"37","DOI":"10.14778\/2735461.2735465","volume":"8","author":"G Graefe","year":"2014","unstructured":"Graefe, G., Volos, H., Kimura, H., Kuno, H., Tucek, J., Lillibridge, M., Veitch, A.: In-memory performance for big data. Proc. VLDB Endow. 8(1), 37\u201348 (2014). https:\/\/doi.org\/10.14778\/2735461.2735465","journal-title":"Proc. VLDB Endow."},{"key":"828_CR20","first-page":"40","volume":"35","author":"S Idreos","year":"2012","unstructured":"Idreos, S., Groffen, F., Nes, N., Manegold, S., Mullender, S., Kersten, M.: MonetDB: two decades of research in column-oriented database architectures. IEEE Data Eng. Bull. 35, 40\u201345 (2012)","journal-title":"IEEE Data Eng. Bull."},{"key":"828_CR21","doi-asserted-by":"publisher","unstructured":"Johnson, R., Pandis, I., Hardavellas, N., Ailamaki, A., Falsafi, B.: Shore-MT: a scalable storage manager for the multicore era. In: Proceedings of the 12th International Conference on Extending Database Technology Advances in Database Technology - EDBT \u201909, p.\u00a024. ACM Press, Saint Petersburg, Russia (2009). https:\/\/doi.org\/10.1145\/1516360.1516365. http:\/\/portal.acm.org\/citation.cfm?doid=1516360.1516365","DOI":"10.1145\/1516360.1516365"},{"key":"828_CR22","unstructured":"Johnson, T., Shasha, D.E.: 2q: A low overhead high performance buffer management replacement algorithm. In: Bocca, J.B., Jarke, M., Zaniolo, C. (eds.) VLDB\u201994, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile, pp. 439\u2013450. Morgan Kaufmann (1994). http:\/\/www.vldb.org\/conf\/1994\/P439.PDF"},{"issue":"12","key":"828_CR23","doi-asserted-by":"publisher","first-page":"972","DOI":"10.14778\/2994509.2994516","volume":"9","author":"M Karpathiotakis","year":"2016","unstructured":"Karpathiotakis, M., Alagiannis, I., Ailamaki, A.: Fast queries over heterogeneous data through engine customization. Proc. VLDB Endow. 9(12), 972\u2013983 (2016). https:\/\/doi.org\/10.14778\/2994509.2994516","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"828_CR24","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/3588687","volume":"1","author":"V Leis","year":"2023","unstructured":"Leis, V., Alhomssi, A., Ziegler, T., Loeck, Y., Dietrich, C.: Virtual-memory assisted buffer management. Proc. ACM Manag. Data 1(1), 7:1-7:25 (2023). https:\/\/doi.org\/10.1145\/3588687","journal-title":"Proc. ACM Manag. Data"},{"key":"828_CR25","doi-asserted-by":"publisher","unstructured":"Leis, V., Haubenschild, M., Kemper, A., Neumann, T.: LeanStore: In-Memory Data Management beyond Main Memory. In: 2018 IEEE 34th International Conference on Data Engineering (ICDE), pp. 185\u2013196. IEEE, Paris (2018). https:\/\/doi.org\/10.1109\/ICDE.2018.00026","DOI":"10.1109\/ICDE.2018.00026"},{"key":"828_CR26","unstructured":"McCalpin, J.D.: Stream: Sustainable memory bandwidth in high performance computers. Tech. rep., University of Virginia, Charlottesville, Virginia (1991-2007). http:\/\/www.cs.virginia.edu\/stream\/. A continually updated technical report. http:\/\/www.cs.virginia.edu\/stream\/"},{"key":"828_CR27","unstructured":"McCalpin, J.D.: Memory bandwidth and machine balance in current high performance computers. IEEE Computer Society Technical Committee on Computer Architecture (TCCA) Newsletter 19\u201325 (1995)"},{"issue":"9","key":"828_CR28","doi-asserted-by":"publisher","first-page":"539","DOI":"10.14778\/2002938.2002940","volume":"4","author":"T Neumann","year":"2011","unstructured":"Neumann, T.: Efficiently compiling efficient query plans for modern hardware. Proc. VLDB Endow. 4(9), 539\u2013550 (2011). https:\/\/doi.org\/10.14778\/2002938.2002940","journal-title":"Proc. VLDB Endow."},{"key":"828_CR29","unstructured":"Neumann, T., Freitag, M.J.: Umbra: A disk-based system with in-memory performance. In: 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12\u201315, 2020, Online Proceedings. www.cidrdb.org (2020). http:\/\/cidrdb.org\/cidr2020\/papers\/p29-neumann-cidr20.pdf"},{"key":"828_CR30","doi-asserted-by":"publisher","unstructured":"Nicholson, H., Chrysogelos, P., Ailamaki, A.: HPCache: Memory-Efficient OLAP Through Proportional Caching. In: DaMoN\u201922, p.\u00a09. Association for Computing Machinery, Philadelphia, PA, USA (2022). https:\/\/doi.org\/10.1145\/3533737.3535100","DOI":"10.1145\/3533737.3535100"},{"key":"828_CR31","unstructured":"Nyberg, C.: Disk scheduling and cache replacement for a database machine. Master\u2019s thesis, UC Berkeley (1984)"},{"key":"828_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-642-10424-4_17","volume-title":"Performance Evaluation and Benchmarking","author":"P O\u2019Neil","year":"2009","unstructured":"O\u2019Neil, P., O\u2019Neil, E., Chen, X., Revilak, S.: The star schema benchmark and augmented fact table indexing. In: Nambiar, R., Poess, M. (eds.) Performance Evaluation and Benchmarking. Lecture Notes in Computer Science, pp. 237\u2013252. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10424-4_17"},{"key":"828_CR33","doi-asserted-by":"crossref","unstructured":"Raza, A., Chrysogelos, P., Anadiotis, A.C., Ailamaki, A.: Adaptive HTAP through Elastic Resource Scheduling. arXiv:2004.05437 [cs, eess] (2020). http:\/\/arxiv.org\/abs\/2004.05437. arXiv:2004.05437","DOI":"10.1145\/3318464.3389783"},{"key":"828_CR34","unstructured":"Reiter, A.: A study of buffer management policies for data management systems. Tech. rep., WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER (1976)"},{"key":"828_CR35","unstructured":"Sacco, G.M., Schkolnick, M.: A mechanism for managing the buffer pool in a relational database system using the hot set model. In: Eigth International Conference on Very Large Data Bases, September 8-10, 1982, Mexico City, Mexico, Proceedings, pp. 257\u2013262. Morgan Kaufmann (1982). http:\/\/www.vldb.org\/conf\/1982\/P257.PDF"},{"key":"828_CR36","unstructured":"Samuels, A.: The consequences of infinite storage bandwidth (2016). https:\/\/events.static.linuxfound.org\/sites\/events\/files\/slides\/Keynote_Allen%20Samuels_Final.pdf. Vault Linux Storage & Filesystems Conference"},{"key":"828_CR37","doi-asserted-by":"publisher","unstructured":"Sirin, U., Ailamaki, A.: Micro-architectural analysis of OLAP: limitations and opportunities. Proc. VLDB Endow. 13(6), 840\u2013853 (2020). https:\/\/doi.org\/10.14778\/3380750.3380755","DOI":"10.14778\/3380750.3380755"},{"key":"828_CR38","doi-asserted-by":"publisher","unstructured":"Stonebraker, M., Woodfill, J., Ranstrom, J., Murphy, M.C., Meyer, M., Allman, E.: Performance enhancements to a relational database system. ACM Trans. Database Syst. 8(2), 167\u2013185 (1983). https:\/\/doi.org\/10.1145\/319983.319984","DOI":"10.1145\/319983.319984"},{"issue":"12","key":"828_CR39","doi-asserted-by":"publisher","first-page":"2662","DOI":"10.14778\/3407790.3407852","volume":"13","author":"L Vogel","year":"2020","unstructured":"Vogel, L., Leis, V., van Renen, A., Neumann, T., Imamura, S., Kemper, A.: Mosaic: a budget-conscious storage engine for relational database systems. Proc. VLDB Endow. 13(12), 2662\u20132675 (2020). https:\/\/doi.org\/10.14778\/3407790.3407852","journal-title":"Proc. VLDB Endow."},{"key":"828_CR40","doi-asserted-by":"publisher","unstructured":"Yu, Y., Wang, W., Zhang, J., Letaief, K.B.: LRC: dependency-aware cache management for data analytics clusters. In: 2017 IEEE Conference on Computer Communications, INFOCOM 2017, Atlanta, GA, USA, May 1\u20134, 2017, pp. 1\u20139. IEEE (2017). https:\/\/doi.org\/10.1109\/INFOCOM.2017.8057007","DOI":"10.1109\/INFOCOM.2017.8057007"},{"issue":"7","key":"828_CR41","doi-asserted-by":"publisher","first-page":"1920","DOI":"10.1109\/TKDE.2015.2427795","volume":"27","author":"H Zhang","year":"2015","unstructured":"Zhang, H., Chen, G., Ooi, B.C., Tan, K.L., Zhang, M.: In-memory big data management and processing: a survey. IEEE Trans. Knowl. Data Eng. 27(7), 1920\u20131948 (2015). https:\/\/doi.org\/10.1109\/TKDE.2015.2427795","journal-title":"IEEE Trans. Knowl. Data Eng."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00828-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-023-00828-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00828-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T10:06:03Z","timestamp":1729505163000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-023-00828-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,22]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["828"],"URL":"https:\/\/doi.org\/10.1007\/s00778-023-00828-7","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,22]]},"assertion":[{"value":"15 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}