Support incremental sorts

[dqii]

B-Tree indices support incremental sorts on top of an index.

postgres=# create table temp_table(id serial primary key, v integer, b integer);
CREATE TABLE
postgres=# insert into temp_table(v) values (1), (2), (3);
INSERT 0 3
postgres=# create index on temp_table(v);
CREATE INDEX
postgres=# set enable_seqscan = off;
SET
postgres=# explain select 1 from temp_table order by v;
                                       QUERY PLAN                                        
-----------------------------------------------------------------------------------------
 Index Only Scan using temp_table_v_idx on temp_table  (cost=0.13..12.18 rows=3 width=8)
(1 row)

postgres=# explain select 1 from temp_table order by v, id;
                                        QUERY PLAN                                         
-------------------------------------------------------------------------------------------
 Incremental Sort  (cost=4.15..12.31 rows=3 width=12)
   Sort Key: v, id
   Presorted Key: v
   ->  Index Scan using temp_table_v_idx on temp_table  (cost=0.13..12.18 rows=3 width=12)
(4 rows)
postgres=# explain select 1 from temp_table order by v, b;
                                        QUERY PLAN                                         
-------------------------------------------------------------------------------------------
 Incremental Sort  (cost=4.15..12.31 rows=3 width=12)
   Sort Key: v, b
   Presorted Key: v
   ->  Index Scan using temp_table_v_idx on temp_table  (cost=0.13..12.18 rows=3 width=12)
(4 rows)

We should do the same.

[dqii]

https://stackoverflow.com/questions/52033327/multi-column-indexes-and-order-by This is a new-ish feature and tests should account for that.

[dqii]

It seems like both https://github.com/lanterndata/lantern/issues/85 and this issue are supposed to be supported out of the box by Postgres. Maybe the issue is with the cost estimate function.

[Ngalstyan4]

Given @dqii 's observation above, it would be great to collect conclusive evidence and add some tests to check these and close this issue with that