Incremental Join Aggregation Using Map Reduce

Abstract

Fast and efficient retrieval mechanisms that work within acceptable time frames and keep pace with the information explosion are essential for efficient and effective database systems of the future. Using more processing power, and in particular, exploiting parallel processing is the intuitive solution. While there have been many successful efforts that aim at parallelizing query evaluation, it is possible to further improve the performance of a database system using newer techniques such as Map/Reduce.

It is observed that the parallel DBMS perform well because they load and index the data before they process queries. Since this loading phase can take a long time, there arises the question if the loading phase itself is worth to process only one or two queries. This is where Map/Reduce comes into play. One such idea for processing enormous quantities of data is Google's Map/Reduce. It is a simple yet powerful framework for efficient execution of complex queries over large datasets involving joins and aggregation.

The work reported in this paper deals with the design of a proposed framework based on Map/Reduce for efficient execution of complex database queries involving joins and aggregations. The user needs to only write specialized map and reduce functions as a part of the Map/Reduce job and the framework takes care of the rest. The design of the framework has been done after exploring existing solutions and then extended to propose an efficient solution for queries involving joins. Join algorithms are of two types - Two-Way joins and Multi-Way joins. This work deals with only two-way joins. Options to pre-process data in order to improve performance at map side have also been explored. Experimental results presented provide an insight into how good a fit Map/Reduce is for evaluating joins with aggregation at reduce side.