BUG #14562: Query optimization when sorting multiple UNIQUE columns

The following bug has been logged on the website:

Bug reference: 14562
Logged by: James Emerton
Email address: james(at)emerton(dot)info
PostgreSQL version: 9.6.1
Operating system: any
Description:

I believe I've found an opportunity for the query planner to make better
decisions when sorting results by multiple columns where the first column
has a unique constraint:

psql (9.5.4, server 9.6.1)
WARNING: psql major version 9.5, server major version 9.6.
Some psql features might not work.
Type "help" for help.

postgres=# CREATE EXTENSION "uuid-ossp";
CREATE EXTENSION
postgres=# CREATE TABLE test (id SERIAL PRIMARY KEY, key UUID DEFAULT
uuid_generate_v1() UNIQUE);
CREATE TABLE
postgres=# INSERT INTO test (id) SELECT * FROM generate_series(1, 1000);
INSERT 0 1000
postgres=# EXPLAIN SELECT * FROM test ORDER BY key, id;
QUERY PLAN
---------------------------------------------------------------
Sort (cost=66.83..69.33 rows=1000 width=20)
Sort Key: key, id
-> Seq Scan on test (cost=0.00..17.00 rows=1000 width=20)
(3 rows)

postgres=# EXPLAIN SELECT * FROM test ORDER BY key;
QUERY PLAN
------------------------------------------------------------------------------
Index Scan using test_key_key on test (cost=0.28..49.27 rows=1000
width=20)
(1 row)

It seems that these two queries are effectively identical, but the query
planner makes significantly different choices. In our application there are
several additional tables joined and the multiple column sort version is
over two orders of magnitude slower.