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

From: Alexandra Wang <[email-masked]>
Date: Thu, 27 Feb 2025 23:22:21 -0600

Hello hackers,

While reviewing Mark Dilger’s patch series "Index AM API cleanup" [1],
I noticed some unexpected plan diffs when running the xtree and treeb
test modules. Specifically, an additional Sort node appears on top of
an Index Only Scan, even when the index key and sort key are the same.
For example:

--- src/test/modules/xtree/expected/interval.out
+++ src/test/modules/xtree/results/interval.out
@@ -375,10 +375,12 @@
 SET enable_seqscan TO false;
 EXPLAIN (COSTS OFF)
 SELECT f1 FROM INTERVAL_TBL_OF r1 ORDER BY f1;
-                             QUERY PLAN
---------------------------------------------------------------------
- Index Only Scan using interval_tbl_of_f1_idx on interval_tbl_of r1
-(1 row)
+                                QUERY PLAN
+--------------------------------------------------------------------------
+ Sort
+   Sort Key: f1
+   ->  Index Only Scan using interval_tbl_of_f1_idx on interval_tbl_of r1
+(3 rows)

I’ve attached a patch that removes this unnecessary Sort node for
B-tree-compatible indexes. This change should:
- Reduce the number of test failures in the xtree module from 43 to 30
- Reduce the size of regression.diffs from 234K to 123K

Since pathkey comparison is a hot path in query planning and exercised
by many test queries, I plan to gather more performance metrics.
However, in a simple test running make installcheck with and without
the patch, I observed no negative impact on the runtime of the
regression test suite (which doesn’t include other btree-like indexes)
and a positive impact on the same regression tests for xtree.

Regression tests (same plans):
w/o patch:
make installcheck  1.36s user 2.21s system 12% cpu 28.018 total
w/ patch:
make installcheck  1.32s user 2.12s system 12% cpu 28.089 total

xtree tests:
w/o patch (inferior plan w/ extra sort node):
make installcheck  1.52s user 2.42s system 10% cpu 36.817 total
w/ patch (good plan):
make installcheck  1.52s user 2.48s system 12% cpu 32.201 total

I’ve marked the patch as no-cfbot, as it applies only on top of the
aforementioned patch series [1].

Thoughts?

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

Best,
Alex