diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 4f93afdebc..8897157817 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -380,6 +380,128 @@ 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. + */ +void +get_cheapest_group_keys_order(PlannerInfo *root, double nrows, + List *target_list, + List **group_pathkeys, List **group_clauses, + int startNum) +{ + PathKeyNumGroup *keys; + int nkeys = list_length(*group_pathkeys) - startNum; + List *pathkeyExprList, + *new_group_pathkeys = NIL, + *new_group_clauses = NIL; + ListCell *cell; + int i = 0; + + if (nkeys < 2) + return; /* nothing to do */ + + /* + * Will try to match ORDER BY pathkeys in hope that one sort is cheaper than + * two + */ + if (startNum == 0 && root->sort_pathkeys) + { + startNum = group_keys_reorder_by_pathkeys(root->sort_pathkeys, + group_pathkeys, + group_clauses); + + nkeys = list_length(*group_pathkeys) - startNum; + 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 + */ + for_each_cell(cell, list_nth_cell(*group_pathkeys, startNum)) + { + 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; + + i++; + } + + list_free(pathkeyExprList); + + qsort(keys, nkeys, sizeof(*keys), pathkey_numgroups_cmp); + + /* + * Construct result lists + */ + i = 0; + foreach(cell, *group_pathkeys) + { + PathKey *pathkey; + SortGroupClause *sgc; + + if (i < startNum) + /* presorted head */ + pathkey = (PathKey *) lfirst(cell); + else + /* pathkey, sorted above */ + pathkey = keys[i - startNum].key; + + 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++; + } + + pfree(keys); + + /* Just append the rest GROUP BY clauses */ + new_group_clauses = list_concat_unique_ptr(new_group_clauses, *group_clauses); + + *group_pathkeys = new_group_pathkeys; + *group_clauses = new_group_clauses; +} + /* * get_cheapest_path_for_pathkeys * Find the cheapest path (according to the specified criterion) that diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 1e7809edf2..257aa5889c 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -6208,11 +6208,20 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, { /* Sort the cheapest-total path if it isn't already sorted */ if (!is_sorted) + { + if (!parse->groupingSets) + get_cheapest_group_keys_order(root, + path->rows, + extra->targetList, + &group_pathkeys, + &group_clauses, + n_preordered_groups); path = (Path *) create_sort_path(root, grouped_rel, path, group_pathkeys, -1.0); + } /* Now decide what to stick atop it */ if (parse->groupingSets) @@ -6286,6 +6295,12 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, { if (path != partially_grouped_rel->cheapest_total_path) continue; + get_cheapest_group_keys_order(root, + path->rows, + extra->targetList, + &group_pathkeys, + &group_clauses, + n_preordered_groups); path = (Path *) create_sort_path(root, grouped_rel, path, @@ -6560,11 +6575,19 @@ create_partial_grouping_paths(PlannerInfo *root, { /* Sort the cheapest partial path, if it isn't already */ if (!is_sorted) + { + get_cheapest_group_keys_order(root, + path->rows, + extra->targetList, + &group_pathkeys, + &group_clauses, + n_preordered_groups); path = (Path *) create_sort_path(root, partially_grouped_rel, path, group_pathkeys, -1.0); + } if (parse->hasAggs) add_path(partially_grouped_rel, (Path *) @@ -6611,11 +6634,19 @@ create_partial_grouping_paths(PlannerInfo *root, /* Sort the cheapest partial path, if it isn't already */ if (!is_sorted) + { + get_cheapest_group_keys_order(root, + path->rows, + extra->targetList, + &group_pathkeys, + &group_clauses, + n_preordered_groups); path = (Path *) create_sort_path(root, partially_grouped_rel, path, group_pathkeys, -1.0); + } if (parse->hasAggs) add_partial_path(partially_grouped_rel, (Path *) diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 226b293622..c52a7c6133 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -193,6 +193,12 @@ extern bool pathkeys_contained_in(List *keys1, List *keys2); extern int group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys, List **group_clauses); +extern void get_cheapest_group_keys_order(PlannerInfo *root, + double nrows, + List *target_list, + List **group_pathkeys, + List **group_clauses, + int n_preordered); extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out index e302dfbdce..f954790ea1 100644 --- a/src/test/regress/expected/aggregates.out +++ b/src/test/regress/expected/aggregates.out @@ -2075,15 +2075,94 @@ SELECT INTO btg FROM generate_series(1, 10000) i; -CREATE INDEX ON btg(p, v); VACUUM btg; ANALYZE btg; +-- GROUP BY optimization by reorder columns by frequency SET enable_hashagg=off; SET max_parallel_workers= 0; SET max_parallel_workers_per_gather = 0; +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, v + -> Sort + Sort Key: p, v + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, v + -> Sort + Sort Key: p, v + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, c, v + -> Sort + Sort Key: p, c, v + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY v, p, c; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: v, p, c + -> Sort + Sort Key: v, p, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: p, c, d, v + -> Sort + Sort Key: p, c, d, v + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY v, p, d ,c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: v, p, d, c + -> Sort + Sort Key: v, p, d, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: p, v, d, c + -> Sort + Sort Key: p, v, d, c + -> 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; SET enable_bitmapscan=off; --- GROUP BY optimization by reorder columns by index scan +VACUUM btg; EXPLAIN (COSTS off) SELECT count(*) FROM btg GROUP BY p, v; QUERY PLAN diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out index b983f9c506..3915a837f0 100644 --- a/src/test/regress/expected/partition_join.out +++ b/src/test/regress/expected/partition_join.out @@ -1140,7 +1140,7 @@ SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, pl QUERY PLAN -------------------------------------------------------------------------------- GroupAggregate - Group Key: t1.c, t2.c, t3.c + Group Key: t1.c, t3.c, t2.c -> Sort Sort Key: t1.c, t3.c -> Append @@ -1284,7 +1284,7 @@ SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, ph QUERY PLAN -------------------------------------------------------------------------------- GroupAggregate - Group Key: t1.c, t2.c, t3.c + Group Key: t1.c, t3.c, t2.c -> Sort Sort Key: t1.c, t3.c -> Append diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out index 054a381dad..adecec8872 100644 --- a/src/test/regress/expected/stats_ext.out +++ b/src/test/regress/expected/stats_ext.out @@ -281,9 +281,9 @@ EXPLAIN (COSTS off) QUERY PLAN ----------------------------------- GroupAggregate - Group Key: a, b + Group Key: b, a -> Sort - Sort Key: a, b + Sort Key: b, a -> Seq Scan on ndistinct (5 rows) @@ -292,9 +292,9 @@ EXPLAIN (COSTS off) QUERY PLAN ----------------------------------- GroupAggregate - Group Key: a, b, c + Group Key: b, a, c -> Sort - Sort Key: a, b, c + Sort Key: b, a, c -> Seq Scan on ndistinct (5 rows) @@ -303,9 +303,9 @@ EXPLAIN (COSTS off) QUERY PLAN ----------------------------------- GroupAggregate - Group Key: a, b, c, d + Group Key: d, b, a, c -> Sort - Sort Key: a, b, c, d + Sort Key: d, b, a, c -> Seq Scan on ndistinct (5 rows) diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql index 7ef703f3a7..061e3360c0 100644 --- a/src/test/regress/sql/aggregates.sql +++ b/src/test/regress/sql/aggregates.sql @@ -919,18 +919,44 @@ SELECT INTO btg FROM generate_series(1, 10000) i; -CREATE INDEX ON btg(p, v); VACUUM btg; ANALYZE btg; +-- GROUP BY optimization by reorder columns by frequency + SET enable_hashagg=off; SET max_parallel_workers= 0; SET max_parallel_workers_per_gather = 0; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY v, p, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c; + +EXPLAIN (COSTS off) +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; + +-- GROUP BY optimization by reorder columns by index scan + +CREATE INDEX ON btg(p, v); SET enable_seqscan=off; SET enable_bitmapscan=off; +VACUUM btg; --- GROUP BY optimization by reorder columns by index scan EXPLAIN (COSTS off) SELECT count(*) FROM btg GROUP BY p, v;