title: Scaling a High Score Database
body: <p>I have a simple high score service for an online game, and it has become more popular than expected. The high score is a webservice which uses a MYSQL backend with a simple table as shown below. Each high score record is stored as a row in this table. The problem is, with >140k rows, I see certain key queries slowing down so much that it will soon be too slow to service requests.</p>
  
  <p>The main table looks like this:</p>
  
  <ul>
  <li>id is a unique key for each score record</li>
  <li>game is the ID number of the game which submitted the score (currently, always equal to "1", soon will have to support more games though)</li>
  <li>name is the display name for that player's submission</li>
  <li>playerId is a unique ID for a given user</li>
  <li>score is a numeric score representation ex 42,035</li>
  <li>time is the submission time</li>
  <li>rank is a large integer which uniquely sorts the score submissions for a given game. It is
  common for people to tie at a certain score, so in that case the tie is broken by who submitted first. Therefore this field's value is equal roughly to "score * 100000000 + (MAX_TIME - time)"</li>
  </ul>
  
  <pre>
  +----------+---------------+------+-----+---------+----------------+
  | Field    | Type          | Null | Key | Default | Extra          |
  +----------+---------------+------+-----+---------+----------------+
  | id       | int(11)       | NO   | PRI | NULL    | auto_increment |
  | game     | int(11)       | YES  | MUL | NULL    |                |
  | name     | varchar(100)  | YES  |     | NULL    |                |
  | playerId | varchar(50)   | YES  |     | NULL    |                |
  | score    | int(11)       | YES  |     | NULL    |                |
  | time     | datetime      | YES  |     | NULL    |                |
  | rank     | decimal(50,0) | YES  | MUL | NULL    |                |
  +----------+---------------+------+-----+---------+----------------+
  </pre>
  
  <p>The indexes look like this:</p>
  
  <pre>
  +-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
  | Table     | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
  +-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
  | pozscores |          0 | PRIMARY  |            1 | id          | A         |      138296 |     NULL | NULL   |      | BTREE      |         |
  | pozscores |          0 | game     |            1 | game        | A         |        NULL |     NULL | NULL   | YES  | BTREE      |         |
  | pozscores |          0 | game     |            2 | rank        | A         |        NULL |     NULL | NULL   | YES  | BTREE      |         |
  | pozscores |          1 | rank     |            1 | rank        | A         |      138296 |     NULL | NULL   | YES  | BTREE      |         |
  +-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
  </pre>
  
  <p>When a user requests high scores, they typically request around 75 high scores from an arbitrary point in the "sorted by rank descending list". These requests are typically for "alltime" or just for scores in the past 7 days.</p>
  
  <p>A typical query looks like this:
  <code>
  "SELECT * FROM scoretable WHERE game=1 AND time>? ORDER BY rank DESC LIMIT 0, 75;"</code> and runs in 0.00 sec.</p>
  
  <p>However, if you request towards the end of the list
  <code>"SELECT * FROM scoretable WHERE game=1 AND time>? ORDER BY rank DESC LIMIT 10000, 75;"</code> and runs in 0.06 sec.</p>
  
  <p><code>"SELECT * FROM scoretable WHERE game=1 AND time>? ORDER BY rank DESC LIMIT 100000, 75;"</code> and runs in 0.58 sec.</p>
  
  <p>It seems like this will quickly start taking way too long as several thousand new scores are submitted each day!</p>
  
  <p>Additionally, there are two other types of queries, used to find a particular player by id in the rank ordered list.
  They look like this: </p>
  
  <p><code>"SELECT * FROM scoretable WHERE game=1 AND time>? AND playerId=? ORDER BY rank DESC LIMIT 1"</code></p>
  
  <p>followed by a </p>
  
  <p><code>"SELECT count(id) as count FROM scoretable WHERE game=1 AND time>? AND rank>[rank returned from above]"</code></p>
  
  <p>My question is: What can be done to make this a scalable system? I can see the number of rows growing to be several million very soon. I was hoping that choosing some smart indexes would help, but the improvement has only been marginal.</p>
  
  <p>Update:
   Here is an explain line:</p>
  
  <pre>
  mysql> explain SELECT * FROM scoretable WHERE game=1 AND time>0 ORDER BY rank DESC LIMIT 100000, 75;
  +----+-------------+-----------+-------+---------------+------+---------+------+--------+-------------+
  | id | select_type | table     | type  | possible_keys | key  | key_len | ref  | rows   | Extra       |
  +----+-------------+-----------+-------+---------------+------+---------+------+--------+-------------+
  |  1 | SIMPLE      | scoretable| range | game          | game | 5       | NULL | 138478 | Using where |
  +----+-------------+-----------+-------+---------------+------+---------+------+--------+-------------+
  </pre>
  
  <hr>
  
  <p><strong>Solution Found!</strong></p>
  
  <p>I have solved the problem thanks to some of the pointers from this thread. Doing a clustered index was exactly what I needed, so I converted the table to use InnoDB in mysql, which supports clustered indexes. Next, I removed the id field, and just set the primary key to be (game ASC, rank DESC). Now, all queries run super fast, no matter what offset I use. The explain shows that no additional sorting is being done, and it looks like it is easily handling all the traffic.</p>