pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedIncorrect choice of Nested Loop for a skewed distribution
3+ messages / 2 participants
[nested] [flat]
* Incorrect choice of Nested Loop for a skewed distribution
@ 2019-09-03 17:47 Oleg Kharin <ok@uvadrev.ru>
2019-09-05 00:18 ` Re: Incorrect choice of Nested Loop for a skewed distribution Justin Pryzby <pryzby@telsasoft.com>
0 siblings, 1 reply; 3+ messages in thread
From: Oleg Kharin @ 2019-09-03 17:47 UTC (permalink / raw)
To: pgsql-performance@lists.postgresql.org
Hi All,
With PostgreSQL 10 and 11, the planner doesn't use the lists of most
common values to determine the selectivity of "=" for Nested Loop as it
does for a normal inner join in eqjoinsel_inner(). Incorrect choice of a
nested loops join strategy causes poor query performance.
To demonstrate it one can make the following test case:
create table t(f integer not null,g integer not null);
create table u(f integer not null,g integer not null);
create sequence s cache 1000;
insert into t select 0,s from (select nextval('s') as s) as d;
insert into t select 0,s from (select nextval('s') as s) as d;
insert into t select 0,s from (select nextval('s') as s from t,t t1,t
t2) as d;
insert into t select 0,s from (select nextval('s') as s from t,t t1,t
t2,t t3) as d;
insert into t(f,g) select g,f from t;
insert into u select * from t;
create index t_f on t(f);
vacuum analyze;
The columns f and g of both tables t and u have a skewed distribution:
10010 values of 0 and 10010 unique values starting from 1.
Let's see query plan for the join of t and u:
explain analyze select * from t,u where t.f=u.f and t.g=u.g;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.29..7629.95 rows=25055030 width=16) (actual
time=0.042..22540.629 rows=20020 loops=1)
-> Seq Scan on u (cost=0.00..289.20 rows=20020 width=8) (actual
time=0.011..3.025 rows=20020 loops=1)
-> Index Scan using t_f on t (cost=0.29..0.36 rows=1 width=8)
(actual time=0.565..1.125 rows=1 loops=20020)
Index Cond: (f = u.f)
Filter: (u.g = g)
Rows Removed by Filter: 5004
Planning Time: 0.394 ms
Execution Time: 22542.639 ms
After dropping the index
drop index t_f;
we obtain much better query plan (without Nested Loop):
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
Merge Join (cost=3439.09..442052.26 rows=25055030 width=16) (actual
time=15.708..32.735 rows=20020 loops=1)
Merge Cond: ((t.f = u.f) AND (t.g = u.g))
-> Sort (cost=1719.54..1769.59 rows=20020 width=8) (actual
time=8.189..10.189 rows=20020 loops=1)
Sort Key: t.f, t.g
Sort Method: quicksort Memory: 1707kB
-> Seq Scan on t (cost=0.00..289.20 rows=20020 width=8)
(actual time=0.012..2.958 rows=20020 loops=1)
-> Sort (cost=1719.54..1769.59 rows=20020 width=8) (actual
time=7.510..9.459 rows=20020 loops=1)
Sort Key: u.f, u.g
Sort Method: quicksort Memory: 1707kB
-> Seq Scan on u (cost=0.00..289.20 rows=20020 width=8)
(actual time=0.008..2.748 rows=20020 loops=1)
Planning Time: 0.239 ms
Execution Time: 34.585 ms
Using MCV lists in var_eq_non_const() would prevent from choosing Nested
Loop in such cases.
Regards,
Oleg Kharin
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Incorrect choice of Nested Loop for a skewed distribution
2019-09-03 17:47 Incorrect choice of Nested Loop for a skewed distribution Oleg Kharin <ok@uvadrev.ru>
@ 2019-09-05 00:18 ` Justin Pryzby <pryzby@telsasoft.com>
2019-09-06 05:02 ` Re: Incorrect choice of Nested Loop for a skewed distribution Oleg Kharin <ok@uvadrev.ru>
0 siblings, 1 reply; 3+ messages in thread
From: Justin Pryzby @ 2019-09-05 00:18 UTC (permalink / raw)
To: Oleg Kharin <ok@uvadrev.ru>; +Cc: pgsql-performance@lists.postgresql.org
On Tue, Sep 03, 2019 at 09:47:42PM +0400, Oleg Kharin wrote:
> Hi All,
>
> With PostgreSQL 10 and 11, the planner doesn't use the lists of most common
> values to determine the selectivity of "=" for Nested Loop as it does for a
> normal inner join in eqjoinsel_inner(). Incorrect choice of a nested loops
> join strategy causes poor query performance.
> To demonstrate it one can make the following test case:
...
> The columns f and g of both tables t and u have a skewed distribution: 10010
> values of 0 and 10010 unique values starting from 1.
> Let's see query plan for the join of t and u:
>
> explain analyze select * from t,u where t.f=u.f and t.g=u.g;
> Nested Loop (cost=0.29..7629.95 rows=25055030 width=16) (actual time=0.042..22540.629 rows=20020 loops=1)
> -> Seq Scan on u (cost=0.00..289.20 rows=20020 width=8) (actual time=0.011..3.025 rows=20020 loops=1)
> -> Index Scan using t_f on t (cost=0.29..0.36 rows=1 width=8) (actual time=0.565..1.125 rows=1 loops=20020)
> Index Cond: (f = u.f)
> Filter: (u.g = g)
> Rows Removed by Filter: 5004
> Planning Time: 0.394 ms
> Execution Time: 22542.639 ms
>
> After dropping the index
> drop index t_f;
> we obtain much better query plan (without Nested Loop):
> Merge Join (cost=3439.09..442052.26 rows=25055030 width=16) (actual time=15.708..32.735 rows=20020 loops=1)
> Merge Cond: ((t.f = u.f) AND (t.g = u.g))
> -> Sort (cost=1719.54..1769.59 rows=20020 width=8) (actual time=8.189..10.189 rows=20020 loops=1)
> Sort Key: t.f, t.g
> Sort Method: quicksort Memory: 1707kB
> -> Seq Scan on t (cost=0.00..289.20 rows=20020 width=8) (actual time=0.012..2.958 rows=20020 loops=1)
> -> Sort (cost=1719.54..1769.59 rows=20020 width=8) (actual time=7.510..9.459 rows=20020 loops=1)
> Sort Key: u.f, u.g
> Sort Method: quicksort Memory: 1707kB
> -> Seq Scan on u (cost=0.00..289.20 rows=20020 width=8) (actual time=0.008..2.748 rows=20020 loops=1)
> Planning Time: 0.239 ms
> Execution Time: 34.585 ms
> Nested Loop (cost=0.29.. 7629.95 rows=25055030 width=16) (actual...
> Merge Join (cost=3439.09..442052.26 rows=25055030 width=16) (actual...
When you dropped the index, you necessarily refused the plan involving index scan.
So it did merge join instead (which it thinks of as expensive because it has to
sort both sides).
As you saw, the rowcount estimate of the join result is badly off. But that's
true of both plans.
Choice of join type is affected by the size of its *inputs*, but doesn't and
shouldn't have any effect on the result rowcount (or its) estimate. The
rowcount *output* of the join would only affect any *following* plan nodes (of
which there are none in this case).
You suggested using the MCV list, but I don't think that's possible, since the
nested loop is evaluating its "inner" table multiple times, in a "loop":
> -> Index Scan using t_f on t (cost=0.29..0.36 rows=1 width=8) (actual time=0.565..1.125 rows=1 loops=20020)
Hypothetically, one could plan the query 20k times, for each value of u.f and
u.g, but that's tantamount to actually executing the query, which is why it
uses (I gather) var_eq_non_const.
If you enable BUFFERS, you can see:
postgres=# explain (analyze on,buffers) select * from t,u WHERE t.g=u.g AND t.f=u.f ;
Nested Loop (cost=0.29..7629.95 rows=25055030 width=16) (actual time=0.031..22634.482 rows=20020 loops=1)
Buffers: shared hit=770913
-> Seq Scan on t (cost=0.00..289.20 rows=20020 width=8) (actual time=0.011..22.883 rows=20020 loops=1)
Buffers: shared hit=89
-> Index Scan using u_f_idx on u (cost=0.29..0.36 rows=1 width=8) (actual time=0.596..1.125 rows=1 loops=20020)
...
Buffers: shared hit=770824
vs.
postgres=# SET enable_nestloop=off;
postgres=# explain (analyze on,buffers) select * from t,u WHERE t.g=u.g AND t.f=u.f ;
Merge Join (cost=3439.09..442052.26 rows=25055030 width=16) (actual time=74.262..187.454 rows=20020 loops=1)
Merge Cond: ((t.g = u.g) AND (t.f = u.f))
Buffers: shared hit=178
...
So the nest loop plan is hitting 770k buffer pages (5GB) while looping 20k
times, rather than 178 buffers when each page is read once (to sort).
Perhaps you could get a good plan by playing with these, but it's unclear why
that's necessary.
effective_cache_size | 1280
cpu_index_tuple_cost | 0.005
cpu_operator_cost | 0.0025
cpu_tuple_cost | 0.01
random_page_cost | 4
seq_page_cost | 1
Also, since PG96, FKs can improve join estimates:
postgres=# CREATE UNIQUE INDEX ON u(f,g);
postgres=# CREATE UNIQUE INDEX ON t(f,g);
postgres=# ALTER TABLE t ADD CONSTRAINT fk_f FOREIGN KEY (f,g) REFERENCES u(f,g);
postgres=# ALTER TABLE u ADD CONSTRAINT fk_u FOREIGN KEY (f,g) REFERENCES t(f,g);
postgres=# explain analyze select * from t,u WHERE t.g=u.g AND t.f=u.f ;
Hash Join (cost=589.50..999.14 rows=20020 width=16) (actual time=29.054..69.296 rows=20020 loops=1)
Hash Cond: ((t.g = u.g) AND (t.f = u.f))
-> Seq Scan on t (cost=0.00..289.20 rows=20020 width=8) (actual time=0.016..11.331 rows=20020 loops=1)
-> Hash (cost=289.20..289.20 rows=20020 width=8) (actual time=28.980..28.981 rows=20020 loops=1)
Buckets: 32768 Batches: 1 Memory Usage: 1039kB
-> Seq Scan on u (cost=0.00..289.20 rows=20020 width=8) (actual time=0.010..12.730 rows=20020 loops=1)
Justin
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Incorrect choice of Nested Loop for a skewed distribution
2019-09-03 17:47 Incorrect choice of Nested Loop for a skewed distribution Oleg Kharin <ok@uvadrev.ru>
2019-09-05 00:18 ` Re: Incorrect choice of Nested Loop for a skewed distribution Justin Pryzby <pryzby@telsasoft.com>
@ 2019-09-06 05:02 ` Oleg Kharin <ok@uvadrev.ru>
0 siblings, 0 replies; 3+ messages in thread
From: Oleg Kharin @ 2019-09-06 05:02 UTC (permalink / raw)
To: Justin Pryzby <pryzby@telsasoft.com>; +Cc: pgsql-performance@lists.postgresql.org
Thank you Justin!
On Wed, 04 Sep 2019 17:18:36 -0700 (PDT), Justin Pryzby wrote:
> When you dropped the index, you necessarily refused the plan involving
> index scan.
> So it did merge join instead (which it thinks of as expensive because it has to
> sort both sides).
>
> As you saw, the rowcount estimate of the join result is badly off. But that's
> true of both plans.
>
> Choice of join type is affected by the size of its *inputs*, but doesn't and
> shouldn't have any effect on the result rowcount (or its) estimate. The
> rowcount *output* of the join would only affect any *following* plan nodes (of
> which there are none in this case).
>
> You suggested using the MCV list, but I don't think that's possible, since the
> nested loop is evaluating its "inner" table multiple times, in a "loop":
>
>> -> Index Scan using t_f on t (cost=0.29..0.36 rows=1 width=8) (actual time=0.565..1.125 rows=1 loops=20020)
> Hypothetically, one could plan the query 20k times, for each value of u.f and
> u.g, but that's tantamount to actually executing the query, which is why it
> uses (I gather) var_eq_non_const.
In fact the planner has information about the outer loop relation when
it is estimating the number of inner loop rows for a nested-loop join.
It ignores this information and considers the outer/inner loop relations
as independent. So it uses for the rowcount estimate the number of
distinct values only, not MCV lists of both tables.
For the test case above, the planner estimates the selectivity of the
clause "t.f=u.f" as 1/10011. It hopes to scan 1/10011*20020=2 rows in a
inner loop for each row of the outer loop. In fact it scans 10010 rows
10010 times and 1 row 10010 times. The average number of rows scanned in
a inner loop is (10010*10010+10010)/20020=5005. That is badly off from 2
rows expected. The planner should use 5005/20020 as a more accurate
value for the effective selectivity of "t.f=u.f".
I tried to make improvements to the function var_eq_non_const() so that
it calculates the effective selectivity using MCV lists if possible. The
patch for PostgreSQL 11.5 is attached to the letter.
The patched PostgreSQL chooses an optimal plan for the test case. As a
result the query execution time is reduced by more than 600 times.
Now if we force the planner to choose the nested-loop join
set enable_mergejoin=off;
set enable_hashjoin=off;
explain analyze select * from t,u where t.f=u.f and t.g=u.g;
Nested Loop (cost=0.29..2261681.75 rows=25055030 width=16) (actual
time=0.048..22519.232 rows=20020 loops=1)
-> Seq Scan on u (cost=0.00..289.20 rows=20020 width=8) (actual
time=0.012..2.970 rows=20020 loops=1)
-> Index Scan using t_f on t (cost=0.29..100.44 rows=1252 width=8)
(actual time=0.565..1.124 rows=1 loops=20020)
Index Cond: (f = u.f)
Filter: (u.g = g)
Rows Removed by Filter: 5004
Planning Time: 0.188 ms
Execution Time: 22521.248 ms
we will see that the cost of the index scan is increased from 0.36 to
100.44, which is much more realistic and reflects 2 to 5005 rows ratio.
Regards,
Oleg
--- a/src/backend/utils/adt/selfuncs.c 2019-08-06 01:14:59.000000000 +0400
+++ b/src/backend/utils/adt/selfuncs.c 2019-09-06 08:23:34.932978863 +0400
@@ -161,7 +161,7 @@
static double var_eq_const(VariableStatData *vardata, Oid operator,
Datum constval, bool constisnull,
bool varonleft, bool negate);
-static double var_eq_non_const(VariableStatData *vardata, Oid operator,
+static double var_eq_non_const(VariableStatData *vardata, PlannerInfo *root, List *args, Oid operator,
Node *other,
bool varonleft, bool negate);
static double ineq_histogram_selectivity(PlannerInfo *root,
@@ -291,7 +291,7 @@
((Const *) other)->constisnull,
varonleft, negate);
else
- selec = var_eq_non_const(&vardata, operator, other,
+ selec = var_eq_non_const(&vardata, root, args, operator, other, /* root, args for detailed statistics of variable on the other hand */
varonleft, negate);
ReleaseVariableStats(vardata);
@@ -453,11 +453,161 @@
return selec;
}
+/* var_eq_var_mcvs - selectivity of "var = var2" using MCV lists
+ * based on eqjoinsel_inner() code
+ */
+static bool
+var_eq_var_mcvs(Oid operator, VariableStatData *vardata1, VariableStatData *vardata2,
+ AttStatsSlot *sslot1, double nullfrac1,
+ double nd1, double *selec)
+{
+ Oid opfuncoid;
+ Form_pg_statistic stats2 = NULL;
+ bool have_mcvs2 = false;
+ AttStatsSlot sslot2;
+ bool result = false; /* managed to use of the MCV lists */
+
+ opfuncoid = get_opcode(operator);
+
+ memset(&sslot2, 0, sizeof(sslot2));
+
+ if (HeapTupleIsValid(vardata2->statsTuple))
+ {
+ /* note we allow use of nullfrac regardless of security check */
+ stats2 = (Form_pg_statistic) GETSTRUCT(vardata2->statsTuple);
+ if (statistic_proc_security_check(vardata2, opfuncoid))
+ have_mcvs2 = get_attstatsslot(&sslot2, vardata2->statsTuple,
+ STATISTIC_KIND_MCV, InvalidOid,
+ ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS);
+ }
+
+ if (have_mcvs2 && stats2->stanullfrac < 1.0 && sslot2.nvalues > 0) /* we use MCV list for selectivity estimate if var2 has MCV statistics, has any not null value and MCV list is not empty */
+ {
+ /*
+ * We have most-common-value lists for both relations. Run through
+ * the lists to see which MCVs actually join to each other with the
+ * given operator. This allows us to determine the exact join
+ * selectivity for the portion of the relations represented by the MCV
+ * lists. We still have to estimate for the remaining population, but
+ * in a skewed distribution this gives us a big leg up in accuracy.
+ * For motivation see the analysis in Y. Ioannidis and S.
+ * Christodoulakis, "On the propagation of errors in the size of join
+ * results", Technical Report 1018, Computer Science Dept., University
+ * of Wisconsin, Madison, March 1992 (available from ftp.cs.wisc.edu).
+ */
+ FmgrInfo eqproc;
+ bool *hasmatch1;
+ bool *hasmatch2;
+ /*double nullfrac1 = stats1->stanullfrac;*/
+ double nullfrac2 = stats2->stanullfrac;
+ double matchprodfreq,
+ matchfreq1,
+ matchfreq2,
+ unmatchfreq1,
+ unmatchfreq2,
+ otherfreq1,
+ otherfreq2,
+ totalsel2;
+ int i,
+ nmatches;
+
+ fmgr_info(opfuncoid, &eqproc);
+ hasmatch1 = (bool *) palloc0(sslot1->nvalues * sizeof(bool));
+ hasmatch2 = (bool *) palloc0(sslot2.nvalues * sizeof(bool));
+
+ /*
+ * Note we assume that each MCV will match at most one member of the
+ * other MCV list. If the operator isn't really equality, there could
+ * be multiple matches --- but we don't look for them, both for speed
+ * and because the math wouldn't add up...
+ */
+ matchprodfreq = 0.0;
+ nmatches = 0;
+ for (i = 0; i < sslot1->nvalues; i++)
+ {
+ int j;
+
+ for (j = 0; j < sslot2.nvalues; j++)
+ {
+ if (hasmatch2[j])
+ continue;
+ if (DatumGetBool(FunctionCall2Coll(&eqproc,
+ DEFAULT_COLLATION_OID,
+ sslot1->values[i],
+ sslot2.values[j])))
+ {
+ hasmatch1[i] = hasmatch2[j] = true;
+ matchprodfreq += sslot1->numbers[i] * sslot2.numbers[j];
+ nmatches++;
+ break;
+ }
+ }
+ }
+ CLAMP_PROBABILITY(matchprodfreq);
+ /* Sum up frequencies of matched and unmatched MCVs */
+ matchfreq1 = unmatchfreq1 = 0.0;
+ for (i = 0; i < sslot1->nvalues; i++)
+ {
+ if (hasmatch1[i])
+ matchfreq1 += sslot1->numbers[i];
+ else
+ unmatchfreq1 += sslot1->numbers[i];
+ }
+ CLAMP_PROBABILITY(matchfreq1);
+ CLAMP_PROBABILITY(unmatchfreq1);
+ matchfreq2 = unmatchfreq2 = 0.0;
+ for (i = 0; i < sslot2.nvalues; i++)
+ {
+ if (hasmatch2[i])
+ matchfreq2 += sslot2.numbers[i];
+ else
+ unmatchfreq2 += sslot2.numbers[i];
+ }
+ CLAMP_PROBABILITY(matchfreq2);
+ CLAMP_PROBABILITY(unmatchfreq2);
+ pfree(hasmatch1);
+ pfree(hasmatch2);
+
+ /*
+ * Compute total frequency of non-null values that are not in the MCV
+ * lists.
+ */
+ otherfreq1 = 1.0 - nullfrac1 - matchfreq1 - unmatchfreq1;
+ otherfreq2 = 1.0 - nullfrac2 - matchfreq2 - unmatchfreq2;
+ CLAMP_PROBABILITY(otherfreq1);
+ CLAMP_PROBABILITY(otherfreq2);
+
+ /*
+ * We can estimate the total selectivity from the point of view of
+ * relation 1 as: the known selectivity for matched MCVs, plus
+ * unmatched MCVs that are assumed to match against random members of
+ * relation 2's non-MCV population, plus non-MCV values that are
+ * assumed to match against random members of relation 2's unmatched
+ * MCVs plus non-MCV values.
+ */
+ /* Same estimate from the point of view of relation 2. */
+ totalsel2 = matchprodfreq;
+ if (nd1 > sslot1->nvalues)
+ totalsel2 += unmatchfreq2 * otherfreq1 / (nd1 - sslot1->nvalues);
+ if (nd1 > nmatches)
+ totalsel2 += otherfreq2 * (otherfreq1 + unmatchfreq1) /
+ (nd1 - nmatches);
+
+ *selec = totalsel2/(1-nullfrac2);
+ result = true;
+
+ }
+
+ free_attstatsslot(&sslot2);
+
+ return result;
+}
+
/*
* var_eq_non_const --- eqsel for var = something-other-than-const case
*/
static double
-var_eq_non_const(VariableStatData *vardata, Oid operator,
+var_eq_non_const(VariableStatData *vardata, PlannerInfo *root, List *args, Oid operator,
Node *other,
bool varonleft, bool negate)
{
@@ -513,8 +663,20 @@
*/
if (get_attstatsslot(&sslot, vardata->statsTuple,
STATISTIC_KIND_MCV, InvalidOid,
+ ATTSTATSSLOT_VALUES | /* need MCV list */
ATTSTATSSLOT_NUMBERS))
{
+ if (sslot.nvalues > 0) /* only if MCV list is not empty */
+ {
+ Node *node2;
+ VariableStatData vardata2;
+
+ node2 = varonleft ? lsecond(args) : linitial(args); /* variable2 is on the other side */
+ examine_variable(root, node2, 0, &vardata2); /* data of the other side */
+ if (vardata2.rel) /* rel from the other side */
+ var_eq_var_mcvs(operator, vardata, &vardata2, &sslot, nullfrac, ndistinct, &selec); /* trying to estimate the selectivity more accurate using the MCV lists */
+ ReleaseVariableStats(vardata2);
+ }
if (sslot.nnumbers > 0 && selec > sslot.numbers[0])
selec = sslot.numbers[0];
free_attstatsslot(&sslot);
Attachments:
[text/plain] nestloop.patch (7.0K, ../../a5fb2f9d-a8ac-2c8a-22fc-6d5f62f6d6b3@uvadrev.ru/2-nestloop.patch)
download | inline diff:
--- a/src/backend/utils/adt/selfuncs.c 2019-08-06 01:14:59.000000000 +0400
+++ b/src/backend/utils/adt/selfuncs.c 2019-09-06 08:23:34.932978863 +0400
@@ -161,7 +161,7 @@
static double var_eq_const(VariableStatData *vardata, Oid operator,
Datum constval, bool constisnull,
bool varonleft, bool negate);
-static double var_eq_non_const(VariableStatData *vardata, Oid operator,
+static double var_eq_non_const(VariableStatData *vardata, PlannerInfo *root, List *args, Oid operator,
Node *other,
bool varonleft, bool negate);
static double ineq_histogram_selectivity(PlannerInfo *root,
@@ -291,7 +291,7 @@
((Const *) other)->constisnull,
varonleft, negate);
else
- selec = var_eq_non_const(&vardata, operator, other,
+ selec = var_eq_non_const(&vardata, root, args, operator, other, /* root, args for detailed statistics of variable on the other hand */
varonleft, negate);
ReleaseVariableStats(vardata);
@@ -453,11 +453,161 @@
return selec;
}
+/* var_eq_var_mcvs - selectivity of "var = var2" using MCV lists
+ * based on eqjoinsel_inner() code
+ */
+static bool
+var_eq_var_mcvs(Oid operator, VariableStatData *vardata1, VariableStatData *vardata2,
+ AttStatsSlot *sslot1, double nullfrac1,
+ double nd1, double *selec)
+{
+ Oid opfuncoid;
+ Form_pg_statistic stats2 = NULL;
+ bool have_mcvs2 = false;
+ AttStatsSlot sslot2;
+ bool result = false; /* managed to use of the MCV lists */
+
+ opfuncoid = get_opcode(operator);
+
+ memset(&sslot2, 0, sizeof(sslot2));
+
+ if (HeapTupleIsValid(vardata2->statsTuple))
+ {
+ /* note we allow use of nullfrac regardless of security check */
+ stats2 = (Form_pg_statistic) GETSTRUCT(vardata2->statsTuple);
+ if (statistic_proc_security_check(vardata2, opfuncoid))
+ have_mcvs2 = get_attstatsslot(&sslot2, vardata2->statsTuple,
+ STATISTIC_KIND_MCV, InvalidOid,
+ ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS);
+ }
+
+ if (have_mcvs2 && stats2->stanullfrac < 1.0 && sslot2.nvalues > 0) /* we use MCV list for selectivity estimate if var2 has MCV statistics, has any not null value and MCV list is not empty */
+ {
+ /*
+ * We have most-common-value lists for both relations. Run through
+ * the lists to see which MCVs actually join to each other with the
+ * given operator. This allows us to determine the exact join
+ * selectivity for the portion of the relations represented by the MCV
+ * lists. We still have to estimate for the remaining population, but
+ * in a skewed distribution this gives us a big leg up in accuracy.
+ * For motivation see the analysis in Y. Ioannidis and S.
+ * Christodoulakis, "On the propagation of errors in the size of join
+ * results", Technical Report 1018, Computer Science Dept., University
+ * of Wisconsin, Madison, March 1992 (available from ftp.cs.wisc.edu).
+ */
+ FmgrInfo eqproc;
+ bool *hasmatch1;
+ bool *hasmatch2;
+ /*double nullfrac1 = stats1->stanullfrac;*/
+ double nullfrac2 = stats2->stanullfrac;
+ double matchprodfreq,
+ matchfreq1,
+ matchfreq2,
+ unmatchfreq1,
+ unmatchfreq2,
+ otherfreq1,
+ otherfreq2,
+ totalsel2;
+ int i,
+ nmatches;
+
+ fmgr_info(opfuncoid, &eqproc);
+ hasmatch1 = (bool *) palloc0(sslot1->nvalues * sizeof(bool));
+ hasmatch2 = (bool *) palloc0(sslot2.nvalues * sizeof(bool));
+
+ /*
+ * Note we assume that each MCV will match at most one member of the
+ * other MCV list. If the operator isn't really equality, there could
+ * be multiple matches --- but we don't look for them, both for speed
+ * and because the math wouldn't add up...
+ */
+ matchprodfreq = 0.0;
+ nmatches = 0;
+ for (i = 0; i < sslot1->nvalues; i++)
+ {
+ int j;
+
+ for (j = 0; j < sslot2.nvalues; j++)
+ {
+ if (hasmatch2[j])
+ continue;
+ if (DatumGetBool(FunctionCall2Coll(&eqproc,
+ DEFAULT_COLLATION_OID,
+ sslot1->values[i],
+ sslot2.values[j])))
+ {
+ hasmatch1[i] = hasmatch2[j] = true;
+ matchprodfreq += sslot1->numbers[i] * sslot2.numbers[j];
+ nmatches++;
+ break;
+ }
+ }
+ }
+ CLAMP_PROBABILITY(matchprodfreq);
+ /* Sum up frequencies of matched and unmatched MCVs */
+ matchfreq1 = unmatchfreq1 = 0.0;
+ for (i = 0; i < sslot1->nvalues; i++)
+ {
+ if (hasmatch1[i])
+ matchfreq1 += sslot1->numbers[i];
+ else
+ unmatchfreq1 += sslot1->numbers[i];
+ }
+ CLAMP_PROBABILITY(matchfreq1);
+ CLAMP_PROBABILITY(unmatchfreq1);
+ matchfreq2 = unmatchfreq2 = 0.0;
+ for (i = 0; i < sslot2.nvalues; i++)
+ {
+ if (hasmatch2[i])
+ matchfreq2 += sslot2.numbers[i];
+ else
+ unmatchfreq2 += sslot2.numbers[i];
+ }
+ CLAMP_PROBABILITY(matchfreq2);
+ CLAMP_PROBABILITY(unmatchfreq2);
+ pfree(hasmatch1);
+ pfree(hasmatch2);
+
+ /*
+ * Compute total frequency of non-null values that are not in the MCV
+ * lists.
+ */
+ otherfreq1 = 1.0 - nullfrac1 - matchfreq1 - unmatchfreq1;
+ otherfreq2 = 1.0 - nullfrac2 - matchfreq2 - unmatchfreq2;
+ CLAMP_PROBABILITY(otherfreq1);
+ CLAMP_PROBABILITY(otherfreq2);
+
+ /*
+ * We can estimate the total selectivity from the point of view of
+ * relation 1 as: the known selectivity for matched MCVs, plus
+ * unmatched MCVs that are assumed to match against random members of
+ * relation 2's non-MCV population, plus non-MCV values that are
+ * assumed to match against random members of relation 2's unmatched
+ * MCVs plus non-MCV values.
+ */
+ /* Same estimate from the point of view of relation 2. */
+ totalsel2 = matchprodfreq;
+ if (nd1 > sslot1->nvalues)
+ totalsel2 += unmatchfreq2 * otherfreq1 / (nd1 - sslot1->nvalues);
+ if (nd1 > nmatches)
+ totalsel2 += otherfreq2 * (otherfreq1 + unmatchfreq1) /
+ (nd1 - nmatches);
+
+ *selec = totalsel2/(1-nullfrac2);
+ result = true;
+
+ }
+
+ free_attstatsslot(&sslot2);
+
+ return result;
+}
+
/*
* var_eq_non_const --- eqsel for var = something-other-than-const case
*/
static double
-var_eq_non_const(VariableStatData *vardata, Oid operator,
+var_eq_non_const(VariableStatData *vardata, PlannerInfo *root, List *args, Oid operator,
Node *other,
bool varonleft, bool negate)
{
@@ -513,8 +663,20 @@
*/
if (get_attstatsslot(&sslot, vardata->statsTuple,
STATISTIC_KIND_MCV, InvalidOid,
+ ATTSTATSSLOT_VALUES | /* need MCV list */
ATTSTATSSLOT_NUMBERS))
{
+ if (sslot.nvalues > 0) /* only if MCV list is not empty */
+ {
+ Node *node2;
+ VariableStatData vardata2;
+
+ node2 = varonleft ? lsecond(args) : linitial(args); /* variable2 is on the other side */
+ examine_variable(root, node2, 0, &vardata2); /* data of the other side */
+ if (vardata2.rel) /* rel from the other side */
+ var_eq_var_mcvs(operator, vardata, &vardata2, &sslot, nullfrac, ndistinct, &selec); /* trying to estimate the selectivity more accurate using the MCV lists */
+ ReleaseVariableStats(vardata2);
+ }
if (sslot.nnumbers > 0 && selec > sslot.numbers[0])
selec = sslot.numbers[0];
free_attstatsslot(&sslot);
^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2019-09-06 05:02 UTC | newest]
Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2019-09-03 17:47 Incorrect choice of Nested Loop for a skewed distribution Oleg Kharin <ok@uvadrev.ru>
2019-09-05 00:18 ` Justin Pryzby <pryzby@telsasoft.com>
2019-09-06 05:02 ` Oleg Kharin <ok@uvadrev.ru>
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