sillyfly sillyfly - 4 months ago 11
MySQL Question

MySQL: Effectively group into equally-sized buckets by data

Suppose I have a table of Players, each player has a score, and now I want to divide all players into levels of equal size, based on their score, so if I have

n
players, level 1 will have the first
n/10
players with the highest score, level 2 will have the next
n/10
, and so on.

I have come up with a query:

UPDATE Players SET Level=? WHERE PlayerID IN (
SELECT * FROM (
SELECT PlayerID FROM Players ORDER BY Score DESC, PlayerID ASC LIMIT ?,?
) AS T1
);


Where I run this 10 times, with the first parameter running from 1-10, the second is 0,
n/10
,
2*n/10
, ... and the third is always
n/10
.

This works, but it takes quite a long time. Trying to get a better result, I have created a temporary table:

CREATE TEMPORARY TABLE TempTable (
IDX INT UNSIGNED NOT NULL AUTO_INCREMENT,
ID INT UNSIGNED NOT NULL,
PRIMARY KEY (IDX)
) ENGINE=MEMORY;
INSERT INTO TempTable (ID) SELECT PlayerID FROM Players ORDER BY Score DESC, PlayerID ASC;


Then I run ten times:

UPDATE Players SET Level=? WHERE PlayerID IN (
SELECT * FROM TempTable WHERE IDX BETWEEN ? AND ?
);


With the appropriate parameters, and finally:

DROP TABLE TempTable;


However, this runs even slower. So is there a more efficient way to do this in MySQL? I've found this answer, but it appears
NTILE
is not available in MySQL.

Note:
Players
have an index on
PlayerID
(Primary key) and on
Score
, although running without index on
Score
doesn't seem to make much of a difference. The reason I sort also by
PlayerID
is so I have well-defined (consistent) behavior in case of ties.

Answer

You could try using a ranking function. This is what I'd use:

SELECT PlayerID, 
    score,
    @levelLimit,
    @counter := @counter + 1 AS counter,
    @level := IF(@counter % @levelLimit = 0, @level:= @level + 1, @level) as level
FROM Players,

    (SELECT @counter := 0) a,

    (SELECT @levelLimit := round(count(*)/4 -- number of groups you want to end with
                                 , 0)
     FROM Players) b,

    (SELECT @level := 1) c
ORDER BY Score DESC,
         PlayerID ASC
;

To update the table:

UPDATE Players join (
    SELECT PlayerID,
       score,
       @levelLimit, @counter := @counter + 1 AS counter, 
       @level := IF(@counter % @levelLimit = 0, @level:= @level + 1, @level) AS level
FROM Players,

    (SELECT @counter := 0) a,

    (SELECT @levelLimit := round(count(*)/4 -- number of clusters
 , 0)
     FROM Players) b,

    (SELECT @level := 1) c
ORDER BY Score DESC,
         PlayerID ASC
) as a on a.PlayerID = Players.PlayerID
    SET Players.level = a.level

http://sqlfiddle.com/#!9/7f55f9/3