pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: PATCH: adaptive ndistinct estimator v4
17+ messages / 6 participants
[nested] [flat]
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-03-31 19:02 Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 3 replies; 17+ messages in thread
From: Tomas Vondra @ 2015-03-31 19:02 UTC (permalink / raw)
To: pgsql-hackers@postgresql.org
Hi all,
attached is v4 of the patch implementing adaptive ndistinct estimator.
I've been looking into the strange estimates, mentioned on 2014/12/07:
> values current adaptive
> ------------------------------
> 106 99 107
> 106 8 6449190
> 1006 38 6449190
> 10006 327 42441
I suspected this might be some sort of rounding error in the numerical
optimization (looking for 'm' solving the equation from paper), but
turns out that's not the case.
The adaptive estimator is a bit unstable for skewed distributions, that
are not sufficiently smooth. Whenever f[1] or f[2] was 0 (i.e. there
were no values occuring exactly once or twice in the sample), the result
was rather off.
The simple workaround for this was adding a fallback to GEE when f[1] or
f[2] is 0. GEE is another estimator described in the paper, behaving
much better in those cases.
With the current version, I do get this (with statistics_target=10):
values current adaptive
------------------------------
106 99 108
106 8 178
1006 38 2083
10006 327 11120
The results do change a bit based on the sample, but these values are a
good example of the values I'm getting.
The other examples (with skewed but smooth distributions) work as good
as before.
--
Tomas Vondra http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments:
ndistinct-estimator-v4.patch (text/x-diff, 13.1K) download
diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c
index d4d1914..2496e83 100644
--- a/src/backend/commands/analyze.c
+++ b/src/backend/commands/analyze.c
@@ -16,6 +16,7 @@
#include <math.h>
+#include "access/hash.h"
#include "access/multixact.h"
#include "access/transam.h"
#include "access/tupconvert.h"
@@ -110,6 +111,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(int 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
@@ -1908,6 +1912,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);
@@ -2026,6 +2031,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;
@@ -2086,6 +2108,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.
*/
@@ -2141,6 +2193,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;
@@ -2198,6 +2287,7 @@ compute_minimal_stats(VacAttrStatsP stats,
double numer,
denom,
stadistinct;
+ double adaptdistinct;
numer = (double) samplerows *(double) d;
@@ -2211,6 +2301,30 @@ 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 current=%.2f adaptive=%.2f",
+ 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);
+ }
+
}
/*
@@ -2434,6 +2548,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;
@@ -2504,6 +2624,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;
@@ -2546,6 +2695,7 @@ compute_scalar_stats(VacAttrStatsP stats,
double numer,
denom,
stadistinct;
+ double adaptdistinct; /* adaptive estimate */
numer = (double) samplerows *(double) d;
@@ -2559,6 +2709,29 @@ 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 current=%.2f adaptive=%.2f",
+ 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);
+ }
}
/*
@@ -2874,6 +3047,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
@@ -2884,3 +3072,130 @@ 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(int total_rows, int sample_rows, int *f, int f_max)
+{
+ int i, m;
+ double A = 0.0, B = 0.0;
+ int opt_m = 0;
+ double opt_diff = total_rows;
+ int step = 1;
+ int 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;
+}
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-04-03 13:46 Greg Stark <stark@mit.edu>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
2 siblings, 1 reply; 17+ messages in thread
From: Greg Stark @ 2015-04-03 13:46 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
> The simple workaround for this was adding a fallback to GEE when f[1] or
f[2] is 0. GEE is another estimator described in the paper, behaving much
better in those cases.
For completeness, what's the downside in just always using GEE?
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-04-04 23:57 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Greg Stark <stark@mit.edu>
0 siblings, 0 replies; 17+ messages in thread
From: Tomas Vondra @ 2015-04-04 23:57 UTC (permalink / raw)
To: Greg Stark <stark@mit.edu>; +Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Hi,
On 04/03/15 15:46, Greg Stark wrote:
> > The simple workaround for this was adding a fallback to GEE when f[1]
> or f[2] is 0. GEE is another estimator described in the paper, behaving
> much better in those cases.
>
> For completeness, what's the downside in just always using GEE?
That's a good question.
GEE is the estimator with minimal average error, as defined in Theorem 1
in that paper. The exact formulation of the theorem is a bit complex,
but it essentially says that knowing just the sizes of the data set and
sample, there's an accuracy limit.
Or put another way, it's possible to construct the data set so that the
estimator gives you estimates with error exceeding some limit (with a
certain probability).
Knowledge of how much the data set is skewed gives us opportunity to
improve the estimates by choosing an estimator performing better with
such data sets. The problem is we don't know the skew - we can only
estimate it from the sample, which is what the hybrid estimators do.
The AE estimator (presented in the paper and implemented in the patch)
is an example of such hybrid estimators, but based on my experiments it
does not work terribly well with one particular type of skew that I'd
expect to be relatively common (few very common values, many very rare
values).
Luckily, GEE performs pretty well in this case, but we can use the AE
otherwise (ISTM it gives really good estimates).
But of course - there'll always be data sets that are poorly estimated
(pretty much as Theorem 1 in the paper says). I'd be nice to do more
testing on real-world data sets, to see if this performs better or worse
than our current estimator.
regards
Tomas
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-04-15 06:45 Jeff Janes <jeff.janes@gmail.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
2 siblings, 1 reply; 17+ messages in thread
From: Jeff Janes @ 2015-04-15 06:45 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
On Tue, Mar 31, 2015 at 12:02 PM, Tomas Vondra <tomas.vondra@2ndquadrant.com
> wrote:
> Hi all,
>
> attached is v4 of the patch implementing adaptive ndistinct estimator.
>
Hi Tomas,
I have a case here where the adaptive algorithm underestimates ndistinct by
a factor of 7 while the default estimator is pretty close.
5MB file:
https://drive.google.com/file/d/0Bzqrh1SO9FcETU1VYnQxU2RZSWM/view?usp=sharing
# create table foo2 (x text);
# \copy foo2 from program 'bzcat ~/temp/foo1.txt.bz2'
# analyze verbose foo2;
INFO: analyzing "public.foo2"
INFO: "foo2": scanned 6021 of 6021 pages, containing 1113772 live rows and
0 dead rows; 30000 rows in sample, 1113772 estimated total rows
WARNING: ndistinct estimate current=998951.78 adaptive=135819.00
Cheers,
Jeff
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-04-20 05:13 Jeff Janes <jeff.janes@gmail.com>
parent: Jeff Janes <jeff.janes@gmail.com>
0 siblings, 0 replies; 17+ messages in thread
From: Jeff Janes @ 2015-04-20 05:13 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
On Tue, Apr 14, 2015 at 11:45 PM, Jeff Janes <jeff.janes@gmail.com> wrote:
> On Tue, Mar 31, 2015 at 12:02 PM, Tomas Vondra <
> tomas.vondra@2ndquadrant.com> wrote:
>
>> Hi all,
>>
>> attached is v4 of the patch implementing adaptive ndistinct estimator.
>>
>
> Hi Tomas,
>
> I have a case here where the adaptive algorithm underestimates ndistinct
> by a factor of 7 while the default estimator is pretty close.
>
> 5MB file:
>
>
> https://drive.google.com/file/d/0Bzqrh1SO9FcETU1VYnQxU2RZSWM/view?usp=sharing
>
> # create table foo2 (x text);
> # \copy foo2 from program 'bzcat ~/temp/foo1.txt.bz2'
> # analyze verbose foo2;
> INFO: analyzing "public.foo2"
> INFO: "foo2": scanned 6021 of 6021 pages, containing 1113772 live rows
> and 0 dead rows; 30000 rows in sample, 1113772 estimated total rows
> WARNING: ndistinct estimate current=998951.78 adaptive=135819.00
>
I've done a more complete analysis with a real world database I have access
to.
I've analyzed patched and current with default_statistics_target of 100 and
10000. (I also have some of the same data under 9.2, but that is not
meaningfully different than unpatched head).
For easier interpretation I hacked up the analyzer so that it just reports
the estimated number, never converting to the negative fraction.
See the spreadsheet here:
https://docs.google.com/spreadsheets/d/1qUcBoQkRFFcSDq7GtkiQkHqlLTbxQYl5hh6S0byff2M/edit?usp=sharing
The 10000 target was initially collected in an attempt to discern the truth
when the 100 target methods disagreed, but I decided to just collect the
gold-standard truth.
The truth is given by:
select count(*) from (select distinct column from schema.table where column
is not null) foo;
And number_not_null is given by:
select count(*) from schema.table where column is not null;
It looks like the proposed method sometimes overestimates, although never
by a huge amount, while the old one never overestimated. Overall it mostly
seems to be more accurate, but occasionally it does substantially worse
than the current method. I suspect most of the problems are related to the
same issue reported in the last email. There are a lot of places where
both underestimate, but where the new method does so by less than head.
If there are any columns anyone wants to examine further, give me the token
for it and I'll try to create a generator that generates data with the same
distribution (and clustering, if that seems relevant).
Cheers,
Jeff
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-04-30 20:57 Robert Haas <robertmhaas@gmail.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
2 siblings, 2 replies; 17+ messages in thread
From: Robert Haas @ 2015-04-30 20:57 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On Tue, Mar 31, 2015 at 3:02 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> attached is v4 of the patch implementing adaptive ndistinct estimator.
So, I took a look at this today. It's interesting work, but it looks
more like a research project than something we can commit to 9.5. As
far as I can see, this still computes the estimate the way we do
today, but then also computes the estimate using this new method. The
estimate computed the new way isn't stored anywhere, so this doesn't
really change behavior, except for printing out a WARNING comparing
the values produced by the two estimators.
IMHO, the comments in this patch are pretty inscrutable. I believe
this is because they presume more knowledge of what the patch is doing
than I myself possess. For example:
+ * 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)
Perhaps I am just a dummy, but I have no idea what any of that means.
I think that needs to be fixed so that someone who knows what
n_distinct is but knows nothing about the details of these estimators
can get an idea of how they are doing their thing without too much
effort. I think a lot of the comments share this problem.
Aside from the problems mentioned above, there's the broader question
of how to evaluate the quality of the estimates produced by this
estimator vs. what we're doing right now. I see that Jeff Janes has
pointed out some cases that seem to regress with this patch; those
presumably need some investigation, or at least some comment. And I
think some testing from other people would be good too, before we
commit to this.
Leaving that aside, at some point, you'll say, "OK, there may be some
regressions left but overall I believe this is going to be a win in
most cases". It's going to be really hard for anyone, no matter how
smart, to figure out through code review whether that is true. So
committing this figures to be extremely frightening. It's just not
going to be reasonably possible to know what percentage of users are
going to be more happy after this change and what percentage are going
to be less happy.
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.
2. There should be a compatibility GUC to restore the old behavior.
The new behavior should be the default, because if we're not confident
that the new behavior will be better for most people, we have no
business installing it in the first place (plus few people will try
it). But just in case it turns out to suck for some people, we should
provide an escape hatch, at least for a few releases.
3. There should be some clear documentation in the comments indicating
why we believe that this is a whole lot better than what we do today.
Maybe this has been discussed adequately on the thread and maybe it
hasn't, but whoever goes to look at the committed code should not have
to go root through hackers threads to understand why we replaced the
existing estimator. It should be right there in the code. If,
hypothetically speaking, I were to commit this, and if, again strictly
hypothetically, another distinguished committer were to write back a
year or two later, "clearly Robert was an idiot to commit this because
it's no better than what we had before" then I want to be able to say
"clearly, you have not what got committed very carefully, because the
comment for function <blat> clearly explains that this new technology
is teh awesome".
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-04-30 21:31 Heikki Linnakangas <hlinnaka@iki.fi>
parent: Robert Haas <robertmhaas@gmail.com>
1 sibling, 1 reply; 17+ messages in thread
From: Heikki Linnakangas @ 2015-04-30 21:31 UTC (permalink / raw)
To: Robert Haas <robertmhaas@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On 04/30/2015 01:57 PM, Robert Haas wrote:
>
> 2. There should be a compatibility GUC to restore the old behavior.
> The new behavior should be the default, because if we're not confident
> that the new behavior will be better for most people, we have no
> business installing it in the first place (plus few people will try
> it). But just in case it turns out to suck for some people, we should
> provide an escape hatch, at least for a few releases.
You can override the ndistinct estimate with ALTER TABLE. I think that's
enough for an escape hatch.
- Heikki
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-04-30 22:18 Robert Haas <robertmhaas@gmail.com>
parent: Heikki Linnakangas <hlinnaka@iki.fi>
0 siblings, 1 reply; 17+ messages in thread
From: Robert Haas @ 2015-04-30 22:18 UTC (permalink / raw)
To: hlinnaka <hlinnaka@iki.fi>; +Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>; pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On Thu, Apr 30, 2015 at 5:31 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> On 04/30/2015 01:57 PM, Robert Haas wrote:
>> 2. There should be a compatibility GUC to restore the old behavior.
>> The new behavior should be the default, because if we're not confident
>> that the new behavior will be better for most people, we have no
>> business installing it in the first place (plus few people will try
>> it). But just in case it turns out to suck for some people, we should
>> provide an escape hatch, at least for a few releases.
>
> You can override the ndistinct estimate with ALTER TABLE. I think that's
> enough for an escape hatch.
I'm not saying that isn't nice to have, but I don't think it really
helps much here. Setting the value manually requires that you know
what value to set, and you might not. If, on some workloads, the old
algorithm beats the new one reliably, you want to be able to actually
go back to the old algorithm, not manually override every wrong
decision it makes. A GUC for this is pretty cheap insurance.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-05-01 01:20 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Robert Haas <robertmhaas@gmail.com>
1 sibling, 2 replies; 17+ messages in thread
From: Tomas Vondra @ 2015-05-01 01:20 UTC (permalink / raw)
To: Robert Haas <robertmhaas@gmail.com>; +Cc: pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
Hi,
On 04/30/15 22:57, Robert Haas wrote:
> On Tue, Mar 31, 2015 at 3:02 PM, Tomas Vondra
> <tomas.vondra@2ndquadrant.com> wrote:
>> attached is v4 of the patch implementing adaptive ndistinct estimator.
>
> So, I took a look at this today. It's interesting work, but it looks
> more like a research project than something we can commit to 9.5. As
> far as I can see, this still computes the estimate the way we do
> today, but then also computes the estimate using this new method.
> The estimate computed the new way isn't stored anywhere, so this
> doesn't really change behavior, except for printing out a WARNING
> comparing the values produced by the two estimators.
I agree that this is not ready for 9.5 - it was meant as an experiment
(hence printing the estimate in a WARNING, to make it easier to compare
the value to the current estimator). Without that it'd be much more
complicated to compare the old/new estimates, but you're right this is
not suitable for commit.
So far it received only reviews from Jeff Janes (thanks!), but I think a
change like this really requires a more thorough review, including the
math part. I don't expect that to happen at the very end of the last CF
before the freeze.
> IMHO, the comments in this patch are pretty inscrutable. I believe
> this is because they presume more knowledge of what the patch is doing
> than I myself possess. For example:
>
> + * 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)
>
> Perhaps I am just a dummy, but I have no idea what any of that means.
> I think that needs to be fixed so that someone who knows what
> n_distinct is but knows nothing about the details of these estimators
> can get an idea of how they are doing their thing without too much
> effort. I think a lot of the comments share this problem.
Well, I don't think you're dummy, but this requires reading the paper
describing the estimator. Explaining that fully would essentially mean
copying a large portion of the paper in the comment, and I suppose
that's not a good idea. The explanation might be perhaps a bit more
detailed, though - not sure what's the right balance.
> Aside from the problems mentioned above, there's the broader question
> of how to evaluate the quality of the estimates produced by this
> estimator vs. what we're doing right now. I see that Jeff Janes has
> pointed out some cases that seem to regress with this patch; those
> presumably need some investigation, or at least some comment. And I
> think some testing from other people would be good too, before we
> commit to this.
Yeah, evaluating is difficult. I think that Jeff's approach - i.e.
testing the estimator on real-world data sets - is the right approach
here. Testing on synthetic data sets has it's value too (if only to
better understand the failure cases).
> Leaving that aside, at some point, you'll say, "OK, there may be some
> regressions left but overall I believe this is going to be a win in
> most cases". It's going to be really hard for anyone, no matter how
> smart, to figure out through code review whether that is true. So
> committing this figures to be extremely frightening. It's just not
> going to be reasonably possible to know what percentage of users are
> going to be more happy after this change and what percentage are
> going to be less happy.
For every pair of estimators you can find cases where one of them is
better than the other one. It's pretty much impossible to find an
estimator that beats all other estimators on all possible inputs.
There's no way to make this an improvement for everyone - it will
produce worse estimates in some cases, and we have to admit that. If we
think this is unacceptable, we're effectively stuck with the current
estimator forever.
> 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.
+1
> 2. There should be a compatibility GUC to restore the old behavior.
> The new behavior should be the default, because if we're not
> confident that the new behavior will be better for most people, we
> have no business installing it in the first place (plus few people
> will try it). But just in case it turns out to suck for some people,
> we should provide an escape hatch, at least for a few releases.
I think a "compatibility GUC" is a damn poor solution, IMNSHO.
For example, GUCs are database-wide, but I do expect the estimator to
perform worse only on a few data sets / columns. So making this a
column-level settings would be more appropriate, I think.
But it might work during the development cycle, as it would make
comparing the estimators possible (just run the tests with the GUC set
differently). Assuming we'll re-evaluate it at the end, and remove the
GUC if possible.
>
> 3. There should be some clear documentation in the comments indicating
> why we believe that this is a whole lot better than what we do today.
> Maybe this has been discussed adequately on the thread and maybe it
> hasn't, but whoever goes to look at the committed code should not have
> to go root through hackers threads to understand why we replaced the
> existing estimator. It should be right there in the code. If,
> hypothetically speaking, I were to commit this, and if, again strictly
> hypothetically, another distinguished committer were to write back a
> year or two later, "clearly Robert was an idiot to commit this because
> it's no better than what we had before" then I want to be able to say
> "clearly, you have not what got committed very carefully, because the
> comment for function <blat> clearly explains that this new technology
> is teh awesome".
I certainly can add such comment to the patch ;-) Choose a function.
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-05-01 01:24 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Robert Haas <robertmhaas@gmail.com>
0 siblings, 0 replies; 17+ messages in thread
From: Tomas Vondra @ 2015-05-01 01:24 UTC (permalink / raw)
To: Robert Haas <robertmhaas@gmail.com>; hlinnaka <hlinnaka@iki.fi>; +Cc: pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On 05/01/15 00:18, Robert Haas wrote:
> On Thu, Apr 30, 2015 at 5:31 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>>
>> You can override the ndistinct estimate with ALTER TABLE. I think
>> that's enough for an escape hatch.
>
> I'm not saying that isn't nice to have, but I don't think it really
> helps much here. Setting the value manually requires that you know
> what value to set, and you might not. If, on some workloads, the old
> algorithm beats the new one reliably, you want to be able to
> actually go back to the old algorithm, not manually override every
> wrong decision it makes. A GUC for this is pretty cheap insurance.
IMHO this is exactly the same situation as with the current ndistinct
estimator. If we find out we'd have to use this workaround more
frequently than before, then clearly the new estimator is rubbish and
should not be committed.
In other words, I agree with Heikki.
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-05-01 11:55 Robert Haas <robertmhaas@gmail.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
1 sibling, 0 replies; 17+ messages in thread
From: Robert Haas @ 2015-05-01 11:55 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On Thu, Apr 30, 2015 at 9:20 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> I agree that this is not ready for 9.5 - it was meant as an experiment
> (hence printing the estimate in a WARNING, to make it easier to compare
> the value to the current estimator). Without that it'd be much more
> complicated to compare the old/new estimates, but you're right this is
> not suitable for commit.
>
> So far it received only reviews from Jeff Janes (thanks!), but I think a
> change like this really requires a more thorough review, including the math
> part. I don't expect that to happen at the very end of the last CF before
> the freeze.
OK.
>> IMHO, the comments in this patch are pretty inscrutable. I believe
>> this is because they presume more knowledge of what the patch is doing
>> than I myself possess. For example:
>>
>> + * 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)
>>
>> Perhaps I am just a dummy, but I have no idea what any of that means.
>> I think that needs to be fixed so that someone who knows what
>> n_distinct is but knows nothing about the details of these estimators
>> can get an idea of how they are doing their thing without too much
>> effort. I think a lot of the comments share this problem.
>
> Well, I don't think you're dummy, but this requires reading the paper
> describing the estimator. Explaining that fully would essentially mean
> copying a large portion of the paper in the comment, and I suppose that's
> not a good idea. The explanation might be perhaps a bit more detailed,
> though - not sure what's the right balance.
Well, I think the problem in this case is that the comment describes
what the values are mathematically without explaining what they are
conceptually. For example, in s=1/2at^2+v_0t+s_0, we could say that a
is meant to be the rate of change of an unseen variable v, while v_0
is the initial vale of v, and that s_0 is meant to be the starting
value of s, changing at a rate described by v. That's basically the
kind of explanation you have right now. It's all correct, but what
does it really mean? It's more helpful to say that we're trying to
project the position of a body at a given time (t) given its initial
position (s_0), its initial velocity (v), and its rate of acceleration
(a).
>> 3. There should be some clear documentation in the comments indicating
>> why we believe that this is a whole lot better than what we do today.
>> Maybe this has been discussed adequately on the thread and maybe it
>> hasn't, but whoever goes to look at the committed code should not have
>> to go root through hackers threads to understand why we replaced the
>> existing estimator. It should be right there in the code. If,
>> hypothetically speaking, I were to commit this, and if, again strictly
>> hypothetically, another distinguished committer were to write back a
>> year or two later, "clearly Robert was an idiot to commit this because
>> it's no better than what we had before" then I want to be able to say
>> "clearly, you have not what got committed very carefully, because the
>> comment for function <blat> clearly explains that this new technology
>> is teh awesome".
>
> I certainly can add such comment to the patch ;-) Choose a function.
Well, at least the way things are organized right now,
adaptive_estimator seems like the place.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-05-13 21:07 Jeff Janes <jeff.janes@gmail.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
1 sibling, 2 replies; 17+ messages in thread
From: Jeff Janes @ 2015-05-13 21:07 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Robert Haas <robertmhaas@gmail.com>; pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On Thu, Apr 30, 2015 at 6:20 PM, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:
> Hi,
>
> On 04/30/15 22:57, Robert Haas wrote:
>
>> On Tue, Mar 31, 2015 at 3:02 PM, Tomas Vondra
>> <tomas.vondra@2ndquadrant.com> wrote:
>>
>>> attached is v4 of the patch implementing adaptive ndistinct estimator.
>>>
>>
>> So, I took a look at this today. It's interesting work, but it looks
>> more like a research project than something we can commit to 9.5. As
>> far as I can see, this still computes the estimate the way we do
>> today, but then also computes the estimate using this new method.
>> The estimate computed the new way isn't stored anywhere, so this
>> doesn't really change behavior, except for printing out a WARNING
>> comparing the values produced by the two estimators.
>>
>
> I agree that this is not ready for 9.5 - it was meant as an experiment
> (hence printing the estimate in a WARNING, to make it easier to compare
> the value to the current estimator). Without that it'd be much more
> complicated to compare the old/new estimates, but you're right this is
> not suitable for commit.
>
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).
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.
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.
> Leaving that aside, at some point, you'll say, "OK, there may be some
>> regressions left but overall I believe this is going to be a win in
>> most cases". It's going to be really hard for anyone, no matter how
>> smart, to figure out through code review whether that is true. So
>> committing this figures to be extremely frightening. It's just not
>> going to be reasonably possible to know what percentage of users are
>> going to be more happy after this change and what percentage are
>> going to be less happy.
>>
>
> For every pair of estimators you can find cases where one of them is
> better than the other one. It's pretty much impossible to find an estimator
> that beats all other estimators on all possible inputs.
>
> There's no way to make this an improvement for everyone - it will produce
> worse estimates in some cases, and we have to admit that. If we think this
> is unacceptable, we're effectively stuck with the current estimator forever.
>
> 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.
> 2. There should be a compatibility GUC to restore the old behavior.
>> The new behavior should be the default, because if we're not
>> confident that the new behavior will be better for most people, we
>> have no business installing it in the first place (plus few people
>> will try it). But just in case it turns out to suck for some people,
>> we should provide an escape hatch, at least for a few releases.
>>
>
> I think a "compatibility GUC" is a damn poor solution, IMNSHO.
>
> For example, GUCs are database-wide, but I do expect the estimator to
> perform worse only on a few data sets / columns. So making this a
> column-level settings would be more appropriate, I think.
>
> But it might work during the development cycle, as it would make comparing
> the estimators possible (just run the tests with the GUC set differently).
> Assuming we'll re-evaluate it at the end, and remove the GUC if possible.
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.
Cheers,
Jeff
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-05-15 18:30 Robert Haas <robertmhaas@gmail.com>
parent: Jeff Janes <jeff.janes@gmail.com>
1 sibling, 1 reply; 17+ messages in thread
From: Robert Haas @ 2015-05-15 18:30 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>; pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On Wed, May 13, 2015 at 5:07 PM, Jeff Janes <jeff.janes@gmail.com> 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).
Presumably the warning is going to go away before we actually commit this thing.
> 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.
If we stick with the idea of a GUC to control the behavior, then
somebody can run ANALYZE, save the ndistinct estimates, run ANALYZE
again, and compare. They can also run SQL queries against the tables
themselves to check the real value. We could even provide a script
for all of that. I think that would be quite handy.
> 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.
Once we enter beta (or even feature freeze), it's too late to whack
around the algorithm heavily. We're pretty much committed to
releasing and supporting whatever we have got at that point. I guess
we could revert it if it doesn't work out, but that's about the only
option at that point. We have more flexibility during the main part
of the development cycle. But your point is certainly valid and I
don't mean to dispute it.
> 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.
Yep. Users, too.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-05-15 19:35 Josh Berkus <josh@agliodbs.com>
parent: Robert Haas <robertmhaas@gmail.com>
0 siblings, 1 reply; 17+ messages in thread
From: Josh Berkus @ 2015-05-15 19:35 UTC (permalink / raw)
To: Robert Haas <robertmhaas@gmail.com>; Jeff Janes <jeff.janes@gmail.com>; +Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>; pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On 05/15/2015 11:30 AM, Robert Haas wrote:
> Once we enter beta (or even feature freeze), it's too late to whack
> around the algorithm heavily. We're pretty much committed to
> releasing and supporting whatever we have got at that point. I guess
> we could revert it if it doesn't work out, but that's about the only
> option at that point. We have more flexibility during the main part
> of the development cycle. But your point is certainly valid and I
> don't mean to dispute it.
I will finally have a customer workload available to test this on this
weekend. That's been rather delayed by the availability of customer
hardware,because I'm not allowed to copy out the database. However,
this is a database which suffers from multiple ndistinct estimation
issues in production, so I should be able to get a set of stats back by
Monday which would show how much of a general improvement it is.
I realize that's after the deadline, but there wasn't much I could do
about it. I've tried to simulate the kind of estimation issues I've
seen, but they don't simulate well.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-05-15 19:58 Robert Haas <robertmhaas@gmail.com>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 17+ messages in thread
From: Robert Haas @ 2015-05-15 19:58 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Jeff Janes <jeff.janes@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On Fri, May 15, 2015 at 3:35 PM, Josh Berkus <josh@agliodbs.com> wrote:
> On 05/15/2015 11:30 AM, Robert Haas wrote:
>> Once we enter beta (or even feature freeze), it's too late to whack
>> around the algorithm heavily. We're pretty much committed to
>> releasing and supporting whatever we have got at that point. I guess
>> we could revert it if it doesn't work out, but that's about the only
>> option at that point. We have more flexibility during the main part
>> of the development cycle. But your point is certainly valid and I
>> don't mean to dispute it.
>
> I will finally have a customer workload available to test this on this
> weekend. That's been rather delayed by the availability of customer
> hardware,because I'm not allowed to copy out the database. However,
> this is a database which suffers from multiple ndistinct estimation
> issues in production, so I should be able to get a set of stats back by
> Monday which would show how much of a general improvement it is.
>
> I realize that's after the deadline, but there wasn't much I could do
> about it. I've tried to simulate the kind of estimation issues I've
> seen, but they don't simulate well.
This is clearly 9.6 material at this point, and has been for a while.
The patch - at least the last version I looked at - didn't store
anything different in pg_statistic. It just logged what it would have
stored. So testing is good, but there's not a question of pushing
this into 9.5.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-05-15 20:00 Josh Berkus <josh@agliodbs.com>
parent: Robert Haas <robertmhaas@gmail.com>
0 siblings, 0 replies; 17+ messages in thread
From: Josh Berkus @ 2015-05-15 20:00 UTC (permalink / raw)
To: Robert Haas <robertmhaas@gmail.com>; +Cc: Jeff Janes <jeff.janes@gmail.com>; Tomas Vondra <tomas.vondra@2ndquadrant.com>; pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
On 05/15/2015 12:58 PM, Robert Haas wrote:
> On Fri, May 15, 2015 at 3:35 PM, Josh Berkus <josh@agliodbs.com> wrote:
>> On 05/15/2015 11:30 AM, Robert Haas wrote:
>>> Once we enter beta (or even feature freeze), it's too late to whack
>>> around the algorithm heavily. We're pretty much committed to
>>> releasing and supporting whatever we have got at that point. I guess
>>> we could revert it if it doesn't work out, but that's about the only
>>> option at that point. We have more flexibility during the main part
>>> of the development cycle. But your point is certainly valid and I
>>> don't mean to dispute it.
>>
>> I will finally have a customer workload available to test this on this
>> weekend. That's been rather delayed by the availability of customer
>> hardware,because I'm not allowed to copy out the database. However,
>> this is a database which suffers from multiple ndistinct estimation
>> issues in production, so I should be able to get a set of stats back by
>> Monday which would show how much of a general improvement it is.
>>
>> I realize that's after the deadline, but there wasn't much I could do
>> about it. I've tried to simulate the kind of estimation issues I've
>> seen, but they don't simulate well.
>
> This is clearly 9.6 material at this point, and has been for a while.
> The patch - at least the last version I looked at - didn't store
> anything different in pg_statistic. It just logged what it would have
> stored. So testing is good, but there's not a question of pushing
> this into 9.5.
I'm personally OK with that. The last thing we want to do is make query
costing changes *in haste*.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: PATCH: adaptive ndistinct estimator v4
@ 2015-06-17 14:47 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Jeff Janes <jeff.janes@gmail.com>
1 sibling, 0 replies; 17+ messages in thread
From: Tomas Vondra @ 2015-06-17 14:47 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Robert Haas <robertmhaas@gmail.com>; pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments:
ndistinct-estimator-v5.patch (text/x-diff, 13.2K) download
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 <math.h>
+#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;
+}
end of thread, other threads:[~2015-06-17 14:47 UTC | newest]
Thread overview: 17+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2015-03-31 19:02 Re: PATCH: adaptive ndistinct estimator v4 Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-04-03 13:46 ` Greg Stark <stark@mit.edu>
2015-04-04 23:57 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-04-15 06:45 ` Jeff Janes <jeff.janes@gmail.com>
2015-04-20 05:13 ` Jeff Janes <jeff.janes@gmail.com>
2015-04-30 20:57 ` Robert Haas <robertmhaas@gmail.com>
2015-04-30 21:31 ` Heikki Linnakangas <hlinnaka@iki.fi>
2015-04-30 22:18 ` Robert Haas <robertmhaas@gmail.com>
2015-05-01 01:24 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-05-01 01:20 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-05-01 11:55 ` Robert Haas <robertmhaas@gmail.com>
2015-05-13 21:07 ` Jeff Janes <jeff.janes@gmail.com>
2015-05-15 18:30 ` Robert Haas <robertmhaas@gmail.com>
2015-05-15 19:35 ` Josh Berkus <josh@agliodbs.com>
2015-05-15 19:58 ` Robert Haas <robertmhaas@gmail.com>
2015-05-15 20:00 ` Josh Berkus <josh@agliodbs.com>
2015-06-17 14:47 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox