problem 2). Index optimization was noticed by me later. But based on your
suggested patch's order I split the patch to index and non-index part and
second part depends of first one. They touch the same part of code and they
could not be independent
The way I see it the patch does two different things:
Yes
a) consider additional indexes by relaxing the pathkeys check
Yes, but not only. Patch could reorder GROUP BY clause to match existing
pathkeys which could come from index scan (suggested by patch or not) or some
another way to get ordered output.
b) if there are no indexes, i.e. when an explicit Sort is needed, consider
reordering the columns by ndistinct
Yes. But again, this description is a bit short. First it works after first
patch and might get some preordered leading pathkeys. Second, it tries to match
ORDER BY clause order if there is no preordered leading pathkeys from first
patch (it was introduced in v7). And third, if there is a tail of unmatched
pathkeys on previous stages then it will reorder that tail.
In the worst case, one part will depend on the other, which is OK. It still
allows us to commit the first part and continue working on the other one, for
example.
Exactly it's our case. Of course, it's possible to split first patch for two
again: just suggestion of index (1.1) and reordering by existing pathkeys (1.2).
Then 1.1 will be independent but 2 still should be applied after 1.2. But patch
1.1 is rather useless.
can decide which one is cheaper etc. The decision which paths to keep is done by
add_path(), and it should stay like this, of course. I wasn't suggesting to move
the logic elsewhere.
Cool, I haven't intention to modify it too.
> I wonder if we should make the add_path() logic smarter to recognize when two
> paths have different pathkeys but were generated to match the same grouping,
> to reduce the number of paths added by this optimization. Currently we do
that > for each pathkeys list independently, but we're considering many more
pathkeys > orderings ...
Hm. I tend to say no.
select .. from t1 group by a, b
union
select .. from t2 group by a, b
t1 and t2 could have different set of indexes and different distribution, so
locally it could be cheaper to use one index (for example, one defined as (b,
a) and second as (a,b,c,d) - second is larger) but totally - another (example:
second table doesn't have (b,a) index)
But add_path() treats each of the relations independently, why couldn't we pick
a different index for each of the two relations?
Having of sorted output of both subselect could be cheaper that sorting one of
them even if index scan was cheaper. But it seems to me that is not deal of
suggested here optimization.
For example, it seems to disregard that different data types have different
comparison costs. For example comparing bytea will be far more expensive
compared to int4, so it may be much more efficient to compare int4 columns
first, even if there are far fewer distinct values in them.
as I can see cost_sort() doesn't pay attention to this details. And it should
be a separated patch to improve that.
But sort also does not reorder columns.
Yes. But estimation of cost of comparing function/number of unique values in
column could be not very accurate and so planner could make a wrong choice. I
saw 2 times difference in real-world application. Again, improving sort cost
estimation is a separate task.
Imagine you have a custom data type that is expensive for comparisons. You know
that, so you place it at the end of GROUP BY clauses, to reduce the number of
comparisons on that field. And then we come along and just reorder the columns,
placing it first, because it happens to have a high ndistinct statistic. And
there's no way to get the original behavior :-(
Hm. that it could be, but I don't know how to improve here. Current cost_sort()
will return the same cost for any columns order.
Okay, here we know an estimation of nrow, we could somehow find a comparing
function oid and find a its procost field. And then? we also need to know width
of tuple here and mostly repeat the cost_sort.
Another option is an introducing enable_groupby_reorder GUC variable although
personally I don't like an idea to add new GUC variable.
Agree, but I don't know how to use it here. Except, may be:
1) first column - the column with bigger estimated number of groups
2) second column - the pair of (first, second) with bigger estimated number of
groups
3) third column - the triple of (first, second, third) with bigger ...
But seems even with that algorithm, ISTM, it could be implemented in cheaper
manner.
Maybe. I do have some ideas, although I haven't tried implementing it.
Implemented, pls, have a look.
If there's no extended statistic on the columns, you can do the current thing
(assuming independence etc.). There's not much we can do here.
Agree
If there's an extended statistic, you can do either a greedy search (get the
next column with the highest ndistinct coefficient) or exhaustive search
(computing the estimated number of comparisons).
Another challenge is that using only the ndistinct coefficient assumes uniform
distribution of the values. But you can have a column with 1M distinct values,
where a single value represents 99% of the rows. And another column with 100k
distinct values, with actual uniform distribution. I'm pretty sure it'd be more
efficient to place the 100k column first.
Interesting. Will think, thank you
--
Teodor Sigaev E-mail: teo...@sigaev.ru
WWW: http://www.sigaev.ru/
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index b22b36ec0e..c073eb061a 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -686,7 +686,18 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (opcintype == cur_em->em_datatype &&
equal(expr, cur_em->em_expr))
- return cur_ec; /* Match! */
+ {
+ /*
+ * Match!
+ *
+ * Copy sortref if it wasn't set yet, it's possible if ec was
+ * constructed from WHERE clause, ie it doesn't have target
+ * reference at all
+ */
+ if (cur_ec->ec_sortref == 0 && sortref > 0)
+ cur_ec->ec_sortref = sortref;
+ return cur_ec;
+ }
}
}
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index ec66cb9c3c..4f93afdebc 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -26,6 +26,7 @@
#include "optimizer/paths.h"
#include "optimizer/tlist.h"
#include "utils/lsyscache.h"
+#include "utils/selfuncs.h"
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
@@ -327,6 +328,58 @@ pathkeys_contained_in(List *keys1, List *keys2)
return false;
}
+/*
+ * Reorder GROUP BY pathkeys and clauses to match order of pathkeys. Function
+ * returns new lists, original GROUP BY lists stay untouched.
+ */
+int
+group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
+ List **group_clauses)
+{
+ List *new_group_pathkeys= NIL,
+ *new_group_clauses = NIL;
+ ListCell *key;
+ int n;
+
+ if (pathkeys == NIL || *group_pathkeys == NIL)
+ return 0;
+
+ /*
+ * For each pathkey it tries to find corresponding GROUP BY pathkey and
+ * clause.
+ */
+ foreach(key, pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(key);
+ SortGroupClause *sgc;
+
+ /*
+ * Pathkey should use the same allocated struct, so, equiality of
+ * pointers is enough
+ */
+ if (!list_member_ptr(*group_pathkeys, pathkey))
+ break;
+
+ 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);
+ }
+
+ n = list_length(new_group_pathkeys);
+
+ /*
+ * Just append the rest of pathkeys and clauses
+ */
+ *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
+ *group_pathkeys);
+ *group_clauses = list_concat_unique_ptr(new_group_clauses,
+ *group_clauses);
+
+ return n;
+}
+
/*
* get_cheapest_path_for_pathkeys
* Find the cheapest path (according to the specified criterion) that
@@ -1611,6 +1664,39 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
return 0; /* path ordering not useful */
}
+/*
+ * pathkeys_useful_for_grouping
+ * Count the number of pathkeys that are useful for grouping (instead of
+ * explicit sort)
+ *
+ * Group pathkeys could be reordered, so we don't bother about actual order in
+ * pathkeys
+ */
+static int
+pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
+{
+ ListCell *key;
+ int n = 0;
+
+ if (root->group_pathkeys == NIL)
+ return 0; /* no special ordering requested */
+
+ if (pathkeys == NIL)
+ return 0; /* unordered path */
+
+ foreach(key, pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(key);
+
+ if (!list_member_ptr(root->group_pathkeys, pathkey))
+ break;
+
+ n++;
+ }
+
+ return n;
+}
+
/*
* truncate_useless_pathkeys
* Shorten the given pathkey list to just the useful pathkeys.
@@ -1625,6 +1711,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
+ if (nuseful2 > nuseful)
+ nuseful = nuseful2;
+ nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
if (nuseful2 > nuseful)
nuseful = nuseful2;
@@ -1660,6 +1749,8 @@ has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
{
if (rel->joininfo != NIL || rel->has_eclass_joins)
return true; /* might be able to use pathkeys for merging */
+ if (root->group_pathkeys != NIL)
+ return true; /* might be able to use pathkeys for grouping */
if (root->query_pathkeys != NIL)
return true; /* might be able to use them for ordering */
return false; /* definitely useless */
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 67a2c7a581..1e7809edf2 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6182,9 +6182,28 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *path = (Path *) lfirst(lc);
bool is_sorted;
+ List *group_pathkeys = root->group_pathkeys,
+ *group_clauses = parse->groupClause;
+ int n_preordered_groups;
+
+ if (parse->groupingSets)
+ {
+ /*
+ * prevent group pathkey rreordering, just check the same
+ * order paths pathkeys and group pathkeys
+ */
+ is_sorted = pathkeys_contained_in(group_pathkeys,
+ path->pathkeys);
+ }
+ else
+ {
+ n_preordered_groups =
+ group_keys_reorder_by_pathkeys(path->pathkeys,
+ &group_pathkeys,
+ &group_clauses);
+ is_sorted = (n_preordered_groups == list_length(group_pathkeys));
+ }
- is_sorted = pathkeys_contained_in(root->group_pathkeys,
- path->pathkeys);
if (path == cheapest_path || is_sorted)
{
/* Sort the cheapest-total path if it isn't already sorted */
@@ -6192,7 +6211,7 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
path = (Path *) create_sort_path(root,
grouped_rel,
path,
- root->group_pathkeys,
+ group_pathkeys,
-1.0);
/* Now decide what to stick atop it */
@@ -6213,9 +6232,9 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ group_clauses ? AGG_SORTED : AGG_PLAIN,
AGGSPLIT_SIMPLE,
- parse->groupClause,
+ group_clauses,
havingQual,
agg_costs,
dNumGroups));
@@ -6230,7 +6249,7 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
create_group_path(root,
grouped_rel,
path,
- parse->groupClause,
+ group_clauses,
havingQual,
dNumGroups));
}
@@ -6251,19 +6270,26 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
foreach(lc, partially_grouped_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
+ List *group_pathkeys = root->group_pathkeys,
+ *group_clauses = parse->groupClause;
+ int n_preordered_groups;
+
+ n_preordered_groups = group_keys_reorder_by_pathkeys(path->pathkeys,
+ &group_pathkeys,
+ &group_clauses);
/*
* Insert a Sort node, if required. But there's no point in
* sorting anything but the cheapest path.
*/
- if (!pathkeys_contained_in(root->group_pathkeys, path->pathkeys))
+ if (n_preordered_groups != list_length(group_pathkeys))
{
if (path != partially_grouped_rel->cheapest_total_path)
continue;
path = (Path *) create_sort_path(root,
grouped_rel,
path,
- root->group_pathkeys,
+ group_pathkeys,
-1.0);
}
@@ -6273,9 +6299,9 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ group_clauses ? AGG_SORTED : AGG_PLAIN,
AGGSPLIT_FINAL_DESERIAL,
- parse->groupClause,
+ group_clauses,
havingQual,
agg_final_costs,
dNumGroups));
@@ -6284,7 +6310,7 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
create_group_path(root,
grouped_rel,
path,
- parse->groupClause,
+ group_clauses,
havingQual,
dNumGroups));
}
@@ -6521,9 +6547,15 @@ create_partial_grouping_paths(PlannerInfo *root,
{
Path *path = (Path *) lfirst(lc);
bool is_sorted;
+ List *group_pathkeys = root->group_pathkeys,
+ *group_clauses = parse->groupClause;
+ int n_preordered_groups;
+
+ n_preordered_groups = group_keys_reorder_by_pathkeys(path->pathkeys,
+ &group_pathkeys,
+ &group_clauses);
+ is_sorted = (n_preordered_groups == list_length(group_pathkeys));
- is_sorted = pathkeys_contained_in(root->group_pathkeys,
- path->pathkeys);
if (path == cheapest_total_path || is_sorted)
{
/* Sort the cheapest partial path, if it isn't already */
@@ -6531,7 +6563,7 @@ create_partial_grouping_paths(PlannerInfo *root,
path = (Path *) create_sort_path(root,
partially_grouped_rel,
path,
- root->group_pathkeys,
+ group_pathkeys,
-1.0);
if (parse->hasAggs)
@@ -6540,9 +6572,9 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ group_clauses ? AGG_SORTED : AGG_PLAIN,
AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
+ group_clauses,
NIL,
agg_partial_costs,
dNumPartialGroups));
@@ -6551,7 +6583,7 @@ create_partial_grouping_paths(PlannerInfo *root,
create_group_path(root,
partially_grouped_rel,
path,
- parse->groupClause,
+ group_clauses,
NIL,
dNumPartialGroups));
}
@@ -6565,17 +6597,24 @@ create_partial_grouping_paths(PlannerInfo *root,
{
Path *path = (Path *) lfirst(lc);
bool is_sorted;
+ List *group_pathkeys = root->group_pathkeys,
+ *group_clauses = parse->groupClause;
+ int n_preordered_groups;
+
+ n_preordered_groups = group_keys_reorder_by_pathkeys(path->pathkeys,
+ &group_pathkeys,
+ &group_clauses);
+ is_sorted = (n_preordered_groups == list_length(group_pathkeys));
- is_sorted = pathkeys_contained_in(root->group_pathkeys,
- path->pathkeys);
if (path == cheapest_partial_path || is_sorted)
{
+
/* Sort the cheapest partial path, if it isn't already */
if (!is_sorted)
path = (Path *) create_sort_path(root,
partially_grouped_rel,
path,
- root->group_pathkeys,
+ group_pathkeys,
-1.0);
if (parse->hasAggs)
@@ -6584,9 +6623,9 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ group_clauses ? AGG_SORTED : AGG_PLAIN,
AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
+ group_clauses,
NIL,
agg_partial_costs,
dNumPartialPartialGroups));
@@ -6595,7 +6634,7 @@ create_partial_grouping_paths(PlannerInfo *root,
create_group_path(root,
partially_grouped_rel,
path,
- parse->groupClause,
+ group_clauses,
NIL,
dNumPartialPartialGroups));
}
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index cafde307ad..226b293622 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -190,6 +190,9 @@ typedef enum
extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
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 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 f85e913850..e302dfbdce 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -2065,3 +2065,107 @@ SELECT balk(hundred) FROM tenk1;
(1 row)
ROLLBACK;
+-- GROUP BY optimization by reorder columns
+SELECT
+ i AS id,
+ i/2 AS p,
+ format('%60s', i%2) AS v,
+ i/4 AS c,
+ i/8 AS d
+ INTO btg
+FROM
+ generate_series(1, 10000) i;
+CREATE INDEX ON btg(p, v);
+VACUUM btg;
+ANALYZE btg;
+SET enable_hashagg=off;
+SET max_parallel_workers= 0;
+SET max_parallel_workers_per_gather = 0;
+SET enable_seqscan=off;
+SET enable_bitmapscan=off;
+-- GROUP BY optimization by reorder columns by index scan
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v;
+ QUERY PLAN
+------------------------------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Index Only Scan using btg_p_v_idx on btg
+(3 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v ORDER BY p, v;
+ QUERY PLAN
+------------------------------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Index Only Scan using btg_p_v_idx on btg
+(3 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p;
+ QUERY PLAN
+------------------------------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Index Only Scan using btg_p_v_idx on btg
+(3 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p ORDER BY p, v;
+ QUERY PLAN
+------------------------------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Index Only Scan using btg_p_v_idx on btg
+(3 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c;
+ QUERY PLAN
+-------------------------------------------------
+ GroupAggregate
+ Group Key: p, v, c
+ -> Sort
+ Sort Key: p, v, c
+ -> Index Scan using btg_p_v_idx on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY p, v;
+ QUERY PLAN
+-------------------------------------------------
+ GroupAggregate
+ Group Key: p, v, c
+ -> Sort
+ Sort Key: p, v, c
+ -> Index Scan using btg_p_v_idx on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, c, p, d;
+ QUERY PLAN
+-------------------------------------------------
+ GroupAggregate
+ Group Key: p, v, c, d
+ -> Sort
+ Sort Key: p, v, c, d
+ -> Index Scan using btg_p_v_idx on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, c, p, d ORDER BY p, v;
+ QUERY PLAN
+-------------------------------------------------
+ GroupAggregate
+ Group Key: p, v, c, d
+ -> Sort
+ Sort Key: p, v, c, d
+ -> Index Scan using btg_p_v_idx on btg
+(5 rows)
+
+RESET enable_hashagg;
+RESET max_parallel_workers;
+RESET max_parallel_workers_per_gather;
+RESET enable_seqscan;
+RESET enable_bitmapscan;
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index 506d0442d7..7ef703f3a7 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -907,3 +907,57 @@ EXPLAIN (COSTS OFF) SELECT balk(hundred) FROM tenk1;
SELECT balk(hundred) FROM tenk1;
ROLLBACK;
+
+-- GROUP BY optimization by reorder columns
+
+SELECT
+ i AS id,
+ i/2 AS p,
+ format('%60s', i%2) AS v,
+ i/4 AS c,
+ i/8 AS d
+ INTO btg
+FROM
+ generate_series(1, 10000) i;
+CREATE INDEX ON btg(p, v);
+
+VACUUM btg;
+ANALYZE btg;
+
+SET enable_hashagg=off;
+SET max_parallel_workers= 0;
+SET max_parallel_workers_per_gather = 0;
+SET enable_seqscan=off;
+SET enable_bitmapscan=off;
+
+-- GROUP BY optimization by reorder columns by index scan
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v ORDER 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 ORDER BY p, v;
+
+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 p, v;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, c, p, d;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, c, p, d ORDER BY p, v;
+
+RESET enable_hashagg;
+RESET max_parallel_workers;
+RESET max_parallel_workers_per_gather;
+RESET enable_seqscan;
+RESET enable_bitmapscan;
+
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);
