Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dTUxm-0006vP-5N for pgsql-hackers@arkaria.postgresql.org; Fri, 07 Jul 2017 15:14:34 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.84_2) (envelope-from ) id 1dTUxl-0005bP-4u for pgsql-hackers@arkaria.postgresql.org; Fri, 07 Jul 2017 15:14:33 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1dTUwB-00008D-LD for pgsql-hackers@postgresql.org; Fri, 07 Jul 2017 15:12:55 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1dTUw7-0005DT-O6 for pgsql-hackers@postgresql.org; Fri, 07 Jul 2017 15:12:55 +0000 Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1]) by sss.pgh.pa.us (8.14.4/8.14.4) with ESMTP id v67FCnBO016233; Fri, 7 Jul 2017 11:12:49 -0400 From: Tom Lane To: Kuntal Ghosh cc: PostgreSQL-development Subject: Re: WIP patch: distinguish selectivity of < from <= and > from >= In-reply-to: <30820.1499376192@sss.pgh.pa.us> References: <12232.1499140410@sss.pgh.pa.us> <4292.1499183421@sss.pgh.pa.us> <8088.1499189048@sss.pgh.pa.us> <29667.1499292924@sss.pgh.pa.us> <30820.1499376192@sss.pgh.pa.us> Comments: In-reply-to Tom Lane message dated "Thu, 06 Jul 2017 17:23:12 -0400" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <16187.1499440276.0@sss.pgh.pa.us> Date: Fri, 07 Jul 2017 11:12:49 -0400 Message-ID: <16232.1499440369@sss.pgh.pa.us> List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-hackers Precedence: bulk Sender: pgsql-hackers-owner@postgresql.org ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <16187.1499440276.1@sss.pgh.pa.us> I wrote: > I looked at that again and realized that one of the answers I was missing > lies in the behavior of analyze.c's compute_scalar_stats(). I updated the patch's comments based on this. I'll just attach the selfuncs.c part of the patch, since nothing else changed. regards, tom lane ------- =_aaaaaaaaaa0 Content-Type: text/x-diff; name="improve-scalar-inequality-estimates-3-selfuncs-only.patch"; charset="us-ascii" Content-ID: <16187.1499440276.2@sss.pgh.pa.us> Content-Description: improve-scalar-inequality-estimates-3-selfuncs-only.patch Content-Transfer-Encoding: quoted-printable diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfu= ncs.c index e103f5e..3ec629b 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -163,7 +163,7 @@ static double var_eq_non_const(VariableStatData *vardat= a, Oid operator, bool varonleft, bool negate); static double ineq_histogram_selectivity(PlannerInfo *root, VariableStatData *vardata, - FmgrInfo *opproc, bool isgt, + FmgrInfo *opproc, bool isgt, bool iseq, Datum constval, Oid consttype); static double eqjoinsel_inner(Oid operator, VariableStatData *vardata1, VariableStatData *vardata2); @@ -544,18 +544,21 @@ neqsel(PG_FUNCTION_ARGS) /* * scalarineqsel - Selectivity of "<", "<=3D", ">", ">=3D" for scalars. * - * This is the guts of both scalarltsel and scalargtsel. The caller has - * commuted the clause, if necessary, so that we can treat the variable as - * being on the left. The caller must also make sure that the other side - * of the clause is a non-null Const, and dissect same into a value and - * datatype. + * This is the guts of scalarltsel/scalarlesel/scalargtsel/scalargesel. + * The isgt and iseq flags distinguish which of the four cases apply. + * + * The caller has commuted the clause, if necessary, so that we can treat + * the variable as being on the left. The caller must also make sure that + * the other side of the clause is a non-null Const, and dissect that into + * a value and datatype. (This definition simplifies some callers that + * want to estimate against a constructed value instead of a Const node.) * * This routine works for any datatype (or pair of datatypes) known to * convert_to_scalar(). If it is applied to some other datatype, * it will return a default estimate. */ static double -scalarineqsel(PlannerInfo *root, Oid operator, bool isgt, +scalarineqsel(PlannerInfo *root, Oid operator, bool isgt, bool iseq, VariableStatData *vardata, Datum constval, Oid consttype) { Form_pg_statistic stats; @@ -587,7 +590,8 @@ scalarineqsel(PlannerInfo *root, Oid operator, bool isg= t, * If there is a histogram, determine which bin the constant falls in, and * compute the resulting contribution to selectivity. */ - hist_selec =3D ineq_histogram_selectivity(root, vardata, &opproc, isgt, + hist_selec =3D ineq_histogram_selectivity(root, vardata, + &opproc, isgt, iseq, constval, consttype); =20 /* @@ -757,7 +761,8 @@ histogram_selectivity(VariableStatData *vardata, FmgrIn= fo *opproc, * ineq_histogram_selectivity - Examine the histogram for scalarineqsel * * Determine the fraction of the variable's histogram population that - * satisfies the inequality condition, ie, VAR < CONST or VAR > CONST. + * satisfies the inequality condition, ie, VAR < (or <=3D, >, >=3D) CONST. + * The isgt and iseq flags distinguish which of the four cases apply. * * Returns -1 if there is no histogram (valid results will always be >=3D = 0). * @@ -768,7 +773,7 @@ histogram_selectivity(VariableStatData *vardata, FmgrIn= fo *opproc, static double ineq_histogram_selectivity(PlannerInfo *root, VariableStatData *vardata, - FmgrInfo *opproc, bool isgt, + FmgrInfo *opproc, bool isgt, bool iseq, Datum constval, Oid consttype) { double hist_selec; @@ -795,11 +800,17 @@ ineq_histogram_selectivity(PlannerInfo *root, if (sslot.nvalues > 1) { /* - * Use binary search to find proper location, ie, the first slot - * at which the comparison fails. (If the given operator isn't - * actually sort-compatible with the histogram, you'll get garbage - * results ... but probably not any more garbage-y than you would - * from the old linear search.) + * Use binary search to find the desired location, namely the + * right end of the histogram bin containing the comparison value, + * which is the leftmost entry for which the comparison operator + * succeeds (if isgt) or fails (if !isgt). (If the given operator + * isn't actually sort-compatible with the histogram, you'll get + * garbage results ... but probably not any more garbage-y than + * you would have from the old linear search.) + * + * In this loop, we pay no attention to whether the operator iseq + * or not; that detail will be mopped up below. (We cannot tell, + * anyway, whether the operator thinks the values are equal.) * * If the binary search accesses the first or last histogram * entry, we try to replace that endpoint with the true column min @@ -864,25 +875,74 @@ ineq_histogram_selectivity(PlannerInfo *root, =20 if (lobound <=3D 0) { - /* Constant is below lower histogram boundary. */ + /* + * Constant is below lower histogram boundary. More + * precisely, we have found that no entry in the histogram + * satisfies the inequality clause (if !isgt) or they all do + * (if isgt). We estimate that that's true of the entire + * table, so set histfrac to 0.0 (which we'll flip to 1.0 + * below, if isgt). + */ histfrac =3D 0.0; } else if (lobound >=3D sslot.nvalues) { - /* Constant is above upper histogram boundary. */ + /* + * Inverse case: constant is above upper histogram boundary. + */ histfrac =3D 1.0; } else { + /* We have values[i-1] <=3D constant <=3D values[i]. */ int i =3D lobound; + double eq_selec =3D 0; double val, high, low; double binfrac; =20 /* - * We have values[i-1] <=3D constant <=3D values[i]. + * In the cases where we'll need it below, obtain an estimate + * of the selectivity of "x =3D constval". We use a calculation + * similar to what var_eq_const() does for a non-MCV constant, + * ie, estimate that all distinct non-MCV values occur equally + * often. But multiplication by "1.0 - sumcommon - nullfrac" + * will be done by our caller, so we shouldn't do that here. + * Therefore we can't try to clamp the estimate by reference + * to the least common MCV; the result would be too small. * + * Note: since this is effectively assuming that constval + * isn't an MCV, it's logically dubious if constval in fact is + * one. But we have to apply *some* correction for equality, + * and anyway we cannot tell if constval is an MCV, since we + * don't have a suitable equality operator at hand. + */ + if (i =3D=3D 1 || isgt =3D=3D iseq) + { + double otherdistinct; + bool isdefault; + AttStatsSlot mcvslot; + + /* Get estimated number of distinct values */ + otherdistinct =3D get_variable_numdistinct(vardata, + &isdefault); + + /* Subtract off the number of known MCVs */ + if (get_attstatsslot(&mcvslot, vardata->statsTuple, + STATISTIC_KIND_MCV, InvalidOid, + ATTSTATSSLOT_NUMBERS)) + { + otherdistinct -=3D mcvslot.nnumbers; + free_attstatsslot(&mcvslot); + } + + /* If result doesn't seem sane, leave eq_selec at 0 */ + if (otherdistinct > 1) + eq_selec =3D 1.0 / otherdistinct; + } + + /* * Convert the constant and the two nearest bin boundary * values to a uniform comparison scale, and do a linear * interpolation within this bin. @@ -936,13 +996,54 @@ ineq_histogram_selectivity(PlannerInfo *root, */ histfrac =3D (double) (i - 1) + binfrac; histfrac /=3D (double) (sslot.nvalues - 1); + + /* + * At this point, histfrac is an estimate of the fraction of + * the population represented by the histogram that satisfies + * "x <=3D constval". Somewhat remarkably, this statement is + * true regardless of which operator we were doing the probes + * with, so long as convert_to_scalar() delivers reasonable + * results. If the probe constant is equal to some histogram + * entry, we would have considered the bin to the left of that + * entry if probing with "<" or ">=3D", or the bin to the right + * if probing with "<=3D" or ">"; but binfrac would have come + * out as 1.0 in the first case and 0.0 in the second, leading + * to the same histfrac in either case. For probe constants + * between histogram entries, we find the same bin and get the + * same estimate with any operator. + * + * The fact that the estimate corresponds to "x <=3D constval" + * and not "x < constval" is because of the way that ANALYZE + * constructs the histogram: each entry is, effectively, the + * rightmost value in its sample bucket. So selectivity + * values that are exact multiples of 1/(histogram_size-1) + * should be understood as estimates including a histogram + * entry plus everything to its left. + * + * However, that breaks down for the first histogram entry, + * which necessarily is the leftmost value in its sample + * bucket. That means the first histogram bin is slightly + * narrower than the rest, by an amount equal to eq_selec. + * Another way to say that is that we want "x <=3D leftmost" to + * be estimated as eq_selec not zero. So, if we're dealing + * with the first bin (i=3D=3D1), rescale to make that true while + * adjusting the rest of that bin linearly. + */ + if (i =3D=3D 1) + histfrac +=3D eq_selec * (1.0 - binfrac); + + /* + * "x <=3D constval" is good if we want an estimate for "<=3D" or + * ">", but if we are estimating for "<" or ">=3D", we now need + * to decrease the estimate by eq_selec. + */ + if (isgt =3D=3D iseq) + histfrac -=3D eq_selec; } =20 /* - * Now histfrac =3D fraction of histogram entries below the - * constant. - * - * Account for "<" vs ">" + * Now the estimate is finished for "<" and "<=3D" cases. If we are + * estimating for ">" or ">=3D", flip it. */ hist_selec =3D isgt ? (1.0 - histfrac) : histfrac; =20 @@ -950,16 +1051,21 @@ ineq_histogram_selectivity(PlannerInfo *root, * The histogram boundaries are only approximate to begin with, * and may well be out of date anyway. Therefore, don't believe * extremely small or large selectivity estimates --- unless we - * got actual current endpoint values from the table. + * got actual current endpoint values from the table, in which + * case just do the usual sanity clamp. Somewhat arbitrarily, we + * set the cutoff for other cases at a hundredth of the histogram + * resolution. */ if (have_end) CLAMP_PROBABILITY(hist_selec); else { - if (hist_selec < 0.0001) - hist_selec =3D 0.0001; - else if (hist_selec > 0.9999) - hist_selec =3D 0.9999; + double cutoff =3D 0.01 / (double) (sslot.nvalues - 1); + + if (hist_selec < cutoff) + hist_selec =3D cutoff; + else if (hist_selec > 1.0 - cutoff) + hist_selec =3D 1.0 - cutoff; } } =20 @@ -970,10 +1076,11 @@ ineq_histogram_selectivity(PlannerInfo *root, } =20 /* - * scalarltsel - Selectivity of "<" (also "<=3D") for scalars. + * Common wrapper function for the selectivity estimators that simply + * invoke scalarineqsel(). */ -Datum -scalarltsel(PG_FUNCTION_ARGS) +static Datum +scalarineqsel_wrapper(PG_FUNCTION_ARGS, bool isgt, bool iseq) { PlannerInfo *root =3D (PlannerInfo *) PG_GETARG_POINTER(0); Oid operator =3D PG_GETARG_OID(1); @@ -984,7 +1091,6 @@ scalarltsel(PG_FUNCTION_ARGS) bool varonleft; Datum constval; Oid consttype; - bool isgt; double selec; =20 /* @@ -1019,14 +1125,8 @@ scalarltsel(PG_FUNCTION_ARGS) /* * Force the var to be on the left to simplify logic in scalarineqsel. */ - if (varonleft) + if (!varonleft) { - /* we have var < other */ - isgt =3D false; - } - else - { - /* we have other < var, commute to make var > other */ operator =3D get_commutator(operator); if (!operator) { @@ -1034,10 +1134,12 @@ scalarltsel(PG_FUNCTION_ARGS) ReleaseVariableStats(vardata); PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL); } - isgt =3D true; + isgt =3D !isgt; } =20 - selec =3D scalarineqsel(root, operator, isgt, &vardata, constval, constty= pe); + /* The rest of the work is done by scalarineqsel(). */ + selec =3D scalarineqsel(root, operator, isgt, iseq, + &vardata, constval, consttype); =20 ReleaseVariableStats(vardata); =20 @@ -1045,78 +1147,39 @@ scalarltsel(PG_FUNCTION_ARGS) } =20 /* - * scalargtsel - Selectivity of ">" (also ">=3D") for integers. + * scalarltsel - Selectivity of "<" for scalars. */ Datum -scalargtsel(PG_FUNCTION_ARGS) +scalarltsel(PG_FUNCTION_ARGS) { - PlannerInfo *root =3D (PlannerInfo *) PG_GETARG_POINTER(0); - Oid operator =3D PG_GETARG_OID(1); - List *args =3D (List *) PG_GETARG_POINTER(2); - int varRelid =3D PG_GETARG_INT32(3); - VariableStatData vardata; - Node *other; - bool varonleft; - Datum constval; - Oid consttype; - bool isgt; - double selec; - - /* - * If expression is not variable op something or something op variable, - * then punt and return a default estimate. - */ - if (!get_restriction_variable(root, args, varRelid, - &vardata, &other, &varonleft)) - PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL); - - /* - * Can't do anything useful if the something is not a constant, either. - */ - if (!IsA(other, Const)) - { - ReleaseVariableStats(vardata); - PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL); - } - - /* - * If the constant is NULL, assume operator is strict and return zero, ie, - * operator will never return TRUE. - */ - if (((Const *) other)->constisnull) - { - ReleaseVariableStats(vardata); - PG_RETURN_FLOAT8(0.0); - } - constval =3D ((Const *) other)->constvalue; - consttype =3D ((Const *) other)->consttype; - - /* - * Force the var to be on the left to simplify logic in scalarineqsel. - */ - if (varonleft) - { - /* we have var > other */ - isgt =3D true; - } - else - { - /* we have other > var, commute to make var < other */ - operator =3D get_commutator(operator); - if (!operator) - { - /* Use default selectivity (should we raise an error instead?) */ - ReleaseVariableStats(vardata); - PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL); - } - isgt =3D false; - } + return scalarineqsel_wrapper(fcinfo, false, false); +} =20 - selec =3D scalarineqsel(root, operator, isgt, &vardata, constval, constty= pe); +/* + * scalarlesel - Selectivity of "<=3D" for scalars. + */ +Datum +scalarlesel(PG_FUNCTION_ARGS) +{ + return scalarineqsel_wrapper(fcinfo, false, true); +} =20 - ReleaseVariableStats(vardata); +/* + * scalargtsel - Selectivity of ">" for scalars. + */ +Datum +scalargtsel(PG_FUNCTION_ARGS) +{ + return scalarineqsel_wrapper(fcinfo, true, false); +} =20 - PG_RETURN_FLOAT8((float8) selec); +/* + * scalargesel - Selectivity of ">=3D" for scalars. + */ +Datum +scalargesel(PG_FUNCTION_ARGS) +{ + return scalarineqsel_wrapper(fcinfo, true, true); } =20 /* @@ -2721,7 +2784,7 @@ neqjoinsel(PG_FUNCTION_ARGS) } =20 /* - * scalarltjoinsel - Join selectivity of "<" and "<=3D" for scalars + * scalarltjoinsel - Join selectivity of "<" for scalars */ Datum scalarltjoinsel(PG_FUNCTION_ARGS) @@ -2730,7 +2793,16 @@ scalarltjoinsel(PG_FUNCTION_ARGS) } =20 /* - * scalargtjoinsel - Join selectivity of ">" and ">=3D" for scalars + * scalarlejoinsel - Join selectivity of "<=3D" for scalars + */ +Datum +scalarlejoinsel(PG_FUNCTION_ARGS) +{ + PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL); +} + +/* + * scalargtjoinsel - Join selectivity of ">" for scalars */ Datum scalargtjoinsel(PG_FUNCTION_ARGS) @@ -2739,6 +2811,15 @@ scalargtjoinsel(PG_FUNCTION_ARGS) } =20 /* + * scalargejoinsel - Join selectivity of ">=3D" for scalars + */ +Datum +scalargejoinsel(PG_FUNCTION_ARGS) +{ + PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL); +} + +/* * patternjoinsel - Generic code for pattern-match join selectivity. */ static double @@ -3035,13 +3116,13 @@ mergejoinscansel(PlannerInfo *root, Node *clause, * fraction that's <=3D the right-side maximum value. But only believe * non-default estimates, else stick with our 1.0. */ - selec =3D scalarineqsel(root, leop, isgt, &leftvar, + selec =3D scalarineqsel(root, leop, isgt, true, &leftvar, rightmax, op_righttype); if (selec !=3D DEFAULT_INEQ_SEL) *leftend =3D selec; =20 /* And similarly for the right variable. */ - selec =3D scalarineqsel(root, revleop, isgt, &rightvar, + selec =3D scalarineqsel(root, revleop, isgt, true, &rightvar, leftmax, op_lefttype); if (selec !=3D DEFAULT_INEQ_SEL) *rightend =3D selec; @@ -3065,13 +3146,13 @@ mergejoinscansel(PlannerInfo *root, Node *clause, * minimum value. But only believe non-default estimates, else stick with * our own default. */ - selec =3D scalarineqsel(root, ltop, isgt, &leftvar, + selec =3D scalarineqsel(root, ltop, isgt, false, &leftvar, rightmin, op_righttype); if (selec !=3D DEFAULT_INEQ_SEL) *leftstart =3D selec; =20 /* And similarly for the right variable. */ - selec =3D scalarineqsel(root, revltop, isgt, &rightvar, + selec =3D scalarineqsel(root, revltop, isgt, false, &rightvar, leftmin, op_lefttype); if (selec !=3D DEFAULT_INEQ_SEL) *rightstart =3D selec; @@ -4012,8 +4093,8 @@ convert_numeric_to_scalar(Datum value, Oid typid) } =20 /* - * Can't get here unless someone tries to use scalarltsel/scalargtsel on - * an operator with one numeric and one non-numeric operand. + * Can't get here unless someone tries to use scalarineqsel() on an + * operator with one numeric and one non-numeric operand. */ elog(ERROR, "unsupported type: %u", typid); return 0; @@ -4194,8 +4275,8 @@ convert_string_datum(Datum value, Oid typid) default: =20 /* - * Can't get here unless someone tries to use scalarltsel on an - * operator with one string and one non-string operand. + * Can't get here unless someone tries to use scalarineqsel() on + * an operator with one string and one non-string operand. */ elog(ERROR, "unsupported type: %u", typid); return NULL; @@ -4399,8 +4480,8 @@ convert_timevalue_to_scalar(Datum value, Oid typid) } =20 /* - * Can't get here unless someone tries to use scalarltsel/scalargtsel on - * an operator with one timevalue and one non-timevalue operand. + * Can't get here unless someone tries to use scalarineqsel() on an + * operator with one timevalue and one non-timevalue operand. */ elog(ERROR, "unsupported type: %u", typid); return 0; @@ -5765,7 +5846,8 @@ prefix_selectivity(PlannerInfo *root, VariableStatDat= a *vardata, elog(ERROR, "no >=3D operator for opfamily %u", opfamily); fmgr_info(get_opcode(cmpopr), &opproc); =20 - prefixsel =3D ineq_histogram_selectivity(root, vardata, &opproc, true, + prefixsel =3D ineq_histogram_selectivity(root, vardata, + &opproc, true, true, prefixcon->constvalue, prefixcon->consttype); =20 @@ -5791,7 +5873,8 @@ prefix_selectivity(PlannerInfo *root, VariableStatDat= a *vardata, { Selectivity topsel; =20 - topsel =3D ineq_histogram_selectivity(root, vardata, &opproc, false, + topsel =3D ineq_histogram_selectivity(root, vardata, + &opproc, false, false, greaterstrcon->constvalue, greaterstrcon->consttype); =20 ------- =_aaaaaaaaaa0 Content-Type: text/plain Content-Disposition: inline Content-Transfer-Encoding: 8bit MIME-Version: 1.0 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers ------- =_aaaaaaaaaa0--