-Aggregation is a database operation that aims to provide basic analytic capabilities by partitioning source data into several groups and computing some function on values belonging to the same group. Nowadays it is common in databases, and especially in the OLAP domain, which is a primary venue for column-stores. In this paper we propose a novel approach to the design of an aggregation operator inside a column-store system. The core of our approach is an analysis of predicates in the HAVINGclause that allows the runtime pruning of groups. We employ monotonicity and codomain analysis in order to detect groups in which predicates would never be satisefid. Eventually, we aim to save I/O and CPU costs by discarding groups as early as possible. We start by providing a high-level overview of our approach and describe its use-cases. Then, we provide a short introduction into our system and describe a straightforward implementation of an aggregation operator. Next, we provide theoretical foundations for our approach and present an improved algorithm. Finally, we present an experimental validation of our approach inside PosDB - a distributed, disk-based column-store engine that features late materialization and block-oriented processing. Experiments using an SSD drive show that our approach can provide up to 5 times improvement over the naive version.
Aggregation is rather common in databases and, in fact, it
forms the basis of OLAP. For example, the TPC-H
benchmark [
Column-stores are a relatively recent development [
In this paper we propose a novel technique intended for optimizing the processing of aggregation queries inside column-stores. Our approach concerns analysis of predicates in the HAVING-clause and relies on a simple idea: terminate processing of a group if, judging by the already processed data, the HAVING-predicate will never be satisfied. Thus, it should be possible to save I/O and CPU costs related to evaluation of aggregation functions located in the SELECT-clause.
In order to illustrate this, let us consider the following example (adapted from Q1 of TPC-H):
l r e t u r n f l a g , l l i n e s t a t u s , SUM( l q u a n t i t y ) a s sum qty , SUM( l e x t e n d e d p r i c e ) a s s u m b a s e p r i c e , SUM( l e x t e n d e d p r i c e ∗ ( 1 − l d i s c o u n t ) ) a s s u m d i s c p r i c e , SUM( l e x t e n d e d p r i c e ∗ ( 1 − l d i s c o u n t ) ∗ ( 1 + l t a x ) ) a s s u m c h a r g e , AVG( l q u a n t i t y ) a s a v g q t y , AVG( l e x t e n d e d p r i c e ) a s a v g p r i c e , AVG( l d i s c o u n t ) a s a v g d i s c ,
COUNT( ∗ ) a s c o u n t o r d e r FROM l i n e i t e m GROUP BY l r e t u r n f l a g , l l i n e s t a t u s HAVING SUM( l q u a n t i t y ) < 1 0 0 0 0 0 0 ORDER BY l r e t u r n f l a g , l l i n e s t a t u s In this case naive processing can be organized as follows: 1) Rewrite query in the form
SELECT ∗
2) Move aggregation expressions from the HAVING-clause to the SELECT-clause of the original query if they are not already present there, and perform aggregation as usual (e.g. hash-based aggregation); 3) Filter aggregation results by the HAVING-predicate that uses columns introduced in the step 2 and then eliminate extra columns by projection.
However, if during the second step the partial sum of l_quantity for some group exceeds 1000000, it is possible to discard this group immediately. In the column-store case, this approach will allow us to save some I/O and CPU costs.
At first glance, it may seem that the benefits of our approach are rather limited, because joins incur more significant costs than aggregation. However, there are aggregation queries which do not involve joins, e.g. Q1 and Q6 in TPC-H. More importantly, all queries in this benchmark try to mimic reallife scenarios, and, thus, they represent an actual business need. This indicates that similar queries can be encountered in reallife workloads.
Overall, there are several types of use-cases when our approach would be of use: 1) Aggregation queries that do not involve joins: aggregation running on a denormalized table, a materialized view, solely on a fact table and so on; 2) A case where join operators produce roughly as much data as they receive or even more, so aggregation requires comparable time for processing.
Unlike row-stores, column-stores offer an opportunity to
reap the fruits of such optimization with ease. In this paper
we consider this problem in the context of PosDB [
Overall, the contribution of this paper is the following: 1) Theoretical basis for on-the-fly pruning of groups during the evaluation of the aggregation operator. 2) An experimental study of our approach using PosDB.
This paper is organized as follows. In Section II we present a short introduction into PosDB and the aggregation operator. Section III provides definitions and presents formal grounds for our analysis. In Section IV we describe an optimized version of the aggregation algorithm. Next, in Section V we present an experimental evaluation and discuss current results. Then, we survey existing aggregation studies in Section VI. Finally, in Section VII we conclude our study and present future work.
In this section we will give a minimally sufficient
description of PosDB internals, and present the naive aggregation
algorithm. For a comprehensive description of the whole
system, see [
Query processing in PosDB is built upon the pull-based
Volcano model [
Currently, PosDB supports late materialization only. This
is a query execution strategy for column-stores that aims to
defer the tuple reconstruction and materialization until as late
as possible. In order to implement this strategy, a special
intermediate representation, based on the join index from the
study [
Some operators (e.g. joins) require not only positions, but also attribute values. Therefore, in order to obtain attribute values from the join index we employ a special entity — a reader. There are two types of readers in PosDB that are essential for understanding of our current study: • ColumnReader is a reader for retrieving values of an individual attribute. In fact, there are several subtypes of ColumnReader, since our system supports data partitioning and data distribution. • SyncReader is a reader for retrieving values of several attributes related to the same join index in a row-byrow manner. It is implemented as a wrapper for several ColumnReaders.
HAVING count = 1 In this query, the three following components should be distinguished: 1) GROUP BY clause. It contains a list of attributes that are used to define groups. We will call these attributes grouping parameters. 2) SELECT clause. It contains a list of expressions that we will call aggregation expressions. In our study we assume that only grouping parameters are allowed on the top level. Other attributes should be wrapped in aggregate functions, such as MAX, SUM, etc. Currently, some database systems allow not only grouping parameters, but arbitrary attributes on the top level as well, e.g., MySQL and SQLite1. However, such understanding of aggregation is unambiguous only if there is a functional dependency between grouping parameters and “raw” attributes on the top-level of SELECT clause. Otherwise, it leads to uncertainty and, consequently, to implementation-dependent behavior. It should be noted that such understanding of aggregation is not prevalent in the database community since it contradicts the SQL’92 standard (see sections 6.5 and 7.9). 3) HAVING clause. It contains a predicate that is applied to the data regarding the whole group and is used to filter resulting rows.
Before describing the aggregation algorithm used in PosDB, we should formally describe the admissible aggregation expressions. They are inductively defined as follows. Definition 1 A stateless expression is either: • an identifier of an attribute belonging to a relation that was mentioned in a FROM-clause (free variable); • a constant of a supported data type (constant); • A + B, A − B, A · B, A ÷ B, An, where A and B are admissible numeric stateless expressions and n is a non-negative integer (arithmetic expressions);
mysql-selecting-a-column-not-in-group-by
An aggregation expression is either: • an identifier of any attribute belonging to grouping pa
rameters; • a constant of a supported data type; • COUNT(E), MAX(E), MIN(E), SUM(E), AVG(E), where E is an admissible stateless expression. In this case, we will call such expressions aggregates. • A + B, A − B, A · B, A ÷ B, An, where A and B are admissible numeric aggregation expressions and n is a non-negative integer. In this case, we will call such expressions aggregation arithmetic expressions.
an individual copy should be maintained for each group) and a new entry is added to the hash table. Otherwise, it already exists in the hash table and, thus, the corresponding aggregates should be updated.
In the end of the aggregate evaluation stage, each individual entry of the hash table contains computed aggregates for a particular group. Next, at the result generation stage, the hash table is iterated through. During this process, the algorithm computes aggregation expressions, constructs full tuples and returns them to a parent operator.
If the considered query contains a HAVING-clause then a parent operator performing filtering of results is added. In
PosDB this operator is implemented as filtering on tuples.
Other types of expressions can be added later in a similar manner.
Both stateless and aggregation expressions may appear in III. PRUNING POSSIBILITY ANALYSIS the SELECT clause. Joint usage of these expressions on the top The core of the proposed approach is HAVING-predicate level of the SELECT clause is prohibited: stateless expressions analysis. It consists of two components: monotonicity analshould be used if there is no aggregation, and aggregation ysis and codomain analysis. Let us begin with an inductive expressions otherwise. As can be seen from the definition, definition of admissible (correct in the context of a HAVINGstateless expressions are also used as subexpressions for ag- clause and currently supported) predicates. gregates. Definition 3 The following predicates are admissible:
Let us now consider the semantics of stateless expressions. • A = B, A 6= B, A > B, A < B, A ≤ x ≤ B, where Here, we consider an abstract processing scheme rather than A, B and x are admissible aggregation expressions or focusing purely on row- or column-stores. Consider row-by- constants (atomic predicates). row scanning of a relation. A stateless expression is a “pure • P ∧ Q, P ∨ Q, where P and Q are admissible predicates function”: it takes a row as an input and produces a result (compound predicates). immediately. On the other hand, aggregation expression can produce a result only when the whole group is processed. Other types of predicates can be added later in the same During group processing, values of aggregates that compose an way. Currently, we support numeric types only. aggregation expression should be updated for each incoming A. Monotonicity analysis row. These updates lead to change of the “current” value of the aggregation expression involving these aggregates. Thus, Consider an aggregation expression from a fixed group. during processing aggregation expressions pass through a As we mentioned earlier, throughout the execution of the sequence of intermediate states. Monotonicity analysis of such aggregation algorithm the “current” value of this expression sequences is a central part of the current study. changes several times and, thus, forms a sequence. Often we
Concerning implementation, we must emphasize that in can guarantee monotonicity of these sequences by analyzing case of a disk-based column-store, expressions should use the properties of the corresponding aggregates. Therefore, we an interface which allows on-demand column reading. This can talk about monotonicity of aggregation expressions itself. requirement is essential in order to reduce the number of disk Aggregates are monotonic in the following way: accesses. In PosDB, SyncReader provides this functionality. • COUNT(E) is weakly increasing;
Let us now turn to the aggregation operator itself. Its inputs • MAX(E) is weakly increasing;
are grouping parameters and a list of aggregation expressions. • MIN(E) is weakly decreasing;
The local state [
In a general case, aggregation is an operation that requires – not monotonic otherwise; full materialization of the corresponding relation, i.e. it should • AVG(E) is not monotonic. process all data in order to produce the first result. Thus, it Note that during algorithm execution values of grouping can be decomposed into two stages: aggregate evaluation and parameters belonging to a particular group do not change. result generation. The aggregate evaluation stage is the core Values of constant expressions behave in a similar manner. of the operator. It is organized as a loop over logical “rows” Thus, the former should be considered as constants as well. (provided by the corresponding reader in case of PosDB). On If we denote weakly increasing aggregation expressions as each iteration of the loop a new key-tuple is created and the E↑ and weakly decreasing ones as E↓, then we can derive hash table is probed. If a corresponding record is not found, monotonicity of aggregation arithmetic expressions according then the aggregates are cloned (they have a state, therefore, to the following rules: to assess their monotonicity. This analysis consists of checking whether E ≥ 0, E ≤ 0 or E ≡ 0. It can be carried out using codomain analysis of corresponding stateless numeric expressions.
Our codomain analysis is based on well-known interval
analysis [
The following operators of interval arithmetic are used to compute the codomain of an arithmetic expression: if n is even,
x1 ≤ 0, x2 ≤ 0 if n is even, x1 ≤ 0, x2 ≤ 0
n is even, x1 ≤ 0, x2 ≥ 0 if n is even,
x1 ≥ 0, x2 ≥ 0 if n is odd • E1↑ + E↑, E1↑ − E2↓ are weakly increasing;
2 • E1↓ + E↓, E1↓ − E2↑ are weakly decreasing;
2 • if E1 ≥ 0 and E2 ≥ 0: – E1↑ · E2↑, E1↑ ÷ E2↓ are weakly increasing; – E1↓ · E2↓, E1↓ ÷ E2↑ are weakly decreasing; • if E1 ≥ 0 and E2 ≤ 0: – E1↑ ÷ E2↑, E1↑ · E2↓ are weakly decreasing; – E1↓ ÷ E2↓, E1↓ · E2↑ are weakly increasing; • if E1 ≤ 0 and E2 ≥ 0: – E1↑ ÷ E2↑, E1↑ · E2↓ are weakly increasing; – E1↓ ÷ E2↓, E1↓ · E2↑ are weakly decreasing; • if E1 ≤ 0 and E2 ≤ 0: – E1↑ · E2↑, E1↑ ÷ E2↓ are weakly decreasing; – E1↓ · E2↓, E1↓ ÷ E2↑ are weakly increasing; • for other cases, we cannot guarantee monotonicity of the
result.
Proof of these statements obviously follows from the properties of arithmetic operations on inequalities.
Let us now turn to HAVING-predicate analysis. We start with atomic predicates and then generalize our approach to the compound ones.
The following predicate types allow to terminate processing of a particular group earlier if the corresponding termination condition is satisfied:
E↓ > E↑ E↓ ≤ E↑ E↑ < E↓ E↓ ≥ E↑ E↓ = E↑ E↓ < E↑
E↑ = E↓ E↓ > E↑
The first column contains the predicate type, which is essentially a predicate with free variables. In contrast, the second column contains an “implementation” of the corresponding predicate where intermediate values of aggregates are substituted instead of being free variables. In our study we refer to both of these entities as predicates. Thus, Definition 4 Potentially terminating predicate is a predicate that has a termination condition.
Definition 5 Terminating predicate is a predicate that has its termination condition fulfilled by a particular instance of data.
The following statements hold for compound predicates: • P1 ∧ P2 is potentially terminating, if P1 or P2 is potentially terminating. • P1 ∧ P2 is terminating, if P1 or P2 is terminating. • P1 ∨ P2 is potentially terminating, if both P1 and P2 are potentially terminating.
• P1 ∨ P2 is terminating, if both P1 and P2 are terminating.
As shown earlier, there are several important cases — aggregate SUM(E), aggregation arithmetic expressions containing multiplication and division — that require additional analysis Information about possible values of attributes is taken from the meta-information based on the CHECK-constraints stored in the catalog.
Concerning endpoint inclusion, it should be noted that inclusion is kept if and only if operation is applied to included endpoints. Otherwise, an endpoint is excluded.
Note that there is an issue with the interval arithmetics. Estimates obtained by its application strongly depend on the form of an expression. For example, consider the expression x/(1−x), for which two different intervals can be obtained — one for x/(1 − x) and another for 1/(1/x − 1). However, it is guaranteed that all intervals would contain the range of the analyzed function.
Currently, it is unclear whether it would be useful to employ more complicated (and more resource-consuming) approaches to get better estimates in case of our algorithm.
Another aspect that should be discussed is the input of operators. Codomain may be described not by a single interval, but by a union of several disjunctive intervals. Thus, operators may also produce unions of several intervals. In our study we restrict ourselves to supporting only a single interval per attribute.
We are now ready to present an optimized version of the aggregation algorithm described in the section II-B. Our algorithm combines both aggregation and filtering into a single operator. Therefore, the interface of the aggregation operator was slightly changed — now it also receives a HAVINGpredicate as a parameter. If there is no HAVING-clause in the query, then a non-optimized version should be run.
The optimized algorithm tracks the state of the predicate for each group, so several changes should be introduced into the hash table. Now this table contains entries that are structures with the following fields: • A list of aggregates that should be evaluated eventually (as in the baseline version). Here we will call such aggregates primary aggregates. • A copy of the HAVING-predicate to check whether it is necessary to further process the current group. • A list of aggregates from the HAVING-predicate that are used to compute the state of the corresponding HAVINGpredicate copy. We will call them auxiliary aggregates.
The optimized algorithm requires a new stage — a predicate analysis stage. At this stage, the HAVING-predicate is analyzed using the approaches described in the previous section. If it is potentially terminating, then it will be possible to perform earlier termination of processing of any group when the corresponding termination condition is satisfied for this group. Otherwise, the baseline version of aggregation algorithm should be used.
Optimization itself is mostly applied at the aggregate evaluation stage. As in the baseline version of algorithm, we iterate through the logical “rows” (provided by SyncReader in PosDB). Inside the loop we check if the corresponding group already exists in the hash table. However, now we need to check the state of the predicate copy as well. If there is no such group, we clone the predicate, extract the aggregates (auxiliary) from it, update their values and evaluate the predicate. If the predicate is not terminating yet, then we also clone the primary aggregates and add a record to the hash table. If the predicate is already terminating, then we delete the cloned predicate and add a “tombstone” into the hash table instead of a normal record.
If the corresponding group is already in the hash table, and it was not “tombstoned”, then we update the values of both primary and auxiliary aggregates from the predicate, and check the status of the predicate. If it becomes terminating, then we delete the found record and replace it with a “tombstone”. Otherwise, we just proceed to the next logical “row” without fetching values needed for computation of both primary and auxiliary aggregates. It is this step of the algorithm that makes I/O and CPU savings possible.
At the result generation stage, we iterate over the hash table, skip groups that have been “tombstoned” and check the HAVING-predicate for the remaining groups. Next, tuples constructed from records that satisfy the predicate are passed to the parent operator.
Experimental evaluation was performed on a PC with the following characteristics: 4-core Intel R CoreTM i5-7300HQ CPU @ 2.50GHz, 8 Gb RAM, running Linux Ubuntu 16.04.1 LTS. 128GB KINGSTON RBU-SNS SSD was used as storage.
Test queries are based on Q1 from TPC-H. The first four of them have the following form:
l r e t u r n f l a g , l l i n e s t a t u s , SUM( l q u a n t i t y ) a s sum qty , SUM( l e x t e n d e d p r i c e ) a s s u m b a s e p r i c e , SUM( l e x t e n d e d p r i c e ∗ ( 1 − l d i s c o u n t ) ) a s s u m d i s c p r i c e , SUM( l e x t e n d e d p r i c e ∗ ( 1 − l d i s c o u n t ) ∗ ( 1 + l t a x ) ) a s s u m c h a r g e , AVG( l q u a n t i t y ) a s a v g q t y , AVG( l e x t e n d e d p r i c e ) a s a v g p r i c e , AVG( l d i s c o u n t ) a s a v g d i s c ,
COUNT( ∗ ) a s c o u n t o r d e r FROM l i n e i t e m GROUP BY l r e t u r n f l a g , l l i n e s t a t u s HAVING having-clause where having-clause is • l_linestatus = ’O’ for Q1; • having count(*) < 100000 for Q2; • (l_returnflag = ’A’) OR (l_linestatus = ’O’)) AND (MIN(l_tax) > MAX(l_discount) for Q3; • SUM(l_quantity) < 1000000 for Q4.
These queries are designed for studying how optimization is affected by different kinds of predicates. All of them are supposed to demonstrate significant performance improvement due to avoidance of unnecessary I/O in the optimized algorithm.
We have also designed the Q5 query for a first, rough appraisal of the overhead introduced by our algorithm. Q5 is an example of a query where no performance improvement could be gained due to absence of I/O savings. In this query, all columns have to be read regardless of predicate values.
For each combination of an algorithm and a scale factor (SF) we have run all the aforementioned queries 10 times and calculated the 95% confidence intervals. The full results of the experiments are presented in the Table I. We have also visualized the results for SF = 50 in Fig. 1 to make it more illustrative.
As we can see from Table I, there is no considerable performance dependency on the predicate complexity — queries Q2– Q4 show very close results on all scale factors. On the other side, as expected, optimization efficiency significantly depends Algorithm Optimized Baseline Optimized Baseline Optimized Baseline Optimized Baseline Optimized Baseline
SF = 1 2087 ms ±2% 3305 ms ±2% 841 ms ±1% 3293 ms ±3% 687 ms ±1% 3458 ms ±2% 766 ms ±1% 3511 ms ±2% 510 ms ±1% 504 ms ±1% on the predicate selectivity and on the time when pruning can be performed. We suppose that the difference between Q1 and Q2–Q4 should be explained by this fact. Detailed analysis of these factors was postponed for the future.
Evaluation of Q5 shows that the overhead introduced by our algorithm is rather small (about 2–3%) and does not depend on the scale factor.
Concerning the dependency on the scale factor, it is looking close to linear for all the considered queries.
According to reference [
These studies can be roughly classified into the following
groups:
1) Optimization of aggregation queries. In these papers
authors study how to efficiently process aggregation
queries mostly by using various plan transformations. In
the study [
Its goal is to provide the database user with means to control the execution of aggregation. The proposed use-case is the following: while processing data, progressively refine an approximate answer and provide its running confidence intervals. Unlike plain aggregation, where the user passively waits for the answer, this approach allows the user to terminate a query early if they deem the approximate results acceptable. Originally, this approach was proposed in reference [20], and later, many studies have followed. For example, the study [21] extends this idea onto nested queries that contain aggregation and also proposes a multithreaded model. Next, the paper [22] addresses parallel aggregation on a cluster of computers. 4) Another group of papers studied approximate processing of aggregation queries. Unlike the previous approach, this type of studies does not imply user intervention during the processing. Approximate aggregation query answering using sampling was studied in reference [23]. The idea of this paper is to index outlying values in order to reduce the approximation error. The study [24] addresses the problem of approximate time-constrained query evaluation. The authors propose an algorithm for evaluating count-containing aggregation queries that can be stopped if the desired error range is obtained or the pre-specified time limit is exceeded. 5) Novel models of aggregation and novel aggregations operators. Horizontal aggregation is proposed in reference [25]. Its idea is to generate a new table, where a separate column for each unique value of columns belonging to aggregation expression is generated. At the same time, the rows of this table contain all unique values from the columns of GROUP BY list. The authors of this paper propose not only semantics of this operation, but also language extension and discuss query execution. Similarly, reference [26] describes two aggregation-like operators: PIVOT and UNPIVOT. The former transforms a series of rows into a series of fewer rows with additional columns. Data in one source column is used to generate the new column for a row, and another source column is used as the data for that new column. The latter performs the inverse operation by removing a number of columns and creating additional rows. In studies [27], [28] novel aggregation operators are proposed. The former study considers embedding of grouping variables [29] into SQL queries. Grouping variables is a tool that allows to specify additional conditions for the desired groups. It is much more expressive than HAVING-clause. The latter study proposes a generalization of an aggregation operator that allows formation of aggregation groups without requiring an ordering of the data relation.
In this paper we have proposed a novel approach to evaluation of aggregation in column-stores. We employ monotonicity and codomain analysis in order to invoke early termination that allows to save CPU and I/O costs. To validate our idea, we have implemented the designed algorithms inside a disk-based column-store query engine. Preliminary experiments show that our approach can improve query performance up to 5 times over the naive algorithm.
In our future studies we plan to evaluate performance dependency on the number of groups, data distribution, selectivity and complexity of the predicate. We also going to assess the overhead introduced by our algorithm in more detail. Other future studies may include combining proposed operator with other approaches to aggregation (e.g. partial aggregation approach), applying it for in-memory systems, and exploring opportunities offered by novel hardware.