Chapter 1. Introduction
2
to load and retrieve data efficiently. There is tremendous amount of research being
undertaken towards creating such algorithms, for example, Google’s BigTable [8] or
Facebook’s Cassandra [1] which is now open-source and is maintained by the Apache
Software Foundation. Many of the leading Information Technology companies have
invested a lot into this research and have come up with a number of innovative ideas
and products.
It is well known that more often than not, the most time consuming step in a
Database Management System is the Query Evaluation engine, especially when there
are large amounts of data involved. Fast and efficient retrieval mechanisms that work
within acceptable time frames and that can keep up with the pace of information ex-
plosion are essential for effective database systems of the future. Using more pro-
cessing power, and in particular, exploiting parallel processing is the intuitive solution.
While there have been many attempts at parallelizing query evaluation, there is still
much scope for research in this area. This project investigates a specific framework
for managing parallel processing in the database context. It consolidates work already
done and proposes new algorithms and optimizations to existing solutions (discussed
in Chapter 3).
One of the most common operations in query evaluation is a Join. Joins combine
records from two or more tables, usually based on some condition. They have been
widely studied and there are various algorithms available to carry out joins. For exam-
ple, the Nested-Loops Join, the Sort-Merge Join and the Hash Join are all examples of
popular join algorithms (see [17]). These algorithms (and more) are used for joining
two as well as more datasets. But more often than not, when multiple datasets are
involved, selectivity factor is exploited to structure the order in which the joins are
made. Selectivity factor can be defined as the fraction of the datasets involved in the
join that will be present in the output of the join. We too will be exploiting it in one of
our algorithms later.
All DBMSs support more than one algorithm to carry out joins. But as expected,
things start to get complicated and unacceptably slow when data starts to run into very
large sizes. Lets Consider a trivial example with a simple algorithm like Nested-Loops
Join.
Given two datasets R and S, the Nested-Loops Join algorithm joins (R ./ S) as
follows -
Create tiff from pdf - Library control class: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
Create tiff from pdf - Library control class: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 1. Introduction
3
for all tuples r e R do
for all tuples s e S do
if JoinCondition then fJoinCondition can be like r:a == s:bg
add (r;s) to the result
end if
end for
end for
Using this algorithm, two tables containing 100,000 and 50,000 rows will take
about an hour and a half to perform an equi-join, in the case where each I/O takes 10
ms, the inputs are clustered and the I/O is done one page at a time [17]. If avoidable,
this option is seldom used. Other algorithms like Hash Join or Sort-Merge Join can
perform the same join in about a minute. But they suffer from the drawback that they
cannot perform a non-equi join and the only option in that case is the Nested-Loops
Join. Join Algorithms have been studied extensively with many variants existing for
each algorithm. For instance, Hash-Join itself has three different variations - Simple
Hash Join, Grace Hash Join and Hybrid Hash Join (all three explained in [17]).
Afew years back, engineers at Google introduced a new programming model
called Map/Reduce [9] (explained in more detail in Chapter 2). Map/Reduce enables
easy development of scalable parallel applications to process vast amounts of data on
large clusters of commodity machines. Map/Reduce framework hides management of
data and job partitioning from the programmer and provides in-built fault-tolerance
mechanisms. This lets the programmer concentrate on the actual problem at hand in-
stead ofworrying abouttheintricacies involved in adistributed system. It was designed
for processing large amounts of raw data (like crawled documents and web-request
logs) to produce various kinds of derived data (like inverted indices, web-page sum-
maries, etc.). It isstill aprominently used model at Googlefor many of its applications
and computations (see [9]).
Map/Reduce was not developed for Database Systems in the conventional sense.
It was designed for computations that were conceptually quite straightforward, but
involved huge amounts of input data. For example, finding the set of most frequent
queries submitted to Google’s search engineon any given day. It is very different from
the traditional database paradigm, in that it does not expect a predefined schema, does
not haveadeclarativequery languageand any indicesaretheprogrammersprerogative.
But at the sametime, Map/Reduce hides the details of parallelization, has built-in fault
toleranceand load balancing in a simple programming framework. The novel idea was
Library control class:C# Create PDF from Tiff Library to convert tif images to PDF in C#
Create PDF from Tiff. |. Home ›› XDoc.PDF ›› C# PDF: Create PDF from Tiff. Create PDF from Tiff in both .NET WinForms and ASP.NET application.
www.rasteredge.com
Library control class:VB.NET Create PDF from Tiff Library to convert tif images to PDF
WPF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint. Create PDF from Tiff. Create PDF from Images.
www.rasteredge.com
Chapter 1. Introduction
4
so appealing that it led to an open-source version called Hadoop. Hadoop has become
extremely popular in the past few years and boasts of big Web 2.0 companies like
Facebook, Twitter and Yahoo! as part of its community.
1.2 Motivation and Aim
Map/Reduce was primarily designed at Google for use with its web-indexing tech-
nologies. These included things like keeping track of the web-pages crawled so far,
creating inverted-indices from them and summarizing the web-pages for search-result
views. Over time, they started considering it for more interesting computations like
query processing on the raw or derived data that they already had. This led to its
wide-spread adoption and led to uses that were not envisioned at the time of design-
ing. Companies have started using Map/Reduce to manage large amounts of data (see
[11] for example). And when there are multiple datasets involved, there will always
be a need for joining these datasets. The goal of this project is to test the viability
of Map/Reduce framework for joining datasets as part of database query processing.
There are four main contributions of this project -
1. Examineand consolidate theexisting algorithms forjoining datasetsusing Map/Re-
duce.
2. Propose new algorithms.
3. Quantitatively evaluate the performance of these algorithms.
4. Analyse the performance and discuss the various factors that come into picture
when using Map/Reduce for joining datasets.
1.3 Related Work
Alot of work has already been done on implementing database queries with Map/Re-
duce and comparing the Map/Reduce model with parallel relational databases. The
framework itself comes with a functionality for sorting datasets (explained further in
2). There is also a functionality to join datasets that is available out of the box. This
is the Map-Side join which [16] explains in greater detail. This kind of join is also
discussed in this thesis in Chapter 3 and Chapter 4. In a very recent publication [6],
Blanas et. al. suggested algorithms and compared the performance for joining log
Library control class:VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to
WPF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint. Create PDF from Tiff. Create PDF from Images.
www.rasteredge.com
Library control class:VB.NET Create PDF from Word Library to convert docx, doc to PDF in
WPF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint. Create PDF from Tiff. Create PDF from Images.
www.rasteredge.com
Chapter 1. Introduction
5
datasets with user datasets. They also compared their work with Yahoo’s Pig Project
[11] and found that their algorithms performed considerably better than those used
in Pig. In [12], Konstantina Palla developed a theoretical cost model to evaluate the
I/O cost incurred during the execution of a Map/Reduce job. She also compared this
cost model with two popular join algorithmsusing Map/Reduce, Reduce-Side Join and
Map-Side Join.
In [14] the authors argue that while Map/Reduce has lately started to replace the
traditional DBMS technology, Map/Reduce in fact complements rather than competes
with with it. They conducted benchmark studies and found that DBMSs were substan-
tially faster (in tasks like query processing) than theMap/Reducesystems oncethe data
is loaded, but that loading the data took considerably longer in the database systems.
This lead them to conclude that Map/Reduce is more like an Extract-Transform-Load
(ETL) system
1
than a DBMS, as it quickly loads and processes large amounts of data
in an ad-hocmanner. Studiesconducted by Pavlo et. al. in [13] found that the Map/Re-
duce model outperformed traditional DBMS systems in terms of scalability and fault
tolerance. But they also noted that it suffered from certain performance limitations
of the model, particularly in terms of computation time. This is attributed mainly to
the fact that the model was not originally designed to perform structured data analysis
and lacks many of the basic features that the relational databases routinely provide.
On the other hand, advocates of the model, deployed it to investigate its computing
capabilities in environments with large amounts of raw data. Abouzeid et al. in their
work [5] attempted to bridge the gap between the two technologies, that is, parallel
databases and Map/Reduce model, suggesting a hybrid system that combines the best
features from both. The acquired results appeared quite promising and pointed out the
advantages of an approach that combinestheefficiency of relational databases with the
scalability and fault tolerance of the Map/Reduce model.
Several research studies also aim to improve the model itself. Yang et al. [19]
proposed a Merge component after the reduce function for performing a join opera-
tion on two datasets. However, the Map-Reduce-Merge approach introduces an extra
processing step that is not there in the standard Map/Reduce framework and therefore
will not be found in a standard Map/Reduce deployment. Moreover, the Pig project at
Yahoo [11], the SCOPE project at Microsoft [7], and theopen source Hive project [15]
introduce SQL-style declarative languages over the standard Map/Reduce model in an
1
AnETLsystem Extractsinformation from the data source,Transformsit using a seriesofrulesand
functions and Loadsthe transformed data into a target, usually a Data Warehouse.
Library control class:VB.NET Create PDF from Excel Library to convert xlsx, xls to PDF
WPF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint. Create PDF from Tiff. Create PDF from Images.
www.rasteredge.com
Library control class:C# Create PDF from Excel Library to convert xlsx, xls to PDF in C#
Create searchable and scanned PDF files from Excel. Description: Convert to PDF/TIFF and save it on the disk. Parameters: Name, Description, Valid Value.
www.rasteredge.com
Chapter 1. Introduction
6
attempt to make it more expressive and limit its schema-less disadvantages. All these
projects provide ways of declaring join executions over datasets.
While most of the work present currently, like the work done by Blanas et. al in
[6], concentrates more on two-way joins, this project extends their work to multi-way
joins. Also, we evaluate the results of the algorithms in a different way focussing more
on datasets of comparable size.
1.4 Thesis Outline
Chapter 2 introduces the Map/Reduce framework in more detail. It explains the stages
involved in the execution of a Map/Reduce program. Section 2.4 talks about Hadoop -
the open-source implementation of Map/Reduce - and throws light upon the function-
alities of Hadoop that have been used in this project.
Chapter 3 explores the existing join algorithms targeted at Map/Reduce and intro-
duces some new algorithms for multi-way joins. Section 3.2 discusses two-way joins
(joins involving two datasets) and section 3.3 addresses multi-way joins (joins involv-
ing more than two datasets). Thechapterdescribes theprosand cons of each algorithm,
discussing their suitability for a given situation.
Experimental results are evaluated in chapter 4. Detailed analysis is done for each
algorithm with different input data sizes and with clusters consisting of different num-
ber of participating machines.
Chapter 5 concludes the thesis. It summarizes the various observations made dur-
ing the project and suggest some future avenues for research.
Library control class:C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF
Easy to create searchable and scanned PDF files from PowerPoint. Description: Convert to PDF/TIFF and save it on the disk. Parameters:
www.rasteredge.com
Library control class:C# Create PDF from Word Library to convert docx, doc to PDF in C#.
Easy to create searchable and scanned PDF files from Word. Description: Convert to PDF/TIFF and save it on the disk. Parameters: Name, Description, Valid Value.
www.rasteredge.com
Chapter 2
Map/Reduce and Hadoop
2.1 What is Map/Reduce?
Map/Reduce [9] is a “programming model and an associated implementation for pro-
cessing and generating large data sets”. It was first developed at Google by Jeffrey
Dean and Sanjay Ghemawat. Their motivation was derived from the multitude of
computations that were carried out everyday in Google that involved huge amounts of
input data. These computations usually happened to be conceptually straightforward.
For instance, finding the most frequent query submitted to Google’s search engine on
any given day or keeping track of the webpages crawled so far. But the input to these
computations would be so large that it would require distributed processing over hun-
dreds or thousands of machines in order to get results in a reasonable amount of time.
And when distributed systems came into picture, a number of problems like carefully
distributing the data and partitioning or parallelizing the computation made it difficult
for the programmer to concentrate on the actual simple computation.
Dean and Ghemawat saw a need foran abstraction thatwould help theprogrammer
focuson thecomputation at hand without having to botherabout the complications ofa
distributed system likefault tolerance, load balancing, data distribution and task paral-
lelization. And that isexactly whatMap/Reducewas designed to achieve. A simple yet
powerful framework which lets the programmer writesimple units of work as map and
reduce functions. The framework then automatically takes care of partitioning and
parallelizing the task on a large cluster of inexpensive commodity machines. It takes
careof all the problems mentioned earlier, namely, fault tolerance, load balancing, data
distribution and task parallelization. Some of the simple and interesting computations
for which Map/Reduce can be used include (see [9] for details on each) -
7
Chapter 2. Map/Reduce and Hadoop
8
 Distributed Grep - finding patterns in a number of files at the same time.
 Count of URL access frequency.
 Reverse Web-Link Graph - Given a list of htarget, sourcei pair of URLs, finding
htarget, list(source)i, i.e., finding all the URLs that link to a given target.
 Construction of Inverted Indices from crawled web pages
 Distributed Sort
The idea was soon picked up by the open-source community, the Apache Software
Foundation specifically, and developed into an open-source project and subsequently
into afull-fledged framework and implementation called Hadoop [2]. Hadoop is freeto
download and now boasts of a very large community of programmers and enterprises
that includes large Web 2.0 corporates like Yahoo. Hadoop is discussed in more detail
in the coming sections.
To createaMap/Reducejob, aprogrammer specifiesa mapfunction and areduce
function. This abstraction is inspired by the ‘map’ and ‘reduce’ primitives present in
Lisp and many other functional languages. The Map/Reduce framework runs multiple
instance of these functions in parallel. The map function processes a key/value pair to
generate another key/value pair. A number of such map functions running in parallel
on thedatathatispartitioned acrossthe cluster, produce asetof intermediatekey/value
pairs. The reduce function then merges all intermediate values that are associated
with the same intermediate key (see figure 2.1).
map (k1, v1) ! k2,v2
reduce (k2, list(v2)) ! v3
Programs written in thisfunctionalstyleareautomatically parallelized by theMap/Re-
duce framework and executed on a large cluster of commodity machines. As men-
tioned earlier, therun-timesystem takescareofthedetails ofdatadistribution, schedul-
ing the various map and reduce functions to run in parallel across the set of ma-
chines, handling machine failures, and managing the required inter-machine commu-
nication. This allows programmers without any prior experience with parallel and
distributed systems to easily utilize the resources of a large distributed system.
Chapter 2. Map/Reduce and Hadoop
9
Figure 2.1: Map Reduce Execution Overview [9]
2.2 Map/Reduce Breakdown
Figure 2.1 gives an overview of the Map/Reduce execution model. Before explaining
the steps involved in a Map/Reduce job, lets clarify the terminology that will be used
from this point on in this thesis (unless specifically specified otherwise) -
 Machine - an actual physical computer, which is part of a distributed cluster
 Task or Worker - a process running on a machine
 Node- Thiscan be thought of as a process handler. This will become moreclear
when we discuss Hadoop where a Node is basically a Java Daemon
1
.Nodes run
on the machinesthat are part of the cluster. Ideally, one machine will correspond
to one node.
An entire “Map/Reduce Job” [9] can be broken down into the following steps (re-
produced here from [9] with a few modifications) -
1. The Map/Reduce framework first splits the input datafiles into M pieces of fixed
size - this typically being 16 megabytes to 64 megabytes (MB) per piece (con-
1
AJava Daemon is a thread that provides services to other threads running in the same process as
the daemon thread
Chapter 2. Map/Reduce and Hadoop
10
trollable by the user via an optional parameter). These M pieces are then passed
on to the participating machines in the cluster. Usually there are 3 copies (user
controllable) of each piece for fault tolerance purposes. It then starts up many
copies of the user program on the nodes in the cluster.
2. One of the nodes in the cluster is special - the master. The rest are workers that
are assigned work by the master. There are M map tasks and R reduce tasks to
assign. R is either decided by the configuration specified with the user-program,
or by the cluster wide default configuration. The master picks idle workers and
assignseach oneamap task. Oncethemap tasks have generated the intermediate
output, the master then assigns reduce tasks to idle workers. Note that all map
tasks have to finish before any reduce task can begin. This is because the reduce
tasks take output from any and every map task that may generate an output that
it will need to consolidate.
3. A worker who is assigned a map task reads the contents of the corresponding
input split. It parses key/value pairs out of the input data and passes each pair
to an instance of the user defined map function. The intermediate key/value
pairs produced by the map functions are buffered in memory at the respective
machines that are executing them.
4. The buffered pairs are periodically written to local disk and partitioned into R
regions by the partitioning function. The framework provides a default parti-
tioning function but the user is allowed to override this function for allowing
custom partitioning. The locations of these buffered pairs on the local disk are
passed back to themaster. The masterthen forwards these locationsto the reduce
workers.
5. When a reduce worker is notified by the master about these locations, it uses
remote procedure calls to read the buffered data from the local disks of the map
workers. When a reduce worker has read all intermediate data, it sorts it by the
intermediate keys (k2 in the definition given earlier for the reduce function)
so that all occurrences of the same key are grouped together. The sorting is
needed because typically many different keys map to the same reduce task. If
the amount of intermediate data is too large to fit in memory, an external sort is
used. Onceagain, theuserisallowed to overridethe default sorting and grouping
behaviours of the framework.
Chapter 2. Map/Reduce and Hadoop
11
6. Next, the reduce worker iterates over the sorted intermediate data and for each
uniqueintermediate key encountered , it passes thekey and thecorresponding set
of intermediate valuesto the users reduce function. Theoutputof the reduce
function is appended to a final output file for this reduce partition.
7. When all map tasks and reducetasks have been completed, the master wakes up
theuser program. At this point, the Map/Reducecall in the user program returns
back to the user code.
2.3 Map/Reduce Example
To better understand the Map/Reduce, lets consider an example. Given below are the
map and reduce function for categorizing a set of numbers as even or odd.
map(String key, Integer values)
f
//key : File Name
//values : list of numbers
for each v in values:
if(v%2==0)
EmitIntermediate("Even", v)
else
EmitIntermediate("Odd", v)
g
reduce(String key, Iterator values)
f
//key: Even or Odd
//values : Iterator over list of numbers
//(categorized as odd or even)
String val = ""verbatim
while(values.hasnext())
f
val=val+","+values.toString()
g
Documents you may be interested
Documents you may be interested