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);