17

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.

37

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:

Clustered index scan with a sort

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:

Clustered index scan with a sort and a top

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:

Index seek and key lookup

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.

  • "By default, there's no index on the DisplayName field, so SQL Server has to scan the entire table, then sort it by DisplayName. " Pardon me if this is a very basic question - in the case I quoted from your answer, When you said "Scan the entire table" , does that mean all the data be brought into memory and sorted (which does not look like the right way) ? – AV94 Nov 4 '16 at 11:54
  • From your answer, I understand that if the field is indexed, then making queries like - get 100th to 200th row is very efficient as SQL looks up to index(B-tree etc) and directly goes to that point(100th row). Could you please tell me if this is right understanding? – AV94 Nov 4 '16 at 11:57
  • @AnilVedala about your first question - yes, the data has to be sorted. How else could a database accomplish that with an unsorted list? – Brent Ozar Nov 4 '16 at 12:16
  • 1
    @AnilVedala about your second question - that's where the last execution plan I gave you comes in. (If you're asking about how to read an execution plan, pick up the book Execution Plans by Grant Fritchey.) – Brent Ozar Nov 4 '16 at 12:17
15

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.

enter image description here

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.

enter image description here

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.