Relax overly strict rules in select_outer_pathkeys_for_merge()

The select_outer_pathkeys_for_merge function made an attempt to build the
merge join pathkeys in the same order as query_pathkeys.  This was done as
it may have led to no sort being required for an ORDER BY or GROUP BY
clause in the upper planner.  However, this restriction seems overly
strict as it required that we match the query_pathkeys entirely or we
don't bother putting the merge join pathkeys in that order.

Here we relax this rule so that we use a prefix of the query_pathkeys
providing that prefix matches all of the join quals.  This may provide the
upper planner with partially sorted input which will allow the use of
incremental sorts instead of full sorts.

Author: David Rowley
Reviewed-by: Richard Guo
Discussion: https://postgr.es/m/CAApHDvrtZu0PHVfDPFM4Yx3jNR2Wuwosv+T2zqa7LrhhBr2rRg@mail.gmail.com

1 files changed, 31 insertions, 0 deletions

diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index e1d9d971d6..b9853af2dc 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2437,6 +2437,37 @@ select count(*) from
  10000
 (1 row)
 
+set enable_hashjoin = 0;
+set enable_nestloop = 0;
+set enable_hashagg = 0;
+--
+-- Check that we use the pathkeys from a prefix of the group by / order by
+-- clause for the join pathkeys when that prefix covers all join quals.  We
+-- expect this to lead to an incremental sort for the group by / order by.
+--
+explain (costs off)
+select x.thousand, x.twothousand, count(*)
+from tenk1 x inner join tenk1 y on x.thousand = y.thousand
+group by x.thousand, x.twothousand
+order by x.thousand desc, x.twothousand;
+                                    QUERY PLAN                                    
+----------------------------------------------------------------------------------
+ GroupAggregate
+   Group Key: x.thousand, x.twothousand
+   ->  Incremental Sort
+         Sort Key: x.thousand DESC, x.twothousand
+         Presorted Key: x.thousand
+         ->  Merge Join
+               Merge Cond: (y.thousand = x.thousand)
+               ->  Index Only Scan Backward using tenk1_thous_tenthous on tenk1 y
+               ->  Sort
+                     Sort Key: x.thousand DESC
+                     ->  Seq Scan on tenk1 x
+(11 rows)
+
+reset enable_hashagg;
+reset enable_nestloop;
+reset enable_hashjoin;
 --
 -- Clean up
 --