A Fully On-Disk Updatable Learned Index

While in-memory learned indexes have shown promising performance as compared to B+-tree, most widely used databases in real applications still rely on disk-based operations.

From our experiments, we observe that directly applying the existing in-memory learned indexes into on-disk setting suffers from several drawbacks and cannot outperform a standard B+-tree in most cases. Therefore, we make the first attempt to show how the idea of learned index can benefit the on-disk index by proposing AULID, a fully on-disk updatable learned index that can achieve state-of-the-art performance across multiple workload types. The AULID approach combines the benefits from both traditional indexing techniques and the learned indexes to reduce the I/O cost -the main overhead under disk setting. Specifically, three aspects are taken into consideration in reducing I/O costs: (1) reduce the overhead in updating the index structure; (2) induce shorter paths from root to leaf node; (3) achieve better locality to minimize the number of block reads required to complete a scan. Five principles are proposed to guide the design of AULID which shows remarkable performance gains and meanwhile is easy to implement. Our evaluation shows that AULID has comparable storage costs to a B+-tree and is much smaller than other learned indexes, and AULID is up to 2.11x, 8.63x, 1.72x, 5.51x, and 8.02x more efficient than FITing-tree, PGM, B+-tree, ALEX, and LIPP.

1 For a Scan-Only workload, we set the start key to the same key that was used in the Lookup-Only workload, and then we scan forward 99 keys. This ensures that ALEX, PGM, a FITing-tree, and a B+-tree fetch the same number of inner nodes and blocks needed for a lookup and a scan.