Subject: Incremental Sort Cost Estimation Instability

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 26 Jun 2024 22:00:27 +0700

Hi,

While designing an improvement for the cost sort model, I discovered 
that the query plan can vary if we slightly change the query text 
without pushing semantic differences. See the example below:

CREATE TABLE test(x integer, y integer,z text);
INSERT INTO test (x,y) SELECT x, 1 FROM generate_series(1,1000000) AS x;
CREATE INDEX ON test(x);
CREATE INDEX ON test(y);
VACUUM ANALYZE;
SET max_parallel_workers_per_gather = 0;

First query:

EXPLAIN (ANALYZE, TIMING OFF) SELECT count(*) FROM test t1, test t2
WHERE t1.x=t2.y AND t1.y=t2.x GROUP BY t1.x,t1.y;

And the second one - just reverse the left and right sides of 
expressions in the WHERE condition:

EXPLAIN (ANALYZE, TIMING OFF) SELECT count(*) FROM test t1, test t2
WHERE t2.y=t1.x AND t2.x=t1.y GROUP BY t1.x,t1.y;

You can see two different plans here:

GroupAggregate  (cost=37824.89..37824.96 rows=1 width=16)
   Group Key: t1.y, t1.x
   ->  Incremental Sort  (cost=37824.89..37824.94 rows=2 width=8)
         Sort Key: t1.y, t1.x
         Presorted Key: t1.y
         ->  Merge Join  (cost=0.85..37824.88 rows=1 width=8)
               Merge Cond: (t1.y = t2.x)
               Join Filter: (t2.y = t1.x)
               ->  Index Scan using test_y_idx on test t1
               ->  Index Scan using test_x_idx on test t2

GroupAggregate  (cost=37824.89..37824.92 rows=1 width=16)
   Group Key: t1.x, t1.y
   ->  Sort  (cost=37824.89..37824.90 rows=1 width=8)
         Sort Key: t1.x, t1.y
         Sort Method: quicksort  Memory: 25kB
         ->  Merge Join  (cost=0.85..37824.88 rows=1 width=8)
               Merge Cond: (t1.y = t2.x)
               Join Filter: (t2.y = t1.x)
               ->  Index Scan using test_y_idx on test t1
               ->  Index Scan using test_x_idx on test t2

Don't mind for now that the best plan is to do IncrementalSort with 
presorted key t1.x. Just pay attention to the fact that the plan has 
altered without any valuable reason.
The cost_incremental_sort() routine causes such behaviour: it chooses 
the expression to estimate the number of groups from the first 
EquivalenceClass member that relies on the syntax.
I tried to invent a simple solution to fight this minor case. But the 
most clear and straightforward way here is to save a reference to the 
expression that triggered the PathKey creation inside the PathKey itself.
See the sketch of the patch in the attachment.
I'm not sure this instability is worth fixing this way, but the 
dependence of the optimisation outcome on the query text looks buggy.

-- 
regards, Andrei Lepikhov

From 8eb9998fe3306005d5067e53fef6a032515ebed5 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email-masked]>
Date: Wed, 26 Jun 2024 16:28:12 +0700
Subject: [PATCH] Add a reference to the expression which has triggered
 creation of this pathkey.

For the sake of consistency in number of groups estimation in incremental sort
we need to have an information about expression which caused the pathkey. It
doesn't guarantee correct estimation but at least estimation doesn't rely on
a SQL string.
---
 contrib/postgres_fdw/postgres_fdw.c   |  6 +++--
 src/backend/optimizer/path/costsize.c | 28 +++++++++++++++++++----
 src/backend/optimizer/path/pathkeys.c | 33 ++++++++++++++++++++++-----
 src/include/nodes/pathnodes.h         |  2 ++
 src/include/optimizer/paths.h         |  3 ++-
 5 files changed, 59 insertions(+), 13 deletions(-)

diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index 0bb9a5ae8f..da26d99fb1 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -976,6 +976,7 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
 	foreach(lc, useful_eclass_list)
 	{
 		EquivalenceClass *cur_ec = lfirst(lc);
+		EquivalenceMember *em;
 		PathKey    *pathkey;
 
 		/* If redundant with what we did above, skip it. */
@@ -988,14 +989,15 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
 			continue;
 
 		/* If no pushable expression for this rel, skip it. */
-		if (find_em_for_rel(root, cur_ec, rel) == NULL)
+		if ((em = find_em_for_rel(root, cur_ec, rel)) == NULL)
 			continue;
 
 		/* Looks like we can generate a pathkey, so let's do it. */
 		pathkey = make_canonical_pathkey(root, cur_ec,
 										 linitial_oid(cur_ec->ec_opfamilies),
 										 BTLessStrategyNumber,
-										 false);
+										 false,
+										 em->em_expr); /* TODO */
 		useful_pathkeys_list = lappend(useful_pathkeys_list,
 									   list_make1(pathkey));
 	}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index ee23ed7835..a64f3e5797 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2038,21 +2038,41 @@ cost_incremental_sort(Path *path,
 	foreach(l, pathkeys)
 	{
 		PathKey    *key = (PathKey *) lfirst(l);
-		EquivalenceMember *member = (EquivalenceMember *)
-			linitial(key->pk_eclass->ec_members);
+
+#ifdef USE_ASSERT_CHECKING
+		ListCell *lc;
+
+		/* Be paranoid, but caring about performace don't check on prod */
+		foreach(lc, key->pk_eclass->ec_members)
+		{
+			if (find_ec_member_matching_expr(
+								key->pk_eclass, key->source_expr,
+								pull_varnos(root, (Node *) key->source_expr)))
+				break;
+		}
+		if (!lc)
+			/*
+			 * XXX: Can we build PathKey over derived expression and does it
+			 * trigger this error?
+			 */
+			elog(ERROR, "PathKey source expression must be a part of EQ class");
+#endif
+
+		/* Reassure ourselves no one created pathkeys alternative way */
+		Assert(key->source_expr != NULL);
 
 		/*
 		 * 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)))
+		if (bms_is_member(0, pull_varnos(root, (Node *) key->source_expr)))
 		{
 			unknown_varno = true;
 			break;
 		}
 
 		/* expression not containing any Vars with "varno 0" */
-		presortedExprs = lappend(presortedExprs, member->em_expr);
+		presortedExprs = lappend(presortedExprs, key->source_expr);
 
 		if (foreach_current_index(l) + 1 >= presorted_keys)
 			break;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 416fc4e240..d859e79208 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -54,7 +54,7 @@ static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
 PathKey *
 make_canonical_pathkey(PlannerInfo *root,
 					   EquivalenceClass *eclass, Oid opfamily,
-					   int strategy, bool nulls_first)
+					   int strategy, bool nulls_first, Expr *src_expr)
 {
 	PathKey    *pk;
 	ListCell   *lc;
@@ -89,6 +89,7 @@ make_canonical_pathkey(PlannerInfo *root,
 	pk->pk_opfamily = opfamily;
 	pk->pk_strategy = strategy;
 	pk->pk_nulls_first = nulls_first;
+	pk->source_expr = src_expr;
 
 	root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
 
@@ -241,7 +242,7 @@ make_pathkey_from_sortinfo(PlannerInfo *root,
 
 	/* And finally we can find or create a PathKey node */
 	return make_canonical_pathkey(root, eclass, opfamily,
-								  strategy, nulls_first);
+								  strategy, nulls_first, expr);
 }
 
 /*
@@ -1117,7 +1118,8 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 											   outer_ec,
 											   sub_pathkey->pk_opfamily,
 											   sub_pathkey->pk_strategy,
-											   sub_pathkey->pk_nulls_first);
+											   sub_pathkey->pk_nulls_first,
+											   (Expr *) outer_var);
 			}
 		}
 		else
@@ -1199,7 +1201,8 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 													  outer_ec,
 													  sub_pathkey->pk_opfamily,
 													  sub_pathkey->pk_strategy,
-													  sub_pathkey->pk_nulls_first);
+													  sub_pathkey->pk_nulls_first,
+													  (Expr *) outer_var);
 					/* score = # of equivalence peers */
 					score = list_length(outer_ec->ec_members) - 1;
 					/* +1 if it matches the proper query_pathkeys item */
@@ -1643,6 +1646,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 	List	   *pathkeys = NIL;
 	int			nClauses = list_length(mergeclauses);
 	EquivalenceClass **ecs;
+	Expr			 **exprs;
 	int		   *scores;
 	int			necs;
 	ListCell   *lc;
@@ -1657,6 +1661,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 	 * duplicates) and their "popularity" scores.
 	 */
 	ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
+	exprs = (Expr **) palloc(nClauses * sizeof(Expr *));
 	scores = (int *) palloc(nClauses * sizeof(int));
 	necs = 0;
 
@@ -1666,14 +1671,21 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 		EquivalenceClass *oeclass;
 		int			score;
 		ListCell   *lc2;
+		Expr	   *expr;
 
 		/* get the outer eclass */
 		update_mergeclause_eclasses(root, rinfo);
 
 		if (rinfo->outer_is_left)
+		{
 			oeclass = rinfo->left_ec;
+			expr = (Expr *) linitial(((OpExpr *) rinfo->clause)->args);
+		}
 		else
+		{
 			oeclass = rinfo->right_ec;
+			expr = (Expr *) lsecond(((OpExpr *) rinfo->clause)->args);
+		}
 
 		/* reject duplicates */
 		for (j = 0; j < necs; j++)
@@ -1697,6 +1709,8 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 		}
 
 		ecs[necs] = oeclass;
+		exprs[necs] = expr;
+
 		scores[necs] = score;
 		necs++;
 	}
@@ -1798,7 +1812,8 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 										 ec,
 										 linitial_oid(ec->ec_opfamilies),
 										 BTLessStrategyNumber,
-										 false);
+										 false,
+										 exprs[best_j]);
 		/* can't be redundant because no duplicate ECs */
 		Assert(!pathkey_is_redundant(pathkey, pathkeys));
 		pathkeys = lappend(pathkeys, pathkey);
@@ -1852,18 +1867,23 @@ make_inner_pathkeys_for_merge(PlannerInfo *root,
 		EquivalenceClass *oeclass;
 		EquivalenceClass *ieclass;
 		PathKey    *pathkey;
+		Expr	   *src_expr;
 
 		update_mergeclause_eclasses(root, rinfo);
 
+		Assert(IsA(rinfo->clause, OpExpr) && rinfo->orclause == NULL);
+
 		if (rinfo->outer_is_left)
 		{
 			oeclass = rinfo->left_ec;
 			ieclass = rinfo->right_ec;
+			src_expr = (Expr *) lsecond(((OpExpr *) rinfo->clause)->args);
 		}
 		else
 		{
 			oeclass = rinfo->right_ec;
 			ieclass = rinfo->left_ec;
+			src_expr = (Expr *) linitial(((OpExpr *) rinfo->clause)->args);
 		}
 
 		/* outer eclass should match current or next pathkeys */
@@ -1891,7 +1911,8 @@ make_inner_pathkeys_for_merge(PlannerInfo *root,
 											 ieclass,
 											 opathkey->pk_opfamily,
 											 opathkey->pk_strategy,
-											 opathkey->pk_nulls_first);
+											 opathkey->pk_nulls_first,
+											 src_expr);
 
 		/*
 		 * Don't generate redundant pathkeys (which can happen if multiple
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 2ba297c117..7e99725e00 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1469,6 +1469,8 @@ typedef struct PathKey
 	Oid			pk_opfamily;	/* btree opfamily defining the ordering */
 	int			pk_strategy;	/* sort direction (ASC or DESC) */
 	bool		pk_nulls_first; /* do NULLs come before normal values? */
+
+	Expr	   *source_expr;	/* Expression, which triggered this creation */
 } PathKey;
 
 /*
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 5e88c0224a..4b99229ebf 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -264,7 +264,8 @@ extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
 extern List *append_pathkeys(List *target, List *source);
 extern PathKey *make_canonical_pathkey(PlannerInfo *root,
 									   EquivalenceClass *eclass, Oid opfamily,
-									   int strategy, bool nulls_first);
+									   int strategy, bool nulls_first,
+									   Expr *src_expr);
 extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 									List *live_childrels);
 
-- 
2.45.2