Subject: Re: POC: GROUP BY optimization

From: "Andrey V. Lepikhov" <[email-masked]>
Date: Tue, 1 Feb 2022 14:48:11 +0500

> On 7/22/21 3:58 AM, Tomas Vondra wrote:
> I've simplified the costing a bit, and the attached version actually
> undoes all the "suspicious" plan changes in postgres_fdw. It changes one
> new plan, but that seems somewhat reasonable, as it pushes sort to the
> remote side.

I tried to justify heap-sort part of the compute_cpu_sort_cost() routine 
and realized, that here we may have a mistake.
After a week of efforts, I don't found any research papers on dependence 
of bounded heap-sort time compexity on number of duplicates.

So, I suppose self-made formula, based on simple logical constructions:

1. We should base on initial formula: cost ~ N*LOG2(M), where M - 
output_tuples.
2. Realize, that full representation of this formula is:

cost ~ N*LOG2(min{N,M})

3. In the case of multicolumn, number of comparisons for each next 
column can be estimated by the same formula, but arranged to a number of 
tuples per group:

comparisons ~ input * LOG2(min{input,M})

4. Realize, that for the case, when M > input, we should change this 
formula a bit:

comparisons ~ max{input,M} * LOG2(min{input,M})

Remember, that in our case M << tuples.
So, general formula for bounded heap sort can be written as:

cost ~ N * sum(max{n_i,M}/N * LOG2(min{n_i,M})), i=1,ncols

where n_1 == N, n_i - number of tuples per group, estimated from 
previous iteration.

In attachment - an implementation of this approach.

-- 
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 68a32740d7..2c3cce57aa 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1872,6 +1872,15 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
  *
  *	N * sum( Fk * log(Gk) )
  *
+ * For bounded heap sort we haven't such a duplicates-related research. So invent
+ * it based on a simple logic (M - number of output tuples):
+ * For one column we can estimate number of comparisons as:
+ * N * log(min{N,M})
+ * For the case of many columns we can natively estimate number of comparisons by
+ * the formula:
+ * sum(max{n_i,M} * log(min{N,M})),
+ * where n_0 == N, n_i - number of tuples per group, estimated on previous step.
+ *
  * Note: We also consider column width, not just the comparator cost.
  *
  * NOTE: some callers currently pass NIL for pathkeys because they
@@ -1881,7 +1890,7 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
 static Cost
 compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 					  Cost comparison_cost, double tuples, double output_tuples,
-					  bool heapSort)
+					  bool bounded_sort)
 {
 	Cost		per_tuple_cost = 0.0;
 	ListCell	*lc;
@@ -1907,7 +1916,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 		 * of this function, but I'm not sure. I suggest we introduce some simple
 		 * constants for that, instead of magic values.
 		 */
-		output_tuples = (heapSort) ? 2.0 * output_tuples : tuples;
+		output_tuples = (bounded_sort) ? 2.0 * output_tuples : tuples;
 		per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples);
 
 		/* add cost provided by caller */
@@ -1925,8 +1934,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 	{
 		PathKey				*pathkey = (PathKey*) lfirst(lc);
 		EquivalenceMember	*em;
-		double				 nGroups,
-							 correctedNGroups;
+		double				 nGroups;
 
 		/*
 		 * We believe that equivalence members aren't very different, so, to
@@ -2000,24 +2008,16 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
 		 */
 		if (i >= nPresortedKeys)
 		{
-			if (heapSort)
-			{
-				double heap_tuples;
-
-				/* have to keep at least one group, and a multiple of group size */
-				heap_tuples = Max(ceil(output_tuples / tuplesPerPrevGroup) * tuplesPerPrevGroup,
-								  tuplesPerPrevGroup);
-
-				/* so how many (whole) groups is that? */
-				correctedNGroups = ceil(heap_tuples / tuplesPerPrevGroup);
-			}
+			/*
+			 * Quick sort and 'top-N' sorting (bounded heap sort) algorithms
+			 * have different formulas for time complexity estimation.
+			 */
+			if (bounded_sort)
+				per_tuple_cost += totalFuncCost *
+								  (Max(tuplesPerPrevGroup, output_tuples) / tuples) *
+								  LOG2(2.0 * Min(tuplesPerPrevGroup, output_tuples));
 			else
-				/* all groups in the input */
-				correctedNGroups = nGroups;
-
-			correctedNGroups = Max(1.0, ceil(correctedNGroups));
-
-			per_tuple_cost += totalFuncCost * LOG2(correctedNGroups);
+				per_tuple_cost += totalFuncCost * LOG2(nGroups);
 		}
 
 		i++;