8

SQL Server and Oracle both have DENSE_RANK functions. Is there a way to do something similar in MongoDB without having to resort to MapReduce? In other words, suppose you have a T-SQL select clause like this:

SELECT DENSE_RANK() OVER(ORDER BY SomeField DESC) SomeRank

What is the best way to do the same thing in MongoDB?

(Note: This is a repost of the MongoDB question over here. I'm hoping to get more feedback from DBAs...)

  • Bold question, indeed. If you find the answers to your MongoDB questions satisfactory here in the DBA.SE, please let others know to bring their questions and answers here as well. +1 !!! – RolandoMySQLDBA Aug 20 '11 at 21:59
5

MongoDB doesn't have any concept of ranking. The closest I could find comes from here:

Here's some sample data:

 > db.scoreboard.find()`
 { "_id" : ObjectId("4d99f71450f0ae2165669ea9"), "user" : "dave", "score" : 4 }
 { "_id" : ObjectId("4d99f71b50f0ae2165669eaa"), "user" : "steve", "score" : 5 }`
 { "_id" : ObjectId("4d99f72350f0ae2165669eab"), "user" : "tom", "score" : 3 }

First, find the score of the user "dave":

 db.scoreboard.find({ user : "dave" }, { score : 1 }) { "_id" : ObjectId("4d99f71450f0ae2165669ea9"), "score" : 4 }

Then, count how many users have a higher score:

 db.scoreboard.find({ score : { $gt : 4 }}).count() 
 1

Since there is 1 higher score, dave's rank is 2 (just add 1 to the count of higher scores to get the rank).

Obviously, this is far from ideal. However, MongoDB simply does not have any type of functionality for this since it's simply not designed for this type of querying.

  • 2
    Actually, it does have the functionality via MapReduce, it's just slow. – kgriffs Aug 24 '11 at 4:09
  • @Kurt Oh, you should post that as the answer! The internets would really appreciate it, I'm sure. ;) – Richard Aug 24 '11 at 11:46
5

After some experimentation, I found that it is possible to build a ranking function based on MapReduce, assuming the result set can fit in the max document size.

For example, suppose I have a collection like this:

{ player: "joe", points: 1000, foo: 10, bar: 20, bang: "some text" }
{ player: "susan", points: 2000, foo: 10, bar: 20, bang: "some text" }
{ player: "joe", points: 1500, foo: 10, bar: 20, bang: "some text" }
{ player: "ben", points: 500, foo: 10, bar: 20, bang: "some text" }
...

I can perform the rough equivalent of a DENSE_RANK like so:

var m = function() { 
  ++g_counter; 

  if ((this.player == "joe") && (g_scores.length != g_fake_limit)) { 
    g_scores.push({
      player: this.player, 
      points: this.points, 
      foo: this.foo,
      bar: this.bar,
      bang: this.bang,
      rank: g_counter
    });   
  }

  if (g_counter == g_final)
  {
    emit(this._id, g_counter);
  }
}}


var r = function (k, v) { }
var f = function(k, v) { return g_scores; }

var test_mapreduce = function (limit) {
  var total_scores = db.scores.count();

  return db.scores.mapReduce(m, r, {
    out: { inline: 1 }, 
    sort: { points: -1 }, 
    finalize: f, 
    limit: total_scores, 
    verbose: true,
    scope: {
      g_counter: 0, 
      g_final: total_scores, 
      g_fake_limit: limit, 
      g_scores:[]
    }
  }).results[0].value;
}

For comparison, here is the "naive" approach mentioned elsewhere:

var test_naive = function(limit) {
  var cursor = db.scores.find({player: "joe"}).limit(limit).sort({points: -1});
  var scores = [];

  cursor.forEach(function(score) {
    score.rank = db.scores.count({points: {"$gt": score.points}}) + 1;
    scores.push(score);
  });

  return scores;
}

I benchmarked both approaches on a single instance of MongoDB 1.8.2 using the following code:

var rand = function(max) {
  return Math.floor(Math.random() * max);
}

var create_score = function() {
  var names = ["joe", "ben", "susan", "kevin", "lucy"]
  return { player: names[rand(names.length)], points: rand(1000000), foo: 10, bar: 20, bang: "some kind of example text"};
}

var init_collection = function(total_records) {
  db.scores.drop();

  for (var i = 0; i != total_records; ++i) {
    db.scores.insert(create_score());
  }

  db.scores.createIndex({points: -1})
}


var benchmark = function(test, count, limit) {
  init_collection(count);

  var durations = [];
  for (var i = 0; i != 5; ++i) {
    var start = new Date;
    result = test(limit)
    var stop = new Date;

    durations.push(stop - start);
  }

  db.scores.drop();

  return durations;
}

While MapReduce was faster than I expected, the naive approach blew it out of the water for larger collection sizes, especially once the cache was warmed up:

> benchmark(test_naive, 1000, 50);
[ 22, 16, 17, 16, 17 ]
> benchmark(test_mapreduce, 1000, 50);
[ 16, 15, 14, 11, 14 ]
> 
> benchmark(test_naive, 10000, 50);
[ 56, 16, 17, 16, 17 ]
> benchmark(test_mapreduce, 10000, 50);
[ 154, 109, 116, 109, 109 ]
> 
> benchmark(test_naive, 100000, 50);
[ 492, 15, 18, 17, 16 ]
> benchmark(test_mapreduce, 100000, 50);
[ 1595, 1071, 1099, 1108, 1070 ]
> 
> benchmark(test_naive, 1000000, 50);
[ 6600, 16, 15, 16, 24 ]
> benchmark(test_mapreduce, 1000000, 50);
[ 17405, 10725, 10768, 10779, 11113 ]

So for now, it looks like the naive approach is the way to go, although I'll be interested to see if the story changes later this year as the MongoDB team continues improving MapReduce performance.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.