Multi-column indexes and ORDER BY

Question

The PostgreSQL documentation states that if we run a query ... ORDER BY x ASC, y DESC on a table with an index ... (x ASC, y ASC), the index cannot be used because the directions do not match.

1. Does this mean that this index is completely useless, or can the database engine use the index to order the x ASC part (and then manually sort the y DESC part)?
2. What if we run a query ... WHERE x = 999 ORDER BY y DESC, can this index be used?

Answer 1

Answer to question 1.

Postgres 12 or older

No, the index cannot be used, like the manual suggests. You can verify by creating such an index on any table and then, for the test session only:

SET enable_seqscan = OFF;

Then:

EXPLAIN
SELECT * FROM tbl ORDER BY ORDER BY x, y DESC;

Now, if the index could be used in any way, it would be. But you'll still see a sequential scan.

Corner case exception: If an index-only scan is possible, the index might still be used if it's substantially smaller than the table. But rows have to be sorted from scratch.

Related:

• Optimizing queries on a range of timestamps (two columns)

Postgres 13 or newer

Postgres 13 added "incremental sort", which can be controlled with the GUC setting enable_incremental_sort that is on by default. The release notes:

If an intermediate query result is known to be sorted by one or more leading keys of a required sort ordering, the additional sorting can be done considering only the remaining keys, if the rows are sorted in batches that have equal leading keys.

Corner case problems have been fixed with version 13.1 and 13.2. So - as always - be sure to run the latest point release.

Now, the index can be used. You'll see something like this in the EXPLAIN plan:

Sort Key: x, y DESC
Presorted Key: x

It's not as efficient as an index with matching (switched) sort order where readily sorted rows can be read from the index directly (with no sort step at all). But it can be a huge improvement, especially with a small LIMIT, where Postgres had to sort all rows historically. Now it can look at each (set of) leading column(s), sort only those, and stop as soon as LIMIT is satisfied.

Answer to question 2.

Yes, the index fits perfectly.

(Even works if the index has y ASC. It can be scanned backwards. Only NULL placement is a drawback in this case.)

Of course, if x = 999 is a stable predicate (it's always 999 we are interested in) and more than a few rows have a different x, then a partial index would be even more efficient:

CREATE INDEX ON tbl (y DESC) WHERE x = 999;

db<>fiddle here - Postgres 10

db<>fiddle here - Postgres 13 (2nd demo uses incremental sort now)