On 9/12/24 16:57, Tomas Vondra wrote:
On 9/12/24 12:12, David Rowley wrote:
On Thu, 12 Sept 2024 at 21:51, Andrei Lepikhov <lepi...@gmail.com> wrote:
Initial problem causes wrong cost_sort estimation. Right now I think
about providing cost_sort() the sort clauses instead of (or in addition
to) the pathkeys.
I'm not quite sure why the sort clauses matter any more than the
EquivalenceClass. If the EquivalanceClass defines that all members
will have the same value for any given row, then, if we had to choose
any single member to drive the n_distinct estimate from, isn't the
most accurate distinct estimate from the member with the smallest
n_distinct estimate? (That assumes the less distinct member has every
value the more distinct member has, which might not be true)
I'm not sure how to fix this, but it seems estimate_num_groups() needs
to do things differently. And I agree looking for the minimum ndistinct
seems like the right approach. but doesn't estimate_num_groups()
supposed to already do that? The comment says:
Hi,
I have rewritten the code according to the idea of the
estimate_num_groups responsibility to adjust estimation according to the EC.
I haven't changed all the places of ngroups estimation - only where the
planner can access pathkeys to avoid the overhead of passing through all
the ECs. And added some cache in the EM.
The most important case for me here is GROUP-BY estimation and
create_unique_path because I frequently see them as sides of a JOIN.
It would be also nice to adjust the cost of memoize rescan, but it may
be a subject of the future improvement.
--
regards, Andrei Lepikhov
From 18a320cf9eee52299909f50533ef49cf2af2c69e Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <lepi...@gmail.com>
Date: Wed, 14 May 2025 12:36:10 +0200
Subject: [PATCH v0] Employ EquivalenceClass to adjust ndistinct estimation.
Operations like grouping, incremental sort, hash join, memoize, etc., estimate
the number of groups in a source using the statistics of this column
or expression.
Equivalence clauses like 'x=y' obviously reduce the maximum number of distinct
values above the clause evaluation node to the fewest distincts in the 'x'
or 'y' source. Therefore, in estimating the groups number, the planner may
involve this data from the EC.
Identification of proper EC for arbitrary expression seems too expensive
operation. However, having a pathkey gives the planner immediate access to
the EC. Here, a routine to identify proper expression is provided. ndistinct
estimation is cached inside the EM.
---
contrib/postgres_fdw/postgres_fdw.c | 2 +-
src/backend/optimizer/path/costsize.c | 130 ++++++++++--------
src/backend/optimizer/path/equivclass.c | 1 +
src/backend/optimizer/path/indxpath.c | 1 +
src/backend/optimizer/plan/createplan.c | 1 +
src/backend/optimizer/plan/planner.c | 29 ++--
src/backend/optimizer/prep/prepunion.c | 1 +
src/backend/optimizer/util/pathnode.c | 2 +
src/backend/utils/adt/selfuncs.c | 41 +++++-
src/include/nodes/pathnodes.h | 5 +
src/include/optimizer/cost.h | 5 +-
src/include/utils/selfuncs.h | 2 +-
.../regress/expected/incremental_sort.out | 50 +++++++
src/test/regress/expected/stats.out | 17 +++
src/test/regress/sql/incremental_sort.sql | 29 ++++
src/test/regress/sql/stats.sql | 8 ++
16 files changed, 249 insertions(+), 75 deletions(-)
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index 331f3fc088d..09766daf97c 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -3370,7 +3370,7 @@ estimate_path_cost_size(PlannerInfo *root,
numGroups = estimate_num_groups(root,
get_sortgrouplist_exprs(root->processed_groupClause,
fpinfo->grouped_tlist),
- input_rows, NULL, NULL);
+ input_rows, NULL, NULL, NULL);
/*
* Get the retrieved_rows and rows estimates. If there are HAVING
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 3d44815ed5a..5b51d020b7f 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1999,7 +1999,7 @@ cost_tuplesort(Cost *startup_cost, Cost *run_cost,
void
cost_incremental_sort(Path *path,
PlannerInfo *root, List *pathkeys, int presorted_keys,
- int input_disabled_nodes,
+ int input_disabled_nodes, Relids relids,
Cost input_startup_cost, Cost input_total_cost,
double input_tuples, int width, Cost comparison_cost, int sort_mem,
double limit_tuples)
@@ -2012,9 +2012,6 @@ cost_incremental_sort(Path *path,
Cost group_startup_cost,
group_run_cost,
group_input_run_cost;
- List *presortedExprs = NIL;
- ListCell *l;
- bool unknown_varno = false;
Assert(presorted_keys > 0 && presorted_keys < list_length(pathkeys));
@@ -2025,58 +2022,10 @@ cost_incremental_sort(Path *path,
if (input_tuples < 2.0)
input_tuples = 2.0;
- /* Default estimate of number of groups, capped to one group per row. */
- input_groups = Min(input_tuples, DEFAULT_NUM_DISTINCT);
-
- /*
- * Extract presorted keys as list of expressions.
- *
- * We need to be careful about Vars containing "varno 0" which might have
- * been introduced by generate_append_tlist, which would confuse
- * estimate_num_groups (in fact it'd fail for such expressions). See
- * recurse_set_operations which has to deal with the same issue.
- *
- * Unlike recurse_set_operations we can't access the original target list
- * here, and even if we could it's not very clear how useful would that be
- * for a set operation combining multiple tables. So we simply detect if
- * there are any expressions with "varno 0" and use the default
- * DEFAULT_NUM_DISTINCT in that case.
- *
- * We might also use either 1.0 (a single group) or input_tuples (each row
- * being a separate group), pretty much the worst and best case for
- * incremental sort. But those are extreme cases and using something in
- * between seems reasonable. Furthermore, generate_append_tlist is used
- * for set operations, which are likely to produce mostly unique output
- * anyway - from that standpoint the DEFAULT_NUM_DISTINCT is defensive
- * while maintaining lower startup cost.
- */
- foreach(l, pathkeys)
- {
- PathKey *key = (PathKey *) lfirst(l);
- EquivalenceMember *member = (EquivalenceMember *)
- linitial(key->pk_eclass->ec_members);
-
- /*
- * Check if the expression contains Var with "varno 0" so that we
- * don't call estimate_num_groups in that case.
- */
- if (bms_is_member(0, pull_varnos(root, (Node *) member->em_expr)))
- {
- unknown_varno = true;
- break;
- }
-
- /* expression not containing any Vars with "varno 0" */
- presortedExprs = lappend(presortedExprs, member->em_expr);
-
- if (foreach_current_index(l) + 1 >= presorted_keys)
- break;
- }
-
/* Estimate the number of groups with equal presorted keys. */
- if (!unknown_varno)
- input_groups = estimate_num_groups(root, presortedExprs, input_tuples,
- NULL, NULL);
+ input_groups = estimate_num_groups(root,
+ list_copy_head(pathkeys, presorted_keys),
+ input_tuples, NULL, NULL, relids);
group_tuples = input_tuples / input_groups;
group_input_run_cost = input_run_cost / input_groups;
@@ -2579,7 +2528,7 @@ cost_memoize_rescan(PlannerInfo *root, MemoizePath *mpath,
/* estimate on the distinct number of parameter values */
ndistinct = estimate_num_groups(root, mpath->param_exprs, calls, NULL,
- &estinfo);
+ &estinfo, NULL);
/*
* When the estimation fell back on using a default value, it's a bit too
@@ -2900,7 +2849,7 @@ get_windowclause_startup_tuples(PlannerInfo *root, WindowClause *wc,
root->parse->targetList);
num_partitions = estimate_num_groups(root, partexprs, input_tuples,
- NULL, NULL);
+ NULL, NULL, NULL);
list_free(partexprs);
partition_tuples = input_tuples / num_partitions;
@@ -2923,7 +2872,7 @@ get_windowclause_startup_tuples(PlannerInfo *root, WindowClause *wc,
/* estimate out how many peer groups there are in the partition */
num_groups = estimate_num_groups(root, orderexprs,
partition_tuples, NULL,
- NULL);
+ NULL, NULL);
list_free(orderexprs);
peer_tuples = partition_tuples / num_groups;
}
@@ -3703,6 +3652,7 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
outersortkeys,
outer_presorted_keys,
outer_path->disabled_nodes,
+ outer_path->parent->relids,
outer_path->startup_cost,
outer_path->total_cost,
outer_path_rows,
@@ -6614,3 +6564,67 @@ compute_gather_rows(Path *path)
return clamp_row_est(path->rows * get_parallel_divisor(path));
}
+
+/*
+ * Find suitable member of the equivalence class.
+ * Passing through the list of EC members find the member with minimum of
+ * distinct values. Cache estimated number of distincts in the em_ndistinct
+ * field of each member.
+ *
+ * Return NULL if no one proper member found (each member contains 0 relid).
+ */
+EquivalenceMember *
+identify_proper_ecmember(PlannerInfo *root, EquivalenceClass *ec, Relids relids)
+{
+ EquivalenceMember *candidate = NULL;
+ EquivalenceMember *em;
+ EquivalenceMemberIterator it;
+
+ setup_eclass_member_iterator(&it, ec, relids);
+ while ((em = eclass_member_iterator_next(&it)) != NULL)
+ {
+ VariableStatData vardata;
+
+ if (bms_is_member(0, em->em_relids))
+ continue;
+
+ if (em->em_is_const || bms_is_empty(em->em_relids))
+ {
+ /* Trivial case. Set up cache values and go further */
+ em->em_default_nd = false;
+ em->em_ndistinct = 1.0;
+ }
+ else if (relids && !bms_is_subset(em->em_relids, relids))
+ continue;
+
+ if (em->em_ndistinct < 0.)
+ {
+ /* Let's check candidate's ndistinct value */
+ examine_variable(root, (Node *) em->em_expr, 0, &vardata);
+ if (HeapTupleIsValid(vardata.statsTuple))
+ em->em_ndistinct =
+ get_variable_numdistinct(&vardata, &em->em_default_nd);
+ else
+ {
+ em->em_ndistinct = 0.0;
+ em->em_default_nd = true;
+ }
+ ReleaseVariableStats(vardata);
+ }
+
+ if (candidate == NULL)
+ candidate = em;
+
+ if (em->em_default_nd)
+ /* Nothing helpful */
+ continue;
+
+ Assert(em->em_ndistinct > 0.);
+
+ if (candidate->em_ndistinct == 0. ||
+ em->em_ndistinct < candidate->em_ndistinct)
+ candidate = em;
+ }
+
+ return candidate;
+}
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 441f12f6c50..422241aa7f1 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -601,6 +601,7 @@ make_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
em->em_datatype = datatype;
em->em_jdomain = jdomain;
em->em_parent = parent;
+ em->em_ndistinct = -1.0;
if (bms_is_empty(relids))
{
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 601354ea3e0..d3354506813 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2400,6 +2400,7 @@ adjust_rowcount_for_semijoins(PlannerInfo *root,
sjinfo->semi_rhs_exprs,
nraw,
NULL,
+ NULL,
NULL);
if (rowcount > nunique)
rowcount = nunique;
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 4ad30b7627e..cb728e1e12d 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -5523,6 +5523,7 @@ label_incrementalsort_with_costsize(PlannerInfo *root, IncrementalSort *plan,
cost_incremental_sort(&sort_path, root, pathkeys,
plan->nPresortedCols,
plan->sort.plan.disabled_nodes,
+ NULL,
lefttree->startup_cost,
lefttree->total_cost,
lefttree->plan_rows,
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index beafac8c0b0..c6881362637 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -144,6 +144,7 @@ static List *extract_rollup_sets(List *groupingSets);
static List *reorder_grouping_sets(List *groupingSets, List *sortclause);
static void standard_qp_callback(PlannerInfo *root, void *extra);
static double get_number_of_groups(PlannerInfo *root,
+ Relids relids,
double path_rows,
grouping_sets_data *gd,
List *target_list);
@@ -3599,7 +3600,7 @@ standard_qp_callback(PlannerInfo *root, void *extra)
* determining whether some combination of them could be hashed instead.
*/
static double
-get_number_of_groups(PlannerInfo *root,
+get_number_of_groups(PlannerInfo *root, Relids relids,
double path_rows,
grouping_sets_data *gd,
List *target_list)
@@ -3639,7 +3640,8 @@ get_number_of_groups(PlannerInfo *root,
groupExprs,
path_rows,
&gset,
- NULL);
+ NULL,
+ relids);
gs->numGroups = numGroups;
rollup->numGroups += numGroups;
@@ -3665,7 +3667,8 @@ get_number_of_groups(PlannerInfo *root,
groupExprs,
path_rows,
&gset,
- NULL);
+ NULL,
+ relids);
gs->numGroups = numGroups;
gd->dNumHashGroups += numGroups;
@@ -3676,12 +3679,12 @@ get_number_of_groups(PlannerInfo *root,
}
else
{
- /* Plain GROUP BY -- estimate based on optimized groupClause */
- groupExprs = get_sortgrouplist_exprs(root->processed_groupClause,
- target_list);
+ List *pathkeys = list_copy_head(root->group_pathkeys,
+ root->num_groupby_pathkeys);
- dNumGroups = estimate_num_groups(root, groupExprs, path_rows,
- NULL, NULL);
+ /* Plain GROUP BY -- estimate based on grouping pathkeys */
+ dNumGroups = estimate_num_groups(root, pathkeys, path_rows,
+ NULL, NULL, relids);
}
}
else if (parse->groupingSets)
@@ -4071,7 +4074,7 @@ create_ordinary_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel,
/*
* Estimate number of groups.
*/
- dNumGroups = get_number_of_groups(root,
+ dNumGroups = get_number_of_groups(root, cheapest_path->parent->relids,
cheapest_path->rows,
gd,
extra->targetList);
@@ -4843,7 +4846,7 @@ create_partial_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
/* estimate how many distinct rows we'll get from each worker */
numDistinctRows = estimate_num_groups(root, distinctExprs,
cheapest_partial_path->rows,
- NULL, NULL);
+ NULL, NULL, NULL);
/*
* Try sorting the cheapest path and incrementally sorting any paths with
@@ -5014,7 +5017,7 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
parse->targetList);
numDistinctRows = estimate_num_groups(root, distinctExprs,
cheapest_input_path->rows,
- NULL, NULL);
+ NULL, NULL, NULL);
}
/*
@@ -7355,13 +7358,13 @@ create_partial_grouping_paths(PlannerInfo *root,
/* Estimate number of partial groups. */
if (cheapest_total_path != NULL)
dNumPartialGroups =
- get_number_of_groups(root,
+ get_number_of_groups(root, input_rel->relids,
cheapest_total_path->rows,
gd,
extra->targetList);
if (cheapest_partial_path != NULL)
dNumPartialPartialGroups =
- get_number_of_groups(root,
+ get_number_of_groups(root, input_rel->relids,
cheapest_partial_path->rows,
gd,
extra->targetList);
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index eab44da65b8..e094ad103d6 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -665,6 +665,7 @@ build_setop_child_paths(PlannerInfo *root, RelOptInfo *rel,
get_tlist_exprs(subroot->parse->targetList, false),
rel->cheapest_total_path->rows,
NULL,
+ NULL,
NULL);
}
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index e0192d4a491..9652094b47b 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1858,6 +1858,7 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
sjinfo->semi_rhs_exprs,
rel->rows,
NULL,
+ NULL,
NULL);
numCols = list_length(sjinfo->semi_rhs_exprs);
@@ -3059,6 +3060,7 @@ create_incremental_sort_path(PlannerInfo *root,
cost_incremental_sort(&pathnode->path,
root, pathkeys, presorted_keys,
subpath->disabled_nodes,
+ subpath->parent->relids,
subpath->startup_cost,
subpath->total_cost,
subpath->rows,
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index a96b1b9c0bc..1ab5863338f 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3444,7 +3444,7 @@ add_unique_group_var(PlannerInfo *root, List *varinfos,
*/
double
estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
- List **pgset, EstimationInfo *estinfo)
+ List **pgset, EstimationInfo *estinfo, Relids relids)
{
List *varinfos = NIL;
double srf_multiplier = 1.0;
@@ -3481,6 +3481,27 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
*/
numdistinct = 1.0;
+ /*
+ * We need to be careful about Vars containing "varno 0" which might have
+ * been introduced by generate_append_tlist, which would confuse
+ * estimate_num_groups (in fact it'd fail for such expressions). See
+ * recurse_set_operations which has to deal with the same issue.
+ *
+ * Unlike recurse_set_operations we can't access the original target list
+ * here, and even if we could it's not very clear how useful would that be
+ * for a set operation combining multiple tables. So we simply detect if
+ * there are any expressions with "varno 0" and use the default
+ * DEFAULT_NUM_DISTINCT in that case.
+ *
+ * We might also use either 1.0 (a single group) or input_tuples (each row
+ * being a separate group), pretty much the worst and best case for
+ * incremental sort. But those are extreme cases and using something in
+ * between seems reasonable. Furthermore, generate_append_tlist is used
+ * for set operations, which are likely to produce mostly unique output
+ * anyway - from that standpoint the DEFAULT_NUM_DISTINCT is defensive
+ * while maintaining lower startup cost.
+ */
+
i = 0;
foreach(l, groupExprs)
{
@@ -3494,6 +3515,24 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
if (pgset && !list_member_int(*pgset, i++))
continue;
+ /*
+ * PathKey doesn't provide an expression explicitly. With a sake of
+ * estimation we may choose any one from the equvalence class which
+ * provides least number of distinct values and evaluates under the
+ * relids provided.
+ */
+ if (IsA(groupexpr, PathKey))
+ {
+ PathKey *pathkey = (PathKey *) groupexpr;
+ EquivalenceMember *em;
+
+ em = identify_proper_ecmember(root, pathkey->pk_eclass, relids);
+ if (em == NULL)
+ /*The case of varno 0 */
+ return Min(input_rows, DEFAULT_NUM_DISTINCT);
+ groupexpr = (Node *) em->em_expr;
+ }
+
/*
* Set-returning functions in grouping columns are a bit problematic.
* The code below will effectively ignore their SRF nature and come up
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 1dd2d1560cb..203445eda7e 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1501,6 +1501,8 @@ typedef struct EquivalenceClass
* different when dealing with a binary-compatible opfamily; in particular
* anyarray_ops would never work without this. Use em_datatype when
* looking up a specific btree operator to work with this expression.
+ * em_ndistinct caches statistical estimation of ndistinct value for specific
+ * expression. special values: 0 - no statistic available; -1 - not initialised.
*/
typedef struct EquivalenceMember
{
@@ -1516,6 +1518,9 @@ typedef struct EquivalenceMember
JoinDomain *em_jdomain; /* join domain containing the source clause */
/* if em_is_child is true, this links to corresponding EM for top parent */
struct EquivalenceMember *em_parent pg_node_attr(read_write_ignore);
+
+ double em_ndistinct; /* cached ndistinct value */
+ bool em_default_nd;
} EquivalenceMember;
/*
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index d397fe27dc1..984104433fd 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -114,7 +114,7 @@ extern void cost_sort(Path *path, PlannerInfo *root,
double limit_tuples);
extern void cost_incremental_sort(Path *path,
PlannerInfo *root, List *pathkeys, int presorted_keys,
- int input_disabled_nodes,
+ int input_disabled_nodes, Relids relids,
Cost input_startup_cost, Cost input_total_cost,
double input_tuples, int width, Cost comparison_cost, int sort_mem,
double limit_tuples);
@@ -222,5 +222,8 @@ extern double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel,
Path *bitmapqual, double loop_count,
Cost *cost_p, double *tuples_p);
extern double compute_gather_rows(Path *path);
+extern EquivalenceMember *identify_proper_ecmember(PlannerInfo *root,
+ EquivalenceClass *ec,
+ Relids relids);
#endif /* COST_H */
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index 013049b3098..665d659497f 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -216,7 +216,7 @@ extern void mergejoinscansel(PlannerInfo *root, Node *clause,
extern double estimate_num_groups(PlannerInfo *root, List *groupExprs,
double input_rows, List **pgset,
- EstimationInfo *estinfo);
+ EstimationInfo *estinfo, Relids relids);
extern List *estimate_multivariate_bucketsize(PlannerInfo *root,
RelOptInfo *inner,
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index b00219643b9..b23dc13ca6f 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1722,3 +1722,53 @@ order by t1.four, t1.two limit 1;
-> Seq Scan on tenk1 t2
(12 rows)
+--
+-- Commuting of sides in an expression doesn't influence cost estimation
+--
+CREATE TABLE sort_ndist_t1 (x numeric, y numeric);
+CREATE TABLE sort_ndist_t2 (x numeric, y numeric);
+INSERT INTO sort_ndist_t1 (x,y)
+ SELECT gs%10, gs%1000 FROM generate_series(1,1E4) AS gs;
+INSERT INTO sort_ndist_t2 (x,y)
+ SELECT gs, gs FROM generate_series(1,1E4) AS gs;
+CREATE INDEX t1_idx ON sort_ndist_t1 (x);
+CREATE INDEX t2_idx ON sort_ndist_t2 (x);
+VACUUM ANALYZE sort_ndist_t1, sort_ndist_t2;
+SET enable_hashjoin = 'off';
+-- Having lots of duplicates after the join it is more effective to use plain
+-- Sort instead of incremental sort.
+EXPLAIN (COSTS OFF)
+SELECT t1.x, t1.y FROM sort_ndist_t1 t1, sort_ndist_t2 t2
+WHERE t1.x=t2.x
+ORDER BY t1.x,t1.y;
+ QUERY PLAN
+--------------------------------------------------------------------
+ Sort
+ Sort Key: t1.x, t1.y
+ -> Nested Loop
+ -> Seq Scan on sort_ndist_t1 t1
+ -> Memoize
+ Cache Key: t1.x
+ Cache Mode: logical
+ -> Index Only Scan using t2_idx on sort_ndist_t2 t2
+ Index Cond: (x = t1.x)
+(9 rows)
+
+EXPLAIN (COSTS OFF) -- the plan must be the same as above
+SELECT t1.x, t1.y FROM sort_ndist_t1 t1, sort_ndist_t2 t2
+WHERE t2.x=t1.x
+ORDER BY t1.x,t1.y;
+ QUERY PLAN
+--------------------------------------------------------------------
+ Sort
+ Sort Key: t1.x, t1.y
+ -> Nested Loop
+ -> Seq Scan on sort_ndist_t1 t1
+ -> Memoize
+ Cache Key: t1.x
+ Cache Mode: logical
+ -> Index Only Scan using t2_idx on sort_ndist_t2 t2
+ Index Cond: (x = t1.x)
+(9 rows)
+
+RESET enable_hashjoin;
diff --git a/src/test/regress/expected/stats.out b/src/test/regress/expected/stats.out
index 776f1ad0e53..a04b580c643 100644
--- a/src/test/regress/expected/stats.out
+++ b/src/test/regress/expected/stats.out
@@ -1868,4 +1868,21 @@ SELECT * FROM check_estimated_rows('SELECT * FROM table_fillfactor');
(1 row)
DROP TABLE table_fillfactor;
+-- The estimation of the number of groups is based on the equivalence class
+-- definition and shouldn't change if an alternative member of the same EC
+-- is chosen.
+SELECT * FROM check_estimated_rows('
+ SELECT count(*) FROM sort_ndist_t1 t1 WHERE t1.x=t1.y GROUP BY t1.x');
+ estimated | actual
+-----------+--------
+ 10 | 10
+(1 row)
+
+SELECT * FROM check_estimated_rows('
+ SELECT count(*) FROM sort_ndist_t1 t1 WHERE t1.x=t1.y GROUP BY t1.y');
+ estimated | actual
+-----------+--------
+ 10 | 10
+(1 row)
+
-- End of Stats Test
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index f1f8fae5654..298a2782b95 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -298,3 +298,32 @@ explain (costs off)
select * from
(select * from tenk1 order by four) t1 join tenk1 t2 on t1.four = t2.four and t1.two = t2.two
order by t1.four, t1.two limit 1;
+
+--
+-- Commuting of sides in an expression doesn't influence cost estimation
+--
+CREATE TABLE sort_ndist_t1 (x numeric, y numeric);
+CREATE TABLE sort_ndist_t2 (x numeric, y numeric);
+
+INSERT INTO sort_ndist_t1 (x,y)
+ SELECT gs%10, gs%1000 FROM generate_series(1,1E4) AS gs;
+INSERT INTO sort_ndist_t2 (x,y)
+ SELECT gs, gs FROM generate_series(1,1E4) AS gs;
+CREATE INDEX t1_idx ON sort_ndist_t1 (x);
+CREATE INDEX t2_idx ON sort_ndist_t2 (x);
+VACUUM ANALYZE sort_ndist_t1, sort_ndist_t2;
+
+SET enable_hashjoin = 'off';
+
+-- Having lots of duplicates after the join it is more effective to use plain
+-- Sort instead of incremental sort.
+EXPLAIN (COSTS OFF)
+SELECT t1.x, t1.y FROM sort_ndist_t1 t1, sort_ndist_t2 t2
+WHERE t1.x=t2.x
+ORDER BY t1.x,t1.y;
+EXPLAIN (COSTS OFF) -- the plan must be the same as above
+SELECT t1.x, t1.y FROM sort_ndist_t1 t1, sort_ndist_t2 t2
+WHERE t2.x=t1.x
+ORDER BY t1.x,t1.y;
+
+RESET enable_hashjoin;
diff --git a/src/test/regress/sql/stats.sql b/src/test/regress/sql/stats.sql
index 232ab8db8fa..b4d3d6d0862 100644
--- a/src/test/regress/sql/stats.sql
+++ b/src/test/regress/sql/stats.sql
@@ -925,4 +925,12 @@ SELECT * FROM check_estimated_rows('SELECT * FROM table_fillfactor');
DROP TABLE table_fillfactor;
+-- The estimation of the number of groups is based on the equivalence class
+-- definition and shouldn't change if an alternative member of the same EC
+-- is chosen.
+SELECT * FROM check_estimated_rows('
+ SELECT count(*) FROM sort_ndist_t1 t1 WHERE t1.x=t1.y GROUP BY t1.x');
+SELECT * FROM check_estimated_rows('
+ SELECT count(*) FROM sort_ndist_t1 t1 WHERE t1.x=t1.y GROUP BY t1.y');
+
-- End of Stats Test
--
2.39.5
