From 7a3a7facd15d2c0034eeff7041df56a4e0d456f4 Mon Sep 17 00:00:00 2001 From: Tomas Vondra 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; imutatorNColumns; 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