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
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.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 *vardata, 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 "<", "<=", ">", ">=" 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 isgt,
* If there is a histogram, determine which bin the constant falls in, and
* compute the resulting contribution to selectivity.
*/
- hist_selec = ineq_histogram_selectivity(root, vardata, &opproc, isgt,
+ hist_selec = ineq_histogram_selectivity(root, vardata,
+ &opproc, isgt, iseq,
constval, consttype);
/*
@@ -757,7 +761,8 @@ histogram_selectivity(VariableStatData *vardata, FmgrInfo *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 <=, >, >=) 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 >= 0).
*
@@ -768,7 +773,7 @@ histogram_selectivity(VariableStatData *vardata, FmgrInfo *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,
if (lobound <= 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 = 0.0;
}
else if (lobound >= sslot.nvalues)
{
- /* Constant is above upper histogram boundary. */
+ /*
+ * Inverse case: constant is above upper histogram boundary.
+ */
histfrac = 1.0;
}
else
{
+ /* We have values[i-1] <= constant <= values[i]. */
int i = lobound;
+ double eq_selec = 0;
double val,
high,
low;
double binfrac;
/*
- * We have values[i-1] <= constant <= values[i].
+ * In the cases where we'll need it below, obtain an estimate
+ * of the selectivity of "x = 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 == 1 || isgt == iseq)
+ {
+ double otherdistinct;
+ bool isdefault;
+ AttStatsSlot mcvslot;
+
+ /* Get estimated number of distinct values */
+ otherdistinct = 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 -= mcvslot.nnumbers;
+ free_attstatsslot(&mcvslot);
+ }
+
+ /* If result doesn't seem sane, leave eq_selec at 0 */
+ if (otherdistinct > 1)
+ eq_selec = 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 = (double) (i - 1) + binfrac;
histfrac /= (double) (sslot.nvalues - 1);
+
+ /*
+ * At this point, histfrac is an estimate of the fraction of
+ * the population represented by the histogram that satisfies
+ * "x <= 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 ">=", or the bin to the right
+ * if probing with "<=" 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 <= 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 <= leftmost" to
+ * be estimated as eq_selec not zero. So, if we're dealing
+ * with the first bin (i==1), rescale to make that true while
+ * adjusting the rest of that bin linearly.
+ */
+ if (i == 1)
+ histfrac += eq_selec * (1.0 - binfrac);
+
+ /*
+ * "x <= constval" is good if we want an estimate for "<=" or
+ * ">", but if we are estimating for "<" or ">=", we now need
+ * to decrease the estimate by eq_selec.
+ */
+ if (isgt == iseq)
+ histfrac -= eq_selec;
}
/*
- * Now histfrac = fraction of histogram entries below the
- * constant.
- *
- * Account for "<" vs ">"
+ * Now the estimate is finished for "<" and "<=" cases. If we are
+ * estimating for ">" or ">=", flip it.
*/
hist_selec = isgt ? (1.0 - histfrac) : histfrac;
@@ -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 = 0.0001;
- else if (hist_selec > 0.9999)
- hist_selec = 0.9999;
+ double cutoff = 0.01 / (double) (sslot.nvalues - 1);
+
+ if (hist_selec < cutoff)
+ hist_selec = cutoff;
+ else if (hist_selec > 1.0 - cutoff)
+ hist_selec = 1.0 - cutoff;
}
}
@@ -970,10 +1076,11 @@ ineq_histogram_selectivity(PlannerInfo *root,
}
/*
- * scalarltsel - Selectivity of "<" (also "<=") 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 = (PlannerInfo *) PG_GETARG_POINTER(0);
Oid operator = PG_GETARG_OID(1);
@@ -984,7 +1091,6 @@ scalarltsel(PG_FUNCTION_ARGS)
bool varonleft;
Datum constval;
Oid consttype;
- bool isgt;
double selec;
/*
@@ -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 = false;
- }
- else
- {
- /* we have other < var, commute to make var > other */
operator = get_commutator(operator);
if (!operator)
{
@@ -1034,10 +1134,12 @@ scalarltsel(PG_FUNCTION_ARGS)
ReleaseVariableStats(vardata);
PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
}
- isgt = true;
+ isgt = !isgt;
}
- selec = scalarineqsel(root, operator, isgt, &vardata, constval, consttype);
+ /* The rest of the work is done by scalarineqsel(). */
+ selec = scalarineqsel(root, operator, isgt, iseq,
+ &vardata, constval, consttype);
ReleaseVariableStats(vardata);
@@ -1045,78 +1147,39 @@ scalarltsel(PG_FUNCTION_ARGS)
}
/*
- * scalargtsel - Selectivity of ">" (also ">=") for integers.
+ * scalarltsel - Selectivity of "<" for scalars.
*/
Datum
-scalargtsel(PG_FUNCTION_ARGS)
+scalarltsel(PG_FUNCTION_ARGS)
{
- PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
- Oid operator = PG_GETARG_OID(1);
- List *args = (List *) PG_GETARG_POINTER(2);
- int varRelid = 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 = ((Const *) other)->constvalue;
- consttype = ((Const *) other)->consttype;
-
- /*
- * Force the var to be on the left to simplify logic in scalarineqsel.
- */
- if (varonleft)
- {
- /* we have var > other */
- isgt = true;
- }
- else
- {
- /* we have other > var, commute to make var < other */
- operator = get_commutator(operator);
- if (!operator)
- {
- /* Use default selectivity (should we raise an error instead?) */
- ReleaseVariableStats(vardata);
- PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
- }
- isgt = false;
- }
+ return scalarineqsel_wrapper(fcinfo, false, false);
+}
- selec = scalarineqsel(root, operator, isgt, &vardata, constval, consttype);
+/*
+ * scalarlesel - Selectivity of "<=" for scalars.
+ */
+Datum
+scalarlesel(PG_FUNCTION_ARGS)
+{
+ return scalarineqsel_wrapper(fcinfo, false, true);
+}
- ReleaseVariableStats(vardata);
+/*
+ * scalargtsel - Selectivity of ">" for scalars.
+ */
+Datum
+scalargtsel(PG_FUNCTION_ARGS)
+{
+ return scalarineqsel_wrapper(fcinfo, true, false);
+}
- PG_RETURN_FLOAT8((float8) selec);
+/*
+ * scalargesel - Selectivity of ">=" for scalars.
+ */
+Datum
+scalargesel(PG_FUNCTION_ARGS)
+{
+ return scalarineqsel_wrapper(fcinfo, true, true);
}
/*
@@ -2721,7 +2784,7 @@ neqjoinsel(PG_FUNCTION_ARGS)
}
/*
- * scalarltjoinsel - Join selectivity of "<" and "<=" for scalars
+ * scalarltjoinsel - Join selectivity of "<" for scalars
*/
Datum
scalarltjoinsel(PG_FUNCTION_ARGS)
@@ -2730,7 +2793,16 @@ scalarltjoinsel(PG_FUNCTION_ARGS)
}
/*
- * scalargtjoinsel - Join selectivity of ">" and ">=" for scalars
+ * scalarlejoinsel - Join selectivity of "<=" 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)
}
/*
+ * scalargejoinsel - Join selectivity of ">=" 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 <= the right-side maximum value. But only believe
* non-default estimates, else stick with our 1.0.
*/
- selec = scalarineqsel(root, leop, isgt, &leftvar,
+ selec = scalarineqsel(root, leop, isgt, true, &leftvar,
rightmax, op_righttype);
if (selec != DEFAULT_INEQ_SEL)
*leftend = selec;
/* And similarly for the right variable. */
- selec = scalarineqsel(root, revleop, isgt, &rightvar,
+ selec = scalarineqsel(root, revleop, isgt, true, &rightvar,
leftmax, op_lefttype);
if (selec != DEFAULT_INEQ_SEL)
*rightend = 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 = scalarineqsel(root, ltop, isgt, &leftvar,
+ selec = scalarineqsel(root, ltop, isgt, false, &leftvar,
rightmin, op_righttype);
if (selec != DEFAULT_INEQ_SEL)
*leftstart = selec;
/* And similarly for the right variable. */
- selec = scalarineqsel(root, revltop, isgt, &rightvar,
+ selec = scalarineqsel(root, revltop, isgt, false, &rightvar,
leftmin, op_lefttype);
if (selec != DEFAULT_INEQ_SEL)
*rightstart = selec;
@@ -4012,8 +4093,8 @@ convert_numeric_to_scalar(Datum value, Oid typid)
}
/*
- * 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:
/*
- * 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)
}
/*
- * 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, VariableStatData *vardata,
elog(ERROR, "no >= operator for opfamily %u", opfamily);
fmgr_info(get_opcode(cmpopr), &opproc);
- prefixsel = ineq_histogram_selectivity(root, vardata, &opproc, true,
+ prefixsel = ineq_histogram_selectivity(root, vardata,
+ &opproc, true, true,
prefixcon->constvalue,
prefixcon->consttype);
@@ -5791,7 +5873,8 @@ prefix_selectivity(PlannerInfo *root, VariableStatData *vardata,
{
Selectivity topsel;
- topsel = ineq_histogram_selectivity(root, vardata, &opproc, false,
+ topsel = ineq_histogram_selectivity(root, vardata,
+ &opproc, false, false,
greaterstrcon->constvalue,
greaterstrcon->consttype);
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
