DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2026.14

Lower Bounds for the Algorithmic Complexity of Learned Indexes

Authors: Luis Alberto Croquevielle, Roman Sokolovskii, and Thomas Heinis

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract

Learned index structures aim to accelerate queries by training machine learning models to approximate the rank function associated with a database attribute. While effective in practice, their theoretical limitations are not fully understood. We present a framework for proving lower bounds on query time for learned indexes, expressed in terms of their space overhead and parameterized by the model class used for approximation. Our formulation captures a broad family of one-dimensional learned indexes, including most existing designs, as piecewise model-based predictors. We solve the problem of lower bounding query time in two steps: first, we use probabilistic tools to control the effect of sampling when the database attribute is drawn from a probability distribution. Then, we analyze the approximation-theoretic problem of how to optimally represent a cumulative distribution function with approximators from a given model class. Within this framework, we derive lower bounds under a range of modeling and distributional assumptions, paying particular attention to the case of piecewise linear and piecewise constant model classes, which are common in practical implementations. Our analysis shows how tools from approximation theory, such as quantization and Kolmogorov widths, can be leveraged to formalize the space-time trade-offs inherent to learned index structures. The resulting bounds illuminate core limitations of these methods.

Cite as

Luis Alberto Croquevielle, Roman Sokolovskii, and Thomas Heinis. Lower Bounds for the Algorithmic Complexity of Learned Indexes. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{croquevielle_et_al:LIPIcs.ICDT.2026.14,
  author =	{Croquevielle, Luis Alberto and Sokolovskii, Roman and Heinis, Thomas},
  title =	{{Lower Bounds for the Algorithmic Complexity of Learned Indexes}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.14},
  URN =		{urn:nbn:de:0030-drops-256285},
  doi =		{10.4230/LIPIcs.ICDT.2026.14},
  annote =	{Keywords: Learned Indexes, Stochastic Processes, Approximation Theory}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2025.19

Beyond Logarithmic Bounds: Querying in Constant Expected Time with Learned Indexes

Authors: Luis Alberto Croquevielle, Guang Yang, Liang Liang, Ali Hadian, and Thomas Heinis

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract

Learned indexes leverage machine learning models to accelerate query answering in databases, showing impressive practical performance. However, theoretical understanding of these methods remains incomplete. Existing research suggests that learned indexes have superior asymptotic complexity compared to their non-learned counterparts, but these findings have been established under restrictive probabilistic assumptions. Specifically, for a sorted array with n elements, it has been shown that learned indexes can find a key in O(log(log n)) expected time using at most linear space, compared with O(log n) for non-learned methods. In this work, we prove O(1) expected time can be achieved with at most linear space, thereby establishing the tightest upper bound so far for the time complexity of an asymptotically optimal learned index. Notably, we use weaker probabilistic assumptions than prior research, meaning our work generalizes previous results. Furthermore, we introduce a new measure of statistical complexity for data. This metric exhibits an information-theoretical interpretation and can be estimated in practice. This characterization provides further theoretical understanding of learned indexes, by helping to explain why some datasets seem to be particularly challenging for these methods.

Cite as

Luis Alberto Croquevielle, Guang Yang, Liang Liang, Ali Hadian, and Thomas Heinis. Beyond Logarithmic Bounds: Querying in Constant Expected Time with Learned Indexes. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{croquevielle_et_al:LIPIcs.ICDT.2025.19,
  author =	{Croquevielle, Luis Alberto and Yang, Guang and Liang, Liang and Hadian, Ali and Heinis, Thomas},
  title =	{{Beyond Logarithmic Bounds: Querying in Constant Expected Time with Learned Indexes}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.19},
  URN =		{urn:nbn:de:0030-drops-229603},
  doi =		{10.4230/LIPIcs.ICDT.2025.19},
  annote =	{Keywords: Learned Indexes, Expected Time, Stochastic Processes, R\'{e}nyi Entropy}
}

Search Results

Documents authored by Heinis, Thomas

Lower Bounds for the Algorithmic Complexity of Learned Indexes

Abstract

Cite as

Beyond Logarithmic Bounds: Querying in Constant Expected Time with Learned Indexes

Abstract

Cite as

Thanks for your feedback!

Could not send message