{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:56:15Z","timestamp":1775638575042,"version":"3.50.1"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"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,11,13]]},"abstract":"<jats:p>The end-to-end lookup latency of a hierarchical index---such as a B-tree or a learned index---is determined by its structure such as the number of layers, the kinds of branching functions appearing in each layer, the amount of data we must fetch from layers, etc. Our primary observation is that by optimizing those structural parameters (or designs) specifically to a target system's I\/O characteristics (e.g., latency, bandwidth), we can offer a faster lookup compared to the ones that are not optimized. Can we develop a systematic method for finding those optimal design parameters? Ideally, the method must have the potential to generate almost any existing index or a novel combination of them for the fastest possible lookup.<\/jats:p>\n          <jats:p>In this work, we present new data and an I\/O-aware index builder (called AirIndex) that can find high-speed hierarchical index designs in a principled way. Specifically, AirIndex minimizes an objective function expressing the end-to-end latency in terms of various designs---the number of layers, types of layers, and more---for given data and a storage profile, using a graph-based optimization method purpose-built to address the computational challenges rising from the inter-dependencies among index layers and the exponentially many candidate parameters in a large search space. Our empirical studies confirm that AirIndex can find optimal index designs, build optimal indexes within the times comparable to existing methods, and deliver up to 4.1x faster lookup than a lightweight B-tree library (LMDB), 3.3x--46.3x faster than state-of-the-art learned indexes (RMI\/CDFShop, PGM-index, ALEX\/APEX, PLEX), and 2.0 faster than Data Calculator's suggestion on various dataset and storage settings.<\/jats:p>","DOI":"10.1145\/3617308","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T22:28:39Z","timestamp":1699914519000},"page":"1-26","source":"Crossref","is-referenced-by-count":7,"title":["AirIndex: Versatile Index Tuning Through Data and Storage"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2881-8501","authenticated-orcid":false,"given":"Supawit","family":"Chockchowwat","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-1460-1093","authenticated-orcid":false,"given":"Wenjie","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3786-6214","authenticated-orcid":false,"given":"Yongjoo","family":"Park","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n.d.]. https:\/\/github.com\/illinoisdata\/airindex-public."},{"key":"e_1_2_2_2_1","unstructured":"[n.d.]. https:\/\/github.com\/illinoisdata\/lmdb."},{"key":"e_1_2_2_3_1","unstructured":"[n.d.]. https:\/\/github.com\/illinoisdata\/RMI."},{"key":"e_1_2_2_4_1","unstructured":"[n.d.]. https:\/\/github.com\/illinoisdata\/PGM-index."},{"key":"e_1_2_2_5_1","unstructured":"[n.d.]. https:\/\/github.com\/illinoisdata\/ALEX_ext."},{"key":"e_1_2_2_6_1","unstructured":"[n.d.]. https:\/\/github.com\/illinoisdata\/airindex-public\/tree\/main\/src\/bin\/data_calculator.rs."},{"key":"e_1_2_2_7_1","volume-title":"A high-performance distributed shared-log for Ceph. https:\/\/github.com\/cruzdb\/zlog. [Online","year":"2022","unstructured":"[n.d.]. A high-performance distributed shared-log for Ceph. https:\/\/github.com\/cruzdb\/zlog. [Online; accessed December-27--2022]."},{"key":"e_1_2_2_8_1","volume-title":"https:\/\/www.mysql.com\/. [Online","author":"SQL.","year":"2022","unstructured":"[n.d.]. MySQL. https:\/\/www.mysql.com\/. [Online; accessed December-27--2022]."},{"key":"e_1_2_2_9_1","volume-title":"Lyric Doshi, Tim Kraska, Xiaozhou Li, Andy Ly, and Christopher Olston.","author":"Abu-Libdeh Hussam","year":"2020","unstructured":"Hussam Abu-Libdeh, Deniz Altinb\u00fcken, Alex Beutel, Ed H. Chi, Lyric Doshi, Tim Kraska, Xiaozhou Li, Andy Ly, and Christopher Olston. 2020. Learned Indexes for a Google-scale Disk-based Database. CoRR abs\/2012.12501 (2020)."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90072-3"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318163"},{"key":"e_1_2_2_12_1","volume-title":"https:\/\/azure.microsoft.com. [Online","author":"Azure Microsoft","year":"2022","unstructured":"Microsoft Azure. [n.d.]. Azure. https:\/\/azure.microsoft.com. [Online; accessed Jul-17--2022]."},{"key":"e_1_2_2_13_1","volume-title":"Azure Blob Storage. https:\/\/azure.microsoft.com\/en-us\/services\/storage\/blobs\/. [Online","author":"Azure Microsoft","year":"2022","unstructured":"Microsoft Azure. [n.d.]. Azure Blob Storage. https:\/\/azure.microsoft.com\/en-us\/services\/storage\/blobs\/. [Online; accessed Jul-17--2022]."},{"key":"e_1_2_2_14_1","volume-title":"Azure managed disk types. https:\/\/docs.microsoft.com\/en-us\/azure\/virtual-machines\/disks-types. [Online","author":"Azure Microsoft","year":"2022","unstructured":"Microsoft Azure. [n.d.]. Azure managed disk types. https:\/\/docs.microsoft.com\/en-us\/azure\/virtual-machines\/disks-types. [Online; accessed Jul-17--2022]."},{"key":"e_1_2_2_15_1","volume-title":"Network File System (NFS) 3.0 protocol support for Azure Blob Storage. https:\/\/docs.microsoft.com\/en-us\/azure\/storage\/blobs\/network-file-system-protocol-support. [Online","author":"Azure Microsoft","year":"2022","unstructured":"Microsoft Azure. [n.d.]. Network File System (NFS) 3.0 protocol support for Azure Blob Storage. https:\/\/docs.microsoft.com\/en-us\/azure\/storage\/blobs\/network-file-system-protocol-support. [Online; accessed Jul-17--2022]."},{"key":"e_1_2_2_16_1","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Balakrishnan Mahesh","year":"2020","unstructured":"Mahesh Balakrishnan, Jason Flinn, Chen Shen, Mihir Dharamshi, Ahmed Jafri, Xiao Shi, Santosh Ghosh, Hazem Hassan, Aaryaman Sagar, Rhed Shi, et al . 2020. Virtual consensus in delos. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 617--632."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892128"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.2174\/1874110x01408010302"},{"key":"e_1_2_2_20_1","volume-title":"Bigtable: A Distributed Storage System for Structured Data (Awarded Best Paper!)","author":"Chang Fay","year":"2006","unstructured":"Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Michael Burrows, Tushar Chandra, Andrew Fikes, and Robert Gruber. 2006. Bigtable: A Distributed Storage System for Structured Data (Awarded Best Paper!). In OSDI. USENIX Association, 205--218."},{"key":"e_1_2_2_21_1","volume-title":"Narasayya","author":"Chaudhuri Surajit","year":"1998","unstructured":"Surajit Chaudhuri and Vivek R. Narasayya. 1998. AutoAdmin 'What-if' Index Analysis Utility. In SIGMOD Conference. ACM Press, 367--378."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW53142.2021.00019"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375688"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564710"},{"key":"e_1_2_2_25_1","volume-title":"Issue 2","author":"Comer Douglas","year":"1979","unstructured":"Douglas Comer. 1979. UBIQUITOUS B-TREE. Comput Surv 11 (1979). Issue 2."},{"key":"e_1_2_2_26_1","volume-title":"Arpaci-Dusseau","author":"Dai Yifan","year":"2020","unstructured":"Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2020. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. In OSDI. USENIX Association, 155--171."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2018.18"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978668"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3876"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_2_31_1","volume-title":"ALEX: An Updatable Adaptive Learned Index. In SIGMOD Conference. ACM, 969--984","author":"Ding Jialin","year":"2020","unstructured":"Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David B. Lomet, and Tim Kraska. 2020. ALEX: An Updatable Adaptive Learned Index. In SIGMOD Conference. ACM, 969--984."},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Hal Daum\u00e9 III and Aarti Singh (Eds.)","volume":"119","author":"Ferragina Paolo","year":"2020","unstructured":"Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. 2020. Why Are Learned Indexes So Effective?. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Hal Daum\u00e9 III and Aarti Singh (Eds.), Vol. 119. PMLR, 3123--3132. https:\/\/proceedings.mlr.press\/v119\/ferragina20a.html"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_2_34_1","volume-title":"Navathe","author":"Frank Martin R.","year":"1992","unstructured":"Martin R. Frank, Edward Omiecinski, and Shamkant B. Navathe. 1992. Adaptive and Automated Index Selection in RDBMS. In EDBT (Lecture Notes in Computer Science), Vol. 580. Springer, 277--292."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914847"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/271074.271094"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11771-018--3927-0"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3199671"},{"key":"e_1_2_2_39_1","volume-title":"The Internals of the Data Calculator. CoRR abs\/1808.02066","author":"Idreos Stratos","year":"2018","unstructured":"Stratos Idreos, Kostas Zoumpatianos, Brian Hentschel, Michael S. Kester, and Demi Guo. 2018. The Internals of the Data Calculator. CoRR abs\/1808.02066 (2018)."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213932"},{"key":"e_1_2_2_41_1","volume-title":"Learned cardinalities: Estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677","author":"Kipf Andreas","year":"2018","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 (2018)."},{"key":"e_1_2_2_42_1","volume-title":"SOSD: A Benchmark for Learned Indexes. NeurIPS Workshop on Machine Learning for Systems","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2019. SOSD: A Benchmark for Learned Indexes. NeurIPS Workshop on Machine Learning for Systems (2019)."},{"key":"e_1_2_2_43_1","first-page":"1","article-title":"RadixSpline: a single-pass learned index. In aiDM@SIGMOD","volume":"5","author":"Kipf Andreas","year":"2020","unstructured":"Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2020. RadixSpline: a single-pass learned index. In aiDM@SIGMOD. ACM, 5:1--5:5.","journal-title":"ACM"},{"key":"e_1_2_2_44_1","volume-title":"Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan.","author":"Kraska Tim","year":"2019","unstructured":"Tim Kraska, Mohammad Alizadeh, Alex Beutel, Ed H. Chi, Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan. 2019. SageDB: A Learned Database System. In CIDR. www.cidrdb.org."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_46_1","volume-title":"LISA: A Learned Index Structure for Spatial Data. In SIGMOD Conference. ACM, 2119--2133","author":"Li Pengfei","year":"2020","unstructured":"Pengfei Li, Hua Lu, Qian Zheng, Long Yang, and Gang Pan. 2020. LISA: A Learned Index Structure for Spatial Data. In SIGMOD Conference. ACM, 2119--2133."},{"key":"e_1_2_2_47_1","unstructured":"LMDB. [n.d.]. Lightning Memory-Mapped Database Manager. http:\/\/www.lmdb.tech\/doc\/ Online; accessed Jul-17--2022."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/290593.290598"},{"key":"e_1_2_2_49_1","volume-title":"Umar Farooq Minhas, and Tianzheng Wang","author":"Lu Baotong","year":"2021","unstructured":"Baotong Lu, Jialin Ding, Eric Lo, Umar Farooq Minhas, and Tianzheng Wang. 2021. APEX: A High-Performance Learned Index on Persistent Memory. arXiv preprint arXiv:2105.00683 (2021)."},{"key":"e_1_2_2_50_1","volume-title":"ACM Annual Conference. ACM, 349--356","author":"Vincent","unstructured":"Vincent Y. Lum and Huei Ling. 1971. An optimization problem on the selection of secondary keys. In ACM Annual Conference. ACM, 349--356."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_2_52_1","volume-title":"CDFShop: Exploring and Optimizing Learned Index Structures. In SIGMOD Conference. ACM, 2789--2792","author":"Marcus Ryan","year":"2020","unstructured":"Ryan Marcus, Emily Zhang, and Tim Kraska. 2020. CDFShop: Exploring and Optimizing Learned Index Structures. In SIGMOD Conference. ACM, 2789--2792."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_2_54_1","volume-title":"Postcard: A no_std serde compatible message library for Rust. https:\/\/github.com\/jamesmunns\/postcard. [Online","year":"2022","unstructured":"Postcard. [n.d.]. Postcard: A no_std serde compatible message library for Rust. https:\/\/github.com\/jamesmunns\/postcard. [Online; accessed July-17--2022]."},{"key":"e_1_2_2_55_1","volume-title":"PostgreSQL: The World's Most Advanced Open Source Relational Database. https:\/\/www.postgresql.org. [Online","author":"SQL.","year":"2022","unstructured":"PostgreSQL. [n.d.]. PostgreSQL: The World's Most Advanced Open Source Relational Database. https:\/\/www.postgresql.org. [Online; accessed July-17--2022]."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501620.2501623"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(75)90003-4"},{"key":"e_1_2_2_59_1","volume-title":"https:\/\/serde.rs. [Online","year":"2022","unstructured":"Serde. [n.d.]. Serde. https:\/\/serde.rs. [Online; accessed July-17--2022]."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","unstructured":"Stefan Sprenger Steffen Zeuch and Ulf Leser. 2017. Cache-sensitive skip list: Efficient range queries on modern CPUs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10195 LNCS. https:\/\/doi.org\/10.1007\/978--3--319--56111-0_1","DOI":"10.1007\/978--3--319--56111-0_1"},{"key":"e_1_2_2_61_1","volume-title":"https:\/\/www.sqlite.org. [Online","year":"2021","unstructured":"SQLite. [n.d.]. SQLite. https:\/\/www.sqlite.org. [Online; accessed April-24--2021]."},{"key":"e_1_2_2_62_1","volume-title":"PLEX: Towards Practical Learned Indexing. CoRR abs\/2108.05117","author":"Stoian Mihail","year":"2021","unstructured":"Mihail Stoian, Andreas Kipf, Ryan Marcus, and Tim Kraska. 2021. PLEX: Towards Practical Learned Indexing. CoRR abs\/2108.05117 (2021)."},{"key":"e_1_2_2_63_1","first-page":"167","article-title":"The choice of partial inversions and combined indices","volume":"3","author":"Stonebraker Michael","year":"1974","unstructured":"Michael Stonebraker. 1974. The choice of partial inversions and combined indices. Int. J. Parallel Program. 3, 2 (1974), 167--188.","journal-title":"Int. J. Parallel Program."},{"key":"e_1_2_2_64_1","volume-title":"AirIndex: Versatile Index Tuning Through Data and Storage (Extended Version). arXiv preprint","author":"Supawit Chockchowwat Yongjoo Park","year":"2023","unstructured":"Yongjoo Park Supawit Chockchowwat, Wenjie Liu. 2023. AirIndex: Versatile Index Tuning Through Data and Storage (Extended Version). arXiv preprint (2023)."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056101"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00054"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409963.3410496"},{"key":"e_1_2_2_68_1","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Wei Xingda","year":"2020","unstructured":"Xingda Wei, Rong Chen, and Haibo Chen. 2020. Fast RDMA-based Ordered Key-Value Store using Remote Learned Cache. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 117--135. https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/wei"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920991"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-013-0246-y"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617308","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:15Z","timestamp":1750178775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":70,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11,13]]}},"alternative-id":["10.1145\/3617308"],"URL":"https:\/\/doi.org\/10.1145\/3617308","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]}}}