Approximate Calculation of Window Aggregate Functions via Global Random Sample

Window functions are part of the SQL:2003 standard in order to accommodate complex analytical queries. The general form of a window aggregate function is as follows:

where Agg can be any of the standard aggregation functions such as SUM, AVG, COUNT and expression is the attribute to be aggregated upon. The OVER clause defines the aggregation window, inside which PARTITION BY, ORDER BY and \(frame\_clause\) determine the properties of the window jointly(In fact, a frame is just a window). Examples include MAX(velocity) OVER (PARTITION BY roadid,carid ORDER BY time\(\_\)t ROWS BETWEEN 10 PRECEDING AND 10 FOLLOWING), which means we monitor the maximum speed of the car within 20 min of each time in a car monitoring application.

Figure 1 illustrates the process of determining the range of a window. Firstly, the PARTITION BY clause divides the tuples into disjoint groups according to the attribute columns in \(partition\_list\). Nextly, attributes in \(order\_list\) are used to sort tuples in each partition. Finally, we confirm the bounds of the frame, i.e., the range of tuples to aggregate upon, for the current tuple by \(frame\_clause\) and invoke the related aggregate function to compute the aggregation result. The first two processes are called reordering, and the last one is called sequencing.

For each row in a partition, a window frame identifies two bounds in the window and only the rows between these two bounds are included for aggregate calculation. There are two frame models, ROWS and RANGE. In the ROWS model, the boundaries of a frame can be expressed as how many rows before or after the current row belong to the frame; in the RANGE model, the boundaries are specified as a range of values with respect to the value in the current row [10].

Like traditional aggregate functions, a window aggregate function is composed of a state transition function transfun and an optional final calculation function finalfun. To compute the final result of an aggregate function, a transition value is maintained for the current internal state of aggregation, which is continuously updated by transfun for each new tuple seen. After all input tuples in the window have been processed; the final aggregate result is computed using finalfun. Then we determine the frame boundaries for the next tuple in the partition and do the same work again.

Sampling has been widely used in various fields of computer science, such as statistics, model training, query processing. With the advent of Big Data era, sampling is gaining unprecedented popularity in various applications, since it is prohibitively expensive to compute an exact answer for each query, especially in an interactive system. Sampling techniques provide an efficient alternative in applications that can tolerate small errors, in which case exact evaluation becomes an overkill.

Online aggregation [12] a classic approach based on sampling provides users with continuous updates of aggregation results as the query evaluation proceeds. It is attractive since estimates can be timely returned to users, and the accuracy improves with time as the evaluation proceeds.

There are four components in a typical online aggregation system, as shown in Fig. 2. The first one is the approximate result created by the system. The second and third parts consist of reliability and confidence interval which reflect the accuracy and feasibility of the result. The progress bar is the last part that reports the schedule information for the current task. All values improve over time until they meet a user’s needs.

Since the results generated by sampling are approximate, it is important to calculate an associated confidence interval. For a simple aggregate query on one table, like SELECT op (expression) FROM table WHERE predicate, it’s easy to achieve online aggregation by continuously sampling from the target table. Standard statistical formulas can help us get unbiased estimators and estimate the confidence interval. A lot of previous work [13‐16] have made great contributions on this problem.

A window function is evaluated in two phases: resorting and sequencing. Accordingly, existing approaches for evaluating window functions mainly fall into two categories.

Cao et al. [7] improved the full sort technique for evaluating window functions by proposing more competitive hash-sort and segment-sort algorithms. Then Cao et al. [8] proposed a novel method for the multi-sorting operations in one query. They found that most computation time is spent in sorting and partitioning when window size is small. And they proved that it is an NP-hard problem to find the optimal sequence to avoid repeated sorting for multiple window functions in one query and provided a heuristic method. Other earlier studies, such as [9, 17, 18] and [19], made a lot of contributions with regard to the ORDER BY clause and GROUP BY clause and they proposed optimization algorithms based on either the function dependencies or the reuse of the intermediate results.

Besides, there are several recent works about window operators and their functions. Leis et al. [10] proposed a general execution framework of window functions which is more suitable for memory-based systems. An novel data structure named segment tree is proposed to store aggregates for sub-ranges of an entire group, which helps reduce redundant calculations. However, the approach is only suitable for distributive and algebraic aggregates. Wesley et al. [11] proposed an incremental method for three holistic windowed aggregates. And Song et al. [20] provided an general optimization method based on shared computing, which uses temporary windows to store the shared results and only need a small amount of memory. However, all the above works are toward exact evaluation and they face performance bottlenecks when processing massive data.

Sampling has been used in approximate query evaluation [21, 22], data stream processing [23], statistical data analysis [24] and other fields [25, 26]. Moreover, as the classic application of sampling, Hellerstein et al. [12] first proposed the concept of online aggregation. Since then, research on online aggregation has been actively pursued. Xu et al. [14] studied online aggregation with group by clause and Wu et al. [16] proposed a continuous sampling algorithm for online aggregation over multiple queries. Qin and Rusu [27] extended online aggregate to distributed and parallel environments. Li et al. [13] studied online aggregation on the queries with join clauses. These techniques based on sampling give us an opportunity to calculate the aggregate easily. In general, sampling is required to be uniform and independent in order to get reasonable results, but both [13] and [28] proved that a non-uniform or a non-independent samples can be used to estimate the result of an aggregate.

There are many other valuable works [29‐32] on query optimization and sampling, but none of them deals with the problem of window functions. In this paper, we study how to evaluate online aggregate for queries involving and extend the existing work [1] for new application scenarios. What’s more, work [33] extended the definition of window functions for graph computing and proposed three different types of graph window: unified window, K-hop window and topological window. This provides a way for us to achieve cross-domain development of the window in the future.

As mentioned in Sect. 2, window functions in commercial database systems are generally evaluated over a windowed table in a two-phase manner. In the first phase, the windowed table is reordered into a set of physical window partitions, each of which has a distinct value of the PARTITION BY key and is sorted on the ORDER BY key. The generated window partitions are then pipelined into the second phase, where the window function is sequentially invoked for each row over its window frame within each window partition.

Firstly, for each window \(W_{i}\) in the partition, we initialize the parameters of \(W_{i}\) and place the read pointer at the start of the window (Line 3). Then determine whether the start position of the current window is equal to that of the previous one. If the condition is true, we can reuse the previous result and assign it to \(W_{i}.V\) (Line 5). Nextly, we place the read pointer at the end of the previous window and traverse all tuples from \(W_{i-1}.t\) to \(W_{i}.t\). If it is false, we just traverse all tuples from \(W_{i}.h\) to \(W_{i}.t\). Finally, return the result and prepare for the next window.

An example of the processing of window functions is shown in Fig. 3, where the aggregate function is summation and the frame model adopted is ROW. The entire table is partitioned and sorted according to \(attr\_2\) and makes summation on \(attr\_1\). Red brackets in Fig. 3 represent windows. Then we find that W2 begins with the same tuple as W1 and the result of W2 is incrementally updated. However, the start tuple is different between W2 and W3, we have to traverse all the tuples to evaluate a result.

For a table with N tuples, if we use a general window function query, like SUM(\(attr\_1\)) OVER ( PARTITION BY attr_2 ORDER BY attr_2 ROWS BETWEEN S / 2 PRECEDING AND S / 2 FOLLOWING). In most cases, we must use S tuples to get one result for each tuple. And the total execution cost is \(\Theta (NS)\) without considering partitioning and sorting.

The evaluation cost of the window functions is proportional to the number of tuples in the table and in each window. Thus, the execution time increases sharply as the data size grows. Since the table size N is a constant, we propose to reduce the number of tuples checked in each window, S, by sampling.

NRS is the base algorithm in paper [1], which using native random sampling in each window. Here, we only introduce the improved version named ISR in the paper. Since a large number of common tuples are shared by adjacent windows, ISR reuses the sampling results of the previous window.

Algorithm 2 shows the procedure of incremental sampling. Firstly, we reuse the previous structure \(SW_{i-1}\) (Line 4). Then tuples, which are beyond the range of current window, are removed from \(SW_{i}\) (Line 6). Function \(remove\_head\) is used to remove the first item in \(SW_{i}.indexarr\) and update \(SW_{i}.sh\) depending on how many tuples are removed. Then we use a temporary structure \(T\_SW\) to store the indexes of newly sampled tuples in the range from \(SW_{i}.indexarr[SW_{i}.st]\) to \(W_{i}.t\) (Line 9–11). Next, we append the indexes in \(T\_SW.indexarr\) to \(SW_{i}\) and update \(SW_{i}.st\) (Line 12). Finally, we aggregate the tuples in \(SW_{i}\) to estimate the final result (Line 13–14).

The first improved algorithm is designed for window in RANGE mode, named range-based global sampling algorithm (RGSA). As we discuss above, range mode is able to ensure that the data is clean, which is friendly in statistical calculations. And we don’t need to adjust the window boundaries, because the nature of the range window ensures that the exact boundary can be found. So all operations are the same as dealing with normal windows. For more information, refer to algorithm 3. Here we just give the basic version.

Besides, because RGSA has the same characteristics as native algorithm, we can use some improved methods to optimize RGSA. Almost all the optimized algorithms in work [10, 11, 20] can be used to RGSA with simple change.

Another improved algorithm is designed for window in ROW mode. As we discuss above, there exist dirty tuples in ROW window. And these tuples influence the accuracy of estimated results. Hence, in order to reduce or eliminate adverse effects, an intuitive idea is that we can dynamically adjust the window boundaries according to the sampling rate. For example, suppose the sampling rate is 0.5, we can reduce the window size by half. Sometimes this simple method can work, but the fatal flaw is that the dirty data can’t be completely avoided. As shown in Fig. 5, although we have changed the size of window from 2 to 1, there exists a dirty tuple (tuple 8.5).

In order to eliminate dirty data completely, we design row-labeled sampling algorithm (RLSA). This algorithm doesn’t sample from the origin data directly, but sample from the sorted data after first phase, when each tuple is in the final correct position. Unlike the RGSA algorithm, a new column of attributes is added to each sampling data to record the subscript position. Then the boundaries of the window can be determined accurately according to the subscript value. In other words, a window function in row mode is converted to range mode based on subscript.

Algorithm 4 shows the details of RLSA. Firstly, the data table T is partitioned and sorted according to the normal process (Line 1). After that, the position of each data in T will not be changed and we generate a sub-table ST by random sampling with rate s (Line 2). It should be explained that not only the source data are sampled, but also the index of the sampled data in table S is recorded. Then we calculate the boundaries of each window based on each row in ST and get the subscript of r (Line 3-6). Next, traverse data from the current row to the both sides until the subscript exceeds window range and invoke \(adjust\_transfunc\) for each row that is traversed (Line 7–15). In fact, it’s a range style computing process. Finally, return the final results (Line 16).

Figure 6 shows the new diagram of previous example by using RLSA. To make it easy to understand, we mark the subscript of each data in dashed frame. Then we can find that a new subscript attribute is added to the subset( i.e., the sample set) to identify the original position of each tuple. In this example, the current window is based on tuple 7 whose subscript is 4 and the size of window is 2, so the subscript of low bound and high bound is 2 and 6. Next we just need to find the tuples whose subscript satisfy boundary constrains (i.e., greater than or equal to 2, less than or equal to 6). Finally, 4 tuples (i.e., 6,7,7.8,8) are found in the subset and all of them belong to the original window. Hence, the dirty data can be completely avoided by this method.

Consider a window W containing m tuples, denoted by \(t_1,t_2,\ldots ,t_m\). Suppose v(i) is an auxiliary function whose result is equal to m times the value of \(t_i\) when applied to \(t_i\). Then we define a new function \(F \left( f \right)\), and the extra result \(\alpha\) of sum function is equal to \(F \left( v \right)\).Now we sample tuples from window W and get a sequence of tuples, denoted as \(T_1,T_2,\ldots ,T_n\), after n tuples are selected. Then estimated result \(\overline{Y_n}\) can be calculated by using Eq. (2). \(\overline{Y_n}\) is the average value of the samples and is equal to \(T_n \left( v \right)\).The formula of sample variance is shown as Eq. (3). \(T_n(f)\) is the average value of the samples. So the sample variance \(\widetilde{\sigma ^{2}}\) is equal to \(T_{n,2}(v)\).According to central limit theorem, we can conclude that the left-hand side follows normal distribution with mean 0 and variance 1.After we get \(\overline{Y_n}\) and \(\widetilde{\sigma ^{2}}\), we havewhere \(\Psi\) is the cumulative distribution function of the \(\mathcal {N}(0,1)\) random variable. Finally, we define \(z_p\) as the \(\frac{p+1}{2}\)-quantile of the normal distribution function and set Eq. (5) equal to p. Then a confidence interval is computed asOther aggregation functions, such as COUNT, AVG, VAR, have the similar proof process. And [13, 15] give more details about the proofs of a few common aggregation functions. In addition, Haas and Hellerstein [28] proved that we could estimate the aggregate by using a non-independent and uniform sample method.

We run PostgreSQL on a computer of Lenovo with an Intel (R) Core (TM) i5-4460M CPU at 3.20 Hz, whose system has 24 GB 1600 MHz DDR3 of RAM. Then we implemented IRS and NRS on it. Since PostgreSQL does not fully support window functions in RANGE mode, we achieve RGSA with C++ and use gcc 5.3 as a compiler. Besides, RLSA can be regarded as special range calculation, so we also implemented it with C++.

In this section, we use the following query template in our experiments to demonstrate our implementation:

where aggf are aggregation functions, such as sum, avg, count, frame model is ROW, and the bounds of window are limited by pre and fel.