V8 contains fixes of Tomas Vondra complaints:
- correct usage of comparison_cost
- remove uneeded check of sortop
--
Teodor Sigaev E-mail: [email protected]
WWW: http://www.sigaev.ru/
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index a2a7e0c520..521a7d3c9a 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1612,6 +1612,250 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
rterm->pathtarget->width);
}
+/*
+ * is_fake_var
+ * Workaround for generate_append_tlist() which generates fake Vars with
+ * varno == 0, that will cause a fail of estimate_num_group() call
+ */
+static bool
+is_fake_var(Expr *expr)
+{
+ if (IsA(expr, RelabelType))
+ expr = (Expr *) ((RelabelType *) expr)->arg;
+
+ return (IsA(expr, Var) && ((Var *) expr)->varno == 0);
+}
+
+/*
+ * get_width_cost_multiplier
+ * Returns relative complexity of comparing two valyes based on it's width.
+ * The idea behind - long values have more expensive comparison. Return value is
+ * in cpu_operator_cost unit.
+ */
+static double
+get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
+{
+ double width = -1.0; /* fake value */
+
+ if (IsA(expr, RelabelType))
+ expr = (Expr *) ((RelabelType *) expr)->arg;
+
+ /* Try to find actual stat in corresonding relation */
+ if (IsA(expr, Var))
+ {
+ Var *var = (Var *) expr;
+
+ if (var->varno > 0 && var->varno < root->simple_rel_array_size)
+ {
+ RelOptInfo *rel = root->simple_rel_array[var->varno];
+
+ if (rel != NULL &&
+ var->varattno >= rel->min_attr &&
+ var->varattno <= rel->max_attr)
+ {
+ int ndx = var->varattno - rel->min_attr;
+
+ if (rel->attr_widths[ndx] > 0)
+ width = rel->attr_widths[ndx];
+ }
+ }
+ }
+
+ /* Didn't find any actual stats, use estimation by type */
+ if (width < 0.0)
+ {
+ Node *node = (Node*) expr;
+
+ width = get_typavgwidth(exprType(node), exprTypmod(node));
+ }
+
+ /*
+ * Any value in pgsql is passed by Datum type, so any operation with value
+ * could not be cheaper than operation with Datum type
+ */
+ 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.
+ */
+ return 1.0 + 0.125 * LOG2(width / sizeof(Datum));
+}
+
+/*
+ * compute_cpu_sort_cost
+ * compute CPU cost of sort (i.e. in-memory)
+ *
+ * NOTE: some callers currently pass NIL for pathkeys because they
+ * can't conveniently supply the sort keys. In this case, it will fallback to
+ * simple comparison cost estimate.
+ *
+ * Estimation algorithm is based on ideas from course Algorithms,
+ * Robert Sedgewick, Kevin Wayne, https://algs4.cs.princeton.edu/home/ and paper
+ * "Quicksort Is Optimal For Many Equal Keys", Sebastian Wild,
+ * arXiv:1608.04906v4 [cs.DS] 1 Nov 2017.
+ *
+ * In term of that papers, let N - number of tuples, Xi - number of tuples with
+ * key Ki, then estimation is:
+ * log(N! / (X1! * X2! * ..)) ~ sum(Xi * log(N/Xi))
+ * In our case all Xi are the same because noew we don't have an estimation of
+ * group sizes, we have only estimation of number of groups. In this case,
+ * formula becomes: N * log(NumberOfGroups). Next, to support correct estimation
+ * of multicolumn sort we need separately compute each column, so, let k is a
+ * column number, Gk - number of groups defined by k columns:
+ * N * sum( Fk * log(Gk) )
+ * Fk is sum of functions costs for k columns.
+ */
+
+static Cost
+compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys,
+ Cost comparison_cost,
+ double tuples, double output_tuples, bool heapSort)
+{
+ Cost per_tuple_cost = 0.0;
+ ListCell *lc;
+ List *pathkeyExprs = NIL;
+ double tuplesPerPrevGroup = tuples;
+ bool has_fake_var = false;
+ double totalFuncCost = 0.0;
+
+ /* fallback if pathkeys is unknown */
+ if (list_length(pathkeys) == 0)
+ {
+ /*
+ * 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.
+ */
+ output_tuples = (heapSort) ? 2.0 * output_tuples : tuples;
+ per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples);
+
+ return per_tuple_cost * tuples;
+ }
+
+ totalFuncCost = 1.0;
+
+ /*
+ * Computing total cost of sorting takes into account:
+ * - per column comparison function cost
+ * - we try to compute needed number of comparison per column
+ */
+
+ foreach(lc, pathkeys)
+ {
+ PathKey *pathkey = (PathKey*)lfirst(lc);
+ Cost funcCost = 1.0; /* fallback value */
+ EquivalenceMember *em;
+ double nGroups,
+ correctedNGroups;
+
+ /*
+ * 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);
+
+ if (em->em_datatype != InvalidOid)
+ {
+ Oid sortop;
+
+ sortop = get_opfamily_member(pathkey->pk_opfamily,
+ em->em_datatype, em->em_datatype,
+ pathkey->pk_strategy);
+
+ funcCost = get_func_cost(get_opcode(sortop));
+ }
+
+ /* Try to take into account actual width fee */
+ funcCost *= get_width_cost_multiplier(root, em->em_expr);
+
+ totalFuncCost += funcCost;
+
+ /* remeber if we have 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
+ */
+ if (has_fake_var == false)
+ /*
+ * Recursively defin number of group in group from previous step
+ */
+ nGroups = estimate_num_groups(root, pathkeyExprs,
+ tuplesPerPrevGroup, NULL);
+ 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.
+ */
+ nGroups = ceil(2.0 + sqrt(tuples) *
+ list_length(pathkeyExprs) / list_length(pathkeys));
+ else
+ nGroups = tuples;
+
+ if (heapSort)
+ {
+ if (tuplesPerPrevGroup < output_tuples)
+ /* comparing only inside output_tuples */
+ correctedNGroups =
+ ceil(2.0 * output_tuples / (tuplesPerPrevGroup / nGroups));
+ else
+ /* two groups - in output and out */
+ correctedNGroups = 2.0;
+ }
+ else
+ correctedNGroups = nGroups;
+
+ per_tuple_cost += totalFuncCost * LOG2(correctedNGroups);
+
+ /*
+ * 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.
+ */
+ tuplesPerPrevGroup = ceil(1.5 * tuples / nGroups);
+ if (tuplesPerPrevGroup > tuples)
+ tuplesPerPrevGroup = tuples;
+
+ /*
+ * We could skip all followed columns for cost estimation, because we
+ * believe that tuples are unique by set ot previous columns
+ */
+ if (tuples <= nGroups)
+ break;
+ }
+
+ list_free(pathkeyExprs);
+
+ /* per_tuple_cost is in cpu_operator_cost units */
+ per_tuple_cost *= cpu_operator_cost;
+
+ /*
+ * 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 inmplemented 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.
+ */
+ per_tuple_cost += 10 * cpu_operator_cost;
+
+ /* add cost provided by caller */
+ per_tuple_cost += comparison_cost;
+
+ return tuples * per_tuple_cost;
+}
+
/*
* cost_sort
* Determines and returns the cost of sorting a relation, including
@@ -1628,7 +1872,7 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
* number of initial runs formed and M is the merge order used by tuplesort.c.
* Since the average initial run should be about sort_mem, we have
* disk traffic = 2 * relsize * ceil(logM(p / sort_mem))
- * cpu = comparison_cost * t * log2(t)
+ * and cpu cost computed by compute_cpu_sort_cost().
*
* If the sort is bounded (i.e., only the first k result tuples are needed)
* and k tuples can fit into sort_mem, we use a heap method that keeps only
@@ -1649,13 +1893,6 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
* 'comparison_cost' is the extra cost per comparison, if any
* '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
- *
- * NOTE: some callers currently pass NIL for pathkeys because they
- * can't conveniently supply the sort keys. Since this routine doesn't
- * currently do anything with pathkeys anyway, that doesn't matter...
- * but if it ever does, it should react gracefully to lack of key data.
- * (Actually, the thing we'd most likely be interested in is just the number
- * of sort keys, which all callers *could* supply.)
*/
void
cost_sort(Path *path, PlannerInfo *root,
@@ -1682,9 +1919,6 @@ cost_sort(Path *path, PlannerInfo *root,
if (tuples < 2.0)
tuples = 2.0;
- /* Include the default cost-per-comparison */
- comparison_cost += 2.0 * cpu_operator_cost;
-
/* Do we have a useful LIMIT? */
if (limit_tuples > 0 && limit_tuples < tuples)
{
@@ -1713,7 +1947,9 @@ cost_sort(Path *path, PlannerInfo *root,
*
* Assume about N log2 N comparisons
*/
- startup_cost += comparison_cost * tuples * LOG2(tuples);
+ startup_cost += compute_cpu_sort_cost(root, pathkeys,
+ comparison_cost, tuples,
+ tuples, false);
/* Disk costs */
@@ -1729,18 +1965,17 @@ cost_sort(Path *path, PlannerInfo *root,
}
else if (tuples > 2 * output_tuples || input_bytes > sort_mem_bytes)
{
- /*
- * 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.
- */
- startup_cost += comparison_cost * tuples * LOG2(2.0 * output_tuples);
+ /* We'll use a bounded heap-sort keeping just K tuples in memory. */
+ startup_cost += compute_cpu_sort_cost(root, pathkeys,
+ comparison_cost, tuples,
+ output_tuples, true);
}
else
{
/* We'll use plain quicksort on all the input tuples */
- startup_cost += comparison_cost * tuples * LOG2(tuples);
+ startup_cost += compute_cpu_sort_cost(root, pathkeys,
+ comparison_cost, tuples,
+ tuples, false);
}
/*
