2011-12-03Indexing ASC, DESC and NULLS FIRST/LAST

Databases can read indexes in both directions. That means, that a pipelined order by works also, if the scanned index range is in the exact opposite order as requested by the order by clause. But ASC and DESC modifiers can still make an index unusable for a pipelined order by. And even that problem has a solution.

The following example just demonstrates index usage in reverse order. It delivers the sales since yesterday ordered by date and PRODUCT_ID—both descending.

SELECT sale_date, product_id, quantity
  FROM sales
 WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY sale_date DESC, product_id DESC;

The descending index scan is visible in the execution plan.

---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |  320 |  300 |
| 1 | TABLE ACCESS BY INDEX ROWID | SALES       |  320 |  300 |
|*2 |  INDEX RANGE SCAN DESCENDING| SALES_DT_PR |  320 |    4 |
---------------------------------------------------------------

The database traverses the index tree to find the last matching entry. From there on, it follows the leaf node chain “upwards”, as shown in Figure 6.2. That is why the leaf nodes are connected by a doubly linked list.

It is, however, crucial that the scanned index range is in the exact opposite order as required for the order by clause.

The following example does not fulfill this prerequisite, because it mixes ASC and DESC modifiers in the order by clause:

SELECT sale_date, product_id, quantity
  FROM sales
 WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY sale_date ASC, product_id DESC;

Figure 6.3 shows that the index cannot deliver the rows as requested by the order by clause—no matter which way you read the index. Getting the data in the desired order would need a “jump” while reading the index. But there is no such link in the index, that would tell where to continue reading. The database can therefore not use this index to avoid an explicit sort operation.

Most databases offer the possibility to align the index order to the order by clause for cases like that. More concretely, it means that you can use ASC and DESC modifiers in the index declaration:

  DROP INDEX sales_dt_pr;

CREATE INDEX sales_dt_pr
    ON sales (sale_date ASC, product_id DESC);

The index order corresponds to the order by clause, so that the database can omit the sort operation:

---------------------------------------------------------------
|Id | Operation                   | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT            |             |  320 |  301 |
| 1 |  TABLE ACCESS BY INDEX ROWID| SALES       |  320 |  301 |
|*2 |   INDEX RANGE SCAN          | SALES_DT_PR |  320 |    4 |
---------------------------------------------------------------

Figure 6.4 visualizes the new index order. Changing the sort order of the second column kind of swaps the direction of the two arrows from the previous figure. That makes the first arrow end where the second arrow starts, so that index can deliver the desired order without any “jump”.

Since indexes can be used in both directions anyway, ASC/DESC indexing is only needed to sort columns in mixed order. Secondary index on index organized tables being the only exception. They add the clustering key implicitly to the index definition, not leaving any possibility to specify their sort order manually. If you need to sort the clustering key descending, you have no other option than sorting all other columns descending. The index can be read backwards to deliver the desired order.

Besides ASC and DESC, the SQL standard defines one more modifier for the order by clause: NULLS FIRST or NULLS LAST. Explicit control over NULL sorting was introduced as an optional extension with SQL:2003 only. Database support is sparse, as a consequence. This is particularly worrying because the standard does not define the sort order of NULL. Although it defines that sorting must put all NULLs together, it does not specify if they should appear before or after all other entries. Strictly speaking, you would need to explicitly specify NULL sorting for all nullable columns in the order by clause to get a well-defined behaviour.

Fact is, however, that the optional extension is neither implemented by SQL Server 2012 nor MySQL 5.6. The Oracle database, to the contrary, supported NULLS sorting before it was part of the standard, but does not accept it in an index definition as of release 11g. The Oracle database can therefore not do a pipelined order by when sorting with NULLS FIRST. Solely the PostgreSQL database supports the NULLS modifier in both, the order by clause and the index definition.

The following overview summarizes the features provided by different databases.