T-SQL Querying (2015)

---

The second method to guarantee a deterministic result is to make the ordering specification unique by adding a tiebreaker. For example, you could add orderid, DESC as the tiebreaker in our example. This means that, in the case of ties in the order date values, a row with a higher order ID value is preferred to a row with a lower one. Here’s our query with the tiebreaker applied:

SELECT TOP (3) orderid, orderdate, custid, empid
FROM Sales.Orders
ORDER BY orderdate DESC, orderid DESC;

This query generates the following output:

orderid orderdate custid empid
----------- ---------- ----------- -----------
11077 2015-05-06 65 1
11076 2015-05-06 9 4
11075 2015-05-06 68 8

Use of unique ordering makes both the row selection and presentation ordering deterministic. The result set as well as the presentation ordering of the rows are guaranteed to be repeatable so long as the underlying data doesn’t change.

If you have a case where you need to filter a certain number of rows but truly don’t care about order, it could be a good idea to specify ORDER BY (SELECT NULL), like so:

SELECT TOP (3) orderid, orderdate, custid, empid
FROM Sales.Orders
ORDER BY (SELECT NULL);

This way, you let everyone know your choice of arbitrary order is intentional, which helps to avoid confusion and doubt.

As a reminder of what I explained in Chapter 1, “Logical query processing,” about the TOP and OFFSET-FETCH filters, presentation order is guaranteed only if the outer query has an ORDER BY clause. For example, in the following query presentation, ordering is not guaranteed:

SELECT orderid, orderdate, custid, empid
FROM ( SELECT TOP (3) orderid, orderdate, custid, empid
FROM Sales.Orders
ORDER BY orderdate DESC, orderid DESC ) AS D;

To provide a presentation-ordering guarantee, you must specify an ORDER BY clause in the outer query, like so:

SELECT orderid, orderdate, custid, empid
FROM ( SELECT TOP (3) orderid, orderdate, custid, empid
FROM Sales.Orders
ORDER BY orderdate DESC, orderid DESC ) AS D
ORDER BY orderdate DESC, orderid DESC;

The OFFSET-FETCH filter

The OFFSET-FETCH filter is a standard feature designed similar to TOP but with an extra element. You can specify how many rows you want to skip before specifying how many rows you want to filter.

As you could have guessed, this feature can be handy in implementing paging solutions—that is, returning a result to the user one chunk at a time upon request when the full result set is too long to fit in one screen or web page.

The OFFSET-FETCH filter requires an ORDER BY clause to exist, and it is specified right after it. You start by indicating how many rows to skip in an OFFSET clause, followed by how many rows to filter in a FETCH clause. For example, based on the indicated order, the following query skips the first 50 rows and filters the next 25 rows:

SELECT orderid, orderdate, custid, empid
FROM Sales.Orders
ORDER BY orderdate DESC, orderid DESC
OFFSET 50 ROWS FETCH NEXT 25 ROWS ONLY;

In other words, the query filters rows 51 through 75. In paging terms, assuming a page size of 25 rows, this query returns the third page.

To allow natural declarative language, you can use the keyword FIRST instead of NEXT if you like, though the meaning is the same. Using FIRST could be more intuitive if you’re not skipping any rows. Even if you don’t want to skip any rows, T-SQL still makes it mandatory to specify the OFFSET clause (with 0 ROWS) to avoid parsing ambiguity. Similarly, instead of using the plural form of the keyword ROWS, you can use the singular form ROW in both the OFFSET and the FETCH clauses. This is more natural if you need to skip or filter only one row.

If you’re curious what the purpose of the keyword ONLY is, it means not to include ties. Standard SQL defines the alternative WITH TIES; however, T-SQL doesn’t support it yet. Similarly, standard SQL defines the PERCENT option, but T-SQL doesn’t support it yet either. These two missing options are available with the TOP filter.

As mentioned, the OFFSET-FETCH filter requires an ORDER BY clause. If you want to use arbitrary order, like TOP without an ORDER BY clause, you can use the trick with ORDER BY (SELECT NULL), like so:

SELECT orderid, orderdate, custid, empid
FROM Sales.Orders
ORDER BY (SELECT NULL)
OFFSET 0 ROWS FETCH NEXT 3 ROWS ONLY;

The FETCH clause is optional. If you want to skip a certain number of rows but not limit how many rows to return, simply don’t indicate a FETCH clause. For example, the following query skips 50 rows but doesn’t limit the number of returned rows:

SELECT orderid, orderdate, custid, empid
FROM Sales.Orders
ORDER BY orderdate DESC, orderid DESC
OFFSET 50 ROWS;

Concerning presentation ordering, the behavior is the same as with the TOP filter; namely, with OFFSET-FETCH also, presentation ordering is guaranteed only if the outermost query has an ORDER BY clause.

Optimization of filters demonstrated through paging

So far, I described the logical design aspects of the TOP and OFFSET-FETCH filters. In this section, I’m going to cover optimization aspects. I’ll do so by looking at different paging solutions. I’ll describe two paging solutions using the TOP filter, a solution using the OFFSET-FETCH filter, and a solution using the ROW_NUMBER function.

In all cases, regardless of which filtering option you use for your paging solution, an index on the ordering elements is crucial for good performance. Often you will get good performance even when the index is not a covering one. Curiously, sometimes you will get better performance when the index isn’t covering. I’ll provide the details in the specific implementations.

I’ll use the Orders table from the PerformanceV3 database in my examples. Suppose you need to implement a paging solution returning one page of orders at a time, based on orderid as the sort key. The table has a nonclustered index called PK_Orders defined with orderid as the key. This index is not a covering one with respect to the paging queries I will demonstrate.

Optimization of TOP

There are a couple of strategies you can use to implement paging solutions with TOP. One is an anchor-based strategy, and the other is TOP over TOP (nested TOP queries).

The anchor-based strategy allows the user to visit adjacent pages progressively. You define a stored procedure that when given the sort key of the last row from the previous page, returns the next page. Here’s an implementation of such a procedure:

USE PerformanceV3;
IF OBJECT_ID(N'dbo.GetPage', N'P') IS NOT NULL DROP PROC dbo.GetPage;
GO
CREATE PROC dbo.GetPage
@orderid AS INT = 0, -- anchor sort key
@pagesize AS BIGINT = 25
AS

SELECT TOP (@pagesize) orderid, orderdate, custid, empid
FROM dbo.Orders
WHERE orderid > @orderid
ORDER BY orderid;
GO

Here I’m assuming that only positive order IDs are supported. Of course, you can implement such an integrity rule with a CHECK constraint. The query uses the WHERE clause to filter only orders with order IDs that are greater than the input anchor sort key. From the remaining rows, using TOP, the query filters the first @pagesize rows based on orderid ordering.

Use the following code to request the first page of orders:

EXEC dbo.GetPage @pagesize = 25;

I got the following result (but yours may vary because of the randomization aspects used in the creation of the sample data):

orderid orderdate custid empid
----------- ---------- ----------- -----------
1 2011-01-01 C0000005758 205
2 2011-01-01 C0000015925 251
...
24 2011-01-01 C0000003541 316
25 2011-01-01 C0000005636 256

In this example, the last sort key in the first page is 25. Therefore, to request the second page of orders, you pass 25 as the input anchor sort key, like so:

EXEC dbo.GetPage @orderid = 25, @pagesize = 25;

Of course, in practice the last sort key in the first page could be different than 25, but in my sample data the keys start with 1 and are sequential. I got the following result when running this code:

orderid orderdate custid empid
----------- ---------- ----------- -----------
26 2011-01-01 C0000017397 332
27 2011-01-01 C0000012629 27
28 2011-01-01 C0000016429 53
...
49 2011-01-01 C0000015415 95
50 2010-12-06 C0000008667 117

To ask for the third page of orders, you pass 50 as the input sort key in the next page request:

EXEC dbo.GetPage @orderid = 50, @pagesize = 25;

I got the following output for the execution of this code:

orderid orderdate custid empid
----------- ---------- ----------- -----------
51 2011-01-01 C0000000797 438
52 2011-01-01 C0000015945 47
53 2011-01-01 C0000013558 364
...
74 2011-01-01 C0000019720 249
75 2011-01-01 C0000000807 160

The execution plan for the query is shown in Figure 5-1. I’ll assume the inputs represent the last procedure call with the request for the third page.

FIGURE 5-1 Plan for TOP with a single anchor sort key.

I’ll describe the execution of this plan based on data flow order (right to left). But keep in mind that the API call order is actually left to right, starting with the root node (SELECT). I’ll explain why that’s important to remember shortly.

The Index Seek operator performs a seek in the index PK_Orders to the first leaf row that satisfies the Start property of the Seek Predicates property: orderid > @orderid. In the third execution of the procedure, @orderid is 50. Then the Index Seek operator continues with a range scan in the index leaf based on the seek predicate. Absent a Prefix property of the Seek Predicates property, the range scan normally continues until the tail of the index leaf. However, as mentioned, the internal API call order is done from left to right. The Top operator has a property called Top Expression, which is set in the plan to @pagesize (25, in our case). This property tells the Top operator how many rows to request from the Nested Loops operator to its right. In turn, the Nested Loops operator requests the specified number of rows (25, in our case) from the Index Seek operator to its right. For each row returned from the Index Seek Operator, Nested Loops executes the Key Lookup operator to collect the remaining elements from the respective data row. This means that the range scan doesn’t proceed beyond the 25th row, and this also means that the Key Lookup operator is executed 25 times.

Not only is the range scan in the Index Seek operator cut short because of TOP’s row goal (Top Expression property), the query optimizer needs to adjust the costs of the affected operators based on that row goal. This aspect of optimization is described in detail in an excellent article by Paul White: “Inside the Optimizer: Row Goals In Depth.” The article can be found here: http://sqlblog.com/blogs/paul_white/archive/2010/08/18/inside-the-optimiser-row-goals-in-depth.aspx.

The I/O costs involved in the execution of the query plan are made of the following:

Seek to the leaf of index: 3 reads (the index has three levels)

Range scan of 25 rows: 0–1 reads (hundreds of rows fit in a page)

Nested Loops prefetch used to optimize lookups: 9 reads (measured by disabling prefetch with trace flag 8744)

25 key lookups: 75 reads

In total, 87 logical reads were reported for the processing of this query. That’s not too bad. Could things be better or worse? Yes on both counts. You could get better performance by creating a covering index. This way, you eliminate the costs of the prefetch and the lookups, resulting in only 3–4 logical reads in total. You could get much worse performance if you don’t have any good index with the sort column as the leading key—not even a noncovering index. This results in a plan that performs a full scan of the data, plus a sort. That’s a very expensive plan, especially considering that you pay for it for every page request by the user.

With a single sort key, the WHERE predicate identifying the start of the qualifying range is straightforward: orderid > @orderid. With multiple sort keys, it gets a bit trickier. For example, suppose that the sort vector is (orderdate, orderid), and you get the anchor sort keys @orderdateand @orderid as inputs to the GetPage procedure. Standard SQL has an elegant solution for this in the form of a feature called row constructor (aka vector expression). Had this feature been implemented in T-SQL, you could have phrased the WHERE predicate as follows: (orderdate, orderid) > (@orderdate, @orderid). This also allows good optimization by using a supporting index on the sort keys similar to the optimization of a single sort key. Sadly, T-SQL doesn’t support such a construct yet.

You have two options in terms of how to phrase the predicate. One of them (call it the first predicate form) is the following: orderdate >= @orderdate AND (orderdate > @orderdate OR orderid > @orderid). Another one (call it the second predicate form) looks like this: (orderdate = @orderdate AND orderid > @orderid) OR orderdate > @orderdate. Both are logically equivalent, but they do get handled differently by the query optimizer. In our case, there’s a covering index called idx_od_oid_i_cid_eid defined on the Orders table with the key list (orderdate, orderid) and the include list (custid, empid).

Here’s the implementation of the stored procedure with the first predicate form:

IF OBJECT_ID(N'dbo.GetPage', N'P') IS NOT NULL DROP PROC dbo.GetPage;
GO
CREATE PROC dbo.GetPage
@orderdate AS DATE = '00010101', -- anchor sort key 1 (orderdate)
@orderid AS INT = 0, -- anchor sort key 2 (orderid)
@pagesize AS BIGINT = 25
AS

SELECT TOP (@pagesize) orderid, orderdate, custid, empid
FROM dbo.Orders
WHERE orderdate >= @orderdate
AND (orderdate > @orderdate OR orderid > @orderid)
ORDER BY orderdate, orderid;
GO

Run the following code to get the first page:

EXEC dbo.GetPage @pagesize = 25;

I got the following output from this execution:

orderid orderdate custid empid
----------- ---------- ----------- -----------
310 2010-12-03 C0000014672 218
330 2010-12-03 C0000009594 10
90 2010-12-04 C0000012937 231
...
300 2010-12-07 C0000019961 282
410 2010-12-07 C0000001585 342

Run the following code to get the second page:

EXEC dbo.GetPage @orderdate = '20101207', @orderid = 410, @pagesize = 25;

I got the following output from this execution:

orderid orderdate custid empid
----------- ---------- ----------- -----------
1190 2010-12-07 C0000004678 465
1270 2010-12-07 C0000015067 376
1760 2010-12-07 C0000009532 104
...
2470 2010-12-09 C0000008664 205
2830 2010-12-09 C0000010497 221

Run the following code to get the third page:

EXEC dbo.GetPage @orderdate = '20101209', @orderid = 2830, @pagesize = 25;

I got the following output from this execution:

orderid orderdate custid empid
----------- ---------- ----------- -----------
3120 2010-12-09 C0000015659 381
3340 2010-12-09 C0000008708 272
3620 2010-12-09 C0000009367 312
...
2730 2010-12-10 C0000015630 317
3490 2010-12-10 C0000002887 306

As for optimization, Figure 5-2 shows the plan I got for the implementation using the first predicate form.

FIGURE 5-2 Plan for TOP with multiple anchor sort keys, first predicate form.

Observe that the Start property of the Seek Predicates property is based only on the predicate orderdate >= @orderdate. The residual predicate is orderdate > @orderdate OR orderid > @orderid. Such optimization could result in some unnecessary work scanning the pages holding the first part of the range with the first qualifying order date with the nonqualifying order IDs—in other words, the rows where orderdate = @orderdate AND orderid <= @orderid are going to be scanned even though they need not be returned. How many unnecessary page reads will be performed mainly depends on the density of the leading sort key—orderdate, in our case. The denser it is, the more unnecessary work is likely going to happen. In our case, the density of the orderdate column is very low (~1/1500); it is so low that the extra work is negligible. But, when the leading sort key is dense, you could get a noticeable improvement by using the second form of the predicate. Here’s an implementation of the stored procedure with the second predicate form:

IF OBJECT_ID(N'dbo.GetPage', N'P') IS NOT NULL DROP PROC dbo.GetPage;
GO
CREATE PROC dbo.GetPage
@orderdate AS DATE = '00010101', -- anchor sort key 1 (orderdate)
@orderid AS INT = 0, -- anchor sort key 2 (orderid)
@pagesize AS BIGINT = 25
AS

SELECT TOP (@pagesize) orderid, orderdate, custid, empid
FROM dbo.Orders
WHERE (orderdate = @orderdate AND orderid > @orderid)
OR orderdate > @orderdate
ORDER BY orderdate, orderid;
GO

Run the following code to get the third page:

EXEC dbo.GetPage @orderdate = '20101209', @orderid = 2830, @pagesize = 25;

The query plan for the implementation with the second form of the predicate is shown in Figure 5-3.

FIGURE 5-3 Plan for TOP with multiple anchor sort keys, second predicate form.

Observe that there’s no residual predicate, only Seek Predicates. Curiously, there are two seek predicates. Remember that, generally, the range scan performed by an Index Seek operator starts with the first match for Prefix and Start and ends with the last match for Prefix. In our case, one predicate (marked in the plan as [1] Seek Keys...) starts with orderdate = @orderdate AND orderid > @orderid and ends with orderdate = @orderdate. Another predicate (marked in the plan as [2] Seek Keys...) starts with orderdate = @orderdate and has no explicit end. What’s interesting is that during query execution, if Top Expression rows are found by the first seek, the execution of the operator short-circuits before getting to the second. But if the first seek isn’t sufficient, the second will be executed. The fact that in our example the leading sort key (orderdate) has low density could mislead you to think that the first predicate form is more efficient. If you test both implementations and compare the number of logical reads, you might see the first one performing 3 or more reads and the second one performing 6 or more reads (when two seeks are used). But if you test the solutions with a dense leading sort key, you will notice a significant difference in favor of the second solution.

There’s another method to using TOP to implement paging. You can think of it as the TOP over TOP, or nested TOP, method. You work with @pagenum and @pagesize as the inputs to the GetPage procedure. There’s no anchor concept here. You use one query with TOP to filter@pagenum * @pagesize rows based on the desired order. You define a table expression based on this query (call it D1). You use a second query against D1 with TOP to filter @pagesize rows, but in inverse order. You define a table expression based on the second query (call it D2). Finally, you write an outer query against D2 to order the rows in the desired order. Run the following code to implement the GetPage procedure based on this approach:

IF OBJECT_ID(N'dbo.GetPage', N'P') IS NOT NULL DROP PROC dbo.GetPage;
GO
CREATE PROC dbo.GetPage
@pagenum AS BIGINT = 1,
@pagesize AS BIGINT = 25
AS

SELECT orderid, orderdate, custid, empid
FROM ( SELECT TOP (@pagesize) *
FROM ( SELECT TOP (@pagenum * @pagesize) *
FROM dbo.Orders
ORDER BY orderid ) AS D1
ORDER BY orderid DESC ) AS D2
ORDER BY orderid;
GO

Here are three consecutive calls to the procedure requesting the first, second, and third pages:

EXEC dbo.GetPage @pagenum = 1, @pagesize = 25;
EXEC dbo.GetPage @pagenum = 2, @pagesize = 25;
EXEC dbo.GetPage @pagenum = 3, @pagesize = 25;

The plan for the third procedure call is shown in Figure 5-4.

FIGURE 5-4 Plan for TOP over TOP.

The plan is not very expensive, but there are three aspects to it that are not optimal when compared to the implementation based on the anchor concept. First, the plan scans the data in the index from the beginning of the leaf until the last qualifying row. This means that there’s repetition of work—namely, rescanning portions of the data. For the first page requested by the user, the plan will scan 1 * @pagesize rows, for the second page it will scan 2 * @pagesize rows, for the nth page it will scan n * @pagesize rows. Second, notice that the Key Lookup operator is executed 75 times even though only 25 of the lookups are relevant. Third, there are two Sort operators added to the plan: one reversing the original order to get to the last chunk of rows, and the other reversing it back to the original order to present it like this. For the third page request, the execution of this plan performed 241 logical reads. The greater the number of pages you have, the more work there is.

The benefit of this approach compared to the anchor-based strategy is that you don’t need to deal with collecting the anchor from the result of the last page request, and the user is not limited to navigating only between adjacent pages. For example, the user can start with page 1, request page 5, and so on.

Optimization of OFFSET-FETCH

The optimization of the OFFSET-FETCH filter is similar to that of TOP. Instead of reinventing the wheel by creating an entirely new plan operator, Microsoft decided to enhance the existing Top operator. Remember the Top operator has a property called Top Expression that indicates how many rows to request from the operator to the right and pass to the operator to the left. The enhanced Top operator used to process OFFSET-FETCH has a new property called OffsetExpression that indicates how many rows to request from the operator to the right and not pass to the operator to the left. The OffsetExpression property is processed before the Top Expression property, as you might have guessed.

To show you the optimization of the OFFSET-FETCH filter, I’ll use it in the implementation of the GetPage procedure:

IF OBJECT_ID(N'dbo.GetPage', N'P') IS NOT NULL DROP PROC dbo.GetPage;
GO
CREATE PROC dbo.GetPage
@pagenum AS BIGINT = 1,
@pagesize AS BIGINT = 25
AS

SELECT orderid, orderdate, custid, empid
FROM dbo.Orders
ORDER BY orderid
OFFSET (@pagenum - 1) * @pagesize ROWS FETCH NEXT @pagesize ROWS ONLY;
GO

As you can see, OFFSET-FETCH allows a simple and flexible solution that uses the @pagenum and @pagesize inputs. Use the following code to request the first three pages:

EXEC dbo.GetPage @pagenum = 1, @pagesize = 25;
EXEC dbo.GetPage @pagenum = 2, @pagesize = 25;
EXEC dbo.GetPage @pagenum = 3, @pagesize = 25;