Comparison of Join algorithms in MapReduce Framework

• Mani Bhushan, Balaraj J, Oinam Martina Devi

Abstract: In the current technological world, there is generation of enormous data each and every day by different media and social networks. The MapReduce framework is increasingly being used widely to analyse large volumes of data. One of the techniques that framework is join algorithm. Join algorithms can be divided into two groups: Reduce-side join and Map-side join. The aim of our work is to compare existing join algorithms which are used by the MapReduce framework. We have compared Reducer-side merge join and Map-side replication-join in terms of pre-processing, the number of phases involved, whether it is sensitive to data skew, whether there is need for distributed Cache, memory overflow. The objective is to determine which algorithm holds well in given scenario.

I INTRODUCTION

Data-intensive applications include large-scale data warehouse systems, cloud computing, data-intensive analysis. Applications for large-scale data analysis use MapReduce (MR) paradigm [6]. MAPREDUCE is a programming model for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs and a reduce function that merges all intermediate values associated with the same intermediate key [5]. Let us look upon the execution of MapReduce execution.

MapReduce Execution:

The Map/Reduce framework consists of two operations, “map” and “reduce”, which are executed on a cluster of shared-nothing commodity nodes. In a map operation, the input data available through a distributed file system, is distributed among a number of nodes in the cluster in the form of key-value pairs. Each of these mapper nodes transforms a key-value pair into a list of intermediate key-value pairs [1]. The intermediate key-value pairs are propagated to the reducer nodes such that each reduce process receives values related to one key. The values are processed and the result is written to the file system [1].

Figure 1.1: MR execution in detail [7].

In [3], the authors have described crucial implementation details of a number of well-known join strategies in MapReduce, and present a comprehensive experimental comparison of these join techniques on a 100-node Hadoop cluster. The authors have provided the overview of MapReduce overall. They have described how to implement several equijoin algorithms for log processing in MapReduce. They have used the MapReduce framework as it is, without any modification. Therefore, the support for fault tolerance and load balancing in MapReduce is preserved. They have worked on Repartition Join, Broadcast Join, Semi-Join, and Per-Split Semi-Join. The authors have revealed many details that make the implementation more efficient. We have evaluated the join methods on a 100-node system and shown the unique tradeoffs of these join algorithms in the context of MapReduce. We have also explored how our join algorithms can benefit from certain types of practical preprocessing techniques.

In [4], the authors have examined the algorithms for performing equi-joins between datasets over Map/Reduce and have provided a comparative analysis. The results indicate that all join algorithms are significantly affected by certain properties of the input datasets (size, selectivity factor, etc.) and that each algorithm performs better under certain circumstances. Our cost model manages to capture these factors and estimates fairly accurately the performance of each algorithm.

II COMPARISON OF ALGORITHMS

Data-intensive applications required to process multiple data sets. This implies the need to perform several join operation. Its known join operation is one of the most expensive operations in terms both I / O and CPU costs [6]. Now let us see two of the join algorithms analysed in the earlier work:

2.1 Reducer-side merge join:

It is the most straightforward way to join two datasets over the Hadoop framework. It can be considered as the Hadoop version of the parallel sort-merge join algorithm. The main idea is to sort the input splits on the join column, forward them to the appropriate reducer and then merge them during the reduce phase.

The performance of the algorithm is dominated by two main factors.

• The first is the communication overhead required to shuffle the datasets through the network from mapper to reducer.
• The second one is the time required to sort and write the datasets to disk before forwarding them to the reducers.

However, the drawback of the the Reduce-side merge join is that the map function does not apply any filter and the output size remains at the same size with the input and also the reducer loads in memory all the tuples of each split.

Figure 1.2 Reducer-side merge join [4]

2.2 Map-side replication-join

The Map-Side Replication join tries to address the drawbacks of the previous approach. The concept was initially conceived in the database literature [2]. The implementation is much simpler compared to the previous algorithm. We start by replicating the small table to all nodes by using the distributed cache facility. Then, during the setup2 of the mapper we load the table into a hash table. For each value of the hash table we nest an array list for storing multiple rows with the same join attribute. Hence, for each row of the bigger table we search over only the unique keys of the small table. In the case we have many rows per join attribute it results in substantial performance gain. The hash table provides constant time search for a key value. During the execution of the mapper for each key-value pair of the input split we extract the join attribute and probe the hash table. If the value exists we combine the tuples of the matching keys and submit the new tuple. The algorithm is illustrated in figure 1.3. The main disadvantage of this algorithm is that it is restricted by the memory size of the nodes. If the small table does not fit in memory we cannot use the algorithm at all.

Figure 2.2 Map-side replication-join.

III CONCLUSION

IV REFERENCES

[1] Fariha Atta. Implementation and analysis of join algorithms to handle skew for the hadoop mapreduce framework. Master’s thesis, MSc Informatics, School of Informatics, University of Edinburgh, 2010.

[2] Shivnath Babu. Towards automatic optimization of mapreduce programs. In Proceedings of the 1st ACM symposium on Cloud computing, SoCC ’10, pages 137–142, New York, NY, USA, 2010. ACM.

[3] Spyros Blanas, Jignesh M. Patel, Vuk Ercegovac, Jun Rao, Eugene J. Shekita, and Yuanyuan Tian. A comparison of join algorithms for log processing in mapreduce. In Proceedings of the 2010 international conference on Management of data, SIGMOD ’10, pages 975–986, New York, NY, USA, 2010. ACM.

[4] A Chatzistergiou. Designing a parallel query engine over map/reduce. Master’s thesis, MSc Informatics, School of Informatics, University of Edinburgh, 2010.

[5] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: a flexible data processing tool. Commun. ACM, 53:72–77, January 2010.

[6] A. Pigul. Comparative Study Parallel Join Algorithms for MapReduce environment. Saint Petersburg State University.

[7] S. Blanas, J. M. Patel, V. Ercegovac, J. Rao, E. J. Shekita, and Y. Tian. A comparison

of join algorithms for log processing in mapreduce. In SIGMOD ’10: Proceedings of the 2010 international conference on Management of data, pages 975–986, New York, NY, USA, 2010. ACM.

[8] Shivnath Babu. Towards automatic optimization of MapReduce programs. In SIGMOD ’10: Proceedings of the 2010 international conference on Management of data. Pages 137-142. New York, NY, USA, 2010. ACM.