When you select from a table on an indexed column and order by that column in the opposite direction of the index, does the index help

Question

Let's say I have a large table of transactions with a date field and an index on that field in ascending order. If I select that field from the table and order by in reverse order is it able to somehow use that index in reverse, or is it going to have to do a table scan or some other less efficient method of accessing those records and sorting them?

Answer 1

If the index is covering it's likely it will be used in conjuction with a sort operation in the query plan to reverse the order.

Edit: Following a little more thought!

It will depend on whether this is a trivial query or involves joins. If trivial:

SELECT x,y FROM MyTable ORDER BY y DESC

and the index order is Y ASC, a reverse scan of the index leaf level should avoid a sort.

If non-trivial:

SELECT x,y FROM MyTable mt INNER JOIN MyOtherTable mot ON mot.y = mt.y

it should depend on the sort order of MyOtherTable.y. If it's ASC as per MyTable.y then the two indexes would be read in index order and a sort applied after the join. If it's desc, in theory a reverse order index scan could be used for the join and an additional sort wouldn't be required to satisfy your order by clause.

Edit2: Couldn't recall if this would show up in the execution plan in SQL Server. The icon doesn't indicate this is a reverse scan, nor does the tooltip on hover. Properties however shows 'Scan Direction - Backward' or checking the plan XML reveals

<IndexScan Ordered="true" --->ScanDirection="BACKWARD"<--- ForcedIndex="false" NoExpandHint="false">
            <DefinedValues>
              <DefinedValue>
                <ColumnReference Database="[TestDb]" Schema="[dbo]" Table="[MyTable]" Column="OtherId" />
              </DefinedValue>
            </DefinedValues>
            <Object Database="[TestDb]" Schema="[dbo]" Table="[MyTable]" Index="[IX_MyTable_OtherId]" />
          </IndexScan>

Answer 2

It can use the index but may need an extra sort to reverse it.

Ive noticed that later versions of SQL Server (2005+) seem to be cleverer and may not require a sort, but I haven't dug too deeply (Edit: as per Mark Storey-Smith's updated answer)

Answer 3

In MySQL, I would still say that the index helps. Here is why:

There are several status variables that monitor bidirectional and random key traversal.

Here are those status variables:

• Handler_read_first : The number of times the first entry in an index was read. If this value is high, it suggests that the server is doing a lot of full index scans; for example, SELECT col1 FROM foo, assuming that col1 is indexed.

• Handler_read_key : The number of requests to read a row based on a key. If this value is high, it is a good indication that your tables are properly indexed for your queries.

• Handler_read_last : The number of requests to read the last key in an index. With ORDER BY, the server will issue a first-key request followed by several next-key requests, whereas with With ORDER BY DESC, the server will issue a last-key request followed by several previous-key requests. This variable was added in MySQL 5.5.7.

• Handler_read_next : The number of requests to read the next row in key order. This value is incremented if you are querying an index column with a range constraint or if you are doing an index scan.

• Handler_read_prev : The number of requests to read the previous row in key order. This read method is mainly used to optimize ORDER BY ... DESC.

• Handler_read_rnd : The number of requests to read a row based on a fixed position. This value is high if you are doing a lot of queries that require sorting of the result. You probably have a lot of queries that require MySQL to scan entire tables or you have joins that do not use keys properly.

• Handler_read_rnd_next : The number of requests to read the next row in the data file. This value is high if you are doing a lot of table scans. Generally this suggests that your tables are not properly indexed or that your queries are not written to take advantage of the indexes you have.

Monitoring these variables will directly tell you of the presence of table scans (if the event indexes are not used), if ORDER BY ... DESC queries are present, and so forth.

IMHO, if Handler_read_last did not exist before MySQL 5.5, then ORDER BY ... DESC would have to be executed by full index scan and then executing Handler_read_prev for backward traversal.

Some detective work may be necessary in order to locate the specific queries (slow query logs, using --log-queries-not-using-indexes, general logs, etc).