# A Pluggable Learned Index Method via Sampling and Gap Insertion

arXiv: https://arxiv.org/abs/2101.00808 · HTML: https://mlsanity.com/paper/2101.00808/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 4 Jan 2021.

## Builds on (most cited first, 15 of 15)

- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [A Survey on Learning to Hash](https://mlsanity.com/paper/1606.00185/) (2016)
- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [Minimum Description Length Revisited](https://mlsanity.com/paper/1908.08484/) (2019)
- [Learning to Optimize Join Queries With Deep Reinforcement Learning](https://mlsanity.com/paper/1808.03196/) (2018)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [FITing-Tree: A Data-aware Index Structure](https://mlsanity.com/paper/1801.10207/) (2018)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Learning Memory Access Patterns](https://mlsanity.com/paper/1803.02329/) (2018)
- [Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads](https://mlsanity.com/paper/2006.13282/) (2020)
- [Learning State Representations for Query Optimization with Deep Reinforcement Learning](https://mlsanity.com/paper/1803.08604/) (2018)
- [Towards a Hands-Free Query Optimizer through Deep Learning](https://mlsanity.com/paper/1809.10212/) (2018)

## Built on by (most cited first, 1 of 1)

- [NFL: Robust Learned Index via Distribution Transformation](https://mlsanity.com/paper/2205.11807/) (2022)

## Abstract (arXiv)

Database indexes facilitate data retrieval and benefit broad applications in real-world systems. Recently, a new family of index, named learned index, is proposed to learn hidden yet useful data distribution and incorporate such information into the learning of indexes, which leads to promising performance improvements. However, the "learning" process of learned indexes is still under-explored. In this paper, we propose a formal machine learning based framework to quantify the index learning objective, and study two general and pluggable techniques to enhance the learning efficiency and learning effectiveness for learned indexes. With the guidance of the formal learning objective, we can efficiently learn index by incorporating the proposed sampling technique, and learn precise index with enhanced generalization ability brought by the proposed result-driven gap insertion technique. We conduct extensive experiments on real-world datasets and compare several indexing methods from the perspective of the index learning objective. The results show the ability of the proposed framework to help to design suitable indexes for different scenarios. Further, we demonstrate the effectiveness of the proposed sampling technique, which achieves up to 78x construction speedup while maintaining non-degraded indexing performance. Finally, we show the gap insertion technique can enhance both the static and dynamic indexing performances of existing learned index methods with up to 1.59x query speedup. We will release our codes and processed data for further study, which can enable more exploration of learned indexes from both the perspectives of machine learning and database.