Background

As the title says, this is yet-another-tutorial on Map Reduce using MongoDB. But two things that are different here:

  1. A problem solving approach is used, so we’ll take a problem, solve it in SQL first and then discuss Map Reduce.
  2. Lots of diagrams, so you’ll hopefully better understand how Map Reduce works.

 

The Problem

So without further ado, let us get started. We’ll use the GeoBytes’ free GeoWorldMap database. It is a database of countries, their states/regions and major cities. You can find this database on this page under Geobytes’ Free Services section. The zip archive contains CSV files and instructions on importing this data to MySQL are available here.

The task is to find the 2 closest cities in each country, except in United States. (I excluded USA because over 75% of the cities in “cities” table are from USA, and by excluding it the results arrive much faster! Plus, it gives an additional flavor to the task.)

alt
This image on top displays field and corresponding datatypes of “cities” table. Note the fields CountryID, Latitude and Longitude.

 

Assumptions

For sake of simplicity, we’ll represent earth as a 2D plane. The distance between any two points P1 (x1,y1) and P2 (x2,y2) on a 2D plane is computed as Square-Root of { (x1-x2)2 + (y1-y2)2 }

 

SQL Solution

If the distance between each pair of cities in a country were known then we could simply apply a GROUP BY statement where we divide the data by Country and find those two cities where the distance is minimum. Since data is not available in this form, let’s try to manipulate it to get the desired structure.

/* QUERY1 - VIEW: city_dist */
create view city_dist as
select c1.CountryID,
	c1.CityId, c1.City,
	c2.CityId as CityId2, c2.City as City2,
	sqrt(pow(c1.Latitude-c2.Latitude,2) + pow(c1.Longitude-c2.Longitude,2)) as Dist
from cities c1 inner join cities c2
where c1.CountryID = c2.CountryID /* Country should be same */
and c1.CityId < c2.CityId  /* Calculate distance between 2 cities only once */
and c1.CountryID <> 254 /* Don't include US cities */; 

 

Now that we have distance between each pair of cities, we can now group this data by country and then proceed to select those 2 cities that have the least value for “Dist” field but still greater than zero. This can be accomplished easily as shown below:

 

/* QUERY 2 */
select city_dist.*
from (
	select CountryID, min(Dist) as MinDist
	from city_dist
	where Dist > 0 /* Avoid cities which share Latitude & Longitude */
	group by CountryID
) a inner join city_dist on a.CountryID = city_dist.CountryID and a.MinDist = city_dist.Dist;

 

That completes our SQL solution to the given problem. (You can delete the View “city_dist” later)

It is important to note the steps we followed. In the first step we performed all the computations (by calculating the distance between 2 cities of each country). In the next step we grouped (or divided) our results by country and selected those 2 cities where the value of distance was least. These steps can be represented graphically as shown below.

SQL 2 step solution

 

 

Map Reduce Solution

We can easily import our “cities” table from MySQL to MongoDB using MongoVUE. Instruction on importing are available here. Once this is done, a sample document in MongoDB looks like this:

Sample document in "cities" collection

 

Map Reduce is a 3 step approach to solving problems.

Map Reduce 2 step approach

 

Step 1 – Map

Map step is used to group or divide data into sets based on a desired value (called Key). This is actually similar to Step 2 of SQL solution above. The Map step is accomplished by writing a JavaScript function, and the signature of this function is given below.

function /*void*/ MapCode() {

}

 

In other words the Map function takes no arguments and returns no data! That doesn’t seem much useful, does it? So lets explore it in greater detail.  Although Map function doesn’t take any arguments, it gets invoked on each document of the collection as a method. Since it is invoked as a method, it has access to “this” reference. So with “this” you can access any data within the “current” document. Something else that is available is the “emit” function and it takes two 2 arguments, first, the key on which you want to group the data. Second argument is the data itself that you want to group.

When we write the Map function, we need to be careful about 3 things.

  1. Firstly, how do we want to divide or group the data? In other words, what is our key? Or what should be passed as the first parameter to “emit” function?
  2. Secondly, what part of the data will we we need or what part of data is extraneous? This helps un in determining the second parameter passed to “emit” function.
  3. Thirdly, in what form or structure do we need our data? This helps us refine the second parameter of “emit” function.

Let’s find the answers to these questions.

  1. It should be quite evident that we will group our data based on “CountryID”. We used the same field in SQL too. So we’ll pass “CountryID” as the first parameter to “emit” function.

 

function MapCode() {
	emit(this.CountryID, ...);
}

 

We certainly don’t care about RegionID, TimeZone, DmaID, County and Code for calculating closest cities. We can easily ignore these. Keys that seems helpful are CityId, City, Latitude and Longitude.

 

function MapCode() {
	emit(this.CountryID,
	{
		"city": this.City,
		"lat":  this.Latitude,
		"lon":  this.Longitude
	});
}

 

With this we have answered our second question as well, i.e. what data is extraneous and what is necessary. Now before we get to the third question above, lets understand a bit more about Reduce. After the Map step completes we obtains a bunch of key-value pairs. In our case, we’ll get a bunch of key-value pairs (where key is CountryID and value is a Json object) as shown in the image below:

emit Function outputs Keys & (associated) Values

Reduce operation aggregates different values for each given key using a user defined function. In other words, Reduce operation will take up each key (or CountryID) and then pick up all the values (in our case Json objects) created from Map step and then one-by-one process them using a custom defined logic. Lets look at the signature of Reduce function.

 

function /*object*/ ReduceCode(key, arr_values) {

}

 

Reduce takes 2 parameters – 1) Key 2) An array of values (number of values outputted from Map step). Output of Reduce is an object. It is important to note that Reduce can be called multiple times on a single key! Yes, you read it correctly. It is not that difficult to think actually – consider a case where your data is huge and it lies on 2 different servers. It would be ideal to perform a Reduce on the given key on first server, and then perform a Reduce for the same key on second server. And then do a Reduce on the results of these two reduced values.

Here is a picture explaining Reduce step.

Reduce step

The picture above shows Reduce being called twice. This is just can example. To be frank, we don’t know how MongoDB executes Reduce. We don’t know which key it is going to be reduced first and which key last. We also don’t know how many times it is going to call reduce for a key. This optimization is better left with MongoDB itself as it finds the most suitable parallel execution for every MapReduce command.

What we do know is that if Reduce is executed more than once then the value returned will be passed in a subsequent reduce as part of input.

For our given problem, we want Reduce to output all the cities of a given country (so that we can then try to find the closest two). So the expected format of final reduced value (rF) is:

 

{
	"data" : [
			{ city E },
			{ city B },
			{ . . .  }
	]
}     

 

But the input values in Reduce array (param 2) should have exactly the same format as the output, as the output may be intermediate and may participate in further Reduce. So lets mould the Map function to produce values in  the above desired format.

 

function MapCode() {
	emit(this.CountryID,
	{ "data":
		[
			{
				"city": this.City,
				"lat":  this.Latitude,
				"lon":  this.Longitude
			}
		]
	});
}

 

Our reduce function simply assimilates all the cities.

 

function ReduceCode(key, values) {

	var reduced = {"data":[]};
	for (var i in values) {
		var inter = values[i];
		for (var j in inter.data) {
			reduced.data.push(inter.data[j]);
		}
	}

	return reduced;
}

 

This brings us to Finalize step. Finalize is used to do any required transformation on the final output of Reduce. The function signature of Finalize is given below:

 

function /*object*/ FinalizeCode(key, value) {

}

 

The function takes a a key value pair, and outputs a value. After the Reduce is complete, MongoDB runs Finalize on each key’s final reduced value. The output of Finalize for all keys is put in a collection, and it is this collection which is the result of Map Reduce. You can give it a desired name, and if left unspecified, MongoDB selects a collection name for you.

image

In our case, we’ll use Finalize to find the closest 2 cities out of all the given cities in a country. Here is the Finalize function.

 

function Finalize(key, reduced) {

	if (reduced.data.length == 1) {
		return { "message" : "This Country contains only 1 City" };
	}

	var min_dist = 999999999999;
	var city1 = { "name": "" };
	var city2 = { "name": "" };

	var c1;
	var c2;
	var d;
	for (var i in reduced.data) {
		for (var j in reduced.data) {
			if (i>=j) continue;
			c1 = reduced.data[i];
			c2 = reduced.data[j];
			d = Math.sqrt((c1.lat-c2.lat)*(c1.lat-c2.lat)+(c1.lon-c2.lon)*(c1.lon-c2.lon));
			if (d < min_dist && d > 0) {
				min_dist = d;
				city1 = c1;
				city2 = c2;
			}
		}
	}

	return {"city1": city1.name, "city2": city2.name, "dist": min_dist};
}

 

This completes our MapReduce solutions as well. We just need to filter out US cities when we invoke this – that is easy enough to do with a simple condition:

 

{
	CountryID: { $ne: 254 }  /* 254 is US CountryID */
}

Points to note

  • While this is clearly not intended to be a benchmark, but still, the SQL solution took about 100 sec on my laptop (the view creation took only 1 sec, rest is spent in grouping and joins. Using a temp table/indexes would speed this up).
  • Map Reduce took 6 seconds to run
  • There are other SQL and MapReduce solutions to this problem. For example, you could open cursors in SQL and iterate through all the records in nested for loops. Similarly, you could do an 2 back to back MapReduce operations without resorting to use of Finalize step. I’ll try to explore these in a future post.

If you want to learn about how to execute these steps in MongoVUE, then refer to this step-by-step tutorial.

Tags: , ,

14 Responses to “Yet another MongoDB Map Reduce tutorial”

  1. Jamal Soueidan December 20, 2010 at 11:40 pm #

    You have good description about mapReduce, thanks for your help :-)

  2. Sammaye December 21, 2010 at 1:52 pm #

    Nicely broken down. Found this to be better explained than the 10gen documentation. That is always the problem with map/reduces they are very hard to understand at first.

    I especially like the “points to note” section at the end. My greatest worry is that my mr’s are slow but knowing they are just as fast as SQL joins and provides me with 10x the manipulating power is really reassuring since I built a realtime reverse indexing relevancy search within Mongo using two separate mr’s and I am always worried about whether it would scale correctly.

    Thanks,

  3. RA January 5, 2011 at 7:05 pm #

    How do I write the map, reduce and finalize functions after that ?

  4. RA January 5, 2011 at 7:15 pm #

    What I mean is that, in mongoVUE I copy/paste the map, reduce and finalize functions from above into the “Map Reduce” field and hit “Go” . After that it says “executing” but it takes too long and i think somwhere keeps the CPU in a loop.

  5. RA January 5, 2011 at 7:25 pm #

    Could you please tell me the shell command how I run thos functions ? Something like this ?

    res = db.users.mapReduce(MapCode,ReduceCode, {finalize:finalize});
    db[res.result].find()

  6. Mardix January 6, 2011 at 5:58 am #

    Thanx.

    Good stuff

  7. David P. Nesbitt June 7, 2011 at 1:20 am #

    This is a great tutorial! Very helpful in understanding map/reduce in MongoDB.

    We found a couple of things that we needed to do get it working on our end.

    1. We had to change “city” in the MapCode data array to “name”.
    2. The US cities filter is crucial. Here is how we got it working:

    res = db.runCommand(
    {
    “mapreduce”: “cities”,
    “map”: MapCode,
    “reduce” : ReduceCode,
    “finalize” : Finalize,
    “query” : { “CountryID” : { “$ne” : 254 } },
    “out”: “closestcities”
    }
    )

  8. Mark July 29, 2011 at 2:44 am #

    Very good description of MapReduce – I have been looking for something other than the word counting example to help me understand it.

    BTW – It would be interesting to know how quick it is without the sqrt calls in the loop, usually the slowest part of such a loop. They are not necessary. You can just compare distance squared and call it once at the end once you have your closest squared distance.

  9. Fatih Samet Cetin September 13, 2011 at 4:19 pm #

    Hi, that was very useful article. I suppose i missed a point. We gather the groups of data but how can we get the count of document which belongs to same group.

    Thank you.

    • ishaan September 15, 2011 at 9:36 am #

      In map step, just say emit(key, {count:1}), and then in reduce add up all the counts!

Trackbacks/Pingbacks

  1. links for 2011-01-24 « Bloggitation - January 25, 2011

    [...] Yet another MongoDB Map Reduce tutorial (tags: mongodb database nosql) [...]

  2. Yet another MongoDB Map Reduce tutorial – Post « Another Word For It - January 25, 2011

    [...] Yet another MongoDB Map Reduce tutorial [...]

  3. How to perform MapReduce operations in MongoVUE – a step-by-step guide | MongoVUE - April 5, 2011

    [...] screens) in MongoVUE for solving the MapReduce problem defined in an earlier tutorial – Yet another MongoDB MapReduce tutorial (should be read before reading the present [...]

  4. Map Reduce « Missional Code - August 11, 2011

    [...] http://www.mongovue.com/2010/11/03/yet-another-mongodb-map-reduce-tutorial/ Filed under: Uncategorized Leave a comment Comments (0) Trackbacks (0) ( subscribe to comments on this post ) [...]