Lower Bounds for the Algorithmic Complexity of Learned Indexes

We consider a probabilistic model for a database attribute. Formally, we model the attribute as a stochastic process $X={\{X_i\}}_{i\in \mathbb{N}}$, where each $X_i$ is a real-valued random variable. At time $n\in \mathbb{N}$, the attribute consists of the first $n$ values in the sequence, sorted in increasing order. We denote the sorted values by $X_{(1)}\le \mathrm{\dots }\le X_{(n)}$, so that the attribute is represented as an array $A_n$ with $A_n[i]=X_{(i)}$ for all $i\in \{1,\mathrm{\dots },n\}$. This framework accommodates both worst-case and average-case analyses: we may consider a single sequence $X_1,\mathrm{\dots },X_n$ to study worst-case behavior, or incorporate the probability measure $\mathbb{P}$ governing the stochastic process to analyze expected performance.

No complexity lower bounds will apply in full generality. For instance, if $X_i=i$, then the rank function $\mathrm{𝐫𝐚𝐧𝐤}$ can be computed in $O(1)$ time and space, and existing structures such as the PGM-Index easily attain that performance. In this work, we derive lower bounds under the assumption that the $X_i$ are independent random variables drawn according to a common cumulative distribution function (CDF) $F$. We further assume that the query value $q$ is generated independently from the $X_i$ according to a probability measure $\mu$ which has support $𝒬\subseteq ℝ$.¹¹1Formally, one must specify measurable spaces for the data and query distributions. For simplicity, we assume that all relevant spaces are equipped with the Borel $\sigma$-algebra and that all functions we integrate are measurable; these assumptions are standard and introduce no meaningful restrictions. We emphasize that independence assumptions are only required for average-case analyses; our worst-case bounds hold unconditionally, though independence is used as a technical tool in their derivation.

Throughout the paper, we use ${𝔼}_X[\cdot ]$ to denote expectation with respect to the measure $\mathbb{P}$ governing the key sequence ${\{X_i\}}_{i=1}^n$. The notation ${𝔼}_q[\cdot ]$ denotes expectation with respect to the query distribution $\mu$, treating the key values ${\{X_i\}}_{i=1}^n$ as fixed (i.e., conditioning on a realization of the data). When expectations are taken jointly, we write ${𝔼}_{X,q}[\cdot ]$, corresponding to integration with respect to the product measure $\mathbb{P}\otimes \mu$.

One-dimensional index structures that support point and range queries over a sorted attribute must be able to determine the relative position of a query value among the stored keys. This requirement naturally leads to the rank function, which maps a query value to the number of keys less than or equal to it, and serves as the central abstraction in our analysis. As introduced in Section 2, the $\mathrm{𝐫𝐚𝐧𝐤}$ function over the attribute $A_n$ is given by

where ${\mathrm{𝟏}}_U$ denotes the indicator function of a set $U$. Hence, ${\mathrm{𝐫𝐚𝐧𝐤}}_n(q)$ maps a query value $q\in ℝ$ to the number of keys less than or equal to it. Since it is usually clear from context, we omit the sub-index $n$ and write $\mathrm{𝐫𝐚𝐧𝐤}$ instead.

Given access to $\mathrm{𝐫𝐚𝐧𝐤}(q)$, point queries and range queries can both be expressed in terms of positions within the array $A_n$. In most one-dimensional learned indexes, the goal is therefore to compute $\mathrm{𝐫𝐚𝐧𝐤}(q)$ while minimizing the required time and space overhead. We make these notions precise through the RAM model of computation.

Specifically, we adopt the RAM model of computation under the uniform cost criterion [1], where each basic instruction requires one time unit and each register, storing an arbitrary integer, uses one space unit. Time complexity is defined as the number of basic instructions required to evaluate $\mathrm{𝐫𝐚𝐧𝐤}(q)$ using an index. Space complexity measures the redundant memory used by the index, excluding the space needed to store the attribute $A_n$ itself.

Let $I$ be an indexing procedure that builds a data structure $I(A_n)$ from the attribute $A_n$. For a query value $q$, let $T(I(A_n),q)$ denote the time required to compute $\mathrm{𝐫𝐚𝐧𝐤}(q)$ using the data structure $I(A_n)$, and let $S(I(A_n))$ denote the space overhead used by $I(A_n)$. Since it is always clear from context, we usually write $T(q)$ in place of $T(I(A_n),q)$.

We model a learned index as a directed acyclic graph (DAG), as shown in Figure 1. Internal nodes implement routing functions, and sink nodes contain predictive models and store the keys. Each query follows a path from the root to a sink node, where a prediction of its rank is refined via local search. In order to support efficient range queries, keys associated with each sink are stored contiguously (or in a small number of contiguous blocks), so that scanning incurs low overhead. This structure captures a wide range of learned indexes, most of which include hierarchical routing–such as RMI [17], ALEX [5], and PGM-Index [8].

For the purpose of lower bounds, we focus on the local correction step. Regardless of how queries are routed, the exact rank of $q$ is ultimately recovered by searching around the predicted value $h(q)$ in the sorted array. Since we aim for lower bounds that hold regardless of internal structure–which can vary substantially between different designs–the cost of this local search becomes the main driver of query complexity in our analysis. By isolating this step, our analysis applies independently of the routing mechanism and can only underestimate the true query time of any concrete index.

We therefore abstract the index as a piecewise function defined by its sink-node models, and let $K$ denote the number of sinks. This corresponds to a partitioning of the query domain into $K$ regions ${\{I_v\}}_{v=1}^K$, each associated with a model $h_v$. Although we do not analyze the routing structure, we include it in the model to emphasize that our lower bounds apply regardless of graph topology or the complexity of the routing functions. Understanding how this structure impacts query time remains an open question and may lead to sharper bounds.

This abstraction captures one-dimensional index structures designed to support both point and range queries by locating positions within sorted data. A canonical example is the PGM-Index, which partitions the query domain into disjoint intervals and assigns to each interval a piecewise linear model that approximates the rank function over a contiguous subarray of keys. In contrast, data structures that only support membership or equality queries fall outside the scope of our analysis.

We denote by $ℐ$ the class of learned indexes captured by our DAG model, and by ${ℐ}_{K,ℒ}$ those whose sink-node models belong to a function class $ℒ$ (e.g., $ℒ$ could be the set of polynomial functions) and use at most $K$ sinks. For the rest of the paper, we use $K$ as a lower bound (and proxy) for space usage, and we focus on how the approximation power of $ℒ$ interacts with $K$ to characterize performance.

A learned index as defined in Section 3.3 can be seen as a structure that approximates $\mathrm{𝐫𝐚𝐧𝐤}(q)$ through a piecewise-defined prediction function

where each $h_v$ is a predictive model and $I_v\subseteq 𝒬$ its associated subdomain. For convenience, we identify an index $I$ with its induced predictive model $h$; thus, we take $h\in {ℐ}_{K,ℒ}$ to mean that $h$ is defined piecewise over $K$ disjoint intervals using functions from the class $ℒ$.

Given a predictive function $h$, the prediction error is $\epsilon (q)=|\mathrm{𝐫𝐚𝐧𝐤}(q)-h(q)|$. To analyze $\epsilon (q)$ from the perspective of function approximation, we use the empirical cumulative distribution function (ECDF). Recall that our standing assumption is that the keys $X_1,\mathrm{\dots },X_n$ are drawn i.i.d. from a distribution with CDF $F$. The ECDF is correspondingly defined as

The rank function can then be expressed as $\mathrm{𝐫𝐚𝐧𝐤}(q)=n{F}_n(q)$. Now, for both average and worst-case analysis, it is relevant to consider the expected error over all query values $q$, conditioned on $X_1,\mathrm{\dots },X_n$. Since $q$ is generated independently from $\{X_i\}$, we have

where ${\parallel \cdot \parallel }_{\mu }$ denotes the absolute norm in $L^1(\mu )$, the space of $\mu$-integrable functions over $𝒬$. In other words, the best $h$ function on average would be the function that minimizes the absolute distance to $\mathrm{𝐫𝐚𝐧𝐤}=n{F}_n$. This motivates the introduction of the minimum approximation error:

for any $G\in L^1(\mu )$. When $G=\mathrm{𝐫𝐚𝐧𝐤}=n{F}_n$, this yields

by the linear scaling property of the approximation error (see Appendix A in the extended version of the paper [3] for the proof). Now, the analysis of ${𝔼}_q\left[\epsilon (q)\right]$ reduces to an approximation problem. The key idea is that ${𝔼}_q\left[\epsilon (q)\right]$ can be lower bounded by the optimal $L^1(\mu )$-approximation of $F$, up to a small deviation term arising from sampling randomness. This deviation is captured by the function ${\delta }_n(x)=F(x)-F_n(x)$, where $F_n$ is the ECDF. The following result makes this relationship precise. The proof is straightforward and can be found in Appendix A of the extended version of the paper [3].

This shows that the expected prediction error is lower bounded by a deterministic approximation term $n{R}_{K,ℒ}(F)$, minus a data-dependent fluctuation term $n{\parallel {\delta }_n\parallel }_{\mu }$. Controlling this fluctuation is the main probabilistic step in our analysis and will be addressed in the next subsection. In addition to ${𝔼}_q\left[\epsilon (q)\right]$, we also need bounds on ${𝔼}_q\left[{\log }_2\epsilon (q)\right]$, which arises in the analysis of exponential search. To this end, we define a proxy for query time: $\tilde{T}(q)={\log }_2\left(\max \{2,\epsilon (q)\}\right)$, and establish a lower bound for its expectation. This requires a careful analysis and specific assumptions on $F$, $\mu$, and $ℒ$. The following result illustrates this type of bound (for the proof, see the extended version of the paper [3]).

Proposition 2 provides a logarithmic analogue to Proposition 1, which is useful for analyzing exponential search. The use of $\max \{2,\cdot \}$ in $\tilde{T}(q)$ ensures that the proxy for query time is at least $1$. The constants $C_1$ and $C_2$ depend on $c_F$ and $C_F$, and might be disadvantageous. Still, they are independent of $n$ and $K$, and do not change the asymptotic analysis. Moreover, the condition need not be satisfied on all of $𝒬$; it suffices that it holds over a subinterval ${𝒬}^{\prime }\subseteq 𝒬$. The main limitation of this variant, in contrast to Proposition 1, is the constraint $ℒ=P_0$, and the fact that this bound only holds for a specific realization $X_1,\mathrm{\dots },X_n$: it does not necessarily hold for all ${\{X_i\}}_{i=1}^n\sim \mathbb{P}$.

The lower bounds in Propositions 1 and 2 depend on $R_{K,ℒ}(F)$ and the behavior of ${\delta }_n$. On the one hand, $R_{K,ℒ}(F)$ is a deterministic quantity that depends only on $F$, the model class $ℒ$, and the measure $\mu$, and can be studied using approximation theory. On the other hand, we can use probabilistic tools to control the term ${\parallel {\delta }_n\parallel }_{\mu }$ , ensuring it is small enough that the dominant source of error stems from approximating $F$ rather than from sampling variability.

Generally, we wish to say that ${\delta }_n$ behaves like $1/r(n)$ for some function $r(n)$ that quantifies the rate of convergence of $F_n$ to $F$. This allows us to isolate all randomness in a single term, $1/r(n)$, and express lower bounds on ${𝔼}_q\left[\epsilon (q)\right]$ in terms of the deterministic approximation error for $F$. To make this precise, we rely on two types of results: expected and worst-case concentration. All proofs are included in the extended version of the paper, Appendix D [3].

We now complete our framework by translating prediction error into actual query time. As discussed in Section 3.3, the final stage of query processing involves a local search to correct the predicted rank $h(q)$ into the true value $\mathrm{𝐫𝐚𝐧𝐤}(q)$. The cost of this step depends on the prediction error $\epsilon (q)=|\mathrm{𝐫𝐚𝐧𝐤}(q)-h(q)|$, and varies depending on the algorithm used. We analyze the three most common search strategies: linear, exponential, and binary search.

We are now ready to combine the results from the previous subsections to derive concrete lower bounds on the query time $T(q)$ under the three search strategies described in Section 4.3. We consider three natural types of lower bounds, which differ in the strength of their guarantees and the assumptions they require. In increasing order of generality, we consider:

1. (A)

   Full expectation bounds (average-case):

   $${𝔼}_{X,q}[T(q)]\ge C(n,K,ℒ,F,\mu ).$$

   This is the strongest type of result, holding in expectation over both the random dataset ${\{X_i\}}_{i=1}^n$ and the query value $q\sim \mu$ . It typically requires strong assumptions (e.g., i.i.d. sampling) but yields average-case bounds across the entire system.

2. (B)

   Conditional expectation bounds (mixed-case):

   $$\underset{{\{X_i\}}_{i=1}^n}{sup}{𝔼}_q[T(q)]\ge C(n,K,ℒ,F,\mu ).$$

   This corresponds to worst-case bound over data and average-case bound over queries.

3. (C)

   Pointwise bounds (worst-case):

   $$\underset{{\{X_i\}}_{i=1}^n,q\in 𝒬}{sup}T(q)\ge C(n,K,ℒ,F,\mu ).$$

   This is a purely worst-case guarantee, asserting that there exists some dataset and query for which the query time is large. It requires the fewest assumptions.

These regimes form a natural hierarchy: a type (A) bound implies one of type (B), which in turn implies one of type (C). This implication structure follows directly from the probabilistic method and reflects a trade-off between generality and the strength of assumptions. Importantly, the bounds hold uniformly over the model class ${ℐ}_{K,ℒ}$ , i.e., they apply to every learned index structure in ${ℐ}_{K,ℒ}$ .

Table 1 summarizes the resulting lower bounds on query time $T(q)$ under different search strategies, assumptions on the query distribution $\mu$, and the three types of lower bounds (A)–(C) discussed above. These results show how the strongest bounds are attainable for linear search, followed by exponential search, and finally binary search, where we can only derive worst-case guarantees. All proofs are included in the extended version of the paper [3]; most follow directly from the general framework developed earlier in this section.

Notice that the type (B) bound for exponential search is written asymptotically, without the constant $C_1$ from Proposition 2, in order to highlight its structural similarity to the rest.

These results highlight the trade-offs between model complexity, dataset size, search strategy, and query performance in learned indexes. Note that Table 1 considers two representative regimes for the query distribution: (i ) arbitrary $\mu$, and (ii ) the matched case $d\mu =dF$, where queries are drawn from the same distribution as the dataset. The latter is especially relevant in practice, as it is widely used in evaluations of learned indexes [8, 21, 19].

Altogether, this framework provides a general and flexible method for deriving query time lower bounds. In the following sections, we analyze the error term $R_{K,ℒ}(F)$ for concrete model classes commonly used in learned index structures. Section 5 focuses on $ℒ=P_0$, corresponding to piecewise constant models [29, 4], while Section 6 considers $ℒ=P_1$, corresponding to piecewise linear approximators, the most widely adopted choice in practice.

For the relatively simple case of piecewise constant approximating functions $h\in {ℐ}_{K,P_0}$ and $f=g$, the minimum approximation error $R_{K,P_0}(F)$ can be calculated exactly for any $K$. We achieve this by first showing that this problem setup reduces to optimal quantization of a uniformly distributed random variable, and then relying on a well-known result in quantization theory to calculate the error of the associated optimal quantizer.

Let $h\in {ℐ}_{K,P_0}$. Since $F$ is a CDF with range $[0,1]$, without loss of generality we can assume $0\le h(q)\le 1$ for all $q$. Therefore, $h$ can be written as

where the $K$ intervals $\{I_k\}$ partition $𝒬$, and $c_k\in [0,1]$ are the corresponding approximating constants. This means that when $f=g$, the absolute error ${\parallel F-h\parallel }_{\mu }$ can be written as

where $J_k=F(I_k)=\{F(q):q\in I_k\}$ (which is a continuous interval), and the last equality comes from substituting $u=F(q)$ and $du=f(q)dq$ inside the integrals. Since $F$ is a CDF we know that $\{J_k\}$ is a partition of $[0,1]$. If we now define $Q_K(u)={\sum }_{k=1}^K{c}_k{\mathrm{𝟏}}_{J_k}(u),$ then (4) can be expressed as

where $Q_K$ is a piecewise constant function over $[0,1]$ and the expectation is taken over a $\text{Uniform}([0,1])$ random variable $U$. Note that (4)–(5) reflect the fact that $F(X)$ is uniformly distributed when $X\sim F$.

In other words, minimizing ${\parallel F-h\parallel }_{\mu }$ is equivalent to choosing a set of intervals $\{J_k\}$ and the associated points $\{c_k\}$ so as to minimize the expected distance between a realization of $U$ and its corresponding value $c_k$. We recognize this as the problem of optimal quantization of $U$ under the absolute error.

It is a well-established result in quantization theory that uniform quantization is optimal for $\text{Uniform}([0,1])$. Specifically, the quantization points should be equally spaced as $\{c_k=\frac{2k-1}{2K}:k=1,\mathrm{\dots },K\}$, and the quantization intervals $\{J_k\}$ should split the domain $[0,1]$ evenly. The associated minimum quantization error is equal to [12, Example 5.5]

this means that, in our notation,

It is interesting to note that the minimum approximation error (6) and the optimal $\{c_k\}$ and $\{J_k\}$ are the same for any $F$; the only dependence on $F$ is via the regions $\{I_k\}$ that should split $𝒬$ at the $K$-quantiles of $F$ to yield equal-sized $\{J_k\}$.

We illustrate this setting graphically in Figure 5, where we show an example CDF curve $F(x)$ (blue), optimally approximated by a piecewise constant function $h$ (red) with $K=5$ segments. The approximation points $\{c_k\}$ are evenly spaced along the $y$-axis, and the mid-points between them, when reflected onto the $x$-axis via $F^{-1}$, mark the quintiles of $F$, which split $𝒬$ into $K=5$ equiprobable regions $\{I_k\}$. The “uniformization” of a distribution by its own CDF that we used in (4)–(5) is illustrated by the green dotted lines–their density below the blue CDF curve is proportional to $f$, whereas above the CDF curve, when reflected off it onto the $y$-axis, it becomes uniform.

To illustrate the limitations of piecewise linear approximators, we construct a family of CDFs ${\{F_M\}}_{M\in \mathbb{N}}$ with the following property: for any $M>(1+\alpha )K$ with $\alpha >0$, the approximation error satisfies $R_{K,P_1}(F_M)=\mathrm{\Omega }(1/K)$. The construction, detailed in Appendix B, is based on stitching together rescaled copies of the quadratic function $x^2$ over $M$ disjoint intervals. While this is presented under the assumption that $\mu$ is the uniform distribution, the argument naturally extends to a broader class: specifically, any measure $\mu$ with a density $g$ satisfying $g(q)\ge \lambda >0$ over an interval. In such cases, the lower bound continues to hold up to constants depending on $\lambda$.

Thus, this construction provides a worst-case lower bound for $R_{K,P_1}(F)$ within the class of Lipschitz continuous CDFs. It also highlights a fundamental aspect of learned indexes: the approximation error depends on both the location and the number of difficult-to-approximate regions. Hence, the choice of partition and local model must be adapted to the data. Fixing the model class and budget $K$ in advance cannot guarantee uniformly good approximation.

To further understand the limitations of learned index models beyond explicit constructions, we turn to a more general framework from approximation theory: Kolmogorov widths. This concept provides a way to quantify how well an entire function class $ℱ$ can be approximated by models of bounded complexity. Formally, the Kolmogorov width $d_{\kappa }(ℱ)$ captures the best possible worst-case approximation error over $ℱ$:

where the outermost infimum is taken over the set ${\mathscr{H}}_{\kappa }$ of all linear subspaces of dimension $\kappa$.

We relate $d_{\kappa }(ℱ)$ to our context in the following way. Throughout, we have considered approximation by functions in ${ℐ}_{K,ℒ}$. This class is not necessarily a linear subspace of $L^1(\mu )$, since the sum of two $K$-piecewise functions is not necessarily $K$-piecewise. Nonetheless, if we fix a partition $𝒫={\{I_k\}}_{k=1}^K$ of $𝒬$, the subclass

does form a linear subspace, provided that $ℒ$ is itself a linear subspace of $L^1(\mu )$. In such cases–e.g., when $ℒ$ consists of polynomials of bounded degree–any function class ${ℐ}_{𝒫,ℒ}$ has dimension at most $\kappa =K\cdot dim(ℒ)$. This characterization leads to the following inequality.

The proof can be found in Appendix G of the extended version of the paper [3]. We now focus on the case where $ℱ$ is the class of Lipschitz continuous functions, denoted by $W^{1,\mathrm{\infty }}$. This notation comes from Sobolev space theory, which provides a convenient formalism for characterizing function smoothness, and within which most Kolmogorov width results are typically stated. When $\mu$ is the uniform distribution over a compact interval $[a,b]$, it holds that (see [20, Chapter 14, Theorem 3.8]):

Notice that for $ℒ=P_m$, the class of degree-$m$ polynomials, we have $\kappa =(m+1)K$, since each piece has $m+1$ parameters. Piecewise linear models correspond to $m=1$ and thus $\kappa =2K$. Hence, for fixed $m$, Lemma 6 and equation (7) imply ${sup}_{F\in W^{1,\mathrm{\infty }}}{R}_{K,P_m}(F)=\mathrm{\Omega }(1/K)$.

This has a direct implication for learned index structures: even the best possible model using $K$ adaptive segments and bounded-degree polynomial predictors cannot achieve approximation error $o(1/K)$ for general Lipschitz continuous CDFs.²²2This conclusion requires some care. While the Kolmogorov width bound is stated for the worst-case over the class $W^{1,\mathrm{\infty }}$, it is not immediate that the worst-case functions realizing the $\mathrm{\Omega }(1/\kappa )$ bound include any CDFs. In principle, one might worry that these worst-case functions do not include any valid CDFs. However, this is not the case. In the extended version of the paper [3], we provide a rigorous argument showing that any hard-to-approximate function $F\in W^{1,\mathrm{\infty }}$ can be mapped to a CDF that remains equally hard to approximate.

These results match the $\mathrm{\Omega }(1/K)$ result obtained in Section 6.1. While the explicit construction from Section 6.1 can accommodate a wide class of distributions $\mu$, including non-uniform densities, the Kolmogorov width approach offers a wider perspective in regards to the approximating functions. In particular, it applies to any piecewise polynomial class ${ℐ}_{K,P_m}$ and, more generally, to any linear span of $\kappa$ functions, such as truncated Fourier series.

The Kolmogorov width framework makes it explicit that the $\mathrm{\Omega }(1/K)$ bound is inherently a worst-case result. For smoother subclasses $ℱ\subseteq W^{1,\mathrm{\infty }}$, the theory yields sharper rates: for example, for $W^{2,\mathrm{\infty }}$ (i.e., functions with Lipschitz continuous derivatives), one obtains $d_{\kappa }(W^{2,\mathrm{\infty }})=\mathrm{\Theta }(1/{\kappa }^2)$. This highlights how stronger regularity assumptions can enable faster approximation. In contrast, the lower bound for piecewise constant models (Section 5) applies uniformly to all Lipschitz continuous CDFs and does not improve with additional regularity.