Efficient SQL Query/Schema for a Leader Board

Question

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

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 2

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 3

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.