Learned Indices for String Keys with Optimized Performance and O(N) Space Cost

Index is an important component in database systems. Learned indices have been shown to outperform traditional tree-based index structures for fixed-sized integer or floating point keys. However, the application of the learned solution to variable-length string keys is under-researched. Our experiments show that existing learned indices for strings fail to outperform traditional string indices, such as HOT and ART. String keys are long and variable sized, and often contain skewed prefixes, which make the last-mile search expensive, and adversely impact the capability of learned models to capture the skewed distribution of string keys. In this paper, we propose a novel learned index for string keys, LITS ( L earned I ndex with Hash-enhanced Prefix T able and S ub-tries). We design an optimized learned model that combines a global Hash-enhanced Prefix Table (HPT) with per-node local linear models to better distinguish string keys. Moreover, we exploit two techniques, i.e., dynamic scale factor and cell-based root, to improve the space efficiency. We prove that the resulting design is guaranteed to have O ( N ) space cost. Furthermore, we leverage compact leaf nodes and hybrid structures with a PMSS model to support efficient point and range queries. Our experimental results using eleven string data sets show that LITS achieves up to 2.19 × and 1.85 × improvement over HOT and ART for point operations with comparable scan performance and space cost.