Order By causes a scan on a large table

Question

I have the following query;

SELECT TOP 100 ID
FROM [dbo].[TableName] WITH (NOLOCK)
WHERE TypeId = 2
    AND DateTimeUTC < '2022-Aug-04 07:02:40'
    AND DateTimeUTC > '4/26/2022 7:36:36 AM'
ORDER BY ID ASC

The table [dbo].[TableName] (Not its real name, btw) has just over 118 million rows.

I've created the following Index on this table;

CREATE INDEX [ix_TableName_DateTimeUTC_TypeId] 
ON [dbo].[TableName] (DateTimeUTC, TypeId)
    WITH FILLFACTOR = 90;

If I run this query (excluding the ORDER BY), the query performs a SEEK on the above index, and completes instantly. However, as soon as I include the ORDER BY, the query performs a SCAN instead on the PK, reading all 118+ million rows. As you can imagine, this tanks the performance and the query takes a long time to finish.

The simplest way to resolve this problem is to just remove the ORDER BY clause altogether, however I don't think that's possible because the application (which makes this call) requires the data to be returned in order.

Any suggestions on how to improve this?

Answer 1

sortie

I would change the index to look like this:

CREATE INDEX 
    [TypeId_Id_DateTimeUTC] 
ON [dbo].[TableName] 
(
    TypeId, 
    Id, 
    DateTimeUTC
)
WITH 
(
    FILLFACTOR = 100,
    SORT_IN_TEMPDB = ON
);

The idea is to make the initial data location and sorting free, and also support the range predicate.

Having Id as the second column is so that the TypeId = 2 portion can be seeked and then the index rows are logically ordered by Id - SQL Server then just needs to read the index rows in their existing order until 100 rows matching the DateTimeUTC predicate are read. i.e. it is to avoid any sort operation.

I discuss this in some detail in these blog posts:

Let’s Design A SQL Server Index Together Part 1, Part 2, Part 3.

It is usually better, as a practical matter, to avoid a sort than a residual predicate.

Answer 2

You should use a consistent unambiguous format for datetime literals. It is weird having two entirely different formats for the > and < predicates.

DateTimeUTC, TypeId is not the optimal order for that index.

Columns used in equality conditions should be listed first so if this index is specifically to optimise that query then TypeId should be listed first (TypeId, DateTimeUTC). Otherwise best it can do is a range seek on the date part and a residual predicate.

If you do make that indexing change and still see the scan on the clustered index this is presumably because SQL Server thinks it is quicker to read them from a source that already has them in the desired order and discard the unmatching ones than it will be to sort them at run time. Due to the TOP 100 it only needs to find the first 100 to match and then can stop the scan.

You may well be a similar case to the issue here where date is largely correlated with id rather than being independent of it so it underestimates the rows that will need to be read in id order before it finds 100 matching the predicate.

Assuming ID is an ascending identity column and given that your DateTimeUTC predicate ends today likely the matching rows will all be at the end of the index not scattered evenly through out it so this is pretty much worst case.

Possible query hints to look at are DISABLE_OPTIMIZER_ROWGOAL to remove the row goal effect from the TOP or FORCESEEK to just tell it to use the seek anyway

Answer 3

The query pattern that you posted (range predicate and an ORDER BY on different columns) is difficult to cover with a traditional index. With a typical approach you have to choose between eliminating the sort (Erik's answer) or eliminating the residual predicate (Martin's answer). Assuming strong correlation between ID and DateTimeUTC and a relatively short date range filter, the performance of queries using Erik's index scales with the total row count in the table with a matching IdType value. The performance of queries using Martin's index depends on scanning and sorting the rows with a matching IdType value that are in the desired date range. You may not get acceptable performance with either solution depending on what your data looks like.

Consider the following alternate algorithm:

• For each calendar date in the date range, get the 100 rows with the lowest IDs for that date
• Combine all of the rows and sort to get the 100 rows with the globally lowest IDs

That approach scales with the number of days in your date range (about 100) as well as the number of rows in the table for just one day (to account for the start date not beginning at midnight). This algorithm can be efficiently implemented in SQL Server by creating a computed column and adding that column to an index:

ALTER TABLE Q315205 ADD DateUTC AS CAST(DateTimeUTC AS DATE);
 
CREATE INDEX [TypeId_DateUTC_ID_INCLUDE_DatetimeUTC] ON [dbo].Q315205
(TypeId, DateUTC, ID)
INCLUDE (DatetimeUTC);
 
GO 
 
DECLARE @StartDate DATE = '20220426';
DECLARE @EndDate DATE = '20220805';

SELECT TOP (100) ca.ID
FROM ( -- derived table of numbers, can replace with something else
    SELECT TOP (DATEDIFF(DAY, @StartDate, @EndDate)) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) q
CROSS APPLY (
    SELECT TOP (100) ID
    FROM [dbo].Q315205 WITH (NOLOCK)
    WHERE TypeId = 2
    AND DateTimeUTC < '20220804 07:02:40'
    AND DateTimeUTC > '20220426 07:36:36' -- causes a residual predicate for one day
    AND DateUTC = DATEADD(DAY, q.RN - 1, @StartDate)
    ORDER BY ID
) ca (ID)
ORDER BY ca.ID
OPTION (NO_PERFORMANCE_SPOOL);

Here's what the query plan looks like:

The part in green generates the date values needed for the filter range (all 101 of them), the red part uses the index to get the smallest IDs for each date using the new index, and the blue part sorts the 10100 rows to get the smallest IDs globally.

I created a test table 28 GB in size with 120 million rows. The values for DateTimeUTC were evenly spread between 2018-01-01 and 2022-08-05. All of the data had a TypeId of 2. To be fair, this is the worst case scenario for Erik's index. Here are the timings for the different approaches on my local machine:

+------------------------------+---------------+
|          Algorithm           | CPU Time (ms) |
+------------------------------+---------------+
| Clustered index scan         |         13858 |
| Erik's index (no sort)       |          3222 |
| Martin's index (no residual) |          1044 |
| Computed column skip scan    |             6 |
+------------------------------+---------------+

Answer 4

If you need a scheme to find rows for a given time range ordered by ID, but don't want to create a computed column or an index that might be bigger than the original table, there is a way using an indexed view, assuming some correlation between ID values and the date.

The general idea of the solution below is to maintain a distinct list of dates and associated ID ranges for each TypeID using an indexed view (which is always synchronized with the base table in SQL Server). Aggregating IDs into ranges means the indexed view can be very much smaller than the base table.

Given a range of dates to query, we can find the ID ranges we need to inspect from the indexed view, then check for exact matches in the base table using a seek on the existing clustered index. Sorting the small view list by ID range allows us to find ordered matching rows efficiently.

This scheme works best when many IDs in a range occur for each day and TypeID. The worst case is when all IDs are separated by more than the range size from every other value per day and TypeID. The range size used in this example is 1000.

Aside from the required unique clustered index on the small indexed view, no new columns or indexes are needed for this solution.

Test table and data

This script creates 84,067,200 rows of data, requiring 1GB of storage with page compression. There's a row for each second between 1 January 2020 and 31 August 2022.

CREATE TABLE dbo.TableName
(
    ID bigint IDENTITY NOT NULL,
    TypeID integer NOT NULL,
    DateTimeUTC datetime NOT NULL,

    CONSTRAINT [PK dbo.TableName ID]
        PRIMARY KEY CLUSTERED (ID)
        WITH (DATA_COMPRESSION = PAGE)
);

-- Add 84,067,200 rows
WITH N AS
(
    SELECT TOP 
    (
        DATEDIFF(SECOND,
            CONVERT(datetime, '2020-01-01', 120),
            CONVERT(datetime, '2022-08-31', 120)) 
    )
        n = ROW_NUMBER() OVER (ORDER BY @@SPID) 
    FROM sys.all_columns AS AC1
    CROSS JOIN sys.all_columns AS AC2
    ORDER BY n
)
INSERT dbo.TableName WITH (TABLOCK)
    (TypeID, DateTimeUTC)
SELECT 
    TypeID = 2,
    DateTimeUTC =
        DATEADD(SECOND, N.n, 
            CONVERT(datetime, '2020-01-01', 120))
FROM N;

Indexed view

The view contains one row for each TypeID, date, and range of up to 1000 IDs. There's nothing special about the 1000 number—you can experiment with different range sizes by changing the constants and rebuilding the view.

CREATE OR ALTER VIEW dbo.TableNameSummary
WITH SCHEMABINDING AS
SELECT 
    TN.TypeID,
    DateOnly = CONVERT(date, TN.DateTimeUTC),
    IDrange1K = FLOOR(TN.ID / 1000) * 1000,
    NumRows = COUNT_BIG(*)
FROM dbo.TableName AS TN
GROUP BY
    TN.TypeID,
    CONVERT(date, TN.DateTimeUTC), 
    FLOOR(TN.ID / 1000) * 1000;
GO
CREATE UNIQUE CLUSTERED INDEX 
    [CUQ dbo.TableNameSummary TypeID, DateOnly, IDrange1K]
ON dbo.TableNameSummary 
    (TypeID, DateOnly, IDrange1K)
WITH (DATA_COMPRESSION = PAGE);

The view contains 84,847 rows in 952KB for this example.

Query

DECLARE 
    @Rows bigint = 100,
    @StartDate datetime = CONVERT(datetime, '2022-04-26 07:36:36', 120),
    @EndDate datetime = CONVERT(datetime, '2022-08-04 07:02:40', 120);

WITH Ranges AS
(
    -- Low end of ID ranges from the indexed view.
    -- DISTINCT because a range may have data for several days.
    SELECT DISTINCT TNS.IDrange1K
    FROM dbo.TableNameSummary AS TNS WITH (NOEXPAND)
    WHERE
        TNS.TypeID = 2
        AND TNS.DateOnly >= CONVERT(date, @StartDate)
        AND TNS.DateOnly <= CONVERT(date, @EndDate)
)
SELECT TOP (@Rows)
    MR.ID
FROM Ranges AS R
CROSS APPLY 
(
    -- Find matching rows in each ID range
    SELECT TOP (@Rows) TN.ID
    FROM dbo.TableName AS TN
    WHERE 
        -- Match ID group from indexed view
        TN.ID >= R.IDrange1K
        AND TN.ID < (R.IDrange1K + 1000)
        -- Must check individual rows match
        -- the exact date & time range
        AND TN.DateTimeUTC > @StartDate
        AND TN.DateTimeUTC < @EndDate
    ORDER BY
        TN.ID ASC
) AS MR
ORDER BY
    R.IDrange1K ASC,
    MR.ID ASC;

Results are returned in 11ms with a serial row-mode execution plan:

The distinct sort is applied to 8,807 rows from the indexed view in this example. The base table seek finds 27,897 rows before applying a residual predicate for exact date & time range matches. This is due to many rows on the first date falling before the start time at the low end of the desired range.

Example execution plans

Original query:

With Erik's index:

With Dan's index:

With the indexed view (as above):

Using Joe's scheme:

Performance summary

Tested on SQL Server 2019 CU16-GDR. Parallelism enabled where it's beneficial, MAXDOP 12.

Table size (with page compression) 1,026,312KB.

Best result in each group in bold.

Author	Time (ms)	Extra Index Size (KB)	Compression	Parallel
Original	1364			Yes
Erik	359	2,170,296	None	Yes
Erik	590	1,493,784	Row	Yes
Erik	974	1,026,000	Page	Yes
Dan	275	2,170,296	None	Yes
Dan	311	1,493,784	Row	Yes
Dan	387	1,026,000	Page	Yes
Paul	10	2,712	None	No
Paul	11	1,344	Row	No
Paul	11	952	Page	No
Joe	4	2,418,640	None	No
Joe	5	1,742,936	Row	No
Joe	6	1,027,456	Page	No

Answer 5

Quite often, people order by an ID column when it's the clustered primary key because they believe that will make the query faster.

In reality, the consumer of your query results might just want the oldest records first. The query currently uses ID as a proxy for record age, since rows with lower ID values are likely to have been inserted earlier. This is particularly so for the common case when the ID column is also IDENTITY.

In this case, the practice of ordering by the clustering key is counter-productive as other answers have already explained.

If you were to select the 100 rows by oldest date instead of ID, your problem would be much simpler:

SELECT TOP 100 ID
FROM [dbo].[TableName] WITH (NOLOCK)
WHERE TypeId = 2
    AND DateTimeUTC < '2022-Aug-04 07:02:40'
    AND DateTimeUTC > '4/26/2022 7:36:36 AM'
ORDER BY DateTimeUTC ASC; -- changed from ID

This is a very straightforward query to satisfy with an index, as proposed by Martin Smith:

CREATE INDEX [IX dbo.TableName TypeID, DateTimeUTC (ID)] 
ON dbo.TableName (TypeID, DateTimeUTC) 
INCLUDE (ID);

No matter the size of the table, this index will immediately locate the required 100 rows in the right order:

The biggest problem with this new index (assuming there are no, or very few, other columns) is it essentially makes a copy of the whole table, just sorted differently.

You could consider making the new index clustered instead, and creating a unique nonclustered index on the ID column alone if that would be useful. It depends on how other queries use this table in your workload.

Having a clustered primary key on an identity column isn't always a bad practice, but it's not always optimal either. Indexing should support the ways your data is actually used.

Answer 6

Have you tried to make ID an included column in the index?

I'm not talking about making ID a part of the indexed column list, but adding it as a supplemental "included column", as explained in https://learn.microsoft.com/en-us/sql/relational-databases/indexes/create-indexes-with-included-columns?view=sql-server-ver16

For instance, you may define your index as:

CREATE INDEX [ix_TableName_DateTimeUTC_TypeId] 
    ON [dbo].[TableName] (DateTimeUTC, TypeId)
    INCLUDE (ID) -- this is the "included column" part
    WITH FILLFACTOR = 90;

Included columns don't alter the index definition per se, and don't impact on query performance, but allow the engine to return them as part of a query without having to perform secondary scans.

Answer 7

Adding to Eriks answer: If you only query with TypeId = 2, you can add a filtered index that is only built for that clause by adding

WHERE TypeId = 2

when declaring the index https://learn.microsoft.com/en-us/sql/relational-databases/indexes/create-filtered-indexes

Answer 8

Insetad of dealing with Microsoft's cumbersome index bulding criteria and execution plans, you can try the following low tech workaround. I assumed field ID is of type Int, but you can create the temporary table as needed.

CREATE TABLE #Temp ( ID Int NOT Null)

INSERT INTO #Temp SELECT TOP 100 ID FROM [dbo].[TableName] WITH (NOLOCK) WHERE TypeId = 2 AND DateTimeUTC < '2022-Aug-04 07:02:40' AND DateTimeUTC > '4/26/2022 7:36:36 AM'

SELECT ID FROM #Temp ORDER BY ID ASC

DROP TABLE #Temp