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

Learned indexes use statistical models. Therefore, theoretical analysis of learned indexes is done under a probabilistic model of some kind [34, 9]. In general, keys are assumed to come from a data generating process with specified properties. For instance, in [34] it is assumed that the keys are independent and identically distributed, while [9] uses a completely different model. We strive to generalize the probabilistic setting as much as possible.

Formally, we model a database attribute $X$ as a stochastic process $X={\{X_i\}}_{i\in \mathbb{N}}$. We assume all random variables $X_i$ have the same cumulative distribution function $F$. For any time $n\in \mathbb{N}$, we can observe the data $X_1,X_2,\mathrm{\dots },X_n$ generated so far. Sorting the ${\{X_i\}}_{i=1}^n$ gives rise to a new set of random variables, usually called the order statistics [7], which we denote $X_{(1)},X_{(2)},\mathrm{\dots },X_{(n)}$. We consider the sorted array $A$ at time $n$ to be formed by this last group of random variables, such that $A[i]=X_{(i)}$ for all $i=1,\mathrm{\dots },n$. Duplicate keys are possible in principle, and do not constitute a problem. In that case, $X_{(i+1)}=X_{(i)}$ for some $i$ and all analysis remains the same.

That way, in our setting a stochastic process generates the data in attribute $X$. For each $n\in \mathbb{N}$, there is a sorted array $A$ with the first $n$ keys from this process, and a learned index can be built to search this array. For now, we do not assume anything about $F$. Also, we do not assume independence of the ${\{X_i\}}_{i=1}^n$ variables. In Sections 3 and 4, we analyze our results under certain probabilistic assumptions. In Section 5, we compare our model and results to those of prior work.

Assume array $A$ has $n$ keys. The learning problem can be formalized by the introduction of a $\mathrm{𝐫𝐚𝐧𝐤}$ function. For any number $q\in ℝ$, ${\mathrm{𝐫𝐚𝐧𝐤}}_A(q)$ is defined as the number of elements in $A$ that are smaller than or equal to $q$, that is

where $\mathrm{𝟏}$ is the indicator function. We omit the subscript $A$ if it is clear from context. For a point query with value $q$, $\mathrm{𝐫𝐚𝐧𝐤}(q)$ gives the position of $q$ in the array if it exists. For a range query matching an interval $[q,q^{\prime }]$, the relevant records are found by scanning the array $A$, starting at position $\mathrm{𝐫𝐚𝐧𝐤}(q)$ and ending when an element greater than $q^{\prime }$ is found. Since $\mathrm{𝐫𝐚𝐧𝐤}$ is sufficient to answer these queries, we focus on the problem of learning the $\mathrm{𝐫𝐚𝐧𝐤}$ function under specific probabilistic assumptions.

The model of computation we use is the Random Access Machine (RAM) under the uniform cost criterion [1]. In this model, each instruction requires one unit of time and each register (storing an arbitrary integer) uses one unit of space. This is in contrast to part of the existing literature. In [34] the computation model is such that $O(\log n)$ space units are needed to store an integer $n$. On the other hand, in [9] an I/O model of computation is used [20], which assumes the existence of an external memory (e.g., disk) from which data is read and written to. Under this model, time complexity consists only of the number of I/O operations.

We argue the RAM model under the uniform cost criterion is better suited for analysing learned indexes than either of these two. On the one hand, numbers are usually represented as data types with a fixed number of bits (e.g., long int in C++). On the other hand, most learned indexes work in main memory and avoid the use of disk storage. To make results comparable, in Section 5 we restate all previous complexity results using our RAM model.

Regarding space complexity, we take the standard approach of only counting the redundant space introduced by the index, and not the space necessary to store the array $A$ in the first place [10]. Regarding time complexity, we do not consider the time needed to train the model, just for finding the keys. We focus the asymptotic analysis on expected time, where the expectation is taken over the realizations of the stochastic process and the choice of query.

For any $n\in \mathbb{N}$, let $R_n$ be a procedure that takes the sorted array $A=[X_{(1)},\mathrm{\dots },X_{(n)}]$ as input, and outputs an index structure $R_n(A)$. Denote by $S(R_n(A))$ the space overhead of $R_n(A)$. Also, for any $q\in ℝ$ denote by $T(R_n(A),q)$ the query time for $q$ over array $A$ when using the index $R_n(A)$. We are interested in bounds for $S$ and $T$ that do not depend on $A$ or $q$. With that in mind, we denote

where $𝔼$ denotes expected value. In Section 3.1 we state asymptotic results for ${\overline{S}}_n$ and ${\overline{T}}_n$.

We mentioned above that all the $X_i$ share the same cumulative distribution function. Formally, we consider that the $X_i$ are defined in a probability space $(\mathrm{\Omega },ℱ,\mathbb{P})$, such that $F_{X_i}(x)≔\mathbb{P}\left(X_i\le x\right)$ is the same for all $i$, and is denoted by $F$. Now, assume $F$ can be characterized by a square-integrable density function $f$ and define ${\rho }_f$ as:

Moreover, assume $f$ has bounded support $[a,b]$, that is, $f(x)=0$ for all $x\notin [a,b]$. This can be a reasonable assumption in many practical applications [22, 23] where there are known bounds to the values of data: for instance, for storing medical information such as test results, or personal financial information. Our results can be extended to the case of $f$ with unbounded support, by incurring a penalty on space usage. In Section 4.3.3 we show how this penalty relates to the tails of the probability distribution.

The main complexity results are stated in Theorems 1 and 2. Both are attained by the ESPC index, which we introduce in Section 3.2. Both theorems as stated here assume that the query parameter follows the same probability distribution as the keys. This is done for ease of presentation. In Section 4.3.2 we prove that these results can be generalized to include the case when that assumption does not hold.

We prove Theorems 1 and 2 in Section 4.3.1, as corollaries of a more general result.

All complexity results in Section 3.1 are achieved by the Equal-Split Piecewise Constant (ESPC) index, which we now describe. As explained in Section 1, learned indexes usually combine predictive and corrective steps. The ESPC index follows this idea, and is remarkably simple to define and implement. It is important to mention that a similar design, the PCA Index, was analyzed in [34], but the complexity bounds we prove for this type of index are tighter and more general. Moreover, there are some design differences. First, the ESPC index uses exponential search for the corrective step, while the PCA Index uses binary search. More importantly, the PCA Index presumes knowledge of the interval $[a,b]$ where the distribution is supported, a potentially restrictive assumption that we dispense with for the ESPC index.

The general idea is to learn a function $\widehat{𝐫}$ to approximate the $\mathrm{𝐫𝐚𝐧𝐤}$ function up to some error. Then $\mathrm{𝐫𝐚𝐧𝐤}$ can be computed exactly by first evaluating $\widehat{𝐫}$ and then correcting the error by use of an exponential search algorithm [2]. If the prediction error is small, this gives a procedure for computing $\mathrm{𝐫𝐚𝐧𝐤}$ exactly in low expected time. The approximator function $\widehat{𝐫}$ is built as a piecewise constant function defined over equal-length subintervals. This equal-length property ensures that $\widehat{𝐫}$ can be evaluated in constant time.

We now describe how the approximator $\widehat{𝐫}$ is defined. Take an array $A$ formed by the sorted keys $X_{(1)},\mathrm{\dots },X_{(n)}$. For a positive integer $K$, divide the range $[X_{(1)},X_{(n)}]$ into $K$ subintervals of equal length, which we denote by ${\{I_k\}}_{k=1}^K$. Figure 2 illustrates this type of partition for a dataset with 40 keys and $K=4$. Formally, for each $k=1,\mathrm{\dots },K$ the $k$-th subinterval is defined as $I_k=[t_{k-1},t_k]$ where

Notice that all intervals have the same length, but not necessarily the same number of keys. Now, we want $\widehat{𝐫}$ to be defined as a piecewise constant function. If $q\in ℝ$ does not belong to any $I_k$, this means that either or $q>X_{(n)}$, so that $\mathrm{𝐫𝐚𝐧𝐤}(q)=0$ or $\mathrm{𝐫𝐚𝐧𝐤}(q)=n$, respectively. On the other hand, for each subinterval $I_k$ the ESPC index stores a constant value ${\widehat{r}}_k$ which approximates $\mathrm{𝐫𝐚𝐧𝐤}$ over $I_k$. Combining these ideas, we define $\widehat{𝐫}$ as

Figure 2 represents this type of piecewise approximator over equal-length subintervals. It remains to define the ${\{{\widehat{r}}_k\}}_{k=1}^K$ values. Since $\mathrm{𝐫𝐚𝐧𝐤}$ is an increasing function, for all $q\in I_k$ it holds $\mathrm{𝐫𝐚𝐧𝐤}(t_{k-1})\le \mathrm{𝐫𝐚𝐧𝐤}(q)\le \mathrm{𝐫𝐚𝐧𝐤}(t_k)$. This motivates a candidate for ${\widehat{r}}_k$ in the form of

where $n_k=\mathrm{𝐫𝐚𝐧𝐤}(t_k)-\mathrm{𝐫𝐚𝐧𝐤}(t_{k-1})$ is the number of keys in $I_k$. As we prove in Section 4.1, this means that ${\widehat{r}}_k$ can approximate $\mathrm{𝐫𝐚𝐧𝐤}(q)$ for any $q\in I_k$ with error at most $n_k/2$, so that the quality of $\widehat{𝐫}$ as an approximator depends on the expected number of keys per interval. Algorithm 1 details the index construction, based on our definitions for $\{I_k\}$ and $\{{\widehat{r}}_k\}$.

The approximator $\widehat{𝐫}$ can be evaluated in constant time for any $q\in ℝ$. If then $\widehat{𝐫}(q)=0$, and if $q>X_{(n)}$ then $\widehat{𝐫}(q)=n$. If neither is true, then $q$ belongs to some interval $I_k$. In that case, $\widehat{𝐫}(q)={\widehat{r}}_k$ where $k$ is given by $k=\lceil K\frac{q-X_{(1)}}{X_{(n)}-X_{(1)}}\rceil =\lceil \frac{1}{\delta }(q-X_{(1)})\rceil .$ To find $\mathrm{𝐫𝐚𝐧𝐤}(q)$ exactly, the ESPC index then performs an exponential search on array $A$ around position $\lceil \widehat{𝐫}(q)\rceil$. We prove in Section 4 that the expected value of the approximation error $|\mathrm{𝐫𝐚𝐧𝐤}(q)-\widehat{𝐫}(q)|$ is low enough to establish the results of Section 3.1. Algorithm 2 formalizes this evaluation process. It assumes the existence of a procedure ExponentialSearch$(A,i,q)$ which uses exponential search around index $i$ to find the position of $q$ in array $A$.

We now turn to an analysis of the space and time complexity of the ESPC index. In the following, assume the sorted array $A$ has $n$ elements and the index is built with $K$ subintervals ${\{I_k\}}_{k=1}^K$. As seen from Algorithm 1, an ESPC index can be represented as a tuple $R=(r,\delta )$ where $r$ is an array of length $K$ storing the approximators ${\{{\widehat{r}}_k\}}_{k=1}^K$ and $\delta$ is the length of the subintervals. For $q\in ℝ$ recall that $\widehat{𝐫}(q)$ is the approximation for $\mathrm{𝐫𝐚𝐧𝐤}(q)$ before the exponential search (see Algorithm 2).

In the RAM model with the uniform cost criterion, each stored value uses $1$ unit of space. Hence, the space used to store an ESPC index $R=(r,\delta )$ is $O(K)$. Additionally, as seen from Algorithm 2, the evaluation for any $q\in ℝ$ takes constant time, plus the exponential search. An exponential search takes time $O(2\log \epsilon )=O(\log \epsilon )$ [2], where $\epsilon$ is the difference between the starting position and the correct position. This is summarized in the following result.

In light of Proposition 3, a way to estimate the time complexity of the ESPC index is to bound the expected value of $\epsilon$ as a function of $K$. Hence, our focus is on finding an expression for the approximation error $\epsilon =|\mathrm{𝐫𝐚𝐧𝐤}(q)-\widehat{𝐫}(q)|$. We start with the following result, which was mentioned in passing in Section 3.2.

The proof is straightforward and can be found in the extended version of the paper [6]. We now introduce other necessary notation. First, notice that if $f$ has bounded support $[a,b]$, then $[X_{(1)},X_{(n)}]\subseteq [a,b]$ holds with probability $1$. Now, for a given $K$ we can define a set of subintervals ${\{J_k\}}_{k=1}^K$ that partition the interval $[a,b]$ into $K$ equal-length parts, similarly to how the ${\{I_k\}}_{k=1}^K$ form a partition of $[X_{(1)},X_{(n)}]$. See Figure 3 for an illustration with $K=3$.

From this definition, it may be the case that some $I_k$ is not entirely contained within just one $J_k$ interval, as Figure 3 illustrates for the case of $I_2$. Notice however that if this happens, then $I_k$ must be contained in the union of two consecutive $J_k$ intervals, as exemplified by $I_2\subseteq J_1\cup J_2$ in Figure 3. We formalize this observation below, which is easily verified.

Recapping, by Proposition 3 the ESPC index time complexity for input $q$ depends on the approximation error $\epsilon =|\mathrm{𝐫𝐚𝐧𝐤}(q)-\widehat{𝐫}(q)|$. By Lemma 4, the error $\epsilon$ critically depends on the number of keys in the subintervals $\{I_k\}$. We now state and prove the key results which provide bounds for the approximation error. As mentioned in Section 3.1, we assume that the density $f$ has bounded support $[a,b]$ for some $a,b\in ℝ$. That is, $f(x)=0$ for any $x\notin [a,b]$. Our results can be extended to the case of $f$ with unbounded support by incurring a penalty in terms of space complexity. Notice that the $\{J_k\}$ implicitly define a random variable, which models how the ${\{X_i\}}_{i=1}^n$ are distributed among the subintervals. This can be characterized by a parameter $(p_1,\mathrm{\dots },p_K)$ where $p_k=\mathbb{P}(X_i\in J_k)$. Notice that $p_k$ is not indexed by $i$ because all $X_i$ follow the same distribution. In this context, the core of the time complexity analysis is contained in the following theorem.

We now use Theorem 6 to prove the results stated in Section 3.1. For this, we need to relate the error bound in Theorem 6 with ${\rho }_f={\parallel f\parallel }_2^2$. For this, notice that

where $|J_k|$ denotes the length of interval $J_k$ and we have used Cauchy-Schwarz inequality to bound ${\left({\int }_{J_k}f(x)𝑑x\right)}^2$. Substituting this in the error bound from Theorem 6 and using the fact that $|J_k|=(b-a)/K$ for all $k$, we obtain

We can summarize the main error bound for the ESPC index in the following proposition.

The complexity results from Section 3.1 are proved in Section 4.3.1 as corollaries of Proposition 7. In Sections 4.3.2 and 4.3.3 we discuss two important generalizations of our results. In Section 5, we present further analysis and a comparison to previous results.

The term $\log \left({\sum }_{k=1}^K{p}_k^2\right)$ is related to a notion of entropy and is minimized when $(p_1,\mathrm{\dots },p_K)$ is a uniform distribution (see Section 5.2). Hence, we could conceivably get better performance by trying to induce $p_k=1/K$ for all $k$. Consider then an alternative design where the $\{I_k\}$ subintervals are defined in such a way that they cover the $[a,b]$ range (instead of the $[X_{(1)},X_{(n)}]$ range) and we aim to enforce $p_k=1/K$ for all $k$, rather than an equal-length condition. This requires knowledge of $a$, $b$, and $F$, which we usually lack, but several strategies can be explored to estimate them from the data.

This new index design would refine the intervals where we expect data to be more concentrated, which seems to be a reasonable strategy. However, there is a trade-off. Choosing the subintervals so that $p_k=1/K$ means that they will not be equal-length, unless the $\{X_i\}$ distribute uniformly. Consequently, for a given query parameter $q$, we can no longer find its subinterval in constant time, as we did before with $k\leftarrow \lceil \frac{1}{\delta }\left(q-X_{(1)}\right)\rceil$. This version of the index would need a new strategy to find the relevant subinterval $I_k$ such that $q\in I_k$.

A standard strategy would be to create a new array $A^{\prime }$ formed by the left endpoints of the $\{I_k\}$, that is, $A^{\prime }=[t_0,\mathrm{\dots },t_{k-1}]$. Now, for a given search parameter $q$ we can find the relevant $I_k$ with $k={\mathrm{𝐫𝐚𝐧𝐤}}_{A^{\prime }}(q)$, and then proceed with steps (2) and (2) from Algorithm 2. Notice that the index is now hierarchical, with $A^{\prime }$ at the top and $A$ (segmented into the $\{I_k\}$) at the bottom. From equation (6), expected time at the bottom layer would scale as

On the other hand, the top layer has $K$ keys $\{t_0,\mathrm{\dots },t_{k-1}\}$. Since the index is designed so that $p_k=1/K$, this means $F(t_i)=i/k$. As a consequence, the keys in $A^{\prime }$ approximately follow distribution $F$, with a better approximation as $K\to \mathrm{\infty }$. Suppose we use an ESPC index with $K^{\prime }$ subintervals to speed up computation of ${\mathrm{𝐫𝐚𝐧𝐤}}_{A^{\prime }}$. By Proposition 7 the expected time at the top layer will be dominated by $𝔼\left[\log {\epsilon }_{\text{top}}\right]\le \log \left(3(b-a){\rho }_{f}K/(2K^{\prime })\right)$ and the total expected time can be bounded as

Notice that $(b-a){\rho }_f$ is still present in this bound. Now, for instance, with $K=K^{\prime }=n$ we get twice the space usage compared to Theorem 1 and the same asymptotic expected query time. This indicates that asymptotic complexity remains the same for a hierarchical or tree-like version of the index, so the basic ESPC index gives a simpler proof for our results.