Towards Establishing Guaranteed Error for Learned Database Operations

We thank the reviewer for the comments. We have updated the paper based on the reviewers’ comments, and changes are marked in blue in the updated file.

R4Q1/W1. Regarding the error metric for learned indexing, we are unsure what the reviewer means by “maintaining delta”. The typical practice in learned indexing is to do binary (or exponential) search (Kraska et al., 2018; Ferragina & Vinciguerra, 2020; Ding et al., 2020) from the final estimate on the sorted array to find the exact answer, in which case, as R3Q3 mentions one may be interested in the $\log_2$ error of the model (which is the runtime of this binary search step). We have added a discussion to the newly added Appendix A showing how our bounds can be translated to log2 error, as discussed next. Ideally, to ensure $\log_2$ error is at most an error parameter $\tau$, setting $\epsilon=2^\tau$ in our bounds would provide the required model size given the $\log_2$ error $\tau$. This is true when considering worst-case error (i.e., Theorem 1) and in our upper-bounds on the required model size when considering average case error (i.e., Theorem 4, Lemma 2 and part (ii) of Theorems 2,3,5). That is, our bounds on the mentioned results simply translate to bounds for $\log_2$ error by replacing $\epsilon$ with $2^\tau$. However, this is not true in the case of lower bounds for average error, (i.e., Corollary 1 and part (i) of Theorems 2,3,5) and the required model size can be smaller than what the results would suggest if we set $\epsilon=2^\tau$. We leave study of the log2 error in these cases to future work, although we expect similar proof techniques that were used in this paper to be applicable to that case as well.

Regarding the error for cardinality estimation, although q-error is a useful metric for the evaluation of cardinality estimators, worst-case guarantees on absolute error can provide more meaningful guarantees on the performance of a system. For example, Negi et al. 2021 show that a cardinality estimator that achieves a worst-case q-error of 4100 can lead to a similar runtime as another method with a worst-case q-error of 100. Indeed a worst-case bound on q-error is a worse indicator of the system’s performance compared with a worst-case bound on absolute error. For instance, the q-error of 4100 can correspond to a query with true cardinality 4100 and estimated cardinality 1 (in which case one needs to read an extra 4100 items from disk, which will take little resources, both computation and memory wise) while the error can also correspond to an estimate of 1,000,000 for a query whose true cardinality is 4,100,000,000 (in which case one needs to read an extra 4 billion records, a huge computation and memory cost). On the other hand, the absolute error in those two cases will respectively be 4,399 and 4,099,000,000 a much better indicator of the extra computation caused by the error of the cardinality estimator. Overall, a worst-case bound on absolute error can readily translate to performance metrics (e.g., worst-case memory consumption and number of disk accesses), while worse-case q-error in itself is not informative.

Finally, note that cardinality estimation is not just used for query optimization, and has use-cases in approximate query processing (similar to range-sum estimation), where the goal is to return to the user an estimated query answer (e.g., for the query of how many people are in an area), which is common in analytical applications. In such settings, the absolute error is useful as it provides a bound on what the true query answer can be, and is often directly shown to the user as error bars.

We thank the reviewer for the comments. We have updated the paper based on the reviewers’ comments, and major changes are marked in blue in the updated file.

R3, Response to comment “ it is not clear to me how these bounds could be used in systems … error bounds at the specified size. “. Please see our response to R2Q2 and R4Q3 regarding practical use cases of our bounds.

R3Q1-2. We have added a new subsection to Appendix B, further discussing the intuition behind our proofs which we present here. As, the reviewer observed, given that there are $2^\sigma$ possible bitstrings (for model size $\sigma$), multiple datasets must be mapped to the same model parameter values (that is, after training, multiple datasets will have the exact same model parameter values). To obtain a bound on the error, the proof shows that some datasets that are mapped to the same parameter values will be too different from each other (i.e., queries on the datasets have answers that are too different), so that the exact same parameter setting cannot lead to answering queries accurately for both datasets. The proofs do this by constructing $2^\sigma+1$ different datasets such that query answers differ by more than $2\epsilon$ on all the $2^\sigma+1$ datasets. Thus two of those datasets must be mapped to the same model parameter values, and the model must have an error more than $\epsilon$ on at least one of them, which completes the proof. The majority of the proofs are on how this set of $2^\sigma+1$ datasets is constructed. Specifically, the proofs construct a set of datasets, where each pair differs in some set of points $S$. The main technical challenge is constructing/showing that for any of the two datasets that differ in a set of points $S$, the maximum or average difference between the query answers is at least $2\epsilon$. This last statement is query dependent, and our technical Lemmas 3-8 in the appendix are proven to quantify the difference between query answers between the datasets based on the properties of the set $S$ and the query type. This is especially difficult in the average-case scenario, as one needs to study how the set $S$ affects all possible queries.

R3Q3. We have added a discussion to the newly added Appendix A showing how our bounds can be translated to $\log_2$ error, as discussed next. Ideally, to ensure $\log_2$ error is at most an error parameter $\tau$, setting $\epsilon=2^\tau$ in our bounds would provide the required model size given the $\log_2$ error $\tau$. This is true when considering worst-case error (i.e., Theorem 1) and in our upper bounds on the required model size when considering average case error (i.e., Theorem 4, Lemma 2 and part (ii) of Theorems 2,3,5). That is, our bounds on the mentioned results simply translate to bounds for $\log_2$ error by replacing $\epsilon$ with $2^\tau$. However, this is not true in the case of lower bounds for average error, (i.e., Corollary 1 and part (i) of Theorems 2,3,5) and the required model size can be smaller than what the results would suggest if we set $\epsilon=2^\tau$. We leave the study of the $\log_2$ error in these cases to future work, although we expect similar proof techniques that were used in this paper to be applicable to that case as well.

We thank the reviewer for the comments. We have updated the paper based on the reviewers’ comments, and major changes are marked in blue in the updated file.

R2W1/Q1: The reviewer has correctly pointed out that our results on cardinality and range-sum estimation only apply to axis-parallel range queries for numerical data (which is a very common setting, e.g., Kipf et al., 2018; Ma & Triantafillou, 2019; Zeighami et al. 2023). We have modified the introduction to specify this earlier on. We have also added Sec. A to the appendix to discuss various other considerations not addressed in the paper, such as cardinality estimation for joins, other aggregation functions and other error metrics.

R2W2/Q2: We have added a new paragraph to the introduction further clarifying the implication of our results, as discussed next. There are two important predictive statements made by our theorems, following two interpretations of our theorems. First, our results provide a lower bound on the worst-case error given a model size (this view is presented in our experiments). This shows what error is achievable by a model of a certain size. Our experiments illustrate that our bound on error is meaningful, showing that models achieve error values close to what the bound suggests. Second, our results provide a lower bound on the required model size to achieve the desired accuracy level across datasets. This has important implications for resource management in database systems. For instance, this helps a cloud service provider decide how much resources it needs to allocate (and calculate the cost) for the learned model to be able to guarantee an accuracy level. Moreover, our bound provides the first theoretical guideline on how the model size should be set in practice to be able to guarantee a desired accuracy level.

Moreover, based on the reviewer’s suggestions, we have added random sampling as a baseline in Figure 1. The figure shows that sampling performs worse than learned models for uniform distribution while it performs similarly for GMMs (Sample should be compared with Linear as they both have the same size). We note that although presenting results for sampling in our experiments provides more context to our empirical study, the goal of our experiments is not a detailed empirical evaluation of different modeling choices, and we refer the reviewer to the related work (e.g., Kipf et al., 2018; Zeighami et al. 2023) for such a comparison. The goal of our experiments is to show our theoretical bounds are meaningful, showing that existing modeling choices achieve similar error values as our bound suggests. We also note that our theoretical bounds suggest (discussed in Sec. 5 and also in our response to R2W3) that the gap between learned models and sampling will grow as dimensionality increases (we use one-dimensional datasets in our experiments).

R2W3/Q3. We thank the reviewer for pointing out the related work and the interesting connection between our results and non-learned data models. We have updated the related work section based on the reviewer’s suggestion. Please see the newly added paragraph in the related work section for a detailed answer to the reviewer’s question. To summarize, the newly added paragraph includes a discussion of theoretical results in the related non-learned literature (such as $\epsilon$-approximation, sampling and use of VC dimensionality, non-learned data summaries). We specifically compare our bounds with bounds on $\epsilon$-approximations, showing that $\epsilon$-approximations (which include random sampling) have a worse lower bound compared with our theorems in high dimensions. This shows that random sampling (and other $\epsilon$-approximations) can be a much worse data model in terms of space efficiency compared with other modeling choices in high dimensions.

We thank the reviewer for the comments. We have updated the paper based on the reviewers’ comments, and major changes are marked in blue in the updated file.

R1W1. We have added a paragraph in the newly added Appendix A discussing how our results may apply to joins as follows. A naive extension of our bounds to the cardinality estimation for joins is to apply the bound to the join of tables. That is, if two tables have respectively $d_1$ and $d_2$ dimensions and if their join consists of $n_J$ elements, then we can apply our bounds in Table 1 with $d=d_1+d_2$ and $n=n_J$ to obtain a lower bound on the required model size for estimating the cardinality of the join. However, we expect such an approach to overestimate the required model size, as it does not consider the join relationship between the two tables. For instance, $n_J\times d$ may be much larger than $n_1\times d_1+n_2\times d_2$, because of duplicate records created due to the join operations. Considering the join relationship, one may be able to provide bounds that depend on the original table sizes and not the join size.

R1W2. We have added a paragraph in the newly added Appendix A that discusses providing bounds for other aggregation functions as follows. Although we expect similar proof techniques as what was used to apply to other aggregations such as min/max/avg, we note that studying worst-case bounds for min/max/avg may not be very informative. Intuitively, this is because, for such aggregations, one can create arbitrary difficult queries that require the model to memorize all the data points. For instance, consider datasets for which the $(d+1)$-th dimension, where the aggregation is applied, only takes 0 or 1 values, while the other dimensions can take any values in a domain of size $u$. Now avg/min/max for any range query will have an answer between 0 and 1 (for min/max the answer be exactly 0 or 1). However, unless the model memorizes all the points exactly (which requires a model size close to the data size), its worst-case error can be up to 0.5. This is because queries with a very small range can be constructed that match exactly one point in the database, and unless the model knows the exact value of all the points, it will not be able to provide a correct answer for all such queries. Note that the error of 0.5 is very large for avg/min/max queries, and a model that always predicts 0.5 also obtains a worst-case error 0.5. This is not the case for sum/count aggregations whose query answers range between 0 to $n$, and a model with an absolute error of 0.5 can be considered a very good model for most queries when answering sum/count queries.

To summarize, worst-case errors of min/avg/max queries are disproportionately affected by smaller ranges, while smaller ranges have a limited impact on the worst-case error of count/sum queries. As such we expect that for the case of min/max/avg queries, one needs to study the error for a special set of queries (e.g., queries with a lower bound on their range, as done in Zeighami et al. (2023), which also makes similar observations) to be able to obtain meaningful bounds. We leave such a study to future work.