0002-opt_group_by_index_and_order-v8.patch

diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 8897157817..39f7409d75 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -380,46 +380,30 @@ group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
 	return n;
 }
 
-/*
- * Work struct from sorting pathkeys
- */
-typedef struct PathKeyNumGroup
-{
-	PathKey	   *key;
-	double		numGroups;
-	int			order; /* just to make qsort stable */
-} PathKeyNumGroup;
-
-static int
-pathkey_numgroups_cmp(const void *a, const void *b)
-{
-	const PathKeyNumGroup *pka = (const PathKeyNumGroup*)a,
-						  *pkb = (const PathKeyNumGroup*)b;
-
-	if (pka->numGroups == pkb->numGroups)
-		/* make qsort stable */
-		return (pka->order > pkb->order) ? 1 : -1;
-	return (pka->numGroups > pkb->numGroups) ? -1 : 1;
-}
-
 /*
  * Order tail of list of group pathkeys by uniqueness descendetly. It allows to
  * speedup sorting. Returns newly allocated lists, old ones stay untouched.
- * startNum defines a head of list which order should be prevented.
+ * n_preordered defines a head of list which order should be prevented.
  */
 void
 get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
 							  List *target_list,
 							  List **group_pathkeys, List **group_clauses,
-							  int startNum)
+							  int n_preordered)
 {
-	PathKeyNumGroup	   *keys;
-	int					nkeys = list_length(*group_pathkeys) - startNum;
-	List			   *pathkeyExprList,
-					   *new_group_pathkeys = NIL,
-					   *new_group_clauses = NIL;
-	ListCell		   *cell;
-	int					i = 0;
+	struct
+	{
+		PathKey			*pathkey;
+		SortGroupClause	*sgc;
+		Node			*pathkeyExpr;
+	}
+				   *keys, tmp;
+	int				nkeys = list_length(*group_pathkeys) - n_preordered;
+	List		   *pathkeyExprList = NIL,
+				   *new_group_pathkeys = NIL,
+				   *new_group_clauses = NIL;
+	ListCell	   *cell;
+	int				i = 0, n_keys_to_est;
 
 	if (nkeys < 2)
 		return; /* nothing to do */
@@ -428,48 +412,82 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
 	 * Will try to match ORDER BY pathkeys in hope that one sort is cheaper than
 	 * two
 	 */
-	if (startNum == 0 && root->sort_pathkeys)
+	if (n_preordered == 0 && root->sort_pathkeys)
 	{
-		startNum = group_keys_reorder_by_pathkeys(root->sort_pathkeys,
-												  group_pathkeys,
-												  group_clauses);
+		n_preordered = group_keys_reorder_by_pathkeys(root->sort_pathkeys,
+													  group_pathkeys,
+													  group_clauses);
 
-		nkeys = list_length(*group_pathkeys) - startNum;
+		nkeys = list_length(*group_pathkeys) - n_preordered;
 		if (nkeys < 2)
 			return; /* nothing to do */
 	}
 
 	keys = palloc(nkeys * sizeof(*keys));
-	pathkeyExprList = list_make1(NULL);
 
 	/*
-	 * for each pathkeys to be ordered we count a number of group to sort them
-	 * in descending order
+	 * Collect information about pathkey for subsequent usage
 	 */
-	for_each_cell(cell, list_nth_cell(*group_pathkeys, startNum))
+	for_each_cell(cell, list_nth_cell(*group_pathkeys, n_preordered))
 	{
 		PathKey			*pathkey = (PathKey *) lfirst(cell);
-		Node			*pathkeyExpr;
-		SortGroupClause	*sgc;
-
-		sgc = get_sortgroupref_clause(pathkey->pk_eclass->ec_sortref,
-									  *group_clauses);
-		pathkeyExpr = get_sortgroupclause_expr(sgc, target_list);
-		linitial(pathkeyExprList) = pathkeyExpr;
-		keys[i].numGroups= estimate_num_groups(root, pathkeyExprList,
-											   nrows, NULL);
-		keys[i].key = pathkey;
-		keys[i].order = i;
 
+		keys[i].pathkey = pathkey;
+		keys[i].sgc = get_sortgroupref_clause(pathkey->pk_eclass->ec_sortref,
+											  *group_clauses);
+		keys[i].pathkeyExpr = get_sortgroupclause_expr(keys[i].sgc,
+													   target_list);
 		i++;
 	}
 
-	list_free(pathkeyExprList);
+	/*
+	 * Find the cheapest to sort order of columns. We will find a first column
+	 * with bigger number of group, then pair (first column in pair is  already
+	 * defined in first step), them triple and so on.
+	 */
+	for(n_keys_to_est = 1; n_keys_to_est <= nkeys - 1; n_keys_to_est++)
+	{
+		ListCell   *tail_cell;
+		int			best_i = 0;
+		double		best_est_num_groups = -1;
 
-	qsort(keys, nkeys, sizeof(*keys), pathkey_numgroups_cmp);
+		/* expand list of columns and remeber last cell */
+		pathkeyExprList = lappend(pathkeyExprList, NULL);
+		tail_cell = list_tail(pathkeyExprList);
+
+		/*
+		 * Find the best last column - the best means bigger number of groups,
+		 * previous columns are already choosen
+		 */
+		for(i = n_keys_to_est - 1; i < nkeys; i++)
+		{
+			double  est_num_groups;
+
+			lfirst(tail_cell) = keys[i].pathkeyExpr;
+			est_num_groups = estimate_num_groups(root, pathkeyExprList,
+												 nrows, NULL);
+
+			if (est_num_groups > best_est_num_groups)
+			{
+				best_est_num_groups = est_num_groups;
+				best_i = i;
+			}
+		}
+
+		/* Save the best choice */
+		lfirst(tail_cell) = keys[best_i].pathkeyExpr;
+		if (best_i != n_keys_to_est - 1)
+		{
+			tmp = keys[n_keys_to_est - 1];
+			keys[n_keys_to_est - 1] = keys[best_i];
+			keys[best_i] = tmp;
+		}
+	}
+	list_free(pathkeyExprList);
 
 	/*
-	 * Construct result lists
+	 * Construct result lists, keys array is already ordered to get a cheapest
+	 * sort
 	 */
 	i = 0;
 	foreach(cell, *group_pathkeys)
@@ -477,17 +495,19 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
 		PathKey	   *pathkey;
 		SortGroupClause *sgc;
 
-		if (i < startNum)
-			/* presorted head */
+		if (i < n_preordered)
+		{
 			pathkey = (PathKey *) lfirst(cell);
+			sgc = get_sortgroupref_clause(pathkey->pk_eclass->ec_sortref,
+										  *group_clauses);
+		}
 		else
-			/* pathkey, sorted above */
-			pathkey = keys[i - startNum].key;
+		{
+			pathkey = keys[i - n_preordered].pathkey;
+			sgc = keys[i - n_preordered].sgc;
+		}
 
 		new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
-
-		sgc = get_sortgroupref_clause(pathkey->pk_eclass->ec_sortref,
-									  *group_clauses);
 		new_group_clauses = lappend(new_group_clauses, sgc);
 
 		i++;
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index f954790ea1..31dcf70e47 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -2071,7 +2071,8 @@ SELECT
 	i/2 AS p,
 	format('%60s', i%2) AS v,
 	i/4 AS c,
-	i/8 AS d
+	i/8 AS d,
+	(random() * (10000/8))::int as e --the same as d but no correlation with p
 	INTO btg
 FROM
 	generate_series(1, 10000) i;
@@ -2108,9 +2109,9 @@ SELECT count(*) FROM btg GROUP BY v, p, c;
          QUERY PLAN          
 -----------------------------
  GroupAggregate
-   Group Key: p, c, v
+   Group Key: p, v, c
    ->  Sort
-         Sort Key: p, c, v
+         Sort Key: p, v, c
          ->  Seq Scan on btg
 (5 rows)
 
@@ -2130,9 +2131,9 @@ SELECT count(*) FROM btg GROUP BY v, p, d, c;
           QUERY PLAN          
 ------------------------------
  GroupAggregate
-   Group Key: p, c, d, v
+   Group Key: p, v, d, c
    ->  Sort
-         Sort Key: p, c, d, v
+         Sort Key: p, v, d, c
          ->  Seq Scan on btg
 (5 rows)
 
@@ -2158,6 +2159,52 @@ SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c;
          ->  Seq Scan on btg
 (5 rows)
 
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, d, e;
+         QUERY PLAN          
+-----------------------------
+ GroupAggregate
+   Group Key: p, d, e
+   ->  Sort
+         Sort Key: p, d, e
+         ->  Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, e, d;
+         QUERY PLAN          
+-----------------------------
+ GroupAggregate
+   Group Key: p, e, d
+   ->  Sort
+         Sort Key: p, e, d
+         ->  Seq Scan on btg
+(5 rows)
+
+CREATE STATISTICS btg_dep ON d, e, p FROM btg;
+ANALYZE btg;
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, d, e;
+         QUERY PLAN          
+-----------------------------
+ GroupAggregate
+   Group Key: p, e, d
+   ->  Sort
+         Sort Key: p, e, d
+         ->  Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, e, d;
+         QUERY PLAN          
+-----------------------------
+ GroupAggregate
+   Group Key: p, e, d
+   ->  Sort
+         Sort Key: p, e, d
+         ->  Seq Scan on btg
+(5 rows)
+
 -- GROUP BY optimization by reorder columns by index scan
 CREATE INDEX ON btg(p, v);
 SET enable_seqscan=off;
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index adecec8872..a686a75fb0 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -244,9 +244,9 @@ EXPLAIN (COSTS off)
             QUERY PLAN             
 -----------------------------------
  GroupAggregate
-   Group Key: a, b, c, d
+   Group Key: a, d, c, b
    ->  Sort
-         Sort Key: a, b, c, d
+         Sort Key: a, d, c, b
          ->  Seq Scan on ndistinct
 (5 rows)
 
@@ -255,9 +255,9 @@ EXPLAIN (COSTS off)
             QUERY PLAN             
 -----------------------------------
  GroupAggregate
-   Group Key: b, c, d
+   Group Key: b, d, c
    ->  Sort
-         Sort Key: b, c, d
+         Sort Key: b, d, c
          ->  Seq Scan on ndistinct
 (5 rows)
 
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index 061e3360c0..e4415c8d84 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -915,7 +915,8 @@ SELECT
 	i/2 AS p,
 	format('%60s', i%2) AS v,
 	i/4 AS c,
-	i/8 AS d
+	i/8 AS d,
+	(random() * (10000/8))::int as e --the same as d but no correlation with p
 	INTO btg
 FROM
 	generate_series(1, 10000) i;
@@ -950,6 +951,22 @@ SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY v, p, d ,c;
 EXPLAIN (COSTS off)
 SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c;
 
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, d, e;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, e, d;
+
+CREATE STATISTICS btg_dep ON d, e, p FROM btg;
+ANALYZE btg;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, d, e;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, e, d;
+
+
 -- GROUP BY optimization by reorder columns by index scan
 
 CREATE INDEX ON btg(p, v);