Thread: Remove extra Sort node above a btree-compatible Index Scan

Thank you so much for asking! 

I borrowed the following three patches from the Index AM API cleanup
thread [1] and attached them here for reference:

v20-0001: TEST - Add loadable modules as tests of the AM API
v20-0003: TEST - Stop requiring BTREE_AM_OID outside btree
v20-0012: Use CompareType more and StrategyNumber less

The v20-0001 patch introduces the xtree loadable test module. Xtree as
an extension is a shallow copy of the btree index, it should behave
exactly like btree. Specifically, it uses the same operators and
strategy numbers as btree, and all of its IndexAMRoutine methods point
to the corresponding btree methods. The only difference is that xtree
belongs to a different opfamily.

v20-0001 adds two loadable modules:
src/test/module/xtree (a shallow copy of btree)
src/test/module/xhash (a shallow copy of hash, not relevant to this discussion)

These test modules are not meant for commit; they are used solely for
testing the Index AM API.

By running "make check" in src/test/module/xtree, a script included in
the patch copies all tests from src/test/regress and replaces all
btree indexes with xtree indexes, allowing verification of how the
Index AM API works with non-core indexes.

The other two patches serve the following purposes:

v20-0003 removes BTREE_AM_OID-specific assertions outside btree code,
allowing other Index AMs.

v20-0012 is nice to have since it also touches the PathKey struct and
adds a CompareType field in PathKey. CompareType is more generic for
sort ordering compared to AM-specific strategy numbers. I’d like to
include this patch because even if two AMs have different strategy
numbers, they could still map to the same CompareType. When it comes
to deciding whether two PathKeys represent the same ordering, what
really matters is the underlying sort operator, and CompareType is
very relevant in that regard.

So, with the above patches applied (v20-0012 is optional for this
demonstration), I can run the following queries:

-- setup
create extension xtree;
create table t (b int, x int);
create index on t using btree(b);
create index on t using xtree(x);
insert into t select i, i from generate_series(1, 1000)i;
analyze t;

-- queries
explain (costs off) select b from t where b < 10 order by (b);
explain (costs off) select x from t where x < 10 order by (x);

-- output:
test=# explain (costs off) select b from t where b < 10 order by (b);
             QUERY PLAN
------------------------------------
 Index Only Scan using t_b_idx on t
   Index Cond: (b < 10)
(2 rows)

test=# explain (costs off) select x from t where x < 10 order by (x);
                QUERY PLAN
------------------------------------------
 Sort
   Sort Key: x
   ->  Index Only Scan using t_x_idx on t
         Index Cond: (x < 10)
(4 rows)

Notice that the xtree index scan introduces an unnecessary Sort node,
even though the Index Only Scan already returns rows of x sorted by
the same operator (int4lt (”<”)) used in the ORDER BY (x) clause.

The problem I'm trying to solve is to eliminate this redundant sort
for btree-like index AMs.

[1] https://www.postgresql.org/message-id/a5dfb7cd-7a89-48ab-a913-e5304eee0854%40eisentraut.org

Best,
Alex