Research map / Learning theory and algorithms / Prediction and decision losses
Theoretical Analysis of Learned Database Operations under Distribution Shift through Distribution Learnability
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 a distribution-learnability framework giving theoretical bounds on learned indexing, cardinality estimation and sorting under insertions and distribution shift, showing a Ω(√k) generalization error lower bound for any fixed model.
Problem
Learned database operations (indexing, cardinality estimation, sorting) degrade under data insertions and distribution shift, yet no theoretical guarantees exist for their performance in dynamic datasets.
Approach
Introduces distribution learnability, which abstracts the modeling problem into a learnable-distribution-class oracle with accuracy, inference and training complexity parameters, so that generalization under insertions and distribution shift (measured by total variation) can be analyzed separately; shows any fixed model's expected error grows as Ω(√k) after k insertions, and derives query/insertio
Key results
- Theorem shows any fixed model trained after i insertions has expected sup error at least √k/4 after k further insertions, independent of model capacity and data distribution (for continuous distributions).
- For distributions with bounded p.d.f., learned indexing achieves O(T log log n + log(δn)) query and insertion time with O(n log n) space, per the summary of results.
- Learned sorting with a learned model achieves O(n log log n) time for bounded-pdf distributions, and O(n) when the distribution is known and efficiently evaluable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use learned indexing with no distribution shift (δ=0) | Learned indexing · Dynamic indexing, 𝔛_ρ or 𝔛_c | query and insertion complexity: O(log log n) vs O(log n) | Helped |
| Increase distribution shift to the worst case (δ=1) | Learned indexing · Dynamic indexing | query and insertion complexity: O(log log n+logδn) | Hurt |
| Use learned cardinality estimation for a known distribution class with ε≥√n | Cardinality estimation · High-dimensional cardinality estimation, 𝔛_c | query and insertion time: O(1) vs space exponential in dimensionality | Helped |
| Use learned cardinality estimation in 1 dimension for 𝔛_c | Cardinality estimation · 1-dimensional cardinality estimation | query and insertion complexity: O(log n) | Helped |
| Use learned sorting when the distribution is approximately known and efficiently evaluable | Learned sorting · Static sorting | time complexity: O(n) | Helped |
| Keep a single model fixed for k insertions instead of retraining | Learned indexing or cardinality estimation · Dynamic data sampled i.i.d. from a continuous distribution | expected maximum generalization error: √k/4 | Hurt |
Surprising findings
- Any fixed learned model's generalization error grows as Ω(√k) with insertions even when the distribution does not change, so frequent retraining or partial retraining is theoretically necessary.
- With total variation distribution shift δ=1 (worst case), learned indexing gives no advantage over non-learned methods.
Limitations
- Purely theoretical; no empirical evaluation reported in the provided text.
- Indexing bounds degrade to no advantage over non-learned methods as distribution shift approaches the worst case (δ=1).
- Cardinality estimation results in high dimensions require error at least √n and space exponential in dimensionality for general distribution classes.
Experimental setup
Baselines: B-tree PGM index sampling-based cardinality estimation
Builds on: PGM index interpolation search piecewise linear approximation
Closest papers by meaning
- Towards Establishing Guaranteed Error for Learned Database Operations (ICLR 2024 · similarity 0.89)
- Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.84)
- Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization (NeurIPS 2024 · similarity 0.83)
- Adaptive Data Optimization: Dynamic Sample Selection with Scaling Laws (ICLR 2025 · similarity 0.83)
- In-Context Adaptation to Concept Drift for Learned Database Operations (ICML 2025 · similarity 0.83)
- "What is Different Between These Datasets?" A Framework for Explaining Data Distribution Shifts (NeurIPS 2026 · similarity 0.83)
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.