CODEWITHSUNDEEP
sql
Frank Krueger
Frank Krueger

Reputation: 71053

Efficient SQL Query/Schema for a Leader Board

I have written a stupid little game and want to have some kind of leader board website.

Usually leaderboards are limited to 10 or 20 top players, but I thought it would be nice if I could record, for every player, their top score. Then, I could always display their world-wide rank.

A simple schema such as:

create table leaderboard (
    userid varchar(128) not null,
    score real not null,
    when datetime not null
);
create index on leaderboard(userid);

Would store the minimal amount of information that I need - 1 entry per user with their best score.

My question revolves around how to efficiently determine someone's position on the leader board. The general idea is that I would want their position in the list returned by:

select userid from leaderboard order by score desc

But running this query and then linearly searching the list seems a bit ridiculous to me from a DB performance standpoint. Even so, I am having a hard time imagining a query/schema that would make it a quick operation.

Any ideas?

(I would prefer to keep the DB schema and query generic (not tied to a vendor). But, if one vendor makes this easy, I am happy to use either MS SQL or MySQL.

Upvotes: 8

Views: 5463

Answers (7)

Marcus Vinicius de LIma
Marcus Vinicius de LIma

Reputation: 1

I was thinking about the select "select count(*)+1 as rank from leaderboard
where score > (select score from leaderboard where userid = ?)"

Think of the the following situation: Player 1, Score 100 Player 2, Score 100 Player 3, Score 50

Using that SQL the rank of player 3 would be 3, where the correct answer should be 2, because Player 1 and Player 2 are tied in the first position. The count() aggregate function in that case consider 2 records with Score column > 50.

To handle this case I think the right option is to make a group by, so repeatable values of score will be handled as a single ranking position:

select score, count(*)+1 as rank from leaderboard  
group by score having (score) > (select score from leaderboard where userid = ?)

Upvotes: 0

Nikhil S
Nikhil S

Reputation: 1209

In Sql server 2005, Rank() pretty much does the job for you. But if u have millions of records then ranking them real-time whenever the underlying stats change will be performance hog.

I tried to create a Indexed view on top of the select query... ( the voted answer in this thread ) but Sql 2005 would not let me create it cause u cannot use subqueries, self-reference in a indexed view.

So our workaround is to update the rank table nightly using Row() function. To avoid blocking while doing this update, we keep 2 copies of the ranking table one which is being updated and one which is being used in the application. We have a RankingView which points to the active ranking table at any given time.

I would like to know if there is a solution for real-time ranking update for really large tables ?

Upvotes: 1

Russ Cam
Russ Cam

Reputation: 125538

In SQL Server 2005 onwards, you can use the RANK() function to return the rank for each user, based on their score

SELECT 
    userid,
    RANK() OVER 
    (ORDER BY score) AS rank
FROM leaderboard

If you had more than one type of 'game type', then you could include this in the Leaderboard table and use the PARTITION BY clause within the RANK function to determine ranking for each game type.

Upvotes: 2

Edwin
Edwin

Reputation: 2671

Looks like you want to query this:

select userid , max(score)
from leaderboard 
group by userid
order by max(score) desc

This returns the leaderboard with 1 entry for every user.

EDIT BELOW: I see in the comment that you want to see the rank, not the score. for this I don't know the ANSI SQL answer, but database specific:

In MySQL:

SELECT @rownum:=@rownum+1 rank
, t.userid 
FROM (SELECT @rownum:=0) r, 
 (select userid , score
from leaderboard 
order by score desc
) t;

In Oracle you can use the RANK statement.

Upvotes: 1

Henning
Henning

Reputation: 16349

How about: 

select count(*)+1 as rank from leaderboard  
where score > (select score from leaderboard where userid = ?)

You'll also want an index on the score column.

Doing count()+1 with score > (...) will give you accurate ranks even when multiple players have the same score; doing count() with score >= (...) will not.

Upvotes: 12

MaxVT
MaxVT

Reputation: 13244

If this does not have to be real-time (for example if updating once a day is acceptable), add an additional "position" field and update it periodically using a query ordered by score.

Upvotes: 1

dkretz
dkretz

Reputation: 37655

The obvious option would be to create an index on "score", which is perfectly reasonable. (It sounds like you want to preserve two values - cumulative score and high-water score - or else I misunderstand?)

Unless you expect tens of thousands of users, even table scans shouldn't be a big problem on a table with that many records.

Upvotes: 1

Related Questions