Index structure plays a crucial role in enhancing the performance of storage systems. By integrating machine learning models, learned indexes outperform traditional tree-based indexes. However, real-world scenarios often involve limited memory, making on-disk indexes necessary for large-scale data. When directly migrating memory-based learned indexes to disk, inaccurate predictions of disk blocks lead to excessive disk I/Os, causing waste of time and space. Existing on-disk learned indexes consider disk I/O characteristics but still overlook environments where both memory and disk are used, resulting in excessive memory consumption. To address redundant disk I/Os and inefficient memory use, we propose DCLex, a learned index optimized for minimal disk I/Os and efficient memory utilization. During query processing, DCLex accurately predicts the target disk block through a carefully crafted leaf node structure, effectively reducing I/O overhead. Furthermore, DCLex exploits an adaptive CombinedCache that dynamically adjusts the ratio between key-value cache and block cache, thus improving the cache efficiency across diverse workloads. Finally, DCLex accelerates the index construction as much as possible with low memory usage. Evaluations on four real-world datasets show that DCLex outperforms the state-of-the-art disk-based learned indexes by 1.8 \(\times \) to 3.4 \(\times \) in search performance and 1.6 \(\times \) to 14.1 \(\times \) in insert performance.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

DCLex: An On-Disk Learned Index with Optimized I/O and Caching

  • Zhuoran Wang,
  • Lixiao Cui,
  • Gang Wang,
  • Xiaoguang Liu

摘要

Index structure plays a crucial role in enhancing the performance of storage systems. By integrating machine learning models, learned indexes outperform traditional tree-based indexes. However, real-world scenarios often involve limited memory, making on-disk indexes necessary for large-scale data. When directly migrating memory-based learned indexes to disk, inaccurate predictions of disk blocks lead to excessive disk I/Os, causing waste of time and space. Existing on-disk learned indexes consider disk I/O characteristics but still overlook environments where both memory and disk are used, resulting in excessive memory consumption. To address redundant disk I/Os and inefficient memory use, we propose DCLex, a learned index optimized for minimal disk I/Os and efficient memory utilization. During query processing, DCLex accurately predicts the target disk block through a carefully crafted leaf node structure, effectively reducing I/O overhead. Furthermore, DCLex exploits an adaptive CombinedCache that dynamically adjusts the ratio between key-value cache and block cache, thus improving the cache efficiency across diverse workloads. Finally, DCLex accelerates the index construction as much as possible with low memory usage. Evaluations on four real-world datasets show that DCLex outperforms the state-of-the-art disk-based learned indexes by 1.8 \(\times \) to 3.4 \(\times \) in search performance and 1.6 \(\times \) to 14.1 \(\times \) in insert performance.