在MongoDB中执行类似于DENSE_RANK的最佳方法是什么？

Question

SQL Server和Oracle都有DENSE_RANK函数。这个函数可以让你在仅返回记录的子集时获取其全局排名，比如：

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

在MongoDB中，做同样的事情最好的方法是什么？

- kgriffs

Answer 1

经过一些实验，我发现可以基于MapReduce构建排名函数，假设结果集适合最大文档大小。

举个例子，假设我有这样一个集合：

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

我可以执行类似于DENSE_RANK的大致等价操作，如下所示：

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

为了比较，这里提到了“天真”的方法：

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

我在MongoDB 1.8.2的单个实例上对这两种方法进行了基准测试，使用了以下代码：

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

尽管MapReduce比我预期的要快，但是对于更大的集合大小，特别是一旦缓存被预热后，朴素的方法表现更好：

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

目前来看，朴素方法似乎是可行的选择，但我很想知道在今年后期MongoDB团队继续提高MapReduce性能之后情况是否会有所改变。

- kgriffs

Answer 2

如果您的分数字段直接在文档中，密集排名就是文档在某个排序顺序中的索引。

假设您有一个游戏得分的集合，例如：

{user: "dcrosta", score: 10}
{user: "someone", score: 18}
{user: "another", score: 5}
...

然后（假设您在分数上有索引），要获取排名，您只需按分数排序查询（在此处显示为pymongo语法）：

scores = db.scores.find().sort('score', pymongo.DESCENDING)
for rank, record in enumerate(scores, start=1):
    print rank, record['user']

# prints
1 someone
2 dcrosta
3 another

如果您对Python不熟悉，enumerate函数将创建一个迭代器，返回(index, element)的一组数据。

编辑：我假设您想要一个排名表——如果您正在寻找特定用户的排名，则Richard的答案或类似答案是您需要的。

- dcrosta

---

谢谢你的想法。不幸的是，这对我行不通，因为我需要知道例如“dcrosta”的全球排名是“2”，即使我查询时省略了一个或多个其他文档。如果我能够在结果中返回索引值，那将非常方便；然后我就可以在分数上添加索引。 - kgriffs

“密集排名”仅仅是某个排序顺序下文档的索引并不正确。如果两行具有相同的“SomeField”，那么它们将具有相同的密集排名，但它们将具有不同的索引。 “dense_rank”和“rank”窗口函数与“row_number”窗口函数不同。 - mu is too short