Efficient SQL Query/Schema for a Leader Board

Question

Hello. 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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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 ?