v8-0006-SLOPE-redundancy-checks.patch

From bbde7e9d939647862dc0bd0fcf7ede6a4ed8aaab Mon Sep 17 00:00:00 2001
From: Alexandre Felipe <o.alexandre.felipe@gmail.com>
Date: Tue, 7 Apr 2026 08:23:20 +0100
Subject: [PATCH 6/6] SLOPE: redundancy checks

Detect two redundant cases that can be proven from monotonicity
1. When multiple pathkeys depend on the same index column,
   and each is a monotonic function of the next
   i.e. f2(f1(x)), f1(x), x, where f1 and f2 are monotonic functions.

This can be motivated by a query
SELECT row_number() OVER (PARTITION BY ts::date ORDER BY ts)
An index on ts would satisfy both the order on ts::date and on ts,
but when ts expression ts::dat

2. A pathkey is a function of a preceeding pathkey
   i.e. x, ..., f(x),
This is a generalisation of the existing redundancy check
Notice that this doesn't require f(x) to be monotonic,
just invariant.
---
 src/backend/optimizer/path/pathkeys.c | 112 ++++++++++++++----------
 src/test/regress/expected/slope.out   | 119 ++++++++++++++++++++++++++
 src/test/regress/sql/slope.sql        |  59 +++++++++++++
 3 files changed, 246 insertions(+), 44 deletions(-)

diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 0c0d1138cac..d5f6439f7f8 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1140,14 +1140,22 @@ build_index_pathkeys(PlannerInfo *root,
 											  false);
 
 		/*
-		 * SLOPE: if the first unmatched query pathkey is a monotonic
-		 * function of this index column, use that pathkey instead of
-		 * the column's own pathkey so the index can satisfy the query
-		 * ordering without a Sort.
+		 * SLOPE: scan query_pathkeys to emit all pathkeys that this
+		 * index column can satisfy — both direct (EquivalenceClass)
+		 * and monotonic (SLOPE) matches — in query order.
+		 *
+		 * Emitting in query order handles pathkey chains like:
+		 *
+		 *  [f(x), g(x), x] with all monotonic in x, the index order
+		 *    on x implies the order of every function.
+		 *
+		 *  [x, ..., f(x)] with f(x) is constant when x is constant, so
+		 *    f(x) is a redundant tiebreaker after x.
 		 */
-		if (index->rel->reloptkind == RELOPT_BASEREL)
 		{
 			ListCell   *lc2;
+			bool		cpathkey_emitted = false;
+			bool		slope_matched = false;
 
 			foreach(lc2, root->query_pathkeys)
 			{
@@ -1156,56 +1164,72 @@ build_index_pathkeys(PlannerInfo *root,
 				if (pathkey_is_redundant(qpk, retval))
 					continue;
 
-				if (cpathkey && qpk->pk_eclass == cpathkey->pk_eclass)
-					break;
+				if (cpathkey &&
+					qpk->pk_eclass == cpathkey->pk_eclass)
+				{
+					if (!pathkey_is_redundant(cpathkey, retval))
+						retval = lappend(retval, cpathkey);
+					cpathkey_emitted = true;
+					continue;
+				}
 
-				if (qpk->pk_var != NULL &&
+				if (index->rel->reloptkind == RELOPT_BASEREL &&
+					qpk->pk_var != NULL &&
 					!qpk->pk_eclass->ec_has_volatile &&
 					qpk->pk_varrelid == index->rel->relid &&
 					equal(qpk->pk_var, indexkey))
 				{
-					PathKey    *spk;
-
-					if (qpk->pk_slope == MONOTONICFUNC_BOTH)
+					/*
+					 * Case 1: f(x) before x — descending chain.
+					 * Need monotonicity to determine the sort direction
+					 * that f(x) inherits from the index order on x.
+					 */
+					if (!cpathkey_emitted)
 					{
-						EquivalenceMember *em;
-
-						em = linitial(qpk->pk_eclass->ec_members);
-						qpk->pk_slope = get_expr_slope_wrt(em->em_expr,
-														   qpk->pk_var);
+						PathKey    *spk;
+
+						if (qpk->pk_slope == MONOTONICFUNC_BOTH)
+						{
+							EquivalenceMember *em;
+
+							em = linitial(qpk->pk_eclass->ec_members);
+							qpk->pk_slope = get_expr_slope_wrt(em->em_expr,
+															   qpk->pk_var);
+						}
+						spk = slope_emit_pathkey(root, qpk, indexkey,
+												 reverse_sort, nulls_first);
+						if (spk && !pathkey_is_redundant(spk, retval))
+							retval = lappend(retval, spk);
+						slope_matched = true;
+						continue;
 					}
-					spk = slope_emit_pathkey(root, qpk, indexkey,
-											 reverse_sort, nulls_first);
-					if (spk)
-						cpathkey = spk;
+
+					/*
+					 * Case 2: f(x) after x — ascending chain.
+					 * x is already in retval, so within each group of
+					 * equal x values, f(x) is constant (for any
+					 * deterministic f).  The pathkey is redundant as a
+					 * tiebreaker regardless of monotonicity.
+					 */
+					if (!pathkey_is_redundant(qpk, retval))
+						retval = lappend(retval, qpk);
+					slope_matched = true;
+					continue;
 				}
 				break;
 			}
-		}
 
-		if (cpathkey)
-		{
-			/*
-			 * We found the sort key in an EquivalenceClass, so it's relevant
-			 * for this query.  Add it to list, unless it's redundant.
-			 */
-			if (!pathkey_is_redundant(cpathkey, retval))
-				retval = lappend(retval, cpathkey);
-		}
-		else
-		{
-			/*
-			 * Boolean index keys might be redundant even if they do not
-			 * appear in an EquivalenceClass, because of our special treatment
-			 * of boolean equality conditions --- see the comment for
-			 * indexcol_is_bool_constant_for_query().  If that applies, we can
-			 * continue to examine lower-order index columns.  Otherwise, the
-			 * sort key is not an interesting sort order for this query, so we
-			 * should stop considering index columns; any lower-order sort
-			 * keys won't be useful either.
-			 */
-			if (!indexcol_is_bool_constant_for_query(root, index, i))
-				break;
+			if (!cpathkey_emitted)
+			{
+				if (cpathkey)
+				{
+					if (!pathkey_is_redundant(cpathkey, retval))
+						retval = lappend(retval, cpathkey);
+				}
+				else if (!slope_matched &&
+						 !indexcol_is_bool_constant_for_query(root, index, i))
+					break;
+			}
 		}
 
 		i++;
diff --git a/src/test/regress/expected/slope.out b/src/test/regress/expected/slope.out
index 13fe339caf5..74d7f82b94a 100644
--- a/src/test/regress/expected/slope.out
+++ b/src/test/regress/expected/slope.out
@@ -401,5 +401,124 @@ FROM slope_nulls_results ORDER BY seq;
 RESET enable_seqscan;
 DROP TABLE slope_nulls_results;
 DROP TABLE slope_nulls_tmp;
+--
+-- Test pathkey chains: f(x), x (descending chain)
+-- The order of f(x) is implied by the order of x when f is monotonic.
+-- A single index on ts should satisfy ORDER BY ts::date, ts.
+--
+-- descending chain: ts::date, ts — both from index on ts
+explain (costs off, verbose)
+select * from slope_src order by ts::date, ts limit 10;
+                                           QUERY PLAN                                            
+-------------------------------------------------------------------------------------------------
+ Limit
+   Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, ((ts)::date)
+   ->  Index Scan using slope_src_ts_idx on public.slope_src
+         Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, (ts)::date
+(4 rows)
+
+-- descending chain: date_trunc('day', ts), ts
+explain (costs off, verbose)
+select * from slope_src order by date_trunc('day', ts), ts limit 10;
+                                                    QUERY PLAN                                                    
+------------------------------------------------------------------------------------------------------------------
+ Limit
+   Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, (date_trunc('day'::text, ts))
+   ->  Index Scan using slope_src_ts_idx on public.slope_src
+         Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, date_trunc('day'::text, ts)
+(4 rows)
+
+-- descending chain with siblings: date_trunc('month', ts), ts::date, ts
+explain (costs off, verbose)
+select * from slope_src order by date_trunc('month', ts), ts::date, ts limit 10;
+                                                           QUERY PLAN                                                           
+--------------------------------------------------------------------------------------------------------------------------------
+ Limit
+   Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, (date_trunc('month'::text, ts)), ((ts)::date)
+   ->  Index Scan using slope_src_ts_idx on public.slope_src
+         Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, date_trunc('month'::text, ts), (ts)::date
+(4 rows)
+
+--
+-- Test pathkey chains: x, f(x) (ascending chain)
+-- f(x) is constant when x is constant, so f(x) is a redundant tiebreaker.
+-- A single index on ts should satisfy ORDER BY ts, ts::date.
+--
+-- ascending chain: ts, ts::date — f(x) redundant after x
+explain (costs off, verbose)
+select * from slope_src order by ts, ts::date limit 10;
+                                           QUERY PLAN                                            
+-------------------------------------------------------------------------------------------------
+ Limit
+   Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, ((ts)::date)
+   ->  Index Scan using slope_src_ts_idx on public.slope_src
+         Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, (ts)::date
+(4 rows)
+
+-- ascending chain: ts, date_trunc('day', ts)
+explain (costs off, verbose)
+select * from slope_src order by ts, date_trunc('day', ts) limit 10;
+                                                    QUERY PLAN                                                    
+------------------------------------------------------------------------------------------------------------------
+ Limit
+   Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, (date_trunc('day'::text, ts))
+   ->  Index Scan using slope_src_ts_idx on public.slope_src
+         Output: id, v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz, date_trunc('day'::text, ts)
+(4 rows)
+
+-- ascending chain with non-monotonic but immutable function:
+-- abs() is immutable but NOT monotonic; still valid as tiebreaker.
+explain (costs off, verbose)
+select v_float8, abs(v_float8)
+from slope_src order by v_float8, abs(v_float8) limit 10;
+                               QUERY PLAN                               
+------------------------------------------------------------------------
+ Limit
+   Output: v_float8, (abs(v_float8))
+   ->  Index Only Scan using slope_src_v_float8_idx on public.slope_src
+         Output: v_float8, abs(v_float8)
+(4 rows)
+
+--
+-- Test DISTINCT with monotonic functions
+--
+-- DISTINCT on ts::date should use index on ts
+explain (costs off, verbose)
+select distinct ts::date from slope_src;
+                            QUERY PLAN                            
+------------------------------------------------------------------
+ Unique
+   Output: ((ts)::date)
+   ->  Index Only Scan using slope_src_ts_idx on public.slope_src
+         Output: (ts)::date
+(4 rows)
+
+-- DISTINCT on floor(v_float8)
+explain (costs off, verbose)
+select distinct floor(v_float8) from slope_src;
+                               QUERY PLAN                               
+------------------------------------------------------------------------
+ Unique
+   Output: (floor(v_float8))
+   ->  Index Only Scan using slope_src_v_float8_idx on public.slope_src
+         Output: floor(v_float8)
+(4 rows)
+
+--
+-- Test window functions with PARTITION BY monotonic function
+--
+-- Window with PARTITION BY ts::date ORDER BY ts
+explain (costs off, verbose)
+select ts::date, ts, row_number() over (partition by ts::date order by ts)
+from slope_src;
+                                             QUERY PLAN                                             
+----------------------------------------------------------------------------------------------------
+ WindowAgg
+   Output: ((ts)::date), ts, row_number() OVER w1
+   Window: w1 AS (PARTITION BY (slope_src.ts)::date ORDER BY slope_src.ts ROWS UNBOUNDED PRECEDING)
+   ->  Index Only Scan using slope_src_ts_idx on public.slope_src
+         Output: (ts)::date, ts
+(5 rows)
+
 -- Cleanup
 RESET enable_hashagg;
diff --git a/src/test/regress/sql/slope.sql b/src/test/regress/sql/slope.sql
index 2de5d69cdf3..31eba90695f 100644
--- a/src/test/regress/sql/slope.sql
+++ b/src/test/regress/sql/slope.sql
@@ -215,5 +215,64 @@ RESET enable_seqscan;
 DROP TABLE slope_nulls_results;
 DROP TABLE slope_nulls_tmp;
 
+--
+-- Test pathkey chains: f(x), x (descending chain)
+-- The order of f(x) is implied by the order of x when f is monotonic.
+-- A single index on ts should satisfy ORDER BY ts::date, ts.
+--
+
+-- descending chain: ts::date, ts — both from index on ts
+explain (costs off, verbose)
+select * from slope_src order by ts::date, ts limit 10;
+
+-- descending chain: date_trunc('day', ts), ts
+explain (costs off, verbose)
+select * from slope_src order by date_trunc('day', ts), ts limit 10;
+
+-- descending chain with siblings: date_trunc('month', ts), ts::date, ts
+explain (costs off, verbose)
+select * from slope_src order by date_trunc('month', ts), ts::date, ts limit 10;
+
+--
+-- Test pathkey chains: x, f(x) (ascending chain)
+-- f(x) is constant when x is constant, so f(x) is a redundant tiebreaker.
+-- A single index on ts should satisfy ORDER BY ts, ts::date.
+--
+
+-- ascending chain: ts, ts::date — f(x) redundant after x
+explain (costs off, verbose)
+select * from slope_src order by ts, ts::date limit 10;
+
+-- ascending chain: ts, date_trunc('day', ts)
+explain (costs off, verbose)
+select * from slope_src order by ts, date_trunc('day', ts) limit 10;
+
+-- ascending chain with non-monotonic but immutable function:
+-- abs() is immutable but NOT monotonic; still valid as tiebreaker.
+explain (costs off, verbose)
+select v_float8, abs(v_float8)
+from slope_src order by v_float8, abs(v_float8) limit 10;
+
+--
+-- Test DISTINCT with monotonic functions
+--
+
+-- DISTINCT on ts::date should use index on ts
+explain (costs off, verbose)
+select distinct ts::date from slope_src;
+
+-- DISTINCT on floor(v_float8)
+explain (costs off, verbose)
+select distinct floor(v_float8) from slope_src;
+
+--
+-- Test window functions with PARTITION BY monotonic function
+--
+
+-- Window with PARTITION BY ts::date ORDER BY ts
+explain (costs off, verbose)
+select ts::date, ts, row_number() over (partition by ts::date order by ts)
+from slope_src;
+
 -- Cleanup
 RESET enable_hashagg;
-- 
2.53.0