Design a Leaderboard: Sorted Set vs Database ORDER BY

Design a Leaderboard: Sorted Set vs Database ORDER BY in one line: an indexed table answers ORDER BY score DESC LIMIT 100 well and is enough for small boards with few updates, but every score change is an indexed write and every rank is a COUNT(*) over everyone above; an in-memory sorted set makes both logarithmic, so large live boards keep the sorted set for reads and the database as the durable record. The choice turns on update rate and rank depth, not on the top hundred.

The two side by side:

Operation	Table with an index on score	In-memory sorted set
Top 100	index range read, 100 entries	range read, 100 entries
Rank of a player at position r	COUNT(*) reads about r entries	logarithmic walk with counts
Score update	a durable row and index write	remove and insert in memory
After a crash	the data is the record	rebuilt from a durable copy

The problem it solves

A leaderboard has three reads and one write: the top hundred, a player's rank, the players around them, and a score change. With a thousand players and a change a minute, any database is fine. The lesson's illustrative ten million players and thousands of updates a second is where it hurts. The skill is saying where the line is, instead of reaching for a sorted set by reflex.

The sibling article, sorted sets, top-K and rank, covers the sorted set's internals and approximate rank. This one is the comparison.

The intuition

The database version is one table, players(id, score), with an index on score. The top hundred reads the first hundred index entries. A player's rank is 1 + COUNT(*) WHERE score > their score, and that is the catch: most relational B-tree indexes store no subtree counts, so counting reads every entry above the player. Cheap near the top; nine million entries for the player in nine-millionth place.

Writes are the other cost. Each score change is a transaction: a row update, an index delete and insert, a log flush. Thousands a second on one hot index falls over long before reads do.

The sorted set version keeps (score, player) pairs in a skip list or balanced tree in memory, the structure behind in-memory sorted sets such as Redis's. An update is a logarithmic remove and insert, the top hundred a range read, and rank a logarithmic walk when nodes store their span counts. Memory is the limit, and a crash empties it.

When the database is enough:

• Up to a few hundred thousand players, or more if nobody asks for deep ranks.
• Score changes in the tens a second, not thousands.
• Ranks asked only near the top, where the count is small.
• A top hundred allowed to be seconds stale, so it can be cached.

The hybrid keeps both. The sorted set serves every read and takes every update. The database stays the durable record, written behind in batches, and the set is rebuilt from it after a restart.

Watch it run

The animation begins with the constraint: ten million players, thousands of changes a second, no sorting at read time. A new score arrives and one entry slides up a place after a logarithmic walk. Order is kept on the way in, so the top hundred is a range read off the front, and the durable copy is written behind. Then a player deep in the list asks for their rank, and counting everyone above them turns out to be the expensive part.

The code

Derived from the lesson's sorted-set model, as a toy model: a dict plus a list kept sorted with bisect, standing in for a skip list (its insert shifts elements, O(n) here). Against it, an in-memory SQLite table with a descending index on score. First, SQLite's plans for the two reads:

import random
import sqlite3
import time
from bisect import bisect_left, insort

class SortedSet:
    """Toy sorted set: player -> score, plus (-score, player) pairs kept in order."""
    def __init__(self):
        self.score, self.ranked = {}, []

    def update(self, player, new):
        old = self.score.get(player)
        if old is not None:
            self.ranked.pop(bisect_left(self.ranked, (-old, player)))   # remove the old pair
        self.score[player] = new
        insort(self.ranked, (-new, player))                             # one ordered insert

    def top(self, k):
        return [(p, -s) for s, p in self.ranked[:k]]                    # a range read

    def rank(self, player):
        return bisect_left(self.ranked, (-self.score[player], "")) + 1  # 1 + players above

class Table:
    """The database answer: one row per player, an index on score, ORDER BY at read time."""
    def __init__(self):
        self.db = sqlite3.connect(":memory:")
        self.db.execute("CREATE TABLE players (id TEXT PRIMARY KEY, score INTEGER NOT NULL)")
        self.db.execute("CREATE INDEX idx_score ON players (score DESC, id)")
        self.rows_counted = 0

    def update(self, player, new):
        self.db.execute("INSERT INTO players VALUES (?, ?) ON CONFLICT(id) "
                        "DO UPDATE SET score = excluded.score", (player, new))

    def top(self, k):
        return self.db.execute("SELECT id, score FROM players ORDER BY score DESC, id "
                               "LIMIT ?", (k,)).fetchall()

    def rank(self, player):
        above = self.db.execute("SELECT COUNT(*) FROM players WHERE score > "
                                "(SELECT score FROM players WHERE id = ?)", (player,)).fetchone()[0]
        self.rows_counted += above                     # every row above is an index entry read
        return above + 1

t = Table()
for sql in ["SELECT id, score FROM players ORDER BY score DESC, id LIMIT 100",
            "SELECT COUNT(*) FROM players WHERE score > 500"]:
    print(t.db.execute("EXPLAIN QUERY PLAN " + sql).fetchall()[0][-1])
# SCAN players USING COVERING INDEX idx_score
# SEARCH players USING COVERING INDEX idx_score (score>?)

Both reads use the index. The rank is a range read too, but its range is everyone above the player. Now one seeded workload on both: 20,000 players, 20,000 updates, 200 top-100 reads and 500 ranks, shuffled. Timings are on one machine, roughly; this SQLite never touches a disk, so its writes are the cheapest a database can offer:

def workload(board, n_players, updates, top_reads, rank_reads, seed=15):
    """The same seeded mix for both: load players, then updates, top-100s and ranks."""
    rng = random.Random(seed)
    players = ["p%05d" % i for i in range(n_players)]
    for p in players:
        board.update(p, rng.randint(0, 100_000))
    ops = ["update"] * updates + ["top"] * top_reads + ["rank"] * rank_reads
    rng.shuffle(ops)
    answers, spent = [], dict.fromkeys(["update", "top", "rank"], 0.0)
    for op in ops:
        started = time.perf_counter()
        if op == "update":
            board.update(rng.choice(players), rng.randint(0, 100_000))
        elif op == "top":
            answers.append(tuple(board.top(100)))
        else:
            answers.append(board.rank(rng.choice(players)))
        spent[op] += time.perf_counter() - started
    return answers, spent

N, M, K, R = 20_000, 20_000, 200, 500
sset, table = SortedSet(), Table()
a1, s1 = workload(sset, N, M, K, R)
a2, s2 = workload(table, N, M, K, R)
print(a1 == a2)                                       # True: same top-100s, same ranks
for op in s1:
    print("%-6s sorted set %6.3f s   table %6.3f s" % (op, s1[op], s2[op]))
# update sorted set  0.106 s   table  0.074 s
# top    sorted set  0.003 s   table  0.007 s
# rank   sorted set  0.001 s   table  0.125 s
print(table.rows_counted // R, len(sset.ranked).bit_length())   # rows counted vs steps, per rank
# 10224 15

Read it honestly. Updates are close, because this table never flushes a log and the toy list shifts elements; a durable database pays a flush per committed update. Top-100 reads are cheap on both. Ranks differ in shape: about 10,000 index entries counted per lookup against 15 steps. Then rank cost as the board grows, and the hybrid: reads from the sorted set, the table written behind in batches and used to rebuild after a restart:

for n in (10_000, 40_000):                            # rank cost as the board grows
    s, tb = SortedSet(), Table()
    workload(s, n, 0, 0, 300)
    workload(tb, n, 0, 0, 300)
    print(n, tb.rows_counted // 300, len(s.ranked).bit_length())
# 10000 5034 14
# 40000 20061 16

class Hybrid:
    """Sorted set serves every read; the table is the durable record, written behind."""
    def __init__(self, flush_every=1_000):
        self.live, self.store, self.dirty = SortedSet(), Table(), {}
        self.flush_every, self.commits = flush_every, 0

    def update(self, player, new):
        self.live.update(player, new)                 # reads see it immediately
        self.dirty[player] = new                      # last score per player wins
        if len(self.dirty) >= self.flush_every:
            self.flush()

    def flush(self):
        with self.store.db:                           # one transaction per batch
            for player, score in self.dirty.items():
                self.store.update(player, score)
        self.commits, self.dirty = self.commits + 1, {}

    def top(self, k):
        return self.live.top(k)

    def rank(self, player):
        return self.live.rank(player)

h = Hybrid()
answers, _ = workload(h, N, M, K, R)
h.flush()
print(answers == a1, h.commits)                       # True 40
restarted = SortedSet()                               # the cache died: rebuild from the record
for player, score in h.store.db.execute("SELECT id, score FROM players"):
    restarted.update(player, score)
print(restarted.top(100) == h.top(100), restarted.rank("p00042") == h.rank("p00042"))
# True True

Quadrupling the board quadruples the rows counted per rank while the walk grows by two steps. The hybrid gave identical answers with 40 commits for 40,000 score writes, and the rebuilt set matches.

The complexity

• Top K: O(log n + K) for both, if the table has an index on score.
• Exact rank: O(rank) entries counted in a plain B-tree index; O(log n) in a sorted set with per-node counts.
• Update: O(log n) for both in theory; the database also pays a transaction and a log flush per committed change.
• Hybrid durability lag: at most one unflushed batch of score changes is lost if the process dies before a flush.

Where it goes wrong

• No index on score. Every top-100 becomes a full sort, the classic slow query.
• Serving deep ranks from COUNT(*). Fine near the top, ruinous at position nine million. Cache it, bucket it, or move it to the sorted set.
• One durable write per score change on a hot board. Batch or write behind.
• Treating the sorted set as the record. Without a durable copy, a restart empties the board.
• Ties decided differently in each store. The set and the query must break ties the same way, by id here, or the two will disagree.

When it shows up in interviews

As "design a gaming leaderboard" or "design a real-time top-K". Strong answers start with the database, say when it breaks with numbers, then add the sorted set. Follow-ups: deep rank, sharding, resets per season, ties. Related structures are in B-tree vs hash index and hash map vs tree map; the lesson is design a leaderboard.

How to say it in an interview

"At small scale I'd use one table with an index on score: the top hundred is an index range read, and rank is one plus a count of higher scores. That breaks on two things: every score change is a durable indexed write, and a deep rank counts everyone above the player, because a B-tree index keeps no subtree counts. At millions of players and thousands of updates a second I'd keep a sorted set in memory for updates, top-K and rank, all logarithmic, and write scores behind to the database in batches, which stays the durable record and rebuilds the set after a restart."

Frequently asked questions

Can I build a leaderboard with SQL ORDER BY?

Yes, for small boards. An index on score makes ORDER BY score DESC LIMIT 100 a range read. It strains when score changes reach thousands a second, because each is a durable indexed write, and when players far down ask for their exact rank, because the count reads every entry above them.

Is a sorted set faster than a database for a leaderboard?

For updates and ranks at scale, yes: both are logarithmic in memory, while a database pays a transaction per update and counts every entry above a player for a rank. For a top-100 read on an indexed table the difference is small. The sorted set still needs a durable copy behind it.

How do you get a player's rank in SQL?

Count the players with a strictly higher score and add one: SELECT COUNT(*) + 1 FROM players WHERE score > ?. With an index on score it reads only the entries above the player, which is cheap near the top and slow far down. Ties share a rank unless you add a tie-breaker.