window_prefix_sort.patch

From eba463f191d59485225f38b56d0597d750417957 Mon Sep 17 00:00:00 2001
From: Daniel Gustafsson <daniel@yesql.se>
Date: Wed, 30 May 2018 10:16:23 -0400
Subject: [PATCH] Order windows on partition/ordering prefix to reuse Sort
 nodes

By ordering the Windows on partitioning/ordering prefix, the result
from Sort nodes can be reused by multiple WindowAgg nodes and thus
we can avoid Sort nodes.
---
 src/backend/optimizer/plan/planner.c | 81 +++++++++++++++++++++---------------
 1 file changed, 47 insertions(+), 34 deletions(-)

diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 67a2c7a581..4431d0c2a9 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -237,6 +237,8 @@ static void create_partitionwise_grouping_paths(PlannerInfo *root,
 static bool group_by_has_partkey(RelOptInfo *input_rel,
 					 List *targetList,
 					 List *groupClause);
+static int common_prefix_cmp(const void *a, const void *b);
+
 
 
 /*****************************************************************************
@@ -5251,7 +5253,6 @@ postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
 static List *
 select_active_windows(PlannerInfo *root, WindowFuncLists *wflists)
 {
-	List	   *result;
 	List	   *actives;
 	ListCell   *lc;
 
@@ -5273,43 +5274,55 @@ select_active_windows(PlannerInfo *root, WindowFuncLists *wflists)
 	 * says that only one sort is to be used for such windows, even if they
 	 * are otherwise distinct (eg, different names or framing clauses).
 	 *
-	 * There is room to be much smarter here, for example detecting whether
-	 * one window's sort keys are a prefix of another's (so that sorting for
-	 * the latter would do for the former), or putting windows first that
-	 * match a sort order available for the underlying query.  For the moment
-	 * we are content with meeting the spec.
-	 */
-	result = NIL;
-	while (actives != NIL)
-	{
-		WindowClause *wc = linitial_node(WindowClause, actives);
-		ListCell   *prev;
-		ListCell   *next;
-
-		/* Move wc from actives to result */
-		actives = list_delete_first(actives);
-		result = lappend(result, wc);
+	 * Also sort windows by partitioning/ordering prefixes where the sorting
+	 * required for a window will cover the sorting required for another
+	 * window, thus reducing the number of Sort nodes.
+	 */
+	if (list_length(actives) > 1)
+		actives = list_qsort(actives, common_prefix_cmp);
 
-		/* Now move any matching windows from actives to result */
-		prev = NULL;
-		for (lc = list_head(actives); lc; lc = next)
-		{
-			WindowClause *wc2 = lfirst_node(WindowClause, lc);
+	return actives;
+}
 
-			next = lnext(lc);
-			/* framing options are NOT to be compared here! */
-			if (equal(wc->partitionClause, wc2->partitionClause) &&
-				equal(wc->orderClause, wc2->orderClause))
-			{
-				actives = list_delete_cell(actives, lc, prev);
-				result = lappend(result, wc2);
-			}
-			else
-				prev = lc;
-		}
+static int
+common_prefix_cmp(const void *a, const void *b)
+{
+	WindowClause *wca = (WindowClause *) lfirst(*(ListCell **) a);
+	WindowClause *wcb = (WindowClause *) lfirst(*(ListCell **) b);
+	List *aa = NIL;
+	List *bb = NIL;
+	ListCell *item_a;
+	ListCell *item_b;
+	int lla;
+	int llb;
+
+	aa = list_concat_unique(list_copy(wca->partitionClause), wca->orderClause);
+	bb = list_concat_unique(list_copy(wcb->partitionClause), wcb->orderClause);
+
+	forboth(item_a, aa, item_b, bb)
+	{
+		SortGroupClause *sca = lfirst(item_a);
+		SortGroupClause *scb = lfirst(item_b);
+
+		if (sca->tleSortGroupRef < scb->tleSortGroupRef)
+			return -1;
+		else if (sca->tleSortGroupRef > scb->tleSortGroupRef)
+			return 1;
+		else if (sca->sortop < scb->sortop)
+			return -1;
+		else if (sca->sortop > scb->sortop)
+			return 1;
 	}
 
-	return result;
+	lla = list_length(aa);
+	llb = list_length(bb);
+
+	if (lla < llb)
+		return -1;
+	else if (lla > llb)
+		return 1;
+
+	return 0;
 }
 
 /*
-- 
2.14.1.145.gb3622a4ee