0

I have a game where each player has a score. I would like to have a global scoreboard where players can compare their scores, see how well they are placed and browse the scoreboard.

Unfortunately I cannot find an efficient way to program this: storing the current player position in the scoreboard means I have to update a large part of the scoreboard when a player improves his score, and not storing the position means I have to recompute it each time I need it (which would also require a lot of computations).

Is there a better solution to this problem? Or is one of the above solutions "good enough" to be used practically with a lot of users and a lot of updates?

Pierre Bourdon
  • 10,521
  • 4
  • 33
  • 27
  • Hmh. I'd almost consider not using SQL for this -- an XQuery database with the XQUF extensions (for modifying the document) would let you do things like "move $FOO to the position just above $BAR" (or "move $FOO two siblings up") or "retrieve position of $BAZ in this document". – Charles Duffy Mar 06 '12 at 02:30
  • 1
    ...that said, do rankings really need to be real-time? Updating them as a batch process, ie. every minute doing a `SELECT INTO`, would make your life easier. – Charles Duffy Mar 06 '12 at 02:31

3 Answers3

0

The ORDER BY clause was made for that and doesn't look so slow.

Zsolt Botykai
  • 50,406
  • 14
  • 85
  • 110
user1251176
  • 1
0

For ease of implementation I would consider using the second solution. Depending on the size of your project you should be able to use ORDER_BY to order your solutions.

As far as whether that is "good enough" that would probably depend greatly on your needs. In the worst case, sorting your data every time you perform an update could be expensive, but if you found the ORDER_BY slow, you might want to consider a rewrite.

The best question to ask yourself is which operation will be performed more? If you were writing very rarely and reading often, maybe a sort would be a good idea. As it stands I would suggest using ORDER_BY.

As far as implementing the position, is there any reason to have that in your data model and not track it on output? It seems like it'd be pretty easy to write a counter while you're outputting rows and considerably less trouble than storing this in the table.

There appears to be a solution using stored procedures at this SO question if you'd like to do this with the request.

Community
  • 1
  • 1
angusiguess
  • 639
  • 5
  • 11
  • I'm worried that having a `O(n)` rank lookup will make things really slow as soon as I'll have >1K users. Even more if I need to query all of the data in order to compute the ranking outside of the database :/ Anyway I think I found a good solution, see my answer to the question. – Pierre Bourdon Mar 06 '12 at 04:03
0

I think I finally found a solution which does not require to recompute the whole scoreboard at each score update. Basically, in pseudo SQL code:

max_rank = SELECT MIN(rank) FROM scoreboard WHERE score <= $new_score AND score >= $old_score
UPDATE scoreboard SET rank = rank + 1 WHERE score < $new_score AND score >= $old_score
UPDATE scoreboard SET rank = $max_rank, score = $new_score WHERE player = $player

The ranking is only updated for players between the old score and the new score (which can still be a lot, but not as much as the "naive" solution of recomputing the whole scoreboard. The SQL database handles most of the work: all the rank updates are done in one query.

I'm going to go with this one unless someone finds a problem about it :)

Pierre Bourdon
  • 10,521
  • 4
  • 33
  • 27
  • Main thing that comes to mind is that you'll have to be sure to handle the case of a new player being added to the scoreboard, but if their old score was considered to be 0 that logic should handle it fine. – fluffy Mar 06 '12 at 05:59