SQL, which is the standard language for database processing on relational
databases, has also evolved along with the evolution of map-reduce as a program
paradigm. Sql, by itself, is difficult to compile
directly into map-reduce, and a more finer level of programming is required to get
reasonable efficiency. There are two languages which are popular
in this regard. There is Pig, which came out of Yahoo, and
Hive, which came out of Facebook. Each of these is a form of sequel
primitives but executed procedurally rather than in a single functional
statement. So, for example, if one were to do the,
the calculation that we did last week that using map-reduce that is first trying to
figure out the sales and cities that match for a particular address ID by joining the
sale and city tables on address and then, joining the results on the city to
essentially get sales by city. This is how Pig and Hive make this
programming a little bit easier. So, the COGROUP command in Pig is
essentially a map-reduce join. The generate for each parallel, no
construct is essentially a map construct, which essentially deals, deals with the
output of the first join and creates what the keys are.
And then, again, there's a second map-reduce which is done by grouping on
city. And then, the FOREACH generates what the
output one wants, the, what is the reduce.So, essentially, the without going
into great detail, what Pig does is it takes these statements and compiles them
into a map-reduce program. Hive is sort of similar, just a little bit
closer to sequel, where you can actually do a select statement with a limited form
of join and a similar kind of select statement for the second join.
Both of these are quite popular now. Pig has one advantage that it works
directly on the distributed file system, HDFS, if one wants to.
Or it can also work with Hbase. Hive on the other hand, requires data to
be stored in its own format, on top of HDFS.
So, it has it's own database rather than the Hbase and cannot work directly on flat
files. But both of these have become reasonably
popular for coding map-reduced programs as opposed to writing map and reduce
functions in a programming language like Python or Java, the way you did in your
assignment. Another direction where SQL is evolving is
to introduce statistical primitives within the database itself.
One example of this is the, MADlib library which works on the Greenplum big data
database. And this work is emanated from the
University of California at Berkeley. I'll illustrate MADlib with a simple
example which you can see directly on the website for MADlib and this is essentially
taken from there. Suppose one has training data, just as we
discussed last week training for [unknown] classifier, we have attributes which take
values, you know, one, two, three, one, two, one, etc.
And their classes, yes, maybe, no, the positives sentiment, negative sentiment,
whatever. And, one wants to create a classifier.
Well, the way we did it last week, one would have to compute this using programs,
maybe using map-reduce. But in MADlib, we can create a classifier
using extensions to SQL itself. So, suppose we want to create a classifier
using this training set and classify in the end these two new samples which are
present in another table called toclassify.
This is how one would does, one does it. You first do a preparation statement where
essentially one is computing the likelihood values from the training set
and the prior probabilities. Next one actually creates the
classification using the two classify tables that one wants to classify, and
then returns the actual classification. So, it's internally created a [unknown]
base classifier. If one wants more details, one can
actually figure out what the likely hood values were.
So, one finds that for the first element in the two classified table, we have a 0.4
chance of a one and a 0.6 chance of a two, and that's why it was classified as two.
Whereas, the second one, we had a 0.75 chance of a one and a 0.2 for a chance of
a two. And therefore, were classified as two.
We haven't gone into the details of the syntax, but I guess the, the idea is there
are, there are similar parameters for set, for example, for computing regressions and
other types of machine learning which we will study in the following lecture after
this one. But this is one direction in which
databases are evolving to try to include within SQL, some statistical or machine
learning primitives. Next, map-reduce is also evolving and the
main element that one needs to add to map-reduce is iteration.
Essentially, many applications require one to apply map-reduce again and again.
Continuous page rank calculations is one example.
Continuously updating an index is another. Continuous machine learning by updating
the training set with fresh values and corrections, is a third.
And there are many such examples. Of course, there are many ways of
iterating. The simplest is simply to run map-reduce
again and again. But the trouble with that is, that every
time one is writing to the distributed file system, which is costly, so there
have been some attempts at trying to make this approach of iterating map-reduce
directly more efficient by essentially avoiding the data copy and pipelining the
output of the reducers directly into the map phase of the next iteration of
map-reduce. Another example of iteration is
generalizing the map produced paradigm to a general data flow graph, where map and
produce are simply two types of operations and one can have a general, directed graph
of such tasks and data can flow across such a graph.
The key feature that is important here is the tasks block just like map and reduce
tasks so that one map task needs to process all its data before moving on, and
that's critical for fault tolerance as we've seen in map-reduce, if a mapper
fails, one can simply restart the mapper with whatever data was given simply
because it hasn't written anything. So, blocking tasks are essential for fault
tolerance. An example of such data flow systems are,
is the Dryad link system from Mira, from Microsoft, the Hyracks research project,
and a few others. Lastly, there are implementations of
recursion directly in map-reduce. And here, the challenge is how to recover
if tasks, which are no longer now blocking, because you're doing iteration
using recursion and recursion requires every step to essentially produce an
output, otherwise, the next recursion cannot begin.
So, how does one recover from non-blocking tasks failing?
There are two main models here. There's a graph based model which is
exemplified by Pregel and Giraph and there's a stream model which is
exemplified by S4. We're not going to go into details of
these in this course we just don't have the time.
But the, for those brighter students amongst you looking for a research work in
map-reduce, these are three essential areas where, on essential ways, which
iteration is being made more efficient in map-reduce in our promising areas for
doing fresh research.