arXiv CSopen access

Index-Assisted Stratified Sampling for Online Aggregation

Index-Assisted Stratified Sampling for Online Aggregation Yunnan Yu

Zhuoyue Zhao

University at Buffalo [email protected]

University at Buffalo [email protected]

Artifact Availability: The source code, data, and/or other artifacts have been made available at https://anonymous.4open.science/r/optiaqp.

1

Introduction

Ad-hoc queries often require low latency in real-time business intelligence and reporting applications [8], where users often execute ad-hoc range queries over fresh data in a flat schema (such as online ads log data, flight status monitoring, etc.). Materialization and online full scan are too expensive as they are large and frequently updated. Online Aggregation [11] is a sampling-based approximate query processing method for users to obtain approximate answers with low response time, where samples must be drawn online [28] to ensure the correctness of results under updates and independence of multiple queries. To achieve so, state of the art is to utilize indexassisted sampling [11, 29, 34] (Figure 1), which can produce highly accurate results within seconds due to the ability to draw samples with a cost (almost) linear to sample size instead of database size.

Date 2001-09-11 2001-09-11 2001-09-11 2001-09-12 2001-09-12 2001-09-13

Online updates

Approximate aggregation and confidence interval computation

Random Sampling ad-hoc queries

Carrier cancelled UA 1 DL 0 DL 1 AA 1 DL 0 UA 1

IRS Index on (date)

IRS Index on (carrier)

delay_time 5 0 1000 0 600 1000 ……

duration … 100 200 0 0 1000 0

Figure 1: Ad-hoc queries over in index-assisted S-AQP system cancelled%

#flights (right)

2 σoverall = 0.212

σ22 = 0.0026

1.0 0.8

15000 σ32 = 0.0369

0.6 0.4

20000

σ12 = 0.0035

10000 5000

0.2 0.0

1

2

3

4

5

6

7

8 9 Day

10 11 12 13 14 15

Number of flights

Ad-hoc queries over frequently updated data in a flat schema are common in real-time data analysis applications and often require very low latency. Online aggregation can achieve so by providing approximate aggregation answers with confidence bound guarantees. It relies on the ability to draw samples online in a linear time to sample size rather than database size, which can be supported by indexassisted Sampling-based Approximate Query Processing (S-AQP) systems. However, the query latencies of approximate queries in these systems can still suffer from excessive sampling cost required to achieve a desired confidence bound, due to increased sample size for data with high variance in value distribution and selectivity. Classic stratified sampling methods with Neyman allocation can minimize sample size in theory, but several challenges prevent it from being applicable in index-assisted S-AQP systems, including requiring apriori statistics, high optimization cost, and inaccurate sampling cost model based on sample size. Towards that, we design index-assisted stratified sampling for online aggregation, which features a two-phase sampling framework. Samples drawn from first phase are used for both online aggregation and optimizing future sampling cost, while the second phase continues the online aggregation using the optimized strata. We prove optimal stratification and sample size allocation strategies for index-based sampling cost model, and design several greedy and dynamic programming based optimization methods to balance optimization cost and effectiveness in cost reduction. We evaluate our methods on several real-world and synthetic datasets and queries, and the results show ours consistently achieve good speedup and, in extreme cases, up to 3x speedup and 98708x speedup, when compared to index-assisted uniform sampling and classic scan-based stratified sampling respectively.

target CI = 10000.0 at confidence 0.95

SELECT APPROX_COUNT(*), APPROX_COUNT_CI(0.95) FROM FLIGHT WHERE DATE BETWEEN L AND U AND CANCELLED = 1

Cancellation rate (%)

arXiv:2604.28141v1 [cs.DB] 30 Apr 2026

Abstract

0

Figure 2: The percentage of cancelled flights and the total flight during the date range. Overall estimator variance is higher than those of any of the three smaller date ranges. However, the time to achieve a given confidence interval in these systems may vary heavily. The root cause is these systems often draw samples uniformly without considering the variations of data distribution and query selectivity within a dataset, which results in excessive amount of samples to be drawn uniformly across an entire query range. As a concrete example (Figure 1), consider an ad-hoc range query over a real-world dataset: the US airline on-time performance dataset [1], on which one wants to find the number of flights that were cancelled in some date range for analysis. For most of the date ranges, the cancellation rate in the US is consistently low, leading to very accurate COUNT estimation with a small number of samples. However, if we happen to query a range where part of the query range has cancellation spikes due to special events (e.g., a snow storm) (Figure 2), the estimator variance will be extremely high, leading to high latency to achieve a desired confidence bound. On the other hand, if we query the three smaller ranges as shown in Figure 2 and combine their estimators instead, all of them have smaller estimator variances, which could lead to much lower latency. This is known as stratified sampling, which breaks the entire query range into smaller partitions and independently sample from each partition and can often reduce the total sample needed and thus reduce query time. However, all known stratified sampling in AQP systems require scanning the database table for preprocessing online or offline, which either cause long preprocessing delays during query time or cannot handle data updates efficiently. As examples, VerdictDB, a state-of-the-art AQP middleware for existing DBMS [24], uses a form of stratified sampling where stratification is done over distinct values of range predicate columns, and sample size is allocated evenly to different partitions. QuickR [18] performs online scan-based sampling using a slightly improved version called

Table 3: List of notations in this paper

distinct sampling, where sample size allocation across distinct values where a minimum sample size is guaranteed for each distinct value. In [7], Surajit et el. optimizes offline samplings for query workload, which utilizes a well-known technique, Neyman allocation, to optimally allocate sample sizes to different partitions in order to minimize total sample size needed. none of these works it targets offline sampling scenario where the The crux of the problem is having to know distinct keys and/or sum statistics to create strata and/or perform sample size allocation, which currently cannot be easily derived in an online fashion. In addition, traditional methods only consider sample size as a simple cost model for sampling-based approximate query evaluation, but ignore the fact that sampling in different strata can often have very different per-sample cost. Motivated by that, we propose a two-phase index-assisted approximate query evaluation framework based on stratification, OptiAQP, which can use a small initial sample to obtain a number of candidate partition boundaries and estimated statistics to derive an optimized stratification strategy for the subsequent approximate query cost until a desired confidence bound is achieved. Combining the existing concurrency-safe index-assisted sampler [34] that can draw samples from a latest snapshot at any time under snapshot isolation, our method will significantly reduce latencies of ad-hoc approximate aggregation queries over frequently updated data with no apriori statistics. The main challenges in our proposed method are threefold: (1) how to effectively utilize sampling indexes to collect initial samples for stratification; (2) how to balance the first phase optimization cost and the sample cost reduction it results in the second phase; (3) how to accurately model the sampling cost. To summarize, We claim the following contribution:

𝑇 Q, Q̃ 𝐴, 𝐴˜ 𝜀 1−𝛿 𝛾𝐴𝐺𝐺 (𝑒 ) (·) Γ𝑛 (·) P, P𝑟 , P𝑓 𝑥 𝐿, 𝑈 𝑆 𝑐, 𝑐 0 𝐷 𝑘, Δ𝑘 𝜏 𝑚 ® ® 𝐶® 𝐵, ℎ, 𝐻 𝑑

2

a relational table exact query and approximate query exact answer and its unbiased estimator half-width of confidence interval confidence level aggregation operator [27] that computes 𝐴𝐺𝐺 (𝜋𝑒 (·) ) i.i.d. sampling with replacement of size 𝑛 over ( · ) overall selection, range and additional filter predicates range predicate column (set) lower/upper bounds in range column bag of sampled tuples total cost and preprocessing factor query range number of strata and number of children of 𝐷 ′ stopping threshold for Greedy cumulative moment statistics stratum boundaries and collect candidate boundaries height of the LCA and the tree root partition granularity

Problem Formulation and Background

In this section, we first provide an overview of problem formulation, and then introduce necessary background on online aggregation style approximate evaluation and sampling indexes. Table 3 lists the notations in this paper. Problem Formulation. In this work, we study the problem of reducing online aggregation style approximate query evaluation cost in an index-assisted S-AQP system. Without loss of generality, let 𝑇 be a relational table and we consider a single-table approximate aggregation query in the form of Q = 𝛾 SUM(𝑒 ) 𝜎 P𝑇

(1)

where P is a conjunctive predicate. It can be written as P𝑟 ∧ P𝑓 . Here, P𝑟 is a range predicate 𝑥 ∈ [𝐿, 𝑈 ) and there is a sampling index [3, 14, 23, 26, 34] over 𝑥 which can draw independent samples from 𝜎𝑥 ∈ [𝐿,𝑈 ) 𝑇 without scanning table 𝑇 . For the rest of the paper, we denote the Independent Range Sampling (IRS) operation [28] of sample size 𝑛 with replacement as Γn 𝜎 Pr T – i.e., Γ𝑛 is a sampling operator that draws an i.i.d. random samples with some distribution (e.g., uniform/weighted) over 𝜎 P𝑟 𝑇 . In addition, the sampling index also appends to the output schema of 𝜎 P𝑟 𝑇 an additional probability column 𝑝 to indicate each sample’s probability. The remaining part of the selection predicate P𝑓 is an additional filter on top of the range filter. Let 𝐴 be the (unknown) answer of the exact query Q. An approximate evaluation of Q yields an unbiased estimation ˜ = 𝐴, and a confidence bound (𝜀, 𝛿) such that 𝐴˜ such that 𝐸 [𝐴] 𝑃𝑟 {𝐴˜ ∈ [𝐴 −𝜀, 𝐴 +𝜀]} ≥ 1 −𝛿. Typically, user specifies the desirable (half-width) confidence interval 𝜀 and confidence level 1 − 𝛿, and the goal is to achieve the desired confidence bound as fast as possible. Basic S-AQP Algorithms. To obtain an approximate answer of query Q is to evaluate its approximate counterpart:

• We describe how to perform index-assisted stratified sampling and analyze the cost model of approximate query evaluation in index-assisted S-AQP system with stratification. • We prove the optimal stratification and sample size allocation strategies under the cost model given full statistics. • We design OptiAQP, a two-phase index-assisted approximate query evaluation framework and introduce 4 stratification optimization methods for OptiAQP with different trade-offs between optimization overhead and cost reduction. • We implement OptiAQP in PostgreSQL based on a state-of-theart index-assisted S-AQP system [29, 34]. We validate the query time reduction of OptiAQP over existing approaches compared to several baselines over several real-world datasets and a synthetic benchmark based on the skewed TPC-H. • We discuss possible future extensions for handling more query types including joins, spatial ranges, and group-by queries, and the additional design space. The rest of the paper is organized as follows. In Section 2, we provide necessary background on independent range sampling and the basic S-AQP algorithms in index-assisted S-AQP systems. In Section 3, we provide analysis of the cost model of index-assisted stratified sampling and the optimal stratification and sample size allocation strategy. Based on the analysis, we provide the design and implementation details of OptiAQP in Section 4. We provide extensive evaluation in Section 5. We survey related works and provide a discussion of possible extensions in Section 6 and conclude the paper in Section 7.

Q̃ (𝑛) = 𝛾𝐴,𝜀 ˜ Γ𝑛 𝜎 P𝑟 𝑇 incrementally with increasing sample size 𝑛 until the derived confidence interval 𝜀 is smaller than user specification 𝜀 0 . In more details, the evaluation of Q̃ (𝑛) works in rounds by invoking the sampling index for obtaining a delta sample bag ΔS = ΓΔ𝑛 𝜎 P𝑟 𝑇 . To derive the current estimator and confidence interval after a certain round, we Ð first denote the union of all delta sample bags as S = ΔS, and the Í total sample size so far as 𝑛 = Δ𝑛. Note that the estimator 𝐴˜ and the confidence interval 𝜀 both depend on P𝑓 as it is not evaluated by 2

0 𝑃𝑟 = 11,19 , 𝑑 ← 𝑟𝑎𝑛𝑑() = 0.4, 𝑊 = 11

6 6

10

7

20 3

11

8

1 𝑟 ← 𝑑𝑊 = 4 0 ≤ 𝑟 < 0 + 11

……

…… 2

the query range. Then it descends down into that subtree with the residual weight 𝑟 subtracted by the prefix sum of aggregate weights of the left sibling of the chosen child pointer. This results in a cost of 𝑐 𝑠𝑎𝑚𝑝𝑙𝑒 (𝑁 ) = 𝑂 (log 𝑁 ) per sample, but as we will show later, this modified procedure can help with additional cost reduction for stratified sampling. Note that we assume each node visited incurs a non-negligible constant cost, including I/O cost, locking overhead, and the linear cost for searching for the child node pointing to the subtree that contains the ⌊𝑑𝑊 ⌋ th leaf record.

26

10

12

2

3

15

19 2

2

2 𝑟 ← 𝑟−0= 4 2≤𝑟 < 2+3

……

…… 13

14

15

3 𝑟 ← 𝑟−2= 2 pick leaf record 2

Figure 4: Sampling from an aggregate B-tree. Underscored numbers are aggregate weights for child pointers. the sampling index, but we omit them when they are unambiguous in the context to simplify the notations. Their formulae [10] are given below based on the Horvitz-Thompson estimator [13] and the Lindeberge-Lévy Central Limit Theorem [5, Thm. 27.1]1 ( ˜ = 𝑒 (𝑡)/𝑝 (𝑡) if P𝑓 (𝑡) 𝐴(𝑡) (2) 0 o.w. ∑︁ ˜ ˜ 𝐴˜ = 𝐴(S) = 𝐴(𝑡)/𝑛 (3)

3

Optimal Stratification Strategies

This section provides a theoretical foundation of OptiAQP– how we can derive the optimal stratification strategies assuming we can estimate statistics of the data. Towards that, we first describe how index-assisted stratified sampling works and its cost model. Then we show the optimal sample size allocation through a modified Neyman allocation assuming strata are fixed. Finally, we prove how we can optimally determine the strata given full statistics.

𝑡 ∈S

√ 𝑍𝛿 𝜎 (4) 𝜀 = √ , 𝑍𝛿 = 2erf−1 (1 − 𝛿) 𝑛 √︄ Í ˜ ˜ 2 𝑡 ∈ S (𝐴(𝑡) − 𝐴) 𝜎 ≈ 𝜎˜ = (5) 𝑛−1 Sampling Indexes. All existing sampling indexes [3, 14, 23, 26, 34] are tree indexes. In general, the cost of these sampling indexes for drawing 𝑘 independent random records from a table of size 𝑁 can modeled as 𝑐 𝑝𝑟𝑒 (𝑁 ) + 𝑘 · 𝑐 𝑠𝑎𝑚𝑝 (𝑁 ), where 𝑐 𝑝𝑟𝑒 (𝑁 ) and 𝑐 𝑠𝑎𝑚𝑝 (𝑁 ) are two sample-index dependent factors bounded by 𝑂 (log 𝑁 ). In this work, we consider the classic aggregate B-tree first described by Olken [23] because it is the only one with open-source DBMS integration to the best of our knowledge [34]. Nevertheless, most of analysis below can adapt to other sampling indexes with plugging in their specific cost models. In aggregate B-tree, each leaf record is assigned an unnormalized weight such that the sampling probability for each leaf record is proportional to its weight – for uniform sampling, the weight of each leaf record is simply 1. It also has each of its internal node child pointer annotated with the aggregate weight of the subtree it points to. The original Olken’s approach involves performing random selection of child pointers at each level proportional to the aggregate weights, incurring an 𝑂 (log 𝑁 ) per-sample cost. Instead, [34] describes a slightly different procedure (Figure 4), which has the same complexity but only requires generating one random number per sample. Sampling 𝑘 records from a range starts with a preprocessing stage to find the left-most and right-most paths leading to the first and last records in the range, and compute the total weight 𝑊 between these two paths. This takes 𝑐 𝑝𝑟𝑒 (𝑁 ) = 𝑂 (log 𝑁 ) time. Then, for each sample to draw, it draws a random number 𝑑 in [0, 1), and performs a weight-guided descent in the tree to identify the ⌊𝑑𝑊 ⌋ th leaf record in the range: It first sets the residual weight as 𝑟 = ⌊𝑑𝑊 ⌋. Starting from root, it computes the prefix sum of the aggregate weights associated with the child pointers and find the last one such that 𝑟 is no larger than the prefix sum of aggregate weights, which is guaranteed to contain the ⌊𝐷𝑊 ⌋ th leaf record in

3.1

Online aggregation with index-assisted stratified sampling and its cost model

Recall that the range predicate in the query P𝑟 is in the form of 𝑥 ∈ [𝐿, 𝑈 ) and we denote 𝐷 = [𝐿, 𝑈 ). Then online aggregation with stratified sampling works as follows: 1. We logically partition 𝐷 into two or more non-empty disjoint ranges 𝐷 = 𝐷 1 ⊎ 𝐷 2 . . . ⊎ 𝐷𝑘 . The disjoint ranges 𝐷 1, . . . 𝐷𝑘 are also known as strata. Ð 2. The original query can be rewritten as Q = 𝛾𝑆𝑈 𝑀 𝑘𝑖=1 Q𝑖 , where each subquery Q𝑖 is the partial aggregation over the subrange 𝐷𝑖 : Q𝑖 = 𝛾 SUM(𝑒 ) 𝜎𝑥 ∈𝐷𝑖 ∧P𝑓 𝑇 . 3. We perform 𝑘 independent approximate evaluations of the (𝑛 ) subqueries Q̃1(𝑛1 ) , . . . Q̃𝑘 𝑘 with certain sample sizes 𝑛 1, . . . 𝑛𝑘 , and aggregate all estimators and confidence bounds to derive the final estimation using Equations 6 and 7 below. In other words, Q̃ ′ = Ð 𝛾𝐴˜ ′ ,𝜀 ′ 𝑘𝑖=1 Q̃𝑖(𝑛𝑖 ) . 𝑘 ∑︁ 𝐴˜ ′ = 𝐴˜𝑖 (6)

𝜀 ′ = 𝑍𝛿

𝑖=1 v u t 𝑘 2 ∑︁ 𝜎 𝑖

𝑖=1

𝑛𝑖

=

v u t 𝑘 ∑︁

𝜀𝑖2

(7)

𝑖=1

where 𝐴˜𝑖 and 𝜀𝑖 are the unbiased estimator and half-width of confidence interval produced by Q̃𝑖 . We also denote the estimated estimator variance of Q𝑖 as 𝜎𝑖2 . Then 𝐴˜′ remains an unbiased estimation of 𝐴 due to the linearity of expectation, and 𝜀 ′ remains to the estimated half-width of confidence interval of 𝐴˜′ such that 𝑃𝑟 {𝐴˜ ′ ∈ [𝐴 − 𝜀, 𝐴 + 𝜀]} ≥ 1 − 𝛿, by modeling the distribution of 𝐴˜ ′ as the sum of 𝑘 independent normal variables 𝐴˜ 1′ , . . . , 𝐴˜𝑘′ . We omit the proofs and refer interested readers to our supplemental materials. To model the cost of the query with sample size 𝑛 1, . . . , 𝑛𝑘 , an obvious bound is linear to the number of strata and the total number Í of samples taken 𝑐 = 𝑐 𝑝𝑟𝑒 (𝑁 ) · 𝑘 + 𝑐 𝑠𝑎𝑚𝑝𝑙𝑒 (𝑁 ) 𝑘𝑖=1 𝑛𝑖 . However, we argue this is often a loose overestimation in practice due to a simple implementation trick of the sampling procedure below: When sampling from a subrange 𝐷𝑖 = [𝐿𝑖 , 𝑈𝑖 ), we can first find the leftmost and right-most paths leading to the first and last record in 𝐷𝑖 with two regular tree search descents from root. Let the lowest

1 Note that, the computed half width of CI 𝜀 is an estimation due to the fact that the true

estimator variance 𝜎 2 is unknown and can only be estimated from sample variance 𝜎˜2 . 3

common ancestor of the two paths be 𝐿𝐶𝐴 and let the height of the 𝐿𝐶𝐴 and the tree root be ℎ and 𝐻 . Then, we know any leaf record in 𝐷𝑖 must have a unique ancestor node for levels above ℎ. Thus, in the sampling algorithm, we can simply skip visiting any node above level ℎ because there is no random choice to make, which results in a lower upper bound of per-sample cost of 𝐻ℎ · 𝑐 𝑠𝑎𝑚𝑝𝑙𝑒 (𝑁 ). Taking Figure 4 as an example, the LCA for the left-most and right-most paths for query range [11, 19) is the middle node at height 2. To draw samples from this range, instead of starting the weight-guided descent from the root at height 3, which can make no other choices but to descend down into the middle node, we can always start from the middle node. This reduces the per-sample cost from 3 to 2. There are two reasons why we have to consider the cost: (1) As strata in stratified sampling are often much smaller than the entire key range of the range column 𝑥, ℎ is often much lower than the entire tree height, this can result in significantly lowered cost. (2) As different strata may have LCA at different height, the per-sample cost in different stratum can also vary significantly. For example, consider the flight cancellation count query in Figure 2. Suppose each day has 200𝑘 scheduled flights and we have 20 years of data. The total tree height of a sampling index with fanout 50 is 6 – thus per-sample cost is bounded by 6. Suppose we are querying the 20day cancellation count since 9/11/2021. As there are significantly more cancellation on 9/11 than others, we might want to create two strata 9/11, and 9/12 - 9/30. With the same tree fanout and number of scheduled flights, the first stratum will have a per-sample cost of log50 100𝐾 ≈ 3, while the second stratum will have a per-sample cost of log50 1.9𝑀 ≈ 4. Both are much smaller than sampling in the entire tree, and also differ by 1/3 from each other. Hence, we must take height into account when modeling the cost. Thus, with an appropriately re-scaled constant 𝑐 0 = 𝑐 𝑠𝑎𝑚𝑝𝑙𝑒 (𝑁 )/𝐻 (preprocessing factor), we model the total cost of index-assisted stratified sampling for 𝑘 strata with sample sizes 𝑛 1, . . . 𝑛𝑘 as: 𝑘 ∑︁ 𝑐 = 𝑐 0𝑘 + 𝑛𝑖 ℎ𝑖 (8)

Solving for this using the standard Lagrange multiplier method results in Lemma 3.2, which we call modified Neyman allocation. We omit the proof for brevity, which is available in the supplemental materials. Note that, technically, 𝑛 1, . . . , 𝑛𝑘 must be integers, but the difference between the optimal and the rounded up 𝑛 ′ is very small (bounded by 𝑘). Even if we round up all 𝑛𝑖 ’s, it only incurs negligible increase of ultimate cost. L EMMA 3.2. (Modified Neyman allocation) Given a set of strata 𝐷 = 𝐷 1 ⊎ . . . ⊎ 𝐷𝑘 and the estimator variances 𝜎12, . . . 𝜎𝑘2 within each stratum, the minimum index-assisted sampling cost for approximate query Q̃ ′ to reach a (𝜀, 𝛿) confidence bound is √ 𝑍2 Í 𝑐 = 𝑐 0𝑘 + 𝜀 𝛿2 ( 𝑘𝑖=1 𝜎𝑖 ℎ𝑖 ) 2 , where the sample size for each stratum 2 √ 𝑍 Í is 𝑛𝑖 = 𝜀 𝛿2 ( 𝑘𝑖=1 𝜎𝑖 ℎ𝑖 ) √𝜎ℎ𝑖 . 𝑖

3.3

Finally, we consider the optimal stratification, assuming we will apply the modified Neyman allocation and we are able to know the estimator variances and possible candidate partition boundaries. Plugging in the 𝑛𝑖 ’s from Lemma 3.2 into the cost function (Equation 8), we essentially need to minimize the function below (Equation 9). Note that the free variables in this function are the number of strata 𝑘, and the stratum boundaries, which impacts ℎ𝑖 and 𝜎𝑖 . 𝑘 ∑︁ √︁ 𝑐𝑜𝑝𝑡 = 𝑐 0𝑘 + ( 𝜎𝑖 ℎ𝑖 ) 2 (9) 𝑖=1

The first term 𝑐 0𝑘, which corresponds to preprocessing cost, obviously increases when there’s a finer stratification. If we can show that the minimal of the second √ squared summation term, which we Í ′ denote as 𝑐𝑜𝑝𝑡 = ( 𝑘𝑖=1 𝜎𝑖 ℎ𝑖 ) 2 and represents the squared cost of actual drawing samples, over all possible 𝑘-stratification only decreases as 𝑘 increases, then 𝑐𝑜𝑝𝑡 is a V-shaped function with a global minimum. Intuitively, this is true – the finer stratification is, the smaller the second summation term of 𝑐𝑜𝑝𝑡 will be, for having lower intra-stratum estimator variance and lower tree height of the LCA for each stratum. To formalize that, we argue that Theorem 3.3 is true. We show a proof sketch below. T HEOREM 3.3. Let 𝑛 be all the possible stratification boundary keys (i.e., distinct keys in the query range). For any 𝑘 disjoint strata of the range 𝐷 = ⊎𝑘𝑖=1 𝐷𝑖 , where 𝐷 1, . . . , 𝐷𝑘 are non-empty, √ Í ′ 𝑐𝑜𝑝𝑡 = ( 𝑘𝑖=1 𝜎𝑖 ℎ𝑖 ) 2 for index-assisted stratified sampling in Q̃ ′ is no larger than that with 𝑘 − 1 disjoint strata ∀1 ≤ 𝑖 ′ < 𝑖 ′′ ≤ 𝑛, 𝐷 = ⊎1≤𝑖 ≤𝑛∧𝑖≠𝑖 ′ ∧𝑖≠𝑖 ′′ 𝐷𝑖 ⊎ 𝐷𝑖 ′ ,𝑖 ′′ , where 𝐷𝑖 ′ ,𝑖 ′′ = 𝐷𝑖 ′ ⊎ 𝐷𝑖 ′′ is treated as a single stratum. P ROOF. Without loss of generality, we only need to prove so √︁ for √ √ 𝑖 ′ = 1 and 𝑖 ′′ = 2. It suffices to show that 𝜎𝑙 ℎ 1 + 𝜎2 ℎ 2 ≤ 𝜎1,2 ℎ 1,2 , 2 and ℎ where 𝜎1,2 1,2 represent the estimator variance and LCA in sampling tree for sampling in stratum 𝐷 1,2 . We first note that, the LCA of stratum 𝐷 1,2 must be at the same height or higher height of the LCAs of 𝐷 1 and 𝐷 2 , because 𝐷 1,2 covers a larger range (see Figure 5). Thus, we have ℎ 1,2 ≥ ℎ 1 and ℎ 1,2 ≥ ℎ 2 . Thus, it suffices to prove that 𝜎1 + 𝜎2 ≤ 𝜎1,2 . Then, we can analytically compute the estimator variance below for stratum 𝑖 ∈ {1, 2}, where 𝐴˜𝑖 (𝑡) is the individual estimator variance defined in Equation 2. Here we denote the fraction of tuples in stratum i out of both strata as 𝛼𝑖 , the total number of tuples in

𝑘=1

3.2

Optimal sample size allocation via modified Neyman allocation given fixed strata

L EMMA 3.1. (Neyman allocation) Given a set of strata 𝐷 = 𝐷 1 ⊎ . . . ⊎ 𝐷𝑘 and the estimator variances 𝜎12, . . . 𝜎𝑘2 within each stratum, the minimum total sample size for approximate query Q̃ ′ 𝑍2 Í to reach a (𝜀, 𝛿) confidence bound is 𝑛 ′ = 𝜀 𝛿2 ( 𝑘𝑖=1 𝜎𝑖 ) 2 , where the 𝑍2 Í sample size for each stratum is 𝑛𝑖 = 𝜀 𝛿2 ( 𝑘𝑖=1 𝜎𝑖 )𝜎𝑖 . Neyman allocation [7] (Lemma 3.1) provides the optimal sample size allocation with respect to minimizing total sample size given a set of strata. However, it fails to consider the different sampling cost in each stratum, which can vary a lot as we discussed. Hence, we minimize the total cost rather than the total sample size below. Note that here all strata are fixed so 𝑘 and 𝜎𝑖2 are constants. 𝑘 ∑︁ minimize 𝑐 0𝑘 + 𝑛𝑖 · ℎ𝑖 𝑖=1

subject to 𝜀 = 𝑍𝛿

Optimal stratification given full statistics

v u t 𝑘 2 ∑︁ 𝜎 𝑖

𝑛 𝑖=1 𝑖 4

h 6

3

10

20

Algorithm 1: Two-phase index-assisted approx. query evaluation

26

Input: Q: original query; 𝜀, 1 − 𝛿: desired half-width of confidence interval and level 1 𝑛 0 : initial sample budget; Output: periodic unbiased estimators 𝐴˜ and half-width of confidence intervals 𝜀 //Phase 0 2 S0 ← 𝛾𝑛 0 𝜎 P𝑟 𝑇 ; ® 𝜎, 3 𝐵, ® ℎ® ← optimize( S0 ) ; ˜ ˜ S0 ), 𝜀 ( S0 ); 4 𝐴0 , 𝜀 0 ← 𝐴( 5 Output 𝐴˜ 0 , 𝜀 0 ;

𝐷1,2 = [15, 25) ℎ1,2 = 3

2

10

1

12

15

24

21

19

𝐷1 = [15, 20) …… …… ℎ1 = 2

25

𝐷2 = [20, 25) …… …… ℎ2 = 2

Figure 5: Union of two strata has a higher LCA height than either stratum, resulting in higher per-sample cost 𝐿, 𝑥0 ⊎ 𝑥0 , 𝑥1 ⊎ 𝑥1 , 𝑥2 ⊎ 𝑥2 , 𝑈 𝐿, 𝑥0 ⊎ 𝑥0 , 𝑥1 ⊎ [𝑥1 , 𝑈)

𝐿, 𝑥0 ⊎ 𝑥0 , 𝑥2 ⊎ [𝑥2 , 𝑈)

𝐿, 𝑥0 ⊎ [𝑥0 , 𝑈)

𝐿, 𝑥1 ⊎ [𝑥1 , 𝑈)

lower sample drawing cost higher preprocessing cost

𝐿, 𝑥1 ⊎ 𝑥1 , 𝑥2 ⊎ 𝑥2 , 𝑈

//Phase 1 𝑆 ← 𝜙; 𝑛 ← 0; 7 while 𝜀 1 ≥ 𝜀 do 8 Compute next sample batch size and sample size allocation Δ𝑛, 𝑛®𝑖 based on modified Neyman allocation ; 9 𝑛 ← 𝑛 + Δ𝑛 ; Ð 10 𝑆 ← 𝑆 ∪ 1≤ 𝑗 ≤𝑘 Γ𝑛 𝑗 𝜎𝑥 ∈ [𝐵 𝑗 ,𝐵 𝑗 +1 ) 𝑇 ; 11 𝐴˜ 1 , 𝜀 1 ← 𝐴˜ ′ ( S), 𝜀 ′ ( S);

𝐿, 𝑥2 ⊎ [𝑥2 , 𝑈)

6

[𝐿, 𝑈)

Figure 6: Possible stratification forms a lattice with decreasing sample drawing cost and higher preprocessing cost both strata as 𝑁 and assume uniform distribution as the sampling distribution: 𝜎𝑖2 = 𝐸 [𝐴˜𝑖 (𝑡) 2 ] − 𝐸 2 [𝐴˜𝑖 (𝑡)] ∑︁ (𝑒 (𝑡)P𝑓 (𝑡)) 2 ∑︁ 𝑒 (𝑡)P𝑓 (𝑡) = (𝛼𝑖 𝑁 ) 2 [ −( )2] 𝛼𝑖 𝑁 𝛼𝑖 𝑁 𝑡 ∈𝐷 𝑡 ∈𝐷 𝑖

12

Output 𝐴˜ =

2

2

𝑛 0 𝜀 0 +𝑛 𝜀 1 𝑛 0 𝐴˜ 0 +𝑛𝐴˜ 1 and 𝜀 = (𝑛 2 ; 𝑛 0 +𝑛 0 +𝑛)

𝑖

In this section, we describe the design and implementation of OptiAQP based on the previous theoretical analysis. As we need to know the statistics and candidate partition keys for stratification, we first design a two-phase index-assisted approximate query evaluation framework, where the first phase draws initial samples using the available sampling index to compute an optimized stratification for the second phase of index-assisted stratified sampling. Then, we provide 4 different stratification optimization methods with varying trade-offs between optimization overhead and the aggressiveness of optimization. In the end, we describe our implementation details in PostgreSQL with an aggregate B-tree implementation, AB-tree [34].

and phase 1 performs index-assisted stratified sampling using the stratification derived from phase 0 samples. A user specifies an ad-hoc query Q in the form defined in Equation 1, the desired halfwidth of confidence interval 𝜀 and confidence level 𝛿. In addition, we require the user to specify an initial sample size 𝑛 0 . This is proportional to the time the user allows the system to spend to derive an optimal stratification – in the case where intra-query-range estimator variance is so small that 𝑛 0 is sufficient to achieve the desired confidence bound, the system will skip phase 1 entirely. When phase 0 cannot achieve the desired confidence bound, we use one of our stratification optimization methods (to be described in the next subsection), to produce three vectors (line 3): the stratum boundaries 𝐵® = [𝐿, 𝑥 1, . . . 𝑥𝑘 −1, 𝑈 ] (recall that [𝐿, 𝑈 ) is the query range in P𝑟 ), the estimated per-stratum estimator standard deviation 𝜎® = [𝜎1, . . . , 𝜎𝑘 ], and the estimated LCA height/per-sample cost ℎ® = [ℎ 1, . . . , ℎ𝑘 ]. Then we repeatedly perform index-assisted stratified sampling with the stratification until the desired confidence bound is achieved. In each loop, we compute the next sample batch size and sample size allocation using the modified Neyman allocation (Algorithm 2), which also considers that each estimator we output in the loop combines both phase 0 and phase 1 estimators (line 12). Note that we make two small changes. (1) For online aggregation, it is desirable to periodically produce answers so it is set to the smaller of a pre-configured step-size (or it can be set to infinity if the user wants the execution to finish as fast as possible) and the estimated remaining sample size needed to achieve the confidence bound; (2) For each stratum, in order for the Central Limit Theorem to be valid, we follow the suggestions in the literature [10] to ensure at least 30 samples are fetched from each stratum, if its allocated sample size is smaller than 30 in modified Neyman allocation.

4.1

4.2

Then it is easy to prove 𝜎1 + 𝜎2 ≤ 𝜎1,2 by applying Jensen’s inequality twice (omitted for space). In addition, if the sampling distribution is not uniform, we can apply the generalized Jensen’s inequality instead, which provides the same conclusion. □ Interesting, this gives rise to a lattice structure (Figure 6) where finer stratification that breaks a coarser stratum into two finer ones always leads to lowered sampling drawing cost (i.e., second term ′ ). Thus, one can either holistically optimize 𝑐 𝑐𝑜𝑝𝑡 𝑜𝑝𝑡 with increasing 𝑘 from bottom up, which is the basis of the dynamic programming algorithm CostOpt in the next section, or start from a single query range and gradually break it down into smaller strata, which is the greedy algorithm in the next section. The main difference is the trade-off between optimization overhead and cost reduction. Topdown strategy often has lower optimization cost but possibly lower ′ reduction in 𝑐𝑜𝑝𝑡 while bottom-up strategy has higher optimization ′ . cost but more reduction in 𝑐𝑜𝑝𝑡

4

OptiAQP design and implementation

Two-phase index-assisted approximate query evaluation framework

Stratification optimization

In this subsection, we present 4 different methods for stratification optimization with varying tradeoff between optimization overhead and sampling cost reduction. Note that stratification optimization

Algorithm 1 shows our two-phase index-assisted approximate query evaluation framework, where phase 0 performs uniform sampling 5

Algorithm 2: Modified Neyman allocation (line 8 in Algorithm 1) ® per-stratum estimator variance and sampling Input: 𝜎, ® ℎ: cost 𝑛 0 : phase 0 sample size 𝜀 0 : phase 0 estimated confidence interval 𝜀, 𝛿: desired confidence bound Output: 𝑛: next batch sample size 𝑛: ® sample size allocation 1 𝑘 ← |𝜎 ®| ; Í𝑘 √ Í𝑘 𝜎𝑖 2 2 𝜎 ← 𝑗=1 ℎ𝑖 𝜎𝑖 ∗ 𝑗=1 √ℎ ;

Algorithm 3: Greedy Stratification Optimization Skip line 2 in Algorithm 1 ; Partition 𝐷 = ∪D using AB-tree and each stratum 𝐷 ′ ∈ D is the full key range of some subtrees on the left-most or right-most paths for the query range 𝐷; ′ 3 For each 𝐷 ∈ D, 𝑆 𝐷 ′ ← ΓΔ𝑛 0 𝜎𝑥 ∈𝐷 𝑇 ; Ð 4 S0 ← 𝐷 ′ ∈D 𝑆 𝐷 ′ ; 5 𝑛 0 ← 𝑛 0 − Δ𝑛 0 × | D | ; 6 Compute current cost 𝑐 = 𝑐 𝑜𝑝𝑡 as in Equation 9 ; 7 while 𝑛 0 ≥ 0 do 2 ; 8 Find 𝐷 ′ ∈ D with the largest estimator variance 𝜎𝐷 ′ 9 Remove 𝐷 ′ from D; 10 Δ𝑘 ← number of children of 𝐷 ′ ; 11 Add all subtrees rooted at 𝐷 ′ ’s children as new strata ; 12 For each new strata 𝐷 ′ , 𝑆 𝐷 ′ ← ΓΔ𝑛0 𝜎𝑥 ∈𝐷 𝑇 ; Ð 13 S0 ← S ∪ new stratum𝐷 ′ 𝑆 𝐷 ′ ; 14 𝑛 0 ← 𝑛 0 − Δ𝑛 0 × Δ𝑘 ; 15 Recompute cost 𝑐 ′ = 𝑐𝑜𝑝𝑡 as in Equation 9 ; 16 if (𝑐 − 𝑐 ′ )/𝑐 < 𝜏 then // 𝜏 is stopping threshold 17 break; 18 𝑐 ← 𝑐′ ; 19 Replace line 4 of Algorithm 1 with modified estimators for samples from strata with overlapping (see Section 4.2.1); ® 𝜎, 20 Output 𝐵, ® ℎ® for all strata in D ; 1 2

𝑖

𝑍𝛿2 𝜎 2 − 𝑛0 ; 2𝜀 2 2 2 2 2 4 𝑡2 = 𝑡1 + 𝑛 0 (𝜀 0 /𝜀 − 1) ; √

3 𝑡1 =

5 𝑛𝑡𝑜𝑡 ← min{𝑡1 +

𝑡2, step-size};

for ( 𝑗 ← 1 to 𝑘 )

6

√

𝑛 𝑗 ← max{30, Í𝑘𝜎𝑖 / ℎ√𝑖 𝑛𝑡𝑜𝑡 } 𝑖=1 𝜎𝑖 / ℎ𝑖 Í𝑘 8 Output 𝑛 = 𝑖=1 𝑛 𝑗 , 𝑛 = [𝑛 1 , 𝑛 2 , . . . , 𝑛𝑘 ] ; 7

Table 7: Summary of stratification strategies in this paper Strategy Greedy CostOpt SizeOpt Equal

Effectiveness Mostly Good Good Varies a lot Varies a lot

Extension? (§ 6) No Yes Yes Yes

Overhead Medium Higher Higher Smallest

P3

6

10

20

P3

26

6 7

9

P1

P2

10

21

24

25

10

20

P3_1 P3_2

P3_3

13

19

11 Leaf 7

then easily identify the following strata: (1) all subtrees between the two paths in the LCA (P3); (2) subtrees in all internal nodes on the left-most or right-most paths whose subtrees’ key ranges are entirely covered by the query range (P1 and P2); (3) leaf entries on the left-most and right-most paths covered by the query range (P0 – as an optimization, we exactly aggregate this stratum instead of sampling as it is small). This step is essentially free because it requires no additional index page access and can always reduce future sampling cost thanks to Theorem 3.3. To further reduce cost, we start picking existing stratum with the highest potential cost reduction and greedily break it down into a number of strata corresponding to the immediate subtrees rooted at its children. To do so, instead of drawing 𝑛 0 samples upfront from the entire query range 𝐷 in Algorithm 1 line 2, we draw a smaller sample of size Δ𝑛 0 from each stratum, which we call the per-stratum sample size and is Greedy’s parameter, and compute the estimated total cost to reach the desired confidence bound using Equation 9 under the current stratification. Then, we greedily pick one stratum 𝐷 ′ with the largest estimator variance and break it down into a number of strata corresponding to subtrees rooted at 𝐷 ′ ’s children (see Figure 9 for an example). However, as an heuristic optimization, if two or more adjacent partitions only contain the same keys (which are common for low-cardinality dimension columns in a large table, such as date), we do not further partition them. We repeat this process until the relative improvement of overall cost is smaller than a preset stopping threshold 𝜏 or we run out of the initial sample budget 𝑛 0 . Another caveat in Greedy is we need to account for samples from overlapping strata when computing the initial estimator and half-width of confidence interval (line 19). Conceptually each sample can be tagged with which stratum it is sampled from. When there are overlapping strata spanning two adjacent levels, the overlapping

26

19

...... 8

8

P0

21

22

23

......

......

......

......

Figure 8: Greedy initial strati- Figure 9: Dividing a stratum fication for query range [8, 24) with the highest variance in OptiAQP is executed during query execution and thus is counted towards the entire query execution latency – hence, we must strike a balance between bounding optimization latency and how much we can improve future sampling cost. As an overview, we summarize the trade-offs between these 4 different methods in Table 7. In general, the first two methods Greedy and CostOpt have similarly good effectiveness. The trade-off is CostOpt has slightly higher overhead but tends to optimal cost if given sufficient optimizer time while Greedy may not always produce the best solution. Note that Greedy requires using the physical sampling index to guide the optimization, and thus is limited to the single-table aggregation we discuss so far. The techniques in CostOpt, however, are extendible beyond single tables, which we will discuss in Section 6. The other two methods are baseline solutions based on existing works in the literature, and they generally perform poorly and cannot achieve optimal cost. 4.2.1 Greedy. We present a top-down structure-guided greedy algorithm for stratification optimization (Algorithm 3). We first opportunistically partition the entire range into a number of strata where each stratum is covered by some subtrees on the left-most or right-most path found during the preprocessing for query range 𝐷 (line 1). For example, Figure 8 shows the leftmost and rightmost paths for query range [8, 24) in a 3-level aggregate B-tree, we can 6

phase 1 samples

Algorithm 4: CostOpt Stratification Optimization

partition granularity d = 3 distinct keys in phase 1 samples

Sort S0 in range key order; ® 𝑚, ® 𝑆2, ® ℎ® ← collect candidate boundaries, cumulative moment 2 𝐶, ® 𝑆, 1

𝐿

statistics, and cumulative LCA heights (Def. 4.1); 3 𝐾 ← |𝑘𝑒𝑦 |; √︁ 4 𝑔1 ← [𝜎 [𝐿, 𝐶𝑖 ) ℎ[𝐿, 𝐶𝑖 ) for 0 ≤ 𝑖 ≤ 𝐾 ] ;

𝑥3

𝑘𝑒𝑦1 = 𝑥3

𝑥4

𝑥5 𝑥6

𝑘𝑒𝑦2 = 𝑥5

𝑈

𝑘𝑒𝑦3 = 𝑈

(upper) boundary keys of pre-grouped partitions

Figure 10: Partition granularity 𝑑 = 3 on a phase 1 sample with 6 distinct values results in ∑︁3 pre-grouped partitions. 𝑆 𝑗 = 𝑛0 𝑒 (𝑡)P𝑓 (𝑡)

𝑍2

min𝑓 ← 𝑟 + 𝜀 𝛿2 𝑔12 [𝐾 ] ; 6 for ( 𝑘 = 2 to 𝐾 ) 7 compute 𝑔𝑘 [𝐾 ] (Equation 10) ;

5

8

𝑥1 𝑥2

𝑡 ∈ S0 ∧𝑡 .𝑥 <𝐶 𝑗

𝑍2 min𝑓 ′ ← 𝑘𝑟 + 𝜀 𝛿2 𝑔𝑘2 [𝐾 ] ;

∑︁

𝑆2 𝑗 =

(𝑛 0𝑒 (𝑡)P𝑓 (𝑡) − 𝑆 𝑗 /𝑚 𝑗 ) 2

𝑡 ∈ S0 ∧𝑡 .𝑥 <𝐶 𝑗

if min𝑓 ′ ≥ min𝑓 then 10 𝑘 ←𝑘 −1; 11 break; 12 compute 𝑔𝑘 [𝑘..𝐾 − 1] (Equation 10); 13 𝐵 ← arg min𝐵 𝑔𝑘 [𝐾 ] ; 9

∑︁

ℎ𝑗 =

LCA height of t

𝑡 ∈ S0 ∧𝑡 .𝑥 <𝐶 𝑗

P ROPOSITION 4.1. It takes 𝑂 (1) time to compute any 𝜎 2 [𝐶 𝑗 ′ , 𝐶 𝑗 ) and ℎ[𝐶 𝑗 ′ , 𝐶 𝑗 ), with 𝑂 (𝑛 0 )-time pre-processing and 𝑂 (𝐾) space3 . ® 𝑆2 ® 𝑗 and ℎ® obviously P ROOF. Preprocessing and storage of 𝑚, ® 𝑆, take 𝑂 (𝐾) space and 𝑂 (𝑛 0 ) time after sorting. ∀0 ≤ 𝑗 ′ < 𝑗 ≤ 𝐾, the estimator variance for partition [𝐶 𝑗 ′ , 𝐶 𝑗 ) can be estimated as follows:

must stem from the greedy stratification – i.e., there’s a parent stratum and a number of child strata which collectively match with the range of the parent stratum. Suppose there are Δ𝑘 such child strata, then we take a simple arithmetic mean of all the estimators 𝐴˜ derived from the Δ𝑘 + 1 strata, which is still unbiased, and treat it as if it were derived for the parent stratum. The confidence interval 𝜀 also needs to be appropriately scaled by (Δ𝑘 + 1) 2 . In our actual implementation, we do not need to physically tag the samples. Instead, we can perform streaming aggregation with appropriate scaling factors (more details in supplemental materials), with no extra overhead. Greedy is a heuristic approach that runs very fast (for only performing a linear amount of additional computation to the number of strata). However, it may run out of budget before it is able to break down a high-variance stratum deep in the tree, and thus could sometimes result in inferior stratification than the next method below.

𝜎 2 [𝐶 𝑗 ′ , 𝐶 𝑗 ) =(𝑆2 𝑗 − 𝑆2 𝑗 ′ −1 − 𝑆 ′

𝑆 𝑗 −𝑆 ′

𝑚 𝑗 ′ −1 (𝑚 𝑗 − 𝑚 𝑗 ′ −1 )( 𝑚𝑗 ′−1 − 𝑚 𝑗 −𝑚𝑗 ′−1 ) ) 2 𝑗 −1

𝑗 −1

)

𝑚𝑗 ×

𝑚 𝑗 − 𝑚 𝑗 ′ −1 (𝑚 𝑗 − 𝑚 𝑗 ′ −1 − 1)𝑛 0

And the average LCA height can be estimated as follows: ℎ 𝑗 − ℎ 𝑗 ′ −1 ℎ[𝐶 𝑗 ′ , 𝐶 𝑗 ) = 𝑚 𝑗 − 𝑚 𝑗 ′ −1 Both have a constant complexity.

□

® we have Now, if we rewrite Equation 9 as a function over 𝐵, 𝑘 2 ∑︁ √︁ 𝑍 ® = 𝑐 0 (|𝐵| ® − 1) + 𝛿 ( 𝑐𝑜𝑝𝑡 ( 𝐵) 𝜎 [𝐵 𝑗 −1, 𝐵 𝑗 ) ℎ[𝐵 𝑗 −1, 𝐵 𝑗 )) 2 𝜀 2 𝑗=1

4.2.2 CostOpt. Next we present a bottom-up method, CostOpt (Algorithm 4). At a glance, we first use the initial sample S0 of size 𝑛 0 to obtain a set of candidate boundary keys – for now, we assume these are distinct keys from the sample S0 and the query range’s lower and upper bounds L and U. We sort and store this set in 𝐶® = [𝐶 0 = 𝐿, 𝐶 1, 𝐶 2, . . . , 𝐶𝐾 = 𝑈 ] of size 𝐾 + 1. Then we minimize 𝑐𝑜𝑝𝑡 in Equation 9 using a dynamic programming algorithm below. Before we go into the details, we note that we must be able to calculate the estimator variance and average per-sample cost2 for ® in order for calculating any subrange with boundary keys from 𝐶, 𝑐𝑜𝑝𝑡 . While these can be re-estimated using S0 on demand, this will increase the optimization cost by a factor of 𝑛 0 – which could be too expensive. Instead we maintain a few cumulative statistics in linear time and space to be able to compute them in 𝑂 (1) time. More ® and we denote specifically, let 0 ≤ 𝑗 ′ < 𝑗 ≤ 𝐾 be two indices into 𝐶, the estimator variance for range [𝐶 𝑗 ′ , 𝐶 𝑗 ) (if it is used as a stratum) as 𝜎 2 [𝐶 𝑗 ′ , 𝐶 𝑗 ) and per-sample cost as ℎ[𝐶 𝑗 ′ , 𝐶 𝑗 ). We maintain four ® 𝑆2, ® ℎ® as follows: cumulative vectors 𝑚, ® 𝑆,

While the total number of 𝐵® is exponential in 𝐾, we can derive a dynamic programming algorithm that works in 𝑂 (𝐾 3 ) in the worstcase. As analyzed previously, 𝑐𝑜𝑝𝑡 is a V-shaped function over the number of strata, denoted as 𝑘. Therefore, we can first optimize the target function 𝑐𝑜𝑝𝑡 by performing linear search with increasing 𝑘, and then solve for minimum of the second term in 𝑐𝑜𝑝𝑡 for each 𝑘. We can stop as early as we find the turning point (lines 9 - 11). To find the minimum of 𝑐𝑜𝑝𝑡 given 𝑘, it is sufficient to find the minimum of the summation inside the square – we denote that as 𝑔𝑘 =

min

∑︁

® 𝐵® |=𝑘+1∧𝐵 0 =𝐿∧𝐵𝑘 =𝑈 𝐵:| 1≤ 𝑗 ≤𝑘

√︁ 𝜎 [𝐵 𝑗 −1, 𝐵 𝑗 ) ℎ[𝐵 𝑗 −1, 𝐵 𝑗 )

Slightly overloading the notation, we define 𝑔𝑘 [ 𝑗] as the minimal value of the summation with 𝑘 partitions in the range of [𝐿, 𝐵 𝑗 ) (and thus 𝑔𝑘 = 𝑔𝑘 [𝑘]). Then we can recursively find 𝑔𝑘 [ 𝑗] as follows: √︁ 𝑔𝑘 [ 𝑗] = min{𝑔𝑘 −1 [ 𝑗 ′ ] +𝜎 [𝐵 𝑗 ′ , 𝐵 𝑗 ) ℎ[𝐵 𝑗 ′ , 𝐵 𝑗 )|𝑘 −1 ≤ 𝑗 ′ < 𝑗 } (10)

𝑚 𝑗 = |{𝑡 ∈ S0 |𝑡 .𝑥 < 𝐶 𝑗 }| 2 A stratum for arbitrary range could span multiple subtrees at different heights on

3 This is based on the classic Youngs-Cramer algorithm [32], a numerically stable

the left-most and right-most path during preprocessing in aggregate B-tree. We adopt another optimization: each sample only needs to start from a lower subtree if it falls into a subtree is on the left-most or right-most paths. Hence, the per-sample cost can be an average instead of just the height of LCA.

algorithm in PostgreSQL for computing variance and standard deviation. We explain this using uniform sampling for the ease of illustration, but it can be extended to weighted sampling by substituting 𝑚𝑖 with empirical cumulative distribution functions and appropriately scaling of 𝑆 and 𝑆2. 7

Now that any 𝜎 [𝐵 𝑗 ′ , 𝐵 𝑗 ) and ℎ [ 𝐵 𝑗 ′ , 𝐵 𝑗 ) can be computed in 𝑂 (1) time, each 𝑔𝑘 [ 𝑗] can be computed in 𝑂 (𝐾) time through dynamic programming with only 𝑂 (𝐾) space (since only the latest 𝑔𝑘 needs to be stored at a time if we compute in decreasing order on line 12), resulting in a total time of 𝑂 (𝐾 3 ). Finally, we compute the optimal partition boundaries 𝐵 on line 13 with 𝑂 (𝐾) time and 𝑂 (𝐾 2 ) space, which leverages a standard technique for tracking optimal decisions in dynamic programming and we omit for brevity. Hence, Algorithm 4 runs in 𝑂 (𝐾 3 ) time and 𝑂 (𝐾 2 ) space. Clearly, this could be very expensive if the initial sample size is large and the range predicate column 𝑥 has a high cardinality. On the flip side, the algorithm can minimize the future cost. To further limit the optimization overhead and balance the trade-off between cost and benefit, we introduce one additional hyper-parameter 𝑑, the partition granularity (Figure 10), such that the optimization will run in 𝑂 (min{𝐾 3, 𝑑 3 }) time. Specifically, we group the distinct values in S0 into up to 𝑑 groups with the same number of distinct values in each, and treat them as up to 𝑑 minimal strata that we do not further divide during stratification. As Theorem 3.3 suggests, this results in higher future sampling cost required, but meanwhile, bounds the optimization time by a constant. On one extreme when the partition granularity is 𝑑 = +∞, we place no restriction on how fine we may partition the query range. On the other extreme when the partition granularity is 𝑑 = 1, we effectively disable the stratification optimization. Later, we will show in our experiment that a moderate value of 𝑑 of tens to hundreds typically works the best.

PG SQL Parser

Approx. UDAF + index-assisted TABLESAMPLE method

Sampling access path and planning hooks PG planner

AQP Control Operator Plan Global Param Store

Post-planning fixes for AQP OptiAQP planner hook

Improved AB-tree (sampling index) PG access methods

OptiAQP operator hooks PG query executor

Aggregation

Shared Agg State Sampler Side Info

Indexassisted sampling

(a) (b) Figure 11: OptiAQP (left) components; (right) query plan S-AQP PostgreSQL plugin, pgAQP [29]. The original pgAQP plugin only supports the approximate query evaluation with indexassisted uniform sampling of user specified sample sizes. Specifically, it has two special index-assisted sampling access methods: SWRScan and SWRIndexOnlyScan, implemented as the extensible CustomScan operator. They use the sampling index over a selected range predicate column to provide sampled tuples and sampling probabilities to the upper physical plan tree nodes. Upon receiving a query with a TABLESAMPLE SWR(k) clause, its optimizer hooks rewrite the query plan to (1) inject the index-assisted access path for the sampled table; (2) modify the approximate aggregation and CLT-based confidence interval functions as aggregation of estimators. To implement the two-phase index-assisted approximate query evaluation framework in OptiAQP, we introduce TABLESAMPLE PSWR operator and significantly modified the query rewriting, planning and execution logics from pgAQP (Figure 11(left)). Following shows as an example syntax for the flight delay query in Figure 2:

4.2.3 SizeOpt. We also consider a Neyman allocation only approach to minimize sample size as an alternative. Based on Theorem 3.3, we should partition the query range into the finest strata that we can achieve. To do so, we simply collect all distinct keys from the initial sample S0 , sort them, and create a different strata with every two adjacent keys as lower and upper bounds. Then we run the standard Neyman allocation (Lemma 3.1). As Neyman allocation can be implemented using one single pass over sorted data – we can compute the estimator variances of each strata 𝜎𝑖2 in a streaming fashion over sorted samples as needed – we do not have to additionally maintain any statistics or data structure as we do in Greedy and CostOpt. Thus, SizeOpt can be cheaper at the cost of sometimes worse future sampling cost, especially when the per-strata sampling cost has a larger variance.

SELECT APPROX_COUNT(*), APPROX_COUNT_HALF_CI(0.95) FROM T TABLESAMPLE PSWR(50000, 8000, 0.95) WHERE date BETWEEN '2001-09-06' AND '2001-09-20' AND cancelled = 1;

Given this query, OptiAQP will perform the two-phase indexassisted approximate query evaluation as described in this section, with a target absolute confidence interval 8000 at confidence level 0.95 and an initial sample size 𝑛 0 = 50000. The specific stratification method used is controlled by a session-wide parameter. Internally, we generate a custom query plan as shown in Figure 11(right). The AQP control operator is a special operator that serves dual purposes (1) as a standard projection operator that applies the projection on top of aggregation; (2) to perform the stratification optimization discussed previously. We further optimize the implementation to avoid unnecessary recomputation and memory copies during runtime, by introducing two types of shared states in the plan global parameter store: (1) sampler side information object, which is used by AQP control operator to provide new partitioning and sample size information one partition at a time to the index-assisted sampling operator, as well as the index-assisted sampling operator to pass sampling probability and filter or index rejection results back to the aggregation functions; (2) shared aggregation state object for each unique aggregation expression4 which serves as the sample estimator store for phase 05 , and the standard streaming aggregation state for

4.2.4 Equal. The last method, Equal, is a baseline approach similar to [24] that does not require any apriori statistics. Strata are derived in the same way as SizeOpt. Then we do not perform any computation of estimator variances – instead, we simply allocate equal number of samples to all strata. Note that, the main differences between Equal and the stratified sampling in [24] (which we denote as ScanEqual) are: (1) Equal uses samples to create strata while ScanEqual scans the entire table for distinct keys to create strata; (2) Equal uses sampling indexes to perform index-assisted stratified sampling while ScanEqual performs scans to perform Bernoulli sampling within each stratum.

4.3

Pre-planning rewriting for AQP

4 An approximate aggregation function and the corresponding CI function share the

Implementation of OptiAQP in PostgreSQL

same aggregation state. 5 To avoid recomputing the aggregation twice for phase 0, we defer the actual aggregation in phase 0 after aggregation operator returns to the AQP control operator, when we compute the cumulative moment statistics.

We implemented OptiAQP in PostgreSQL 13.1 with AB-tree (an aggregate B-tree implementation) [34], based on an index-assisted 8

Table 12: Summary of datasets in this paper

phase 1. In addition, we also modified the original AB-tree with the various optimization previously discussed. Our current implementation only supports single-threaded execution. Nevertheless, we note that both phases are embarrassingly parallel, and thus we consider parallel execution support as a future work.

5

Flight Intel Census Lineitem

Columns 30 8 15 17

Rows 1.19 B 2.31 B 0.33 B 0.13 B

Table in PG 211.9 GB 147.1 GB 92.0 GB 38.8 GB

Sampling Index 13.0 GB 25.3 GB 3.6 GB 1.5 GB

(4) lineitem: We generated the lineitem table from the skewed TPC-H benchmark [17], with a modification to create special date ranges with higher delivery delays during the most common ship dates, to simulate holiday seasons. We generate several different datasets with varying scaling factors and number of special ranges. We query the total revenue of sales (SUM(l_extendedprice * (1 - l_discount))) in the ship date between ’1992-01-01’ and ’1998-12-31’, filtered by higher delivery delay: l_receiptdate - l_shipdate > 49.

Experiments

In this section, we empirically evaluate OptiAQP. All code and data generator/links to datasets are available in our open-source repository. The main objectives of our experiments include: • Can two-phase index-assisted approximate query evaluation achieve a desired confidence bound faster than existing non-index-assisted S-AQP approaches? • What are the overhead/benefit trade-offs among the four different stratification optimization methods? • How sensitive are our approaches to the algorithms’ parameters?

System configuration. We perform experiments on a dual-socket server with Intel Xeon Gold 6330 CPUs clocked at 2.6 GHz (max 5.1 Experiment setup frequency at 3.1 GHz in turbo mode) and 512 GB DDR4 RAM. The system is installed with Ubuntu Linux 22.04 LTS and configured Methods under comparison: with performance scaling policy. The database files and logs are • Greedy: OptiAQP with Greedy (Section 4.2.1). Default perplaced on a Samsung 990 PRO 4TB NVMe SSD. All experiments stratum sample size Δ𝑛 0 = 600 and stopping threshold 𝜏 = 0.004. are done in single-thread execution in the PostgreSQL 13.1 with • CostOpt: OptiAQP with CostOpt (Section 4.2.2). By default, AB-tree sampling index support [34] under snapshot isolation, built we set partition granularity 𝑑 = 100. using GCC 11.3 with -O3 flag. We configure all the databases with • SizeOpt: OptiAQP with SizeOpt (Section 4.2.3). 32 GB shared buffer pools, with all default optimizer flags except for • Equal: OptiAQP with Equal (Section 4.2.4). those of parallelism, which are disabled to ensure single-threaded • Uniform: Baseline index-assisted uniform sampling in pgAQP [29]. execution. For all databases, we create an AB-tree index over the As the original pgAQP only takes sample size as parameter, we range predicate column and sufficiently warm up the internal and modified its implementation to take a requested confidence bound system I/O buffer cache before experiments. We repeat each test for (𝜀, 𝛿) and an initial sample size 𝑛 0 instead. It does not perform any 10 times to account for randomness, except tests on VerdictDB which optimization after the initial sampling; rather, only runs the phase are only run for 3 times due to its long execution time. When we plot 1 loop in Algorithm 1 until the confidence bound is achieved. • ScanEqual: Baseline scan-based stratified sampling in VerdictDB [24] data points, we also plot the spread across runs using the standard whisker plots (representing 1.5 times of the difference between 25% on PostgreSQL. Since we test the online ad-hoc query settings, and 75% quantiles). we include the time for refreshing the sample sets before each 6 query . As ScanEqual only takes a sampling rate as parameter, 5.2 Latency improvement on real-world datasets we manually tune it for the requested 𝜀 with high probability. We first evaluate OptiAQP’s latency improvement over queries on • Exact: Baseline exact query in PostgreSQL with heap scan. real-world datasets, which have high value/selectivity skewness. For In all experiments, we configure all AQP methods to derive confieach experiment, we first perform exact query in PostgreSQL, and dence intervals at 1−𝛿 = 0.95 confidence level. We set preprocessing obtain the exact answers. Then we request a half-width of confactor 𝑐 0 = 100 and initial sample sizes (or maximum initial sample fidence interval 𝜀 that corresponds to 0.4%, 0.5%, 1%, 2%, 5% of the size for Greedy) 𝑛 0 = 𝑚𝑖𝑛(200 ∗ 𝑁 𝐷𝑉 , 100000), where 𝑁 𝐷𝑉 is the exact answers. Figure 13 show the query latencies. Overall, all varitotal number of distinct values of in query range – it can easily be ants of OptiAQP outperform Exact by 1 - 4 orders of magnitude. estimated using existing DBMS statistics in practice. Thanks to index-assisted sampling, our methods also significantly Datasets and queries. Dataset statistics are in Table 12. outperform scan-based sampling method ScanEqual by even a larger margin. For example, the speedup of CostOpt compared to (1) flight: the US airline on-time performance dataset [1], enlarged ScanEqual to achieve the same confidence interval is up to 98708x to 10x. We use the query in the motivating example in Section 1. on flight dataset, while the speedup of CostOpt over Exact is up (2) intel: the Intel Lab sensor data [6], enlarged to 1000x. We query to 16421x on the same dataset. the total number of readings between ’2004-02-28’ and ’2004In general, CostOpt, SizeOpt and Greedy can outperform 04-05’, filtered by temperature greater than 27 Celsius degree. baseline index-assisted sampling Uniform for lower requested 𝜀 (3) census: the 1994 US Census income dataset [19], enlarged to on these datasets and queries. Specifically, CostOpt consistently 10,000x. We query the number of surveyees who worked bespeeds up queries when compared to the baseline Uniform by tween 1 (inclusive) and 100 (exclusive) hours per week, filtered up to 3x in our tested queries. Compared to the baseline stratificaby income greater than $50𝐾. tion strategy Equal, CostOpt can achieve up to 14.6x speedup. 6 We thank the authors of [24] for generating the query templates for stratified sampling SizeOpt performs similarly to CostOpt on these datasets bewith variational subsampling for computing CI for TPC-H queries, as it was disabled in its open-source repository. We manually created the rewriting for the rest of the queries. cause the resulting strata’s LCAs are roughly at the same height and 9

3 2 1 0

0.004

0.005

0.01

0.02

requested half-width of CI ε

(a) flight

0.05

3000 2900 2800 350 220 25 22 10 8 6 4 2 0

Equal

Uniform

3000 2900 2800 230 220 10

ScanEqual

query latency (s)

Xtimeout

Greedy

query latency (s)

2600 2400 2200 380 370

SizeOpt

query latency (s)

query latency (s)

CostOpt

8 6 4 2

Exact 800 600 400 120 17 10 8 6 4 2

0

0.004

0.004

0.005

0.01

0.02

0.05

0

0.004

requested half-width of CI ε 0.005 0.01 0.02 0.05 (b) intel

0.005

0.01

0.02

0.05

requested half-width of CI ε

(c) census

requested half-width of CI ε

10

query latency (s)

query latency (s)

query latency (s)

Figure 13: Query latency with varying requested confidence interval CostOpt Greedy Uniform thus have similar per-sample cost. Greedy performs better than SizeOpt Equal Exact 80 CostOpt and SizeOpt on flight and census dataset, but worse on 100 100 70 intel dataset. The reason is Greedy can find a good stratification 80 60 80 with lower optimization overhead for flight and census, while it fails 50 60 40 to find a good stratification for intel based on the same stopping cri60 40 30 teria. Notably, Greedy even performs worse than the naïve Equal 20 20 with equal sample size per stratum on intel. This shows the better 40 10 0 robustness of CostOpt. In addition, we also verified that all meth0 10 20 40 60 1 3 5 10 20 scale factor number of high-variance query range ods except ScanEqual are returning confidence intervals below the requested confidence intervals (figures are omitted due to space (a) Varying0 Scale Factors (b) Varying high variance regions 10 20 40 60 constraint, which are available in the supplemental materials). Note Figure 14: TPC-H scale factor latency that the error bars for all methods in OptiAQP are quite small, indiTherefore, this experiment evaluates the margin for improvement cating that for these high-variance queries, OptiAQP can produce under different overall estimation variances. The results are shown quite stable estimations. in Figure 14(b). CostOpt is consistently the best method among 5.3 Scalability all. In contrast, Greedy and SizeOpt demonstrate less robustness. Exact slightly increases in time as the overall variance increases, We evaluate the scalability with increasing data size. Specifically, due to an increase of the total number of records. we generate the lineitem table using our modified TPC-H benchmark, with 3 high shipping delay date ranges and varying scale 5.5 Speedup on randomly generated queries factors. We report the query latencies across 10 runs of CostOpt, In previous experiments, we mostly show our speedup for queries SizeOpt, Greedy, Equal, Uniform, and exact query in Figwith high estimator variances to begin with, as our method is deure 14(a). We observe that CostOpt and SizeOpt consistently signed for that. However, to further demonstrate the overall perrun faster than Uniform under all scale factors. Notably, at scale formance improvement in realistic workload, we further show its factor 60, CostOpt starts to outperform SizeOpt, because the speedup over a set of randomly generated queries over these datasets. LCA heights of strata start to vary on larger datasets. Except for scale Specifically, Figure 15 shows the speedup of CostOpt, Equal, factor 10, Greedy outperforms Uniform, and the trend further Greedy, SizeOpt and Uniform on flight, census and TPC-H increases when the scale factor increases. The reason is that there lineitem table while randomly generated query ranges, where the are more records associated with the high shipping delay date ranges speedup is computed as the ratio of the query latency of other methwhen the scale factor increases, leading to even higher estimator ods to the query latency of Uniform. CostOpt is the most robust variance without partitioning. Greedy is able to optimize the esmethod while Greedy is mostly robust with a similar speedup. As timator variance through an optimized partitioning to speedup of expected, some are less optimizable due to small estimator variabout 3.4x in query latency at scale factor 60. In contrast, Equal ance, so our methods could be less effective or even cause a small shows a rapid increase in latency at scale factor 60, indicating that slow down. However, in most query ranges on these real-world and equal allocation without considering the data distribution of the large synthetic datasets, the estimator variance is high enough for these dataset is inferior to optimized stratification. Exact query latency, as methods to have sizable speedup. We also want to note that, in rare expected, increases super-linearly as scale factor increases, which is cases, there are outliers of these methods such that the slow down almost an order of magnitude higher than CostOpt and Greedy is significant. However, they are easy to mitigate in practice: As we at scale factor 60. This experiment demonstrates good scalability of can compute whether the resulting confidence interval is close to CostOpt and Greedy. what we expect for a particular stratification strategy during Phase 5.4 Impact of varying estimator variances 1, we can run Phase 1 in incremental steps similar to traditional We also vary the number of high shipping delay date ranges we genonline aggregation [11], compute the resulting confidence interval erate in the lineitem table of TPC-H (SF 20). The more high shipping and compare it against the estimated confidence interval based on delay date ranges we generate, the smaller the overall variance is Phase 0 statistics. If they differ too much, then we can immediately because a larger proportion of data will have similar higher values. switch back to Uniform to avoid further slow down. In contrast,

2.0

2.0 1.5 1.0 0.5 0.0

CostOpt

Equal

Greedy

1.5 1.0 0.5 0.0

SizeOpt

2.5 speedup over uniform

speedup over uniform

speedup over uniform

2.5

CostOpt

Equal

(a) flight

Greedy

2.0 1.5 1.0 0.5

SizeOpt

CostOpt

Equal

(b) census

Greedy

SizeOpt

(c) TPC-H

Figure 15: Speedup over uniform with randomly generated query ranges phase 1 time 3500

200000

10 1

1500

200000

1000 1

(a) Query latency

500

50 100 500 1000 1500 2000 2500

(b) Total sample size

1000 20

5000 10000

15

50000 10

100000 200000

5 1

100 1000

10000 50000

101

100000

1

(c) Optimization time

100

(d) Resulting number of partitions

Figure 16: Varying parameters for CostOpt 200 30

First Phase

Second Phase

Uniform

0.004

150

0.04

125 100

0.4 75 4

50

query latency (s)

175

query latency (s)

stopping threshold τ (%)

4e-05

20

10

0

CostOpt

SizeOpt

Greedy

Equal

25

40 30

200

600

1000

2000

per-stratum sample size ∆n0

Figure 17: Varying parameters for Greedy

Figure 18: Execution time breakdown for different stratification strategies over TPC-H

the two baseline methods Equal and SizeOpt are significantly volatile in speedup and can have larger proportion that causes slow down, because they do not have optimality guarantees.

5.6

0.005 1000 10

2000

3200

5000

initial sample size n0

(a) flight

6000

0.000

2

5 50000

70000

100000 200000 300000 500000

initial sample size n0

2

1

0

(b) TPC-H 1

0

50 100 500 1000 1500 2000 2500

partition granularity d

0

0.010

10

50000 70000query 100000 200000For 300000 500000 preprocessgood trade-offs and low latencies. CostOpt, initial sampleoverhead size n0 of tree traversals and ing factor 𝑐 0 represents the constant data structure settings. When migrating to a new environment, it requires only a one-time calibration, which is similar to other cost constants in optimizer. Partition granularity 𝑑 directly influences the 𝑂 (𝑑 3 ) dynamic programming algorithm. We find that while increasing 𝑑 can do produce slightly better estimation, it makes optimization too expensive with limited return, which leads to increasing in query latency. So, we recommend using our default settings for 𝑑. However, if a user finds that a particular 𝑑 does not work too well, then they may want to maximize 𝑑 until optimization overhead becomes unacceptable (as projected based on the 𝑂 (𝑑 3 ) complexity). In contrast, Greedy are more sensitive to its hyper-parameters because the decrease of estimator variance in each stratification step highly depends on the data distribution. In real deployment, we recommend using a reference workload or historical workload to identify the hyper-parameter that works best overall. Query latency breakdown. Figure 18 provides a breakdown of query latency under our default settings for different methods on TPC-H query. First phase represents the time for drawing samples in Phase 0 and the subsequent stratification optimization time. Second phase is the remaining time for fetching samples in Phase 1 until the approximate aggregation reaches the specified relative CI 0.01. For reference, we also show the total execution time with non-stratified method Uniform as a dashed line. In general, if we set parameters of each of the methods to have less than 1 second Phase 0 time, CostOpt and Greedy typically have good speedup compared to Uniform. The improvement of SizeOpt and Equal can vary and highly depend on datasets and query. Impact of varying initial sample size 𝑛 0 . Clearly, the initial sample size can greatly impact the distinct values we find and the accuracy of statistics we estimate for stratification optimization, which in turn can impact the effectiveness and the overall speedup. We evaluate the impact of initial sample size 𝑛 0 in OptiAQP on the flight dataset and the lineitem table (SF 20) with 3 high delay ranges. For each different

200000

50 100 500 1000 1500 2000 2500

partition granularity d

102

5000

0.015

3

3

15

Figure 19: Varying the initial sample size 𝑛 0 for CostOpt

0

number of partitions

25

preprocessing factor c0

100

DP latency (s)

preprocessing factor c0

30

0.020

15

5 103

0

0.4 0.2

partition granularity d

5

0.6

0.025

phase 0 time (s)

50000 100000

50 100 500 1000 1500 2000 2500

partition granularity d

2000

4

phase 0 time (s)

15

100000

5000 10000

0.8

0.030

phase 1 time (s)

20

50000

2500

20

20

phase 0 time (s)

25

10000

1000

4

0.035

1.0

phase 1 time (s)

30

5000

3000

phase 1 time (s)

1000

0 100

phase 0 time (right)

0.040

total sample size (103)

35

query latency (s)

0 100

preprocessing factor c0

preprocessing factor c0

40

Parameter tuning

We next investigate the impact of algorithm parameters on CostOpt and Greedy using TPC-H lineitem scale factor 20 with 3 highvariance query ranges. Hyper-parameter selection. The selection of hyper-parameters is guided by the trade-offs between optimization overhead and benefit. As demonstrated in Figure 16 and Figure 17, our methods remain robust performance across a large amount of hyper-parameters. The default settings are recommended because it consistently provides 11

𝑛 0 , we run the experiments for 10 times and plot the error bars in Figure 19. The actual time for first phase includes optimization time. As shown in the figures, as 𝑛 0 increases, the actual time for the second phase becomes more stable. However, if too many 𝑛 0 is requested, the actual time for the first time will increase without reducing much of the actual time of the second phase. In practice, if distinct values are not stored separately, we recommend setting 𝑛 0 to 𝑂˜ (𝑁 𝐷𝑉 ) such that every distinct value will have a sufficient support for accurate statistics estimation in Phase 0. However, this may become too expensive over datasets with too many distinct values, so practitioner may also want to bound the Phase 0 time with a constant cost. Hence, in our experiments, we choose the smaller of 200𝑁 𝐷𝑉 , or 100, 000 (which roughly corresponds to 1 second of Phase 0 time on average), but these can be further adjusted based on actual need and dataset. In addition, if the distinct values already exist separately, e.g., encoded in a dictionary or catalog, then our Phase 0 execution can be modified to directly draw 200 samples for each distinct value.

6

decide how many samples to fetch in the second phase. However, PilotDB uses SYSTEM sampling which in general increases sample variance by sampling large blocks one at a time. More importantly, it does not perform stratification to optimize latency for high-variance data as OptiAQP does. Our current work builds efficient IRS index designs [2, 3, 14, 23, 26, 30, 33]. We specifically build upon [29, 34] which enables concurrent approximate queries over frequent updates. Possible extensions. While this work focuses on optimizing ad-hoc single-table approximate aggregation queries where the table can be sampled with an IRS index, many different extensions are possible by combining the more general IRS and IQS (Independent Query Sampling, e.g., join sampling) indexing techniques with our design. However, all such extensions may have non-trivial design trade-offs beyond the scope of this work, and we would like to further explore these directions in the future. For example, Then this work can be naturally extended to a join aggregation query with high estimator variance. However, it is also possible that more fine-grained stratification based on the (subset of) join attributes combined with a predicate on the starting table may help reduce high variance induced by join skewness. This work can also be extended to support more general range queries such as spatial range aggregation queries leveraging SIRS (Spatial Independent Range Sampling) [30] indexes. However, in higher dimensions, how to compose larger strata from smaller strata may become a more complex optimization decision, which needs to be investigated further. This work may also extend to group-by queries with two possible strategies: (1) We stratify on a composite key of group-by and range columns on which there is an IRS index, and perform per-group two-level index-assisted approximate query evaluation; or (2) We perform rejection sampling for each group by only sampling from the range column on which there is an IRS index, similar to [20]. They are different trade-offs in performance and optimization overhead that require in-depth investigation.

Related work and possible extension

There are many works that optimize approximate query latencies in different AQP system settings. Most related are those that design stratified sampling strategies. Previous works materialize offline samples used repeatedly for approximate queries [4, 24] or draw online samples with table scans [18] , where the stratification is done at the finest granularity with each distinct value on a set of stratification columns. However, as we show in the experiments, such strategy can cause too much per-partition overhead on queries with too many distinct values. Note that these works do not utilize the optimal Neyman allocation. Closest to our work is due to Surajit et al. [7] but it was designed for materializing an offline sample given a query workload. In addition, their optimization target is also different than ours because our setting, in which we optimize for ad-hoc queries with fast indexassisted scans, significantly differs from traditional AQP system setting that scans. Their approach is to first create the fundamental regions given a workload (i.e., regions that are read entirely or not at all by all queries in the workload), and then further divide it up into finer regions to 6 levels. This approach is not feasible with indexassisted sampling because the sampling index used in index-assisted sampling restricts what strata (i.e., must be ranges for IRS index) we can efficiently sample from. [9] also performs sample size allocation but they focus on stratification on group-by and join columns and uses an auto-encoder to generate synthetic samples with similar data characteristics instead of drawing samples from the database, which will highly depends on the quality of trained autoencoder. [21, 25] takes a different route to selectively materializes subrange query results for a query workload, and combines online scan-based sampling with pre-aggregated results, which are orthogonal to this work and we may explore in the future. Machine learning based AQP systems [12, 22, 31] and deterministic AQP systems [15, 16] utilize pre-built models or data encoding to perform to perform queries over a specific query template, which can often lead to extremely low query latencies and high accuracy on the data and query trained or designed for. However, they may require specialized training or customization for workloads. PilotDB [35] also performs a similar two-phase sampling to first determine the estimator variance to

7

Conclusion

In this work, we present OptiAQP, an index-assisted sampling system which improves approximate range aggregation query latencies using a two-phase index-assisted approximate query evaluation framework with optimized stratified sampling. Experiments show OptiAQP significantly improves the approximate query cost for query ranges with high variances compared to baselines. We also discuss multiple possible extensions to handle additional query types in future work, including joins, group-by and multi-dimensional range predicates.

Acknowledgments This work is supported by NSF IIS-2339596.

References [1] 2008. Data Expo 2009: Airline on time data. https://doi.org/10.7910/DVN/ HG7NV7 [2] Peyman Afshani and Jeff M. Phillips. 2019. Independent Range Sampling, Revisited Again. In SoCG 2019. 4:1–4:13. [3] Peyman Afshani and Zhewei Wei. 2017. Independent Range Sampling, Revisited. In ESA 2017. 3:1–3:14. [4] Sameer Agarwal, Barzan Mozafari, Aurojit Panda, Henry Milner, Samuel Madden, and Ion Stoica. 2013. BlinkDB: queries with bounded errors and bounded response times on very large data. In EuroSys. 29–42. [5] Patrick. Billingsley. 2012. Probability and measure (anniversary edition. ed.). Wiley, Hoboken, N.J. 12

[30] Dong Xie, Jeff M. Phillips, Michael Matheny, and Feifei Li. 2021. Spatial Independent Range Sampling. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 2023–2035. https: //doi.org/10.1145/3448016.3452806 [31] Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2020. NeuroCard: One Cardinality Estimator for All Tables. Proc. VLDB Endow. 14, 1 (sep 2020), 61–73. https://doi.org/10.14778/3421424. 3421432 [32] Edward A. Youngs and Elliot M. Cramer. 1971. Some Results Relevant to Choice of Sum and Sum-of-Product Algorithms. Technometrics 13, 3 (1971), 657–665. https://doi.org/10.1080/00401706.1971.10488826 [33] Fangyuan Zhang, Mengxu Jiang, and Sibo Wang. 2023. Efficient Dynamic Weighted Set Sampling and Its Extension. Proc. VLDB Endow. 17, 1 (Sept. 2023), 15–27. https://doi.org/10.14778/3617838.3617840 [34] Zhuoyue Zhao, Dong Xie, and Feifei Li. 2022. AB-Tree: Index for Concurrent Random Sampling and Updates. Proc. VLDB Endow. 15, 9 (may 2022), 1835–1847. https://doi.org/10.14778/3538598.3538606 [35] Yuxuan Zhu, Tengjun Jin, Stefanos Baziotis, Chengsong Zhang, Charith Mendis, and Daniel Kang. 2025. PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees. Proc. ACM Manag. Data 3, 3, Article 198 (June 2025), 28 pages. https://doi.org/10.1145/3725335

[6] Peter Bodik, Wei Hong, Carlos Guestrin, Sam Madden, Mark Paskin, and Romain Thibaux. 2004. Intel Lab Data. https://db.csail.mit.edu/labdata/labdata.html [7] Surajit Chaudhuri, Gautam Das, and Vivek Narasayya. 2007. Optimized stratified sampling for approximate query processing. ACM Trans. Database Syst. 32, 2 (June 2007), 9–es. https://doi.org/10.1145/1242524.1242526 [8] Bolin Ding, Silu Huang, Surajit Chaudhuri, Kaushik Chakrabarti, and Chi Wang. 2016. Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee. In SIGMOD ’16. 679–694. [9] Rong Gu, Han Li, Haipeng Dai, Wenjie Huang, Jie Xue, Meng Li, Jiaqi Zheng, Haoran Cai, Yihua Huang, and Guihai Chen. 2023. ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-Oriented Sample Size Allocation and Data Generation. Proc. VLDB Endow. 16, 13 (Sept. 2023), 4216–4229. https://doi.org/10.14778/3625054.3625059 [10] Peter J. Haas. 1997. Large-Sample and Deterministic Confidence Intervals for Online Aggregation. In SSDBM ’97. 51–63. [11] J. M. Hellerstein, P. J. Haas, and H. J. Wang. 1997. Online Aggregation. In Proc. ACM SIGMOD International Conference on Management of Data. [12] Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2020. DeepDB: Learn from Data, Not from Queries! Proc. VLDB Endow. 13, 7 (mar 2020), 992–1005. https: //doi.org/10.14778/3384345.3384349 [13] D. G. Horvitz and D. J. Thompson. 1952. A generalization of sampling without replacement from a finite universe. J. Amer. Statist. Assoc. 47 (1952), 663–685. [14] Xiaocheng Hu, Miao Qiao, and Yufei Tao. 2014. Independent Range Sampling. In PODS ’14. 246–255. [15] Saehan Jo and Immanuel Trummer. 2020. BitGourmet: Deterministic Approximation via Optimized Bit Selection. In 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings. www.cidrdb.org. http://cidrdb.org/cidr2020/papers/p5-jo-cidr20.pdf [16] Saehan Jo and Immanuel Trummer. 2020. Demonstration of BitGourmet: Data Analysis via Deterministic Approximation. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo (Eds.). ACM, 2801–2804. https://doi.org/10.1145/3318464.3384709 [17] Srikanth Kandula. 2020. A Parallel Zipf-skewed Data Generator for TPC-H Benchmark. Retrieved July, 2023 from https://github.com/SrikanthKandula/ tpch_dbgen_zipf_skew [18] Srikanth Kandula, Anil Shanbhag, Aleksandar Vitorovic, Matthaios Olma, Robert Grandl, Surajit Chaudhuri, and Bolin Ding. 2016. Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters. In SIGMOD ’16. 631–646. [19] Ron Kohavi. 1996. Census Income. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5GP7S. [20] Feifei Li, Bin Wu, Ke Yi, and Zhuoyue Zhao. 2016. Wander Join: Online Aggregation via Random Walks. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD ’16). ACM, New York, NY, USA, 615–629. https://doi.org/10.1145/2882903.2915235 [21] Xi Liang, Stavros Sintos, Zechao Shang, and Sanjay Krishnan. 2021. Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 1129–1141. https://doi.org/10.1145/3448016.3457277 [22] Qingzhi Ma and Peter Triantafillou. 2019. DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models. In SIGMOD ’19. 1553–1570. [23] F. Olken. 1993. Random Sampling from Databases. Ph.D. Dissertation. University of California at Berkeley. [24] Yongjoo Park, Barzan Mozafari, Joseph Sorenson, and Junhao Wang. 2018. VerdictDB: Universalizing Approximate Query Processing. In SIGMOD ’18. 1461–1476. [25] Jinglin Peng, Dongxiang Zhang, Jiannan Wang, and Jian Pei. 2018. AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics. In SIGMOD ’18. 1477–1492. [26] Douglas B. Rumbaugh and Dong Xie. 2023. Practical Dynamic Extension for Sampling Indexes. Proc. ACM Manag. Data 1, 4, Article 254 (dec 2023), 26 pages. https://doi.org/10.1145/3626744 [27] Avi Silberschatz, Henry F. Korth, and S. Sudarshan. 2020. Database System Concepts, Seventh Edition. McGraw-Hill Book Company. https://www.dbbook.com/ [28] Yufei Tao. 2022. Algorithmic Techniques for Independent Query Sampling. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Philadelphia, PA, USA) (PODS ’22). Association for Computing Machinery, New York, NY, USA, 129–138. https://doi.org/10.1145/ 3517804.3526068 [29] Congying Wang, Nithin Sastry Tellapuri, Sphoorthi Keshannagari, Dylan Zinsley, Zhuoyue Zhao, and Dong Xie. 2023. Approximate Queries over Concurrent Updates. Proc. VLDB Endow. 16, 12 (aug 2023), 3986–3989. https://doi.org/10. 14778/3611540.3611602 13

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181