EXPLAIN EXTENDED

From Stack Overflow:

My table (SQL Server 2008) has more than 1 million records.

When I try to order records by datetime, it takes 1 second, but when I order by id (integer), it only takes about 0.1 second.

Is there any way to improve the efficiency?

The obvious answer would be create an index on datetime

However, everything's not so simple.

Let's create a sample table and see why:

Table creation details

CREATE SCHEMA [20091111_clustered]
CREATE TABLE t_data (
id INT NOT NULL PRIMARY KEY,
data INT NOT NULL,
idatetime DATETIME NOT NULL,
udatetime DATETIME NOT NULL,
cdatetime DATETIME NOT NULL
)
GO
CREATE INDEX IX_data_idatetime ON [20091111_clustered].t_data (idatetime)
CREATE INDEX IX_data_cdatetime ON [20091111_clustered].t_data (cdatetime) INCLUDE (data)
BEGIN TRANSACTION
SELECT  RAND(20091111)
DECLARE @cnt INT
SET @cnt = 1
WHILE @cnt <= 1000000
BEGIN
        INSERT
        INTO    [20091111_clustered].t_data (id, data, idatetime, udatetime, cdatetime)
        VALUES  (@cnt,
                FLOOR(RAND() * 100),
                DATEADD(minute, -@cnt, '2009-11-11'),
                DATEADD(minute, -@cnt, '2009-11-11'),
                DATEADD(minute, -@cnt, '2009-11-11')
                )
        SET @cnt = @cnt + 1
END
COMMIT
GO

This table has 1,000,000 rows with a CLUSTERED PRIMARY KEY on id, and three DATETIME fields (all containing same data), indexed differently.

Let's see the performance of different ordering queries:

ORDER BY id

SELECT  SUM(data)
FROM    (
SELECT  TOP 999999 data
FROM    [20091111_clustered].t_data
ORDER BY
id
) q

Table 't_data'. Scan count 1, logical reads 6829, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

SQL Server Execution Times:
   CPU time = 297 ms,  elapsed time = 297 ms. 

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN [Expr1009]=(0) THEN NULL ELSE [Expr1010] END))
       |--Stream Aggregate(DEFINE:([Expr1009]=Count(*), [Expr1010]=SUM([test].[20091111_clustered].[t_data].[data])))
            |--Top(TOP EXPRESSION:((999999)))
                 |--Clustered Index Scan(OBJECT:([test].[20091111_clustered].[t_data].[PK__t_data__7345FA8E]), ORDERED FORWARD)

This query completes in less than 300 ms.

It uses a clustered index scan, of course. A clustered index keeps makes the table records to be in id order anyway and the rows come out of the clustered index scan already in id order.

ORDER BY udatetime

There is no index on udatetime:

SELECT  SUM(data)
FROM    (
SELECT  TOP 999999 data
FROM    [20091111_clustered].t_data
ORDER BY
udatetime DESC
) q

Table 't_data'. Scan count 3, logical reads 7493, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

SQL Server Execution Times:
   CPU time = 1813 ms,  elapsed time = 4037 ms. 

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN [Expr1009]=(0) THEN NULL ELSE [Expr1010] END))
       |--Stream Aggregate(DEFINE:([Expr1009]=Count(*), [Expr1010]=SUM([test].[20091111_clustered].[t_data].[data])))
            |--Top(TOP EXPRESSION:((999999)))
                 |--Parallelism(Gather Streams, ORDER BY:([test].[20091111_clustered].[t_data].[udatetime] DESC))
                      |--Sort(TOP 999999, ORDER BY:([test].[20091111_clustered].[t_data].[udatetime] DESC))
                           |--Clustered Index Scan(OBJECT:([test].[20091111_clustered].[t_data].[PK__t_data__7345FA8E]))

Since there is no index on udatetime, there is no other way to get the records sorted but to sort them. And that's what SQL Server does.

Since there are quite lots of records to sort here, the query takes 4 seconds. This is 13 times longer than sorting on id, which is what the original question states.

ORDER BY idatetime

There is an index on idatetime.

SELECT  SUM(data)
FROM    (
SELECT  TOP 999999 data
FROM    [20091111_clustered].t_data
ORDER BY
idatetime DESC
) q

Table 't_data'. Scan count 3, logical reads 7493, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

SQL Server Execution Times:
   CPU time = 1812 ms,  elapsed time = 3992 ms. 

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN [Expr1009]=(0) THEN NULL ELSE [Expr1010] END))
       |--Stream Aggregate(DEFINE:([Expr1009]=Count(*), [Expr1010]=SUM([test].[20091111_clustered].[t_data].[data])))
            |--Top(TOP EXPRESSION:((999999)))
                 |--Parallelism(Gather Streams, ORDER BY:([test].[20091111_clustered].[t_data].[idatetime] DESC))
                      |--Sort(TOP 999999, ORDER BY:([test].[20091111_clustered].[t_data].[idatetime] DESC))
                           |--Clustered Index Scan(OBJECT:([test].[20091111_clustered].[t_data].[PK__t_data__7345FA8E]))

Despite the fact that the index is present, SQL Server decides to use the same method as it used on a non-indexed column.

This may seem inefficient unless we remember that sorting is not everything we need here: we also need to get the value of data. The index on idatetime does not contain the values of data, only the values of idatetime and id. SQL Server would need to shuttle between the index pages and table pages to get the values of data while maintaining the idatetime order, were the index used. This would result in an extra row: Key Lookup in the plan that would describe this.

SQL Server considers the Key Lookup so expensive that it prefers ordering all rows over it.

Let's see whether this judgment is fair. To do this we should force SQL Server to use the index:

SELECT  SUM(data)
FROM    (
SELECT  TOP 100000 data
FROM    [20091111_clustered].t_data WITH (INDEX (IX_data_idatetime) FASTFIRSTROW)
ORDER BY
idatetime DESC
) q

Table 't_data'. Scan count 1, logical reads 306625, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

SQL Server Execution Times:
   CPU time = 313 ms,  elapsed time = 317 ms. 

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Stream Aggregate(DEFINE:([Expr1010]=Count(*), [Expr1011]=SUM([test].[20091111_clustered].[t_data].[data])))
            |--Top(TOP EXPRESSION:((100000)))
                 |--Nested Loops(Inner Join, OUTER REFERENCES:([test].[20091111_clustered].[t_data].[id], [Expr1009]) WITH ORDERED PREFETCH)
                      |--Index Scan(OBJECT:([test].[20091111_clustered].[t_data].[IX_data_idatetime]), ORDERED BACKWARD)
                      |--Clustered Index Seek(OBJECT:([test].[20091111_clustered].[t_data].[PK__t_data__7345FA8E]), SEEK:([test].[20091111_clustered].[t_data].[id]=[test].[20091111_clustered].[t_data].[id]) LOOKUP ORDERED FORWARD)

I changed the TOP 999999 to TOP 100000, or SQL Server would refuse to scan the table in the index order at all. But even with 10 times less rows, the overall query time is larger than of the query ordering by id. So using the index to keep the data ordered does not seem such a wise solution.

However, there is a third option

ORDER BY cdatetime

There is a covering index on cdatetime. The index pages are stored in a B+Tree ordered by cdatetime, and, additionally, the value of data is stored along with each record pointer.

SELECT  SUM(data)
FROM    (
SELECT  TOP 999999 data
FROM    [20091111_clustered].t_data
ORDER BY
cdatetime DESC
) q

Table 't_data'. Scan count 1, logical reads 4103, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

SQL Server Execution Times:
   CPU time = 281 ms,  elapsed time = 287 ms. 

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN [Expr1004]=(0) THEN NULL ELSE [Expr1005] END))
       |--Stream Aggregate(DEFINE:([Expr1004]=Count(*), [Expr1005]=SUM([test].[20091111_clustered].[t_data].[data])))
            |--Top(TOP EXPRESSION:((999999)))
                 |--Index Scan(OBJECT:([test].[20091111_clustered].[t_data].[IX_data_cdatetime]), ORDERED BACKWARD)

Now the query is fast, only 287 ms, even faster than ORDER BY id.

Since everything the query needs is contained in the index, no Clustered Index Scan is required to retrieve the values of data.

SQL Server documentation states that it is not possible to create two clustered indexes on a table. However, an index that would cover all columns of a table (except the indexed columns and the PRIMARY KEY) is exactly just like a secondary clustered index.

In fact, this would be just a shadow copy of the table but with records stored in other order.

Such an index could serve all the queries that require this order and it would never have to reference the actual table.