public inbox for [email protected]help / color / mirror / Atom feed
[PATCH 2/2] review 2+ messages / 2 participants [nested] [flat]
* [PATCH 2/2] review @ 2021-03-09 20:09 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 2+ messages in thread From: Tomas Vondra @ 2021-03-09 20:09 UTC (permalink / raw) --- src/backend/optimizer/path/costsize.c | 77 ++++++++++++++++++++------- src/backend/optimizer/path/pathkeys.c | 14 ++++- 2 files changed, 69 insertions(+), 22 deletions(-) diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 1639258aaf..f55a4f20e5 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -1755,6 +1755,8 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm) * 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 + * + * XXX Ummm, why would estimate_num_group fail with this? */ static bool is_fake_var(Expr *expr) @@ -1828,27 +1830,53 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr) * compute_cpu_sort_cost * compute CPU cost of sort (i.e. in-memory) * + * 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 + * 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 + * 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). + * + * Estimation of the number of comparisons is based on ideas from two sources: + * + * 1) "Algorithms" (course), Robert Sedgewick, Kevin Wayne [https://algs4.cs.princeton.edu/home/] + * + * 2) "Quicksort Is Optimal For Many Equal Keys" (paper), Sebastian Wild, + * arXiv:1608.04906v4 [cs.DS] 1 Nov 2017. [https://arxiv.org/abs/1608.04906] + * + * In term of that paper, let N - number of tuples, Xi - number of tuples with + * key Ki, then the estimate of number of comparisons is: + * + * log(N! / (X1! * X2! * ..)) ~ sum(Xi * log(N/Xi)) + * + * In our case all Xi are the same because now we don't have any estimation of + * group sizes, we have only know the estimate of number of groups (distinct + * values). In that case, formula becomes: + * + * N * log(NumberOfGroups) + * + * For multi-column sorts we need to estimate the number of comparisons for + * each individual column - for example with columns (c1, c2, ..., ck) we + * can estimate that number of comparions on ck is roughly + * + * ncomparisons(c1, c2, ..., ck) / ncomparisons(c1, c2, ..., c(k-1)) + * + * Let k be a column number, Gk - number of groups defined by k columns, and Fk + * the cost of the comparison is + * + * N * sum( Fk * log(Gk) ) + * + * Note: We also consider column witdth, not just the comparator cost. + * * 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 now 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 multi-column 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 a function costs (including width) for k columns. */ - static Cost compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, Cost comparison_cost, double tuples, double output_tuples, @@ -1862,7 +1890,7 @@ 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.; + Cost funcCost = 0.0; List *cache_varinfos = NIL; /* fallback if pathkeys is unknown */ @@ -1873,6 +1901,10 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, * 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. */ output_tuples = (heapSort) ? 2.0 * output_tuples : tuples; per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples); @@ -1888,7 +1920,6 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, * - per column comparison function cost * - we try to compute needed number of comparison per column */ - foreach(lc, pathkeys) { PathKey *pathkey = (PathKey*)lfirst(lc); @@ -1952,6 +1983,11 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, * 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? + * + * XXX What's the logic of the following formula? */ nGroups = ceil(2.0 + sqrt(tuples) * list_length(pathkeyExprs) / list_length(pathkeys)); @@ -1968,6 +2004,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, { if (tuplesPerPrevGroup < output_tuples) /* comparing only inside output_tuples */ + /* XXX why not to use the same multiplier (1.5)? */ correctedNGroups = ceil(2.0 * output_tuples / (tuplesPerPrevGroup / nGroups)); else @@ -1993,7 +2030,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, tuplesPerPrevGroup = ceil(1.5 * tuplesPerPrevGroup / nGroups); /* - * We could skip all followed columns for cost estimation, because we + * We could skip all following columns for cost estimation, because we * believe that tuples are unique by set ot previous columns */ if (tuplesPerPrevGroup <= 1.0) diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 7beb32488a..b092c3e055 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -515,10 +515,19 @@ pathkey_sort_cost_comparator(const void *_a, const void *_b) return 0; return 1; } + /* * Order tail of list of group pathkeys by uniqueness descendetly. It allows to * speedup sorting. Returns newly allocated lists, old ones stay untouched. * n_preordered defines a head of list which order should be prevented. + * + * XXX But we're not generating this only based on uniqueness (that's a bad + * term anyway, because we're using ndistinct estimates, not uniqueness). + * We're also using the comparator cost to calculate the expected sort cost, + * and optimize that. + * + * XXX This should explain how we generate the values - all permutations for + * up to 4 values, etc. */ void get_cheapest_group_keys_order(PlannerInfo *root, double nrows, @@ -597,8 +606,9 @@ 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. + * 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. */ new_group_pathkeys = list_copy(*group_pathkeys); nToPermute = nFreeKeys; -- 2.29.2 --------------A955BFDEDE369DCD57A45C5A-- ^ permalink raw reply [nested|flat] 2+ messages in thread
* Re: daitch_mokotoff module @ 2022-01-03 13:07 Dag Lem <[email protected]> 0 siblings, 0 replies; 2+ messages in thread From: Dag Lem @ 2022-01-03 13:07 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Thomas Munro <[email protected]>; Andres Freund <[email protected]>; PostgreSQL Hackers <[email protected]> Tom Lane <[email protected]> writes: > Thomas Munro <[email protected]> writes: >> Erm, it looks like something weird is happening somewhere in cfbot's >> pipeline, because Dag's patch says: > >> +SELECT daitch_mokotoff('Straßburg'); >> + daitch_mokotoff >> +----------------- >> + 294795 >> +(1 row) > > ... so, that test case is guaranteed to fail in non-UTF8 encodings, > I suppose? I wonder what the LANG environment is in that cfbot > instance. > > (We do have methods for dealing with non-ASCII test cases, but > I can't see that this patch is using any of them.) > > regards, tom lane > I naively assumed that tests would be run in an UTF8 environment. Running "ack -l '[\x80-\xff]'" in the contrib/ directory reveals that two other modules are using UTF8 characters in tests - citext and unaccent. The citext tests seem to be commented out - "Multibyte sanity tests. Uncomment to run." Looking into the unaccent module, I don't quite understand how it will work with various encodings, since it doesn't seem to decode its input - will it fail if run under anything but ASCII or UTF8? In any case, I see that unaccent.sql starts as follows: CREATE EXTENSION unaccent; -- must have a UTF8 database SELECT getdatabaseencoding(); SET client_encoding TO 'UTF8'; Would doing the same thing in fuzzystrmatch.sql fix the problem with failing tests? Should I prepare a new patch? Best regards Dag Lem ^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2022-01-03 13:07 UTC | newest] Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-03-09 20:09 [PATCH 2/2] review Tomas Vondra <[email protected]> 2022-01-03 13:07 Re: daitch_mokotoff module Dag Lem <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox