Towards Establishing Guaranteed Error for Learned Database Operations
Authors: Sepanta Zeighami
Cyrus Shahabi
Venue: ICLR 2024 poster (2024)
Keywords: Learned Indexing
Learned Cardinality Estimation
Machine learning for Data Management
Primary area: learning theory
TL;DR: We present the first known bounds on the model size required when using machine learning to perform indexing, cardinality and range-sum estimation

Abstract: Machine learning models have demonstrated substantial performance enhancements over non-learned alternatives in various fundamental data management operations, including indexing (locating items in an array), cardinality estimation (estimating the number of matching records in a database), and range-sum estimation (estimating aggregate attribute values for query-matched records). However, real-world systems frequently favor less efficient non-learned methods due to their ability to offer (worst-case) error guarantees — an aspect where learned approaches often fall short. The primary objective of these guarantees is to ensure system reliability, ensuring that the chosen approach consistently delivers the desired level of accuracy across all databases. In this paper, we embark on the first theoretical study of such guarantees for learned methods, presenting the necessary conditions for such guarantees to hold when using machine learning to perform indexing, cardinality estimation and range-sum estimation. Specifically, we present the first known lower bounds on the model size required to achieve the desired accuracy for these three key database operations. Our results bound the required model size for given average and worst-case errors in performing database operations, serving as the first theoretical guidelines governing how model size must change based on data size to be able to guarantee an accuracy level. More broadly, our established guarantees pave the way for the broader adoption and integration of learned models into real-world systems.

Published as a conference paper at ICLR 2024
TOWARDS ESTABLISHING GUARANTEED ERROR FOR LEARNED DATABASE OPERATIONS
Sepanta Zeighami"
Cyrus Shahabi
UC Berkeley zei reigiami weighham@@erreer behhamibbrrreeey.ooo edu
University of Southern California shahabi Mhahabi@usc.cem @usccuucel
ABSTRACT
Machine learning models have demonstrated substantial performance enhance- ments over non-learned alternatives in various fundamental data management op- erations, including indexing (locating items in an array), cardinality estimation (estimating the number of matching records in database), and range-sum esti- mation (estimating aggregate attribute values for query-matched records). How- ever, real-world systems frequently favor less efficient non-learned methods due to their ability to offer (worst-case) error guarantees - an aspect where learned approaches often fall short. The primary objective of these guarantees is ensure system reliability, ensuring that the chosen approach consistently delivers the de- sired level of accuracy across all databases. In this paper, we embark on the first theoretical study of such guarantees for learned methods, presenting the necessary conditions for such guarantees to hold when using machine learning to perform in- dexing, cardinality estimation and range-sum estimation. Specifically, we present the first known lower bounds on the model size required to achieve the desired accuracy for these three key database operations. Our results bound the required model size for given average and worst-case errors in performing database oper- ations, serving as the first theoretical guidelines governing how model size must change based on data size to be able to guarantee an accuracy level. More broadly, our established guarantees pave the way for the broader adoption and integration of learned models into real-world systems.
INTRODUCTION
Recent empirical results show that learned models perform many fundamental database operations (e.g.. indexing, cardinality estimation) more efficiently than non-learned methods, providing signif- icant speed-ups and space savings (Galakatos et al., 2019 Kraska et al.) 2018: [Ferragina & Vin- ciguerra| 2020 /Zeigamm et al., 2023 Kipf et al.] (018)) Nevertheless, the lack of theoretical guar- antees on their performance poses a significant hurdle to their practical deployment, especially since the non-learned alternatives often provide the required theoretical guarantees (Agarwal al. [013]] Pătraşcu & Thorup [0066] Hellerstein et al. [197; Bayer & McCreight) 1970). Such guarantees are needed to ensure reliability of the learned operations across all databases deployment time, that is, to ensure consistent performance of the learned model on databases where the learned model had not been apriori evaluated. Thus, similar to existing worst-case bounds for non-learned methods, guarantee is needed that a learned operation will achieve the desired accuracy level on all possible databases. Providing such a guarantee depends on how large the learned model (e.g., number of parameters of neural network), the desired accuracy level, and the size and dimensionality of the underlying databases. This paper takes the first step towards a thcoretical understanding of the relationship between these factors for three key database operations, offering theoretical bounds the required model size to achieve a desired accuracy on all possible databases of a certain size and dimensionality when using learned models to perform the operation.
Specifically, the three operations studied in this paper are (1) indexing: finding an item in an array, (2) cardinality estimation: estimating how many records in database match a query, and (3) range- sum estimation: estimating the aggregate value of an attribute for the records that match a query. We focus on numerical datasets and consider axis-aligned range queries for cardinality and range- sum estimation (i.c., queries that ask for the intersection of ranges across dimensions). Typical
"This work completed when the author was PhD) student USC's Infolab

---

Published as a conference paper at ICLR 2024
Database
Worst-Case Error
Average-Case Error (Uniform Dist.)
Average- Case Error
Operation
(Arbitrary Dist.)
log(1
(vn-2) 2) log ( THEOREM
(Vii 2) log(1 26
Indexing
2c+1
n
2
THEOREM
THERBEM
Cardinality
(2c 1)a log(1
(Vn- 2) log(1 +
Vn 11 2
X LEMMA
Estimation
2c+1
76
V
THEOREM
THEOREM
Range-Sum Estimation
log(1 + (2c+1)a (Vn l)g + 4 )
X LEMMA
2c+1
n
THEOREM
COROLLARY
Our bounds on required model size in terms of data size, n, dimensionality, d, tolerable error, 6, and domain size, u. Each column shows the result when e the tolerable error for the specified error scenario. X: No non-trivial bound possible. Base of log is 2.
Table I:
learned approaches to the above database operations take a function approximation view of the operations. Let f(4) be a function that takes a query, q. as an input, and outputs the answer to the query calculated from the database. For instance, in the case of cardinality estimation, f(() will be the number of records in the dataset that match the query q (and [4) can be similarly defined for indexing and range-sum estimation). At training time, a model, f(z; 0) (e.g., a neural network) is trained to approximate f. Training is done using supervised learning, where training labels are collected for different queries by performing the queries on the database using an existing method (e.g., for cardinality estimation, by iterating over the database and counting how many records match a query). At test time, the models are used to obtain estimates directly (c.g., by performing a forward pass of a neural network), providing f(g 0) as estimate to the answer where the exact location of the query in the array is needed (not an estimated location returned by the model), local search around the model estimate is performed to find the exact answer.
query q. For indexing,
Such learned approaches are currently state-of-the-art, with experimental results showing signifi- cantly faster query time and lower storage space when using learned methods compared with non- learned methods for indexing (Kraska et al. 2018 Ferragina & Vinciguerra) 2020 Ding et al.) 2020). cardinality estimation (Kipf al.] 2018 Negi et al. (023) and range-sum estimation ZZighami
jet al. 2023). Furthermore, recent results also show theoretical advantages to using learned models
(Zeighami & Shahabi 2023 Ferragina et al.] 2020 Zeighami et al.) 2023), most significantly, with
Zeighami & Shahabi 2023) showing the existence of a learned index that can achieve expected
query time of Olog log n) under mild assumptions on the data distribution, asymptotically bet- ter than the traditional Ollog of non-learned methods such as binary search. However, there has been no theoretical understanding of the required modeling choices, such as the required model size, for the learned approaches to provide an error guarantee across databases. Without any theoretical guidelines, design choices are made through empirical hyperparameter tuning, leading to choices with unknown performance guarantees at deployment time.
1.1 OUR RESULTS
In this paper, we present the first known bounds on the model size needed to achieve a desired accuracy when using machine learning to perform indexing, cardinality estimation and range-sum estimation. We provide bounds on the required model size, defined as the smallest possible size for a model to achieve error at most c on all d-dimensional datasets of size n. We measure model size in terms of number of bits required to store model (which translates to the number of model param- eters by considering the storage precision for the parameters). We refer to e as the tolerable error parameter, which denotes the maximum error that can be tolerated in the system. We thoroughly study the required model size in two different scenarios, namely when considering the worst-case and average-case error. That is, e can be provided in terms of worst-case or average-case error across queries that can be tolerated for all databases (i.c., worst-case across databases). [abberruummaize our main results, which we further discuss considering the two error scenarios in turn.
First, suppose our goal is to answer all possible queries with error at most across all d-dimensional datasets of size n. The results in the second column of Table []] summarizing our Theorem [ in Sec provide lower bound on the required model size to achieve this. For example, for indexing, to be able to guarantee error at most on all possible queries and datasets of size n, one must use a x model whose size exceeds 2 log(1 + (2++-1)x, Notably, the bounds depend on the domain size u, which is the number of possible values the records in the database can take, implicitly assuming finite data domain. We show in Lemma 1 in Sec. 3.1 that this is necessary: model with finite
2

---

Published as a conference paper at ICLR 2024
size answer queries with bounded worst-case error on all possible datasets with infinite domain (this result is mostly of theoretical interest, since data stored in a computer always has finite domain).
In the second scenario, our goal is to answer queries with average enror of at most on all d- dimensional datasets of size n. Assuming the queries are uniformly distributed, the third column in Table [ summarizing Theorem 2 3 and Corollary [ in Sec. 3.2 presents our lower bounds on the required model size. Our bounds in this scenario show a weaker dependency on data size and tolerable error parameter compared with the worst-case error scenario, and as expected, suggest smaller required model size. Interestingly. bounds do not depend on the domain size and hold when the data domain is the set of real numbers, showing a significant difference between model size requirements when considering the two scenarios. Thus, our results formally show that robustness guarantees (i.e., guarantees on worst-case error) must come at the expense of larger model sizes.
Furthermore, the results in the last column of Table summarizing our Theorem 5 Jnd Lemma 2 in Sec. S.c.3.3 show that we can extend our results to arbitrary query distribution (compared with uniform distribution) in the case of indexing without affecting the bounds. However, for cardinality and range-sum estimation, we show in Lemma 2 that when relaxing our assumption on data distribution, one can construct arbitrarily easy distribution to answer queries from, so that no non-trivial lower bound on the model size can be obtained (surprisingly, this is not possible for learned indexing).
Finally, not presented in Table I for average-case error, we complement our lower bounds on the required model size with corresponding upper bounds, showing tightness of our results. Theorem 5 show that our lower bounds are tight up to O(yn) factor, asymptotically in data size.
1.2 DISCUSSION
In practice, model size is often set in practice to a fixed value or through hyperparamter tuning LLu al. 2021 Kraska et al., 2018 Kipf et al.) 2018 Zeighami et al., (203)) without taking data size into account Our results show that model size indeed needs to depend on data size to be able to guarantee any fixed error. More specifically, for practical purposes, our results can be interpreted in two ways. In the first interpretation, given a model size and data size, our results provide lower bound on the worst-case possible error. This bound shows what error can be guaranteed by a model of a certain size (and how bad the model can get) after it is deployed in practice. This is important, because datasets change in practice and our bound on error help quantify if a model of a given size can guarantee desired accuracy level when the dataset changes. Experiments in Sec. dec.ffillustratt that this bound on error is mcaningful, showing that models achieve error values close to what the bound suggests. In the second interpretation, our results provide lower bound the required model size to achieve a desired accuracy level across datasets. This shows how large the model needs to be, guarantee the desired accuracy, and has significant implications for resource management in database systems. For instance, it helps a cloud service provider decide how much resources it needs to allocate for models be able to guarantee an accuracy level across all its database instances.
Overall, our results are information theoretic, showing that it is not possible for any model to con- tain enough information answer queries on all datasets accurately if they contain less than the specified number of bits. The bounds are obtained by considering the parameters of model as a data representation, and showing bounds on the required size of any data representation to achieve a desired accuracy when performing the specific operations. Our proofs provide novel exploration of the function approximation view of database operations, connecting combinatorial properties of datasets with function approximation concepts. Specifically, we prove novel bounds packing and metric entropy of the metric space of database query functions to prove the bounds, which are particularly challenging to obtain for the average-case error. In Sec we discuss various possible extensions of our results to queries with joins, other aggregation function such as min/max/avg. and other error metrics not considered in this paper.
2 PRELIMINARIES
Setup. We are given a dataset, D E D i.e., a dataset consisting of n records and in d dimensions with each attribute in the data domain D, where n and d are integers greater than or equal to 1. Unless otherwise stated, we assume D [0, 1] so that D [0, 1 1 (attributes can be scaled to [o, 1] if they fall outside the range). We use D; to refer to the i-th record of the dataset (which is a d- dimensional vector) and Dr,, to refer to the j-th element of D,. If d = 1 (i.e., D is 1-dimensional), then D; is the i-th element of D (and is not a vector). We study the following database operations.
At least explicitly, as hyperparameter tuning can implicitly account for data size
3

---

Published as a conference paper at ICLR 2024
Indexing. The goal is to find an item in a sorted array. Formally, consider I 1-dimensional sorted dataset D (i.e., a sorted 1-dimensional array). Given a query q E [0, 1], return the index i" = Di= Ip..g where I is the indicator function. 1" is the index of the largest element no greater than q and is 0 if no such element exists. Furthermore, if q E D. q will be at index i" + 1. i* is referred to as the rank of q. Define the rank function of the dataset D as r (q) = Dim /D which takes a query as an input and outputs its rank. We have Q. = [0, 1] as the domain of the rank function.
Cardinality Estimation. Used mainly for query optimization, the goal is find how many records in the dataset match a range query, where the query specifies lower and upper bound conditions on the values of each attribute. Formally, consider a d-dimensional dataset. A query predicate (cI..., Cd. 71, ..... Td), specifics the condition that the i-th attribute is in the interval (Cs, C + r.].
Define Ip.g as an indicator function equal to one a d-dimensional point p = (p1, Pa) matches a query predicate
(C1,.... ..... Cd. Fl,.....'a) r'd), that is, if cz S S ej + rr Vj E [d] ([k] is defined as
[k] = (1.... }) for integers k). Then, the answer to a cardinality estimation query is the number of
points in D that match the query q. i.e., (g = Exj ID..q. We refer to ep as the cardinality
function of the dataset D, which take query as input and outputs the cardinality of the query. We define Qe = fr, E 1], E [-r3. 1 - ryl. j E [d]] where the definition ensures ej + ry E [0. to avoid asking queries outside of the data domain.
Range-Sum Estimation. The goal is to calculate the aggregate value of an attribute for the records that match query. Formally, consider a (d + 1)-dimensional dataset D and a query where q. similar to the case of cardinality estimation, defines lower
va), Ya), and upper bounds on the data points. The goal is to return the total value of the (d + 1)-th attributes of the points in D that match the query q. i..., sp(g) = Eve(n Did41. Here, for simplicity, we overload the notation and use Ip.q. when the dimensionality of the query and predicate doesn't 't match to be defined as Cj S Pj S Cg. + r,, Vj. E [min d') }), where is dimensionality of the point p and d' is the dimensionality of the predicate q. sD is called the range-sum function of the dataset D, which takes a query as an input and outputs the range-sum of the query. We define the range-sum function domain Q. to be the same as Qe.
(CI,..,, Cd, 11 ...,,...
We use the term query function to collectively refer to the rank, cardinality and range-sum functions, and use the notation fo E {TD, S7,,DD. ) to refer to all the three functions, TD. cD and sD (for instance, fD 2 0 is equivalent to the three independent statements that TD 2 O, cD 2 0 and D if it is clear from context and simply use f(g). We also use Qy to refer to Q.. Qe and Q, for f E (r, s]..
sD 2 0). We drop the dependence
For cardinality and range-sum estimation, often only an estimate of the query result is needed, because many applications (e.g., query optimization and data analytics) prefer a fast estimate over slow but exact answer. For indexing. although exact answers are needed to locate an element in an array, one can do so through approximation. First, an estimate of the rank function is obtained, and then, a local search of the array around the provided estimate (c.g., using exponential or binary search) leads to the exact result. Thus, in all cases, approximating the query function with desired accuracy is the main component in answering the query, which is the focus of the rest of this paper.
Learned Database Operations. Learned database operations use machine learning to approximate the database operations as follows. First, during training, a function approximator, f(:: 0) is learned to approximate the function f, for f E {r, s, c). This is typically done through supervised learning (although unsupervised approaches are also possible), where for different queries sampled from Q,,, the operations are performed on the database to find the ground-truth answer, and the models are optimized through a mean squared loss. Subsequently, at test time, for a test query q. f(q: 0) is used as an estimate of the query answer, which is obtained by performing forward pass of the model. In practice, models used have a much fewer number of parameters than the data size, so that the models don't memorize the data but rather utilize patterns in query answers to perform the operations, leading to the practical gains in query answering.
This procedure can be formally specified as follows (both for supervised and unsupervised ap- proaches). First, function p(D), takes the dataset as an input and generates model parameters 0 (e.g., through training with gradient descent). Then, to answer a query q at test time, the func- tion f(q; 0) takes both the model parameters and the query as input and provides the final query answer (i.e., f specifies the model forward pass). From this perspective, the model parameters is
4

---

Published as a conference paper at ICLR 2024
representation of the dataset D and the function f only uses this representation answer queries, without accessing the data itself. We call p the training function and f the inference finctiin..
The Model Size Problem. An important question how large the model needs to be to be able to datasets of size We quantify the model size in terms of the number of
achieve eπror at most bits needed to store the parameters 0. The required model size is formalized as below.
Definition (Required Model Size). Let f E (r,c,s) and consider an error norm [|ll functions approximating J. and data domain D. Let Fo be the set of all possible training and inference function pairs, where the training function generates a parameter set of size at most size a bits. Let E be the smallest a so that there exists (p: f) E Fo such that (I P(D) foll S for all D E Daxd_ We call E the required model size achieve |I-I|-error of at most in the worst-case across all d-dimensional datasets of size n.
E is the size of the parameter set passed from the training function to the inference function. Thus, in the above formulation, the training/inference functions can be arbitrarily complex. The goal of this paper is to present lower bounds on Σ in terms of and e, and depending on the error norm ||-Il- which is an important factor impacting the lower bounds. One expects that larger models are needed the worst-case error over all queries is considered, compared with the average error. Specifically, for f E fr, 8, c), we consider the 1 n-norm error of approximating ff with f as f fff = -Q, 1f 1f-fl, the co-norm error as |l. flls- = , [f(g) - f()) and the y--ormm |lf fllp = Say ff-fldy where y is probability measure over Qy- oc-norm is also called the worst-case error and j--nor error is referred to as the average error with arbitrarily distributed queries and 1-norm is referred to as the average error with uniformly distributed queries (note that the volume of query space is I for all the function domains, so that I-norm indeed corresponds to uniform distribution).
LOWER BOUNDS ON MODEL SIZE FOR DATABASE OPERATIONS
We present lower bounds on the required model size to be able provide worst-case and average- case eтrоr guarantees. For all cases, our results provide lower bounds for achieving eπror e on all datasets. In other words, we show that if the model size smaller than specific threshold, then there exists a dataset such that the error is larger than c. As such, our bounds consider the worst- case error across datasets, while considering either average or worst-case error across queries. We first present results considering the worst-case error in Sec. 3.1] then present results considering average-case error in Secs. 3.2 and 3.3 for uniform and arbitrary query distributions, respectively. Proof of our results are presented in Sec. B
3.1 BOUNDS CONSIDERING WORST- CASE ERROR
We present our results when considering the worst-case error, or co-norm in approximation.
First, for the purpose of the following theorem, suppose the datasets are discretized at the unit 1 that is datasets are from the set D, = { u E [u]]axd (this reduces the data domain from the set of real numbers in [0, 1] to multiples of ] in [O. IJ). Define Σ, for E {r,, C, 8). the required model size to answer queries to oc-norm error at most e for all datasets in D,, For instance, D is the smallest possible model size to be able to approximate rank function with co-norm at most 6 on all possible datasets from the data domain D.,
Theorem 1. For any error 1 <<<
(i) For the case of learned indexing, we have that Σ 2
Ze+I log(1 + (2c+1)uu
m
(it) For the case of learned cardinality estimation, have that D > 2ct1 log( (2++1) and
(ii) For the case of learned range-sum estimation, we have that Σg
log(1 1
(2c+1)
I
The theorem provides lower bounds the required model size to be able to perform database operations with a desired accuracy. For instance, for the case of learned indexing, the thcorem states that the model size must be larger than ž log(1 + [2c+1ju to be able to guarantee oc-nrmm error e on all datasets, or alternatively, that if the model size is less than य log(1 + [2e+1la, ), then for "
any model approximating the rank function, there exists a database where the model's 's oommomm error more than We see that the required model size is close to linearly dependent on data size and
5

---

Published as a conference paper at ICLR 2024
dimensionalityy, while inversely correlated with the tolerable error paramter. Besides dependence on data size, dimensionality and error, the bound shows dependence on u, the domain size. An interesting question, then, is whether similar bounds on model size will hold if the data domain is not finite. The next lemma shows that the answer is no.
Lemma 1. When < z/z and the data domain D = [0, 11, for any finite size o, and any training/inference function pair f) E Fa. there exists dataset D E [0, such that -rlll -FDlll
We remark that Lemma I may not be surprising. Storing real numbers requires infinitely many bits, and, although we are interested in the size the model required to answer queries (and not the space required to store the data), one might expect the model size should be similar to the space required to store that data. Samma[]shore perhaps more surprisingly, the remainder of our results in the next sections show this is not true when considering the average-case error. As such, we consider the case where D E [0, 1jaxd for the remainder of this paper.
this to be true in the case worst-case error. However,
3.2 BOUNDS CONSIDERING AVERAGE- CASE ERROR WITH UNIFORM DISTRIBUTION
In this section, our results provide the average-case error assuming uniform data distribution, or 1-norm approximation error. Average-case error corresponds with the expected performance of the system, another important measure needed for real-world deployments. A bound on 1-norm error across all possible databases provides performance guarantee for all possible databases. Our results in this section show how large the model needs to be to provide such guarantees.
3.2.1 LEARNED INDEXING
We first present our result showing a lower bound on the required model size for learned indexing. Theorem 2. Let Σ be the required model size to achieve I-norm error of at most e on datasets of size n when approximating the rank function.
(i) For any 0 <<< < v/ we have that Σ 2 (yn 2) log(1 (1 + 1 ).
(ii) For any < c S n, we have that Σ 4 n log (e
5.
Part (i) of the theorem states that, if model whose size is less than (VT- 2) log(1 + 2e ) bits is used to approximate the rank function, then there will exist dataset of size n for which the model results in eтror larger than As expected, the required model size increases both as data size increases, and as error threshold decreases. Furthermore, for a constant error the results shows that the require model size is S2( (V)n,, providing the first known results showing the increase of model size with data size has to be at least in the order of /n.
Part (ii) of the theorem shows that the asymptotic dependence on in the lower bound is tight up to a /n factor and to achieve a desired accuracy, model size does not need increase more than linearly in data size. Overall, Theorem 2 shows that for constant error, ΣJ is (2(r)) and ((n). The proof of part (ii) constructs a model that achieves the bound. The model can be seen as a nearest neighbor encoder, modeling a dataset based on its nearest neighbor in constructed set of datasets.
Observe that this, and the rest our results considering average case error do not depend on the domain size (as Theorem did). Thus. a fundamental difference between answering queries accu- rately in the worst case, compared with average case is that in the first scenario the lower bounds depend the discritization unit, while in the second scenario, model size does not depend the discretization unit (i.e., Theorems 2 4). Furthermore, our results show that the lower bound in the case of the worst-case with when average error is considered.
has stronger dependence the tolerable error parameter, compared
3.2.2 LEARNED CARDINALITY ESTIMATION
Next, we present analog of Theorem 2 for the case of cardinality estiamtion.
Theorem 3. Let Σl be the required model size to achieve 1-norm error at most on d-dimensional datasets of size n when upproximating the cardinality function.
(i) For any
S
fa 4 we have that Σl 2 (Vn 2) log((1
+
Vnl
(ii) For any S n, we have that Σ} < n log( n
+ e .)
ca

---

Published as a conference paper at ICLR 2024
The above theorem shows that, in the case of cardinality estimation, bounds of a similar form to the case of indexing hold, however, the bounds now also depend on data dimensionality. We see that, asymptotically in data size, M is /n log( } )) and (dn log 2dm), where we see a close to lin- ear required dependency on dimensionality while there also an additional logarithmic dependency on compared with the case of indexing.
3.2.3 RANGE- SUM ESTIMATION
Finally, we extend our results to range-sum estimation. For the discussion in this section, let x be the required model size to achieve 1-norm error at most on (d + 1)-dimensional datasets of size when approximating the range-sum function. Recall that we consider d + dimensional datasets here, where query predicates apply to the first d dimensions and the query answers are the aggregation of the (d 1)-th dimension, as defined in Sec.
To prove lower bound on Σ. observe that range-sum estimation can be seen as generalization of cardinality estimation. Specifically, answering range-sum queries on d + 1-dimensional dataset, where the d + 1-th attribute of all the records is set to 1, is equivalent to answering cardinality estimation queries on the d-dimensional dataset consisting only of the first d dimensions of the original dataset. Thus, if a model with size less than 2 is able to answer range-sum queries all datasets with error at most e, then it can also answer cardinality estimation queries with error at most This means the lower bound on model size from Thoerem (i) translates to range-sum estimation as well. Thus, we have the following result as a corollary to Thoerem 3
Corollary 1. For any 0 < cs
we have that Σ 2 (Vn- - (in-2) log 1 v
14
Next, we show that an upper bound very similar to Theorem 3 (ii) on the required model size also holds for range-sum estimation.
Theorem 4. For any << e S n, we have that Σ S n log((( ( yd
ydt - +)
Observe that the upper bound on Σ! is similar to E/ but slightly larger, showing a stronger de- pendence dimensionality in the case of E!. This reflects the discussion above, that range-sum estimation is generalization of cardinality estimation. Indeed, the proof of Theorem is gener- alization of the proof of Theorem 3 (ii).
3.3 BOUNDS CONSIDERING AVERAGE- -ASE ERROR WITH ARBITRARY DISTRIBUTION
Next, diseuss extending the results in Sec. 3.2 to arbitrary query distribution. The following theorem shows that this generalization does not impact the bounds in the case of indexing, i.c., the theorem below shows that the same bounds as in Thcorem ( also hold when considering μ-norm.
Theorem 5. Let Σ/ be the required model size to achieve μ-norm error at most e on datasets of size n when approximating the rank function, for any continuous probability measure ls over [0, 1).
(i) For any 0 < S
s/ " we have that Σ₁ 2 (Vn 22) log(1
(ii) For any < S n, we have that EN S n log (e + + 9)
However, the next lemma shows that the lower bounds do not hold for arbitrary distributions in the case of cardinality and range sum estimation.
Lemma 2. For f E &c, there exists query distribution, μ. such that for any error parameter e > O, we have IlfD - fD' I for all D. E [0,1]xxd
The above lemma shows that one can construct a distribution for which the μ-norm difference be- tween all datasets is arbitrarily small. As a result, one can answer queries independently of the observed dataset, and therefore the required model size for achieving any error is 0. The proof of Lemma@ccrateer a data distribution consisting only of queries with small ranges, so that the answer to most queries is zero close to zero for any dataset. Thus, comparing Lemma 2 with Theo- rem5] [ we see that queries having both a lower and upper bound on the attributes leads to a different theoretical characteristic for cardinality and range-sum estimation compared with indexing.
4 EMPIRICAL RESULTS
We present experiments comparing our bounds with the error obtained by training different models on datasets sampled from different distributions. We train a linear model, and two neural networks with a single hidden layer where the two neural networks have 10 and 50 model parameters, re- spectively referred as NN-SI and NN-S2. Small neural networks and linear models common
7

---

Published as a conference paper at ICLR 2024
Lineur
KN-51 (b) Card. Est (Worst-Case)
NN-52 # Sample
GMM (c) Indexing Case)
Uniform
Lower Bound
(a) Indexing (Worst.Case) Case)
(d) Card, Est. (Avp-Case)
10
10
10f
Moottee Brror
Sm Btror
100
10F
10F
20
Tox
30'
Jag:
700
10
105 Data Size
10
107
10
10
105
10
107
10
10-1
10a
10
165
10
107
104
10-1
10a
10
165
10"
107
Data Size
Data Size
Data Size
Figure 1: Theoretical Bounds in Practice
modeling choices for learned database operations (Kraska et al.] 2018 Ferragina & Vinciguerra 2020 Kipt et al. 2018 Zeighami et al., (023). We also present results for using a random samples as a non-learned baseline, referred to as Sample, For direct comparison, the number of samples are set so that Sample takes the same space as the linear model. We consider 1-dimensional datasets sampled from uniform and 2-component Gaussian mixture model distributions.
Recall that our theoretical results provide bounds of the form E >> g(n, e, d), for some function specified in our theorems. Given a model size, d, data size, n and dimensionality d, define e* as the largest such that S g(n e, d) holds. For model size a, this implies that for any model, there exists a d-dimensional dataset of size n where the error of the model is at least c". Thus, an interpretation of our theoretical results is that given model size, 0, data size, n and dimensionality, d, our results provide a lower bound on the worst-case error across all d-dimensional datasets of size n for any model of size s, where this lower bound is equal e* as defined above. Our experiments present results following this view of our theoretical bounds.
Our experimental results are presented in Fig. [ The color of the lines/points in the figure corre- sponds to the specific models, and the points in the figures show either the maximum or average error across queries, observed after training the specific models on datasets sampled from either GMM or uniform distributions. The solid lines in the figures plot the value of c" i.e., lower bound on the worst-case error across datasets, for different model and data sizes. The results are presented for in- dexing and cardinality estimation and under 1-norm and co-norm errors. Our bounds range-sum estimation are similar to cardinality estimation, and are thus omitted. Note that the error is often (much) larger than 1, since the error is based on the absolute difference between model prediction and true query answers. The true query answers can be large, and their values scale with data size, so that the absolute error of the models is also large and increases with data size. We perform no normalization of the error values, to allow direct comparison with our theoretical results.
First, consider our results the worst-case error, shown in Figs. D (a) and (b). As expected, the observed error of different trained models increases with data size, with the models achieving lower error on uniform distribution compared with GMM. Furthermore, our theoretical bounds on the model size lie close to the error of the models on GMMs, showing that the bounds are meaningful. In fact, the case of the linear model, all the observed errors lie below the theoretical lower bound. This implies that, based on our theoretical result, there exists some dataset (on which the models haven't been evaluated in this experiment) whose error lies on or above the theoretical lower bound. This shows a practical benefits of our bound: one can obtain a bound on the error of the model on all possible databases, and beyond the datasets on which the model has been empirically evaluated.
Next, consider our results on the average-case error, shown in Figs. [ (c) and (d). Compared with the worst-case scenario, we see that the results show large gap between error of the models and our theoretical bounds, especially so for larger model sizes. Our tightness results in Sec.(.2) not plotted here, thcoretically quantify how large this gap can be. We also note tha, for both worst-case and average-case scenarios, the gap between the observed error and our lower bounds on large models does not necessarily imply that our bounds are looser for larger model sizes. Such a gap can also be due to the models used in practice being wasteful of their storage space for larger model sizes. Our results support the latter hypothesis, since we observe marginal improvement in accuracy as model size increases across both distributions. This is also supported by observations that sparse neural networks can achieve similar accuracy as non-sparse models while using much less space Frankle (rank.Frankke & Carbin (2019)), hinting at the suboptimality of fully connected networks.
Finally, Fig. shows that sampling performs worse than learned models for uniform distribution while performs similarly for GMMs (Sample should be compared with Linear as they both have the same size). The latter can be because a linear model is not good modeling choice for GMMs.
8

---

Published as a conference paper at ICLR 2024
Nonetheless, our theoretical bounds suggest (see Sec. 5 theoretical comparison) the gap between learned models and sampling will grow as dimensionality increases (d = 1 in our experiments).
RELATED WORK
A large and growing body of work has focused on using machine learning to speed up database
operations, among them, learned ineexnn (Galakatos et al., 2019 Kraska al. 2018: Ferraginal
& Vinciguerra 2020, Ding et al. 2020). learned cardinality estimation (Kipf et al.] [0188] Wu &
Cong 2021 Hu et al. 2022 Yang al.
2019 2020 Lu al., [02T Negi al. (021) and learned
range-sum estimation Zeighami et al.
2023 Hilprecht et al. 2019; Ma & Triantafillou 2019)
Most existing work focus on improving modeling choices, with various modeling choices such as Kipf et al., 2018 Kraska et al. 2018). piece- wise linear
neural networks (Zeighami et al. 2023
approximation (Ferragina Vinciguerra 2020). sum- sum-product networks (Hilprecht et | (2019) and
density estimators (Ma & Triantafillou, 2019). In all existing work, modeling choices are based
on empirical observations and hyperparametr tuning, with no theoretical understanding of how the model size should be set for a dataset to achieve desired accuracy.
On the theory side, existing results in learned database theory show existence of models that achieve a desired accuracy (Zeighami et al., [223] Zeighami & Shahabi 2023 Ferragina et al.. 20220) show- ing bounds on the performance of specifically constructed models to perform database operation. Among them, Zeighami & Shahabi (2023) shows that learned model can perform indexing in Olog log n) expected query time (i.e., better than the traditional O(log n)). Our results complement such work, showing a lower bound on the required size for any modeling approach to perform the database operations. We note that the bounds in Zeighami et al. al. (2033); Zeighami & Shahabi (2023); Ferragina et al. (2020) either hold on expectation or with a certain probability, while our bounds are non-probabilistic and consider the worst-case across all datasets. Orthogonal to our work, Huu et al.) (2022; Agarwala et al. (202T) study the number of training samples needed to achieve a desired accuracy for different database operations.
More broadly, non-learned data models, such as samples, histograms, sketches, etc. (see e.g. Cor- mode et al. 2012); Cormode & Yi (2020); Shekelyan et al. (217)) are also used to estimate query answers. We discuss existing lower bounds which is the focus of our paper. and refer the reader to Cormode al. (2012): Cormode & Yi (2020) for complete treatment of non-learned meth- ods. One approach is using t-approximations, where a subset of the dataset is selected (through random sampling or deterministically) and used for query answering. Wei & Yi (2018); Matoušck & Nikolov 20155) show that for cardinality estimation, the size of such subset has to be at least 2 log (P)) to answer queries with worst-case error at most Using the fact that VC dimen- sion of orthogonal range queries 2d (Shalev-Shwartz & Ben Ben-David] 2014), we have that random sampling uses O (1)) ) + log 5)) samples to provide error at most with probability 5 Mustafa
& Varadarajan 2017 while Phillips (2008) provides a deterministic method using a subset of size O log" (B) polylog(log (log()))) Compared to our bound in Theorem we observe that c- approximations can be much less space-efficient compared with other modeling choices in high dimensions. This is because e-approximations correspond to a restricted class of models, where the model of the data is simply subset of the data. Relaxing this restriction, /Wi & Yi 2018 considers a special case of our Theorem 1 (ii), where they provide lower bound of (log ()) log(n)) on the required size when answering cardinality estimation queries in two dimensions and when u = n (recall that is the discretization factor in Sec. 3.1). The lower bound is tighter than our bound in Theorem I (ii), but unlike our bound that applies to arbitrary dimensionsionality and granularity, is only applicable present a non-learned data structure that matches the lower bound, Orthogonal to our work, other lower bounds have been presented in the streaming setting (Cormode & Yi 2020 Suri al. 2004).
the specialized case of d = 2 and = n. In this setting, Wei & Yi (2018) also
6 CONCLUSION
We presented the first known lower bounds on the required model size to achieve desired accuracy when using machine learning to perform indexing, cardinality estimation and range-sum estimation. We studied the required model size when considering average-case and worst-case error scenarios, showing how the model size needs to change based on accuracy, data size and data dimensional- ity. Our results highlight differences in model size requirements when considering average-case and worst-case error scenarios and when performing different database operations. Our theoreti- cal results provide necessary conditions for ensuring reliability of learned models when performing database operations. Future work includes providing tighter bounds for average-case error, bounds based on data characteristics such as data distribution, and studying other database operations.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This research has been funded by NSF grant [IS-212866] and NIH grant 5RO1LM01402 Opinions, findings, conclusions, or recommendations expressed in this material are those of the author(s) and do necessarily reflect the views of any sponsors, such as NSF.
REFERENCES
Sameer Agarwal, Barzan Mozafari, Aurojit Panda, Henry Milner, Samuel Madden, and Ion Sto- ica. Blinkdb: queries with bounded enrors and bounded response times on very large data. In Proceedings of the 8th ACM European conference on computer systems, pp. 29-42, 2013.
Atish Agarwala, Abhimanyu Das, Brendan Juba, Rina Panigrahy, Vatsal Sharan, Xin Wang, and Qiuyi Zhang. One network fits all? modular versus monolithic task formulations in neural networks. In International Conference Learning Representations, 2021. URL https:
/ //openreview.
Rudolf Bayer and Edward McCreight. Organization and maintenance of large ordered indices. In Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, pp. 107-141, 1970.
Graham Cormode and Ke Yi. Small summaries for big data. Cambridge University Press, 2020.
Graham Cormode, Minos Garofalakis, Peter J. Haas, and Chris Jermaine. Synopses for massive data: Samples, histograms, wavelets, sketches. Found. Trends Databases, 4(1-3):1-294, January 2012. ISSN 1931-7883. doi: 10.1561/19000000044 URL mattps://@ci.org/110
1900000004]
Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, et al. Alex: updatable adaptive learned index. Proceedings of the 2020 ACM SIGMOD International Conference on Manage- ment of Data, pp. 969-984, 2020.
Paolo Ferragina and Giorgio Vinciguerra. The pgm-index: fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment, 1328):166 2020.
Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. Why are learned indexes so effective? In International Conference on Machine Learning, pp. 3122-3132. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL https:// openreview net wtatt//formmiiddid
b3RcF7
Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. Fiting- tree: data-aware index structure. Proceedings of the 2019 International Conference on Management Data, pp. 1189-1206, 2019.
Joseph M Hellerstein, Peter J Haas, and Helen J Wang. Online aggregation. In Proceedings of the 1997 ACM SIGMOD international conference on Management of data, pp. 171-182, 1997.
Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. Deepdb: Learn from data, not from queries! Proceedings of the VLDB Endow- ment, 13(7), 2019.
Xiao Hu, Yuxi Liu. Haibo Xiu, Pankaj K. Agarwal, Debmalya Panigrahi. Sudeepa Roy, and Jun Yang. Selectivity functions of range queries are learnable. In Proceedings of the 2022 Interna- fional Conference Management of Data, SIGMOD '22, pp. 959-972, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392495. doi: 10.1145/3514221. 3517896. URL https:: //d:: arei..rrg/11 10. 11411111110 35142211222222 3517896
Andreas Kipf. Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Bonez, and Alfons Kemper. Learned cardinalities: Estimating correlated joins with deep learning. CIDR 2019, 9th Biennial Conference Innovative Data Systems Research, 2018
10

---

Published as a conference paper at ICLR 2024
Tim Kraska, Alex Beutel, Ed H Chi, Jeftrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pp. 489-40444 2018.
Yao Lu, Srikanth Kandula, Amd Christian König, and Surajit Chaudhuri. Pre-training summariza- tion models of structured datasets for cardinality estimation. Proceedings of the VLDB Endow- ment, 15(3):414 4266 2021.
Qingzhi Ma and Peter Triantafillou. Dbest: Revisiting approximate query processing engines with machine learning models. In Proceedings of the 2019 International Conference Management of Data, pp. 1553-1570, 2019.
Jirí Matoušek and Aleksandar Nikolov. Combinatorial discrepancy for boxes via the gamma. 2 norm. In s International Symposium on Computational Geometry (SoCG 2015). Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik, 2015.
Nabil H Mustafa and Kasturi R Varadarajan. saaixiiapppro and epsilon-nets. Chapter 47 in Handbook of Discrete and Computational Geometry, 3rd edition, 2017.
Parimarjan Negi, Ryan Marcus, Andreas Kipf, Hongzi Mao, Nesime Tatbul, Tim Kraska, and Mo- hammad Alizadeh. Flow-loss: Learning cardinality estimates that matter. Proc. VLDB En- dow. 14(11):2019-200 jul 2021. ISSN 2150-8097. doi: 10. 1447883346629994776599 URL.
/ttpss///do1 o0gg
3476259
Parimarjan Negi, Ziniu Wu, Andreas Kipf, Nesime Tatbul, Ryan Marcus, Sam Madden, Tim Kraska, and Mohammad Alizadeh. Robust query driven cardinality estimation under changing workloads. Proceedings of the VLDB Endowment, 1606):1500-153,, 2023.
query
Mihai Pätraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. In Proceedings of the thirty-eighth annual ACM symposium Theory of computing, pp. 232-240, 2006.
Jeff M Phillips. Algorithms for e-approximations terrains. In International Colloquium on Au-
tomata, Languages, and Programming, pp. 447-458. Springer, 2008.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Michael Shekelyan, Anton Dignös, and Johann Gamper. Digithist: a histogram- data summary with tight error bounds. Proceedings of the VLDB Endowment, 10(11):1514-155, 2017.
Subhash Suri, Csaba Tóth, and Yunhong Zhou. Range counting over multidimensional data streams. In Proceedings of the twentieth annual symposium on Computational geometry, pp- 160-169, 2004.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Zhewei Wei and Ke Yi. Tight space bounds for two-dimensional approximate range counting. ACM Transactions on Algorithms (TALG)) 14(2):1-17, 2018.
Peizhi Wu and Gao Cong. A unified deep model learning from both data and queries for cardi- nality estimation. In Proceedings of the 2021 International Conference Management of Data, pp. 2009-2022, 2021.
Zongheng Yang. Eric Liang. Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M Hellerstein, Sanjay Krishnan, and Ion Stoica. Deep unsupervised cardinality estimation. Proceedings of the VLDB Endowment, 13(3):279-292, 2019.
Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. Neurocard: one cardinality estimator for all tables. Proceedings of the VLDB Endowment, 14(1): 61-73, 2020.
11

---

Published as a conference paper at ICLR 2024
Sepanta Zeighami and Cyrus Shahabi. On distribution dependent sub-logarithmic query time of learned indexing. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 40669 40660. PMLR, 23-29 Jul 2023. URL
ings www.srr.ressvv0000 http:////rrrrreenennno...prrrr/s
ze gham 23a html
Sepanta Zeighami, Cyrus Shahabi, and Vatsal Sharan. Neurosketch: Fast and approximate evalua- tion of range aggregate queries with neural networks. Proceedings of the ACM on Management of Data, 1(1):1-26, 2023.
A DISCUSSION
Bounding log2 error. Recall that our results consider the absolute error of prediction. In the case of indexing. one is often interested in log2 of the error, since that's the runtime of the binary search performed to find the true element after obtaining an estimate from the model. Our worst-case absolute error bound directly translates to worst-case log, error bound (this is because log is an increasing function). That is, there exists dataset such that worst-case absolute error is e if and only if there exists a dataset such that worst-case logg error is logg e. Thus, to ensure logg error is at most an error parameter 7, we can directly set 2" in the bound presented in Theorem to obtain the bound on required model size. Regarding the average-case eπrоr, the situation is slightly more complex. Using Jensen's inequality, we have that the average log, error can be smaller than log, of the average error. This implies that, to obtain average log, error of the required model size may indeed be smaller than the bounds in Corollary | and part (i) of Theorems 2 5 would suggest
set 2". Nonetheless, our upper bounds the required model size (i.e., Theorem 4 and part (ii) of Theorems
Lemma]
S) still apply by setting = 2
Cardinality Estimation for Joins. Cardinality estimation is often used to estimate cardinality of joins, which is important for query optimization. Our bounds present lower bounds on cardinality estimation single table. Note that 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 d1 and d2 dimensions and if their join consists of n. elements, then we can apply our bounds in Table [ with d = di + d2 and n = n. to obtain lower bound on the required model size for estimating the cardinality of the join. However, we expect such an approach overestimate the required model size, as it does not consider the join relationship between the two tables. For instance, n. x d may be much larger than n1 x d1 + n2 d2, 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.
Other Aggregations. Our results consider count and sum aggregations. Although we expect similar proof techniques as what was used to apply to other aggregations such as min/max/avv, we note that studying worst-case bounds for min/max/avg may not be very informative. Intuitively, this because, for such aggregations, one can create arbitrary difficult queries that require the model to memorize all the data points. For instance, consider datasets where 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 domain of size u. Now avg/min/max for any range query will have an answer between O and (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 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 worst-case error 0.5. This is not the case for sum/count aggregations whose query answers range between O to and 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 lower bound on their range, as done in Zeighami et al.) (023)) which also makes similar observations) to be able to obtain meaningful bounds. We leave such a study to future work.
12

---

Published as a conference paper at ICLR 2024
B PROOFS
B.I INTUITION
Our proofs study the characteristics of the space of the query functions to show the number of bits needed represent the elements of this space with a desired accuracy. For f {r, c, let F == [fD, size Then, for norm ||-I|, M = (F, |I-II) is metric space. A Iearned model, f(.; represents Therefore, 0 needs to be large enough (contain enough
D E [0, 1] J. be the set of all possible query functions for d-dimensional datasets of
the elements of M with its parameters number of bits), to able to represent all the possible elements of FF with desired accuracy. This in turn depends how large M is and how far its elements are from each other. Thus, our bounds follow from bounding suitable measures of the size of M, specifically, the packing entropy and metric entropy of M. Bounding the packing entropy and metric entropy of .M is non-trivial, especially when considering the 1-norm error, and requires an in-depth analysis of the metric space, relating combinatorial and approximation theoretic concepts. We note that the packing entropy argument is, in essence, the same argument also used by Wei & Yi (018) in obtaining (part of) their lower bounds (see Sec. | for the difference in our results).
Intutiveily, our proofs for the lower bounds on the required model size proceed as follows. Note that if model has size a bits there are exactly 2n different possible model parameter settings. Thus, when there are more than 2 different possible datasets, multiple datasets must be mapped to the same model parameters values (that is, after training, multiple datasets will have the exact same model parameter values). To obtain a bound on the error, our proof shows that some datasets that mapped to the same parameter values will be too different from each other (i.c., 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 + 1 different datasets such that query answers differ by more than 2c on all the 2" +1 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 on at least one of them, which completes the proof. The majority of the proofs are on how datasets is constructed. Specifically, the proofs construct a set of datasets, where
this set of 2 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 2c. 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.
B.2 BACKGROUND
Our proofs are based on the notions of metric and packing entropy which we briefly describe here.
Consider a metric space, .M- = (F,, II-II) Let IMF [I-1I. c) be the packing number of M and let N(F,1I-1|, +) be the covering number of M. The packing number is the maximum number of non- overlapping balls of radius that can be placed in M, and the covering number is the minimum number of balls of radius that can cover M (see Vershynin (0188) for rigorous definitions). We have that for MM = IMF,, [I-I], e), that there exists f1, .... f'M E F s.t. flfe - fyll > e for all i * j, and for N NJF [1-II, c), that there exists f1, .... JN E F s.t. Vf E F. If fill < c for some i E [N]. log, MF, ll- is called the packing entropy of M and log, N(F, II-II, <) is called the
metric entropy of M.
Our proofs are based on the following theorem, utilizing the metric and packing entropy of metric space. Let pr (ʃ) [ (0, 1)" be function that takes elements of the metric space as input and outputs a bit vector of size a, and let fo fo, 1) + F", be a function that takes bit vector of size o as input and outputs elements of space F² where ||-|| is well-defined on F UF
Theorem 6. Consider metric space, M (F, II-II)
(i) For any Po and fo such that (p+ - fll s e for all f E F, we must have N log, |MFF,11-1.220
(ii) There exists Pa and fo such that (p)((() - fll s e for all f E F with a 1 [log2 INFF, [)]
13

---

Published as a conference paper at ICLR 2024
Proof of Part (i). Let M MMF. 2c). By definition, there exists f1, ... fM F, such that Il - fyll > 2e for all i + j. Now assume, for the purpose of contradiction that there exists Pa and fo with 2" < M s.t., (p= - fl I for all f E F. Note that a bit vector of size d can take at most 2n different values. Since 2 < M, then p(f) must create an identical output for at least two of f1. SM. That is, there exist Si and fj. i, E [M], i + j s.t. p(fi) = p(fz). Therefore, f(p(f.) f(p(f))). By assumption the error of approximation is less than for both fo and fy. i.., (l.(((()))) - fill S and (If()(G)) - fyll S e. Then
I1/G -Jill S |I/= - f(o(si))) + (If(o(())) - Syll I[ (((A))I +I((A())) fill S 2e, Showing [ - fell s 2e which is contradiction. Therefore, we must have 2 2 M which implies
2 log2 [M, I1-11, 2c) as desired.
0
Proof of Part (ii). Let N = NNF, [l-ll.).. There exists JI, .... JN F V/ |
for some E [M]. Then, construct Pa follows. For any f E F, find i.t. f fil S Let Pa be the binary representation of Since i E [AV] [log, N bits are needed to represent i, so that o = [log2 N1. Then, for a binary representation b, define (b) as a function that finds the integer with representation b and returns fi. Thus, for any E F, we have that (po (f)) fll = II - fll S which completes the proof.
B.3 RESULTS WITH No-MORM
B.3.1 PROOF OF THEOREM 1
For the purpose of this section, define Le] + 1 for the proof of all three parts.
Proof of Part (i). Let = (TD, D E D... be the set of all possible rank functions for datasets of size n, and consider the metric space M = (F, [1- We prove lower bound IMFF, I1-1loo: c) which in turn proves the desired results using Theorem
Let PI, P2 C P P2, that is, P1 and P3 are datasets of size | | only containing points in Du. Let Dj be the dataset of size n, where each point in Pi is repeated é times (let the remainder of n- -- elements be equal one), and similarly define D2. We have that ||r,, -TD, ll >> Let S be the set of all possible datasets generated using the above procedure. We have that S is an e-Packing of M, and thus. [S] IMFF, e)).
It remains to find [S]. Each element of S' is created by selecting L elements from + elements
in Da with repetition. The unique number of ways to perform this selection is C(L " + u, [T])
(
+ +u ) Thus, M(F, 11-1lo..)) c) 2 (1 (e-1)a)=:
n
Combining this with Theorem size least 2041 1ogg (2r (2++1)").
6 we have that any model answering queries to co-error must have
(eD, D E D.), be the set of all possible cardinality functions for datasets of size n, and consider the metric space M IF.l).))))) We prove a lower bound on
Proof of Part (ii). Let F
M(F, |1-1loo, e) which turn proves the desired results using Theorem 6
Let Pt, P2 D. FIxd P1 * P2, that is, P1 and P2 are d-dimensional datasets of size L only containing values in D.. Let D2 be the dataset of size n, where each point in P1 is repeated ē times (let the remainder of | E elements be equal to one), and similarly define D2-
First, we show that ||cD, - cD 2 E. Let p be a point that appears more times in D than D2. and
and consider query q (c,r) with matches q is p. Since p appears more times in D; than D2, and each appearance of the point is repeated E times by definition we have (cD (q) cD, (9)l 2 č.
p
The only point in P1 U Pa that
Thus, we have ||cp, - -p 2 > e. Let S be the set of all possible datasets generated using the above procedure. We have that S is c-Packing of M, and thus, |S| < IMFF, el)
14

---

Published as a conference paper at ICLR 2024
It remains to find (S]. Each element of S is created by selecting L elements from (u + 1) elements in Du with repetition. The unique number of ways to perform this selection is at least C(L + w², 1
fr. Thus, M(F, l1-1 <) 2 (1 + fe+ #
Combining this with Theorem 6 we have that any model answering queries to co-error e must have size at least 2c41 1ogg + [2c+ 1u""
Proof of Part (iti). For the purpose of contradiction, assume there exists a training/inference func-
tion pair (p. f) with size less than 2++1 R logg(1 + (2++1)"") that for all datasets D "D (d+x(d+1) we have [I p()) sp c. We use (p: to construct training/inference function pair (p', that answers cardinality estimation queries for any dataset D E D with error at most e. Specif- ically, define p' (D) as a function that takes D Daxd as an input, constructs D' E DDx((+1) as D'ji.]] Dii, j] for j E [d]. E [n], and D'ii, d + 1] = 1, and returns pl D'D). Here, D' is a dataset with its first d dimensions identical to D and but with it's + 1-th dimension set for all data points. Then, we have that (=(())((D)) eD cDll S for all D E Daxd, because by spr bl by assump- cDllo I contradicts Part (ii), and thus we have proven that no
construction eD = sD', ((= p(D)) and that (lf(;)
tion. However, training/inference function pair (p, f) with size less than Z+1 log2(1 [2e+ [t+1)j")) exists that for all datasets D D (xx(d+1) we have (= sp Se.
12
B.3.2 PROOF OF LEMMA 1
For any Pa. Pa, fo with finite a, construct dataset, D, such that ||D fo(pp >
Let D be the dataset of size n with point p repeated n times. For any k; consider 4₂ = (D+ 1p 0 i & k). Note that for any D, D' E Ak. I|r -TD' I| n. Now for the purpose of contradiction, assume, bits are sufficient for answering queries with error across all datasets of size n. Now consider any fo. Let k = 2", so that | = 2" + 1. Thus. there exists D, D' E A s.t. Pa (D) Pa (D"), so that fo (D)) = (pa (D')). Now assume the error on either D or D' is less than 5. or otherwise the proof is complete. Therefore, w.l.o.g., we have II. (D)) 2. We have that
n = n=IIrD TD 1o000 = (o))))
n - Thus, for any Pa. fo with finite o, there exists a dataset, D
- (po (D')) bo
So that ||r - (po
2.
such that ||r-- - (o
B.4 RESULTS WITH 1-NORM
B.4.1 PROOF OF THEOREM 2
We first present the following lemma, whose proof can be found in Appendix C
Lemma 3. Let D. D' E [0, 1]" be datasets in sorted order. Then, ||rD TD 11 = Σien
D
D'iill Note that Eiejn D D'[i] D 1D-D'M D'Ili, that ||r TDr || || D'
The lemma shows that 1-norm between rank functions has a closed-form solution that can be caleu- lated based the difference between the points in the dataset. We use this lemma throughout for analyzing the 1-norm error.
Let F = {rp, D E [o. 1]"}. be the set of all possible rank functions for datasets of size n, and consider the metric space M = (F, I1))
Proof of Theorem 2 (i). We prove lower bound on M(F,Illll,e)) which in turn proves the desired results using Theorem
Let P -
[ 1} for an integer specified later. Let P,P' P' p
that is, P and P' are datasets of size L only containing points in P. Let D be the dataset of size
15

---

Published as a conference paper at ICLR 2024
n, where each point in P is repeated & times (let the remainder of n [& x elements be equal to one), and similarly define D' using P', and consider D and D' in sorted order.
We show that ||r TD II > Observe that D and D' differ in at least & points, that D[i] *
D' for different values Using this observation and Lemma 3 we have that
[rD rD | - D'Il
X k =
Thus, for any two different datasets, D, D' generated by the above procedure, we have ||n- > Let S be the set of all datasets generated that way. We have that S is an e- e-Packing of M,, and thus, |S| s M(F, e).
remains find (S]. Each element S created by selecting [ elements from [ elements in P with repetition. The unique number of ways to perform this selection is C(L + T - 1, Lk
Let / so that we have
[vn
|+ [v - 1-1,
C(L
1)
[v
[vn
+
yn
T
=11 (1+
vn / |
1
n
V
vn
Thus, M(F, 11-111.c) 2 (1+ _ w Combining this with Theorem 6 we have that any model answering queries to 1-error c must have size at least (vn - 2) loga (1
Proof of Theorem (i.) We prove upper bound the metric entropy INF,, 11-112,c).
Let D { 1 sis [ and define F {rn, D E D" We show that F is an e-cover of F, so that its size provides an upper bound for the covering number of F.
Specifically. for any D E [0, 1]", we show that 3rp E F, s.t. ||rD rDlla S Consider D such that Di [ for all Such D exists in Drh all its points belong D. This because
[1l _ x Dil is an integer between 0 and 1 1. for D [ E [0, 1]. Furthermore, using Lemma 3
|rD -D-T
Σ sE|m]
D D(o]
x D
|D[
xE[m]
iE[n]
S.
Therefore, F an e-covering of F. It remains calculate the size of F, which is the number of possible ways to select n elements from
[ + elements in D with repetition. That is,
(e e + Syn F C(n + n) < (e n1 + + (e n + 22 +1 ===
So that (NF,, (1. e) < (e+ s 5 + Combining this with Theorem 6 we obtain that n log, + 4) is an upper bound on the required model size.
16

---

Published as a conference paper at ICLR 2024
B.4.2 PROOF OF THEOREM
We first present two lemmas, whose proof can be found in Appendix C These lemmas can be seen as substitute for Lemma 3 for the case of cardinality estimation, since we not have such a closed-form general statement for 1-norm difference between cardinality functions (as we did for indexing in Lemma 3). However, the following lemmas provide scenarios where the I-norm difference between the cardinality functions are bounded, which are utilized in our Theorem's 's proof.
Lemma 4, Consider two I-dimensional databases D and D' of size n such that D for E [n]. Then |CDD cpr ||1 S 2e.
S
Lemma 5. Consider a 1 1-dimensional database D of size n.. Assume that we are given two mask
vectors, m m² {0, 13"h that each create two new dataset D and D s.l., D' consists of records in D with m = 1 i E {1,2}. We have that ||D' - CD> 3 Eie(n)
m - m
For the remainder this section, let JF (cD. De [0, 1] be the of all possible cardinality functions for d- d-dimensional datasets of size n. and consider the metric space M = (F, Il.) Our proof this case reduce the problem to 1-dimensional setting and then utilize the lemmas stated above to analyze the cardinality functions.
Proof of Theorem Part (i). We prove lower bound on MMF,, II-I1,,c) which in turn proves the desired results using Theorem
Let =
and let P= (( 1,00 i1,.,, S 3 for an integer k specified later. Let P. P, P + P', that is, P and P are datasets of size 1x only containing points in P. Let D be the dataset of size n, where each point in P is repeated k times, and similarly define D' using P.. W.l.o.g, assume D and D' differ on their i-th point and its d-th dimension. We have
||ep - -c ca-1 Jn
Jra |[e[(e,,...... Cacbb......attaa (dd cDr(Ci, Cd-l,,, Fa-1,,,.
le Cd- Pa-1s cD (c Cd-l rd-1.
... JTá-1
Where qp is an indicator function equal to if record p matches the first dimensions in q = (o1, Cd. (i,,,,,, that if e, S Sp S Cg + ry for all j E [i]. and zero otherwise.
Next, show that for any q, have
AipglllD(es Ca-1s Thr Td-1:.)) cD (c (c., Ca .i..... Td-1, -11 2 2
-d-1
Specifically, if Dii) does not match the first Otherwise, let D = (D[i,d) Vi, Ii,I tribute the records of D that matches the first d dimensions of q. and similarly define D' = (D'(i, Vi, [ = 1} for D'. By, definition, we have that
dimensions of q. then both sides are zero 1} a I-dimensional dataset of the d-th at-
[[ep(et,.... ... Ca Fl ..., la- 1, cpr (CI, Cd- 12--1.11 Fl, -.., Ta )l ||cp ep I|
We state the following lemma whose proof deferred to Appendix bound the 1-norm difference between D and D'.
Lemma 6. Let and D' be as defined above. For e < K, we have that ||cp - -cp $
Using Lemma and the preceding discussion, have that
... .
||cD cp >
Id-1 E Jram
Ca-1 Jr
2 Jel
c4-1 r1
Pa-1
17

---

Published as a conference paper at ICLR 2024
We have that I for queries where, for all dimension, j, ry [0, and Cj
[D min D 1. j. 1 ry Calculating the total volume of such queries, we have
min min 1ii
1 de; dry = L ( -rj] - D(i,j] 15) dry
Diisl-rs
Dli
ry rydr, + S:
(1 - D Dii,j)) dr,
1-D(kal
D1i + + D(i
2
1
Dii,j]²
2
1
4'
Where the last inequality follows because all points in P have all their coordinates less than 1 2" Repeating the above for all the dimensions, we obtain that
||D cp' ||| > e0.254.
Thus, for any two different datasets, D, D' generated by the above procedure, we have ||cD -c e0.254. Let S be the set of all datasets generated that way.
It remains to find (S]. Each element of S is created by selecting [ elements in P with repetition. Set k [vn] which is
from the (5 1) possible
d
C(1 C(( +1 + [vn [v
Lrm
Tva
vn 2e
)a
+ vn 1
vn-
vn
Vvvn vn
+1
vn-
(2e)al
Vn
Thus, we have that S contains elements each of which are at least c0.25 apart for < vn.
Define e' e0.25 so that 0.25 and repeat tha above procedure for we have that there exists
-T set of (dda+t)c + vn
Vn elements where they all differ by e' for 4dd' S vn.. Thus, [pt +1 J v < M(FF11l-11, Using this together
v
have <-Packing of M, and thus,
with Theorem proves the results.
Proof of Theorem 3 Part (ii). We prove an upper bound on NNF, I1-Il.e) which in turn proves the desired results using Theorem 6
Let D = {(
["]], and define j {ep. D E Dr}. We show that F an e-cover of F, that its size provides upper bound for the covering number of F.
[[] .....
b4 ( 5 ii
[
For any D E [0, nxd we show that Ecp E F. s.t. ||cp - -ppl1 S e. Specifically, consider D such that Di [ Dir.ill for all Such D exists in D all its points belong to D. Our goal is to show that | - cplli <.
|
To do so, consider the dataset D that D[i = D for E [d - 1] and Dii, d] = Díi, d]. That is D is dataset with its first d - 1 dimensions the same as D and its d-th dimension the same as D. We have that
||cD collı |CDD collı |co cplla
We study the first two terms separately. Consider the second term ||cp - collı. Observe that the
first d - 1 dimensions of D and D are identical, so that applying any predicate on the first d
18

---

Proof of Corollary 7 For the purpose contradiction, assume there exists a training/inference 7 that for all datasets D E [0, 1]xx (d++1) we have (l: p(D): - splla S c. We use (p, f) to construct a training/inference function pair (p'.f) that answers cardinality estimation queries for any dataset D E [0, 1jnxd with error at most e. Specifically, define p' (D) constructs D' E [0, (d++1) as D' Di Díi Jl for j id] [m], and D' d + 1] 1, and returns p(D'). Here, D' a dataset with its first d dimensions identical to D and but with it's d + 1-th dimension set to 1 for all data points. Then, we have that for all D E [0, da because by construction eD spr and that f(: that (i((::(D')) ID < by assumption. However, lIf(: p' (DD) cDll1 S contradicts Theorem 3 and thus we have proven that no training/inference function pair () with size less have Published as a conference paper at ICLR 2024
attributes of the datasets leads to the same filtered data points.
Furthermore, the d-th dimension of we have
the points differ by at most n." so by Lemma 4
clop cpll 2c.
The following Lemma, proven in Appendix studies ||eD - -pll1.
Lemma 7. Let D and D be defined as above. We have ||ep - cDll1 S (d 1)e.
Thus, putting everything together, we have that
||cD - -clli S 2E (d 1)c (d+ 1)e.
We have shown that for any D. there exists cD E F such that |cep cDll S (d + 1)e. Next, we calculate the size of F. it is equal to the number of ways n elements can be selected from set of size (I + 1)". This is equal to
C(( a(II" 1) 1, s (e (1 + 1)dd + )m
n
Define 6' = (d+1)e, we have that there exists ofover F with (e (2nld 1d - ynhh elements for é' S 2 nn(d (d 1) (we have used the fact that 2x [=] + for }), which proves (1-,11-12,e)) S
(2iid11) 1
(e)
yr. Note that d 2 1 implies that e' S En(d + 1) is satisfied for all é' s n.
Combining this with Theorem 6 we obtain that n loga(e( 2(d++) an +e :)) is an upper bound on the required model size.
B.4.3 PROOFS FOR RANGE-SUR ESTIMATION
Similar to previous sections, we first present the following lemma that is used for bounding differ- ence between range-sum functions. proved in Appendix C Lemmas 9 and T0 are a direct general- ization of I Jo answering range count queries, with almost identical proofs. However, Lemma [ is specific to range-sum queries, allowing us to analyze the attribute that is being aggre- gated by the query.
Lemma 8. Assume D and D' are two dimeeniiis datasets with identical first d dimensions, but with Dii, 1] D' + 1]1 S 2 [ni]. Then, [|sD 10---3 -sDill S. E.
Lemma Consider two 2-dimensional databases and D' of size n such that DDii 1] - Dii !]] < å and D (0i,2) 2] = Di 2) for E [n]. Then [| sprlli S 2e.
Lemma 10. Consider a 2-dimensional database D of size n. Assume that are given mask vectors, m m² {0, 11ah that each create two new dataset D and D s.t., D' consists of records in D with m for E [1, We have that ||>p sp=lll S 5 EiEn))) |m m
In this section, let J = {sp. D E [0, 1]nxd], be the set of possible range-sum functions for d + 1-dimensional datasets of size n, and consider the metric space M = (F, 11
fad-1 function pair f) with size less than (vn- 2) logg(1 4d0e+iiaa
function that takes D E [0, 1]mxd as an input,
- cplli S p(D)(())) and
than (VT- 2) logz( (1 + - + exists that for all datasets D E [0, 10,x(x((++))
-m"-1
(lf(;p(D)) spil1 < c. Thus, Σ. 2 (Vn- 2) loge(1 + quaaeiied
).)
19

---

2 We first present a generalization of Published as a conference paper at ICLR 2024
Proof of Theorem 4 Let D ([ 1, i1, S 121 and define F {sD. D D" We show that F is an c-cover of F, so that its size provides an upper bound for the covering number F. For any D E [0, 1|axd we show that Jsp E F, s.t. || - =bl|1 S e. Specifically, consider D such that Diū,j]
[ for all i. Such a D exists in 2 as all its points belong
to D. Furthermore, define D' as D' Dr, for i E [n], J E [d] but D'i d - 1] = Dli d + 1).
We have that ||sp $ <pll - ||sp SD 1l + || - splli I - ||D sp Il + c by Lemma 8
The remainder of the proof follows closely the proof of Theorem 3 Part (ii) with slight generaliza- tion. We state this as lemma and differ the proof to Appendix C
Lemma 11. Let D and D' be as defined as above. We have that || SD - (d + 1)c
This, together with the above discussion implies that ||>D -sp S (d 2)c. Thus, we have shown that for any D, there exists 8D E F such that ||s sDl I (d 1)c. Next, we calculate the size of F. it is equal to the number of ways n elements can be selected from set of size (1 + 1) This is equal to
2h 6 + 1) + + - 1, S (e (121
1)
n
Define e' = (d + 2)e, we have that there exists an é'coverr of F with (e 22 d+ +o ym ele-
ments for e' S 3n(d + 2) (we have used the fact that 2x 2 [x]] + 1 for x 2 3) which proves N(F () S (e (e!_ ( ydt + yr. Note that d 2 1 implies that c' I En(d + 2) is satisfied for
all e' < n. Combining this with Theorem 6 we obtain that n logg (e( 2ld+2) yd n + e 5) is an upper bound on the required model size.
B.5 RESULTS WITH N-NORM
B.5.1 PROOF OF THEOREM 5
Theorem can be seen direct generalization of Theorem
Lemma 3 to the case of p--ormm
Lemma 12. Let D and D' be 1-dimensional datasets in sorted order. Then, I|D - -TD 1l =
DD-D'llla where [| - D2lla Evein [([D][i), D2(1l) and [([Di[i), D2(il) is the probability
of observing a query in the range [Dr [t], [2]
Using this lemma, the remainder of the proof is straightforward adaptation of arguments in the proof of Theorem 2 Let F (rp. D E [o, 1]m}. be the set of all possible rank functions for datasets of size n, and consider the metric space M = (F, (1-1.).)
Proof of Theorem 5 Part (i). Let po = 0 and define p. inductively s.t. p((p:-1,P)) = T-T-T
for i > 0. Since a is continuous distribution over [0. 1], total of [&] distinct such points in [0, 1] exist. Let P = {Pu.... P1} } be the set of all such points, for an integer & specified later. Let P,P' E pl P & P., that is, P and P' are datasets of size [ only containing points in P. Let D be the dataset of size n, where each point in P is repeated k times, and similarly define P'. Note that D and D' differ in at least & points, so that D
(1] * D' [i] for i different i's. This means kk = e. Therefore, as long as we generate datasets the [|D - rr 1| D D'lla 2 -
way described above, for every two datasets have [lr rDy || > c. Similar the case of 1-norm error, the total number of such distinct datasets is greater than (1 (1+5 + ) vv which bounds the packing entropy and together with Theorem 6 proves the results (see proof of Theorem for more details).
O
Proof of Theorem Part (ii). Let Pb = 0 and define Pt s.t. ((Pp--1PP)) = T and let P be the
set of ['] + 1 such points. For any D E [o, 1]", we show that 3D E pm, s.t. D D1,, S c. Specifically, consider D such that D = arg mig lp D[i for all i. Note that for every i, we have that ((D Diil) S n. Therefore, ||rD rpll < Eien]]
c. Similar to the case of
1-norm error, we can calculate the total number of possible datasets in p to be at most (e+ + $)",
which combined with Theorem 6 proves the result.
20

---

Published as a conference paper at ICLR 2024
B.5.2 PROOF OF LEMMA
For E {s, e), we construct a query distribution such that for any error > 0. have Ilff- fD v
for any D and D'. Specifically, consider the set Q {(x) kn 0 s i I kn 1} for an integer defined later.
Then, define the p.d.f. g(e, r) 2nk Vf Q, & [c, + r] and 0 otherwise. Note that this is a valid p.d.f that integrates to 1, as shown below.
Σ USiSkn
2nk dr de 2nk
Tul
c) dc
usiskn-1
2nk
nk
2
10
0siskn-1
2
2
2nk
nk
I nik
2
0siskn-
2nk
1
)2
1
2
nkk
0siskn-1
Now for any two dataset D and D', we have
Ilf SD
2kn
-D
i1
< 2kn
2fp(c,r)
111
< 4kn Σ
7k
nk
fn
nk nk
nk (nk)² (nk) Σ fol i 1
4kn Σ fol
nk'
nk nk
The first inequality follows by assuming, w.l.o.g that SD(g) > [D) The second inequality follows because both cardinality and range-sum functions are increasing functions in the length of the query predicate and the last inequality follows since E, IfD (+t = S n because all queries in Q are disjoint, that every point in D will contribute at most once to queries in Q. Now setting so that < complete the proof.
21

---

Published as a conference paper at ICLR 2024
C PROOF OF TECHNICAL LEMMAS
Proof of Lemma 3 The 1-norm error is the area between the two curves for D and D We break down this into rectangles whose can be computed in closed form. The main intuition is to calculate this area by considering vertically stacked rectangles on top of each other. Specifically, we
have I|DD rD |
(4)(4) - -rD((g) Let li.g be an indicator function denoting whether E
[D D' [T] (or D []] D if D' < D(i)) We have that [r rD) Di L... Thus,
we have [rD TDrll || So == lia Ei lig 2
m D DM 1 = E, DD ["]] O
Proof of Lemma
4
I|DD - CD 11>11= / Σ (1D.Elaoot)) D(E((ctt))
VEN
$ ((DD.E - D(E(octt))
iEn
Σ ELI. (In,Elactr) Def(actr)) inn
min - r)
2
n1
n
iEn
2c
Proof of Lemma We first state the following lemma, whose proof is deferred to the end.
Lemma 13. Consider two 1-d datasets D and D' over points Pi.... Pk s.t. the points in D are each repeated 21 ... Ri times for k E [n]] and 0 < 2; S n, and the points D' are each repeated z on 2k
times for l E [n] and 0 S 2 < n. Let ExEm Iz, 2//. We have that ||CD ccrll 111 S 14.
In our setting, let Pl, Pk be the distinct element of D, let 21,-., 25 be the number of times each element is repeated in D and z/, zi,--., 2's be the number of times each element is repeated in D By Lemma 13 we have that ||cp: cDalli 1 Exe(y) l 2//- Now observe that 2; Ejem m m and similarly 2/ = ]jEnn] m²]j]/DD)-.. Thus, we have
|cD - -pe 111 s
22 z/1l
iE
[k]
Inp]
(m² [5] m m²DI
EE(A
jE(n]
<
Σ
Σ
IDb
m [7] m [j]l
2
kE[k) jE(M]
Σ
m
m m²b]l
2
JE[n]
Proof of Lemma 6 For simplicity of notation, we prove this lemma with D renamed as D and D' renamed as
For any fixed r, we first bound [[c)(,,r) (.,(.,))ll Let = r
2). Let be the index of the first element which D and D' differ, and let min D [i] ).). Such an index exists the datasets different (also recall that any difference is repeated & times, by construction). Therefore, the functions are identical in the range [-1,p- p- r). Now consider two cases, when a. and when < n
(recall that u = 2
22

---

Published as a conference paper at ICLR 2024
In the first case consider the range [p -,--r,1 r.p r 2] and - - 311 Over both ranges
the functions are constant, and the functions may only change at - 2. Since the functions are identical before p but change p r, and one changes more than the other, the difference between the two functions in the range Jp- p-r,, p- r + 2] is at least k; that is [cp(c, r) - CD (c, r)] 2 for q E [p T.P
z]. Now, observe that p r + is multiple of - and that it is strictly less than p. Thus, all points in D and D' at p r + 2 are identical. Therefore, both functions have an identical change at p r so that their difference remains the same. Thus, we have that leD(g, r) - cpr (c, 2 k for q E [p T.P
41 Thus, in this case ([ep(..)) - cDr r) 2
k x 1 > 1 for u 2 &
2c 2.
In the second case, consider the range Ip - r, pl. Both functions are identical right before at p - T, while one changes by at least &or more than the other at p r, and the functions are constant over (p r.p). Therefore, (cD(c,r) rpr(c,r) 2 lo for E Ip- r. p). Thus, in this case (cD(..))
(.))il k x r.
Now we have
cD IcD-colll1- = / (cplar) ccrlar)
|CDD
[cp(..r) cpr(,))]l + ( (ep(ur) c..r)))
Jree
/
E
k(
++
r21 k
k( (1)
)
-)
2
E (E)
k(
k
Note that, for E < k. ( < f
so that
(
2
e
2
k
2
h
2
As such, we have [|ep - cD 11
M
Proof of Lemma 7 Recall that points in D and D have identical last dimensions.
Define Ti q.p (similar to proof for Theorem Part (i)) as an indicator function equal to I if a record p matches the first dimensions in q (c1...., Cd. Fi...., that is if c, S P) $ cytry for all j E [i], and let D (Dii, d] Vi, Id-1 D.) 1} be a I-dimensional dataset of the d-th attribute the records
of that matches the first d dimensions of q, and similarly define D = [Dii d Vi, - =
1} for D. Note that the d-th dimension of D' and D' are identical, that they both contain subset of elements of the d-th dimension of D, where the subset selected based on the indicator function... Thus, we apply Lemma 5 D* and D* (the masks in the lemma are induced based on the indicator functions, i.e., m (Id-1 obtain
q. D ... Idl1
and m²
I,.(nn)-11)) to
p q.b(n)
1 Σ ICDD - -p- 11 S
Id-1 Id-1
iE|m]
Moreover, by definition,
[cp(C) Cd- Ply (d CD- -1, (c)
P1 1a..-.rrdd-- 1. ||1 |cpp- -cp-ll:
23

---

Published as a conference paper at ICLR 2024
Combining the last two inequalities, have
Ja
[
l|eD - -coll $
2 9.Dis
Id-1
q.
ca-i Jra-1 iE(n)
1
2
ra-1
9.
(c(n]
Now observe that for any q and
TT - Id-1 aD
Σ
Seisssststttt,, - 10DDi11stt
JEld-1
Where / is the indicator function, so that
||CD cbll S Σ ΣΣ
()(d_)) 9 1 1/.../
ra-1 Ja
/
Me; sesdslssesett
Note that for any j. sl..slt.sssttt 1 Diulssttt = 1 only in the two following scenario:
(1) if p I 9j < Di and Dii,j] - 9j $ ry S or (2) Dii - 1 S og - D and
D Dig oj rr - D Cj- For the first scenario, we have that DRial
dr, de, = D
(1 (1- D(i,j [ +c,)
Dial D(id)-es
2 D(i.il dej
[[1 - D(i,j)) +
2 -Di,jl
D Dii,1
+ [[1 D(..j) D
=-((1 D(i.
Dii D()
Díi.jl² + Dli,j]
Dii.j1²
-Di.j Dii [i,
(Dli. - D(.,)) [Diij] - -(i,)))
And for the second scenario we have
D(val
Dlisl-
D(ba]
-(.d)-1- dr, de,-
D (D(i.j] - D(i,j) de,
(Dli..) - D(i,j))
n
Thus, have
|CD - cplli s
1
Σ
Σ
MesDRolsoth -oggbi-Ssett
2
jeld 1]
ke(n)
Ca
ri
P1-1
$ 2
Σ
Σ
jc(d-1)
1)c.
Proof of Lemma
24

---

Published as a conference paper at ICLR 2024
8D - &
Σ
Di, - [i 1))
qEQ. iE|n]
$
ID.aa +[i -
qEQu iE(n)
Σ ID.
qEQ. (E(N]
iEin
qEQ.
e
Proof of Lemma
J. Σ
S 1sD-sD-ll
D(i,2] Dia Dii 2))
iEn
f - [[.eeee((sst D
[
Σ Du..eeee.t [1..jeele.t
Σ J. I Du.jelecc ['p.jeetect
min!
r}
iEn
2
n
2c
Proof of Lemma 10
We first state the following lemma, whose proof is deferred the end.
Lemma 14. Consider two 2-dimensional datasets and D' over points Pi.... Ps. S.f. the points
in D are each repeated 21, 2k times for [n] and O S S n, and the points D' each repeated 21, ..., 2 times for l E [n] and 0 S 2 S n. Let = Σie(m 121 2/-- We have that
||sp sD 1la I L
In our setting, let Pt. Pp be the distinct element of D, let 21, 25 be the number of times each element repeated in D and z/,,.., z' be the number of times each element is repeated in
D2 By Lemma 14 have that ||>p- =Dall /|1 2 Eieje lz 2/{- Now observe that 2;
25

---

Published as a conference paper at ICLR 2024
ΣjE(nl m [) and similarly 2/ Σ JE[nn m mi))) p.- Thus, we have
|| sp=ll1
-
22 zi
(A]
I. (m
m Gi)
=
(E(A]
jE(n)
Dbbl= |m [5] m Li]l
iE [e(M] jE(m]
Σ
mm
[b]
m²
jE(x]
Proof of Lemma 17 For notational consistency with proof of Theorem 3 rename D' as D in the proof here.
Consider the dataset D that Dii,j] D jl for E [ - 1] and Di, Dii, d.. That is D is a dataset with its first d dimensions the same D and its d-th dimension the same D. We have that
Is spll1 S -|sp-spll ||>p spllı
We study the first two terms separately. Consider the second term || spll1- Observe that the first d dimensions of D and D are identical, so that applying any predicate the first d attributes of the datasets leads to the same filtered data points. Furthermore, the d-th dimension of the points differ by at most f, so by Lemma 9 we have
||
spll1 S 2c.
Next, consider the term ||s spll. Define T an indicator function equal to if record matches the first i dimensions in = (cI,..., Cd, Ti..... ra), that is if oj S Pj S Cj + ry for all j E [i]. and let D (Dli, d d + Vi, Iig 1} be 2-dimensional dataset of the d-th and d + 1-th attribute of the records of D that matches the first 1} for D. Note that the d-th and d + 1-th dimension of D and D are identical, so that they both contain a subset of elements of the d-th and + 1-th dimension of D, where the subset is selected based on the indicator function I Thus, we apply Lemma 10 to D' and D (the masks in the lemma are induced based on the indicator functions, ie., (I Id-1 and m² (Id-1
dimensions of q, and similarly
define D (Dli, d: : d + 1] vi, 9.D Ii-
q(D] 7d-1 (m)
)) obtain
D(D] a.Dmm)
||s0 8b-111 111 S
1 Σ
Idl
I
d 9
sE|n
Moreover, by definition,
[Csp(C Cd-l, rd-1,-) (c, ..., -dd
rd-1, = || -8-111-
Combining the last two inequalities, we have
|8 +bll < [
[dd1
- -d-1
2
Di
ca-1
J
iE[n]
[d-I DID
I b
[E|M)
62 Ga
S (d - 1)c
Where the last inequality was shown in the proof of Theorem have that
Putting everything together, we
||ap - =pl1 11 2x + (d 1)e = (d + 1)e.
26

---

Published as a conference paper at ICLR 2024
Proof of Lemmal 12 We have Irp-rrdll || Jo rD(() -ro-(g) Let Lig be an indicator variable
[P(i, [(] (or [D D(i) if D'ii] < D(i). We have that (nD(g) (gr( Ei=0 Li.q. Thus, we have ||rp rprlla = So Ei= hagd Ei= So L.
denoting whether q E
Eizo Pee dp Σ, p
D [., D'I:.).
Proof of Lemma 13
Let D D U D', that is D is dataset over points pi,.... Pa each repeated max 2e. z/}} We have lleD - <orlllllo - cD. || + ICD cD. |1-
<i "m 2j with 2;
By Lemma
15 (stated and proved below) we have
1 Σ KE[M]
|cpp - -C--c S
(2f 21) =
(max 22 2/} 24)
sE(R)
and similarly
-c- -
1
Σ
(2] 2/1
1
Σ
(max f 22, 2/} - 21)
2
2
EE(
kE(k]
so that
1
1
5
(max 23s 2f} - x + 2 sk[k]
(max{ 24, 2/} 22)
2
kE
k
1
(max (Z 2 24 + max Zz; 2/} 2/)
2
Mc(M]
1
Σ
2 - 41
2
kE(M]
Proof of Lemma 14 Let D = D D', that is D" a dataset over points Pı: Ps: each repeated
2i, ... 26 with 2 max(2), 24, 2/} We have s sprllsl SD- 111 + ISD sD- 11
By Lemma 16 (stated and proved below) we have
||8D - sp- 112 S
Σ
(2)
23)
Σ EE
(max (2x, (z1, 2;)
2
2
KE(A]
and similarly
|SDi - SD- 1111111 S
1
Σ
(2) 2)
1
Σ
mmax Imax(2,,2) 2/} 2/)
2
2
KE(k]
tE(k)
so that
|Ss - SD
5
1
(max Z4, 2/ 2/ +
1
Σ
max 2/ 24)
2
iE(k]
KE(M]
1
Σ
(max 2/, 2/ 2; + max 2/} 22,
2
AE(A]
1
124
2/1
2
SE[R]
Lemma 15. Consider I 1-dimensional database D of size n, such that points Pi...., in D are each repeated 21,... 2y times for k; 2, E [nl], Σie(n) 24 = n. Consider another dataset D' contain-
ing the subset of points PI....P. having 0 I 2 I and Eiejn) 24 = n' so that n' I n. Let
t= Σieje 12 - =4/. We have that |co cD || L f r 1/1
Proof of Lemma 15
Fix value for Let X = fi E [k], 2 + 2/}-
Observe that cn and cp only differ for queries where there exists an E X for which c E [p; [p:-r,p]] pr]. Thus,
27

---

Published as a conference paper at ICLR 2024
||eD - cDrll 5"
Σ
(2 - 2/))
8=-1 KE
(2) z
Ipe(u.)
KE
q=-1
(2z 244)
r= pE[k]
q=p--r
t rt
2
Lemma 16. Consider 2-dimensional database D of size n, such that points Pi.-.. Pk in D are each repeated 21,..., 24. times for k. Rs E [m]] Eie(n) = n. Consider another dataset D' containing the subset of points P1.... .k. having
2 S 2 and EiE(n) n' so that n' S n.
Let Eieta |2g - 2//l. We have that ||s sD || f r Lt.
Proof of Lemma 16 Fix a value for r. Let = fi E [k] 2 + 2/}-
Observe that sp and s only differ for queries where there exists an i X for which E [p,[1]
r. [.]]] Thus,
- 1
(.Eeee)))) - =/)p;(2]
r=0
iE(A)
(2s 21)
c=-1
(P:11]
(2g - 2/
1
KEIKI
[=p,[1]-r
rt
28


Reviews:
[{"review_id": "kNA9X7K0fs", "reviewer": "Reviewer_Aapp", "summary": "In this paper, the authors consider the problem of providing\nguarantees for learned database operations. In particular, they\nconsider indexing, cardinality estimation, and range-sum estimation,\nand provide error guarantees for these three operations in both the\nworst and average case (in the latter, they consider uniform\ndistribution on queries, and a second scenario where any distribution\ncan be used). Besides, they provide an experimental evaluation\ncomparing their error bounds with the errors obtained by training\ndifferent models on datasets sampled from different distributions.", "questions": "* Could you please comment on the two points mentioned in Weaknesses.\n  In particular, could you please comment on the possibility of using\n  the ideas of the paper to provide error guarantees for aggregate\n  operators min, max, and average.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* As pointed out by the authors, for database operations like\n  indexing, learned estimators have empirically been shown to\n  outperform some well-known traditional methods. However, such\n  learned estimators are not widely used as no guarantees on their\n  errors are known. In this sense, this paper makes a significant\n  contribution by providing such guarantees for some useful database\n  operations.\n\n* The experimental evaluation provides some evidence that the bounds\n  provided in the paper are meaningful.\n\n* The paper is well written, with clear statements of the problems studied and the results obtained.", "weaknesses": "* The cardinality estimation queries considered in the paper are\n  restrictive. For such queries to be useful in practical database\n  systems, they should include more complex queries, in particular,\n  the join operator. In fact, one of the most important cardinality\n  estimation tasks in databases is the estimation of the size of a\n  join query, which is witnessed by the large number of research\n  articles on this subject.\n\n* The range-sum estimation queries considered in the paper are also\n  restrictive. In particular, including other forms of aggregation\n  would be very useful for practical database applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "khdXG3tyLi", "reviewer": "Reviewer_q6av", "summary": "The work investigates the minimal size of models (minimal number of bits needed to represent model parameters) that can approximate ranks and (weighted) orthogonal range counts with a guaranteed maximal additive error (epsilon). It derives formulas for the worst/average-case model size and compares them with empirical results of a limited empirical result.", "questions": "Q1) What are the limitations of this work?\n\nQ2) What is a non-trivial prediction that is enabled by the results in this this work?\n\nQ3) What topics in the literature are related to the studied topic and how do the results in this work relate to the results from the related topics (e.g., how much better is a learned model than random sampling / other summaries)?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1) Theoretical results are accompanied by empirical results.\n\nS2) Results provide some insight into the practical complexity of approximating some database operators for multidimensional numerical data with learned models.\n\nS3) The paper is generally easy to read and understand.", "weaknesses": "W1) Presentation a bit misleading: The paper gives the impression as if the results apply to general database operators over all sorts of tabular data (e.g., SQL queries over mix of categorial/numerical data) while the results are limited to orthogonal/axis-aligned range queries (intersection of range selections along each dimensions). In general the limitations of this work are not outlined clearly.\n\nW2) Significance unclear: The empirical study is too limited to give a clear idea how much predictive power is gained via the derived formulas and the general discussion does not clearly explain the implications for learned indexing and related topics. Non-learned baselines such as random sampling are missing.\n\nW3) Literature: The related work discussion is too limited in scope. It does not discuss VC dimensionality of orthogonal range queries (which is well-known and discussed in the referenced works), epsilon approximations in the computational geometry literature and data summaries in the database literature that pose questions that are similar in spirit to the model size question just with non-learned models such as samples and histogram-based data structures. Examples of related work in the aforementioned topics:\n\n- Mustafa, N. H., & Varadarajan, K. R. (2017). Epsilon-approximations and epsilon-nets. arXiv preprint arXiv:1702.03676.\n\n- Suri, S., Tóth, C. D., & Zhou, Y. (2004, June). Range counting over multidimensional data streams. In Proceedings of the twentieth annual symposium on Computational geometry (pp. 160-169).\n\n- Shekelyan, M., Dignös, A., & Gamper, J. (2017). Digithist: a histogram-based data summary with tight error bounds. Proceedings of the VLDB Endowment, 10(11), 1514-1525.\n\n- Cormode, G., Garofalakis, M., Haas, P. J., & Jermaine, C. (2011). Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends® in Databases, 4(1–3), 1-294.\n\n- Wei, Z., & Yi, K. (2018). Tight space bounds for two-dimensional approximate range counting. ACM Transactions on Algorithms (TALG), 14(2), 1-17.\n\nW4) Minor issues\n\n- p.3, Preliminaries, \"specifics\" => \"specifies\"\n- p.6, Learned Cardinality Estimation, \"estiamtion\" => \"estimation\"\n- p.10, Related Work, \"hyperparametr\" => \"hyperparameter\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wKPSrW5uCV", "reviewer": "Reviewer_EAu4", "summary": "The authors prove lower bounds on model sizes for various learned database components (indexing, cardinality estimation, and range-sum estimation) for a given maximum error and domain size across any dataset. For example, using the author's theorems, one can compute a lower bound on the number of bits a learned index structure must use to achieve a worst-case error over all databases of N rows and domain size U. The authors also give results for average case error, assuming either a uniform or an arbitrary query distribution.", "questions": "Q1) I found the main text of the paper to be both overly formal and to give very little intuition about the actual proof. If the main text is just going to go over the results and implications, you might as well drop the formal notation and give intuitive / illustrated examples of each problem and bound.\n\nQ2) That said, I really do wish the authors had tried harder to convey the intuition behind the proof in the main text. Unfortunately, I do not have the required background to parse the appendices. As far as I can tell, the authors assume that a learned structure can, at most, represent 2^n different functions of bitstrings. The authors show an isomorphism between bitstring functions and learned indexing, and then assert that, since only 2^n bitstring functions can be covered, any database admitting more than 2^n values must have at least imperfect prediction. From there, the authors work through to the error bound. I would love to know more!\n\nQ3) A note on error functions: learned index structures today generally care about log-loss (i.e., the average log2 of the absolute differences), since this is the number of binary search steps one will need for the \"last mile\" search. \n\nQ4) typo A.1 \"on the notions of the notions of\"", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "This paper tackles an important problem. Existing learned index structures either grow unbounded to support a specific error (e.g., PGM index), or have an unbounded error but a specific size (e.g., RMI). In the former case, the author's bounds can be used to estimate the size of the fixed-error index structure ahead of time. In the latter case, where the model size is fixed ahead of time and the error is determined during training, the author's bounds can be used to estimate an initial model size from the desired error, or to compute an estimate of the error from the size of the model. Interestingly, the authors show that the domain size is relevant for worse case behavior but not for average case behavior.", "weaknesses": "While the bounds given by the authors certainly help bring our understanding of learned database components closer to that of traditional data structures, it is not clear to me how these bounds could be used in systems today. The most I seem to be able to say with the author's bounds is \"if your learned index uses S bytes of memory, then for a given domain size, there exists a dataset size n for which your index must have an error larger than e.\" \n\nIt is not clear to me how to use these bounds to size a particular structure with a fixed error, which would be useful for estimating the size of error-bounded indexes. Nor is it clear to me how to use these bounds to estimate the error of a fixed-size structure. Further, the authors fall short of actually *constructing* either (1) a dataset of size `n` and domain size `u` for which a particular index cannot achieve an error better than `e` for a given size, or (2) a index structure that can actually achieve the given error bounds at the specified size.\n\nThat said, this paper is still a useful contribution for practitioners like me! Using the worst-case error bounds for indexing given in table 1, setting n=200M, u=2^32, e = 8, I get sizes remarkably close to the exhaustive search performed by the cited learned index papers (7MB). So, even if these bounds are not exactly what database folks need, they appear to be a useful heuristic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "R77jsl7Nw8", "reviewer": "Reviewer_Px8G", "summary": "This paper works on establishing the lower bound of the required model size for arbitrary datasets, given a tolerable error parameter. The authors provide worst-case and average-case theoretical analysis for three database operations, i.e., learned index, learned cardinality estimation, and range-sum estimation. Some empirical evaluations are performed. While this appears to be the first theoretical study of such guarantees for the learned model, there are several concerns.", "questions": "1. It would be great to better articulate the problem settings (See W1)\n2. It would be great to justify the usefulness of worst-case/average-case guarantees instead of instance-level guarantees (See W2).\n3. It would be great to show more implications of the theoretical results (see W3)\n4. what is the unique property of learned DB operators that are used during the proof? Putting it in another way, is this method applicable to arbitrary functions and not limited to learned DB operators?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is the first to study the guaranteed error for learned database operations.\n2. This paper is overall easy to read, though I did not read the proof.", "weaknesses": "1. Concerns about the problem setting -- the studied problem does not quite correspond to the learned DB operators\n-- For the learned index, it is fine for the model to make errors as we can maintain some delta to help correct the error. After all, the training and testing data are the same. \n-- For the learned cardinality estimator, the absolute error is not what people are using for evaluation -- q-error is. This is because for a true cardinality of 10K, an error of 100 is more acceptable than an error of 10 for a true cardinality of 10.\n\n2. When people study learned db operators, the main advantage is that the model can adapt to the underlying data and hence derive instance-optimal solutions. However, this paper is studying the worst-case/average scenario, which contradicts to the motivation of using learned model to be instance-optimal.\n\n3. It would be great to show more implications of this theoretical results and how can we make use of this theoretical results in practice. It is now unclear. The result shown in Figure 1 does not provide actional items for users. In particular, it seems that different models are having similar average-case lower bounds in terms of error -- which is not quite differentiable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)