Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1Z5Ecs-0003wT-UL for pgsql-hackers@arkaria.postgresql.org; Wed, 17 Jun 2015 14:47:39 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.80) (envelope-from ) id 1Z5Ecs-0001OR-A6 for pgsql-hackers@arkaria.postgresql.org; Wed, 17 Jun 2015 14:47:38 +0000 Received: from makus.postgresql.org ([2001:4800:1501:1::229]) by malur.postgresql.org with esmtps (TLS1.2:RSA_AES_256_CBC_SHA256:256) (Exim 4.80) (envelope-from ) id 1Z5Ecq-0001OL-OR for pgsql-hackers@postgresql.org; Wed, 17 Jun 2015 14:47:37 +0000 Received: from mail-ie0-f177.google.com ([209.85.223.177]) by makus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.84) (envelope-from ) id 1Z5Ecm-0001jc-FG for pgsql-hackers@postgresql.org; Wed, 17 Jun 2015 14:47:35 +0000 Received: by iebmu5 with SMTP id mu5so35288826ieb.1 for ; Wed, 17 Jun 2015 07:47:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to :cc:subject:references:in-reply-to:content-type; bh=J4gLhwGiOmXy5dc5xRsCZH7BDvxrRkp02/wEOhA8NC8=; b=gXFbS772gxXGBayuvXptXwGpf9PVYJNY0Y082x+F6suhK307uulKwiwpgkmP7dN09I STgGzThocvRwLqQGE+8XYR0JvNsPk4j6POB6skeepH2VbCb9P0uWHFcgT39OWjE6dtw6 l3YSLfB9S8vjdNUIe14ABRlH1NvncrnEbLwZl3Ahsh+0x0O5qw0gvswYIS9d+SSkx5H+ pDGNPs3zFRhkEIsrzm4FB+3mtw30+ApId+4DVqCU47VqKgWOLx/mdIZkoDmqcPivphTN mqeqvYltSy38rTzqW58LKeU6bEYil70cF0Y2UqFZZI0IfakAyFAtjmqfQqCSBHurKDGU HKHA== X-Gm-Message-State: ALoCoQk7k3pCETDr7mUyHCkx9jODIGj6xyDJtKZB79XD8FC5a9NyPHgbRHM89W/Yx5pqdYui5nDw7fkOJRoe/d0kaVFwI+5fCxhw2a7oTURXV1lXmksfViytS+dk8V5pimMEQ2h4l2uA2fWDLkZ1VtxXpCfy9jvmECuqxYf4DepWTG8Qe9C9j984WJsDxkP9qqR/U8rMQlg3 X-Received: by 10.107.168.13 with SMTP id r13mr8690172ioe.4.1434552451249; Wed, 17 Jun 2015 07:47:31 -0700 (PDT) Received: from [10.137.2.12] ([137.122.64.58]) by mx.google.com with ESMTPSA id qs10sm3297819igb.14.2015.06.17.07.47.30 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 17 Jun 2015 07:47:30 -0700 (PDT) Message-ID: <55818880.10300@2ndquadrant.com> Date: Wed, 17 Jun 2015 16:47:28 +0200 From: Tomas Vondra User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0 MIME-Version: 1.0 To: Jeff Janes CC: Robert Haas , "pgsql-hackers@postgresql.org" Subject: Re: PATCH: adaptive ndistinct estimator v4 References: <541A2335.3060100@agliodbs.com> <542C4E60.3030505@agliodbs.com> <542DADEB.2080103@agliodbs.com> <54381D20.9010501@fuzzy.cz> <5472416C.3080506@fuzzy.cz> <5483B346.6000203@fuzzy.cz> <551AEF45.7010700@2ndquadrant.com> <5542D4CF.5060700@2ndquadrant.com> In-Reply-To: Content-Type: multipart/mixed; boundary="------------060308050200090707040504" X-Pg-Spam-Score: -2.6 (--) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-hackers Precedence: bulk Sender: pgsql-hackers-owner@postgresql.org This is a multi-part message in MIME format. --------------060308050200090707040504 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Hi, On 05/13/15 23:07, Jeff Janes wrote: > With the warning it is very hard to correlate the discrepancy you do > see with which column is causing it, as the warnings don't include > table or column names (Assuming of course that you run it on a > substantial database--if you just run it on a few toy cases then the > warning works well). That's true. I've added attnum/attname to the warning in the attached version of the patch. > If we want to have an explicitly experimental patch which we want > people with interesting real-world databases to report back on, what > kind of patch would it have to be to encourage that to happen? Or are > we never going to get such feedback no matter how friendly we make > it? Another problem is that you really need to have the gold standard > to compare them to, and getting that is expensive (which is why we > resort to sampling in the first place). I don't think there is much > to be done on that front other than bite the bullet and just do > it--perhaps only for the tables which have discrepancies. Not sure. The "experimental" part of the patch was not really aimed at the users outside the development community - it was meant to be used by members of the community, possibly testing it on customer databases I don't think adding the GUC into the final release is a good idea, it's just a noise in the config no-one would actually use. > Some of the regressions I've seen are at least partly a bug: > > + /* find the 'm' value minimizing the difference */ > + for (m = 1; m <= total_rows; m += step) > + { > + double q = k / (sample_rows * m); > > sample_rows and m are both integers, and their product overflows > vigorously. A simple cast to double before the multiplication fixes > the first example I produced. The estimate goes from 137,177 to > 1,108,076. The reality is 1,062,223. > > Perhaps m should be just be declared a double, as it is frequently > used in double arithmetic. Yeah, I just discovered this bug independently. There's another bug that the adaptive_estimator takes total_rows as integer, so it breaks for tables with more than INT_MAX rows. Both are fixed in the v5. > > Therefore, I think that: > > 1. This should be committed near the beginning of a release cycle, > not near the end. That way, if there are problem cases, we'll have a > year or so of developer test to shake them out. > > > It can't hurt, but how effective will it be? Will developers know or > care whether ndistinct happened to get better or worse while they > are working on other things? I would think that problems will be > found by focused testing, or during beta, and probably not by > accidental discovery during the development cycle. It can't hurt, but > I don't know how much it will help. I agree with that - it's unlikely the regressions will get discovered randomly. OTOH I'd expect non-trivial number of people on this list to have a few examples of ndistinct failures, and testing those would be more useful I guess. But that's unlikely to find the cases that worked OK before and got broken by the new estimator :-( > I agree with the "experimental GUC". That way if hackers do happen to > see something suspicious, they can just turn it off and see what > difference it makes. If they have to reverse out a patch from 6 months > ago in an area of the code they aren't particularly interested in and > then recompile their code and then juggle two different sets of > binaries, they will likely just shrug it off without investigation. +1 -- Tomas Vondra http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services --------------060308050200090707040504 Content-Type: text/x-diff; name="ndistinct-estimator-v5.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="ndistinct-estimator-v5.patch" diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c index 861048f..f030702 100644 --- a/src/backend/commands/analyze.c +++ b/src/backend/commands/analyze.c @@ -16,6 +16,7 @@ #include +#include "access/hash.h" #include "access/multixact.h" #include "access/transam.h" #include "access/tupconvert.h" @@ -97,6 +98,9 @@ static void update_attstats(Oid relid, bool inh, static Datum std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull); static Datum ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull); +static double adaptive_estimator(double total_rows, int sample_rows, + int *f, int f_max); +static int hash_comparator(const void *a, const void *b); /* * analyze_rel() -- analyze one relation @@ -1698,6 +1702,7 @@ static void compute_scalar_stats(VacAttrStatsP stats, int samplerows, double totalrows); static int compare_scalars(const void *a, const void *b, void *arg); +static int compare_scalars_simple(const void *a, const void *b, void *arg); static int compare_mcvs(const void *a, const void *b); @@ -1816,6 +1821,23 @@ compute_minimal_stats(VacAttrStatsP stats, StdAnalyzeData *mystats = (StdAnalyzeData *) stats->extra_data; /* + * The adaptive ndistinct estimator requires counts for all the + * repetition counts - we can't do the sort-based count directly + * (because this handles data types with just = operator), and the + * MCV-based counting seems insufficient. We'll instead compute + * hash values, and sort those. We're using just 32-bit hashes, + * which may result in a few collisions - for 30k rows (sampled + * rows for default_statistics_target=100) there's 1:10 chance of + * a hash collision (assuming all values are distinct). But this + * seems like a small error compared to the other factors involved + * (sampling, ...) or compared to the MCV-based counting. + */ + uint32 *hashes = (uint32*)palloc0(samplerows * sizeof(uint32)); + + /* number of computed hashes (technically equal to nonnull_cnt) */ + int nhashes = 0; + + /* * We track up to 2*n values for an n-element MCV list; but at least 10 */ track_max = 2 * num_mcv; @@ -1876,6 +1898,36 @@ compute_minimal_stats(VacAttrStatsP stats, total_width += strlen(DatumGetCString(value)) + 1; } + /* compute the hash value, depending on the data type kind */ + if (stats->attrtype->typbyval) + { + /* simple pass-by-value data type, with 'typlen' bytes */ + hashes[nhashes++] + = DatumGetUInt32(hash_any((unsigned char *) &value, + stats->attrtype->typlen)); + } + else if (is_varlena) + { + /* regular varlena data type */ + hashes[nhashes++] + = DatumGetUInt32(hash_any((unsigned char *) VARDATA_ANY(value), + VARSIZE_ANY_EXHDR(DatumGetPointer(value)))); + } + else if (is_varwidth) + { + /* pass-by-reference with a variable length (e.g. cstring) */ + hashes[nhashes++] + = DatumGetUInt32(hash_any((unsigned char *) DatumGetCString(value), + strlen(DatumGetCString(value)))); + } + else + { + /* pass-by-reference with fixed length (e.g. name) */ + hashes[nhashes++] + = DatumGetUInt32(hash_any((unsigned char *) DatumGetCString(value), + stats->attrtype->typlen)); + } + /* * See if the value matches anything we're already tracking. */ @@ -1931,6 +1983,43 @@ compute_minimal_stats(VacAttrStatsP stats, int nmultiple, summultiple; + /* values needed by the adaptive ndistinct estimator */ + int f_max = 0; + int *f_count = (int*)palloc0(sizeof(int) * (nhashes + 1)); + int prev_index; + + /* sort the hashes and then count the repetitions */ + qsort(hashes, nhashes, sizeof(uint32), hash_comparator); + + /* + * Counting repetitions - walk through the sorted array, compare + * the value to the previous one, and whenever it changes the + * we can compute the repetitions using the array indexes. + */ + prev_index = 0; + for (i = 1; i < nhashes; i++) + { + /* the hashes are different - store the repetition count */ + if (hashes[i] != hashes[i-1]) + { + f_count[i - prev_index] += 1; + + if (f_max < (i - prev_index)) + f_max = (i - prev_index); + + prev_index = i; + } + } + + /* the last element is not updated in the loop */ + f_count[nhashes - prev_index] += 1; + + if (f_max < (nhashes - prev_index)) + f_max = (nhashes - prev_index); + + /* wide values are assumed to be distinct */ + f_count[1] += toowide_cnt; + stats->stats_valid = true; /* Do the simple null-frac and width stats */ stats->stanullfrac = (double) null_cnt / (double) samplerows; @@ -1988,6 +2077,7 @@ compute_minimal_stats(VacAttrStatsP stats, double numer, denom, stadistinct; + double adaptdistinct; numer = (double) samplerows *(double) d; @@ -2001,6 +2091,31 @@ compute_minimal_stats(VacAttrStatsP stats, if (stadistinct > totalrows) stadistinct = totalrows; stats->stadistinct = floor(stadistinct + 0.5); + + /* + * When computing the adaptive estimate, we're only considering + * non-null values, so we need to perform correction of the + * total rows / sample rows to reflect this. Otherwise the + * coefficients (f_count / f_max) are out of sync. We could + * probably do the inverse thing (including NULL values into + * f_count) with the same effect. + */ + adaptdistinct + = adaptive_estimator(totalrows * (nonnull_cnt / (double)samplerows), + nonnull_cnt, f_count, f_max); + + elog(WARNING, "ndistinct estimate attnum=%d attname=%s current=%.2f adaptive=%.2f", + stats->attr->attnum, NameStr(stats->attr->attname), + stadistinct, adaptdistinct); + + /* if we've seen 'almost' all rows, use the estimate instead */ + if (samplerows >= 0.95 * totalrows) + { + adaptdistinct = (d + d/0.95)/2; + elog(WARNING, " corrected ndistinct estimate current=%.2f adaptive=%.2f", + stadistinct, adaptdistinct); + } + } /* @@ -2225,6 +2340,12 @@ compute_scalar_stats(VacAttrStatsP stats, int slot_idx = 0; CompareScalarsContext cxt; + /* f values for the estimator - messy and we likely need much + * less memory, but who cares */ + int f_max = 0; /* max number of duplicates */ + int *f_count = (int*)palloc0(sizeof(int)*(values_cnt+1)); + int first_index = 0; /* first index of a group */ + /* Sort the collected values */ cxt.ssup = &ssup; cxt.tupnoLink = tupnoLink; @@ -2295,6 +2416,35 @@ compute_scalar_stats(VacAttrStatsP stats, } } + /* + * Counting repetitions - walk through the sorted array, compare + * the value to the previous one, and whenever it changes the + * we can compute the repetitions using the array indexes. + */ + for (i = 1; i < values_cnt; i++) + { + /* the hashes are different - store the repetition count */ + if (compare_scalars_simple(&values[i], &values[first_index], &cxt) != 0) + { + /* found first element of the following group, so (i-first) is the count */ + f_count[i - first_index] += 1; + + if (f_max < (i - first_index)) + f_max = (i - first_index); + + first_index = i; + } + } + + /* the last element is not updated in the loop */ + f_count[values_cnt - first_index] += 1; + + if (f_max < (values_cnt - first_index)) + f_max = (values_cnt - first_index); + + /* compensate for wide values (assumed to be distinct) */ + f_count[1] += toowide_cnt; + stats->stats_valid = true; /* Do the simple null-frac and width stats */ stats->stanullfrac = (double) null_cnt / (double) samplerows; @@ -2337,6 +2487,7 @@ compute_scalar_stats(VacAttrStatsP stats, double numer, denom, stadistinct; + double adaptdistinct; /* adaptive estimate */ numer = (double) samplerows *(double) d; @@ -2350,6 +2501,30 @@ compute_scalar_stats(VacAttrStatsP stats, if (stadistinct > totalrows) stadistinct = totalrows; stats->stadistinct = floor(stadistinct + 0.5); + + /* + * When computing the adaptive estimate, we're only considering + * non-null values, so we need to perform correction of the + * total rows / sample rows to reflect this. Otherwise the + * coefficients (f_count / f_max) are out of sync. We could + * probably do the inverse thing (including NULL values into + * f_count) with the same effect. + */ + adaptdistinct + = adaptive_estimator(totalrows * (nonnull_cnt / (double)samplerows), + nonnull_cnt, f_count, f_max); + + elog(WARNING, "ndistinct estimate attnum=%d attname=%s current=%.2f adaptive=%.2f", + stats->attr->attnum, NameStr(stats->attr->attname), + stadistinct, adaptdistinct); + + /* if we've seen 'almost' all rows, use the estimate instead */ + if (samplerows >= 0.95 * totalrows) + { + adaptdistinct = (d + d/0.95)/2; + elog(WARNING, " corrected ndistinct estimate current=%.2f adaptive=%.2f", + stadistinct, adaptdistinct); + } } /* @@ -2665,6 +2840,21 @@ compare_scalars(const void *a, const void *b, void *arg) } /* + * qsort_arg comparator for sorting ScalarItems + * + */ +static int +compare_scalars_simple(const void *a, const void *b, void *arg) +{ + Datum da = ((const ScalarItem *) a)->value; + Datum db = ((const ScalarItem *) b)->value; + + CompareScalarsContext *cxt = (CompareScalarsContext *) arg; + + return ApplySortComparator(da, false, db, false, cxt->ssup); +} + +/* * qsort comparator for sorting ScalarMCVItems by position */ static int @@ -2675,3 +2865,131 @@ compare_mcvs(const void *a, const void *b) return da - db; } + +/* + * Implements AEE ndistinct estimator, desctibed in the paper "Towards + * Estimation Error Guarantees for Distinct Values, ACM 2000" paper, with + * a minor tweak for highly skewed distributions, where the AEE is quite + * unstable. In those cases (when either f1 or f2 are 0) we simply use + * the GEE estimator, which seems to work better in those cases. + * + * The AEE estimator is based on solving this equality (for "m") + * + * m - f1 - f2 = f1 * (A + A(m)) / (B + B(m)) + * + * where A, B are effectively constants (not depending on m), and A(m) + * and B(m) are functions. This is equal to solving + * + * 0 = f1 * (A + A(m)) / (B + B(m)) - (m - f1 - f2) + * + * Instead of looking for the exact solution to this equation (which + * might be fractional), we'll look for a natural number minimizing + * the absolute difference. Number of (distinct) elements is a natural + * number, and we don't mind if the number is slightly wrong. It's + * just an estimate, after all. The error from sampling will be much + * worse in most cases. + * + * We know the acceptable values of 'm' are [d,N] where 'd' is the number + * of distinct elements in the sample, and N is the number of rows in + * the table (not just the sample). For large tables (billions of rows) + * that'd be quite time-consuming to compute, so we'll approximate the + * solution by gradually increasing the step to ~1% of the current value + * of 'm'. This will make it much faster and yet very accurate. + * + * All this of course assumes the function behaves reasonably (not + * oscillating etc.), but that's a safe assumption as the estimator + * would perform terribly otherwise (and we're falling back to GEE for + * cases where this behavior could happen). + */ +static double +adaptive_estimator(double total_rows, int sample_rows, int *f, int f_max) +{ + int i; + double m; + double A = 0.0, B = 0.0; + double opt_m = 0; + double opt_diff = total_rows; + double step = 1.0; + double ndistinct; + int d = f[1] + f[2]; + + double k = (f[1] + 2*f[2]); + + /* for highly-skewed distributions, the GEE works better */ + if (f[1] == 0 || f[2] == 0) + { + d = f[1]; + ndistinct = sqrt(total_rows / (double)sample_rows) * f[1]; + + for (i = 2; i <= f_max; i++) + { + ndistinct += f[i]; + d += f[i]; + } + + /* sanity checks that the estimate is within [d,total_rows] */ + if (ndistinct < d) + ndistinct = d; + else if (ndistinct > total_rows / sample_rows * d) + ndistinct = total_rows / sample_rows * d; + + return ndistinct; + } + + /* compute the 'constant' parts of the equality (A, B) */ + for (i = 3; i <= f_max; i++) + { + double p = i / (double)sample_rows; + A += powl((1.0 - p), sample_rows ) * f[i]; + B += i * powl((1.0 - p), sample_rows-1) * f[i]; + d += f[i]; + } + + /* find the 'm' value minimizing the difference */ + for (m = 1; m <= total_rows; m += step) + { + double q = k / (sample_rows * m); + + double A_m = A + m * powl((1 - q), sample_rows ); + double B_m = B + k * powl((1 - q), sample_rows-1); + + double diff = fabsl(f[1] * (A_m / B_m) - (m - f[1] - f[2])); + + /* + * The function should have a single minimum - stop if we've passed + * it, but not on the first element. + */ + if ((m > 1) && (opt_diff < diff)) + break; + + opt_diff = diff; + opt_m = m; + + /* tweak the step to 1% to make it faster */ + step = ((int)(0.01 * m) > step) ? (int)(0.01 * m) : step; + } + + /* compute the final estimate */ + ndistinct = d + opt_m - f[1] - f[2]; + + /* sanity checks that the estimate is within [d,total_rows] */ + if (ndistinct < d) + ndistinct = d; + else if (ndistinct > total_rows / sample_rows * d) + ndistinct = total_rows / sample_rows * d; + + return ndistinct; +} + +static int +hash_comparator(const void *a, const void *b) +{ + uint32 ai = *(uint32*)a; + uint32 bi = *(uint32*)b; + if (ai < bi) + return -1; + else if (ai > bi) + return 1; + else + return 0; +} --------------060308050200090707040504 Content-Type: text/plain Content-Disposition: inline Content-Transfer-Encoding: 8bit MIME-Version: 1.0 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers --------------060308050200090707040504--