MySQL Top 10 from 50M Rows: SQL Pitfalls, Pre-aggregation & Space-Saving Algorithm

Round 1: Clarify the Time Window, Real-time Requirement, and Precision

The interview starts with a naive SQL:

SELECT item_id, COUNT(*) AS c FROM access_log GROUP BY item_id ORDER BY c DESC LIMIT 10;

The interviewer immediately asks: which time window? Full history, last hour, or last 7 days? Each demands a different approach. Full history can be precomputed once; last hour needs a sliding window; last 7 days can merge daily pre-aggregates. Next: how real-time? T+1, minute-level, or second-level? Finally: must counts be exact? Approximate answers may be acceptable for operational dashboards.

Full history, last hour, last 7 days are three completely different problems.

Round 2: What the Naive SQL Actually Does in MySQL

Running EXPLAIN on an 8C16G instance with 50M rows shows Using temporary and Using filesort. MySQL scans all 50M rows, aggregates ~2M distinct item_id values, spills to disk when memory is insufficient, sorts the 2M intermediate results, and finally discards all but the top 10. The LIMIT 10 only limits output, not computation.

LIMIT 10 saves the return, not the calculation.

Adding an index on item_id may eliminate the temporary table ( Using index for group-by), but the index scan still reads all 50M rows because COUNT(*) requires exact counts. Execution time drops from tens of seconds to ~10 seconds — same order of magnitude.

Key monitoring metrics to watch: Created_tmp_disk_tables — temporary table spilled to disk, performance drops an order of magnitude. Sort_merge_passes — sort chunks too many, repeated merges. Handler_read_rnd_next — large full table scans.

Round 3: Only One MySQL Instance, No Big Data Stack

Candidate suggests pre-aggregation with Flink. Interviewer constraints: only a single MySQL instance. Three practical approaches:

1. Precomputed Snapshot Table

Create a tiny table hot_top10_snapshot with primary key (dt, rank_no). A nightly batch job populates it; daytime queries become a 10-row primary key lookup — milliseconds.

CREATE TABLE hot_top10_snapshot (
  dt DATE NOT NULL,
  rank_no TINYINT NOT NULL,
  item_id BIGINT NOT NULL,
  cnt BIGINT NOT NULL,
  PRIMARY KEY (dt, rank_no)
);
-- Nightly batch writes, daytime API is just:
SELECT item_id, cnt FROM hot_top10_snapshot WHERE dt = CURDATE() ORDER BY rank_no;

The team implemented this; the ops dashboard that used to hang for 30 seconds now loads instantly. The boss never needed "real-time", just "opens without lag".

2. Partitioning + Segmented Parallelism

Partition by day; query today scans one partition. Further split by primary key into 16 segments and run concurrent queries, reducing wall-clock time to ~1/16. Each segment's temporary table fits in memory.

SELECT item_id, COUNT(*) AS c
FROM access_log
WHERE id >= ? AND id < ?
GROUP BY item_id
ORDER BY c DESC
LIMIT 10;

Critical pitfall: Taking top 10 from each segment and merging does not guarantee global top 10. Example: item X ranks 11th in every segment but could be globally #1. To be exact, each segment must emit full counts to an intermediate table for a final sort. This is a trade-off, not a bug.

3. Sampling

MySQL lacks TABLESAMPLE; implement via primary key modulo: WHERE id % 100 = 0 for 1% sample, then multiply counts by 100. Runs ~100x faster, but long-tail items become inaccurate. Suitable for trend spotting, not for billing.

Round 4: What If Top 10 Doesn't Need to Be Exact?

The interviewer reveals the business need: ops only cares "which ten items sell well", not whether third place is 9,213 or 9,207. This is a heavy-hitter problem. The classic solution is Space-Saving (Metwally, 2005). Maintain a fixed-size table of K entries (K=1000 >> 10). On each item:

If item exists: increment count.

If not exists and table not full: insert with count 1.

If not exists and table full: evict entry with smallest count, insert new item with count = evicted_count + 1, record evicted_count as error bound.

High-frequency items never stay at the minimum, so they are never evicted. The algorithm only overestimates, never underestimates; long-tail items are inaccurate but irrelevant for top 10.

Java core logic (capacity=1000, uses HashMap + min-heap):

public class SpaceSavingTopK {
    private final int capacity;
    private final Map<Long, Node> table = new HashMap<>();
    private final PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingLong(n -> n.count));

    static class Node {
        final long itemId;
        long count;
        long error;
        Node(long itemId) { this.itemId = itemId; }
    }

    public void offer(long itemId) {
        Node node = table.get(itemId);
        if (node != null) {
            node.count++;
            minHeap.remove(node);
            minHeap.offer(node);
            return;
        }
        if (table.size() < capacity) {
            node = new Node(itemId);
            node.count = 1;
            table.put(itemId, node);
            minHeap.offer(node);
            return;
        }
        // Table full: evict smallest, new item inherits its count
        Node victim = minHeap.poll();
        table.remove(victim.itemId);
        node = new Node(itemId);
        node.count = victim.count + 1;
        node.error = victim.count; // overestimation upper bound
        table.put(itemId, node);
        minHeap.offer(node);
    }

    public List<Node> topK(int k) {
        return table.values().stream()
            .sorted((a, b) -> Long.compare(b.count, a.count))
            .limit(k)
            .collect(Collectors.toList());
    }
}

With 1000 slots, memory is tens of KB; 50M rows processed in tens of seconds on a single machine, no disk I/O, no distributed system. Note: minHeap.remove(node) is O(K); production can use Stream-Summary (buckets + doubly linked list) for amortized O(1) updates.

Production Pitfalls After Launch

The candidate passed and later deployed a real-time pipeline with Flink + Redis. Three major issues emerged:

Data skew: A blockbuster item had orders of magnitude more traffic, overloading a single Flink subtask after keyBy(itemId). Fix: two-level aggregation — add random salt to key, scatter into 16 sub-keys, aggregate, then desalt and merge.

Redis ZSET bloat: Untrimmed ZINCRBY grows to millions of members per key. Fix: daily key rotation, TTL on whole key, periodic ZREMRANGEBYRANK key 0 -1001 to keep only top 1000.

Historical dominance: Cumulative counts keep last month's blockbuster at #1 forever. Fix: exponential decay — score = old_score * 0.95 + increment.

# Increment
ZINCRBY hot:20261009 1 10086
# Get top 10, O(log N + 10)
ZREVRANGE hot:20261009 0 9 WITHSCORES
# Keep only top 1000, prevent member explosion
ZREMRANGEBYRANK hot:20261009 0 -1001

Top 10 retrieval is negligible; bottleneck remains in Flink processing.

Closing Insight

Don't write SQL first. Tell me what time window you need.

Most SQL interview post-mortems start with optimizing the query: add indexes, tweak LIMIT, adjust sort_buffer. All are patching the wrong direction. The real question is never "how to make this SQL faster" but "who is this leaderboard for". Answer that, and a single snapshot table suffices — no Flink required.