Gibt es eine Möglichkeit, das Äquivalent von DENSE_RANK in MongoDB effizient auszuführen?

SQL Server und Oracle verfügen beide über DENSE_RANK-Funktionen. Gibt es eine Möglichkeit, in MongoDB etwas Ähnliches zu tun, ohne auf MapReduce zurückgreifen zu müssen? Mit anderen Worten, nehmen wir an, Sie haben eine T-SQL-Auswahlklausel wie diese:

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

Was ist der beste Weg, um dasselbe in MongoDB zu tun?

(Hinweis: Dies ist ein Repost der MongoDB-Frage hier . Ich hoffe, mehr Feedback von DBAs zu erhalten ...)

MongoDB hat kein Konzept für ein Ranking. Der nächste, den ich finden konnte, kommt von hier :

Hier einige Beispieldaten:

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

Finden Sie zuerst die Punktzahl des Benutzers "dave":

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

Zählen Sie dann, wie viele Benutzer eine höhere Punktzahl haben:

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

Da es 1 höhere Punktzahl gibt, ist Daves Rang 2 (addieren Sie einfach 1 zur Anzahl der höheren Punktzahlen, um den Rang zu erhalten).

Offensichtlich ist dies alles andere als ideal. MongoDB verfügt jedoch einfach über keinerlei Funktionen, da es einfach nicht für diese Art der Abfrage ausgelegt ist.

Nach einigen Experimenten stellte ich fest, dass es möglich ist, eine Ranglistenfunktion basierend auf MapReduce zu erstellen, vorausgesetzt, die Ergebnismenge passt in die maximale Dokumentgröße.

Angenommen, ich habe eine Sammlung wie diese:

{ 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" }
...

Ich kann das grobe Äquivalent eines DENSE_RANK wie folgt ausführen:

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;
}

Zum Vergleich ist hier der an anderer Stelle erwähnte "naive" Ansatz:

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;
}

Ich habe beide Ansätze an einer einzelnen Instanz von MongoDB 1.8.2 mit dem folgenden Code verglichen:

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;
}

Während MapReduce schneller war als ich erwartet hatte, hat der naive Ansatz es für größere Sammlungsgrößen aus dem Wasser geblasen, insbesondere nachdem der Cache aufgewärmt wurde:

> 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 ]

Im Moment sieht es so aus, als ob der naive Ansatz der richtige Weg ist, obwohl ich gespannt sein werde, ob sich die Geschichte später in diesem Jahr ändert, wenn das MongoDB-Team die MapReduce-Leistung weiter verbessert.