Chapter 3. Join Algorithms
32
Advantages and Drawbacks
 Advantages
(a) Data involved in one Map/Reduce job is lesser than the algorithm men-
tioned in section 3.3.2. Hence lesser load on the buffers and better I/O.
(b) Datasets of any size can be joined provided there is space available on the
HDFS.
(c) Any number of datasets can be joined given enough space on the HDFS.
 Disadvantages
(a) Intermediate results can take up a lot of space. But this can be optimized
to some extent as explained in the next section.
(b) Setting up the multiple jobs on the cluster incurs a non-trivial overhead.
3.3.3.1 Reduce-Side Cascade Join - Optimization
Simply joining datasets two at a time is very inefficient. The intermediate results are
usually quite large and will take up a lot of space. Even if these are removed once the
whole join iscomplete, they could put a lot of strain on thesystem whilethecascading
joins are taking place. Perhaps there is a way of reducing the sizeof these intermediate
results. There are two ways this can be achieved -
 Compressing the intermediate results
 Join the datasets in increasing order of the output cardinality of their joins, i.e.,
join thedatasets that produce theleast number of joined tuplesfirst, then join this
result with thenext datasetwhich will producethenext lowest output cardinality.
Optimization using compression
Compression was explained in section 2.4.9. Compressing the results will not only
save space on the HDFS, but in case the subsequent join’s Map task needs to fetch a
non-local block for processing, it will also result in lower number of bytes transferred
over the network.
Pdf to multipage tiff - Library control component:C# PDF Convert to Tiff SDK: Convert PDF to tiff images in C#.net, ASP.NET MVC, Ajax, WinForms, WPF
Online C# Tutorial for How to Convert PDF File to Tiff Image File
www.rasteredge.com
Pdf to multipage tiff - Library control component:VB.NET PDF Convert to Tiff SDK: Convert PDF to tiff images in vb.net, ASP.NET MVC, Ajax, WinForms, WPF
Free VB.NET Guide to Render and Convert PDF Document to TIFF
www.rasteredge.com
Chapter 3. Join Algorithms
33
Optimization using Output Cardinality
Deciding the order of joining datasets using the output cardinality is more involved.
Lets consider two sample datasets -
(a) Table 1
Key
Value
1
ABC
2
DEF
2
GHI
3
JKL
(b) Table 2
Key
Value
1
LMN
2
PQR
3
STU
3
XYZ
Table 3.2: Sample Datasets
The output of joining these two datasets will be -
Key
Table 1
Table 2
1
ABC
LMN
2
DEF
PQR
2
GHI
PQR
3
JKL
STU
3
JKL
XYZ
Table 3.3: Joined result of the sample datasets
The thing to notice is that the output will have
T
1
(K
1
)T
2
(K
1
)+T
1
(K
2
)T
2
(K
2
):::T
1
(K
n
)T
2
(K
n
)
=
n
å
i=1
T
1
(K
i
) T
2
(K
i
)
number of rows. where T
m
(K
n
)represents the number of tuples in table T
m
having the
key K
n
.In our case, it will be
1 1+2 1+1 2 = 5
Hence, if we find out thenumber ofkeysin each dataset and the corresponding number
of tuples associated with each key in those datasets, we can find the number of output
tuples in the join, or in other words, the output cardinality of the joined dataset. This
Library control component:C# TIFF: C#.NET Code to Split Multipage TIFF File
XDoc.Tiff ›› C# Tiff: Split Tiff. C# TIFF - Split Multi-page TIFF File in C#.NET. C# Guide for How to Use TIFF Processing DLL to Split Multi-page TIFF File.
www.rasteredge.com
Library control component:.NET Multipage TIFF SDK| Process Multipage TIFF Files
to work with .NET development environments, this Multipage TIFF Processing SDK on the Web, open and view TIFF files on to SharePoint and save to PDF documents.
www.rasteredge.com
Chapter 3. Join Algorithms
34
can be very easily done as part of a pre-processing step. This pre-processing is done
using counters that were mentioned on page 17. To accomplish this, output cardinali-
ties are found pair-wiseforall datasets atpre-processing timeand stored in files. When
thejoin isto beexecuted, thedatasets with thelowest output cardinality are chosen and
joined first. This intermediate result this then joined with the dataset that has the low-
est join output cardinality with either of the two tables joined previously. In the next
round, the dataset with the lowest join output cardinality with any of the three datasets
joined so far is chosen to join with the intermediate result and so on. The next chapter
shows the results of experimental evaluation and compares and contrasts the gains that
such optimization leads to.
Library control component:C# TIFF: C# Code for Multi-page TIFF Processing Using RasterEdge .
instance, adding & deleting Tiff file page, merging and splitting Tiff files, and loading & saving Tiff file to commonly used file formats, like PDF, Bmp, Jpeg
www.rasteredge.com
Library control component:VB.NET Image: Multi-page TIFF Editor SDK; Process TIFF in VB.NET
VB.NET Imaging - Multi-page TIFF Processing in VB. VB.NET TIFF Editor SDK to Process Multi-page TIFF Document Image. Visual C#. VB.NET.
www.rasteredge.com
Chapter 4
Evaluation and Analysis
4.1 Enviroment
Experiments were conducted on 3 different kinds of clusters (see section 4.2.1). There
were two types of machines used that were slightly different from each other -
Type 1
Type 2
CPU
Intel
R
Xeon
TM
CPU 3.20GHz Intel
R
Xeon
TM
CPU 3.20GHz
Cores
4
4
Memory
3631632 KB
3369544 KB
Cache Size
2MB
1MB
OS
Scientific Linux 5.5
Scientific Linux 5.5
Linux Kernel
2.6.18-194
2.6.18-194
Table 4.1: Types of machines used in the Experimental Cluster
All machines were running Clouders Inc.’s[3] distribution of Hadoop - version
0.18.3+76. File system used in all the experiments was HDFS.
4.2 Experimental Setup
4.2.1 Cluster Setup
There were three types of clusters used -
35
Library control component:Process Multipage TIFF Images in Web Image Viewer| Online
Export multi-page TIFF image to a PDF; More image viewing & displaying functions. Multipage TIFF Processing. This page provides detailed
www.rasteredge.com
Library control component:Process Multipage TIFF Images in .NET Winforms | Online Tutorials
Swap a Page in a Multipage TIFF Image. Multi-page Tiff Processing; RasterEdge OCR Engine; PDF Reading; Encode & Decode JBIG 2 Files;
www.rasteredge.com
Chapter 4. Evaluation and Analysis
36
Data Node(s) Name Node(s) Job Tracker(s) Total Node(s)
Type 1
1
1
1
1
Type 2
3
1
1
5
Type 3
6
1
1
8
Table 4.2: Types of clusters used for the experiments
4.3 Two-Way Joins
4.3.1 Experiment 1 : Performance of two-way joins on increasing
input data size
Aseries of experiments were conducted to compare the runtime and scalability of the
various algorithms. The first of these involved running the three two-way algorithms
mentioned earlier on increasing data sizes using the Type 3 (see Table 4.2.1) cluster.
Both datasets involved in the joins had the following characteristics -
 Same number of tuples
 Same key space
 #keys =
1
10
#tuples
We tested on two kinds of key distributions as shown in Figure 4.1 and Figure 4.2. In
the case of skewed data, one of the datasets had a key that was repeated 50% of the
times. Which means that given n rows,
n
=
2
of them were the same key. The other
dataset had uniform key distribution
Concentrating first on the Uniform Key Distribution graph (Figure 4.1), it can be
seen that all the three algorithms gave comparable numbers at lower input data sizes.
ButMap-sidejoin alwaysperformed thebest, even with largeinputdatasets. Broadcast
join deteriorated the fastest as the data size increased. This is because a larger file had
to bereplicated across all the machinesin thecluster as theinput size increased. Figure
4.2 shows something interesting. Map-side join gave a worse time than the other two
algorithms for the input with 5 million rows when then input dataset had skewed key
distribution. This can be attributed to the unequal partitioning that will occur due to
the skew.
Apart from testing for runtimes, wealso checked for theamount of datatransferred
over the network from the machines running the Map tasks to the machines running
Library control component:.NET PDF SDK | Read & Processing PDF files
Able to convert PDF documents into other formats (multipage TIFF, JPEG, etc); Multiple font types support, including TrueType, Type0, Type1, Type3 & OpenType;
www.rasteredge.com
Library control component:VB.NET TIFF: .NET TIFF Splitting Control to Split & Disassemble
VB.NET TIFF - Split Multipage TIFF Using VB. Windows.Forms Imports RasterEdge.Imaging. TIFF Imports RasterEdge TIFDecoder()) 'use TIFDecoder open a pdf file Dim
www.rasteredge.com
Chapter 4. Evaluation and Analysis
37
Figure 4.1: Experiment 1 : Uniform Key Distribution
Figure 4.2: Experiment 1 : Skewed Key Distribution
the Reduce tasks. A simple number like the number of bytes transferred might not be
Chapter 4. Evaluation and Analysis
38
very meaningful. Hence we took the ratio -
Bytes transferred over the network
Initial Data Size
We call this the Data Shuffle ratio. This ratio is interesting because it gives an idea
of how well Hadoop achieves data locality and whether it improves with bigger data
sizes. Table 4.3 and Table 4.4 show the actual run-times of the different algorithms
shown in Figure 4.1 and Figure 4.2. Also given are the number of bytes shuffled
across machines from the Map phase to the Reduce phase in the Reduce-Side Join.
Note that Map-Side Join and Broadcast Join do not have a reduce side and hence no
data is shuffled across machines between the Map phase and the Reduce phase. The
sixth column shows the time taken for pre-processing in the case of the Map-Side Join
algorithm.
Tuples
(x100000)
Reduce-Side
Join
Data Shuf-
fled(bytes)
Data Shuffle
Ratio
Map-Side
Join
Pre-
Processing
Broadcast
Join
1
24s
9178000
1.150
9s
38s
10s
2.5
26s
23278000
1.148
14s
45s
16s
5
37s
46778000
1.147
22s
46s
29s
7.5
44s
70278000
1.147
35s
47s
42s
10
53s
93778000
1.147
41s
49s
53s
25
120s
237778000
1.144
103s
56s
144s
50
239s
477778000
1.144
214s
71s
303s
Table 4.3: Experiment 1 : Uniform Key Distribution
Tuples
(x100000)
Reduce-Side
Join
Data Shuf-
fled(bytes)
Data Shuffle
Ratio
Map-Side
Join
Pre-
Processing
Broadcast
Join
1
21s
8194793
1.1.27
8s
41s
10s
2.5
30s
23243259
1.148
16s
42s
15s
5
43s
46805826
1.147
35s
42s
27s
7.5
55s
70118029
1.147
41s
46s
36s
10
64s
93806021
1.147
50s
46s
50s
25
142s
238055988
1.144
165s
54s
129s
50
275s
478056409
1.144
338s
76s
272s
Table 4.4: Experiment 1 : Skewed Key Distribution
There are two main things worth noticing in Table 4.3 and Table 4.4. The first is
that the Data Shuffleratio remains around 1.14 for both uniform and skewed key distri-
bution. Thisis because asthe data size increases, Hadoop isable to bettermanage data
distribution and data locality. The other thing is that though Map-Side performed best
most of the times, it took an average time of 50.29 seconds (uniform key distribution)
Chapter 4. Evaluation and Analysis
39
and 49.57 seconds (skewed key distribution) for the pre-partitioning phase. This may
not seem a lot, but is likely to be quite high if the input datasets are much larger than
the ones used in this experiment.
4.3.2 Experiment 2 - Two-way Join algorithms across different clus-
ters
Instead of just testing the scalability of an algorithm in terms of the input data, we
decided to find out the behaviour of thesealgorithms with different kinds of clusters as
well. For this, the algorithms were run against all the 3 kinds of clusters mentioned in
Table 4.2.1 with the data having the following characteristics -
 Both tables contained 1 million tuples.
 Both tables contained the same number of keys - #keys =
1
10
#tuples spread
across the same key space.
Figure 4.3: Experiment 2 : Two-way Join algorithms across different clusters
We noticed something that we were not expecting to see. The 1-machine cluster,
performed better than the 5-machine cluster for all the three algorithms. The perfor-
mance then improved again when the algorithms were run on the 8-machine cluster.
Chapter 4. Evaluation and Analysis
40
On checking the experiment logs, we concluded that this was because on a 1-machine
cluster, all datawas present locally and there wasno data transfer that happened across
the network. In the case of the Reduce-Side Join algorithm the time taken to transfer
datafromthemachines running the Map task to the machinesrunning theReducetasks
was considerable in the 5-machine cluster, whereas all thedata was local in the case of
the 1-machine cluster. In case of Map-Side Join as well, the input data was all present
locally on the machine running the job and no input had to be fetched for other data
nodes. Similarly for the Broadcast Join the file is not broadcast across the machines in
the cluster, but is just broadcast from the master-node to the task-node, both running
on the same machine. The overall performance improved in the case of the 8-machine
cluster because there were more machines available for processing the task in a well
partitioned distributed fashion. The individual Map tasks performed smaller units of
work and finished much faster.
No. of
Nodes
Reduce-Side
Join
Data Shuf-
fled(bytes)
Data Shuffle
Ratio
Map-Side
Join
Pre-
Processing
Broadcast
Join
1
68s
0
0.000
50s
169s
46s
5
124s
93777932
1.147
87s
55s
87s
8
53s
93778000
1.147
41s
49s
53s
Table 4.5: Experiment 2 : Two-way Join algorithms across different clusters
Table 4.5 shows the actual numbers recorded across the three different kinds of
clusters. Once again, in the case of Reduce-Side Join, we found the value of the
Data Shuffle ratio to analyse data transferred from Mappers to Reducers and how well
Hadoop achievesdatalocality with increasing numberof nodes. Noticethatonce again
the ratio remained close to 1.14. Also notice that this ratio is 0 for the 1-machine clus-
ter since, obviously, there is only 1 machine and there is no data transferred across the
network.
4.3.3 Experiment 3 - Performance of Broadcast Join
The major use-case of the Broadcast Join is when one of the datasets is small in com-
parison to the other. So we decided to test this scenario by keeping one of the datasets
of constant size and increasing the size of the other. The dataset characteristics were
as follows -
 The larger dataset size was fixed at 1,000,000 tuples
Chapter 4. Evaluation and Analysis
41
 The size of the smaller dataset was varied from 100,000 tuples to 1,000,000
tuples
Figure 4.4: Experiment 3 : Broadcast Join Performance
Broadcast Join gave performances that were very close to the ones by Map-Side
Join, but without any pre-processing step involved. Performance of Reduce-Side Join
was the worst when compared to the other two algorithms.
Table4.6 givesthe actual numbers that wererecorded for thegraph shown in Figure
4.4. Once again, noticethat theMap-SideJoin involved an averagepre-processing time
of 45.6 seconds which is not required for the Broadcast Join algorithm.
No.
of tuples
(x100000)
in
smallerrelation
Broadcast Join
MapSideJoin
Pre-Processing
ReduceSide Join
1
13
8
41
26
2.5
16
14
51
40
5
26
30
43
57
7.5
39
32
46
72
10
52
44
47
94
Table 4.6: Experiment 3 : Broadcast Join Performance
Documents you may be interested
Documents you may be interested