# Comparative Analysis of Skew-Join Strategies for Large-Scale Datasets with MapReduce and Spark
## 2 Background  
### Joint Operations in the MapReduce Model  
MapReduce [1] is a parallel and distributed large-scale data processing model. A program can be run on clusters with a number of computing nodes that can be up to thousands. Introduced in 2004, MapReduce has been widely used in the field of Big Data, since it allows users to simply focus on the design of data processing operations regardless of the parallel or distributed nature of the model [3]. MapReduce is implemented through two basic functions, Map and Reduce, which are also two consecutive stages in data processing. The Map function receives input data to convert them into intermediate data (key-value pairs), and the Reduce function accepts the intermediate data created to perform calculations.  
Hadoop ([[http://hadoop.apache.org](http://hadoop.apache.org)]([http://hadoop.apache.org](http://hadoop.apache.org)) (accessed on 8 May 2022)) has become one of the popular Big Data processing platforms of the last decade [16]. Hadoop is an open-source implementation of the MapReduce model. Hadoop breaks data down into many small chunks and runs an application on the data of the computing nodes in the system. Each time it performs a task, Hadoop has to reload the data from the disk, which is costly and is considered a \"penalty\" [17]. Therefore, Hadoop has not fully supported join operations with high I/O and communication costs [2]. In recent years, with the advent of Apache Spark [17], many outstanding features of this platform have helped this to become the next generation of Big Data processing platforms [6].  
The join operation is a basic operation that consumes much processing time, and it is an intensive data operation in data processing [3]. This section discusses the process and gives a concrete example of a join operation using the MapReduce model. Considering the two datasets \(R\) (user data) and \(L\) (log data), to list a username and the corresponding event that the user accesses, we have the query \(R(uname,uid)\bowtie_{uid=uid}L(uid,event)\). In large-scale data applications, such as social networks, this query can enforce the joining of trillions of records. Therefore, the parallel and distributed processing model in MapReduce is a good solution to this problem. As shown in Figure 1, the JobTracker of MapReduce creates three Mappers to process three partitions of the input data simultaneously. The first Mapper computes the first partition, consisting of three records of dataset \(R\). The second Mapper processes one record of \(R\), and the third Mapper processes two records of \(L\). The Mappers transform the datasets \(R\) and \(L\) based on the join key \(uid\).  
* \(\{(A,B),(C,B),(A,F)\}\rightarrow\{(B,A),(B,C),(F,A)\}\)
* \(\{(C,D)\}\rightarrow\{(D,C)\}\)
* \(\{(B,C),(D,F)\}\rightarrow\{(B,C),(D,F)\}\)  
The data after transformation are called intermediate data, and those are sent to the Reducers. Intermediate datasets with the same join key are sent to the same Reducer. Here, the reduction function is called for every single key with a list of values. Finally, each record of \(R\) finds the records of \(L\) that have the same join key to produce the join results. Figure 1 shows that there are three join results from the Reducers.  
* Reducer 1 for join key B: \((B_{\_},[R:A,R:C,L:C])\rightarrow\{(A,C),(C,C)\}\)
* Reducer 2 for join key F: \((F_{\_},[R:A])\rightarrow\{empty\}\)
* Reducer 3 for key join D: \((D,[R:C,L:F])\rightarrow\{(C,F)\}\)