[MUSIC]. 
So let's look at an example that doesn't 
involve processing a corpus of documents. 
So, let's think about how to implement a 
relational the join operation that we 
learn from the relation algebra in Map 
Reduce. 
Okay, so here recall that you're given 
two relations, and a relation is a set of 
tuples, all right? 
And you're trying to find every record in 
one relation that corresponds to a record 
in the other relation, right? 
And so here, we're going to join on SSN 
equal to EmpSSN. 
And actually, it wasn't quite correct for 
me to leave this unspecified. 
There's the notion of a natural join, 
that would match up with the field names. 
they had to remade was mash but here they 
don't. 
So, I need be explicit on what I'm 
joining on. 
Okay, and so the output here is, these 
three records. 
This record with joins with these two, 
and this record joins with this one, 
fine. 
Now, image that both of these relations 
are huge. 
Okay, so the map phase here is going to 
process every two [INAUDIBLE] in general. 
And we have a problem right off the bat 
that join is a binary operation. 
It has a two-input relations a left 
relation and the right relation and 
you're trying to corresponding two equals 
one and match the other. 
Is a unary operation that processes a 
single data set. 
So how can you, you know, at first, to 
first approximation you can't express 
join in map reduce period. 
But that's okay, there's a, there's a, 
there's a bit of a trick here. 
The trick is look you know, if it's okay 
that you know imagine the data set here 
is just a big jumble of tuples. 
It's doesn't matter what table they came 
from we just lump them all together. 
Into a single data set called tuples. 
Okay, and that will be what we process 
with map reduce. 
Okay, and so here I'm asking the question 
you know, what is this for? 
Well, this is a label that we've attached 
to every tuple, so that we can know where 
it came from and that's used later. 
Okay, now I 'm not being specific about 
how, where you get this label or how you 
do it in MapReduce. 
But I want you to think logically that 
it's necessary and in practice it's not 
that difficult. 
Probably because you know, for example, 
if you're processing, you have 
distributed files from this directory 
representing all the employee chunks And 
you've got distributed files in this 
directory representing the assigned 
departments chunks. 
You can look at the file name to tell 
what table it is. 
And so in the map function that you 
write, you can determine that aha, this 
has file name, you know, this has the 
employee relation name in it's, in it's 
file path and I'm going to go ahead and 
attach that as part of the record, okay? 
And so we could write pseudo code for 
this. 
And in fact, you might, as part of the an 
upcoming assignment, alright? 
[INAUDIBLE], so what's the map phrase 
look like of this relational join? 
Well, for every record on the input 
you're going to produce a key value pair. 
We know we have to produce key value 
pairs, because that's how MapReduce 
works. 
So what's the key going to be? 
Well, I'm going to give you, the key is 
going to be the join attribute, the 
attribute that you're joining on, and the 
value is going to be sort of everything 
else, all right? 
The rest of the tuple, and we can 
actually get away with removing this guy 
to save some space but typically 
typically you wouldn't bother. 
Okay, so fine. 
So, given a tuple that looks like this 
with, with three fields, we produce a key 
of seven seven seven seven seven seven so 
on. 
And the value is the entire tuple, and so 
on. 
And again notice that both the tuple from 
both relations are all lumped into the 
same input. 
Alright, I may be belaboring this but I 
want to make sure that it's clear. 
Okay, so so far we've done two tricks. 
One is lump everything together and two 
is produce a key value pair with a key as 
the joint attribute. 
Now, what happens in the magic shuffle 
phase? 
Well Everything with the same key gets 
lumped together, as we've talked about. 
And so now you get a reducer invocation 
that has you know, one reducer invocation 
for every unique key. 
So in this case, it would be one for 999 
so on, one for 777 so on and the list of 
values. 
Associated with that key will be all the 
tuple that share the same join key. 
Now it doesn't matter what relation they 
came from they'll all be in this list. 
So in this case we get one tuple from the 
employee relation, and we get one tuple 
from the department relation. 
And here we get one from the employee 
relation, and two tuples from the 
department relation. 
Alright, so now in the context of a 
single computer, we have everything we 
need to compute a single join. 
And further, each of these reduce 
invocations can be done on a separate 
machine, and that's how we scale. 
So now this reduce function that the 
program would have to write if you are 
implementing a join phase would have to 
take this key, and takes all these tuples 
and produce the joined tuple, right? 
Where these two attributes came from 
employee and these two attributes came 
from department. 
And same thing here employee, department. 
Now, if you want to think about what kind 
of operation you need to implement in 
this reduce function. 
Well, you've got a set of tuples from one 
relation and you need to associate it 
with every possible tuple from the other 
relation, right because we need to know 
they all join. 
They're all by definition, they all join, 
they have the same key, they all match. 
So if you have every member of a set 
paired with. 
Every possible member of another set, if 
you remember that's a cross product 
operation. 
And so here again we see relation 
[INAUDIBLE] popping up sort in a, in a 
different context. 
Okay, so I don't want to confuse you to 
much with the overall operation we're 
trying to do is implement a parallel 
join. 
It happens to be that locally that right 
here inside one reduce function. 
We recognize, aha, that's another 
relational algebra operator, a cross 
product. 
But this is more for abstraction purposes 
than for algorithm purposes, I just 
want to point that out. 
All right, so again, you put on your 
relation algebra colored glasses and the 
whole world, you know, these operators 
start to pop up, pop up everywhere. 
All right, so fine, so let's do this one 
more time just to make sure it's clear. 
So, I'm giving, giving you two relations, 
order and line item and they have these 
fields; an order ID, an account and a 
date and here there's an order ID, an 
item ID and a quantity and we're going to 
join on order ID. 
So what's the map phase look like? 
Well, once again, the key will be the 
join key in this case order ID and the 
value will be this pair. 
The relation name, along with the 
original tuple. 
And before, we just sort of lumped these 
together in one tuple and it doesn't 
matter very much. 
Here I've kind of structured it slightly 
differently, but the point is, is all the 
information is here. 
The key must be the join key and value is 
the tuple as well as some sort of 
indicator for of what relation it came 
from. 
So, maybe I'll ask real quick. 
Why do I need that indicator of the 
relation? 
Well, in the reduced phase, I wouldn't be 
able to produce the joint tuples properly 
if we didn't know which, which two 
peoples went with which relation. 
If I just had a big bundle of tuples and 
I couldn't really figure it out very 
easily, that would be a problem. 
Theoretically, you might be able to avoid 
tagging explicitly with employee and 
department because you could deduce that 
well, the employee table is the one that 
has a string first followed by the join, 
followed by the join key and the 
department relation has the join key 
followed by some other string. 
But it's a little dangerous to rely on 
that kind of information, because you 
could, you could be joining two tables 
that have exactly the same schema. 
And there wouldn't be any real obvious 
way to figure it out. 
So an explicit tag is a little bit safer 
here, alright, fine. 
So that's the map phase. 
Process all the, we, we lump all the 
records together. 
And produce key value pairs, where the 
key is the join key from the, from the 
corresponding relation. 
Join attribute from the corresponding 
relation, and the value is the entire 
tuple tag with this, with the relation 
name, okay? 
And there it is [LAUGH], right there on 
the slide. 
Okay, so what's the reducer look like? 
Well Now we've got all the tuples that 
have this share the same key together and 
it will produce these joined tuples. 
It will join this order tuple with both 
of these line item tuples to produce 
these two joined tuples. 
Okay, fine. 
So, now lets go and do a different 
example, and so here may be we're 
going to get started with analyzing the 
social networks. 
So here we have a graph where every edge 
represents A, let's say a friend 
relationship. 
Or if you're thinking about Twitter, you 
can always be a followers relationship. 
So, the input here is a set of edges with 
the semantics of Jim is friends with Sue, 
or follows Sue, and Sue is friends with 
Jim, or follows Jim, and so on. 
And so, one point I'm making here is 
you'll notice that if, if Lin follow, if 
Jim, if Lin points to Joe then Joe points 
to Lin, and so this is there's a 
symmetric relationship here, okay? 
And I've done that for simplicity sake to 
sort of avoid the confusion that can 
result from thinking about undirected 
graphs versus directed graphs. 
So, any time you see an edge going one 
way you'll see the other edge coming 
back. 
Now, what we want to do here is, well 
before, before I say what we're going to 
do, is make sure task is clear. 
We're going to count the friends. 
We want something very simple. 
We just want to say, how many friends 
does Jim have? 
And how many friends does Sue have, and 
so on. 
And so the desired output here is Jim 
with three, because Jim has Sue as a 
friend and Jim has Kai as a friend and 
Jim has Lin as a friend. 
And we want to have Lin equals two, or 
Lin has two friends, becaue Joe and Jim 
and Kai is just one, right here. 
Jim and Joe is just one, which is right 
here, Lin, okay? 
So, this should already look like 
something we've already done. 
Like before so it happens to be social 
network analysis and the records happen 
to be these you know, pairs of people but 
the algorithm you're going to use should 
start to stand out to you okay and maybe 
you'll see why in a second if it's not 
clear. 
So, in the math phase how are we going to 
do this well for every you know, friend 
on the left hand side produce a key value 
pair with the key is the name of the 
friend or the name of the person and the 
value is just the number one indicating 
that there is exactly one friend 
associated with that. 
So exactly there is, there is that we've, 
that we've encountered 1 friend 
associated with. 
Say Jim in this case alright? 
So this record gets turned into Jim and 1 
and this record gets turned into Sue and 
1 and this record gets turned into Lin 
and 1 and so on. 
Okay and then you know, through the magic 
of map produce the shuffle phase produces 
this new media result where we have Jim 
the key associated with a list of 
occurrences 1, 1 and 1. 
And Lin associated with two occurrences, 
and so on. 
And in the reduced phase, just sim-, 
simply adds up all of these occurrences. 
And so, what does this remind you of? 
Well, it's a lot like the word count 
example, right? 
Instead of documents, producing words and 
counts. 
It's even simpler. 
It's for every record it just produces a 
single count for that for that person 
that the record represents, the person on 
the left hand side. 
And after that the reducer is literally 
exactly the same, right? 
It'll, it'll add up all the occurrences 
and produce a single number. 
Okay, so in the next segment, we'll talk 
about something a little more, a little 
trickier. 
which is implementing matrix 
multiplication in MapReduce, alright?