# Comparative Analysis of Skew-Join Strategies for Large-Scale Datasets with MapReduce and Spark
## 1 Introduction  
Big Data is a term that has been mentioned in many recent studies. People generate terabytes of data every hour, leading to challenges in storing and handling data in traditional ways. Therefore, Google designed the MapReduce processing model [1] for parallel and distributed processing of large-scale datasets. One of the major limitations of the MapReduce model is data-skew processing [2]. A typical case is data skew in join operations, which are the operation of joining many relationships or datasets that have some common attributes into a new relationship [3]. The join operation is used in many applications, such as the construction of search engines and some big data-intensive applications [4]. Taking the example of joining two datasets \(R\) and \(L\), \(R\) has the join key column \(R.id=\{1,1,1,1,1,2\}\) and \(L\) the has join key column \(L.id=\{1,2,3\}\). In MapReduce, Mapreduce, Mappers read input data from the two datasets and distribute intermediate data to reducers based on join keys. Data with the same join keys will be sent to the same reducers to create join results. Assuming that dataset \(R\) is skewed at \(id=1\), the join key with a value of 1 occurs many times. In this case, the reducers \(r_{2}\) and \(r_{3}\) will finish faster than reducer \(r_{1}\), since reducer \(r_{1}\) receives more data than the others. If there is a large amount of skewed data with \(id=1\), thenoverload and congestion will appear at the computing node \(r_{1}\) and lead to inefficiency in the computational system. This is a real challenge for join operations in MapReduce. Some algorithms have been proposed for data-skew-join operations in MapReduce, such as hash-based partition [5], range-based partition [5], multi-dimensional range partition (MDRP) [6], MRFA-Join [7], and randomized partition [8]. [PERSON] et al. [9] introduced LIBRA, a sampling and partitioning algorithm for handling high-frequency join keys in reduction tasks. [PERSON] et al. [10] discussed challenges in large-scale distributed join operation and introduced novel execution strategies that robustly handle data skew. They used different partitioning schemes and join graph topologies for high-frequency key values. [PERSON] et al. [11] proposed an efficient key-select algorithm to find skew key tuples and defined a lightweight tuple migration strategy to solve data-skew problems. Their FastJoin system improved the performance in terms of latency and throughput. [PERSON] and [PERSON] [12] presented an index structure to reorder data so that popular items were concentrated in the cache hierarchy. They analyzed the cache behavior and efficiently processed database queries in the presence of skew. [PERSON] et al. [13] presented their approach for handling data skew in a character-based string-similarity join in MapReduce. They compared the proposed algorithm with three other algorithms for handling data skew for evaluation. [PERSON] and [PERSON] [14] gave a brief survey on the solutions for data skew in MapReduce. [PERSON] and [PERSON] [15] studied various methodologies and techniques used to mitigate data skew and partition skew. [PERSON] et al. [6] proposed multi-dimensional range partitioning to overcome the limitations of traditional algorithms. There have been some studies on data skew in MapReduce. However, there has not been any study that has shown an adequate and systematic comparison of data-skew handling for join operations in Spark. In this paper, we will present and compare three algorithms for partitioning data, i.e, hash-based partition, range-based partition, and multi-dimensional range partition. This helps users to choose suitable solutions for processing join operations in large-scale datasets. We built cost models for the algorithms for evaluation. This provided a scientific basis for the comparison. Experiments were conducted on a Spark cluster with different skew ratios. The structure of this paper is organized as follows. Section 2 presents the background related to the large-scale data processing model and platform.