Pagination in SQL Server

Question

I have a very large database, roughly 100 GB. I'm executing query:

select * from <table_name>;

and I want to show only the 100th to 200th rows.

I want to understand how this happens internally. Does the database fetch all of the records from disk into memory and sends back 100th to 400th rows to the querying client? Or does there exist any mechanism, so that only those records (100th -200th) are fetched from database - by using indexing mechanism like B-trees etc.?

I found that this is related to pagination concept, but I could not exactly find how it happens internally at the database level.

Answer 1

In the query you posted:

select * from <table_name>;

There's no such thing as the 100th-200th rows, because you don't specify an ORDER BY. Order isn't guaranteed unless you include the ORDER BY for a whole lot of interesting reasons, but that's not really the point here.

So to illustrate your point, let's use a table - I'm going to use the Users table from the Stack Overflow data dump, and run this query:

SELECT * FROM dbo.Users ORDER BY DisplayName;

By default, there's no index on the DisplayName field, so SQL Server has to scan the entire table, then sort it by DisplayName. Here's the execution plan:

It's not pretty - that's a lot of work, with an estimated subtree cost of around 30k. (You can see it by hovering your mouse over the select operator over at PasteThePlan.) So what happens if we only want rows 100-200? We can use this syntax in SQL Server 2012+:

SELECT * FROM dbo.Users ORDER BY DisplayName OFFSET 100 ROWS FETCH NEXT 100 ROWS ONLY;

The execution plan on that is pretty ugly too:

SQL Server's still scanning the whole table to build the sorted list just to give you your rows 100-200, and the cost is still around 30k. Even worse, this whole list will be rebuilt every time your query runs (because after all, someone might have changed their DisplayName.)

To make it go faster, we can create an nonclustered index on DisplayName, which is a copy of our table, sorted by that specific field:

CREATE INDEX IX_DisplayName ON dbo.Users(DisplayName);

With that index, our query's execution plan now does an index seek:

The query finishes instantly and has an estimated subtree cost of just 0.66 (as opposed to 30k).

In summary, if you organize the data in a way that supports the queries you frequently run, then yes, SQL Server can take shortcuts to make your queries go faster. If, on the other hand, all you have is heaps or clustered indexes, you're screwed.

Answer 2

Just as an addition to Brent's answer when using a non covering index to avoid a sort there is a potential issue with later page numbers that can be seen from running the below

SELECT * 
FROM dbo.Users 
ORDER BY DisplayName 
OFFSET 100000 ROWS 
FETCH NEXT 100 ROWS ONLY;

The execution plan shows that the lookup was executed 100,100 times even though all but 100 rows are then filtered out by the TOP operator.

This can be mitgated by using the pattern below

WITH T
     AS (SELECT Id,
                DisplayName
         FROM   dbo.Users
         ORDER  BY DisplayName
        OFFSET 100000 ROWS 
        FETCH NEXT 100 ROWS ONLY
        )
SELECT U.*
FROM   dbo.Users U
       JOIN T
         ON U.Id = T.Id
ORDER  BY T.DisplayName 

This filters out all except the final 100 rows before doing the lookups which can have a significant impact on speed for large offset values.

Answer 3

It really depends on how you implement the pagination within your query, the nature of the data and the way that your system is configured. It's pretty safe to say that SQL Server will attempt to return your data using what it feels is the least amount of effort possible. If you have no explicit sort order, filtering, grouping or any windowing then SQL Server could possibly optimize the query plan such that it could return just the pages from the disk that contained the data required by your query - or even better, directly from the buffer pool. As soon as you start changing the query to include sorting, grouping, windowing and filtering then it starts to get complicated.

There is a very good article on SQL Performance here that goes into some detail of the various methods of pagination and how they affect the query plan. I would highly recommend reading it and then trying out some of the various methods they point out and see what query plan is chosen on your own system.