public inbox for [email protected]
help / color / mirror / Atom feedFrom: Andrey V. Lepikhov <[email protected]>
To: Tomas Vondra <[email protected]>
Cc: PostgreSQL-development <[email protected]>
Subject: Re: POC: GROUP BY optimization
Date: Tue, 28 Dec 2021 13:47:35 +0500
Message-ID: <[email protected]> (raw)
In-Reply-To: <20200902161201.ogkjrpf232a7htn3@development>
References: <CA+q6zcW_4o2NC0zutLkOJPsFt80megSpX_dVRo6GK9PC-Jx_Ag@mail.gmail.com>
<20200901210743.lutgvnfzntvhuban@development>
<CAH2-WzmcsdeU0gMXmwT+kwPUwhnyPYfk5E+xDVb0N=13pU+fLg@mail.gmail.com>
<20200902161201.ogkjrpf232a7htn3@development>
On 9/2/20 9:12 PM, Tomas Vondra wrote:
> We could simply use the input "tuples" value here, and then divide the
> current and previous estimate to calculate the number of new groups.
Performing a review of this patch I made a number of changes (see
cleanup.txt). Maybe it will be useful.
As I see, the code, which implements the main idea, is quite stable.
Doubts localized in the cost estimation routine. Maybe try to finish
this work by implementing an conservative strategy to a cost estimation
of sorting?
--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index e617e2ce0e..211ae66b33 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1865,7 +1865,7 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
*
* For multi-column sorts we need to estimate the number of comparisons for
* each individual column - for example with columns (c1, c2, ..., ck) we
- * can estimate that number of comparions on ck is roughly
+ * can estimate that number of comparisons on ck is roughly
*
* ncomparisons(c1, c2, ..., ck) / ncomparisons(c1, c2, ..., c(k-1))
*
@@ -1874,10 +1874,10 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
*
* N * sum( Fk * log(Gk) )
*
- * Note: We also consider column witdth, not just the comparator cost.
+ * Note: We also consider column width, not just the comparator cost.
*
* NOTE: some callers currently pass NIL for pathkeys because they
- * can't conveniently supply the sort keys. In this case, it will fallback to
+ * can't conveniently supply the sort keys. In this case, it will fallback to
* simple comparison cost estimate.
*/
static Cost
@@ -1925,13 +1925,13 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
*/
foreach(lc, pathkeys)
{
- PathKey *pathkey = (PathKey*)lfirst(lc);
+ PathKey *pathkey = (PathKey*) lfirst(lc);
EquivalenceMember *em;
double nGroups,
correctedNGroups;
/*
- * We believe than equivalence members aren't very different, so, to
+ * We believe than equivalence members aren't very different, so, to
* estimate cost we take just first member
*/
em = (EquivalenceMember *) linitial(pathkey->pk_eclass->ec_members);
@@ -1964,7 +1964,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
totalFuncCost += funcCost;
- /* remeber if we have a fake var in pathkeys */
+ /* Remember if we have a fake var in pathkeys */
has_fake_var |= is_fake_var(em->em_expr);
pathkeyExprs = lappend(pathkeyExprs, em->em_expr);
@@ -1974,7 +1974,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
*/
if (has_fake_var == false)
/*
- * Recursively compute number of group in group from previous step
+ * Recursively compute number of groups in a group from previous step
*/
nGroups = estimate_num_groups_incremental(root, pathkeyExprs,
tuplesPerPrevGroup, NULL, NULL,
@@ -1992,8 +1992,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
*
* XXX What's the logic of the following formula?
*/
- nGroups = ceil(2.0 + sqrt(tuples) *
- list_length(pathkeyExprs) / list_length(pathkeys));
+ nGroups = ceil(2.0 + sqrt(tuples) * (i + 1) / list_length(pathkeys));
else
nGroups = tuples;
@@ -2033,7 +2032,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
/*
* We could skip all following columns for cost estimation, because we
- * believe that tuples are unique by set ot previous columns
+ * believe that tuples are unique by the set of previous columns
*/
if (tuplesPerPrevGroup <= 1.0)
break;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 82831a4fa4..707b5ba75b 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -544,9 +544,10 @@ PathkeyMutatorNext(PathkeyMutatorState *state)
return state->elemsList;
}
-typedef struct {
- Cost cost;
- PathKey *pathkey;
+typedef struct PathkeySortCost
+{
+ Cost cost;
+ PathKey *pathkey;
} PathkeySortCost;
static int
@@ -793,7 +794,7 @@ get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
* more complex logic to decide the ordering.
*
* XXX Isn't this somewhat redundant with presorted_keys? Actually, it's
- * more a complement, because it allows benefinting from incremental sort
+ * more a complement, because it allows benefiting from incremental sort
* as much as possible.
*
* XXX This does nothing if (n_preordered == 0). We shouldn't create the
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 7a89cee879..f281a23bb7 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6158,7 +6158,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
{
ListCell *lc2;
Path *path = (Path *) lfirst(lc);
- Path *path_save = path;
Path *path_original = path;
List *pathkey_orderings = NIL;
@@ -6182,9 +6181,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
int presorted_keys = 0;
PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2);
- /* restore the path (we replace it in the loop) */
- path = path_save;
-
is_sorted = pathkeys_count_contained_in(info->pathkeys,
path->pathkeys,
&presorted_keys);
@@ -6653,7 +6649,6 @@ create_partial_grouping_paths(PlannerInfo *root,
{
ListCell *lc2;
Path *path = (Path *) lfirst(lc);
- Path *path_save = path;
List *pathkey_orderings = NIL;
@@ -6676,9 +6671,6 @@ create_partial_grouping_paths(PlannerInfo *root,
int presorted_keys = 0;
PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2);
- /* restore the path (we replace it in the loop) */
- path = path_save;
-
is_sorted = pathkeys_count_contained_in(info->pathkeys,
path->pathkeys,
&presorted_keys);
Attachments:
[text/plain] cleanup.txt (5.5K, ../[email protected]/2-cleanup.txt)
download | inline diff:
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index e617e2ce0e..211ae66b33 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1865,7 +1865,7 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
*
* For multi-column sorts we need to estimate the number of comparisons for
* each individual column - for example with columns (c1, c2, ..., ck) we
- * can estimate that number of comparions on ck is roughly
+ * can estimate that number of comparisons on ck is roughly
*
* ncomparisons(c1, c2, ..., ck) / ncomparisons(c1, c2, ..., c(k-1))
*
@@ -1874,10 +1874,10 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
*
* N * sum( Fk * log(Gk) )
*
- * Note: We also consider column witdth, not just the comparator cost.
+ * Note: We also consider column width, not just the comparator cost.
*
* NOTE: some callers currently pass NIL for pathkeys because they
- * can't conveniently supply the sort keys. In this case, it will fallback to
+ * can't conveniently supply the sort keys. In this case, it will fallback to
* simple comparison cost estimate.
*/
static Cost
@@ -1925,13 +1925,13 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
*/
foreach(lc, pathkeys)
{
- PathKey *pathkey = (PathKey*)lfirst(lc);
+ PathKey *pathkey = (PathKey*) lfirst(lc);
EquivalenceMember *em;
double nGroups,
correctedNGroups;
/*
- * We believe than equivalence members aren't very different, so, to
+ * We believe than equivalence members aren't very different, so, to
* estimate cost we take just first member
*/
em = (EquivalenceMember *) linitial(pathkey->pk_eclass->ec_members);
@@ -1964,7 +1964,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
totalFuncCost += funcCost;
- /* remeber if we have a fake var in pathkeys */
+ /* Remember if we have a fake var in pathkeys */
has_fake_var |= is_fake_var(em->em_expr);
pathkeyExprs = lappend(pathkeyExprs, em->em_expr);
@@ -1974,7 +1974,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
*/
if (has_fake_var == false)
/*
- * Recursively compute number of group in group from previous step
+ * Recursively compute number of groups in a group from previous step
*/
nGroups = estimate_num_groups_incremental(root, pathkeyExprs,
tuplesPerPrevGroup, NULL, NULL,
@@ -1992,8 +1992,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
*
* XXX What's the logic of the following formula?
*/
- nGroups = ceil(2.0 + sqrt(tuples) *
- list_length(pathkeyExprs) / list_length(pathkeys));
+ nGroups = ceil(2.0 + sqrt(tuples) * (i + 1) / list_length(pathkeys));
else
nGroups = tuples;
@@ -2033,7 +2032,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
/*
* We could skip all following columns for cost estimation, because we
- * believe that tuples are unique by set ot previous columns
+ * believe that tuples are unique by the set of previous columns
*/
if (tuplesPerPrevGroup <= 1.0)
break;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 82831a4fa4..707b5ba75b 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -544,9 +544,10 @@ PathkeyMutatorNext(PathkeyMutatorState *state)
return state->elemsList;
}
-typedef struct {
- Cost cost;
- PathKey *pathkey;
+typedef struct PathkeySortCost
+{
+ Cost cost;
+ PathKey *pathkey;
} PathkeySortCost;
static int
@@ -793,7 +794,7 @@ get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
* more complex logic to decide the ordering.
*
* XXX Isn't this somewhat redundant with presorted_keys? Actually, it's
- * more a complement, because it allows benefinting from incremental sort
+ * more a complement, because it allows benefiting from incremental sort
* as much as possible.
*
* XXX This does nothing if (n_preordered == 0). We shouldn't create the
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 7a89cee879..f281a23bb7 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6158,7 +6158,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
{
ListCell *lc2;
Path *path = (Path *) lfirst(lc);
- Path *path_save = path;
Path *path_original = path;
List *pathkey_orderings = NIL;
@@ -6182,9 +6181,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
int presorted_keys = 0;
PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2);
- /* restore the path (we replace it in the loop) */
- path = path_save;
-
is_sorted = pathkeys_count_contained_in(info->pathkeys,
path->pathkeys,
&presorted_keys);
@@ -6653,7 +6649,6 @@ create_partial_grouping_paths(PlannerInfo *root,
{
ListCell *lc2;
Path *path = (Path *) lfirst(lc);
- Path *path_save = path;
List *pathkey_orderings = NIL;
@@ -6676,9 +6671,6 @@ create_partial_grouping_paths(PlannerInfo *root,
int presorted_keys = 0;
PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2);
- /* restore the path (we replace it in the loop) */
- path = path_save;
-
is_sorted = pathkeys_count_contained_in(info->pathkeys,
path->pathkeys,
&presorted_keys);
view thread (89+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected]
Subject: Re: POC: GROUP BY optimization
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox