Tuning Hierarchical Learned Indexes on Disk and Beyond

Entry retrieval-a process to retrieve rows whose field(s) associates with the given key(s)-is one of the core operations in databases. Classical indexes such as B-tree [2, 4] and skip list recursively partition the key space into a hierarchical structure. Such a structure retrieves an entry by traversing the path of partitions that enclose the given key, effectively reducing uncertainty of key's position as the traversal proceeds. Recently, index designers have developed interests in learned indexes, a concept introduced by [13]. Using patterns in key-position pairs, a learned model can provide a significantly higher information gain about the key's position than a pessimistic partitioning index can [8]. Many works have successfully outperformed classical indexes by multiple factors in latency and memory usage. Overall, they incorporate various combinations of models, partitioning, error corrections (a.k.a. last mile search), mutability, and tunable parameters [6, 9, 10, 12, 16] among many other works.