# Comparative Analysis of Skew-Join Strategies for Large-Scale Datasets with MapReduce and Spark
## 3 Data-Skew-Handling Algorithms
### Range-Based Partition  
Range-based partition (RBP) is proposed as a solution for skewed data instead of hash-based partition [5]. The idea of the algorithm is to divide the mapped data into sub-ranges. Therefore, each computing node will process a sub-range instead of a join key value in order to reduce the burden on the computing nodes when data are skewed. The data flow of range-based partition algorithm is presented in Figure 8. A split vector is created to limit the range of sub-ranges. If there are \(n\) partitions, the split vector will contain \(n-1\) elements \(\{e_{1},e_{2},e_{3},\ldots,e_{n-1}\}\). Thus, data with join keys \(\leq e_{1}\) will come to partition 1, data with join keys in the range \(e_{1}<keys\leq e_{2}\) will come to partition 2, and data with join keys \(>e_{n-1}\) will come to partition \(n\). However, the algorithm still produces skewed results after the partition period. In this method, the first thing to do is to create a split vector from the two input datasets by calculating the appearance of the join keys in each dataset. The dataset that has the most skewed join keys will be selected as the split vector. We use the \"fragment-replicate\" technique [22] before the join computation. When a mapper reads input records and maps into RDD key-value pairs, if the join key belongs to more than one partition, this key-value pair is a fragment or replicated. We will use a fragment of the key-value pairs on the dataset with the most skewed join key and use a replicate of the key-value pairs on the other dataset. Figure 8: Data flow of a range-based partition algorithm. Figure 7: Join computation with hash-based partition. The following steps need to be performed to partition key-value pairs in the dataset with more skewed join keys (a build relation):  
* A split vector is created from the input dataset and this vector is stored in the HDFS;
* Each node in the cluster will read the split vector from the HDFS and create a range map, and each sub-range will be assigned to the corresponding partition;
* Based on this range map, when a mapper reads input records and maps into RDD key-value pairs, if the join key belongs to only one sub-range, the data will be partitioned into the corresponding partition; if the join key belongs to more than one sub-range, the data will be randomly assigned to one of the partitions corresponding to the sub-ranges (fragment). For a dataset with fewer skewed join keys, we use the split vector created above to partition key-value pairs (a probing relation). If the join key belongs to only one sub-range, the data will be assigned to the corresponding partition. Conversely, if the join key belongs to more than one sub-range, the data will be distributed to all partitions corresponding to the sub-range (replicate). The algorithm used to partition the datasets is presented in Algorithms 1 and 2. ```
0: An input record \(r\in R\)
0: Split vector
0: A list of partitions \(P\) Begin
1: Create Sub-range
2:for each\(r\in R\)do
3: SR = r.listSubRange()
4:if\(|\)SR\(|\) == 1 then
5: Output (P(SR(1)), r)
6:else
7: i = random() % \(|\)SR\(|\)
8: Output (P(SR(i)), r)
9:endif
10:endfor End. ```  
**Algorithm 1** Range-based partition algorithm for dataset \(R\)--a build relation  
The partitions will have a list of data with a join key \(k\) belonging to the same sub-range. Here, we use a join algorithm to create the join results (presented in Algorithm 3). ```
1:\(\text{tupleR}=\{\}\)
2:for each\(r_{i}\) in input list do
3:\(\text{tupleR}=\text{tupleR}\cup\{r_{i}\}\)
4:endfor
5:for each\(l_{j}\) in input list do
6:for each\(r_{i}\) in tupleR do
7:\(\text{Output}\)\(r_{i}\bowtie l_{j}\)
8:endfor
9:endfor
```  
**Algorithm 3** Join two datasets \(R\bowtie L\)  
Given an example of two datasets \(R(k,v1)\) and \(L(k,v2)\), as presented above, we create a split vector from dataset \(R\). The elements in the split vector will be chosen from \(R.k\) with the formula \(\lfloor\frac{|R|}{p-1}\rfloor\), in which \(|R|\) is the number of records of dataset \(R\).