How to maintain a sorted list in database?-CodePudding

I have a very large list of users (in the millions) stored in a database (Mongo in our case). Each user has a score associated with it. The score is constantly changing based on actions of the user.

I want to be able to query for the position of each user when the list is sorted by score.

Right now, I have an index on the score. I query for all users, sort them by score, and then iterate through to find the position of the user I want.

var users = User.find({})
  .sort({
    score: -1
  });

var position = 1;
for (
  let user = await users.next(); user !== null; user = await users.next()
) {
  if (user === targetUser) {
    return position;
  }
  position  ;
}

Sorting is a slow operation but from my understanding the index orders it already, so this is only as expensive as fetching all the records.

I can maybe increase the speed of finding the element by implementing a binary search since the list is sorted.

The bigger problem is storing the list in memory (I keep running into heap out of memory errors in Node).

What is the right database data structure to achieve what I want?

CodePudding user response：

@barrypicker I tried this and it is slightly faster, but still very slow (on the order of 20 seconds). But it may solve my memory issue problem I think?

  // Get target user
  let target = await User.findOne({
    _id: targetId
  });

  // Find number of users with lower score without bringing all of them into memory
  let lowerScoreCount = await User.count({
    score: { $lt: target.score }
  });

  // Find all users with same score
  let sameScoreSignups = await User.findOne({
    score: target.score
  });

  // Iterate over users with same score till you find your user and add this to the lower score count to get the position of the user in the sorted list
  let position = lowerScoreCount;
  sameScoreSignups.forEach((user) => {
    if (user._id === targetId) {
      return position;
    }
    position  ;
  });

  return position;

CodePudding user response：

You may leverage $setWindowFields and $rank available starting from MongoDB v5.0 .

db.collection.aggregate([
  {
    "$setWindowFields": {
      "partitionBy": null,
      "sortBy": {
        "score": -1
      },
      "output": {
        "rank": {
          $rank: {}
        }
      }
    }
  },
  {
    $match: {
      _id: <target user's identifier>
    }
  }
])

Here is the Mongo playground for your reference.