LSI: A Learned Secondary Index Structure
This addresses the need for efficient secondary indexing in databases, offering significant space savings, though it is an incremental extension of learned indexes to a new setting.
The paper tackled the problem of applying learned index structures to unsorted secondary indexing, introducing LSI which uses a permutation vector and fingerprint vector to achieve comparable lookup performance to state-of-the-art methods while being up to 6x more space efficient.
Learned index structures have been shown to achieve favorable lookup performance and space consumption compared to their traditional counterparts such as B-trees. However, most learned index studies have focused on the primary indexing setting, where the base data is sorted. In this work, we investigate whether learned indexes sustain their advantage in the secondary indexing setting. We introduce Learned Secondary Index (LSI), a first attempt to use learned indexes for indexing unsorted data. LSI works by building a learned index over a permutation vector, which allows binary search to performed on the unsorted base data using random access. We additionally augment LSI with a fingerprint vector to accelerate equality lookups. We show that LSI achieves comparable lookup performance to state-of-the-art secondary indexes while being up to 6x more space efficient.