The curious case of the Top N Sort

Watching Brent Ozar’s 2017 PASS Summit session on Youtube the other day, I learned that the Top N Sort operation in SQL Server behaves dramatically differently, depending on how many rows you want from the TOP.

Consider the following example query in the Stack Overflow database:

SELECT TOP (250) Id, DisplayName, DownVotes
FROM dbo.Users
ORDER BY DownVotes DESC;

SQL Server will scan all of the rows from the Users table (because there’s no index on the DownVotes column), then sort those rows to get only the unfortunate top 250 users with the most downvotes.

Sorting all of those rows is pretty expensive because it’s a large table:

328 MB memory grant for 250 rows

But there’s a built-in (undocumented) shortcut optimization in SQL Server. If you’re returning no more than 100 rows, the internal behaviour of the Top N Sort operator changes.

SELECT TOP (100) Id, DisplayName, DownVotes
FROM dbo.Users
ORDER BY DownVotes DESC;

Look what happened to the memory grant:

Get 100 rows for the cost of just a 1 MB memory grant!

The reason that the smaller query requires so much less memory is that it doesn’t actually store and sort the entire dataset from the Clustered Index Scan operator, as the regular Sort would.

Because the data is relatively small, I suppose, SQL Server keeps just the top 100 rows in an internal work table in memory. For each new row returned by the Scan operator, the Top N Sort operator looks if that row belongs in the top 100. If it does, that row is inserted into the working set and the currently last row (101), is bumped off the working set. And rinse, repeat.

At any point during this iterative process, the only memory we need is to store this work table.

Not just memory

This reflects not just in the memory allocation, but also in execution time. A TOP (101) query takes almost twice as long to run as an otherwise identical TOP (100).

I was going to write a workaround to get more than 100 rows, but I got so far out in the weeds that my legal counsel had to talk me out of it. I’ll save it for another time, when my lawyer is on a well-deserved vacation.

Let me hear your thoughts!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.