Join Algorithms using Map/Reduce
J. Praveen Chandar · 2010
Information explosion is a well known phenomenon now and there is a vast amount of research going on into how best to handle and process huge amounts of data. One such idea for processing enormous quantities of data is Google’s Map/Reduce. Map/Reduce was first introduced by Google engineers Jeffrey Dean and Sanjay Ghemawat [9]. It was designed for and is still used at Google for processing large amounts of raw data (like crawled documents and web-request logs) to produce various kinds of derived data (like inverted indices, web-page summaries, etc.). It is a simple yet powerful framework for implementing distributed applications without having extensive prior knowledge of the intricacies involved in a distributed system. It is highly scalable and works on a cluster of commodity machines with integrated mechanisms for fault tolerance. The programmer is only required to write specialized map and reduce functions as part of the Map/Reduce job and the Map/Reduce framework takes care of the rest. It distributes the data across the cluster, instantiates multiple copies of the map and reduce functions in parallel, and takes care of any system failures that might occur during the execution. Since its inception at Google, Map/Reduce has found many adopters. Among them, the prominent one is the Apache Software Foundation, which has developed an OpenSource version of the Map/Reduce framework called Hadoop [2]. Hadoop boasts of a number of large web-based corporates like Yahoo, Facebook, Amazon, etc., that use it for various kinds of data-warehousing purposes. Facebook for instance, uses it to store copies of internal logs and uses it as a source for reporting and machine learning. See [4] for other companies that use Hadoop. Owing to its ease of use, installation and implementation, Hadoop has found many uses among programmers. One of them is query evaluation over large datasets. And one of the most important queries are Joins. This project explores the existing solutions, extends them and proposes a few new ideas for joining datasets using Hadoop. Algorithms have been broken into two categories Two-Way joins and Multi-Way joins. Join algorithms are then discussed and evaluated under both categories. Options to pre-process data in order to improve performance have also been explored. The results are expected to give an insight into how good a fit Hadoop or Map/Reduce is for evaluating Joins.