# Comparative Analysis of Skew-Join Strategies for Large-Scale Datasets with MapReduce and Spark
## 3 Data-Skew-Handling Algorithms  
### Skew Join  
Data skew is a problem in which the data distribution is uneven or asymmetric. In a database, cases where some attributes appear with a greater frequency than other attributes usually occur [18], and this is called data skew. In distributed parallel computation systems, the join operations using these attributes will take a longer time than with data with a normal distribution. A join operation consists of several steps, including data uploading, projection and selection based on the query, partitioning of the data into partitions, and joining of datasets. Therefore, data skew limits the efficiency of join operations in parallel computation. There are several types of data skew based on the stage in which skew problems occur, such as tuple placement skew, selectivity skew, redistribution skew, and join skew [19]. The initial placement of the datasets in the partitions may cause a tuple placement skew. Selectivity skew occurs when the selectivity of selection predicates is different between nodes. Redistribution skew is caused by a large amount of data on the partitions after the redistribution scheme is applied. Joining product skew is the result of join selectivity on each node. In this paper, we will not consider tuple placement skew, since MapReduce creates split files regardless of the size of the original file. Selectivity skew is also ignored because it does not have any significant impact on the performance, and we do not use projections and selections in our program. Joining product skew cannot be avoided, since it is created after joining two datasets together. Redistribution skew is the main and most important type of data skew, and it affects the distribution of the workload between nodes. This situation is caused by an improper redistribution mechanism. Hence, we will cover redistribution skew in our research. Join computations based on the MapReduce model go through two phases, Map and Reduce. Mappers read the data and convert them into intermediate data in the form of key-value pairs, with the key being the join key and the value being the row containing the join key. After generating key-value pairs, Mappers will shuffle the intermediate data to Reducers according to the rule that pairs of the same key will go to the same Reducers. Data skew may appear at this stage if the input data contain one or more frequent join keys (Figure 4a). This will inevitably lead to data imbalances between computing nodes. Data containing these frequent join keys are processed by only one or a handful of computing nodes, while the rest of the computing nodes are idle. Thus, skewed data occur when one or more computing nodes have to process a much larger number of join keys than other computing nodes in a system [20]. As a result, some nodes encounter bottlenecks or delays, and the remaining nodes are a waste of resources. In parallel computing, the join operation  
Figure 3: Reduction function. execution time is determined by the longest-running task. Therefore, if the data are skewed, the benefits of parallel computation become meaningless [2]. A solution is to clearly point out skew data and to allow it to be distributed in different ways to avoid or reduce the skew effect before calculations begin. In a data-skew problem, heavily weighted partitions will appear. Spark assigns one task per partition, and each worker processes one task at a time; thus, heavy partitions will affect the performance. The main idea now is to avoid heavily weighted partitions. As an example, we add more information on the skew-join key so that it can be distributed into different partitions (Figure 4b). In Spark, data are divided into partitions on many different nodes in a cluster. Thus, it is difficult to avoid data shuffling between nodes with join operations in Spark. This shuffling process will slow down the processing speed and program performance. Therefore, reasonable partitioning of data before the join computation can improve the performance and reduce the effect of shuffling of data.