EXPLAIN EXTENDED

From Stack Overflow:

When you create an index on a column or number of columns in MS SQL Server (I'm using version 2005), you can specify that the index on each column be either ascending or descending.

I'm having a hard time understanding why this choice is even here. Using binary sort techniques, wouldn't a lookup be just as fast either way?

What difference does it make which order I choose?

This matters when the composite indexes are used.

Let's create a sample table:

Table creation details

DROP TABLE [20090427_order].t_orderer
DROP SCHEMA [20090427_order]
GO
CREATE SCHEMA [20090427_order]
CREATE TABLE t_orderer (
id INT NOT NULL PRIMARY KEY,
column1 INT NOT NULL,
column2 INT NOT NULL
)
GO
CREATE INDEX IX_orderer_column1_column2_desc ON [20090427_order].t_orderer (column1, column2 DESC)
GO
SET NOCOUNT ON
DECLARE @cnt INT
SET @cnt = 1
BEGIN TRANSACTION
WHILE @cnt < 1000000
BEGIN
        INSERT
        INTO    [20090427_order].t_orderer
        VALUES  (@cnt, @cnt / 10000 + 1, @cnt % 10000 + 1)
        SET @cnt = @cnt + 1
END
COMMIT
GO

We created a composite index on t_orderer (column1, column2 DESC).

Now, let's try to select some rows with a given column1 value, ordered by column2 in both directions:

Ascending:

SET STATISTICS IO ON
SET STATISTICS TIME ON
SELECT  TOP 10 *
FROM    [20090427_order].t_orderer
WHERE   column1 = 10
ORDER BY
column1 ASC, column2 ASC

Table 't_orderer'. Scan count 1, logical reads 4, 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 = 0 ms,  elapsed time = 1 ms. 

Descending:

SET STATISTICS IO ON
SET STATISTICS TIME ON
SELECT  TOP 10 *
FROM    [20090427_order].t_orderer
WHERE   column1 = 10
ORDER BY
column1 ASC, column2 DESC

Table 't_orderer'. Scan count 1, logical reads 3, 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 = 0 ms,  elapsed time = 1 ms. 

The query plan shows the same for both queries:

INDEX SEEK → TOP

At first blush, there is no difference: index is used with same efficiency for both directions.

But let's look closer into the query above.

We see a condition in the WHERE clause: column1 = 10.

This condition covers a continuously ordered index range: (10, -INFINITY) < (column1, column2) < (10, +INFINITY).

This index range can be used to retrieve ordered value in both directions.

Now, let's change the query a little:

SET STATISTICS IO ON
SET STATISTICS TIME ON
SELECT  TOP 10 *
FROM    [20090427_order].t_orderer
WHERE   column1 BETWEEN 10 AND 100
ORDER BY
column1 ASC, column2 ASC

Table 't_orderer'. Scan count 3, logical reads 1932, physical reads 0, read-ahead reads 1327, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

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

Now, we have same resultset returned as in the query above, but execution time is much greater, and the plan now says:

INDEX SEEK → TOP N SORT → GATHER STREAMS → TOP

What happened?

We created index on (column1, column2 DESC). That means the column2 is sorted in opposite order to column1 in the index.

In the index, the row (10, 1) is immediately followed by (11, 10000), then by (11, 9999), etc.

In our initial query, any order could be satisifed by the index, since only a single value of column1 is to be selected. The optimizer takes this into account.

But in this query, INDEX SCAN does not yield the order on column1 ASC, column2 ASC anymore. That's why an additional SORT is required.

Now, if we use the index sorting condition in ORDER BY:

SET STATISTICS IO ON
SET STATISTICS TIME ON
SELECT  TOP 10 *
FROM    [20090427_order].t_orderer
WHERE   column1 BETWEEN 10 AND 100
ORDER BY
column1 ASC, column2 DESC

Table 't_orderer'. Scan count 1, logical reads 3, 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 = 0 ms,  elapsed time = 1 ms. 

the plan returns to the efficient one:

INDEX SEEK → TOP

and the query is instant again.

Note that we can also reverse the ORDER BY clause completely, and the index is still usable:

SET STATISTICS IO ON
SET STATISTICS TIME ON
SELECT  TOP 10 *
FROM    [20090427_order].t_orderer
WHERE   column1 BETWEEN 10 AND 100
ORDER BY
column1 DESC, column2 ASC

Table 't_orderer'. Scan count 1, logical reads 3, 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 = 0 ms,  elapsed time = 1 ms. 

Since an index can be traversed in either direction with same efficiency, this query is also instant.