# Towards Establishing Guaranteed Error for Learned Database Operations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 9 Nov 2024.

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

- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [Deep Unsupervised Cardinality Estimation](https://mlsanity.com/paper/1905.04278/) (2019)
- [FITing-Tree: A Data-aware Index Structure](https://mlsanity.com/paper/1801.10207/) (2018)
- [Flow-Loss: Learning Cardinality Estimates That Matter](https://mlsanity.com/paper/2101.04964/) (2021)
- [A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation](https://mlsanity.com/paper/2107.12295/) (2021)
- [One Network Fits All? Modular versus Monolithic Task Formulations in Neural Networks](https://mlsanity.com/paper/2103.15261/) (2021)
- [On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing](https://mlsanity.com/paper/2306.10651/) (2023)
- [NeuroSketch: Fast and Approximate Evaluation of Range Aggregate Queries with Neural Networks](https://mlsanity.com/paper/2211.10832/) (2022)

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

- [Lower Bounds for the Algorithmic Complexity of Learned Indexes](https://mlsanity.com/paper/2601.06629/) (2026)
- [Selectivity Estimation for Linear Queries via Online Learning](https://mlsanity.com/paper/2607.02895/) (2026)

## Abstract (arXiv)

Machine learning models have demonstrated substantial performance enhancements over non-learned alternatives in various fundamental data management operations, including indexing (locating items in an array), cardinality estimation (estimating the number of matching records in a database), and range-sum estimation (estimating aggregate attribute values for query-matched records). However, real-world systems frequently favor less efficient non-learned methods due to their ability to offer (worst-case) error guarantees - an aspect where learned approaches often fall short. The primary objective of these guarantees is to ensure system reliability, ensuring that the chosen approach consistently delivers the desired level of accuracy across all databases. In this paper, we embark on the first theoretical study of such guarantees for learned methods, presenting the necessary conditions for such guarantees to hold when using machine learning to perform indexing, cardinality estimation and range-sum estimation. Specifically, we present the first known lower bounds on the model size required to achieve the desired accuracy for these three key database operations. Our results bound the required model size for given average and worst-case errors in performing database operations, serving as the first theoretical guidelines governing how model size must change based on data size to be able to guarantee an accuracy level. More broadly, our established guarantees pave the way for the broader adoption and integration of learned models into real-world systems.