0004-fixup-comments-cleanup-type-fixes-and-rewor-20220328.patch

From 7a3a7facd15d2c0034eeff7041df56a4e0d456f4 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Tue, 29 Mar 2022 01:12:15 +0200
Subject: [PATCH 4/7] fixup: comments cleanup, type fixes and rewording

---
 src/backend/optimizer/path/costsize.c   | 124 +++++++++++++-----------
 src/backend/optimizer/path/equivclass.c |   6 +-
 src/backend/optimizer/path/pathkeys.c   |  68 ++++++-------
 src/backend/utils/adt/selfuncs.c        |  13 ++-
 4 files changed, 105 insertions(+), 106 deletions(-)

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index f4f7ce01065..bb0fe0c22ee 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1773,9 +1773,9 @@ is_fake_var(Expr *expr)
 
 /*
  * get_width_cost_multiplier
- *		Returns relative complexity of comparing two values based on it's width.
- * The idea behind - long values have more expensive comparison. Return value is
- * in cpu_operator_cost unit.
+ *		Returns relative complexity of comparing two values based on its width.
+ * The idea behind is that the comparison becomes more expensive the longer the
+ * value is. Return value is in cpu_operator_cost units.
  */
 static double
 get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
@@ -1806,7 +1806,7 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
 		}
 	}
 
-	/* Didn't find any actual stats, use estimation by type */
+	/* Didn't find any actual stats, try using type width instead. */
 	if (width < 0.0)
 	{
 		Node	*node = (Node*) expr;
@@ -1815,17 +1815,20 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
 	}
 
 	/*
-	 * Any value in pgsql is passed by Datum type, so any operation with value
-	 * could not be cheaper than operation with Datum type
+	 * Values are passed as Datum type, so comparisons can't be cheaper than
+	 * comparing a Datum value.
+	 *
+	 * FIXME I find this reasoning questionable. We may pass int2, and comparing
+	 * it is probably a bit cheaper than comparing a bigint.
 	 */
 	if (width <= sizeof(Datum))
 		return 1.0;
 
 	/*
-	 * Seems, cost of comparision is not directly proportional to args width,
-	 * because comparing args could be differ width (we known only average over
-	 * column) and difference often could be defined only by looking on first
-	 * bytes. So, use log16(width) as estimation.
+	 * We consider the cost of a comparison not to be directly proportional to
+	 * width of the argument, because widths of the arguments could be slightly
+	 * different (we only know the average width for the whole column). So we
+	 * use log16(width) as an estimate.
 	 */
 	return 1.0 + 0.125 * LOG2(width / sizeof(Datum));
 }
@@ -1837,11 +1840,11 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
  * The main thing we need to calculate to estimate sort CPU costs is the number
  * of calls to the comparator functions. The difficulty is that for multi-column
  * sorts there may be different data types involved (for some of which the calls
- * may be much more expensive). Furthermore, the columns may have very different
+ * may be much more expensive). Furthermore, columns may have a very different
  * number of distinct values - the higher the number, the fewer comparisons will
  * be needed for the following columns.
  *
- * The algoritm is incremental - we add pathkeys one by one, and at each step we
+ * The algorithm is incremental - we add pathkeys one by one, and at each step we
  * estimate the number of necessary comparisons (based on the number of distinct
  * groups in the current pathkey prefix and the new pathkey), and the comparison
  * costs (which is data type specific).
@@ -1892,7 +1895,6 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 	bool		has_fake_var = false;
 	int			i = 0;
 	Oid			prev_datatype = InvalidOid;
-	Cost		funcCost = 0.0;
 	List		*cache_varinfos = NIL;
 
 	/* fallback if pathkeys is unknown */
@@ -1901,12 +1903,8 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 		/*
 		 * If we'll use a bounded heap-sort keeping just K tuples in memory, for
 		 * a total number of tuple comparisons of N log2 K; but the constant
-		 * factor is a bit higher than for quicksort.  Tweak it so that the
-		 * cost curve is continuous at the crossover point.
-		 *
-		 * XXX I suppose the "quicksort factor" references to 1.5 at the end
-		 * of this function, but I'm not sure. I suggest we introduce some simple
-		 * constants for that, instead of magic values.
+		 * factor is a bit higher than for quicksort. Tweak it so that the cost
+		 * curve is continuous at the crossover point.
 		 */
 		output_tuples = (heapSort) ? 2.0 * output_tuples : tuples;
 		per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples);
@@ -1924,20 +1922,21 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 	 */
 	foreach(lc, pathkeys)
 	{
-		PathKey				*pathkey = (PathKey*) lfirst(lc);
-		EquivalenceMember	*em;
-		double				 nGroups,
-							 correctedNGroups;
+		PathKey			   *pathkey = (PathKey*) lfirst(lc);
+		EquivalenceMember  *em;
+		double				nGroups,
+							correctedNGroups;
+		Cost				funcCost = 1.0;
 
 		/*
 		 * We believe that equivalence members aren't very different, so, to
-		 * estimate cost we take just first member
+		 * estimate cost we consider just the first member.
 		 */
 		em = (EquivalenceMember *) linitial(pathkey->pk_eclass->ec_members);
 
 		if (em->em_datatype != InvalidOid)
 		{
-			/* do not lookup funcCost if data type is the same as previous */
+			/* do not lookup funcCost if the data type is the same */
 			if (prev_datatype != em->em_datatype)
 			{
 				Oid			sortop;
@@ -1950,54 +1949,56 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 				cost.startup = 0;
 				cost.per_tuple = 0;
 				add_function_cost(root, get_opcode(sortop), NULL, &cost);
-				/* we need procost, not product of procost and cpu_operator_cost */
+
+				/*
+				 * add_function_cost returns the product of cpu_operator_cost
+				 * and procost, but we need just procost, co undo that.
+				 */
 				funcCost = cost.per_tuple / cpu_operator_cost;
+
 				prev_datatype = em->em_datatype;
 			}
 		}
-		else
-			funcCost = 1.0; /* fallback */
 
-		/* Try to take into account actual width fee */
+		/* factor in the width of the values in this column */
 		funcCost *= get_width_cost_multiplier(root, em->em_expr);
 
+		/* now we have per-key cost, so add to the running total */
 		totalFuncCost += funcCost;
 
-		/* Remember if we have a fake var in pathkeys */
+		/* remember if we have found a fake Var in pathkeys */
 		has_fake_var |= is_fake_var(em->em_expr);
 		pathkeyExprs = lappend(pathkeyExprs, em->em_expr);
 
 		/*
-		 * Prevent call estimate_num_groups() with fake Var. Note,
-		 * pathkeyExprs contains only previous columns
+		 * We need to calculate the number of comparisons for this column, which
+		 * requires knowing the group size. So we estimate the number of groups
+		 * by calling estimate_num_groups_incremental(), which estimates the
+		 * group size for "new" pathkeys.
+		 *
+		 * Note: estimate_num_groups_incremntal does not handle fake Vars, so use
+		 * a default estimate otherwise.
 		 */
-		if (has_fake_var == false)
-			/*
-			 * Recursively compute number of groups in a group from previous step
-			 */
+		if (!has_fake_var)
 			nGroups = estimate_num_groups_incremental(root, pathkeyExprs,
 													  tuplesPerPrevGroup, NULL, NULL,
 													  &cache_varinfos,
 													  list_length(pathkeyExprs) - 1);
 		else if (tuples > 4.0)
 			/*
-			 * Use geometric mean as estimation if there is no any stats.
-			 * Don't use DEFAULT_NUM_DISTINCT because it used for only one
-			 * column while here we try to estimate number of groups over
-			 * set of columns.
-			 *
-			 * XXX Perhaps this should use DEFAULT_NUM_DISTINCT at least to
-			 * limit the calculated values, somehow?
+			 * Use geometric mean as estimation if there are no stats.
 			 *
-			 * XXX What's the logic of the following formula?
+			 * We don't use DEFAULT_NUM_DISTINCT here, because that’s used for
+			 * a single column, but here we’re dealing with multiple columns.
 			 */
 			nGroups = ceil(2.0 + sqrt(tuples) * (i + 1) / list_length(pathkeys));
 		else
 			nGroups = tuples;
 
 		/*
-		 * Presorted keys aren't participated in comparison but still checked
-		 * by qsort comparator.
+		 * Presorted keys are not considered in the cost above, but we still do
+		 * have to compare them in the qsort comparator. So make sure to factor
+		 * in the cost in that case.
 		 */
 		if (i >= nPresortedKeys)
 		{
@@ -2006,10 +2007,13 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 				double heap_tuples;
 
 				/* have to keep at least one group, and a multiple of group size */
+				/* FIXME Do we actually need the Max, here? Surely the ceil() returns
+				 * at least 1.0 here, no? */
 				heap_tuples = Max(ceil(output_tuples / tuplesPerPrevGroup) * tuplesPerPrevGroup,
 								  tuplesPerPrevGroup);
 
 				/* so how many (whole) groups is that? */
+				/* FIXME so why not just ceil(putput_tuples / tuplesPerPrevGroup)? */
 				correctedNGroups = ceil(heap_tuples / tuplesPerPrevGroup);
 			}
 			else
@@ -2024,17 +2028,19 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 		i++;
 
 		/*
-		 * Real-world distribution isn't uniform but now we don't have a way to
-		 * determine that, so, add multiplier to get closer to worst case.
-		 * But ensure the number of tuples does not exceed the group size in the
-		 * preceding step.
+		 * Uniform distributions with all groups being of the same size are the
+		 * best case, with nice smooth behavior. Real-world distributions tend
+		 * not to be uniform, though, and we don’t have any reliable easy-to-use
+		 * information. As a basic defense against skewed distributions, we use
+		 * a 1.5 factor to make the expected group a bit larger, but we need to
+		 * be careful not to make the group larger than in the preceding step.
 		 */
 		tuplesPerPrevGroup = Min(tuplesPerPrevGroup,
 								 ceil(1.5 * tuplesPerPrevGroup / nGroups));
 
 		/*
-		 * We could skip all following columns for cost estimation, because we
-		 * believe that tuples are unique by the set of previous columns
+		 * Once we get single-row group, it means tuples in the group are unique
+		 * and we can skip all remaining columns.
 		 */
 		if (tuplesPerPrevGroup <= 1.0)
 			break;
@@ -2049,12 +2055,12 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 	 * Accordingly to "Introduction to algorithms", Thomas H. Cormen, Charles E.
 	 * Leiserson, Ronald L. Rivest, ISBN 0-07-013143-0, quicksort estimation
 	 * formula has additional term proportional to number of tuples (See Chapter
-	 * 8.2 and Theorem 4.1). It has meaning with low number of tuples,
-	 * approximately less that 1e4. Of course, it could be implemented as
-	 * additional multiplier under logarithm, but use more complicated formula
-	 * which takes into account number of unique tuples and it isn't clear how
-	 * to combine multiplier with groups. Estimate it as 10 in cpu_operator_cost
-	 * unit.
+	 * 8.2 and Theorem 4.1). That affects  cases with a low number of tuples,
+	 * approximately less than 1e4. We could implement it as an additional
+	 * multiplier under the logarithm, but we use a bit more complex formula
+	 * which takes into account the number of unique tuples and it’s not clear
+	 * how to combine the multiplier with the number of groups. Estimate it as
+	 * 10 in cpu_operator_cost unit.
 	 */
 	per_tuple_cost += 10 * cpu_operator_cost;
 
@@ -2110,7 +2116,7 @@ cost_sort_estimate(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
  * 'sort_mem' is the number of kilobytes of work memory allowed for the sort
  * 'limit_tuples' is the bound on the number of output tuples; -1 if no bound
  * 'startup_cost' is expected to be 0 at input. If there is "input cost" it should
- * be added by caller later.
+ * be added by caller later
  */
 static void
 cost_tuplesort(PlannerInfo *root, List *pathkeys, Cost *startup_cost, Cost *run_cost,
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 5487ae2ee4c..258302840f8 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -685,9 +685,9 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 				/*
 				 * 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
+				 * Copy the sortref if it wasn't set yet. That may happen if the
+				 * ec was constructed from WHERE clause, i.e. it doesn't have a
+				 * target reference at all.
 				 */
 				if (cur_ec->ec_sortref == 0 && sortref > 0)
 					cur_ec->ec_sortref = sortref;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index fcc99f0fb1c..7913d62625d 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -362,12 +362,12 @@ group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
 
 	/*
 	 * Walk the pathkeys (determining ordering of the input path) and see if
-	 * there's a matching GROUP BY key. If we find one, we append if to the
+	 * there's a matching GROUP BY key. If we find one, we append it to the
 	 * list, and do the same for the clauses.
 	 *
-	 * Once we find first pathkey without a matching GROUP BY key, the rest of
-	 * the pathkeys is useless and can't be used to evaluate the grouping, so
-	 * we abort the loop and ignore the remaining pathkeys.
+	 * Once we find the first pathkey without a matching GROUP BY key, the rest
+	 * of the pathkeys are useless and can't be used to evaluate the grouping,
+	 * so we abort the loop and ignore the remaining pathkeys.
 	 *
 	 * XXX Pathkeys are built in a way to allow simply comparing pointers.
 	 */
@@ -391,8 +391,6 @@ group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
 	/* remember the number of pathkeys with a matching GROUP BY key */
 	n = list_length(new_group_pathkeys);
 
-	/* XXX maybe return when (n == 0) */
-
 	/* append the remaining group pathkeys (will be treated as not sorted) */
 	*group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
 											 *group_pathkeys);
@@ -530,7 +528,7 @@ PathkeyMutatorNext(PathkeyMutatorState *state)
 	}
 
 	/* update the list cells to point to the right elements */
-	for(i=0; i<state->mutatorNColumns; i++)
+	for(i = 0; i < state->mutatorNColumns; i++)
 		lfirst(state->elemCells[i]) =
 			(void *) state->elems[ state->positions[i] - 1 ];
 
@@ -597,18 +595,18 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
 
 	/*
 	 * We could exhaustively cost all possible orderings of the pathkeys, but for
-	 * large number of pathkeys that might be prohibitively expensive. So we try
-	 * to apply a simple cheap heuristics first - we sort the pathkeys by sort
-	 * cost (as if the pathkey was sorted independently) and then check only the
-	 * four cheapest pathkeys. The remaining pathkeys are kept ordered by cost.
+	 * a large number of pathkeys it might be prohibitively expensive. So we try
+	 * to apply simple cheap heuristics first - we sort the pathkeys by sort cost
+	 * (as if the pathkey was sorted independently) and then check only the four
+	 * cheapest pathkeys. The remaining pathkeys are kept ordered by cost.
 	 *
-	 * XXX This is a very simple heuristics, and likely to work fine for most
-	 * cases (because number of GROUP BY clauses tends to be lower than 4). But
-	 * it ignores how the number of distinct values in each pathkey affects the
-	 * following sorts. It may be better to use "more expensive" pathkey first
-	 * if it has many distinct values, because it then limits the number of
-	 * comparisons for the remaining pathkeys. But evaluating that is kinda the
-	 * expensive bit we're trying to not do.
+	 * XXX This is a very simple heuristics, but likely to work fine for most
+	 * cases (because the number of GROUP BY clauses tends to be lower than 4).
+	 * But it ignores how the number of distinct values in each pathkey affects
+	 * the following steps. It might be better to use "more expensive" pathkey
+	 * first if it has many distinct values, because it then limits the number
+	 * of comparisons for the remaining pathkeys. But evaluating that is likely
+	 * quite the expensive.
 	 */
 	nFreeKeys = list_length(*group_pathkeys) - n_preordered;
 	nToPermute = 4;
@@ -649,11 +647,7 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
 	}
 	else
 	{
-		/*
-		 * Since v13 list_free() can clean list elements so for original list
-		 * not to be modified it should be copied to a new one which can then
-		 * be cleaned safely if needed.
-		 */
+		/* Copy the list, so that we can free the new list by list_free. */
 		new_group_pathkeys = list_copy(*group_pathkeys);
 		nToPermute = nFreeKeys;
 	}
@@ -667,18 +661,16 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
 	 * there's room for two dynamic programming optimizations here. Firstly, we
 	 * may pass the current "best" cost to cost_sort_estimate so that it can
 	 * "abort" if the estimated pathkeys list exceeds it. Secondly, it could pass
-	 * return information about the position when it exceeded the cost, and we
-	 * could skip all permutations with the same prefix.
+	 * the return information about the position when it exceeded the cost, and
+	 * we could skip all permutations with the same prefix.
 	 *
 	 * Imagine we've already found ordering with cost C1, and we're evaluating
 	 * another ordering - cost_sort_estimate() calculates cost by adding the
 	 * pathkeys one by one (more or less), and the cost only grows. If at any
 	 * point it exceeds C1, it can't possibly be "better" so we can discard it.
 	 * But we also know that we can discard all ordering with the same prefix,
-	 * because if we're estimating (a,b,c,d) and we exceeded C1 at (a,b) then
-	 * the same thing will happen for any ordering with this prefix.
-	 *
-	 *
+	 * because if we're estimating (a,b,c,d) and we exceed C1 at (a,b) then the
+	 * same thing will happen for any ordering with this prefix.
 	 */
 	PathkeyMutatorInit(&mstate, new_group_pathkeys, n_preordered, n_preordered + nToPermute);
 
@@ -721,7 +713,7 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
  *		Determine which orderings of GROUP BY keys are potentially interesting.
  *
  * Returns list of PathKeyInfo items, each representing an interesting ordering
- * of GROUP BY keys. Each items stores pathkeys and clauses in matching order.
+ * of GROUP BY keys. Each item stores pathkeys and clauses in matching order.
  *
  * The function considers (and keeps) multiple group by orderings:
  *
@@ -730,15 +722,15 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
  * - GROUP BY keys reordered to minimize the sort cost
  *
  * - GROUP BY keys reordered to match path ordering (as much as possible), with
- *   the tail reoredered to minimize the sort cost
+ *   the tail reordered to minimize the sort cost
  *
  * - GROUP BY keys to match target ORDER BY clause (as much as possible), with
- *   the tail reoredered to minimize the sort cost
+ *   the tail reordered to minimize the sort cost
  *
  * There are other potentially interesting orderings (e.g. it might be best to
  * match the first ORDER BY key, order the remaining keys differently and then
- * rely on incremental sort to fix this), but we ignore those for now. To make
- * this work we'd have to pretty much generate all possible permutations.
+ * rely on the incremental sort to fix this), but we ignore those for now. To
+ * make this work we'd have to pretty much generate all possible permutations.
  */
 List *
 get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
@@ -761,8 +753,9 @@ get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
 	infos = lappend(infos, info);
 
 	/*
-	 * If the optimization is disabled, we consider only the pathkey order as
-	 * specified in the query. We don't do any reorderings.
+	 * Should we try generating alternative orderings of the group keys? If not,
+	 * we produce only the order specified in the query, i.e. the optimization
+	 * is effectively disabled.
 	 */
 	if (!enable_group_by_reordering)
 		return infos;
@@ -826,9 +819,6 @@ get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
 	/*
 	 * Try reordering pathkeys to minimize the sort cost (this time consider
 	 * the ORDER BY clause, but only if set debug_group_by_match_order_by).
-	 *
-	 * XXX This does nothing if (n_preordered == 0). We shouldn't create the
-	 * info in this case.
 	 */
 	if (root->sort_pathkeys)
 	{
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 36c303e45c5..fb4fb987e7f 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3294,10 +3294,7 @@ add_unique_group_var(PlannerInfo *root, List *varinfos,
 }
 
 /*
- * estimate_num_groups/estimate_num_groups_incremental
- *		- Estimate number of groups in a grouped query.
- *		  _incremental variant is performance optimization for
- *		  case of adding one-by-one column
+ * estimate_num_groups		- Estimate number of groups in a grouped query
  *
  * Given a query having a GROUP BY clause, estimate how many groups there
  * will be --- ie, the number of distinct combinations of the GROUP BY
@@ -3376,6 +3373,11 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
 										   NULL, 0);
 }
 
+/*
+ * estimate_num_groups_incremental
+ *		An estimate_num_groups variant, optimized for cases that are adding the
+ *		expressions incrementally (e.g. one by one).
+ */
 double
 estimate_num_groups_incremental(PlannerInfo *root, List *groupExprs,
 					double input_rows,
@@ -3386,7 +3388,8 @@ estimate_num_groups_incremental(PlannerInfo *root, List *groupExprs,
 	double		srf_multiplier = 1.0;
 	double		numdistinct;
 	ListCell   *l;
-	int			i, j;
+	int			i,
+				j;
 
 	/* Zero the estinfo output parameter, if non-NULL */
 	if (estinfo != NULL)
-- 
2.34.1