Sail improves learned index query speed with hybrid node structures

SAIL: Self-Adaptive Index Learning with Hybrid Models (Extended Version)

Databases

Summary

Indexes help computers find data quickly, but traditional ones can be slow or bulky. The authors created SAIL, a new kind of index that uses different types of parts inside, chosen based on what fits the data best. This makes searching much faster without needing much more memory or time to build the index. Their tests show it can be twice as fast as older learned indexes.

What this means in practice

  • For database administrators: Speed up data queries by deploying SAIL indexes that adapt node types to key distributions for faster lookups without more memory use.
  • For storage system engineers: Improve storage system metadata search times using hybrid learned indexes built with SAIL's efficient construction approach.

Authors

Kasun Amarasinghe, Farhana Choudhury, Jianzhong Qi

Abstract

Learned index structures have demonstrated a significant improvement in query performance over traditional index structures. The majority of learned indexes use a uniform node structure throughout their index structures. A few studies show that combining multiple types of node structures can lead to indexes that better adapt to local key-set distributions, hence yielding query efficiency gains. Following this line of work, we propose a learned index structure named SAIL that supports a wide range of different candidate node structures for both leaf and inner nodes, selected via cost models based on data driven approximations. We design an efficient construction algorithm that recursively partitions the key-set to be fitted by the candidate node types. Experiments demonstrate that SAIL achieves 2x improvement over existing learned indexes in query time, with similar memory consumption and index build times.