better_windowclause_sorting_dgr-v4.patch

From f3dd5a27f63030dea8d1530896daf4ba1c8a5265 Mon Sep 17 00:00:00 2001
From: Ankit Kumar Pandey <itsankitkp@gmail.com>
Date: Sat, 7 Jan 2023 19:10:24 +0530
Subject: [PATCH] Additional sort for root's order by can be optimized if
 sorting for extra columns are performed while sorting for window functions
 (if sort clause of window functions are subset of root's sort clause).

---
 src/backend/optimizer/plan/planner.c |  68 +++++++++-
 src/include/nodes/pg_list.h          |  14 ++
 src/test/regress/expected/window.out | 187 +++++++++++++++++++++++++++
 src/test/regress/sql/window.sql      |  94 ++++++++++++++
 4 files changed, 362 insertions(+), 1 deletion(-)

diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 000d757bdd..10d68e2fc3 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4423,6 +4423,13 @@ create_one_window_path(PlannerInfo *root,
 	PathTarget *window_target;
 	ListCell   *l;
 	List	   *topqual = NIL;
+	bool		has_runcondition = false;
+
+	List	   *window_pathkeys;
+	List	   *orderby_pathkeys = NIL;
+	int			index = 0;
+	int			i;
+	bool		try_sort_pushdown = false;
 
 	/*
 	 * Since each window clause could require a different sort order, we stack
@@ -4441,10 +4448,41 @@ create_one_window_path(PlannerInfo *root,
 	 */
 	window_target = input_target;
 
+	try_sort_pushdown = (root->parse->distinctClause == NIL &&
+								root->parse->sortClause != NIL &&
+								root->parse->limitCount == NULL &&
+								!contain_window_function((Node *) get_sortgrouplist_exprs(root->parse->sortClause,
+																	  root->processed_tlist)));
+
+
+	if (try_sort_pushdown)
+	{
+		/*
+		 * Search for the window function whose path keys are
+		 * subset of orderby_path keys, this allows us to perform
+		 * order by pushdown from this position of window function onwards
+		 */
+		foreach_reverse(l, activeWindows)
+		{
+			WindowClause *wc = lfirst_node(WindowClause, l);
+			orderby_pathkeys = make_pathkeys_for_sortclauses(root,
+															 root->parse->sortClause,
+															 root->processed_tlist);
+			window_pathkeys = make_pathkeys_for_window(root,
+														wc,
+														root->processed_tlist);
+			has_runcondition |= (wc->runCondition != NIL);
+			if (!pathkeys_contained_in(window_pathkeys, orderby_pathkeys) || has_runcondition)
+				break;
+
+			index = foreach_current_index(l);
+		}
+	}
+
+	i=0;
 	foreach(l, activeWindows)
 	{
 		WindowClause *wc = lfirst_node(WindowClause, l);
-		List	   *window_pathkeys;
 		int			presorted_keys;
 		bool		is_sorted;
 		bool		topwindow;
@@ -4457,6 +4495,34 @@ create_one_window_path(PlannerInfo *root,
 												path->pathkeys,
 												&presorted_keys);
 
+		/*
+		 * If not sorted already and the query has an ORDER BY clause, then we
+		 * try to push the entire ORDER BY below the final WindowAgg.  We
+		 * don't do this when the query has a DISTINCT clause as the planner
+		 * might opt to do a Hash Aggregate and spoil our efforts here.  We
+		 * also can't do this when the ORDER BY contains any WindowFuncs as we
+		 * obviously can't sort something that's yet to be evaluated.  We also
+		 * don't bother with this when there is a WindowClauses with a
+		 * runCondition as those can reduce the number of rows to sort in the
+		 * ORDER BY and we don't want add complexity to the WindowAgg sort if
+		 * the final ORDER BY sort is going to have far fewer rows to sort.
+		 * For the same reason, don't bother if the query has a LIMIT clause.
+		 */
+		if (try_sort_pushdown && !is_sorted && (i == index))
+		{
+			orderby_pathkeys = make_pathkeys_for_sortclauses(root,
+															 root->parse->sortClause,
+															 root->processed_tlist);
+
+			if (pathkeys_contained_in(window_pathkeys, orderby_pathkeys))
+				window_pathkeys = orderby_pathkeys;
+
+			is_sorted = pathkeys_count_contained_in(window_pathkeys,
+													path->pathkeys,
+													&presorted_keys);
+		}
+		i++;
+
 		/* Sort if necessary */
 		if (!is_sorted)
 		{
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 529a382d28..82d108f672 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -378,6 +378,20 @@ lnext(const List *l, const ListCell *c)
 		 (cell = NULL, false); \
 		 cell##__state.i++)
 
+/*
+ * foreach_reverse -
+ *	  a convenience macro for looping through a list in reverse
+ *
+ * This is equivalent to foreach, only in reverse
+ */
+#define foreach_reverse(cell, lst)	\
+	for (ForEachState cell##__state = {(lst), cell##__state.l->length-1}; \
+		 (cell##__state.l != NIL && \
+		  cell##__state.i >= 0) ? \
+		 (cell = &cell##__state.l->elements[cell##__state.i], true) : \
+		 (cell = NULL, false); \
+		 cell##__state.i--)
+
 /*
  * foreach_delete_current -
  *	  delete the current list element from the List associated with a
diff --git a/src/test/regress/expected/window.out b/src/test/regress/expected/window.out
index 90e89fb5b6..d83fea8091 100644
--- a/src/test/regress/expected/window.out
+++ b/src/test/regress/expected/window.out
@@ -3982,7 +3982,194 @@ ORDER BY depname, empno;
                                  ->  Seq Scan on empsalary
 (11 rows)
 
+-- Do not perform sort pushdown if column is presorted
+CREATE INDEX depname_idx ON empsalary(depname);
+SET enable_seqscan=0;
+EXPLAIN (COSTS OFF)
+SELECT empno,
+        min(salary) OVER (PARTITION BY depname) depminsalary
+FROM empsalary
+ORDER BY depname, empno;
+                      QUERY PLAN                       
+-------------------------------------------------------
+ Incremental Sort
+   Sort Key: depname, empno
+   Presorted Key: depname
+   ->  WindowAgg
+         ->  Index Scan using depname_idx on empsalary
+(5 rows)
+
+-- Do perform sort pushdown if columns are only partially sorted
+EXPLAIN (COSTS OFF)
+SELECT empno,
+        min(salary) OVER (PARTITION BY depname, empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+                      QUERY PLAN                       
+-------------------------------------------------------
+ WindowAgg
+   ->  Incremental Sort
+         Sort Key: depname, empno, enroll_date
+         Presorted Key: depname
+         ->  Index Scan using depname_idx on empsalary
+(5 rows)
+
+DROP INDEX depname_idx;
+RESET enable_seqscan;
 RESET enable_hashagg;
+-- If window function's ORDER BY is subset of QUERY's ORDER BY, sort as per as
+-- QUERY's ORDER BY to save additional sorting in the end
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (ORDER BY depname) depminsalary
+FROM empsalary
+ORDER BY depname, empno;
+            QUERY PLAN             
+-----------------------------------
+ WindowAgg
+   ->  Sort
+         Sort Key: depname, empno
+         ->  Seq Scan on empsalary
+(4 rows)
+
+-- Same as above, but PARTITION BY clause is included as well
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+                  QUERY PLAN                   
+-----------------------------------------------
+ WindowAgg
+   ->  Sort
+         Sort Key: depname, empno, enroll_date
+         ->  Seq Scan on empsalary
+(4 rows)
+
+-- Negation of above, when sort optimization is not needed to be performed
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY empno, enroll_date;
+               QUERY PLAN                
+-----------------------------------------
+ Sort
+   Sort Key: empno, enroll_date
+   ->  WindowAgg
+         ->  Sort
+               Sort Key: depname, empno
+               ->  Seq Scan on empsalary
+(6 rows)
+
+-- ORDER BY's in multiple Window functions can be combined into one
+-- if they are subset of QUERY's ORDER BY
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary,
+       sum(salary) OVER (PARTITION BY depname) depsalary,
+       count(*) OVER (ORDER BY enroll_date DESC) c
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+                      QUERY PLAN                      
+------------------------------------------------------
+ WindowAgg
+   ->  WindowAgg
+         ->  Sort
+               Sort Key: depname, empno, enroll_date
+               ->  WindowAgg
+                     ->  Sort
+                           Sort Key: enroll_date DESC
+                           ->  Seq Scan on empsalary
+(8 rows)
+
+-- order of window function shouldn't affect query's ORDER BY pushdown
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       count(*) OVER (ORDER BY enroll_date DESC) c,
+       sum(salary) OVER (PARTITION BY depname) depsalary,
+       min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+                      QUERY PLAN                      
+------------------------------------------------------
+ WindowAgg
+   ->  WindowAgg
+         ->  Sort
+               Sort Key: depname, empno, enroll_date
+               ->  WindowAgg
+                     ->  Sort
+                           Sort Key: enroll_date DESC
+                           ->  Seq Scan on empsalary
+(8 rows)
+
+-- SORT OPTIMIZATION (as in cases above) is not needed to be performed
+-- in cases, as mentioned below.
+-- Case #1: When distinct clause is included
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT empno,
+       depname,
+       min(salary) OVER (PARTITION BY depname) depminsalary,
+       sum(salary) OVER (PARTITION BY depname) depsalary,
+       count(*) OVER (ORDER BY enroll_date DESC) c
+FROM empsalary
+ORDER BY depname, empno;
+                                              QUERY PLAN                                               
+-------------------------------------------------------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: depname, empno, (min(salary) OVER (?)), (sum(salary) OVER (?)), (count(*) OVER (?))
+         ->  WindowAgg
+               ->  Sort
+                     Sort Key: depname
+                     ->  WindowAgg
+                           ->  Sort
+                                 Sort Key: enroll_date DESC
+                                 ->  Seq Scan on empsalary
+(10 rows)
+
+-- Case #2: When Limit clause is specified
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (PARTITION BY empno) depminsalary,
+       sum(salary) OVER (PARTITION BY empno) depsalary
+FROM empsalary
+ORDER BY empno, depname LIMIT 1;
+                  QUERY PLAN                   
+-----------------------------------------------
+ Limit
+   ->  Incremental Sort
+         Sort Key: empno, depname
+         Presorted Key: empno
+         ->  WindowAgg
+               ->  Sort
+                     Sort Key: empno
+                     ->  Seq Scan on empsalary
+(8 rows)
+
+-- Case #3: When ORDER BY contains any WindowFuncs
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       row_number() over (PARTITION BY empno) esalary
+FROM empsalary
+ORDER BY empno, esalary;
+                 QUERY PLAN                 
+--------------------------------------------
+ Incremental Sort
+   Sort Key: empno, (row_number() OVER (?))
+   Presorted Key: empno
+   ->  WindowAgg
+         ->  Sort
+               Sort Key: empno
+               ->  Seq Scan on empsalary
+(7 rows)
+
 -- Test Sort node reordering
 EXPLAIN (COSTS OFF)
 SELECT
diff --git a/src/test/regress/sql/window.sql b/src/test/regress/sql/window.sql
index b7bd0a83da..e989e93737 100644
--- a/src/test/regress/sql/window.sql
+++ b/src/test/regress/sql/window.sql
@@ -1324,8 +1324,102 @@ SELECT DISTINCT
 FROM empsalary
 ORDER BY depname, empno;
 
+-- Do not perform sort pushdown if column is presorted
+CREATE INDEX depname_idx ON empsalary(depname);
+SET enable_seqscan=0;
+
+EXPLAIN (COSTS OFF)
+SELECT empno,
+        min(salary) OVER (PARTITION BY depname) depminsalary
+FROM empsalary
+ORDER BY depname, empno;
+
+-- Do perform sort pushdown if columns are only partially sorted
+EXPLAIN (COSTS OFF)
+SELECT empno,
+        min(salary) OVER (PARTITION BY depname, empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+
+DROP INDEX depname_idx;
+RESET enable_seqscan;
 RESET enable_hashagg;
 
+-- If window function's ORDER BY is subset of QUERY's ORDER BY, sort as per as
+-- QUERY's ORDER BY to save additional sorting in the end
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (ORDER BY depname) depminsalary
+FROM empsalary
+ORDER BY depname, empno;
+
+-- Same as above, but PARTITION BY clause is included as well
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+
+-- Negation of above, when sort optimization is not needed to be performed
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY empno, enroll_date;
+
+-- ORDER BY's in multiple Window functions can be combined into one
+-- if they are subset of QUERY's ORDER BY
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary,
+       sum(salary) OVER (PARTITION BY depname) depsalary,
+       count(*) OVER (ORDER BY enroll_date DESC) c
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+
+-- order of window function shouldn't affect query's ORDER BY pushdown
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       count(*) OVER (ORDER BY enroll_date DESC) c,
+       sum(salary) OVER (PARTITION BY depname) depsalary,
+       min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+
+-- SORT OPTIMIZATION (as in cases above) is not needed to be performed
+-- in cases, as mentioned below.
+
+-- Case #1: When distinct clause is included
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT empno,
+       depname,
+       min(salary) OVER (PARTITION BY depname) depminsalary,
+       sum(salary) OVER (PARTITION BY depname) depsalary,
+       count(*) OVER (ORDER BY enroll_date DESC) c
+FROM empsalary
+ORDER BY depname, empno;
+
+-- Case #2: When Limit clause is specified
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       depname,
+       min(salary) OVER (PARTITION BY empno) depminsalary,
+       sum(salary) OVER (PARTITION BY empno) depsalary
+FROM empsalary
+ORDER BY empno, depname LIMIT 1;
+
+-- Case #3: When ORDER BY contains any WindowFuncs
+EXPLAIN (COSTS OFF)
+SELECT empno,
+       row_number() over (PARTITION BY empno) esalary
+FROM empsalary
+ORDER BY empno, esalary;
+
 -- Test Sort node reordering
 EXPLAIN (COSTS OFF)
 SELECT
-- 
2.37.2