On-the-Fly Filtering of Aggregation Results in Column-Stores Anastasia Tuchina Valentin Grigorev George Chernishev Saint Petersburg State University Saint Petersburg State University Saint Petersburg State University Email: anastasia.i.tuchina@gmail.com Email: valentin.d.grigorev@gmail.com JetBrains Research Email: chernishev@gmail.com Abstract—Aggregation is a database operation that aims to SELECT provide basic analytic capabilities by partitioning source data into l returnflag , l linestatus , several groups and computing some function on values belonging SUM( l q u a n t i t y ) a s sum qty , to the same group. Nowadays it is common in databases, and especially in the OLAP domain, which is a primary venue for 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 , column-stores. 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 ) ) In this paper we propose a novel approach to the design of as sum disc price , an aggregation operator inside a column-store system. The core 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 ) ∗ of our approach is an analysis of predicates in the HAVING- ( 1 + l t a x ) ) a s sum charge , clause that allows the runtime pruning of groups. We employ monotonicity and codomain analysis in order to detect groups in AVG( l q u a n t i t y ) a s a v g q t y , which predicates would never be satisfied. Eventually, we aim to 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 , save I/O and CPU costs by discarding groups as early as possible. AVG( l d i s c o u n t ) a s a v g d i s c , We start by providing a high-level overview of our approach COUNT( ∗ ) a s c o u n t o r d e r and describe its use-cases. Then, we provide a short introduction FROM l i n e i t e m into our system and describe a straightforward implementation of an aggregation operator. Next, we provide theoretical foun- GROUP BY l r e t u r n f l a g , l l i n e s t a t u s dations for our approach and present an improved algorithm. HAVING SUM( l q u a n t i t y ) < 1000000 Finally, we present an experimental validation of our approach ORDER BY l r e t u r n f l a g , l l i n e s t a t u s inside PosDB — a distributed, disk-based column-store engine that features late materialization and block-oriented processing. In this case naive processing can be organized as follows: Experiments using an SSD drive show that our approach can 1) Rewrite query in the form provide up to 5 times improvement over the naive version. SELECT ∗ I. I NTRODUCTION FROM ( original query without having ) Aggregation is rather common in databases and, in fact, it WHERE having-clause forms the basis of OLAP. For example, the TPC-H bench- mark [1] does not contain a single query which does not 2) Move aggregation expressions from the HAVING-clause involve aggregation. Therefore, in the early 80’s the scientific to the SELECT-clause of the original query if they are community recognized the importance of efficient aggregation not already present there, and perform aggregation as processing. While there are hundreds of studies concerning usual (e.g. hash-based aggregation); aggregation in row-stores, the column-store processing is less 3) Filter aggregation results by the HAVING-predicate that explored. uses columns introduced in the step 2 and then eliminate Column-stores are a relatively recent development [2]. Un- extra columns by projection. like classic approaches, where all attributes of every record However, if during the second step the partial sum of are kept together, column-stores employ the opposite idea — l_quantity for some group exceeds 1000000, it is possible they store each attribute separately. This leads to a number of to discard this group immediately. In the column-store case, challenges as well as opportunities in query processing. this approach will allow us to save some I/O and CPU costs. In this paper we propose a novel technique intended At first glance, it may seem that the benefits of our ap- for optimizing the processing of aggregation queries inside proach are rather limited, because joins incur more significant column-stores. Our approach concerns analysis of predicates costs than aggregation. However, there are aggregation queries in the HAVING-clause and relies on a simple idea: terminate which do not involve joins, e.g. Q1 and Q6 in TPC-H. More processing of a group if, judging by the already processed data, importantly, all queries in this benchmark try to mimic real- the HAVING-predicate will never be satisfied. Thus, it should life scenarios, and, thus, they represent an actual business need. be possible to save I/O and CPU costs related to evaluation This indicates that similar queries can be encountered in real- of aggregation functions located in the SELECT-clause. life workloads. In order to illustrate this, let us consider the following Overall, there are several types of use-cases when our example (adapted from Q1 of TPC-H): approach would be of use: 53 1) Aggregation queries that do not involve joins: aggre- a reader. There are two types of readers in PosDB that are gation running on a denormalized table, a materialized essential for understanding of our current study: view, solely on a fact table and so on; • ColumnReader is a reader for retrieving values of an 2) A case where join operators produce roughly as much individual attribute. In fact, there are several subtypes data as they receive or even more, so aggregation re- of ColumnReader, since our system supports data quires comparable time for processing. partitioning and data distribution. Unlike row-stores, column-stores offer an opportunity to • SyncReader is a reader for retrieving values of several reap the fruits of such optimization with ease. In this paper attributes related to the same join index in a row-by- we consider this problem in the context of PosDB [3]–[5] — row manner. It is implemented as a wrapper for several a distributed disk-based column-store engine that features late ColumnReaders. materialization and block-oriented processing. However, we B. Baseline version of aggregation algorithm think that the proposed solution is sufficiently universal — almost any column-store system can benefit from similar Consider the following SQL query: optimization, regardless of its underlying architecture. Also, SELECT T.A , T.B , COUNT(*) as count , despite the current columnar focus of our study, we believe that MAX(T.C) - MIN(T.C) as diff our approach is applicable to hybrid systems and in-memory FROM T DBMSes as well. GROUP BY T.A , T.B Overall, the contribution of this paper is the following: HAVING count = 1 1) Theoretical basis for on-the-fly pruning of groups during In this query, the three following components should be the evaluation of the aggregation operator. distinguished: 2) An experimental study of our approach using PosDB. 1) GROUP BY clause. It contains a list of attributes that This paper is organized as follows. In Section II we present are used to define groups. We will call these attributes a short introduction into PosDB and the aggregation operator. grouping parameters. Section III provides definitions and presents formal grounds 2) SELECT clause. It contains a list of expressions that for our analysis. In Section IV we describe an optimized we will call aggregation expressions. In our study we version of the aggregation algorithm. Next, in Section V we assume that only grouping parameters are allowed on present an experimental evaluation and discuss current results. the top level. Other attributes should be wrapped in Then, we survey existing aggregation studies in Section VI. aggregate functions, such as MAX, SUM, etc. Currently, Finally, in Section VII we conclude our study and present some database systems allow not only grouping param- future work. eters, but arbitrary attributes on the top level as well, II. Q UERY P ROCESSING IN P OS DB e.g., MySQL and SQLite1 . However, such understand- In this section we will give a minimally sufficient descrip- ing of aggregation is unambiguous only if there is a tion of PosDB internals, and present the naive aggregation functional dependency between grouping parameters and algorithm. For a comprehensive description of the whole sys- “raw” attributes on the top-level of SELECT clause. tem, see [3], [5]. Several surveys of column-store technology Otherwise, it leads to uncertainty and, consequently, to are presented in references [2], [6]–[8]. implementation-dependent behavior. It should be noted that such understanding of aggregation is not prevalent in A. Basics the database community since it contradicts the SQL’92 Query processing in PosDB is built upon the pull-based standard (see sections 6.5 and 7.9). Volcano model [9] with block-oriented processing. According 3) HAVING clause. It contains a predicate that is applied to to this model, each query is represented by a tree whose nodes the data regarding the whole group and is used to filter are physical operators and edges are data flows. Each operator resulting rows. supports an iterator interface, and data is passed between Before describing the aggregation algorithm used in PosDB, operators in blocks. we should formally describe the admissible aggregation ex- Currently, PosDB supports late materialization only. This pressions. They are inductively defined as follows. is a query execution strategy for column-stores that aims to defer the tuple reconstruction and materialization until as late Definition 1 A stateless expression is either: as possible. In order to implement this strategy, a special • an identifier of an attribute belonging to a relation that intermediate representation, based on the join index from the was mentioned in a FROM-clause (free variable); study [10], was introduced. This representation links records of • a constant of a supported data type (constant); • A + B, A − B, A · B, A ÷ B, A , where A and B n different tables together. It is used to pass blocks of positional data between operators. are admissible numeric stateless expressions and n is a Some operators (e.g. joins) require not only positions, but non-negative integer (arithmetic expressions); also attribute values. Therefore, in order to obtain attribute 1 https://stackoverflow.com/questions/1023347/ values from the join index we employ a special entity — mysql-selecting-a-column-not-in-group-by 54 Definition 2 An aggregation expression is either: an individual copy should be maintained for each group) and • an identifier of any attribute belonging to grouping pa- a new entry is added to the hash table. Otherwise, it already rameters; exists in the hash table and, thus, the corresponding aggregates • a constant of a supported data type; should be updated. • COUNT(E), MAX(E), MIN(E), SUM(E), AVG(E), In the end of the aggregate evaluation stage, each individual where E is an admissible stateless expression. In this entry of the hash table contains computed aggregates for a case, we will call such expressions aggregates. particular group. Next, at the result generation stage, the hash • A + B, A − B, A · B, A ÷ B, A , where A and B n table is iterated through. During this process, the algorithm are admissible numeric aggregation expressions and n is computes aggregation expressions, constructs full tuples and a non-negative integer. In this case, we will call such returns them to a parent operator. expressions aggregation arithmetic expressions. If the considered query contains a HAVING-clause then a parent operator performing filtering of results is added. In Other types of expressions can be added later in a similar PosDB this operator is implemented as filtering on tuples. manner. Both stateless and aggregation expressions may appear in III. P RUNING 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 anal- should 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 HAVING- stateless 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. Aggregates are monotonic in the following way: requirement is essential in order to reduce the number of disk • COUNT(E) is weakly increasing; accesses. In PosDB, SyncReader provides this functionality. • MAX(E) is weakly increasing; Let us now turn to the aggregation operator itself. Its inputs • MIN(E) is weakly decreasing; are grouping parameters and a list of aggregation expressions. • SUM(E) is The local state [9] of the aggregation operator is a hash table with tuples composed of grouping parameters used as keys – weakly increasing if E ≥ 0, and lists of aggregates extracted from aggregation expressions – weakly decreasing if E ≤ 0, used as values. – constant, if E ≡ 0, 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: 55 • E1↑ + E2↑ , E1↑ − E2↓ are weakly increasing; to assess their monotonicity. This analysis consists of checking ↓ ↓ ↓ ↑ • E1 + E2 , E1 − E2 are weakly decreasing; whether E ≥ 0, E ≤ 0 or E ≡ 0. It can be carried out • if E1 ≥ 0 and E2 ≥ 0: using codomain analysis of corresponding stateless numeric – E1↑ · E2↑ , E1↑ ÷ E2↓ are weakly increasing; expressions. – E1↓ · E2↓ , E1↓ ÷ E2↑ are weakly decreasing; Our codomain analysis is based on well-known interval • if E1 ≥ 0 and E2 ≤ 0: analysis [11]. We support open, closed and half-closed inter- – E1↑ ÷ E2↑ , E1↑ · E2↓ are weakly decreasing; vals. Their endpoints can be infinite. Constants are represented – E1↓ ÷ E2↓ , E1↓ · E2↑ are weakly increasing; by degenerate intervals. • if E1 ≤ 0 and E2 ≥ 0: The following operators of interval arithmetic are used to compute the codomain of an arithmetic expression: – E1↑ ÷ E2↑ , E1↑ · E2↓ are weakly increasing; – E1↓ ÷ E2↓ , E1↓ · E2↑ are weakly decreasing; • (x1 , x2 ) + (y1 , y2 ) = (x1 + y1 , x2 + y2 ) • if E1 ≤ 0 and E2 ≤ 0: • (x1 , x2 ) − (y1 , y2 ) = (x1 − y2 , x2 − y1 ) – E1↑ · E2↑ , E1↑ ÷ E2↓ are weakly decreasing; • (x1 , x2 ) · (y1 , y2 ) = min(x1 y1 , x1 y2 , x2 y1 , x2 y2 ),  – E1↓ · E2↓ , E1↓ ÷ E2↑ are weakly increasing;  1 1 max(x1 y1 , x1 y2 , x2 y1 , x2 y2 ) • for other cases, we cannot guarantee monotonicity of the (  x2 x1  , ), if x1 x2 > 0  (−∞, 1 ), if x < 0, x = 0 result. 1 x1 1 2 • (x ,x ) = Proof of these statements obviously follows from the prop- 1 2   ( , +∞), if x1 = 0, x2 > 0 1   x2 erties of arithmetic operations on inequalities. undefined otherwise Let us now turn to HAVING-predicate analysis. We start 1 • (x1 , x2 ) ÷ (y1 , y2 ) = (x1 , x2 ) · (y ,y ) with atomic predicates and then generalize our approach to  1 2   [1, 1], if n = 0 the compound ones.      n n n is even, The following predicate types allow to terminate processing   (x , x ), if   2 1 x1 ≤ 0, x2 ≤ 0 of a particular group earlier if the corresponding termination      condition is satisfied:   n is even, n  (x2 , x1 ),n if Predicate type Termination condition x ≤ 0, x2 ≤ 0 n • (x1 , x2 ) =  1 E↓ > E↑ E↓ ≤ E↑     n is even,    0, max(xn1 , xn2 ) , if E↑ < E↓ E↓ ≥ E↑   x 1 ≤ 0, x2 ≥ 0    E↓ = E↑ E↓ < E↑   n is even,  (xn1 , xn2 ),  if E↑ = E↓ E↓ > E↑   x 1 ≥ 0, x2 ≥ 0   n n The first column contains the predicate type, which is (x1 , x2 ), if n is odd essentially a predicate with free variables. In contrast, the Concerning endpoint inclusion, it should be noted that second column contains an “implementation” of the corre- inclusion is kept if and only if operation is applied to included sponding predicate where intermediate values of aggregates endpoints. Otherwise, an endpoint is excluded. are substituted instead of being free variables. In our study Note that there is an issue with the interval arithmetics. we refer to both of these entities as predicates. Thus, Estimates obtained by its application strongly depend on the Definition 4 Potentially terminating predicate is a predicate form of an expression. For example, consider the expression that has a termination condition. 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 Definition 5 Terminating predicate is a predicate that has its is guaranteed that all intervals would contain the range of the termination condition fulfilled by a particular instance of data. analyzed function. The following statements hold for compound predicates: Currently, it is unclear whether it would be useful to employ • P1 ∧ P2 is potentially terminating, if P1 or P2 is poten- more complicated (and more resource-consuming) approaches tially terminating. to get better estimates in case of our algorithm. • P1 ∧ P2 is terminating, if P1 or P2 is terminating. Another aspect that should be discussed is the input of • P1 ∨ P2 is potentially terminating, if both P1 and P2 are operators. Codomain may be described not by a single interval, potentially terminating. but by a union of several disjunctive intervals. Thus, operators • P1 ∨P2 is terminating, if both P1 and P2 are terminating. may also produce unions of several intervals. In our study we restrict ourselves to supporting only a single interval per B. Codomain analysis attribute. As shown earlier, there are several important cases — aggre- Information about possible values of attributes is taken from gate SUM(E), aggregation arithmetic expressions containing the meta-information based on the CHECK-constraints stored multiplication and division — that require additional analysis in the catalog. 56 IV. O PTIMIZED AGGREGATION A LGORITHM V. E XPERIMENTS We are now ready to present an optimized version of Experimental evaluation was performed on a PC with the the aggregation algorithm described in the section II-B. Our following characteristics: 4-core Intel R CoreTM i5-7300HQ algorithm combines both aggregation and filtering into a single CPU @ 2.50GHz, 8 Gb RAM, running Linux Ubuntu 16.04.1 operator. Therefore, the interface of the aggregation operator LTS. 128GB KINGSTON RBU-SNS SSD was used as storage. was slightly changed — now it also receives a HAVING- Test queries are based on Q1 from TPC-H. The first four predicate as a parameter. If there is no HAVING-clause in the of them have the following form: query, then a non-optimized version should be run. SELECT The optimized algorithm tracks the state of the predicate for l returnflag , l linestatus , each group, so several changes should be introduced into the SUM( l q u a n t i t y ) a s sum qty , hash table. Now this table contains entries that are structures 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 , with the following fields: 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 list of aggregates that should be evaluated eventually as sum disc price , (as in the baseline version). Here we will call such 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 ) ∗ aggregates primary aggregates. ( 1 + l t a x ) ) a s sum charge , • A copy of the HAVING-predicate to check whether it is AVG( l q u a n t i t y ) a s a v g q t y , necessary to further process the current group. 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 , • A list of aggregates from the HAVING-predicate that are AVG( l d i s c o u n t ) a s a v g d i s c , used to compute the state of the corresponding HAVING- COUNT( ∗ ) a s c o u n t o r d e r predicate copy. We will call them auxiliary aggregates. FROM l i n e i t e m The optimized algorithm requires a new stage — a pred- GROUP BY l r e t u r n f l a g , l l i n e s t a t u s icate analysis stage. At this stage, the HAVING-predicate HAVING having-clause is analyzed using the approaches described in the previous where having-clause is section. If it is potentially terminating, then it will be possible to perform earlier termination of processing of any group • l_linestatus = ’O’ for Q1; when the corresponding termination condition is satisfied for • having count(*) < 100000 for Q2; this group. Otherwise, the baseline version of aggregation • (l_returnflag = ’A’) OR algorithm should be used. (l_linestatus = ’O’)) AND Optimization itself is mostly applied at the aggregate eval- (MIN(l_tax) > MAX(l_discount) for Q3; uation stage. As in the baseline version of algorithm, we • SUM(l_quantity) < 1000000 for Q4. iterate through the logical “rows” (provided by SyncReader These queries are designed for studying how optimization in PosDB). Inside the loop we check if the corresponding is affected by different kinds of predicates. All of them are group already exists in the hash table. However, now we supposed to demonstrate significant performance improvement need to check the state of the predicate copy as well. If due to avoidance of unnecessary I/O in the optimized algo- there is no such group, we clone the predicate, extract the rithm. aggregates (auxiliary) from it, update their values and evaluate We have also designed the Q5 query for a first, rough the predicate. If the predicate is not terminating yet, then we appraisal of the overhead introduced by our algorithm. Q5 also clone the primary aggregates and add a record to the hash is an example of a query where no performance improvement table. If the predicate is already terminating, then we delete could be gained due to absence of I/O savings. In this query, the cloned predicate and add a “tombstone” into the hash table all columns have to be read regardless of predicate values. instead of a normal record. SELECT l r e t u r n f l a g , l l i n e s t a t u s , If the corresponding group is already in the hash table, and FROM l i n e i t e m it was not “tombstoned”, then we update the values of both GROUP BY l r e t u r n f l a g , l l i n e s t a t u s primary and auxiliary aggregates from the predicate, and check HAVING l r e t u r n f l a g = ’A ’ the status of the predicate. If it becomes terminating, then we delete the found record and replace it with a “tombstone”. For each combination of an algorithm and a scale factor Otherwise, we just proceed to the next logical “row” without (SF) we have run all the aforementioned queries 10 times and fetching values needed for computation of both primary and calculated the 95% confidence intervals. The full results of auxiliary aggregates. It is this step of the algorithm that makes the experiments are presented in the Table I. We have also I/O and CPU savings possible. visualized the results for SF = 50 in Fig. 1 to make it more At the result generation stage, we iterate over the hash illustrative. table, skip groups that have been “tombstoned” and check As we can see from Table I, there is no considerable perfor- the HAVING-predicate for the remaining groups. Next, tuples mance dependency on the predicate complexity — queries Q2– constructed from records that satisfy the predicate are passed Q4 show very close results on all scale factors. On the other to the parent operator. side, as expected, optimization efficiency significantly depends 57 TABLE I E XPERIMENTS RESULTS ( MILLISECONDS ) Query Algorithm SF = 1 SF = 5 SF = 10 SF = 25 SF = 50 Optimized 2087 ms ±2% 10515 ms ±2% 20743 ms ±1% 53145 ms ±1% 104899 ms ±1% Q1 Baseline 3305 ms ±2% 16589 ms ±3% 32615 ms ±1% 83419 ms ±2% 159588 ms ±2% Optimized 841 ms ±1% 3830 ms ±2% 8217 ms ±1% 20150 ms ±1% 45833 ms ±2% Q2 Baseline 3293 ms ±3% 16564 ms ±3% 32389 ms ±1% 83336 ms ±2% 158751 ms ±2% Optimized 687 ms ±1% 3634 ms ±1% 8163 ms ±1% 20086 ms ±1% 45734 ms ±1% Q3 Baseline 3458 ms ±2% 17276 ms ±3% 33843 ms ±1% 87288 ms ±2% 164593 ms ±2% Optimized 766 ms ±1% 3717 ms ±1% 8217 ms ±1% 20078 ms ±1% 45754 ms ±1% Q4 Baseline 3511 ms ±2% 17651 ms ±3% 34626 ms ±1% 88972 ms ±2% 168037 ms ±2% Optimized 510 ms ±1% 2500 ms ±1% 4980 ms ±1% 12693 ms ±1% 25994 ms ±1% Q5 Baseline 504 ms ±1% 2439 ms ±1% 4873 ms ±1% 12465 ms ±1% 25666 ms ±1% ·105 BY up). The former allows to reduce the number of en- Algorithm tries that need to be processed by the join operator, and, Baseline consequently, to improve the overall query processing 1.5 Optimized performance. The latter is of interest when the query operates on a view containing a GROUP BY. A similar transformation is proposed in study [15]. The core of this Time (ms) 1 approach is to pre-aggregate data using any column set that functionally determines the table being aggregated. In study [16] authors integrate subquery and aggregation processing techniques by proposing a set of shared 0.5 primitives. Then these primitives are used to generate optimized plans. The problem of aggregation query op- timization in the OLAP environment was considered in 0 reference [17]. In this paper, an analysis of an approach Q1 Q2 Q3 Q4 Q5 called Hierarchical Pre-Grouping is performed and a number of transformations is proposed and analyzed. Fig. 1. Comparison of algorithm performance for SF=50 2) Optimization of evaluation of an individual aggregation operator. These studies aim to organize processing in the most efficient way. There are two basic methods for on the predicate selectivity and on the time when pruning can performing an aggregation [9] — hashing and sorting. be performed. We suppose that the difference between Q1 and According to reference [9] sorting was considered in Q2–Q4 should be explained by this fact. Detailed analysis of study [12]. Among contemporary studies it is essential these factors was postponed for the future. to note Blink [18], where authors consider aggregating Evaluation of Q5 shows that the overhead introduced by our compressed data and reference [19] where hardware- algorithm is rather small (about 2–3%) and does not depend efficient multi-threaded aggregation in column-store was on the scale factor. presented. However, none of these studies analyzed Concerning the dependency on the scale factor, it is looking aggregation predicates in order to improve individual close to linear for all the considered queries. operator performance. 3) A relatively recent approach called online aggregation. VI. R ELATED WORK Its goal is to provide the database user with means According to reference [9], the processing of aggregation to control the execution of aggregation. The proposed queries has been studied at least since the end of the 70’s [12]. use-case is the following: while processing data, pro- Nowadays, it is a mature area of research which features gressively refine an approximate answer and provide its hundreds of papers [13]. running confidence intervals. Unlike plain aggregation, These studies can be roughly classified into the following where the user passively waits for the answer, this groups: approach allows the user to terminate a query early 1) Optimization of aggregation queries. In these papers if they deem the approximate results acceptable. Orig- authors study how to efficiently process aggregation inally, this approach was proposed in reference [20], queries mostly by using various plan transformations. In and later, many studies have followed. For example, the study [14], [15], the authors propose two transfor- the study [21] extends this idea onto nested queries mations: eager aggregation (moving a GROUP BY down that contain aggregation and also proposes a multi- through join) and lazy aggregation (moving a GROUP threaded model. Next, the paper [22] addresses parallel 58 aggregation on a cluster of computers. approach), applying it for in-memory systems, and exploring 4) Another group of papers studied approximate processing opportunities offered by novel hardware. of aggregation queries. Unlike the previous approach, this type of studies does not imply user intervention R EFERENCES during the processing. Approximate aggregation query answering using sampling was studied in reference [23]. [1] Transaction Processing Performance Council, “TPC BenchmarkTM H The idea of this paper is to index outlying values in Standard Specification Revision 2.17.3.” [Online]. Available: http: order to reduce the approximation error. The study [24] //www.tpc.org/tpc documents current versions/pdf/tpc-h v2.17.3.pdf [2] Stavros Harizopoulos, Daniel Abadi, and Peter Boncz, “Column- addresses the problem of approximate time-constrained Oriented Database Systems,” 2009. [Online]. Available: http://nms. query evaluation. The authors propose an algorithm for csail.mit.edu/∼stavros/pubs/tutorial2009-column stores.pdf evaluating count-containing aggregation queries that can [3] G. Chernishev, V. Galaktionov, V. Grigorev, E. Klyuchikov, and K. Smirnov, “PosDB: A Distributed Column-Store Engine,” in Per- be stopped if the desired error range is obtained or the spectives of System Informatics, A. K. Petrenko and A. Voronkov, Eds. pre-specified time limit is exceeded. Cham: Springer International Publishing, 2018, pp. 88–94. 5) Novel models of aggregation and novel aggregations [4] ——, “A study of PosDB Performance in a Distributed Environment,” operators. Horizontal aggregation is proposed in refer- in Proceedings of the 2017 Software Engineering and Information Management, ser. SEIM ’17, 2017. ence [25]. Its idea is to generate a new table, where [5] ——, “PosDB: An Architecture Overview,” Programming and a separate column for each unique value of columns Computer Software, vol. 44, no. 1, pp. 62–74, Jan 2018. [Online]. belonging to aggregation expression is generated. At the Available: https://doi.org/10.1134/S0361768818010024 [6] Daniel Abadi, Peter Boncz, and Stavros Harizopoulos, The Design same time, the rows of this table contain all unique val- and Implementation of Modern Column-Oriented Database Systems. ues from the columns of GROUP BY list. The authors of Hanover, MA, USA: Now Publishers Inc., 2013. [Online]. Available: this paper propose not only semantics of this operation, http://db.csail.mit.edu/pubs/abadi-column-stores.pdf [7] G. Chernishev, “The design of an adaptive column-store system,” but also language extension and discuss query execution. Journal of Big Data, vol. 4, no. 1, p. 5, Mar 2017. [Online]. Available: Similarly, reference [26] describes two aggregation-like https://doi.org/10.1186/s40537-017-0069-4 operators: PIVOT and UNPIVOT. The former trans- [8] S. Idreos, F. Groffen, N. Nes, S. Manegold, K. S. Mullender, and M. L. forms a series of rows into a series of fewer rows Kersten, “MonetDB: Two Decades of Research in Column-oriented Database Architectures,” IEEE Data Eng. Bull., vol. 35, no. 1, with additional columns. Data in one source column pp. 40–45, 2012. [Online]. Available: http://sites.computer.org/debull/ is used to generate the new column for a row, and A12mar/monetdb.pdf another source column is used as the data for that new [9] G. Graefe, “Query Evaluation Techniques for Large Databases,” ACM Comput. Surv., vol. 25, no. 2, pp. 73–169, Jun. 1993. [Online]. column. The latter performs the inverse operation by Available: http://doi.acm.org/10.1145/152610.152611 removing a number of columns and creating additional [10] Z. Li and K. A. Ross, “Fast Joins Using Join Indices,” The VLDB rows. In studies [27], [28] novel aggregation operators Journal, vol. 8, no. 1, pp. 1–24, Apr. 1999. [Online]. Available: http://dx.doi.org/10.1007/s007780050071 are proposed. The former study considers embedding [11] G. Alefeld and G. Mayer, “Interval analysis: theory and applications,” of grouping variables [29] into SQL queries. Grouping Journal of Computational and Applied Mathematics, vol. 121, no. 1-2, variables is a tool that allows to specify additional pp. 421–464, Aug. 2000. [12] R. Epstein, “Techniques for Processing of Aggregates in Relational conditions for the desired groups. It is much more ex- Database Systems,” Univ. of California, Berkeley, Tech. Rep., 01 1979. pressive than HAVING-clause. The latter study proposes [13] I. F. V. Lopez, R. T. Snodgrass, and B. Moon, “Spatiotemporal aggregate a generalization of an aggregation operator that allows computation: a survey,” IEEE Transactions on Knowledge and Data formation of aggregation groups without requiring an Engineering, vol. 17, no. 2, pp. 271–286, Feb 2005. [14] W. P. Yan and P.-A. Larson, “Eager Aggregation and Lazy Aggregation,” ordering of the data relation. in Proceedings of the 21th International Conference on Very Large Data Bases, ser. VLDB ’95. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1995, pp. 345–357. [Online]. Available: VII. C ONCLUSION http://dl.acm.org/citation.cfm?id=645921.673154 [15] P. A. Larson, “Data reduction by partial preaggregation,” in Proceedings In this paper we have proposed a novel approach to evalua- 18th International Conference on Data Engineering, 2002, pp. 706–715. tion of aggregation in column-stores. We employ monotonicity [16] C. Galindo-Legaria and M. Joshi, “Orthogonal Optimization of and codomain analysis in order to invoke early termination that Subqueries and Aggregation,” in Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, ser. allows to save CPU and I/O costs. To validate our idea, we SIGMOD ’01. New York, NY, USA: ACM, 2001, pp. 571–581. have implemented the designed algorithms inside a disk-based [Online]. Available: http://doi.acm.org/10.1145/375663.375748 column-store query engine. Preliminary experiments show that [17] A. Tsois and T. Sellis, “The Generalized Pre-grouping Transformation: Aggregate-query Optimization in the Presence of Dependencies,” in our approach can improve query performance up to 5 times Proceedings of the 29th International Conference on Very Large over the naive algorithm. Data Bases - Volume 29, ser. VLDB ’03. VLDB Endowment, In our future studies we plan to evaluate performance depen- 2003, pp. 644–655. [Online]. Available: http://dl.acm.org/citation.cfm? id=1315451.1315507 dency on the number of groups, data distribution, selectivity [18] V. Raman, G. Swart, L. Qiao, F. Reiss, V. Dialani, D. Kossmann, and complexity of the predicate. We also going to assess I. Narang, and R. Sidle, “Constant-Time Query Processing,” in the overhead introduced by our algorithm in more detail. Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ser. ICDE ’08. Washington, DC, USA: Other future studies may include combining proposed operator IEEE Computer Society, 2008, pp. 60–69. [Online]. Available: with other approaches to aggregation (e.g. partial aggregation http://dx.doi.org/10.1109/ICDE.2008.4497414 59 [19] V. Raman, G. Attaluri, R. Barber, N. Chainani, D. Kalmuk, V. KulandaiSamy, J. Leenstra, S. Lightstone, S. Liu, G. M. Lohman, T. Malkemus, R. Mueller, I. Pandis, B. Schiefer, D. Sharpe, R. Sidle, A. Storm, and L. Zhang, “DB2 with BLU Acceleration: So Much More Than Just a Column Store,” Proc. VLDB Endow., vol. 6, no. 11, pp. 1080–1091, Aug. 2013. [Online]. Available: http://dx.doi.org/10.14778/2536222.2536233 [20] J. M. Hellerstein, P. J. Haas, and H. J. Wang, “Online Aggregation,” in Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’97. New York, NY, USA: ACM, 1997, pp. 171–182. [Online]. Available: http://doi.acm.org/10. 1145/253260.253291 [21] K.-L. Tan, C. H. Goh, and B. C. Ooi, “Progressive Evaluation of Nested Aggregate Queries,” The VLDB Journal, vol. 9, no. 3, pp. 261–278, Dec. 2000. [Online]. Available: http://dx.doi.org/10.1007/s007780000026 [22] C. Qin and F. Rusu, “Parallel Online Aggregation in Action,” in Proceedings of the 25th International Conference on Scientific and Statistical Database Management, ser. SSDBM. New York, NY, USA: ACM, 2013, pp. 46:1–46:4. [Online]. Available: http: //doi.acm.org/10.1145/2484838.2484874 [23] S. Chaudhuri, G. Das, M. Datar, R. Motwani, and V. Narasayya, “Over- coming limitations of sampling for aggregation queries,” in Proceedings 17th International Conference on Data Engineering, 2001, pp. 534–542. [24] W.-C. Hou, G. Ozsoyoglu, and B. K. Taneja, “Processing Aggregate Relational Queries with Hard Time Constraints,” in Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’89. New York, NY, USA: ACM, 1989, pp. 68–77. [Online]. Available: http://doi.acm.org/10.1145/67544.66933 [25] C. Ordonez, J. Garcı́a-Garcı́a, and Z. Chen, “Dynamic Optimization of Generalized SQL Queries with Horizontal Aggregations,” in Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’12. New York, NY, USA: ACM, 2012, pp. 637–640. [Online]. Available: http://doi.acm.org/10. 1145/2213836.2213919 [26] C. Cunningham, C. A. Galindo-Legaria, and G. Graefe, “PIVOT and UNPIVOT: Optimization and Execution Strategies in an RDBMS,” in Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30, ser. VLDB ’04. VLDB Endowment, 2004, pp. 998–1009. [Online]. Available: http://dl.acm.org/citation.cfm?id= 1316689.1316775 [27] D. Chatziantoniou, “Using Grouping Variables to Express Complex Decision Support Queries,” Data Knowl. Eng., vol. 61, no. 1, pp. 114–136, Apr. 2007. [Online]. Available: http://dx.doi.org/10.1016/j. datak.2006.05.001 [28] M. Akinde, M. H. Bhlen, D. Chatziantoniou, and J. Gamper, “θ–constrained multi-dimensional aggregation,” Information Systems, vol. 36, no. 2, pp. 341 – 358, 2011, special Issue: Semantic Integration of Data, Multimedia, and Services. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0306437910000748 [29] D. Chatziantoniou and K. A. Ross, “Querying Multiple Features of Groups in Relational Databases,” in Proceedings of the 22th International Conference on Very Large Data Bases, ser. VLDB ’96. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1996, pp. 295–306. [Online]. Available: http://dl.acm.org/citation.cfm?id=645922. 673628 60