I Sorted Two Million Rows to Keep Ten

A leaderboard endpoint I wrote returns the ten highest-scoring players, and for a while I never thought about it twice. Ten rows out, done. Then it started showing up in our gen0 collection graphs during traffic spikes, which made no sense to me, because the response is ten rows. The allocation counter disagreed, and that counter has never once flattered me.

Here's the line that did it, more or less:

var top = players
    .OrderByDescending(p => p.Score)
    .Take(10)
    .ToList();

It reads exactly like what I want. Sort by score, take ten. The problem is the order of operations under the hood. OrderByDescending doesn't know I only want ten until Take shows up later in the chain, so it buffers every player into an internal array first, then sorts enough of it to hand ten back. To return ten rows, it holds all of them at once. On a small table nobody notices. On two million rows it's a very different graph.

Measuring it instead of guessing

I didn't want to argue from a hunch, so I wrote the smallest honest version I could. Two million rows of (id, score), built once up front so the data itself doesn't land on the scorecard. Then the top ten computed two ways, each wrapped in a best-of-five loop with GC.GetAllocatedBytesForCurrentThread() and a checksum so a wrong answer couldn't sneak through.

The LINQ version printed this:

OrderByDescending().Take(K)      56,000,560 bytes    ~43 ms

Fifty-six megabytes to keep ten rows. The number came back byte-for-byte identical on every run, which is what you'd expect from something whose cost is "buffer N, sort N."

Keeping only the ten you care about

The fix is to never hold more than ten rows in the first place. A min-heap capped at K does exactly that: the smallest of the current top ten sits at the root, so any new row only has to beat that root to earn a spot. PriorityQueue<TElement, TPriority> has shipped since .NET 6 and it has the one method that makes this clean, EnqueueDequeue, which pushes a new item and pops the smallest in a single rebalance.

var heap = new PriorityQueue<Row, double>(K);
foreach (var r in rows)
{
    if (heap.Count < K)
        heap.Enqueue(r, r.Score);
    else if (r.Score > heap.Peek().Score)
        heap.EnqueueDequeue(r, r.Score);
}

Most rows never make it past the Peek() check. One comparison against the current tenth-best, and they're gone. The heap never grows beyond ten entries, so there's nothing to buffer and nothing for gen0 to clean up afterward. Here's the same two approaches side by side, best-of-five in a cloud container with workstation GC. This isn't a lab, so I care about the ratio, not the absolute milliseconds:

OrderByDescending().Take(K)              56,000,560 bytes    ~43 ms
Bounded PriorityQueue (min-heap of K)           568 bytes     ~6 ms

From fifty-six megabytes to five hundred and sixty-eight bytes, and quicker on the clock on top of it. I'd half expected the time to come out close, since LINQ does partial-sort the top of the buffer rather than sorting all two million. But buffering two million structs and running them through a comparer still costs you, and the heap just... doesn't do that.

When I'd leave the LINQ line alone

Most of the time I'd leave it alone, and I want to be clear about that. If your table has a few thousand rows, fifty-six megabytes becomes a few kilobytes and none of this matters. The LINQ version is shorter, it's obvious to the next person, and obvious code is worth real money. I only reach for the heap when K is tiny next to N and the thing runs hot. The whole win comes from that gap: ten out of two million is enormous leverage, ten out of thirty is nothing. And once K creeps close to N, you're basically sorting anyway, so just sort.

One sharp edge worth knowing: the heap gives you the top ten, but not in sorted order. The root is the smallest of the ten, not the largest. If you need them ranked, drain the heap and reverse, which is cheap because it's only ten items. I forgot that the first time and handed back a leaderboard sorted the wrong way, which is a fun bug to explain.

The full runnable sample

Dropping this in a file and running dotnet run -c Release reproduces the numbers. Tweak N and K at the top to find where the heap stops being worth it.

using System.Diagnostics;

const int N = 2_000_000;
const int K = 10;

var rng = new Random(20261114);
var rows = new Row[N];
for (int i = 0; i < N; i++)
    rows[i] = new Row(i, rng.NextDouble() * 1000.0);

Console.WriteLine($"N = {N:N0} rows, K = {K}\n");

Measure("OrderByDescending().Take(K)", () =>
{
    var top = rows.OrderByDescending(r => r.Score).Take(K).ToList();
    return Checksum(top);
});

Measure("Bounded PriorityQueue (min-heap of K)", () =>
{
    var heap = new PriorityQueue<Row, double>(K);
    foreach (var r in rows)
    {
        if (heap.Count < K)
            heap.Enqueue(r, r.Score);
        else if (r.Score > heap.Peek().Score)
            heap.EnqueueDequeue(r, r.Score);
    }

    var top = new List<Row>(K);
    while (heap.Count > 0) top.Add(heap.Dequeue());
    top.Reverse();
    return Checksum(top);
});

static double Checksum(List<Row> top)
{
    double sum = 0;
    foreach (var r in top) sum += r.Score;
    return sum;
}

static void Measure(string label, Func<double> run)
{
    run();
    GC.Collect();
    GC.WaitForPendingFinalizers();
    GC.Collect();

    long bestBytes = long.MaxValue;
    double bestMs = double.MaxValue;
    double checksum = 0;

    for (int i = 0; i < 5; i++)
    {
        long before = GC.GetAllocatedBytesForCurrentThread();
        var sw = Stopwatch.StartNew();
        checksum = run();
        sw.Stop();
        long allocated = GC.GetAllocatedBytesForCurrentThread() - before;

        if (allocated < bestBytes) bestBytes = allocated;
        if (sw.Elapsed.TotalMilliseconds < bestMs) bestMs = sw.Elapsed.TotalMilliseconds;
    }

    Console.WriteLine($"{label,-42} {bestBytes,14:N0} bytes   {bestMs,7:F1} ms   (checksum {checksum:F2})");
}

readonly record struct Row(int Id, double Score);

Have you got a top-N query sitting in a hot path somewhere? Check what it allocates before you assume it's fine. Mine looked harmless for months.

— still benchmarking the ten rows nobody asked me to benchmark