Research map / Learning theory and algorithms / Prediction and decision losses
Towards Establishing Guaranteed Error for Learned Database Operations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first information-theoretic lower bounds on the model size (bits) that learned indexing, cardinality estimation and range-sum estimation need to guarantee a given worst-case or average-case error across all databases of a given size.
Problem
Learned database operations (indexing, cardinality estimation, range-sum estimation) lack theoretical error guarantees, so there is no guidance on how large a learned model must be, as a function of data size, dimensionality and tolerable error, to guarantee accuracy on all databases.
Approach
Treats model parameters as a data representation and applies packing/metric entropy arguments to the metric space of query functions, deriving lower bounds on required model bits for worst-case (infinity-norm) and average-case (1-norm, arbitrary-norm) error across all datasets of size n.
Key results
- Worst-case lower bound for indexing: model size must exceed n/(2eps+1) * log(1+(2eps+1)u/n) bits to guarantee infinity-norm error eps on all datasets.
- Average-case (uniform query) lower bound for indexing is (sqrt(n)-2) log(1+1/(2eps)-1/sqrt(n)) bits, i.e. Omega(sqrt(n)) for constant error, with an O(n) upper bound via a nearest-neighbor encoder.
- For arbitrary query distributions, cardinality and range-sum estimation admit a distribution with no non-trivial lower bound, while indexing bounds carry over.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require worst-case error guarantees rather than average-case error guarantees | Learned database operations · Indexing, cardinality estimation, and range-sum estimation | required model size | Mixed |
| Allow arbitrary query distributions instead of uniform queries | Learned indexing · Indexing | required model size lower bound | No clear effect |
| Allow arbitrary query distributions instead of uniform queries | Learned cardinality and range-sum estimation · Cardinality and range-sum estimation | required model size lower bound | Hurt |
| Increase data size | Learned database operations · All operations | required model size | Hurt |
| Increase model size | Linear model and neural networks · Indexing and cardinality estimation on uniform and GMM data | observed error | No clear effect |
| Use sampling instead of the linear model | Learned database operations · Uniform-distribution experiments | observed error | Hurt |
| Use sampling instead of the linear model | Learned database operations · GMM experiments | observed error | No clear effect |
Surprising findings
- Lower bounds for cardinality and range-sum estimation vanish under some arbitrary query distributions, unlike indexing.
- Worst-case error bounds are impossible with finite model size when the domain is the real numbers ([0,1]), while average-case bounds do not depend on domain size.
Limitations
- Bounds are for worst-case across all datasets and are not tight for average-case (gap up to O(sqrt(n)) and observed gap between models and bounds).
- Results cover only numerical data, axis-aligned range queries, and count/sum aggregations; joins and min/max/avg not covered.
- Empirical validation limited to 1-D datasets and tiny models (linear and NNs with 10 and 50 parameters).
Experimental setup
Datasets: synthetic uniform 1-D datasets synthetic 2-component GMM 1-D datasets
Benchmarks: synthetic uniform and GMM datasets
Metrics: worst-case (infinity-norm) absolute error average (1-norm) absolute error
Baselines: Sample linear model
Builds on: learned index structures (RMI) epsilon-approximations for range counting metric entropy theory
Closest papers by meaning
- Theoretical Analysis of Learned Database Operations under Distribution Shift through Distribution Learnability (ICML 2024 · similarity 0.89)
- Confidence Estimation for Error Detection in Text-to-SQL Systems (AAAI 2025 · similarity 0.84)
- Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries (ICML 2025 · similarity 0.83)
- Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.83)
- Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.83)
- Adaptive Data Analysis for Growing Data (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.