manuscript No. (will be inserted by the editor) Revisiting Aggregation for Data Intensive Applications: A Performance Study

Aggregation has always been a very important operation in database processing. For example, all 22 queries in the TPC-H Benchmark [3] contain aggregation. It is also a key operation for data preprocessing and query processing in data intensive applications, such as machine learning on large volume data [7], and web-related data processing like web-log and page ranking [18], etc. In the big data scenario where data is spread over a distributed environment, like Hadoop and many popular distributed relational databases, aggregation is typically processed in a map-combine-reduce fashion. Such a strategy first obtains the local aggregation results, which are then merged to get the global aggregation results. Hence, the efficiency of the local aggregation algorithm is a key factor for the global aggregation performance. In our effort to support the aggregation operation in our next generation parallel data processing platform AsterixDB [4], we noticed two new challenges that big data applications impose on local aggregation algorithms: first, if the input data is huge and the aggregation is group-based (like the “group-by ” in SQL, where each unique group will have a record in the result set), the aggregation result may not fit in main memory; second, in order to allow multiple operations being processed simultaneously, an aggregation operation should work within a strict memory budget provided by the platform. Implementing an aggregation operation to address these challenges is not trivial. Aggregation has not attracted as much attention as other operations like joins, probably due to its simpler computational logic. Several aggregation algorithms proposed in literature decades ago, like pre-sorting the input data [9], or using hasharXiv:1311.0059v