Efficient ways to calculate "ranks" for over 350,000 users

Question

Possible Duplicate:
Mysql rank function

I am making a rank website and each user will have a unique rank based on level. #1 is the best rank and since there's 350,000 users, the worst rank will be #350000.

No user can have the same rank as anyone else. Now, when a new user is added, their level is calculated. After calculation a script will "rebuild" the ranks, by going through each user one by one, and calculating their new rank.

Here's an explanation of the queries:

"Id" is the member's ID in the database
"RankNum" is their level. It needs to be renamed.
"Rank" is their unique rank, #1 to #350000.

Here's my current script:

function RebuildRanks() {
    $qD = mysql_query("SELECT `Id`,`RankNum` FROM `Members` ORDER BY `Rank` DESC, `Id` ASC");
    $rowsD = mysql_num_rows($qD);

    $curRank = 0;

    for($x = 1; $x <= $rowsD; $x++) {
        $rowD = mysql_fetch_array($qD);

        $curRank++;
        if($rowD['RankNum'] != $curRank) {
            if($curRank != 0) {
                mysql_query("UPDATE `Members` SET `RankNum`='$curRank' WHERE `Id`='".$rowD['Id']."'");
            }
        }
    }

    return true;
}

With 350,000 users, this tends to run very slow. Essentially, in the database the Rank ("ORDER BY `Rank` DESC") is their level, so the query will order them. Unfortunately, the rest of the process is slow.

It takes about 97 seconds to process all 350,000 users this way. Is there any possible solution to running this more efficiently and quickly?

Their "level" is not expressed in any of those queries. Do you mind sharing about it? — Alexander, Oct 20 '12 at 21:27
@Alexander I have two things in the database table Members: Rank and RankNum. Rank is their level, basically. RankNum is their unique rank (1-350000) — Anonymous, Oct 20 '12 at 21:28
sorry Bailey, the design is weak. You should not invent a logic, where inserting or modifying one dataset leads to the necessity to change all of them. What if you don't have 350.000 users but like facebook 1 billion? rethink the design - don't try to find faster hardware or more efficient queries. — NilsB, Oct 20 '12 at 21:32
@NilsB Yeah, I know. I am basically asking for suggestions on how to do this. — Anonymous, Oct 20 '12 at 21:37

david strachan · Answer 1 · 2012-10-20T22:09:10.850

2

You calculate NewNum for new user then increment all numbers after this

 UPDATE Members SET Rank = Rank+1  WHERE Rank > NewNum

EDIT Changed RankNum to Rank. I reviewed question after your edit

edited Oct 20 '12 at 22:09

answered Oct 20 '12 at 21:32

david strachan

7,174
2
23
33

score 1 · Accepted Answer · answered Oct 20 '12 at 21:58

Your RebuildRanks() function will continue to be a performance bottleneck for you as your userbase grows; you best bet is to devise a system that avoids re-ranking every time a new user joins. Here is an example solution that might help:

Add a new table (ScoreMap) that is a sorted hash of your users by their Score (using this term instead of "Rank" to disambiguate).

CREATE TABLE ScoreMap (
  Score BIGINT NOT NULL, 
  Id BIGINT NOT NULL, 
  UNIQUE INDEX (Score), 
  UNIQUE INDEX (Id)
);

When a new user joins, compute their Score and insert into this new table. If there's a collision on Score, you can solve for that (if no two users can have the same RankNum, you must have a tie-breaking function of some sort for Score; move users around in this table as necessary).

Now query the ScoreMap table:

SELECT COUNT(*) FROM ScoreMap WHERE Score >= [the score you just calculated]

That is your new user's RankNum. Everyone with a worse Score than the new user gets their Rank increased by 1, which you can update immediately, periodically, as they log in, put a cache in front of, etc.

PS: Normalize your Rank scoring function to be a BIGINT between 0 and a very high number (e.g. a trillion). This will help you avoid collisions when inserting into the new table. You want to shoot for an even distribution over this range, since you're essentially using score as a hashing function.

score 0 · Answer 3 · answered Oct 20 '12 at 22:22

0

One way to do it is certainly using a query statement as follows (untested):

UPDATE `Members`
SET `RankNum` = (@newRank := @newRank + 1)
ORDER BY `Rank` DESC, `Id` ASC, @newRank := 0

Updating and processing the order at the same time.

answered Oct 20 '12 at 22:22

Alexander

23,432
11
63
73

Efficient ways to calculate "ranks" for over 350,000 users

3 Answers3