/*------------------------------------------------------------------------- * * selfuncs . c * Selectivity functions and index cost estimation functions for * standard operators and index access methods . * * Selectivity routines are registered in the pg_operator catalog * in the " oprrest " and " oprjoin " attributes . * * Index cost functions are located via the index AM ' s API struct , * which is obtained from the handler function registered in pg_am . * * Portions Copyright ( c ) 1996 - 2025 , PostgreSQL Global Development Group * Portions Copyright ( c ) 1994 , Regents of the University of California * * * IDENTIFICATION * src / backend / utils / adt / selfuncs . c * * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - /*---------- * Operator selectivity estimation functions are called to estimate the * selectivity of WHERE clauses whose top - level operator is their operator . * We divide the problem into two cases : * Restriction clause estimation : the clause involves vars of just * one relation . * Join clause estimation : the clause involves vars of multiple rels . * Join selectivity estimation is far more difficult and usually less accurate * than restriction estimation . * * When dealing with the inner scan of a nestloop join , we consider the * join ' s joinclauses as restriction clauses for the inner relation , and * treat vars of the outer relation as parameters ( a / k / a constants of unknown * values ) . So , restriction estimators need to be able to accept an argument * telling which relation is to be treated as the variable . * * The call convention for a restriction estimator ( oprrest function ) is * * Selectivity oprrest ( PlannerInfo * root , * Oid operator , * List * args , * int varRelid ) ; * * root : general information about the query ( rtable and RelOptInfo lists * are particularly important for the estimator ) . * operator : OID of the specific operator in question . * args : argument list from the operator clause . * varRelid : if not zero , the relid ( rtable index ) of the relation to * be treated as the variable relation . May be zero if the args list * is known to contain vars of only one relation . * * This is represented at the SQL level ( in pg_proc ) as * * float8 oprrest ( internal , oid , internal , int4 ) ; * * The result is a selectivity , that is , a fraction ( 0 to 1 ) of the rows * of the relation that are expected to produce a TRUE result for the * given operator . * * The call convention for a join estimator ( oprjoin function ) is similar * except that varRelid is not needed , and instead join information is * supplied : * * Selectivity oprjoin ( PlannerInfo * root , * Oid operator , * List * args , * JoinType jointype , * SpecialJoinInfo * sjinfo ) ; * * float8 oprjoin ( internal , oid , internal , int2 , internal ) ; * * ( Before Postgres 8 . 4 , join estimators had only the first four of these * parameters . That signature is still allowed , but deprecated . ) The * relationship between jointype and sjinfo is explained in the comments for * clause_selectivity ( ) - - - the short version is that jointype is usually * best ignored in favor of examining sjinfo . * * Join selectivity for regular inner and outer joins is defined as the * fraction ( 0 to 1 ) of the cross product of the relations that is expected * to produce a TRUE result for the given operator . For both semi and anti * joins , however , the selectivity is defined as the fraction of the left - hand * side relation ' s rows that are expected to have a match ( ie , at least one * row with a TRUE result ) in the right - hand side . * * For both oprrest and oprjoin functions , the operator ' s input collation OID * ( if any ) is passed using the standard fmgr mechanism , so that the estimator * function can fetch it with PG_GET_COLLATION ( ) . Note , however , that all * statistics in pg_statistic are currently built using the relevant column ' s * collation . * - - - - - - - - - - #include "postgres.h" #include <ctype.h>#include <math.h>#include "access/brin.h" #include "access/brin_page.h" #include "access/gin.h" #include "access/table.h" #include "access/tableam.h" #include "access/visibilitymap.h" #include "catalog/pg_am.h" #include "catalog/pg_collation.h" #include "catalog/pg_operator.h" #include "catalog/pg_statistic.h" #include "catalog/pg_statistic_ext.h" #include "executor/nodeAgg.h" #include "miscadmin.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" #include "optimizer/optimizer.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/plancat.h" #include "parser/parse_clause.h" #include "parser/parse_relation.h" #include "parser/parsetree.h" #include "rewrite/rewriteManip.h" #include "statistics/statistics.h" #include "storage/bufmgr.h" #include "utils/acl.h" #include "utils/array.h" #include "utils/builtins.h" #include "utils/date.h" #include "utils/datum.h" #include "utils/fmgroids.h" #include "utils/index_selfuncs.h" #include "utils/lsyscache.h" #include "utils/memutils.h" #include "utils/pg_locale.h" #include "utils/rel.h" #include "utils/selfuncs.h" #include "utils/snapmgr.h" #include "utils/spccache.h" #include "utils/syscache.h" #include "utils/timestamp.h" #include "utils/typcache.h" #define DEFAULT_PAGE_CPU_MULTIPLIER 50 .0 /* Hooks for plugins to get control when we ask for stats */ static double eqsel_internal(PG_FUNCTION_ARGS, bool negate);static double eqjoinsel_inner(Oid opfuncoid, Oid collation,double nd1, double nd2,bool isdefault1, bool isdefault2,bool have_mcvs1, bool have_mcvs2);static double eqjoinsel_semi(Oid opfuncoid, Oid collation,double nd1, double nd2,bool isdefault1, bool isdefault2,bool have_mcvs1, bool have_mcvs2,static bool estimate_multivariate_ndistinct(PlannerInfo *root,double *ndistinct);static bool convert_to_scalar(Datum value, Oid valuetypid, Oid collid,double *scaledvalue,double *scaledlobound, double *scaledhibound);static double convert_numeric_to_scalar(Datum value, Oid typid, bool *failure);static void convert_string_to_scalar(char *value,double *scaledvalue,char *lobound,double *scaledlobound,char *hibound,double *scaledhibound);static void convert_bytea_to_scalar(Datum value,double *scaledvalue,double *scaledlobound,double *scaledhibound);static double convert_one_string_to_scalar(char *value,int rangelo, int rangehi);static double convert_one_bytea_to_scalar(unsigned char *value, int valuelen,int rangelo, int rangehi);static char *convert_string_datum(Datum value, Oid typid, Oid collid,bool *failure);static double convert_timevalue_to_scalar(Datum value, Oid typid,bool *failure);static Node *strip_all_phvs_deep(PlannerInfo *root, Node *node);static bool contain_placeholder_walker(Node *node, void *context);static Node *strip_all_phvs_mutator(Node *node, void *context);static void examine_simple_variable(PlannerInfo *root, Var *var,static void examine_indexcol_variable(PlannerInfo *root, IndexOptInfo *index,int indexcol, VariableStatData *vardata);static bool get_variable_range(PlannerInfo *root, VariableStatData *vardata,static void get_stats_slot_range(AttStatsSlot *sslot,bool typByVal,bool *p_have_data);static bool get_actual_variable_range(PlannerInfo *root,static bool get_actual_variable_endpoint(Relation heapRel,bool typByVal,static RelOptInfo *find_join_input_rel(PlannerInfo *root, Relids relids);static double btcost_correlation(IndexOptInfo *index,/* * eqsel - Selectivity of " = " for any data types . * * Note : this routine is also used to estimate selectivity for some * operators that are not " = " but have comparable selectivity behavior , * such as " ~ = " ( geometric approximate - match ) . Even for " = " , we must * keep in mind that the left and right datatypes may differ . false ));/* * Common code for eqsel ( ) and neqsel ( ) static double bool negate)0 );operator = PG_GETARG_OID(1 );2 );int varRelid = PG_GETARG_INT32(3 );bool varonleft;double selec;/* * When asked about < > , we do the estimation using the corresponding = * operator , then convert to < > via " 1 . 0 - eq_selectivity - nullfrac " . if (negate)operator = get_negator(operator );if (!OidIsValid(operator ))/* Use default selectivity (should we raise an error instead?) */ return 1 .0 - DEFAULT_EQ_SEL;/* * If expression is not variable = something or something = variable , then * punt and return a default estimate . if (!get_restriction_variable(root, args, varRelid,return negate ? (1 .0 - DEFAULT_EQ_SEL) : DEFAULT_EQ_SEL;/* * We can do a lot better if the something is a constant . ( Note : the * Const might result from estimation rather than being a simple constant * in the query . ) if (IsA(other, Const ))operator , collation,Const *) other)->constvalue,Const *) other)->constisnull,else operator , collation, other,return selec;/* * var_eq_const - - - eqsel for var = const case * * This is exported so that some other estimation functions can use it . double bool constisnull,bool varonleft, bool negate)double selec;double nullfrac = 0 .0 ;bool isdefault;/* * If the constant is NULL , assume operator is strict and return zero , ie , * operator will never return TRUE . ( It ' s zero even for a negator op . ) if (constisnull)return 0 .0 ;/* * Grab the nullfrac for use below . Note we allow use of nullfrac * regardless of security check . if (HeapTupleIsValid(vardata->statsTuple))/* * If we matched the var to a unique index , DISTINCT or GROUP - BY clause , * assume there is exactly one match regardless of anything else . ( This * is slightly bogus , since the index or clause ' s equality operator might * be different from ours , but it ' s much more likely to be right than * ignoring the information . ) if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1 .0 )1 .0 / vardata->rel->tuples;else if (HeapTupleIsValid(vardata->statsTuple) &&bool match = false ;int i;/* * Is the constant " = " to any of the column ' s most common values ? * ( Although the given operator may not really be " = " , we will assume * that seeing whether it returns TRUE is an appropriate test . If you * don ' t like this , maybe you shouldn ' t be using eqsel for your * operator . . . ) if (get_attstatsslot(&sslot, vardata->statsTuple,2 );/* * Save a few cycles by setting up the fcinfo struct just once . * Using FunctionCallInvoke directly also avoids failure if the * eqproc returns NULL , though really equality functions should * never do that . 2 , collation,0 ].isnull = false ;1 ].isnull = false ;/* be careful to apply operator right way 'round */ if (varonleft)1 ].value = constval;else 0 ].value = constval;for (i = 0 ; i < sslot.nvalues; i++)if (varonleft)0 ].value = sslot.values[i];else 1 ].value = sslot.values[i];false ;if (!fcinfo->isnull && DatumGetBool(fresult))true ;break ;else /* no most-common-value info available */ 0 ; /* keep compiler quiet */ if (match)/* * Constant is " = " to this common value . We know selectivity * exactly ( or as exactly as ANALYZE could calculate it , anyway ) . else /* * Comparison is against a constant that is neither NULL nor any * of the common values . Its selectivity cannot be more than * this : double sumcommon = 0 .0 ;double otherdistinct;for (i = 0 ; i < sslot.nnumbers; i++)1 .0 - sumcommon - nullfrac;/* * and in fact it ' s probably a good deal less . We approximate that * all the not - common values share this remaining fraction * equally , so we divide by the number of other distinct values . if (otherdistinct > 1 )/* * Another cross - check : selectivity shouldn ' t be estimated as more * than the least common " most common value " . if (sslot.nnumbers > 0 && selec > sslot.numbers[sslot.nnumbers - 1 ])1 ];else /* * No ANALYZE stats available , so make a guess using estimated number * of distinct values and assuming they are equally common . ( The guess * is unlikely to be very good , but we do know a few special cases . ) 1 .0 / get_variable_numdistinct(vardata, &isdefault);/* now adjust if we wanted <> rather than = */ if (negate)1 .0 - selec - nullfrac;/* result should be in range, but make sure... */ return selec;/* * var_eq_non_const - - - eqsel for var = something - other - than - const case * * This is exported so that some other estimation functions can use it . double bool varonleft, bool negate)double selec;double nullfrac = 0 .0 ;bool isdefault;/* * Grab the nullfrac for use below . if (HeapTupleIsValid(vardata->statsTuple))/* * If we matched the var to a unique index , DISTINCT or GROUP - BY clause , * assume there is exactly one match regardless of anything else . ( This * is slightly bogus , since the index or clause ' s equality operator might * be different from ours , but it ' s much more likely to be right than * ignoring the information . ) if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1 .0 )1 .0 / vardata->rel->tuples;else if (HeapTupleIsValid(vardata->statsTuple))double ndistinct;/* * Search is for a value that we do not know a priori , but we will * assume it is not NULL . Estimate the selectivity as non - null * fraction divided by number of distinct values , so that we get a * result averaged over all possible values whether common or * uncommon . ( Essentially , we are assuming that the not - yet - known * comparison value is equally likely to be any of the possible * values , regardless of their frequency in the table . Is that a good * idea ? ) 1 .0 - nullfrac;if (ndistinct > 1 )/* * Cross - check : selectivity should never be estimated as more than the * most common value ' s . if (get_attstatsslot(&sslot, vardata->statsTuple,if (sslot.nnumbers > 0 && selec > sslot.numbers[0 ])0 ];else /* * No ANALYZE stats available , so make a guess using estimated number * of distinct values and assuming they are equally common . ( The guess * is unlikely to be very good , but we do know a few special cases . ) 1 .0 / get_variable_numdistinct(vardata, &isdefault);/* now adjust if we wanted <> rather than = */ if (negate)1 .0 - selec - nullfrac;/* result should be in range, but make sure... */ return selec;/* * neqsel - Selectivity of " ! = " for any data types . * * This routine is also used for some operators that are not " ! = " * but have comparable selectivity behavior . See above comments * for eqsel ( ) . true ));/* * scalarineqsel - Selectivity of " < " , " < = " , " > " , " > = " for scalars . * * 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 computed 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 an approximate estimate based on assuming that the constant * value falls in the middle of the bin identified by binary search . static double operator , bool isgt, bool iseq,double mcv_selec,double selec;if (!HeapTupleIsValid(vardata->statsTuple))/* * No stats are available . Typically this means we have to fall back * on the default estimate ; but if the variable is CTID then we can * make an estimate based on comparing the constant to the table size . if (vardata->var && IsA(vardata->var, Var) &&double block;double density;/* * If the relation ' s empty , we ' re going to include all of it . * ( This is mostly to avoid divide - by - zero below . ) if (vardata->rel->pages == 0 )return 1 .0 ;/* * Determine the average number of tuples per page ( density ) . * * Since the last page will , on average , be only half full , we can * estimate it to have half as many tuples as earlier pages . So * give it half the weight of a regular page . 0 .5 );/* If target is the last page, use half the density. */ if (block >= vardata->rel->pages - 1 )0 .5 ;/* * Using the average tuples per page , calculate how far into the * page the itemptr is likely to be and adjust block accordingly , * by adding that fraction of a whole block ( but never more than a * whole block , no matter how high the itemptr ' s offset is ) . Here * we are ignoring the possibility of dead - tuple line pointers , * which is fairly bogus , but we lack the info to do better . if (density > 0 .0 )1 .0 );/* * Convert relative block number to selectivity . Again , the last * page has only half weight . 0 .5 );/* * The calculation so far gave us a selectivity for the " < = " case . * We ' ll have one fewer tuple for " < " and one additional tuple for * " > = " , the latter of which we ' ll reverse the selectivity for * below , so we can simply subtract one tuple for both cases . The * cases that need this adjustment can be identified by iseq being * equal to isgt . if (iseq == isgt && vardata->rel->tuples >= 1 .0 )1 .0 / vardata->rel->tuples);/* Finally, reverse the selectivity for the ">", ">=" cases. */ if (isgt)1 .0 - selec;return selec;/* no stats available, so default result */ return DEFAULT_INEQ_SEL;operator ), &opproc);/* * If we have most - common - values info , add up the fractions of the MCV * entries that satisfy MCV OP CONST . These fractions contribute directly * to the result selectivity . Also add up the total fraction represented * by MCV entries . true ,/* * If there is a histogram , determine which bin the constant falls in , and * compute the resulting contribution to selectivity . operator , &opproc, isgt, iseq,/* * Now merge the results from the MCV and histogram calculations , * realizing that the histogram covers only the non - null values that are * not listed in MCV . 1 .0 - stats->stanullfrac - sumcommon;if (hist_selec >= 0 .0 )else /* * If no histogram but there are values not accounted for by MCV , * arbitrarily assume half of them will match . 0 .5 ;/* result should be in range, but make sure... */ return selec;/* * mcv_selectivity - Examine the MCV list for selectivity estimates * * Determine the fraction of the variable ' s MCV population that satisfies * the predicate ( VAR OP CONST ) , or ( CONST OP VAR ) if ! varonleft . Also * compute the fraction of the total column population represented by the MCV * list . This code will work for any boolean - returning predicate operator . * * The function result is the MCV selectivity , and the fraction of the * total population is returned into * sumcommonp . Zeroes are returned * if there is no MCV list . double bool varonleft,double *sumcommonp)double mcv_selec,int i;0 .0 ;0 .0 ;if (HeapTupleIsValid(vardata->statsTuple) &&2 );/* * We invoke the opproc " by hand " so that we won ' t fail on NULL * results . Such cases won ' t arise for normal comparison functions , * but generic_restriction_selectivity could perhaps be used with * operators that can return NULL . A small side benefit is to not * need to re - initialize the fcinfo struct from scratch each time . 2 , collation,0 ].isnull = false ;1 ].isnull = false ;/* be careful to apply operator right way 'round */ if (varonleft)1 ].value = constval;else 0 ].value = constval;for (i = 0 ; i < sslot.nvalues; i++)if (varonleft)0 ].value = sslot.values[i];else 1 ].value = sslot.values[i];false ;if (!fcinfo->isnull && DatumGetBool(fresult))return mcv_selec;/* * histogram_selectivity - Examine the histogram for selectivity estimates * * Determine the fraction of the variable ' s histogram entries that satisfy * the predicate ( VAR OP CONST ) , or ( CONST OP VAR ) if ! varonleft . * * This code will work for any boolean - returning predicate operator , whether * or not it has anything to do with the histogram sort operator . We are * essentially using the histogram just as a representative sample . However , * small histograms are unlikely to be all that representative , so the caller * should be prepared to fall back on some other estimation approach when the * histogram is missing or very small . It may also be prudent to combine this * approach with another one when the histogram is small . * * If the actual histogram size is not at least min_hist_size , we won ' t bother * to do the calculation at all . Also , if the n_skip parameter is > 0 , we * ignore the first and last n_skip histogram elements , on the grounds that * they are outliers and hence not very representative . Typical values for * these parameters are 10 and 1 . * * The function result is the selectivity , or - 1 if there is no histogram * or it ' s smaller than min_hist_size . * * The output parameter * hist_size receives the actual histogram size , * or zero if no histogram . Callers may use this number to decide how * much faith to put in the function result . * * Note that the result disregards both the most - common - values ( if any ) and * null entries . The caller is expected to combine this result with * statistics for those portions of the column population . It may also be * prudent to clamp the result range , ie , disbelieve exact 0 or 1 outputs . double bool varonleft,int min_hist_size, int n_skip,int *hist_size)double result;/* check sanity of parameters */ 0 );2 * n_skip);if (HeapTupleIsValid(vardata->statsTuple) &&if (sslot.nvalues >= min_hist_size)2 );int nmatch = 0 ;int i;/* * We invoke the opproc " by hand " so that we won ' t fail on NULL * results . Such cases won ' t arise for normal comparison * functions , but generic_restriction_selectivity could perhaps be * used with operators that can return NULL . A small side benefit * is to not need to re - initialize the fcinfo struct from scratch * each time . 2 , collation,0 ].isnull = false ;1 ].isnull = false ;/* be careful to apply operator right way 'round */ if (varonleft)1 ].value = constval;else 0 ].value = constval;for (i = n_skip; i < sslot.nvalues - n_skip; i++)if (varonleft)0 ].value = sslot.values[i];else 1 ].value = sslot.values[i];false ;if (!fcinfo->isnull && DatumGetBool(fresult))double ) nmatch) / ((double ) (sslot.nvalues - 2 * n_skip));else 1 ;else 0 ;1 ;return result;/* * generic_restriction_selectivity - Selectivity for almost anything * * This function estimates selectivity for operators that we don ' t have any * special knowledge about , but are on data types that we collect standard * MCV and / or histogram statistics for . ( Additional assumptions are that * the operator is strict and immutable , or at least stable . ) * * If we have " VAR OP CONST " or " CONST OP VAR " , selectivity is estimated by * applying the operator to each element of the column ' s MCV and / or histogram * stats , and merging the results using the assumption that the histogram is * a reasonable random sample of the column ' s non - MCV population . Note that * if the operator ' s semantics are related to the histogram ordering , this * might not be such a great assumption ; other functions such as * scalarineqsel ( ) are probably a better match in such cases . * * Otherwise , fall back to the default selectivity provided by the caller . double int varRelid,double default_selectivity)double selec;bool varonleft;/* * If expression is not variable OP something or something OP variable , * then punt and return the default estimate . if (!get_restriction_variable(root, args, varRelid,return default_selectivity;/* * If the something is a NULL constant , assume operator is strict and * return zero , ie , operator will never return TRUE . if (IsA(other, Const ) &&Const *) other)->constisnull)return 0 .0 ;if (IsA(other, Const ))/* Variable is being compared to a known non-null constant */ Const *) other)->constvalue;double mcvsum;double mcvsel;double nullfrac;int hist_size;/* * Calculate the selectivity for the column ' s most common values . /* * If the histogram is large enough , see what fraction of it matches * the query , and assume that ' s representative of the non - MCV * population . Otherwise use the default selectivity for the non - MCV * population . 10 , 1 , &hist_size);if (selec < 0 )/* Nope, fall back on default */ else if (hist_size < 100 )/* * For histogram sizes from 10 to 100 , we combine the histogram * and default selectivities , putting increasingly more trust in * the histogram for larger sizes . double hist_weight = hist_size / 100 .0 ;1 .0 - hist_weight);/* In any case, don't believe extremely small or large estimates. */ if (selec < 0 .0001 )0 .0001 ;else if (selec > 0 .9999 )0 .9999 ;/* Don't forget to account for nulls. */ if (HeapTupleIsValid(vardata.statsTuple))else 0 .0 ;/* * Now merge the results from the MCV and histogram calculations , * realizing that the histogram covers only the non - null values that * are not listed in MCV . 1 .0 - nullfrac - mcvsum;else /* Comparison value is not constant, so we can't do anything */ /* result should be in range, but make sure... */ return selec;/* * ineq_histogram_selectivity - Examine the histogram for scalarineqsel * * Determine the fraction of the variable ' s histogram population that * satisfies the inequality condition , ie , VAR < ( or < = , > , > = ) CONST . * The isgt and iseq flags distinguish which of the four cases apply . * * While opproc could be looked up from the operator OID , common callers * also need to call it separately , so we make the caller pass both . * * Returns - 1 if there is no histogram ( valid results will always be > = 0 ) . * * Note that the result disregards both the most - common - values ( if any ) and * null entries . The caller is expected to combine this result with * statistics for those portions of the column population . * * This is exported so that some other estimation functions can use it . double bool isgt, bool iseq,double hist_selec;1 .0 ;/* * Someday , ANALYZE might store more than one histogram per rel / att , * corresponding to more than one possible sort ordering defined for the * column type . Right now , we know there is only one , so just grab it and * see if it matches the query . * * Note that we can ' t use opoid as search argument ; the staop appearing in * pg_statistic will be for the relevant ' < ' operator , but what we have * might be some other inequality operator such as ' > = ' . ( Even if opoid * is a ' < ' operator , it could be cross - type . ) Hence we must use * comparison_ops_are_compatible ( ) to see if the operators match . if (HeapTupleIsValid(vardata->statsTuple) &&if (sslot.nvalues > 1 &&/* * 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 ) . * * 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 * or max as found by get_actual_variable_range ( ) . This * ameliorates misestimates when the min or max is moving as a * result of changes since the last ANALYZE . Note that this could * result in effectively including MCVs into the histogram that * weren ' t there before , but we don ' t try to correct for that . double histfrac;int lobound = 0 ; /* first possible slot to search */ int hibound = sslot.nvalues; /* last+1 slot to search */ bool have_end = false ;/* * If there are only two histogram entries , we ' ll want up - to - date * values for both . ( If there are more than two , we need at most * one of them to be updated , so we deal with that within the * loop . ) if (sslot.nvalues == 2 )0 ],1 ]);while (lobound < hibound)int probe = (lobound + hibound) / 2 ;bool ltcmp;/* * If we find ourselves about to compare to the first or last * histogram entry , first try to replace it with the actual * current min or max ( unless we already did so above ) . if (probe == 0 && sslot.nvalues > 2 )0 ],else if (probe == sslot.nvalues - 1 && sslot.nvalues > 2 )if (isgt)if (ltcmp)1 ;else if (lobound <= 0 )/* * 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 ) . 0 .0 ;else if (lobound >= sslot.nvalues)/* * Inverse case : constant is above upper histogram boundary . 1 .0 ;else /* We have values[i-1] <= constant <= values[i]. */ int i = lobound;double eq_selec = 0 ;double val,double binfrac;/* * 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;/* Get estimated number of distinct values */ /* Subtract off the number of known MCVs */ if (get_attstatsslot(&mcvslot, vardata->statsTuple,/* If result doesn't seem sane, leave eq_selec at 0 */ if (otherdistinct > 1 )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 . if (convert_to_scalar(constval, consttype, collation,1 ], sslot.values[i],if (high <= low)/* cope if bin boundaries appear identical */ 0 .5 ;else if (val <= low)0 .0 ;else if (val >= high)1 .0 ;else /* * Watch out for the possibility that we got a NaN or * Infinity from the division . This can happen * despite the previous checks , if for example " low " * is - Infinity . if (isnan(binfrac) ||0 .0 || binfrac > 1 .0 )0 .5 ;else /* * Ideally we ' d produce an error here , on the grounds that * the given operator shouldn ' t have scalarXXsel * registered as its selectivity func unless we can deal * with its operand types . But currently , all manner of * stuff is invoking scalarXXsel , so give a default * estimate until that can be fixed . 0 .5 ;/* * Now , compute the overall selectivity across the values * represented by the histogram . We have i - 1 full bins and * binfrac partial bin below the constant . double ) (i - 1 ) + binfrac;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 )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)/* * Now the estimate is finished for " < " and " < = " cases . If we are * estimating for " > " or " > = " , flip it . 1 .0 - histfrac) : histfrac;/* * 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 , 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)else double cutoff = 0 .01 / (double ) (sslot.nvalues - 1 );if (hist_selec < cutoff)else if (hist_selec > 1 .0 - cutoff)1 .0 - cutoff;else if (sslot.nvalues > 1 )/* * If we get here , we have a histogram but it ' s not sorted the way * we want . Do a brute - force search to see how many of the * entries satisfy the comparison condition , and take that * fraction as our estimate . ( This is identical to the inner loop * of histogram_selectivity ; maybe share code ? ) 2 );int nmatch = 0 ;2 , collation,0 ].isnull = false ;1 ].isnull = false ;1 ].value = constval;for (int i = 0 ; i < sslot.nvalues; i++)0 ].value = sslot.values[i];false ;if (!fcinfo->isnull && DatumGetBool(fresult))double ) nmatch) / ((double ) sslot.nvalues);/* * As above , clamp to a hundredth of the histogram resolution . * This case is surely even less trustworthy than the normal one , * so we shouldn ' t believe exact 0 or 1 selectivity . ( Maybe the * clamp should be more restrictive in this case ? ) double cutoff = 0 .01 / (double ) (sslot.nvalues - 1 );if (hist_selec < cutoff)else if (hist_selec > 1 .0 - cutoff)1 .0 - cutoff;return hist_selec;/* * Common wrapper function for the selectivity estimators that simply * invoke scalarineqsel ( ) . static Datumbool isgt, bool iseq)0 );operator = PG_GETARG_OID(1 );2 );int varRelid = PG_GETARG_INT32(3 );bool varonleft;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,/* * Can ' t do anything useful if the something is not a constant , either . if (!IsA(other, Const ))/* * If the constant is NULL , assume operator is strict and return zero , ie , * operator will never return TRUE . if (((Const *) other)->constisnull)0 .0 );Const *) other)->constvalue;Const *) other)->consttype;/* * Force the var to be on the left to simplify logic in scalarineqsel . if (!varonleft)operator = get_commutator(operator );if (!operator )/* Use default selectivity (should we raise an error instead?) */ /* The rest of the work is done by scalarineqsel(). */ operator , isgt, iseq, collation,/* * scalarltsel - Selectivity of " < " for scalars . return scalarineqsel_wrapper(fcinfo, false , false );/* * scalarlesel - Selectivity of " < = " for scalars . return scalarineqsel_wrapper(fcinfo, false , true );/* * scalargtsel - Selectivity of " > " for scalars . return scalarineqsel_wrapper(fcinfo, true , false );/* * scalargesel - Selectivity of " > = " for scalars . return scalarineqsel_wrapper(fcinfo, true , true );/* * boolvarsel - Selectivity of Boolean variable . * * This can actually be called on any boolean - valued expression . If it * involves only Vars of the specified relation , and if there are statistics * about the Var or expression ( the latter is possible if it ' s indexed ) then * we ' ll produce a real estimate ; otherwise it ' s just a default . int varRelid)double selec;if (HeapTupleIsValid(vardata.statsTuple))/* * A boolean variable V is equivalent to the clause V = ' t ' , so we * compute the selectivity as if that is what we have . true ), false , true , false );else /* Otherwise, the default estimate is 0.5 */ 0 .5 ;return selec;/* * booltestsel - Selectivity of BooleanTest Node . int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)double selec;if (HeapTupleIsValid(vardata.statsTuple))double freq_null;if (get_attstatsslot(&sslot, vardata.statsTuple,0 )double freq_true;double freq_false;/* * Get first MCV frequency and derive frequency for true . if (DatumGetBool(sslot.values[0 ]))0 ];else 1 .0 - sslot.numbers[0 ] - freq_null;/* * Next derive frequency for false . Then use these as appropriate * to derive frequency for each case . 1 .0 - freq_true - freq_null;switch (booltesttype)case IS_UNKNOWN:/* select only NULL values */ break ;case IS_NOT_UNKNOWN:/* select non-NULL values */ 1 .0 - freq_null;break ;case IS_TRUE:/* select only TRUE values */ break ;case IS_NOT_TRUE:/* select non-TRUE values */ 1 .0 - freq_true;break ;case IS_FALSE:/* select only FALSE values */ break ;case IS_NOT_FALSE:/* select non-FALSE values */ 1 .0 - freq_false;break ;default :"unrecognized booltesttype: %d" ,int ) booltesttype);0 .0 ; /* Keep compiler quiet */ break ;else /* * No most - common - value info available . Still have null fraction * information , so use it for IS [ NOT ] UNKNOWN . Otherwise adjust * for null fraction and assume a 50 - 50 split of TRUE and FALSE . switch (booltesttype)case IS_UNKNOWN:/* select only NULL values */ break ;case IS_NOT_UNKNOWN:/* select non-NULL values */ 1 .0 - freq_null;break ;case IS_TRUE:case IS_FALSE:/* Assume we select half of the non-NULL values */ 1 .0 - freq_null) / 2 .0 ;break ;case IS_NOT_TRUE:case IS_NOT_FALSE:/* Assume we select NULLs plus half of the non-NULLs */ /* equiv. to freq_null + (1.0 - freq_null) / 2.0 */ 1 .0 ) / 2 .0 ;break ;default :"unrecognized booltesttype: %d" ,int ) booltesttype);0 .0 ; /* Keep compiler quiet */ break ;else /* * If we can ' t get variable statistics for the argument , perhaps * clause_selectivity can do something with it . We ignore the * possibility of a NULL value when using clause_selectivity , and just * assume the value is either TRUE or FALSE . switch (booltesttype)case IS_UNKNOWN:break ;case IS_NOT_UNKNOWN:break ;case IS_TRUE:case IS_NOT_FALSE:double ) clause_selectivity(root, arg,break ;case IS_FALSE:case IS_NOT_TRUE:1 .0 - (double ) clause_selectivity(root, arg,break ;default :"unrecognized booltesttype: %d" ,int ) booltesttype);0 .0 ; /* Keep compiler quiet */ break ;/* result should be in range, but make sure... */ return (Selectivity) selec;/* * nulltestsel - Selectivity of NullTest Node . int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)double selec;if (HeapTupleIsValid(vardata.statsTuple))double freq_null;switch (nulltesttype)case IS_NULL:/* * Use freq_null directly . break ;case IS_NOT_NULL:/* * Select not unknown ( not null ) values . Calculate from * freq_null . 1 .0 - freq_null;break ;default :"unrecognized nulltesttype: %d" ,int ) nulltesttype);return (Selectivity) 0 ; /* keep compiler quiet */ else if (vardata.var && IsA(vardata.var, Var) &&0 )/* * There are no stats for system columns , but we know they are never * NULL . 0 .0 : 1 .0 ;else /* * No ANALYZE stats available , so make a guess switch (nulltesttype)case IS_NULL:break ;case IS_NOT_NULL:break ;default :"unrecognized nulltesttype: %d" ,int ) nulltesttype);return (Selectivity) 0 ; /* keep compiler quiet */ /* result should be in range, but make sure... */ return (Selectivity) selec;/* * strip_array_coercion - strip binary - compatible relabeling from an array expr * * For array values , the parser normally generates ArrayCoerceExpr conversions , * but it seems possible that RelabelType might show up . Also , the planner * is not currently tense about collapsing stacked ArrayCoerceExpr nodes , * so we need to be ready to deal with more than one level . static Node *for (;;)if (node && IsA(node, ArrayCoerceExpr))/* * If the per - element expression is just a RelabelType on top of * CaseTestExpr , then we know it ' s a binary - compatible relabeling . if (IsA(acoerce->elemexpr, RelabelType) &&else break ;else if (node && IsA(node, RelabelType))/* We don't really expect this case, but may as well cope */ else break ;return node;/* * scalararraysel - Selectivity of ScalarArrayOpExpr Node . bool is_join_clause,int varRelid,operator = clause->opno;bool useOr = clause->useOr;bool isEquality = false ;bool isInequality = false ;/* First, deconstruct the expression */ 2 );/* aggressively reduce both sides to constants */ /* get nominal (after relabeling) element type of rightop */ if (!OidIsValid(nominal_element_type))return (Selectivity) 0 .5 ; /* probably shouldn't happen */ /* get nominal collation, too, for generating constants */ /* look through any binary-compatible relabeling of rightop */ /* * Detect whether the operator is the default equality or inequality * operator of the array element type . if (OidIsValid(typentry->eq_opr))if (operator == typentry->eq_opr)true ;else if (get_negator(operator ) == typentry->eq_opr)true ;/* * If it is equality or inequality , we might be able to estimate this as a * form of array containment ; for instance " const = ANY ( column ) " can be * treated as " ARRAY [ const ] < @ column " . scalararraysel_containment tries * that , and returns the selectivity estimate if successful , or - 1 if not . if ((isEquality || isInequality) && !is_join_clause)if (s1 >= 0 .0 )return s1;/* * Look up the underlying operator ' s selectivity estimator . Punt if it * hasn ' t got one . if (is_join_clause)operator );else operator );if (!oprsel)return (Selectivity) 0 .5 ;/* * In the array - containment check above , we must only believe that an * operator is equality or inequality if it is the default btree equality * operator ( or its negator ) for the element type , since those are the * operators that array containment will use . But in what follows , we can * be a little laxer , and also believe that any operators using eqsel ( ) or * neqsel ( ) as selectivity estimator act like equality or inequality . if (oprsel == F_EQSEL || oprsel == F_EQJOINSEL)true ;else if (oprsel == F_NEQSEL || oprsel == F_NEQJOINSEL)true ;/* * We consider three cases : * * 1 . rightop is an Array constant : deconstruct the array , apply the * operator ' s selectivity function for each array element , and merge the * results in the same way that clausesel . c does for AND / OR combinations . * * 2 . rightop is an ARRAY [ ] construct : apply the operator ' s selectivity * function for each element of the ARRAY [ ] construct , and merge . * * 3 . otherwise , make a guess . . . if (rightop && IsA(rightop, Const ))Const *) rightop)->constvalue;bool arrayisnull = ((Const *) rightop)->constisnull;bool elmbyval;char elmalign;int num_elems;bool *elem_nulls;int i;if (arrayisnull) /* qual can't succeed if null array */ return (Selectivity) 0 .0 ;/* * For generic operators , we assume the probability of success is * independent for each array element . But for " = ANY " or " < > ALL " , * if the array elements are distinct ( which ' d typically be the case ) * then the probabilities are disjoint , and we should just sum them . * * If we were being really tense we would try to confirm that the * elements are all distinct , but that would be expensive and it * doesn ' t seem to be worth the cycles ; it would amount to penalizing * well - written queries in favor of poorly - written ones . However , we * do protect ourselves a little bit by checking whether the * disjointness assumption leads to an impossible ( out of range ) * probability ; if so , we fall back to the normal calculation . 0 .0 : 1 .0 );for (i = 0 ; i < num_elems; i++)1 ,if (is_join_clause)operator ),else operator ),if (useOr)if (isEquality)else if (isInequality)1 .0 ;/* accept disjoint-probability estimate if in range */ if ((useOr ? isEquality : isInequality) &&0 .0 && s1disjoint <= 1 .0 )else if (rightop && IsA(rightop, ArrayExpr) &&bool elmbyval;/* * We use the assumption of disjoint probabilities here too , although * the odds of equal array elements are rather higher if the elements * are not all constants ( which they won ' t be , else constant folding * would have reduced the ArrayExpr to a Const ) . In this path it ' s * critical to have the sanity check on the s1disjoint estimate . 0 .0 : 1 .0 );/* * Theoretically , if elem isn ' t of nominal_element_type we should * insert a RelabelType , but it seems unlikely that any operator * estimation function would really care . . . if (is_join_clause)operator ),else operator ),if (useOr)if (isEquality)else if (isInequality)1 .0 ;/* accept disjoint-probability estimate if in range */ if ((useOr ? isEquality : isInequality) &&0 .0 && s1disjoint <= 1 .0 )else int i;/* * We need a dummy rightop to pass to the operator selectivity * routine . It can be pretty much anything that doesn ' t look like a * constant ; CaseTestExpr is a convenient choice . typeId = nominal_element_type;1 ;if (is_join_clause)operator ),else operator ),0 .0 : 1 .0 ;/* * Arbitrarily assume 10 elements in the eventual array value ( see * also estimate_array_length ) . We don ' t risk an assumption of * disjoint probabilities here . for (i = 0 ; i < 10 ; i++)if (useOr)else /* result should be in range, but make sure... */ return s1;/* * Estimate number of elements in the array yielded by an expression . * * Note : the result is integral , but we use " double " to avoid overflow * concerns . Most callers will use it in double - type expressions anyway . * * Note : in some code paths root can be passed as NULL , resulting in * slightly worse estimates . double /* look through any binary-compatible relabeling of arrayexpr */ if (arrayexpr && IsA(arrayexpr, Const ))Const *) arrayexpr)->constvalue;bool arrayisnull = ((Const *) arrayexpr)->constisnull;if (arrayisnull)return 0 ;return ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));else if (arrayexpr && IsA(arrayexpr, ArrayExpr) &&return list_length(((ArrayExpr *) arrayexpr)->elements);else if (arrayexpr && root)/* See if we can find any statistics about it */ double nelem = 0 ;/* * Skip calling examine_variable for Var with varno 0 , which has no * valid relation entry and would error in find_base_rel . Such a Var * can appear when a nested set operation ' s output type doesn ' t match * the parent ' s expected type , because recurse_set_operations builds a * projection target list using generate_setop_tlist with varno 0 , and * if the required type coercion involves an ArrayCoerceExpr , we can * be called on that Var . if (IsA(arrayexpr, Var) && ((Var *) arrayexpr)->varno == 0 )return 10 ; /* default guess, should match scalararraysel */ 0 , &vardata);if (HeapTupleIsValid(vardata.statsTuple))/* * Found stats , so use the average element count , which is stored * in the last stanumbers element of the DECHIST statistics . * Actually that is the average count of * distinct * elements ; * perhaps we should scale it up somewhat ? if (get_attstatsslot(&sslot, vardata.statsTuple,if (sslot.nnumbers > 0 )1 ]);if (nelem > 0 )return nelem;/* Else use a default guess --- this should match scalararraysel */ return 10 ;/* * rowcomparesel - Selectivity of RowCompareExpr Node . * * We estimate RowCompare selectivity by considering just the first ( high * order ) columns , which makes it equivalent to an ordinary OpExpr . While * this estimate could be refined by considering additional columns , it * seems unlikely that we could do a lot better without multi - column * statistics . int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)bool is_join_clause;/* Build equivalent arg list for single operator */ /* * Decide if it ' s a join clause . This should match clausesel . c ' s * treat_as_join_clause ( ) , except that we intentionally consider only the * leading columns and not the rest of the clause . if (varRelid != 0 )/* * Caller is forcing restriction mode ( eg , because we are examining an * inner indexscan qual ) . false ;else if (sjinfo == NULL)/* * It must be a restriction clause , since it ' s being evaluated at a * scan node . false ;else /* * Otherwise , it ' s a join if there ' s more than one base relation used . 1 );if (is_join_clause)/* Estimate selectivity for a join clause. */ else /* Estimate selectivity for a restriction clause. */ return s1;/* * eqjoinsel - Join selectivity of " = " 0 );operator = PG_GETARG_OID(1 );2 );#ifdef NOT_USED3 );#endif 4 );double selec;double selec_inner;double nd1;double nd2;bool isdefault1;bool isdefault2;bool have_mcvs1 = false ;bool have_mcvs2 = false ;bool get_mcv_stats;bool join_is_reversed;operator );0 , sizeof (sslot1));0 , sizeof (sslot2));/* * There is no use in fetching one side ' s MCVs if we lack MCVs for the * other side , so do a quick check to verify that both stats exist . 0 ) &&0 ));if (HeapTupleIsValid(vardata1.statsTuple))/* note we allow use of nullfrac regardless of security check */ if (get_mcv_stats &&if (HeapTupleIsValid(vardata2.statsTuple))/* note we allow use of nullfrac regardless of security check */ if (get_mcv_stats &&/* We need to compute the inner-join selectivity in all cases */ switch (sjinfo->jointype)case JOIN_INNER:case JOIN_LEFT:case JOIN_FULL:break ;case JOIN_SEMI:case JOIN_ANTI:/* * Look up the join ' s inner relation . min_righthand is sufficient * information because neither SEMI nor ANTI joins permit any * reassociation into or out of their RHS , so the righthand will * always be exactly that set of rels . if (!join_is_reversed)else operator );/* * We should never estimate the output of a semijoin to be more * rows than we estimate for an inner join with the same input * rels and join condition ; it ' s obviously impossible for that to * happen . The former estimate is N1 * Ssemi while the latter is * N1 * N2 * Sinner , so we may clamp Ssemi < = N2 * Sinner . Doing * this is worthwhile because of the shakier estimation rules we * use in eqjoinsel_semi , particularly in cases where it has to * punt entirely . break ;default :/* other values not expected here */ "unrecognized join type: %d" ,int ) sjinfo->jointype);0 ; /* keep compiler quiet */ break ;/* * eqjoinsel_inner - - - eqjoinsel for normal inner join * * We also use this for LEFT / FULL outer joins ; it ' s not presently clear * that it ' s worth trying to distinguish them here . static double double nd1, double nd2,bool isdefault1, bool isdefault2,bool have_mcvs1, bool have_mcvs2)double selec;if (have_mcvs1 && have_mcvs2)/* * 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 1991 ( available from ftp . cs . wisc . edu ) . 2 );bool *hasmatch1;bool *hasmatch2;double nullfrac1 = stats1->stanullfrac;double nullfrac2 = stats2->stanullfrac;double matchprodfreq,int i,/* * Save a few cycles by setting up the fcinfo struct just once . Using * FunctionCallInvoke directly also avoids failure if the eqproc * returns NULL , though really equality functions should never do * that . 2 , collation,0 ].isnull = false ;1 ].isnull = false ;bool *) palloc0(sslot1->nvalues * sizeof (bool ));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 . . . 0 .0 ;0 ;for (i = 0 ; i < sslot1->nvalues; i++)int j;0 ].value = sslot1->values[i];for (j = 0 ; j < sslot2->nvalues; j++)if (hasmatch2[j])continue ;1 ].value = sslot2->values[j];false ;if (!fcinfo->isnull && DatumGetBool(fresult))true ;break ;/* Sum up frequencies of matched and unmatched MCVs */ 0 .0 ;for (i = 0 ; i < sslot1->nvalues; i++)if (hasmatch1[i])else 0 .0 ;for (i = 0 ; i < sslot2->nvalues; i++)if (hasmatch2[i])else /* * Compute total frequency of non - null values that are not in the MCV * lists . 1 .0 - nullfrac1 - matchfreq1 - unmatchfreq1;1 .0 - nullfrac2 - matchfreq2 - unmatchfreq2;/* * 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 . if (nd2 > sslot2->nvalues)if (nd2 > nmatches)/* Same estimate from the point of view of relation 2. */ if (nd1 > sslot1->nvalues)if (nd1 > nmatches)/* * Use the smaller of the two estimates . This can be justified in * essentially the same terms as given below for the no - stats case : to * a first approximation , we are estimating from the point of view of * the relation with smaller nd . else /* * We do not have MCV lists for both sides . Estimate the join * selectivity as MIN ( 1 / nd1 , 1 / nd2 ) * ( 1 - nullfrac1 ) * ( 1 - nullfrac2 ) . This * is plausible if we assume that the join operator is strict and the * non - null values are about equally distributed : a given non - null * tuple of rel1 will join to either zero or N2 * ( 1 - nullfrac2 ) / nd2 rows * of rel2 , so total join rows are at most * N1 * ( 1 - nullfrac1 ) * N2 * ( 1 - nullfrac2 ) / nd2 giving a join selectivity of * not more than ( 1 - nullfrac1 ) * ( 1 - nullfrac2 ) / nd2 . By the same logic it * is not more than ( 1 - nullfrac1 ) * ( 1 - nullfrac2 ) / nd1 , so the expression * with MIN ( ) is an upper bound . Using the MIN ( ) means we estimate * from the point of view of the relation with smaller nd ( since the * larger nd is determining the MIN ) . It is reasonable to assume that * most tuples in this rel will have join partners , so the bound is * probably reasonably tight and should be taken as - is . * * XXX Can we be smarter if we have an MCV list for just one side ? It * seems that if we assume equal distribution for the other side , we * end up with the same answer anyway . double nullfrac1 = stats1 ? stats1->stanullfrac : 0 .0 ;double nullfrac2 = stats2 ? stats2->stanullfrac : 0 .0 ;1 .0 - nullfrac1) * (1 .0 - nullfrac2);if (nd1 > nd2)else return selec;/* * eqjoinsel_semi - - - eqjoinsel for semi join * * ( Also used for anti join , which we are supposed to estimate the same way . ) * Caller has ensured that vardata1 is the LHS variable . * Unlike eqjoinsel_inner , we have to cope with opfuncoid being InvalidOid . static double double nd1, double nd2,bool isdefault1, bool isdefault2,bool have_mcvs1, bool have_mcvs2,double selec;/* * We clamp nd2 to be not more than what we estimate the inner relation ' s * size to be . This is intuitively somewhat reasonable since obviously * there can ' t be more than that many distinct values coming from the * inner rel . The reason for the asymmetry ( ie , that we don ' t clamp nd1 * likewise ) is that this is the only pathway by which restriction clauses * applied to the inner rel will affect the join result size estimate , * since set_joinrel_size_estimates will multiply SEMI / ANTI selectivity by * only the outer rel ' s size . If we clamped nd1 we ' d be double - counting * the selectivity of outer - rel restrictions . * * We can apply this clamping both with respect to the base relation from * which the join variable comes ( if there is just one ) , and to the * immediate inner input relation of the current join . * * If we clamp , we can treat nd2 as being a non - default estimate ; it ' s not * great , maybe , but it didn ' t come out of nowhere either . This is most * helpful when the inner relation is empty and consequently has no stats . if (vardata2->rel)if (nd2 >= vardata2->rel->rows)false ;if (nd2 >= inner_rel->rows)false ;if (have_mcvs1 && have_mcvs2 && OidIsValid(opfuncoid))/* * 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 . 2 );bool *hasmatch1;bool *hasmatch2;double nullfrac1 = stats1->stanullfrac;double matchfreq1,int i,/* * The clamping above could have resulted in nd2 being less than * sslot2 - > nvalues ; in which case , we assume that precisely the nd2 * most common values in the relation will appear in the join input , * and so compare to only the first nd2 members of the MCV list . Of * course this is frequently wrong , but it ' s the best bet we can make . /* * Save a few cycles by setting up the fcinfo struct just once . Using * FunctionCallInvoke directly also avoids failure if the eqproc * returns NULL , though really equality functions should never do * that . 2 , collation,0 ].isnull = false ;1 ].isnull = false ;bool *) palloc0(sslot1->nvalues * sizeof (bool ));bool *) palloc0(clamped_nvalues2 * 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 . . . 0 ;for (i = 0 ; i < sslot1->nvalues; i++)int j;0 ].value = sslot1->values[i];for (j = 0 ; j < clamped_nvalues2; j++)if (hasmatch2[j])continue ;1 ].value = sslot2->values[j];false ;if (!fcinfo->isnull && DatumGetBool(fresult))true ;break ;/* Sum up frequencies of matched MCVs */ 0 .0 ;for (i = 0 ; i < sslot1->nvalues; i++)if (hasmatch1[i])/* * Now we need to estimate the fraction of relation 1 that has at * least one join partner . We know for certain that the matched MCVs * do , so that gives us a lower bound , but we ' re really in the dark * about everything else . Our crude approach is : if nd1 < = nd2 then * assume all non - null rel1 rows have join partners , else assume for * the uncertain rows that a fraction nd2 / nd1 have join partners . We * can discount the known - matched MCVs from the distinct - values counts * before doing the division . * * Crude as the above is , it ' s completely useless if we don ' t have * reliable ndistinct values for both sides . Hence , if either nd1 or * nd2 is default , punt and assume half of the uncertain rows have * join partners . if (!isdefault1 && !isdefault2)if (nd1 <= nd2 || nd2 < 0 )1 .0 ;else else 0 .5 ;1 .0 - matchfreq1 - nullfrac1;else /* * Without MCV lists for both sides , we can only use the heuristic * about nd1 vs nd2 . double nullfrac1 = stats1 ? stats1->stanullfrac : 0 .0 ;if (!isdefault1 && !isdefault2)if (nd1 <= nd2 || nd2 < 0 )1 .0 - nullfrac1;else 1 .0 - nullfrac1);else 0 .5 * (1 .0 - nullfrac1);return selec;/* * neqjoinsel - Join selectivity of " ! = " 0 );operator = PG_GETARG_OID(1 );2 );3 );4 );if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)/* * For semi - joins , if there is more than one distinct value in the RHS * relation then every non - null LHS row must find a row to join since * it can only be equal to one of them . We ' ll assume that there is * always more than one distinct RHS value for the sake of stability , * though in theory we could have special cases for empty RHS * ( selectivity = 0 ) and single - distinct - value RHS ( selectivity = * fraction of LHS that has the same value as the single RHS value ) . * * For anti - joins , if we use the same assumption that there is more * than one distinct key in the RHS relation , then every non - null LHS * row must be suppressed by the anti - join . * * So either way , the selectivity estimate should be 1 - nullfrac . bool reversed;double nullfrac;if (HeapTupleIsValid(statsTuple))else 0 .0 ;1 .0 - nullfrac;else /* * We want 1 - eqjoinsel ( ) where the equality operator is the one * associated with this ! = operator , that is , its negator . operator );if (eqop)else /* Use default selectivity (should we raise an error instead?) */ 1 .0 - result;/* * scalarltjoinsel - Join selectivity of " < " for scalars /* * scalarlejoinsel - Join selectivity of " < = " for scalars /* * scalargtjoinsel - Join selectivity of " > " for scalars /* * scalargejoinsel - Join selectivity of " > = " for scalars /* * mergejoinscansel - Scan selectivity of merge join . * * A merge join will stop as soon as it exhausts either input stream . * Therefore , if we can estimate the ranges of both input variables , * we can estimate how much of the input will actually be read . This * can have a considerable impact on the cost when using indexscans . * * Also , we can estimate how much of each input has to be read before the * first join pair is found , which will affect the join ' s startup time . * * clause should be a clause already known to be mergejoinable . opfamily , * cmptype , and nulls_first specify the sort ordering being used . * * The outputs are : * * leftstart is set to the fraction of the left - hand variable expected * to be scanned before the first join pair is found ( 0 to 1 ) . * * leftend is set to the fraction of the left - hand variable expected * to be scanned before the join terminates ( 0 to 1 ) . * * rightstart , * rightend similarly for the right - hand variable . void bool nulls_first,int op_strategy;bool isgt;double selec;/* Set default results if we can't figure anything out. */ /* XXX should default "start" fraction be a bit more than 0? */ 0 .0 ;1 .0 ;/* Deconstruct the merge clause */ if (!is_opclause(clause))return ; /* shouldn't happen */ if (!right)return ; /* shouldn't happen */ /* Look for stats for the inputs */ 0 , &leftvar);0 , &rightvar);/* Extract the operator's declared left/right datatypes */ false ,true ) == COMPARE_EQ);/* * Look up the various operators we need . If we don ' t find them all , it * probably means the opfamily is broken , but we just fail silently . * * Note : we expect that pg_statistic histograms will be sorted by the ' < ' * operator , regardless of which sort direction we are considering . switch (cmptype)case COMPARE_LT:false ;true );true );if (op_lefttype == op_righttype)/* easy case */ else break ;case COMPARE_GT:/* descending-order case */ true ;true );true );true );if (op_lefttype == op_righttype)/* easy case */ else break ;default :goto fail; /* shouldn't get here */ if (!OidIsValid(lsortop) ||goto fail; /* insufficient info in catalogs */ /* Try to get ranges of both inputs */ if (!isgt)if (!get_variable_range(root, &leftvar, lstatop, collation,goto fail; /* no range available from stats */ if (!get_variable_range(root, &rightvar, rstatop, collation,goto fail; /* no range available from stats */ else /* need to swap the max and min */ if (!get_variable_range(root, &leftvar, lstatop, collation,goto fail; /* no range available from stats */ if (!get_variable_range(root, &rightvar, rstatop, collation,goto fail; /* no range available from stats */ /* * Now , the fraction of the left variable that will be scanned is the * fraction that ' s < = the right - side maximum value . But only believe * non - default estimates , else stick with our 1 . 0 . true , collation, &leftvar,if (selec != DEFAULT_INEQ_SEL)/* And similarly for the right variable. */ true , collation, &rightvar,if (selec != DEFAULT_INEQ_SEL)/* * Only one of the two " end " fractions can really be less than 1 . 0 ; * believe the smaller estimate and reset the other one to exactly 1 . 0 . If * we get exactly equal estimates ( as can easily happen with self - joins ) , * believe neither . if (*leftend > *rightend)1 .0 ;else if (*leftend < *rightend)1 .0 ;else 1 .0 ;/* * Also , the fraction of the left variable that will be scanned before the * first join pair is found is the fraction that ' s < the right - side * minimum value . But only believe non - default estimates , else stick with * our own default . false , collation, &leftvar,if (selec != DEFAULT_INEQ_SEL)/* And similarly for the right variable. */ false , collation, &rightvar,if (selec != DEFAULT_INEQ_SEL)/* * Only one of the two " start " fractions can really be more than zero ; * believe the larger estimate and reset the other one to exactly 0 . 0 . If * we get exactly equal estimates ( as can easily happen with self - joins ) , * believe neither . if (*leftstart < *rightstart)0 .0 ;else if (*leftstart > *rightstart)0 .0 ;else 0 .0 ;/* * If the sort order is nulls - first , we ' re going to have to skip over any * nulls too . These would not have been counted by scalarineqsel , and we * can safely add in this fraction regardless of whether we believe * scalarineqsel ' s results or not . But be sure to clamp the sum to 1 . 0 ! if (nulls_first)if (HeapTupleIsValid(leftvar.statsTuple))if (HeapTupleIsValid(rightvar.statsTuple))/* Disbelieve start >= end, just in case that can happen */ if (*leftstart >= *leftend)0 .0 ;1 .0 ;if (*rightstart >= *rightend)0 .0 ;1 .0 ;/* * matchingsel - - generic matching - operator selectivity support * * Use these for any operators that ( a ) are on data types for which we collect * standard statistics , and ( b ) have behavior for which the default estimate * ( twice DEFAULT_EQ_SEL ) is sane . Typically that is good for match - like * operators . 0 );operator = PG_GETARG_OID(1 );2 );int varRelid = PG_GETARG_INT32(3 );double selec;/* Use generic restriction selectivity logic. */ operator , collation,/* Just punt, for the moment. */ /* * Helper routine for estimate_num_groups : add an item to a list of * GroupVarInfos , but only if it ' s not known equal to any of the existing * entries . typedef struct /* might be an expression, not just a Var */ /* relation it belongs to */ double ndistinct; /* # distinct values */ bool isdefault; /* true if DEFAULT_NUM_DISTINCT was used */ static List *double ndistinct;bool isdefault;/* * The nullingrels bits within the var could cause the same var to be * counted multiple times if it ' s marked with different nullingrels . They * could also prevent us from matching the var to the expressions in * extended statistics ( see estimate_multivariate_ndistinct ) . So strip * them out first . /* Drop exact duplicates */ if (equal(var, varinfo->var))return varinfos;/* * Drop known - equal vars , but only if they belong to different * relations ( see comments for estimate_num_groups ) . We aren ' t too * fussy about the semantics of " equal " here . if (vardata->rel != varinfo->rel &&if (varinfo->ndistinct <= ndistinct)/* Keep older item, forget new one */ return varinfos;else /* Delete the older item */ sizeof (GroupVarInfo));return varinfos;/* * estimate_num_groups - Estimate number of groups in a grouped query * * Given a query having a GROUP BY clause , estimate how many groups there * will be - - - ie , the number of distinct combinations of the GROUP BY * expressions . * * This routine is also used to estimate the number of rows emitted by * a DISTINCT filtering step ; that is an isomorphic problem . ( Note : * actually , we only use it for DISTINCT when there ' s no grouping or * aggregation ahead of the DISTINCT . ) * * Inputs : * root - the query * groupExprs - list of expressions being grouped by * input_rows - number of rows estimated to arrive at the group / unique * filter step * pgset - NULL , or a List * * pointing to a grouping set to filter the * groupExprs against * * Outputs : * estinfo - When passed as non - NULL , the function will set bits in the * " flags " field in order to provide callers with additional information * about the estimation . Currently , we only set the SELFLAG_USED_DEFAULT * bit if we used any default values in the estimation . * * Given the lack of any cross - correlation statistics in the system , it ' s * impossible to do anything really trustworthy with GROUP BY conditions * involving multiple Vars . We should however avoid assuming the worst * case ( all possible cross - product terms actually appear as groups ) since * very often the grouped - by Vars are highly correlated . Our current approach * is as follows : * 1 . Expressions yielding boolean are assumed to contribute two groups , * independently of their content , and are ignored in the subsequent * steps . This is mainly because tests like " col IS NULL " break the * heuristic used in step 2 especially badly . * 2 . Reduce the given expressions to a list of unique Vars used . For * example , GROUP BY a , a + b is treated the same as GROUP BY a , b . * It is clearly correct not to count the same Var more than once . * It is also reasonable to treat f ( x ) the same as x : f ( ) cannot * increase the number of distinct values ( unless it is volatile , * which we consider unlikely for grouping ) , but it probably won ' t * reduce the number of distinct values much either . * As a special case , if a GROUP BY expression can be matched to an * expressional index for which we have statistics , then we treat the * whole expression as though it were just a Var . * 3 . If the list contains Vars of different relations that are known equal * due to equivalence classes , then drop all but one of the Vars from each * known - equal set , keeping the one with smallest estimated # of values * ( since the extra values of the others can ' t appear in joined rows ) . * Note the reason we only consider Vars of different relations is that * if we considered ones of the same rel , we ' d be double - counting the * restriction selectivity of the equality in the next step . * 4 . For Vars within a single source rel , we multiply together the numbers * of values , clamp to the number of rows in the rel ( divided by 10 if * more than one Var ) , and then multiply by a factor based on the * selectivity of the restriction clauses for that rel . When there ' s * more than one Var , the initial product is probably too high ( it ' s the * worst case ) but clamping to a fraction of the rel ' s rows seems to be a * helpful heuristic for not letting the estimate get out of hand . ( The * factor of 10 is derived from pre - Postgres - 7 . 4 practice . ) The factor * we multiply by to adjust for the restriction selectivity assumes that * the restriction clauses are independent of the grouping , which may not * be a valid assumption , but it ' s hard to do better . * 5 . If there are Vars from multiple rels , we repeat step 4 for each such * rel , and multiply the results together . * Note that rels not containing grouped Vars are ignored completely , as are * join clauses . Such rels cannot increase the number of groups , and we * assume such clauses do not reduce the number either ( somewhat bogus , * but we don ' t have the info to do better ) . double double input_rows,double srf_multiplier = 1 .0 ;double numdistinct;int i;/* Zero the estinfo output parameter, if non-NULL */ if (estinfo != NULL)0 , sizeof (EstimationInfo));/* * We don ' t ever want to return an estimate of zero groups , as that tends * to lead to division - by - zero and other unpleasantness . The input_rows * estimate is usually already at least 1 , but clamp it just in case it * isn ' t . /* * If no grouping columns , there ' s exactly one group . ( This can ' t happen * for normal cases with GROUP BY or DISTINCT , but it is possible for * corner cases with set operations . ) if (groupExprs == NIL || (pgset && *pgset == NIL))return 1 .0 ;/* * Count groups derived from boolean grouping expressions . For other * expressions , find the unique Vars used , treating an expression as a Var * if we can find stats for it . For each one , record the statistical * estimate of number of distinct values ( total in its table , without * regard for filtering ) . 1 .0 ;0 ;double this_srf_multiplier;/* is expression in this grouping set? */ if (pgset && !list_member_int(*pgset, i++))continue ;/* * Set - returning functions in grouping columns are a bit problematic . * The code below will effectively ignore their SRF nature and come up * with a numdistinct estimate as though they were scalar functions . * We compensate by scaling up the end result by the largest SRF * rowcount estimate . ( This will be an overestimate if the SRF * produces multiple copies of any output value , but it seems best to * assume the SRF ' s outputs are distinct . In any case , it ' s probably * pointless to worry too much about this without much better * estimates for SRF output rowcounts than we have today . ) if (srf_multiplier < this_srf_multiplier)/* Short-circuit for expressions returning boolean */ if (exprType(groupexpr) == BOOLOID)2 .0 ;continue ;/* * If examine_variable is able to deduce anything about the GROUP BY * expression , treat it as a single variable even if it ' s really more * complicated . * * XXX This has the consequence that if there ' s a statistics object on * the expression , we don ' t split it into individual Vars . This * affects our selection of statistics in * estimate_multivariate_ndistinct , because it ' s probably better to * use more accurate estimate for each expression and treat them as * independent , than to combine estimates for the extracted variables * when we don ' t know how that relates to the expressions . 0 , &vardata);if (HeapTupleIsValid(vardata.statsTuple) || vardata.isunique)continue ;/* * Else pull out the component Vars . Handle PlaceHolderVars by * recursing into their arguments ( effectively assuming that the * PlaceHolderVar doesn ' t change the number of groups , which boils * down to ignoring the possible addition of nulls to the result set ) . /* * If we find any variable - free GROUP BY item , then either it is a * constant ( and we can ignore it ) or it contains a volatile function ; * in the latter case we punt and assume that each input row will * yield a distinct group . if (varshere == NIL)if (contain_volatile_functions(groupexpr))return input_rows;continue ;/* * Else add variables to varinfos list 0 , &vardata);/* * If now no Vars , we must have an all - constant or all - boolean GROUP BY * list . if (varinfos == NIL)/* Apply SRF multiplier as we would do in the long path */ /* Round off */ /* Guard against out-of-range answers */ if (numdistinct > input_rows)if (numdistinct < 1 .0 )1 .0 ;return numdistinct;/* * Group Vars by relation and estimate total numdistinct . * * For each iteration of the outer loop , we process the frontmost Var in * varinfos , plus all other Vars in the same relation . We remove these * Vars from the newvarinfos list for the next iteration . This is the * easiest way to group Vars of same rel together . do double reldistinct = 1 ;double relmaxndistinct = reldistinct;int relvarcount = 0 ;/* * Split the list of varinfos in two - one for the current rel , one * for remaining Vars on other rels . 1 )if (varinfo2->rel == varinfo1->rel)/* varinfos on current rel */ else /* not time to process varinfo2 yet */ /* * Get the numdistinct estimate for the Vars of this rel . We * iteratively search for multivariate n - distinct with maximum number * of vars ; assuming that each var group is independent of the others , * we multiply them together . Any remaining relvarinfos after no more * multivariate matches are found are assumed independent too , so * their individual ndistinct estimates are multiplied also . * * While iterating , count how many separate numdistinct values we * apply . We apply a fudge factor below , but only if we multiplied * more than one such values . while (relvarinfos)double mvndistinct;if (estimate_multivariate_ndistinct(root, rel, &relvarinfos,if (relmaxndistinct < mvndistinct)else if (relmaxndistinct < varinfo2->ndistinct)/* * When varinfo2 ' s isdefault is set then we ' d better set * the SELFLAG_USED_DEFAULT bit in the EstimationInfo . if (estinfo != NULL && varinfo2->isdefault)/* we're done with this relation */ /* * Sanity check - - - don ' t divide by zero if empty relation . if (rel->tuples > 0 )/* * Clamp to size of rel , or size of rel / 10 if multiple Vars . The * fudge factor is because the Vars are probably correlated but we * don ' t know by how much . We should never clamp to less than the * largest ndistinct value for any of the Vars , though , since * there will surely be at least that many groups . double clamp = rel->tuples;if (relvarcount > 1 )0 .1 ;if (clamp < relmaxndistinct)/* for sanity in case some ndistinct is too large: */ if (clamp > rel->tuples)if (reldistinct > clamp)/* * Update the estimate based on the restriction selectivity , * guarding against division by zero when reldistinct is zero . * Also skip this if we know that we are returning all rows . if (reldistinct > 0 && rel->rows < rel->tuples)/* * Given a table containing N rows with n distinct values in a * uniform distribution , if we select p rows at random then * the expected number of distinct values selected is * * n * ( 1 - product ( ( N - N / n - i ) / ( N - i ) , i = 0 . . p - 1 ) ) * * = n * ( 1 - ( N - N / n ) ! / ( N - N / n - p ) ! * ( N - p ) ! / N ! ) * * See " Approximating block accesses in database * organizations " , S . B . Yao , Communications of the ACM , * Volume 20 Issue 4 , April 1977 Pages 260 - 261 . * * Alternatively , re - arranging the terms from the factorials , * this may be written as * * n * ( 1 - product ( ( N - p - i ) / ( N - i ) , i = 0 . . N / n - 1 ) ) * * This form of the formula is more efficient to compute in * the common case where p is larger than N / n . Additionally , * as pointed out by Dell ' Era , if i < < N for all terms in the * product , it can be approximated by * * n * ( 1 - ( ( N - p ) / N ) ^ ( N / n ) ) * * See " Expected distinct values when selecting from a bag * without replacement " , Alberto Dell ' Era , * http : //www.adellera.it/investigations/distinct_balls/. * * The condition i < < N is equivalent to n > > 1 , so this is a * good approximation when the number of distinct values in * the table is large . It turns out that this formula also * works well even when n is small . 1 - pow((rel->tuples - rel->rows) / rel->tuples,/* * Update estimate of total distinct groups . while (varinfos != NIL);/* Now we can account for the effects of any SRFs */ /* Round off */ /* Guard against out-of-range answers */ if (numdistinct > input_rows)if (numdistinct < 1 .0 )1 .0 ;return numdistinct;/* * Try to estimate the bucket size of the hash join inner side when the join * condition contains two or more clauses by employing extended statistics . * * The main idea of this approach is that the distinct value generated by * multivariate estimation on two or more columns would provide less bucket size * than estimation on one separate column . * * IMPORTANT : It is crucial to synchronize the approach of combining different * estimations with the caller ' s method . * * Return a list of clauses that didn ' t fetch any extended statistics . double ndistinct = 1 .0 ;if (list_length(hashclauses) <= 1 )/* * Nothing to do for a single clause . Could we employ univariate * extended stat here ? return hashclauses;while (clauses != NIL)int relid = -1 ;double mvndistinct;int group_relid = -1 ;/* * Find clauses , referencing the same single base relation and try to * estimate such a group with extended statistics . Create varinfo for * an approved clause , push it to otherclauses , if it can ' t be * estimated here or ignore to process at the next iteration . /* * Find the inner side of the join , which we need to estimate the * number of buckets . Use outer_is_left because the * clause_sides_match_join routine has called on hash clauses . if (bms_get_singleton_member(relids, &relid) &&bool is_duplicate = false ;/* * This inner - side expression references only one relation . * Extended statistics on this clause can exist . if (group_relid < 0 )if (!rte || (rte->relkind != RELKIND_RELATION &&/* Extended statistics can't exist in principle */ continue ;else if (group_relid != relid)/* * Being in the group forming state we don ' t need other * clauses . continue ;/* * We ' re going to add the new clause to the varinfos list . We * might re - use add_unique_group_var ( ) , but we don ' t do so for * two reasons . * * 1 ) We must keep the origin_rinfos list ordered exactly the * same way as varinfos . * * 2 ) add_unique_group_var ( ) is designed for * estimate_num_groups ( ) , where a larger number of groups is * worse . While estimating the number of hash buckets , we * have the opposite : a lesser number of groups is worse . * Therefore , we don ' t have to remove " known equal " vars : the * removed var may valuably contribute to the multivariate * statistics to grow the number of groups . /* * Clear nullingrels to correctly match hash keys . See * add_unique_group_var ( ) ' s comment for details . /* * Detect and exclude exact duplicates from the list of hash * keys ( like add_unique_group_var does ) . if (!equal(expr, varinfo->var))continue ;true ;break ;if (is_duplicate)/* * Skip exact duplicates . Adding them to the otherclauses * list also doesn ' t make sense . continue ;/* * Initialize GroupVarInfo . We only use it to call * estimate_multivariate_ndistinct ( ) , which doesn ' t care about * ndistinct and isdefault fields . Thus , skip these fields . sizeof (GroupVarInfo));/* * Remember the link to RestrictInfo for the case the clause * is failed to be estimated . else /* This clause can't be estimated with extended statistics */ if (list_length(varinfos) < 2 )/* * Multivariate statistics doesn ' t apply to single columns except * for expressions , but it has not been implemented yet . continue ;/* Employ the extended statistics. */ for (;;)bool estimated = estimate_multivariate_ndistinct(root,if (!estimated)break ;/* * We ' ve got an estimation . Use ndistinct value in a consistent * way - according to the caller ' s logic ( see * final_cost_hashjoin ) . if (ndistinct < mvndistinct)1 .0 );/* Collect unmatched clauses as otherclauses. */ if (!list_member_ptr(varinfos, vinfo))/* Already estimated */ continue ;/* Can't be estimated here - push to the returning list */ 1 .0 / ndistinct;return otherclauses;/* * Estimate hash bucket statistics when the specified expression is used * as a hash key for the given number of buckets . * * This attempts to determine two values : * * 1 . The frequency of the most common value of the expression ( returns * zero into * mcv_freq if we can ' t get that ) . * * 2 . The " bucketsize fraction " , ie , average number of entries in a bucket * divided by total tuples in relation . * * XXX This is really pretty bogus since we ' re effectively assuming that the * distribution of hash keys will be the same after applying restriction * clauses as it was in the underlying relation . However , we are not nearly * smart enough to figure out how the restrict clauses might change the * distribution , so this will have to do for now . * * We are passed the number of buckets the executor will use for the given * input relation . If the data were perfectly distributed , with the same * number of tuples going into each available bucket , then the bucketsize * fraction would be 1 / nbuckets . But this happy state of affairs will occur * only if ( a ) there are at least nbuckets distinct data values , and ( b ) * we have a not - too - skewed data distribution . Otherwise the buckets will * be nonuniformly occupied . If the other relation in the join has a key * distribution similar to this one ' s , then the most - loaded buckets are * exactly those that will be probed most often . Therefore , the " average " * bucket size for costing purposes should really be taken as something close * to the " worst case " bucket size . We try to estimate this by adjusting the * fraction if there are too few distinct data values , and then scaling up * by the ratio of the most common value ' s frequency to the average frequency . * * If no statistics are available , use a default estimate of 0 . 1 . This will * discourage use of a hash rather strongly if the inner relation is large , * which is what we want . We do not want to hash unless we know that the * inner rel is well - dispersed ( or the alternatives seem much worse ) . * * The caller should also check that the mcv_freq is not so large that the * most common value would by itself require an impractically large bucket . * In a hash join , the executor can split buckets if they get too big , but * obviously that doesn ' t help for a bucket that contains many duplicates of * the same value . void double nbuckets,double estfract,bool isdefault;0 , &vardata);/* Look up the frequency of the most common value, if available */ 0 .0 ;if (HeapTupleIsValid(vardata.statsTuple))if (get_attstatsslot(&sslot, vardata.statsTuple,/* * The first MCV stat is for the most common value . if (sslot.nnumbers > 0 )0 ];/* Get number of distinct values */ /* * If ndistinct isn ' t real , punt . We normally return 0 . 1 , but if the * mcv_freq is known to be even higher than that , use it instead . if (isdefault)0 .1 , *mcv_freq);return ;/* Get fraction that are null */ if (HeapTupleIsValid(vardata.statsTuple))else 0 .0 ;/* Compute avg freq of all distinct data values in raw relation */ 1 .0 - stanullfrac) / ndistinct;/* * Adjust ndistinct to account for restriction clauses . Observe we are * assuming that the data distribution is affected uniformly by the * restriction clauses ! * * XXX Possibly better way , but much more expensive : multiply by * selectivity of rel ' s restriction clauses that mention the target Var . if (vardata.rel && vardata.rel->tuples > 0 )/* * Initial estimate of bucketsize fraction is 1 / nbuckets as long as the * number of buckets is less than the expected number of distinct values ; * otherwise it is 1 / ndistinct . if (ndistinct > nbuckets)1 .0 / nbuckets;else 1 .0 / ndistinct;/* * Adjust estimated bucketsize upward to account for skewed distribution . if (avgfreq > 0 .0 && *mcv_freq > avgfreq)/* * Clamp bucketsize to sane range ( the above adjustment could easily * produce an out - of - range result ) . We set the lower bound a little above * zero , since zero isn ' t a very sane result . if (estfract < 1 .0 e-6 )1 .0 e-6 ;else if (estfract > 1 .0 )1 .0 ;/* * estimate_hashagg_tablesize * estimate the number of bytes that a hash aggregate hashtable will * require based on the agg_costs , path width and number of groups . * * We return the result as " double " to forestall any possible overflow * problem in the multiplication by dNumGroups . * * XXX this may be over - estimating the size now that hashagg knows to omit * unneeded columns from the hashtable . Also for mixed - mode grouping sets , * grouping columns not in the hashed set are counted here even though hashagg * won ' t store them . Is this a problem ? double const AggClauseCosts *agg_costs, double dNumGroups)/* * Note that this disregards the effect of fill - factor and growth policy * of the hash table . That ' s probably ok , given that the default * fill - factor is relatively high . It ' d be hard to meaningfully factor in * " double - in - size " growth policies here . return hashentrysize * dNumGroups;/*------------------------------------------------------------------------- * * Support routines * * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - /* * Find the best matching ndistinct extended statistics for the given list of * GroupVarInfos . * * Callers must ensure that the given GroupVarInfos all belong to ' rel ' and * the GroupVarInfos list does not contain any duplicate Vars or expressions . * * When statistics are found that match > 1 of the given GroupVarInfo , the * * ndistinct parameter is set according to the ndistinct estimate and a new * list is built with the matching GroupVarInfos removed , which is output via * the * varinfos parameter before returning true . When no matching stats are * found , false is returned and the * varinfos and * ndistinct parameters are * left untouched . static bool double *ndistinct)int nmatches_vars;int nmatches_exprs;/* bail out immediately if the table has no extended statistics */ if (!rel->statlist)return false ;/* look for the ndistinct statistics object matching the most vars */ 0 ; /* we require at least two matches */ 0 ;int nshared_vars = 0 ;int nshared_exprs = 0 ;/* skip statistics of other kinds */ if (info->kind != STATS_EXT_NDISTINCT)continue ;/* skip statistics with mismatching stxdinherit value */ if (info->inherit != rte->inh)continue ;/* * Determine how many expressions ( and variables in non - matched * expressions ) match . We ' ll then use these numbers to pick the * statistics object that best matches the clauses . /* simple Var, search in statistics keys directly */ if (IsA(varinfo->var, Var))/* * Ignore system attributes - we don ' t support statistics on * them , so can ' t match them ( and it ' d fail as the values are * negative ) . if (!AttrNumberIsForUserDefinedAttr(attnum))continue ;if (bms_is_member(attnum, info->keys))continue ;/* expression - see if it's in the statistics object */ if (equal(varinfo->var, expr))break ;/* * The ndistinct extended statistics contain estimates for a minimum * of pairs of columns which the statistics are defined on and * certainly not single columns . Here we skip unless we managed to * match to at least two columns . if (nshared_vars + nshared_exprs < 2 )continue ;/* * Check if these statistics are a better match than the previous best * match and if so , take note of the StatisticExtInfo . * * The statslist is sorted by statOid , so the StatisticExtInfo we * select as the best match is deterministic even when multiple sets * of statistics match equally as well . if ((nshared_exprs > nmatches_exprs) ||/* No match? */ if (statOid == InvalidOid)return false ;1 );/* * If we have a match , search it for the specific item that matches ( there * must be one ) , and construct the output values . if (stats)int i;/* * How much we need to offset the attnums ? If there are no * expressions , no offset is needed . Otherwise offset enough to move * the lowest one ( which is equal to number of expressions ) to 1 . if (matched_info->exprs)1 );else 0 ;/* see what actually matched */ int idx;bool found = false ;/* * Process a simple Var expression , by matching it to keys * directly . If there ' s a matching expression , we ' ll try matching * it later . if (IsA(varinfo->var, Var))/* * Ignore expressions on system attributes . Can ' t rely on the * bms check for negative values . if (!AttrNumberIsForUserDefinedAttr(attnum))continue ;/* Is the variable covered by the statistics object? */ if (!bms_is_member(attnum, matched_info->keys))continue ;/* ensure sufficient offset */ true ;/* * XXX Maybe we should allow searching the expressions even if we * found an attribute matching the expression ? That would handle * trivial expressions like " ( a ) " but it seems fairly useless . if (found)continue ;/* expression - see if it's in the statistics object */ 0 ;if (equal(varinfo->var, expr))1 );/* ensure sufficient offset */ /* there should be just one matching expression */ break ;/* Find the specific item that exactly matches the combination */ for (i = 0 ; i < stats->nitems; i++)int j;if (tmpitem->nattributes != bms_num_members(matched))continue ;/* assume it's the right item */ /* check that all item attributes/expressions fit the match */ for (j = 0 ; j < tmpitem->nattributes; j++)/* * Thanks to how we constructed the matched bitmap above , we * can just offset all attnums the same way . if (!bms_is_member(attnum, matched))/* nah, it's not this item */ break ;/* * If the item has all the matched attributes , we know it ' s the * right one - there can ' t be a better one . matching more . if (item)break ;/* * Make sure we found an item . There has to be one , because ndistinct * statistics includes all combinations of attributes . if (!item)"corrupt MVNDistinct entry" );/* Form the output varinfo list, keeping only unmatched ones */ bool found = false ;/* * Let ' s look at plain variables first , because it ' s the most * common case and the check is quite cheap . We can simply get the * attnum and check ( with an offset ) matched bitmap . if (IsA(varinfo->var, Var))/* * If it ' s a system attribute , we ' re done . We don ' t support * extended statistics on system attributes , so it ' s clearly * not matched . Just keep the expression and continue . if (!AttrNumberIsForUserDefinedAttr(attnum))continue ;/* apply the same offset as above */ /* if it's not matched, keep the varinfo */ if (!bms_is_member(attnum, matched))/* The rest of the loop deals with complex expressions. */ continue ;/* * Process complex expressions , not just simple Vars . * * First , we search for an exact match of an expression . If we * find one , we can just discard the whole GroupVarInfo , with all * the variables we extracted from it . * * Otherwise we inspect the individual vars , and try matching it * to variables in the item . if (equal(varinfo->var, expr))true ;break ;/* found exact match, skip */ if (found)continue ;return true ;return false ;/* * convert_to_scalar * Convert non - NULL values of the indicated types to the comparison * scale needed by scalarineqsel ( ) . * Returns " true " if successful . * * XXX this routine is a hack : ideally we should look up the conversion * subroutines in pg_type . * * All numeric datatypes are simply converted to their equivalent * " double " values . ( NUMERIC values that are outside the range of " double " * are clamped to + / - HUGE_VAL . ) * * String datatypes are converted by convert_string_to_scalar ( ) , * which is explained below . The reason why this routine deals with * three values at a time , not just one , is that we need it for strings . * * The bytea datatype is just enough different from strings that it has * to be treated separately . * * The several datatypes representing absolute times are all converted * to Timestamp , which is actually an int64 , and then we promote that to * a double . Note this will give correct results even for the " special " * values of Timestamp , since those are chosen to compare correctly ; * see timestamp_cmp . * * The several datatypes representing relative times ( intervals ) are all * converted to measurements expressed in seconds . static bool double *scaledvalue,double *scaledlobound, double *scaledhibound)bool failure = false ;/* * Both the valuetypid and the boundstypid should exactly match the * declared input type ( s ) of the operator we are invoked for . However , * extensions might try to use scalarineqsel as estimator for operators * with input type ( s ) we don ' t handle here ; in such cases , we want to * return false , not fail . In any case , we mustn ' t assume that valuetypid * and boundstypid are identical . * * XXX The histogram we are interpolating between points of could belong * to a column that ' s only binary - compatible with the declared type . In * essence we are assuming that the semantics of binary - compatible types * are enough alike that we can use a histogram generated with one type ' s * operators to estimate selectivity for the other ' s . This is outright * wrong in some cases - - - in particular signed versus unsigned * interpretation could trip us up . But it ' s useful enough in the * majority of cases that we do it anyway . Should think about more * rigorous ways to do it . switch (valuetypid)/* * Built - in numeric types case BOOLOID:case INT2OID:case INT4OID:case INT8OID:case FLOAT4OID:case FLOAT8OID:case NUMERICOID:case OIDOID:case REGPROCOID:case REGPROCEDUREOID:case REGOPEROID:case REGOPERATOROID:case REGCLASSOID:case REGTYPEOID:case REGCOLLATIONOID:case REGCONFIGOID:case REGDICTIONARYOID:case REGROLEOID:case REGNAMESPACEOID:return !failure;/* * Built - in string types case CHAROID:case BPCHAROID:case VARCHAROID:case TEXTOID:case NAMEOID:char *valstr = convert_string_datum(value, valuetypid,char *lostr = convert_string_datum(lobound, boundstypid,char *histr = convert_string_datum(hibound, boundstypid,/* * Bail out if any of the values is not of string type . We * might leak converted strings for the other value ( s ) , but * that ' s not worth troubling over . if (failure)return false ;return true ;/* * Built - in bytea type case BYTEAOID:/* We only support bytea vs bytea comparison */ if (boundstypid != BYTEAOID)return false ;return true ;/* * Built - in time types case TIMESTAMPOID:case TIMESTAMPTZOID:case DATEOID:case INTERVALOID:case TIMEOID:case TIMETZOID:return !failure;/* * Built - in network types case INETOID:case CIDROID:case MACADDROID:case MACADDR8OID:return !failure;/* Don't know how to convert */ 0 ;return false ;/* * Do convert_to_scalar ( ) ' s work for any numeric data type . * * On failure ( e . g . , unsupported typid ) , set * failure to true ; * otherwise , that variable is not changed . static double bool *failure)switch (typid)case BOOLOID:return (double ) DatumGetBool(value);case INT2OID:return (double ) DatumGetInt16(value);case INT4OID:return (double ) DatumGetInt32(value);case INT8OID:return (double ) DatumGetInt64(value);case FLOAT4OID:return (double ) DatumGetFloat4(value);case FLOAT8OID:return (double ) DatumGetFloat8(value);case NUMERICOID:/* Note: out-of-range values will be clamped to +-HUGE_VAL */ return (double )case OIDOID:case REGPROCOID:case REGPROCEDUREOID:case REGOPEROID:case REGOPERATOROID:case REGCLASSOID:case REGTYPEOID:case REGCOLLATIONOID:case REGCONFIGOID:case REGDICTIONARYOID:case REGROLEOID:case REGNAMESPACEOID:/* we can treat OIDs as integers... */ return (double ) DatumGetObjectId(value);true ;return 0 ;/* * Do convert_to_scalar ( ) ' s work for any character - string data type . * * String datatypes are converted to a scale that ranges from 0 to 1 , * where we visualize the bytes of the string as fractional digits . * * We do not want the base to be 256 , however , since that tends to * generate inflated selectivity estimates ; few databases will have * occurrences of all 256 possible byte values at each position . * Instead , use the smallest and largest byte values seen in the bounds * as the estimated range for each byte , after some fudging to deal with * the fact that we probably aren ' t going to see the full range that way . * * An additional refinement is that we discard any common prefix of the * three strings before computing the scaled values . This allows us to * " zoom in " when we encounter a narrow data range . An example is a phone * number database where all the values begin with the same area code . * ( Actually , the bounds will be adjacent histogram - bin - boundary values , * so this is more likely to happen than you might think . ) static void char *value,double *scaledvalue,char *lobound,double *scaledlobound,char *hibound,double *scaledhibound)int rangelo,char *sptr;unsigned char ) hibound[0 ];for (sptr = lobound; *sptr; sptr++)if (rangelo > (unsigned char ) *sptr)unsigned char ) *sptr;if (rangehi < (unsigned char ) *sptr)unsigned char ) *sptr;for (sptr = hibound; *sptr; sptr++)if (rangelo > (unsigned char ) *sptr)unsigned char ) *sptr;if (rangehi < (unsigned char ) *sptr)unsigned char ) *sptr;/* If range includes any upper-case ASCII chars, make it include all */ if (rangelo <= 'Z' && rangehi >= 'A' )if (rangelo > 'A' )'A' ;if (rangehi < 'Z' )'Z' ;/* Ditto lower-case */ if (rangelo <= 'z' && rangehi >= 'a' )if (rangelo > 'a' )'a' ;if (rangehi < 'z' )'z' ;/* Ditto digits */ if (rangelo <= '9' && rangehi >= '0' )if (rangelo > '0' )'0' ;if (rangehi < '9' )'9' ;/* * If range includes less than 10 chars , assume we have not got enough * data , and make it include regular ASCII set . if (rangehi - rangelo < 9 )' ' ;127 ;/* * Now strip any common prefix of the three strings . while (*lobound)if (*lobound != *hibound || *lobound != *value)break ;/* * Now we can do the conversions . static double char *value, int rangelo, int rangehi)int slen = strlen(value);double num,if (slen <= 0 )return 0 .0 ; /* empty string has scalar value 0 */ /* * There seems little point in considering more than a dozen bytes from * the string . Since base is at least 10 , that will give us nominal * resolution of at least 12 decimal digits , which is surely far more * precision than this estimation technique has got anyway ( especially in * non - C locales ) . Also , even with the maximum possible base of 256 , this * ensures denom cannot grow larger than 256 ^ 13 = 2 . 03 e31 , which will not * overflow on any known machine . if (slen > 12 )12 ;/* Convert initial characters to fraction */ 1 ;0 .0 ;while (slen-- > 0 )int ch = (unsigned char ) *value++;if (ch < rangelo)1 ;else if (ch > rangehi)1 ;double ) (ch - rangelo)) / denom;return num;/* * Convert a string - type Datum into a palloc ' d , null - terminated string . * * On failure ( e . g . , unsupported typid ) , set * failure to true ; * otherwise , that variable is not changed . ( We ' ll return NULL on failure . ) * * When using a non - C locale , we must pass the string through pg_strxfrm ( ) * before continuing , so as to generate correct locale - specific results . static char *bool *failure)char *val;switch (typid)case CHAROID:char *) palloc(2 );0 ] = DatumGetChar(value);1 ] = '\0' ;break ;case BPCHAROID:case VARCHAROID:case TEXTOID:break ;case NAMEOID:break ;default :true ;return NULL;if (!mylocale->collate_is_c)char *xfrmstr;/* * XXX : We could guess at a suitable output buffer size and only call * pg_strxfrm ( ) twice if our guess is too small . * * XXX : strxfrm doesn ' t support UTF - 8 encoding on Win32 , it can return * bogus data or set an error . This is not really a problem unless it * crashes since it will only give an estimation error and nothing * fatal . * * XXX : we do not check pg_strxfrm_enabled ( ) . On some platforms and in * some cases , libc strxfrm ( ) may return the wrong results , but that * will only lead to an estimation error . 0 , mylocale);#ifdef WIN32/* * On Windows , strxfrm returns INT_MAX when an error occurs . Instead * of trying to allocate this much memory ( and fail ) , just return the * original string unmodified as if we were in the C locale . if (xfrmlen == INT_MAX)return val;#endif char *) palloc(xfrmlen + 1 );1 , mylocale);/* * Some systems ( e . g . , glibc ) can return a smaller value from the * second call than the first ; thus the Assert must be < = not = = . return val;/* * Do convert_to_scalar ( ) ' s work for any bytea data type . * * Very similar to convert_string_to_scalar except we can ' t assume * null - termination and therefore pass explicit lengths around . * * Also , assumptions about likely " normal " ranges of characters have been * removed - a data range of 0 . . 255 is always used , for now . ( Perhaps * someday we will add information about actual byte data range to * pg_statistic . ) static void double *scaledvalue,double *scaledlobound,double *scaledhibound)int rangelo,unsigned char *valstr = (unsigned char *) VARDATA_ANY(valuep);unsigned char *lostr = (unsigned char *) VARDATA_ANY(loboundp);unsigned char *histr = (unsigned char *) VARDATA_ANY(hiboundp);/* * Assume bytea data is uniformly distributed across all byte values . 0 ;255 ;/* * Now strip any common prefix of the three strings . for (i = 0 ; i < minlen; i++)if (*lostr != *histr || *lostr != *valstr)break ;/* * Now we can do the conversions . static double unsigned char *value, int valuelen,int rangelo, int rangehi)double num,if (valuelen <= 0 )return 0 .0 ; /* empty string has scalar value 0 */ /* * Since base is 256 , need not consider more than about 10 chars ( even * this many seems like overkill ) if (valuelen > 10 )10 ;/* Convert initial characters to fraction */ 1 ;0 .0 ;while (valuelen-- > 0 )int ch = *value++;if (ch < rangelo)1 ;else if (ch > rangehi)1 ;double ) (ch - rangelo)) / denom;return num;/* * Do convert_to_scalar ( ) ' s work for any timevalue data type . * * On failure ( e . g . , unsupported typid ) , set * failure to true ; * otherwise , that variable is not changed . static double bool *failure)switch (typid)case TIMESTAMPOID:return DatumGetTimestamp(value);case TIMESTAMPTZOID:return DatumGetTimestampTz(value);case DATEOID:return date2timestamp_no_overflow(DatumGetDateADT(value));case INTERVALOID:/* * Convert the month part of Interval to days using assumed * average month length of 365 . 25 / 12 . 0 days . Not too * accurate , but plenty good enough for our purposes . * * This also works for infinite intervals , which just have all * fields set to INT_MIN / INT_MAX , and so will produce a result * smaller / larger than any finite interval . return interval->time + interval->day * (double ) USECS_PER_DAY +double ) MONTHS_PER_YEAR) * USECS_PER_DAY);case TIMEOID:return DatumGetTimeADT(value);case TIMETZOID:/* use GMT-equivalent time */ return (double ) (timetz->time + (timetz->zone * 1000000 .0 ));true ;return 0 ;/* * get_restriction_variable * Examine the args of a restriction clause to see if it ' s of the * form ( variable op pseudoconstant ) or ( pseudoconstant op variable ) , * where " variable " could be either a Var or an expression in vars of a * single relation . If so , extract information about the variable , * and also indicate which side it was on and the other argument . * * Inputs : * root : the planner info * args : clause argument list * varRelid : see specs for restriction selectivity functions * * Outputs : ( these are valid only if true is returned ) * * vardata : gets information about variable ( see examine_variable ) * * other : gets other clause argument , aggressively reduced to a constant * * varonleft : set true if variable is on the left , false if on the right * * Returns true if a variable is identified , otherwise false . * * Note : if there are Vars on both sides of the clause , we must fail , because * callers are expecting that the other side will act like a pseudoconstant . bool int varRelid,bool *varonleft)/* Fail if not a binary opclause (probably shouldn't happen) */ if (list_length(args) != 2 )return false ;/* * Examine both sides . Note that when varRelid is nonzero , Vars of other * relations will be treated as pseudoconstants . /* * If one side is a variable and the other not , we win . if (vardata->rel && rdata.rel == NULL)true ;/* Assume we need no ReleaseVariableStats(rdata) here */ return true ;if (vardata->rel == NULL && rdata.rel)false ;/* Assume we need no ReleaseVariableStats(*vardata) here */ return true ;/* Oops, clause has wrong structure (probably var op var) */ return false ;/* * get_join_variables * Apply examine_variable ( ) to each side of a join clause . * Also , attempt to identify whether the join clause has the same * or reversed sense compared to the SpecialJoinInfo . * * We consider the join clause " normal " if it is " lhs_var OP rhs_var " , * or " reversed " if it is " rhs_var OP lhs_var " . In complicated cases * where we can ' t tell for sure , we default to assuming it ' s normal . void bool *join_is_reversed)if (list_length(args) != 2 )"join operator should take two arguments" );0 , vardata1);0 , vardata2);if (vardata1->rel &&true ; /* var1 is on RHS */ else if (vardata2->rel &&true ; /* var2 is on LHS */ else false ;/* statext_expressions_load copies the tuple, so just pfree it. */ static void /* * examine_variable * Try to look up statistical data about an expression . * Fill in a VariableStatData struct to describe the expression . * * Inputs : * root : the planner info * node : the expression tree to examine * varRelid : see specs for restriction selectivity functions * * Outputs : * vardata is filled as follows : * var : the input expression ( with any phvs or binary relabeling stripped , * if it is or contains a variable ; but otherwise unchanged ) * rel : RelOptInfo for relation containing variable ; NULL if expression * contains no Vars ( NOTE this could point to a RelOptInfo of a * subquery , not one in the current query ) . * statsTuple : the pg_statistic entry for the variable , if one exists ; * otherwise NULL . * freefunc : pointer to a function to release statsTuple with . * vartype : exposed type of the expression ; this should always match * the declared input type of the operator we are estimating for . * atttype , atttypmod : actual type / typmod of the " var " expression . This is * commonly the same as the exposed type of the variable argument , * but can be different in binary - compatible - type cases . * isunique : true if we were able to match the var to a unique index , a * single - column DISTINCT or GROUP - BY clause , implying its values are * unique for this query . ( Caution : this should be trusted for * statistical purposes only , since we do not check indimmediate nor * verify that the exact same definition of equality applies . ) * acl_ok : true if current user has permission to read all table rows from * the column ( s ) underlying the pg_statistic entry . This is consulted by * statistic_proc_security_check ( ) . * * Caller is responsible for doing ReleaseVariableStats ( ) before exiting . void int varRelid,/* Make sure we don't return dangling pointers in vardata */ 0 , sizeof (VariableStatData));/* Save the exposed type of the expression */ /* * PlaceHolderVars are transparent for the purpose of statistics lookup ; * they do not alter the value distribution of the underlying expression . * However , they can obscure the structure , preventing us from recognizing * matches to base columns , index expressions , or extended statistics . So * strip them out first . /* * Look inside any binary - compatible relabeling . We need to handle nested * RelabelType nodes here , because the prior stripping of PlaceHolderVars * may have brought separate RelabelTypes into adjacency . while (IsA(basenode, RelabelType))/* Fast path for a simple Var */ if (IsA(basenode, Var) &&0 || varRelid == ((Var *) basenode)->varno))/* Set up result fields other than the stats tuple */ /* return Var without phvs or relabeling */ /* Try to locate some stats */ return ;/* * Okay , it ' s a more complicated expression . Determine variable * membership . Note that when varRelid isn ' t zero , only vars of that * relation are considered " real " vars . if (bms_is_empty(basevarnos))/* No Vars at all ... must be pseudo-constant clause */ else int relid;/* Check if the expression is in vars of a single base relation */ if (bms_get_singleton_member(basevarnos, &relid))if (varRelid == 0 || varRelid == relid)/* strip any phvs or relabeling */ /* else treat it as a constant */ else /* varnos has multiple relids */ if (varRelid == 0 )/* treat it as a variable of a join relation */ /* strip any phvs or relabeling */ else if (bms_is_member(varRelid, varnos))/* ignore the vars belonging to other relations */ /* strip any phvs or relabeling */ /* note: no point in expressional-index search here */ /* else treat it as a constant */ if (onerel)/* * We have an expression in vars of a single relation . Try to match * it to expressional index columns , in hopes of finding some * statistics . * * Note that we consider all index columns including INCLUDE columns , * since there could be stats for such columns . But the test for * uniqueness needs to be warier . * * XXX it ' s conceivable that there are multiple matches with different * index opfamilies ; if so , we need to pick one that matches the * operator we are estimating for . FIXME later . /* * The nullingrels bits within the expression could prevent us from * matching it to expressional index columns or to the expressions in * extended statistics . So strip them out first . if (bms_overlap(varnos, root->outer_join_rels))int pos;if (indexpr_item == NULL)continue ; /* no expressions here... */ for (pos = 0 ; pos < index->ncolumns; pos++)if (index->indexkeys[pos] == 0 )if (indexpr_item == NULL)"too few entries in indexprs list" );if (indexkey && IsA(indexkey, RelabelType))if (equal(node, indexkey))/* * Found a match . . . is it a unique index ? Tests here * should match has_unique_index ( ) . if (index->unique &&1 &&0 &&true ;/* * Has it got stats ? We only consider stats for * non - partial indexes , since partial indexes probably * don ' t reflect whole - relation statistics ; the above * check for uniqueness is the only info we take from * a partial index . * * An index stats hook , however , must make its own * decisions about what to do with partial indexes . if (get_index_stats_hook &&1 , vardata))/* * The hook took control of acquiring a stats * tuple . If it did supply a tuple , it ' d better * have supplied a freefunc . if (HeapTupleIsValid(vardata->statsTuple) &&"no function provided to release variable stats with" );else if (index->indpred == NIL)1 ),false ));if (HeapTupleIsValid(vardata->statsTuple))/* * Test if user has permission to access all * rows from the index ' s table . * * For simplicity , we insist on the whole * table being selectable , rather than trying * to identify which column ( s ) the index * depends on . * * Note that for an inheritance child , * permissions are checked on the inheritance * root parent , and whole - table select * privilege on the parent doesn ' t quite * guarantee that the user could read all * columns of the child . But in practice it ' s * unlikely that any interesting security * violation could result from allowing access * to the expression index ' s stats , so we * allow it anyway . See similar code in * examine_simple_variable ( ) for additional * comments . else /* suppress leakproofness checks later */ true ;if (vardata->statsTuple)break ;if (vardata->statsTuple)break ;/* * Search extended statistics for one with a matching expression . * There might be multiple ones , so just grab the first one . In the * future , we might consider the statistics target ( and pick the most * accurate statistics ) and maybe some other parameters . int pos;/* * Stop once we ' ve found statistics for the expression ( either * from extended stats , or for an index in the preceding loop ) . if (vardata->statsTuple)break ;/* skip stats without per-expression stats */ if (info->kind != STATS_EXT_EXPRESSIONS)continue ;/* skip stats with mismatching stxdinherit value */ if (info->inherit != rte->inh)continue ;0 ;/* strip RelabelType before comparing it */ if (expr && IsA(expr, RelabelType))/* found a match, see if we can extract pg_statistic row */ if (equal(node, expr))/* * XXX Not sure if we should cache the tuple somewhere . * Now we just create a new copy every time . /* Nothing to release if no data found */ if (vardata->statsTuple != NULL)/* * Test if user has permission to access all rows from the * table . * * For simplicity , we insist on the whole table being * selectable , rather than trying to identify which * column ( s ) the statistics object depends on . * * Note that for an inheritance child , permissions are * checked on the inheritance root parent , and whole - table * select privilege on the parent doesn ' t quite guarantee * that the user could read all columns of the child . But * in practice it ' s unlikely that any interesting security * violation could result from allowing access to the * expression stats , so we allow it anyway . See similar * code in examine_simple_variable ( ) for additional * comments . break ;/* * strip_all_phvs_deep * Deeply strip all PlaceHolderVars in an expression . * As a performance optimization , we first use a lightweight walker to check * for the presence of any PlaceHolderVars . The expensive mutator is invoked * only if a PlaceHolderVar is found , avoiding unnecessary memory allocation * and tree copying in the common case where no PlaceHolderVars are present . static Node */* If there are no PHVs anywhere, we needn't work hard */ if (root->glob->lastPHId == 0 )return node;if (!contain_placeholder_walker(node, NULL))return node;return strip_all_phvs_mutator(node, NULL);/* * contain_placeholder_walker * Lightweight walker to check if an expression contains any * PlaceHolderVars static bool void *context)if (node == NULL)return false ;if (IsA(node, PlaceHolderVar))return true ;return expression_tree_walker(node, contain_placeholder_walker, context);/* * strip_all_phvs_mutator * Mutator to deeply strip all PlaceHolderVars static Node *void *context)if (node == NULL)return NULL;if (IsA(node, PlaceHolderVar))/* Strip it and recurse into its contained expression */ return strip_all_phvs_mutator((Node *) phv->phexpr, context);return expression_tree_mutator(node, strip_all_phvs_mutator, context);/* * examine_simple_variable * Handle a simple Var for examine_variable * * This is split out as a subroutine so that we can recurse to deal with * Vars referencing subqueries ( either sub - SELECT - in - FROM or CTE style ) . * * We already filled in all the fields of * vardata except for the stats tuple . static void if (get_relation_stats_hook &&/* * The hook took control of acquiring a stats tuple . If it did supply * a tuple , it ' d better have supplied a freefunc . if (HeapTupleIsValid(vardata->statsTuple) &&"no function provided to release variable stats with" );else if (rte->rtekind == RTE_RELATION)/* * Plain table or parent of an inheritance appendrel , so look up the * column in pg_statistic if (HeapTupleIsValid(vardata->statsTuple))/* * Test if user has permission to read all rows from this column . * * This requires that the user has the appropriate SELECT * privileges and that there are no securityQuals from security * barrier views or RLS policies . If that ' s not the case , then we * only permit leakproof functions to be passed pg_statistic data * in vardata , otherwise the functions might reveal data that the * user doesn ' t have permission to see - - - see * statistic_proc_security_check ( ) . else /* suppress any possible leakproofness checks later */ true ;else if ((rte->rtekind == RTE_SUBQUERY && !rte->inh) ||/* * Plain subquery ( not one that was converted to an appendrel ) or * non - recursive CTE . In either case , we can try to find out what the * Var refers to within the subquery . We skip this for appendrel and * recursive - CTE cases because any column stats we did find would * likely not be very relevant . /* * Punt if it ' s a whole - row var rather than a plain column reference . if (var->varattno == InvalidAttrNumber)return ;/* * Otherwise , find the subquery ' s planner subroot . if (rte->rtekind == RTE_SUBQUERY)/* * Fetch RelOptInfo for subquery . Note that we don ' t change the * rel returned in vardata , since caller expects it to be a rel of * the caller ' s query level . Because we might already be * recursing , we can ' t use that rel pointer either , but have to * look up the Var ' s rel afresh . else /* CTE case is more difficult */ int ndx;int plan_id;/* * Find the referenced CTE , and locate the subroot previously made * for it . while (levelsup-- > 0 )if (!cteroot) /* shouldn't happen */ "bad levelsup for CTE \" %s\"" , rte->ctename);/* * Note : cte_plan_ids can be shorter than cteList , if we are still * working on planning the CTEs ( ie , this is a side - reference from * another CTE ) . So we mustn ' t use forboth here . 0 ;if (strcmp(cte->ctename, rte->ctename) == 0 )break ;if (lc == NULL) /* shouldn't happen */ "could not find CTE \" %s\"" , rte->ctename);if (ndx >= list_length(cteroot->cte_plan_ids))"could not find plan for CTE \" %s\"" , rte->ctename);if (plan_id <= 0 )"no plan was made for CTE \" %s\"" , rte->ctename);1 );/* If the subquery hasn't been planned yet, we have to punt */ if (subroot == NULL)return ;/* * We must use the subquery parsetree as mangled by the planner , not * the raw version from the RTE , because we need a Var that will refer * to the subroot ' s live RelOptInfos . For instance , if any subquery * pullup happened during planning , Vars in the targetlist might have * gotten replaced , and we need to see the replacement expressions . /* * Punt if subquery uses set operations or grouping sets , as these * will mash underlying columns ' stats beyond recognition . ( Set ops * are particularly nasty ; if we forged ahead , we would return stats * relevant to only the leftmost subselect . . . ) DISTINCT is also * problematic , but we check that later because there is a possibility * of learning something even with it . if (subquery->setOperations ||return ;/* Get the subquery output expression referenced by the upper Var */ if (subquery->returningList)else if (ste == NULL || ste->resjunk)"subquery %s does not have attribute %d" ,/* * If subquery uses DISTINCT , we can ' t make use of any stats for the * variable . . . but , if it ' s the only DISTINCT column , we are entitled * to consider it unique . We do the test this way so that it works * for cases involving DISTINCT ON . if (subquery->distinctClause)if (list_length(subquery->distinctClause) == 1 &&true ;/* cannot go further */ return ;/* The same idea as with DISTINCT clause works for a GROUP-BY too */ if (subquery->groupClause)if (list_length(subquery->groupClause) == 1 &&true ;/* cannot go further */ return ;/* * If the sub - query originated from a view with the security_barrier * attribute , we must not look at the variable ' s statistics , though it * seems all right to notice the existence of a DISTINCT clause . So * stop here . * * This is probably a harsher restriction than necessary ; it ' s * certainly OK for the selectivity estimator ( which is a C function , * and therefore omnipotent anyway ) to look at the statistics . But * many selectivity estimators will happily * invoke the operator * function * to try to work out a good estimate - and that ' s not OK . * So for now , don ' t dig down for stats . if (rte->security_barrier)return ;/* Can only handle a simple Var of subquery's query level */ if (var && IsA(var, Var) &&0 )/* * OK , recurse into the subquery . Note that the original setting * of vardata - > isunique ( which will surely be false ) is left * unchanged in this situation . That ' s what we want , since even * if the underlying column is unique , the subquery may have * joined to other tables in a way that creates duplicates . else /* * Otherwise , the Var comes from a FUNCTION or VALUES RTE . ( We won ' t * see RTE_JOIN here because join alias Vars have already been * flattened . ) There ' s not much we can do with function outputs , but * maybe someday try to be smarter about VALUES . /* * all_rows_selectable * Test whether the user has permission to select all rows from a given * relation . * * Inputs : * root : the planner info * varno : the index of the relation ( assumed to be an RTE_RELATION ) * varattnos : the attributes for which permission is required , or NULL if * whole - table access is required * * Returns true if the user has the required select permissions , and there are * no securityQuals from security barrier views or RLS policies . * * Note that if the relation is an inheritance child relation , securityQuals * and access permissions are checked against the inheritance root parent ( the * relation actually mentioned in the query ) - - - see the comments in * expand_single_inheritance_child ( ) for an explanation of why it has to be * done this way . * * If varattnos is non - NULL , its attribute numbers should be offset by * FirstLowInvalidHeapAttributeNumber so that system attributes can be * checked . If varattnos is NULL , only table - level SELECT privileges are * checked , not any column - level privileges . * * Note : if the relation is accessed via a view , this function actually tests * whether the view owner has permission to select from the relation . To * ensure that the current user has permission , it is also necessary to check * that the current user has permission to select from the view , which we do * at planner - startup - - - see subquery_planner ( ) . * * This is exported so that other estimation functions can use it . bool int varattno;/* * Determine the user ID to use for privilege checks ( either the current * user or the view owner , if we ' re accessing the table via a view ) . * * Normally the relation will have an associated RelOptInfo from which we * can find the userid , but it might not if it ' s a RETURNING Var for an * INSERT target relation . In that case use the RTEPermissionInfo * associated with the RTE . * * If we navigate up to a parent relation , we keep using the same userid , * since it ' s the same in all relations of a given inheritance tree . if (rel)else if (!OidIsValid(userid))/* * Permissions and securityQuals must be checked on the table actually * mentioned in the query , so if this is an inheritance child , navigate up * to the inheritance root parent . If the user can read the whole table * or the required columns there , then they can read from the child table * too . For per - column checks , we must find out which of the root * parent ' s attributes the child relation ' s attributes correspond to . if (root->append_rel_array != NULL)/* * Partitions are mapped to their immediate parent , not the root * parent , so must be ready to walk up multiple AppendRelInfos . But * stop if we hit a parent that is not RTE_RELATION - - - that ' s a * flattened UNION ALL subquery , not an inheritance parent . while (appinfo &&/* * For each child attribute , find the corresponding parent * attribute . In rare cases , the attribute may be local to the * child table , in which case , we ' ve got to live with having no * access to this column . 1 ;while ((varattno = bms_next_member(varattnos, varattno)) >= 0 )if (attno == InvalidAttrNumber)/* * Whole - row reference , so must map each column of the * child to the parent table . for (attno = 1 ; attno <= appinfo->num_child_cols; attno++)1 ];if (parent_attno == 0 )return false ; /* attr is local to child */ else if (attno < 0 )/* System attnos are the same in all tables */ else if (attno > appinfo->num_child_cols)return false ; /* safety check */ 1 ];if (parent_attno == 0 )return false ; /* attr is local to child */ /* If the parent is itself a child, continue up */ /* Perform the access check on this parent rel */ /* * For all rows to be accessible , there must be no securityQuals from * security barrier views or RLS policies . if (rte->securityQuals != NIL)return false ;/* * Test for table - level SELECT privilege . * * If varattnos is non - NULL , this is sufficient to give access to all * requested attributes , even for a child table , since we have verified * that all required child columns have matching parent columns . * * If varattnos is NULL ( whole - table access requested ) , this doesn ' t * necessarily guarantee that the user can read all columns of a child * table , but we allow it anyway ( see comments in examine_variable ( ) ) and * don ' t bother checking any column privileges . if (pg_class_aclcheck(rte->relid, userid, ACL_SELECT) == ACLCHECK_OK)return true ;if (varattnos == NULL)return false ; /* whole-table access requested */ /* * Don ' t have table - level SELECT privilege , so check per - column * privileges . 1 ;while ((varattno = bms_next_member(varattnos, varattno)) >= 0 )if (attno == InvalidAttrNumber)/* Whole-row reference, so must have access to all columns */ if (pg_attribute_aclcheck_all(rte->relid, userid, ACL_SELECT,return false ;else if (pg_attribute_aclcheck(rte->relid, attno, userid,return false ;/* If we reach here, have all required column privileges */ return true ;/* * examine_indexcol_variable * Try to look up statistical data about an index column / expression . * Fill in a VariableStatData struct to describe the column . * * Inputs : * root : the planner info * index : the index whose column we ' re interested in * indexcol : 0 - based index column number ( subscripts index - > indexkeys [ ] ) * * Outputs : * vardata is filled as follows : * var : the input expression ( with any binary relabeling stripped , if * it is or contains a variable ; but otherwise the type is preserved ) * rel : RelOptInfo for table relation containing variable . * statsTuple : the pg_statistic entry for the variable , if one exists ; * otherwise NULL . * freefunc : pointer to a function to release statsTuple with . * * Caller is responsible for doing ReleaseVariableStats ( ) before exiting . static void int indexcol, VariableStatData *vardata)if (index->indexkeys[indexcol] != 0 )/* Simple variable --- look to stats for the underlying table */ if (get_relation_stats_hook &&/* * The hook took control of acquiring a stats tuple . If it did * supply a tuple , it ' d better have supplied a freefunc . if (HeapTupleIsValid(vardata->statsTuple) &&"no function provided to release variable stats with" );else else /* Expression --- maybe there are stats for the index itself */ 1 ;if (get_index_stats_hook &&/* * The hook took control of acquiring a stats tuple . If it did * supply a tuple , it ' d better have supplied a freefunc . if (HeapTupleIsValid(vardata->statsTuple) &&"no function provided to release variable stats with" );else false ));/* * Check whether it is permitted to call func_oid passing some of the * pg_statistic data in vardata . We allow this if either of the following * conditions is met : ( 1 ) the user has SELECT privileges on the table or * column underlying the pg_statistic data and there are no securityQuals from * security barrier views or RLS policies , or ( 2 ) the function is marked * leakproof . bool if (vardata->acl_ok)return true ; /* have SELECT privs and no securityQuals */ if (!OidIsValid(func_oid))return false ;if (get_func_leakproof(func_oid))return true ;"not using statistics because function \" %s\" is not leakproof" ,return false ;/* * get_variable_numdistinct * Estimate the number of distinct values of a variable . * * vardata : results of examine_variable * * isdefault : set to true if the result is a default rather than based on * anything meaningful . * * NB : be careful to produce a positive integral result , since callers may * compare the result to exact integer counts , or might divide by it . double bool *isdefault)double stadistinct;double stanullfrac = 0 .0 ;double ntuples;false ;/* * Determine the stadistinct value to use . There are cases where we can * get an estimate even without a pg_statistic entry , or can get a better * value than is in pg_statistic . Grab stanullfrac too if we can find it * ( otherwise , assume no nulls , for lack of any better idea ) . if (HeapTupleIsValid(vardata->statsTuple))/* Use the pg_statistic entry */ else if (vardata->vartype == BOOLOID)/* * Special - case boolean columns : presumably , two distinct values . * * Are there any other datatypes we should wire in special estimates * for ? 2 .0 ;else if (vardata->rel && vardata->rel->rtekind == RTE_VALUES)/* * If the Var represents a column of a VALUES RTE , assume it ' s unique . * This could of course be very wrong , but it should tend to be true * in well - written queries . We could consider examining the VALUES ' * contents to get some real statistics ; but that only works if the * entries are all constants , and it would be pretty expensive anyway . 1 .0 ; /* unique (and all non null) */ else /* * We don ' t keep statistics for system columns , but in some cases we * can infer distinctness anyway . if (vardata->var && IsA(vardata->var, Var))switch (((Var *) vardata->var)->varattno)case SelfItemPointerAttributeNumber:1 .0 ; /* unique (and all non null) */ break ;case TableOidAttributeNumber:1 .0 ; /* only 1 value */ break ;default :0 .0 ; /* means "unknown" */ break ;else 0 .0 ; /* means "unknown" */ /* * XXX consider using estimate_num_groups on expressions ? /* * If there is a unique index , DISTINCT or GROUP - BY clause for the * variable , assume it is unique no matter what pg_statistic says ; the * statistics could be out of date , or we might have found a partial * unique index that proves the var is unique for this query . However , * we ' d better still believe the null - fraction statistic . if (vardata->isunique)1 .0 * (1 .0 - stanullfrac);/* * If we had an absolute estimate , use that . if (stadistinct > 0 .0 )return clamp_row_est(stadistinct);/* * Otherwise we need to get the relation size ; punt if not available . if (vardata->rel == NULL)true ;return DEFAULT_NUM_DISTINCT;if (ntuples <= 0 .0 )true ;return DEFAULT_NUM_DISTINCT;/* * If we had a relative estimate , use that . if (stadistinct < 0 .0 )return clamp_row_est(-stadistinct * ntuples);/* * With no data , estimate ndistinct = ntuples if the table is small , else * use default . We use DEFAULT_NUM_DISTINCT as the cutoff for " small " so * that the behavior isn ' t discontinuous . if (ntuples < DEFAULT_NUM_DISTINCT)return clamp_row_est(ntuples);true ;return DEFAULT_NUM_DISTINCT;/* * get_variable_range * Estimate the minimum and maximum value of the specified variable . * If successful , store values in * min and * max , and return true . * If no data available , return false . * * sortop is the " < " comparison operator to use . This should generally * be " < " not " > " , as only the former is likely to be found in pg_statistic . * The collation must be specified too . static bool 0 ;0 ;bool have_data = false ;bool typByVal;/* * XXX It ' s very tempting to try to use the actual column min and max , if * we can get them relatively - cheaply with an index probe . However , since * this function is called many times during join planning , that could * have unpleasant effects on planning speed . Need more investigation * before enabling this . #ifdef NOT_USEDif (get_actual_variable_range(root, vardata, sortop, collation, min, max))return true ;#endif if (!HeapTupleIsValid(vardata->statsTuple))/* no stats available, so default result */ return false ;/* * If we can ' t apply the sortop to the stats data , just fail . In * principle , if there ' s a histogram and no MCVs , we could return the * histogram endpoints without ever applying the sortop . . . but it ' s * probably not worth trying , because whatever the caller wants to do with * the endpoints would likely fail the security check too . if (!statistic_proc_security_check(vardata,return false ;/* mark this as not looked up yet */ /* * If there is a histogram with the ordering we want , grab the first and * last values . if (get_attstatsslot(&sslot, vardata->statsTuple,if (sslot.stacoll == collation && sslot.nvalues > 0 )0 ], typByVal, typLen);1 ], typByVal, typLen);true ;/* * Otherwise , if there is a histogram with some other ordering , scan it * and get the min and max values according to the ordering we want . This * of course may not find values that are really extremal according to our * ordering , but it beats ignoring available data . if (!have_data &&/* * If we have most - common - values info , look for extreme MCVs . This is * needed even if we also have a histogram , since the histogram excludes * the MCVs . However , if we * only * have MCVs and no histogram , we should * be pretty wary of deciding that that is a full representation of the * data . Proceed only if the MCVs represent the whole table ( to within * roundoff error ) . if (get_attstatsslot(&sslot, vardata->statsTuple,bool use_mcvs = have_data;if (!have_data)double sumcommon = 0 .0 ;double nullfrac;int i;for (i = 0 ; i < sslot.nnumbers; i++)if (sumcommon + nullfrac > 0 .99999 )true ;if (use_mcvs)return have_data;/* * get_stats_slot_range : scan sslot for min / max values * * Subroutine for get_variable_range : update min / max / have_data according * to what we find in the statistics array . static void bool typByVal,bool *p_have_data)bool have_data = *p_have_data;bool found_tmin = false ;bool found_tmax = false ;/* Look up the comparison function, if we didn't already do so */ if (opproc->fn_oid != opfuncoid)/* Scan all the slot's values */ for (int i = 0 ; i < sslot->nvalues; i++)if (!have_data)true ;true ;continue ;if (DatumGetBool(FunctionCall2Coll(opproc,true ;if (DatumGetBool(FunctionCall2Coll(opproc,true ;/* * Copy the slot ' s values , if we found new extreme values . if (found_tmin)if (found_tmax)/* * get_actual_variable_range * Attempt to identify the current * actual * minimum and / or maximum * of the specified variable , by looking for a suitable btree index * and fetching its low and / or high values . * If successful , store values in * min and * max , and return true . * ( Either pointer can be NULL if that endpoint isn ' t needed . ) * If unsuccessful , return false . * * sortop is the " < " comparison operator to use . * collation is the required collation . static bool bool have_data = false ;/* No hope if no relation or it doesn't have indexes */ if (rel == NULL || rel->indexlist == NIL)return false ;/* If it has indexes it must be a plain relation */ /* ignore partitioned tables. Any indexes here are not real indexes */ if (rte->relkind == RELKIND_PARTITIONED_TABLE)return false ;/* Search through the indexes to see if any match our problem */ /* Ignore non-ordering indexes */ if (index->sortopfamily == NULL)continue ;/* * Ignore partial indexes - - - we only want stats that cover the entire * relation . if (index->indpred != NIL)continue ;/* * The index list might include hypothetical indexes inserted by a * get_relation_info hook - - - don ' t try to access them . if (index->hypothetical)continue ;/* * get_actual_variable_endpoint uses the index - only - scan machinery , so * ignore indexes that can ' t use it on their first column . if (!index->canreturn[0 ])continue ;/* * The first index column must match the desired variable , sortop , and * collation - - - but we can use a descending - order index . if (collation != index->indexcollations[0 ])continue ; /* test first 'cause it's cheapest */ if (!match_index_to_operand(vardata->var, 0 , index))continue ;0 ]);switch (IndexAmTranslateStrategy(strategy, index->relam, index->sortopfamily[0 ], true ))case COMPARE_LT:if (index->reverse_sort[0 ])else break ;case COMPARE_GT:if (index->reverse_sort[0 ])else break ;default :/* index doesn't match the sortop */ continue ;/* * Found a suitable index to extract data from . Set up some data that * can be used by both invocations of get_actual_variable_endpoint . bool typByVal;1 ];/* Make sure any cruft gets recycled when we're done */ "get_actual_variable_range workspace" ,/* * Open the table and index so we can read from them . We should * already have some type of lock on each . /* build some stuff needed for indexscan execution */ /* set up an IS NOT NULL scan key so that we ignore nulls */ 0 ],1 , /* index col to scan */ /* no strategy */ /* no strategy subtype */ /* no collation */ /* no reg proc for this */ 0 ); /* constant */ /* If min is requested ... */ if (min)else /* If min not requested, still want to fetch max */ true ;/* If max is requested, and we didn't already fail ... */ if (max && have_data)/* scan in the opposite direction; all else is the same */ /* Clean everything up */ /* And we're done */ break ;return have_data;/* * Get one endpoint datum ( min or max depending on indexscandir ) from the * specified index . Return true if successful , false if not . * On success , endpoint value is stored to * endpointDatum ( and copied into * outercontext ) . * * scankeys is a 1 - element scankey array set up to reject nulls . * typLen / typByVal describe the datatype of the index ' s first column . * tableslot is a slot suitable to hold table tuples , in case we need * to probe the heap . * ( We could compute these values locally , but that would mean computing them * twice when get_actual_variable_range needs both the min and the max . ) * * Failure occurs either when the index is empty , or we decide that it ' s * taking too long to find a suitable tuple . static bool bool typByVal,bool have_data = false ;int n_visited_heap_pages = 0 ;bool isnull[INDEX_MAX_KEYS];/* * We use the index - only - scan machinery for this . With mostly - static * tables that ' s a win because it avoids a heap visit . It ' s also a win * for dynamic data , but the reason is less obvious ; read on for details . * * In principle , we should scan the index with our current active * snapshot , which is the best approximation we ' ve got to what the query * will see when executed . But that won ' t be exact if a new snap is taken * before running the query , and it can be very expensive if a lot of * recently - dead or uncommitted rows exist at the beginning or end of the * index ( because we ' ll laboriously fetch each one and reject it ) . * Instead , we use SnapshotNonVacuumable . That will accept recently - dead * and uncommitted rows as well as normal visible rows . On the other * hand , it will reject known - dead rows , and thus not give a bogus answer * when the extreme value has been deleted ( unless the deletion was quite * recent ) ; that case motivates not using SnapshotAny here . * * A crucial point here is that SnapshotNonVacuumable , with * GlobalVisTestFor ( heapRel ) as horizon , yields the inverse of the * condition that the indexscan will use to decide that index entries are * killable ( see heap_hot_search_buffer ( ) ) . Therefore , if the snapshot * rejects a tuple ( or more precisely , all tuples of a HOT chain ) and we * have to continue scanning past it , we know that the indexscan will mark * that index entry killed . That means that the next * get_actual_variable_endpoint ( ) call will not have to re - consider that * index entry . In this way we avoid repetitive work when this function * is used a lot during planning . * * But using SnapshotNonVacuumable creates a hazard of its own . In a * recently - created index , some index entries may point at " broken " HOT * chains in which not all the tuple versions contain data matching the * index entry . The live tuple version ( s ) certainly do match the index , * but SnapshotNonVacuumable can accept recently - dead tuple versions that * don ' t match . Hence , if we took data from the selected heap tuple , we * might get a bogus answer that ' s not close to the index extremal value , * or could even be NULL . We avoid this hazard because we take the data * from the index entry not the heap . * * Despite all this care , there are situations where we might find many * non - visible tuples near the end of the index . We don ' t want to expend * a huge amount of time here , so we give up once we ' ve read too many heap * pages . When we fail for that reason , the caller will end up using * whatever extremal value is recorded in pg_statistic . 1 , 0 );/* Set it up for index-only scan */ true ;1 , NULL, 0 );/* Fetch first/next tuple in specified direction */ while ((tid = index_getnext_tid(index_scan, indexscandir)) != NULL)if (!VM_ALL_VISIBLE(heapRel,/* Rats, we have to visit the heap to check visibility */ if (!index_fetch_heap(index_scan, tableslot))/* * No visible tuple for this index entry , so we need to * advance to the next entry . Before doing so , count heap * page fetches and give up if we ' ve done too many . * * We don ' t charge a page fetch if this is the same heap page * as the previous tuple . This is on the conservative side , * since other recently - accessed pages are probably still in * buffers too ; but it ' s good enough for this heuristic . #define VISITED_PAGES_LIMIT 100 if (block != last_heap_block)if (n_visited_heap_pages > VISITED_PAGES_LIMIT)break ;continue ; /* no visible tuple, try next index entry */ /* We don't actually need the heap tuple for anything */ /* * We don ' t care whether there ' s more than one visible tuple in * the HOT chain ; if any are visible , that ' s good enough . /* * We expect that the index will return data in IndexTuple not * HeapTuple format . if (!index_scan->xs_itup)"no data returned for index-only scan" );/* * We do not yet support recheck here . if (index_scan->xs_recheck)break ;/* OK to deconstruct the index tuple */ /* Shouldn't have got a null, but be careful */ if (isnull[0 ])"found unexpected null value in index \" %s\"" ,/* Copy the index column value out to caller's context */ 0 ], typByVal, typLen);true ;break ;if (vmbuffer != InvalidBuffer)return have_data;/* * find_join_input_rel * Look up the input relation for a join . * * We assume that the input relation ' s RelOptInfo must have been constructed * already . static RelOptInfo *if (!bms_is_empty(relids))int relid;if (bms_get_singleton_member(relids, &relid))else if (rel == NULL)"could not find RelOptInfo for given relids" );return rel;/*------------------------------------------------------------------------- * * Index cost estimation functions * * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - /* * Extract the actual indexquals ( as RestrictInfos ) from an IndexClause list return result;/* * Compute the total evaluation cost of the comparison operands in a list * of index qual expressions . Since we know these will be evaluated just * once per scan , there ' s no need to distinguish startup from per - row cost . * * This can be used either on the result of get_quals_from_indexclauses ( ) , * or directly on an indexorderbys list . In both cases , we expect that the * index key expression is on the left side of binary clauses . 0 ;/* * Index quals will have RestrictInfos , indexorderbys won ' t . Look * through RestrictInfo if present . if (IsA(clause, RestrictInfo))if (IsA(clause, OpExpr))else if (IsA(clause, RowCompareExpr))else if (IsA(clause, ScalarArrayOpExpr))else if (IsA(clause, NullTest))else "unsupported indexqual type: %d" ,int ) nodeTag(clause));/* keep compiler quiet */ return qual_arg_cost;void double loop_count,double indexCorrelation;double numIndexPages;double numIndexTuples;double spc_random_page_cost;double num_sa_scans;double num_outer_scans;double num_scans;double qual_op_cost;double qual_arg_cost;/* * If the index is partial , AND the index predicate with the explicitly * given indexquals to produce a more accurate idea of the index * selectivity . /* * If caller didn ' t give us an estimate for ScalarArrayOpExpr index scans , * just assume that the number of index descents is the number of distinct * combinations of array elements from all of the scan ' s SAOP clauses . if (num_sa_scans < 1 )1 ;if (IsA(rinfo->clause, ScalarArrayOpExpr))double alength = estimate_array_length(root, lsecond(saop->args));if (alength > 1 )/* Estimate the fraction of main-table tuples that will be visited */ /* * If caller didn ' t give us an estimate , estimate the number of index * tuples that will be visited . We do it in this rather peculiar - looking * way in order to get the right answer for partial indexes . if (numIndexTuples <= 0 .0 )/* * The above calculation counts all the tuples visited across all * scans induced by ScalarArrayOpExpr nodes . We want to consider the * average per - indexscan number , so adjust . This is a handy place to * round to integer , too . ( If caller supplied tuple estimate , it ' s * responsible for handling these considerations . ) /* * We can bound the number of tuples by the index size in any case . Also , * always estimate at least one tuple is touched , even when * indexSelectivity estimate is tiny . if (numIndexTuples > index->tuples)if (numIndexTuples < 1 .0 )1 .0 ;/* * Estimate the number of index pages that will be retrieved . * * We use the simplistic method of taking a pro - rata fraction of the total * number of index pages . In effect , this counts only leaf pages and not * any overhead such as index metapage or upper tree levels . * * In practice access to upper index levels is often nearly free because * those tend to stay in cache under load ; moreover , the cost involved is * highly dependent on index type . We therefore ignore such costs here * and leave it to the caller to add a suitable charge if needed . if (index->pages > 1 && index->tuples > 1 )else 1 .0 ;/* fetch estimated page cost for tablespace containing index */ /* * Now compute the disk access costs . * * The above calculations are all per - index - scan . However , if we are in a * nestloop inner scan , we can expect the scan to be repeated ( with * different search keys ) for each row of the outer relation . Likewise , * ScalarArrayOpExpr quals result in multiple index scans . This creates * the potential for cache effects to reduce the number of disk page * fetches needed . We want to estimate the average per - scan I / O cost in * the presence of caching . * * We use the Mackert - Lohman formula ( see costsize . c for details ) to * estimate the total number of page fetches that occur . While this * wasn ' t what it was designed for , it seems a reasonable model anyway . * Note that we are counting pages not tuples anymore , so we take N = T = * index size , as if there were one " tuple " per page . if (num_scans > 1 )double pages_fetched;/* total page fetches ignoring cache effects */ /* use Mackert and Lohman formula to adjust for cache effects */ double ) index->pages,/* * Now compute the total disk access cost , and then report a pro - rated * share for each outer scan . ( Don ' t pro - rate for ScalarArrayOpExpr , * since that ' s internal to the indexscan . ) else /* * For a single index scan , we just charge spc_random_page_cost per * page touched . /* * CPU cost : any complex expressions in the indexquals will need to be * evaluated once at the start of the scan to reduce them to runtime keys * to pass to the index AM ( see nodeIndexscan . c ) . We model the per - tuple * CPU costs as cpu_index_tuple_cost plus one cpu_operator_cost per * indexqual operator . Because we have numIndexTuples as a per - scan * number , we have to multiply by num_sa_scans to get the correct result * for ScalarArrayOpExpr cases . Similarly add in costs for any index * ORDER BY expressions . * * Note : this neglects the possible costs of rechecking lossy operators . * Detecting that that might be needed seems more expensive than it ' s * worth , though , considering all the other inaccuracies here . . . /* * Generic assumption about index correlation : there isn ' t any . 0 .0 ;/* * Return everything to caller . /* * If the index is partial , add its predicate to the given qual list . * * ANDing the index predicate with the explicitly given indexquals produces * a more accurate idea of the index ' s selectivity . However , we need to be * careful not to insert redundant clauses , because clauselist_selectivity ( ) * is easily fooled into computing a too - low selectivity estimate . Our * approach is to add only the predicate clause ( s ) that cannot be proven to * be implied by the given indexquals . This successfully handles cases such * as a qual " x = 42 " used with a partial index " WHERE x > = 40 AND x < 50 " . * There are many other cases where we won ' t detect redundancy , leading to a * too - low selectivity estimate , which will bias the system in favor of using * partial indexes where possible . That is not necessarily bad though . * * Note that indexQuals contains RestrictInfo nodes while the indpred * does not , so the output list will be mixed . This is OK for both * predicate_implied_by ( ) and clauselist_selectivity ( ) , but might be * problematic if the result were passed to other things . if (index->indpred == NIL)return indexQuals;if (!predicate_implied_by(oneQual, indexQuals, false ))return list_concat(predExtraQuals, indexQuals);/* * Estimate correlation of btree index ' s first column . * * If we can get an estimate of the first column ' s ordering correlation C * from pg_statistic , estimate the index correlation as C for a single - column * index , or C * 0 . 75 for multiple columns . The idea here is that multiple * columns dilute the importance of the first column ' s ordering , but don ' t * negate it entirely . * * We already filled in the stats tuple for * vardata when called . static double double indexCorrelation = 0 ;0 ],0 ],0 ],if (OidIsValid(sortop) &&double varCorrelation;1 );0 ];if (index->reverse_sort[0 ])if (index->nkeycolumns > 1 )0 .75 ;else return indexCorrelation;void double loop_count,double *indexCorrelation,double *indexPages)0 };0 };double numIndexTuples;int indexcol;bool eqQualHere;bool found_row_compare;bool found_array;bool found_is_null_op;bool have_correlation = false ;double num_sa_scans;double correlation = 0 .0 ;/* * For a btree scan , only leading ' = ' quals plus inequality quals for the * immediately next attribute contribute to index selectivity ( these are * the " boundary quals " that determine the starting and stopping points of * the index scan ) . Additional quals can suppress visits to the heap , so * it ' s OK to count them in indexSelectivity , but they should not count * for estimating numIndexTuples . So we must examine the given indexquals * to find out which ones count as boundary quals . We rely on the * knowledge that they are given in index column order . Note that nbtree * preprocessing can add skip arrays that act as leading ' = ' quals in the * absence of ordinary input ' = ' quals , so in practice _ most_ input quals * are able to act as index bound quals ( which we take into account here ) . * * For a RowCompareExpr , we consider only the first column , just as * rowcomparesel ( ) does . * * If there ' s a SAOP or skip array in the quals , we ' ll actually perform up * to N index descents ( not just one ) , but the underlying array key ' s * operator can be considered to act the same as it normally does . 0 ;false ;false ;false ;false ;1 ;if (indexcol < iclause->indexcol)double num_sa_scans_prev_cols = num_sa_scans;/* * Beginning of a new column ' s quals . * * Skip scans use skip arrays , which are ScalarArrayOp style * arrays that generate their elements procedurally and on demand . * Given a multi - column index on " ( a , b ) " , and an SQL WHERE clause * " WHERE b = 42 " , a skip scan will effectively use an indexqual * " WHERE a = ANY ( ' { every col a value } ' ) AND b = 42 " . ( Obviously , * the array on " a " must also return " IS NULL " matches , since our * WHERE clause used no strict operator on " a " ) . * * Here we consider how nbtree will backfill skip arrays for any * index columns that lacked an ' = ' qual . This maintains our * num_sa_scans estimate , and determines if this new column ( the * " iclause - > indexcol " column , not the prior " indexcol " column ) * can have its RestrictInfos / quals added to indexBoundQuals . * * We ' ll need to handle columns that have inequality quals , where * the skip array generates values from a range constrained by the * quals ( not every possible value ) . We ' ve been maintaining * indexSkipQuals to help with this ; it will now contain all of * the prior column ' s quals ( that is , indexcol ' s quals ) when they * might be used for this . if (found_row_compare)/* * Skip arrays can ' t be added after a RowCompare input qual * due to limitations in nbtree break ;if (eqQualHere)/* * Don ' t need to add a skip array for an indexcol that already * has an ' = ' qual / equality constraint false ;while (indexcol < iclause->indexcol)double ndistinct;bool isdefault = true ;true ;/* * A skipped attribute ' s ndistinct forms the basis of our * estimate of the total number of " array elements " used by * its skip array at runtime . Look that up first . if (indexcol == 0 )/* * Get an estimate of the leading column ' s correlation in * passing ( avoids rereading variable stats below ) if (HeapTupleIsValid(vardata.statsTuple))true ;/* * If ndistinct is a default estimate , conservatively assume * that no skipping will happen at runtime if (isdefault)break ; /* done building indexBoundQuals */ /* * Apply indexcol ' s indexSkipQuals selectivity to ndistinct if (indexSkipQuals != NIL)/* * If the index is partial , AND the index predicate with * the index - bound quals to produce a more accurate idea * of the number of distinct values for prior indexcol /* * If ndistinctfrac is selective ( on its own ) , the scan is * unlikely to benefit from repositioning itself using * later quals . Do not allow iclause - > indexcol ' s quals to * be added to indexBoundQuals ( it would increase descent * costs , without lowering numIndexTuples costs by much ) . if (ndistinctfrac < DEFAULT_RANGE_INEQ_SEL)break ; /* done building indexBoundQuals */ /* Adjust ndistinct downward */ 1 );/* * When there ' s no inequality quals , account for the need to * find an initial value by counting - inf / + inf as a value . * * We don ' t charge anything extra for possible next / prior key * index probes , which are sometimes used to find the next * valid skip array element ( ahead of using the located * element value to relocate the scan to the next position * that might contain matching tuples ) . It seems hard to do * better here . Use of the skip support infrastructure often * avoids most next / prior key probes . But even when it can ' t , * there ' s a decent chance that most individual next / prior key * probes will locate a leaf page whose key space overlaps all * of the scan ' s keys ( even the lower - order keys ) - - which * also avoids the need for a separate , extra index descent . * Note also that these probes are much cheaper than non - probe * primitive index scans : they ' re reliably very selective . if (indexSkipQuals == NIL)1 ;/* * Update num_sa_scans estimate by multiplying by ndistinct . * * We make the pessimistic assumption that there is no * naturally occurring cross - column correlation . This is * often wrong , but it seems best to err on the side of not * expecting skipping to be helpful . . . /* * . . . but back out of adding this latest group of 1 or more * skip arrays when num_sa_scans exceeds the total number of * index pages ( revert to num_sa_scans from before indexcol ) . * This causes a sharp discontinuity in cost ( as a function of * the indexcol ' s ndistinct ) , but that is representative of * actual runtime costs . * * Note that skipping is helpful when each primitive index * scan only manages to skip over 1 or 2 irrelevant leaf pages * on average . Skip arrays bring savings in CPU costs due to * the scan not needing to evaluate indexquals against every * tuple , which can greatly exceed any savings in I / O costs . * This test is a test of whether num_sa_scans implies that * we ' re past the point where the ability to skip ceases to * lower the scan ' s costs ( even qual evaluation CPU costs ) . if (index->pages < num_sa_scans)break ; /* done building indexBoundQuals */ /* * Finished considering the need to add skip arrays to bridge an * initial eqQualHere gap between the old and new index columns * ( or there was no initial eqQualHere gap in the first place ) . * * If an initial gap could not be bridged , then new column ' s quals * ( i . e . iclause - > indexcol ' s quals ) won ' t go into indexBoundQuals , * and so won ' t affect our final numIndexTuples estimate . if (indexcol != iclause->indexcol)break ; /* done building indexBoundQuals */ /* Examine each indexqual associated with this index clause */ int op_strategy;if (IsA(clause, OpExpr))else if (IsA(clause, RowCompareExpr))true ;else if (IsA(clause, ScalarArrayOpExpr))double alength = estimate_array_length(root, other_operand);true ;/* estimate SA descents by indexBoundQuals only */ if (alength > 1 )else if (IsA(clause, NullTest))if (nt->nulltesttype == IS_NULL)true ;/* IS NULL is like = for selectivity/skip scan purposes */ true ;else "unsupported indexqual type: %d" ,int ) nodeTag(clause));/* check for equality operator */ if (OidIsValid(clause_op))0 ); /* not a member of opfamily?? */ if (op_strategy == BTEqualStrategyNumber)true ;/* * We apply inequality selectivities to estimate index descent * costs with scans that use skip arrays . Save this indexcol ' s * RestrictInfos if it looks like they ' ll be needed for that . if (!eqQualHere && !found_row_compare &&1 )/* * If index is unique and we found an ' = ' clause for each column , we can * just assume numIndexTuples = 1 and skip the expensive * clauselist_selectivity calculations . However , an array or NullTest * always invalidates that theory ( even when eqQualHere has been set ) . if (index->unique &&1 &&1 .0 ;else /* * If the index is partial , AND the index predicate with the * index - bound quals to produce a more accurate idea of the number of * rows covered by the bound conditions . /* * btree automatically combines individual array element primitive * index scans whenever the tuples covered by the next set of array * keys are close to tuples covered by the current set . That puts a * natural ceiling on the worst case number of descents - - there * cannot possibly be more than one descent per leaf page scanned . * * Clamp the number of descents to at most 1 / 3 the number of index * pages . This avoids implausibly high estimates with low selectivity * paths , where scans usually require only one or two descents . This * is most likely to help when there are several SAOP clauses , where * naively accepting the total number of distinct combinations of * array elements as the number of descents would frequently lead to * wild overestimates . * * We somewhat arbitrarily don ' t just make the cutoff the total number * of leaf pages ( we make it 1 / 3 the total number of pages instead ) to * give the btree code credit for its ability to continue on the leaf * level with low selectivity scans . * * Note : num_sa_scans includes both ScalarArrayOp array elements and * skip array elements whose qual affects our numIndexTuples estimate . 0 .3333333 ));1 );/* * As in genericcostestimate ( ) , we have to adjust for any array quals * included in indexBoundQuals , and then round to integer . * * It is tempting to make genericcostestimate behave as if array * clauses work in almost the same way as scalar operators during * btree scans , making the top - level scan look like a continuous scan * ( as opposed to num_sa_scans - many primitive index scans ) . After * all , btree scans mostly work like that at runtime . However , such a * scheme would badly bias genericcostestimate ' s simplistic approach * to calculating numIndexPages through prorating . * * Stick with the approach taken by non - native SAOP scans for now . * genericcostestimate will use the Mackert - Lohman formula to * compensate for repeat page fetches , even though that definitely * won ' t happen during btree scans ( not for leaf pages , at least ) . * We ' re usually very pessimistic about the number of primitive index * scans that will be required , but it ' s not clear how to do better . /* * Now do generic index cost estimation . /* * Add a CPU - cost component to represent the costs of initial btree * descent . We don ' t charge any I / O cost for touching upper btree levels , * since they tend to stay in cache , but we still have to do about log2 ( N ) * comparisons to descend a btree of N leaf tuples . We charge one * cpu_operator_cost per comparison . * * If there are SAOP or skip array keys , charge this once per estimated * index descent . The ones after the first one are not startup cost so * far as the overall plan goes , so just add them to " total " cost . if (index->tuples > 1 ) /* avoid computing log(0) */ 2 .0 )) * cpu_operator_cost;/* * Even though we ' re not charging I / O cost for touching upper btree pages , * it ' s still reasonable to charge some CPU cost per page descended * through . Moreover , if we had no such charge at all , bloated indexes * would appear to have the same search cost as unbloated ones , at least * in cases where only a single leaf page is expected to be visited . This * cost is somewhat arbitrarily set at 50 x cpu_operator_cost per page * touched . The number of such pages is btree tree height plus one ( ie , * we charge for the leaf page too ) . As above , charge once per estimated * SAOP / skip array descent . 1 ) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;if (!have_correlation)0 , &vardata);if (HeapTupleIsValid(vardata.statsTuple))else /* btcost_correlation already called earlier on */ void double loop_count,double *indexCorrelation,double *indexPages)0 };/* * A hash index has no descent costs as such , since the index AM can go * directly to the target bucket after computing the hash value . There * are a couple of other hash - specific costs that we could conceivably add * here , though : * * Ideally we ' d charge spc_random_page_cost for each page in the target * bucket , not just the numIndexPages pages that genericcostestimate * thought we ' d visit . However in most cases we don ' t know which bucket * that will be . There ' s no point in considering the average bucket size * because the hash AM makes sure that ' s always one page . * * Likewise , we could consider charging some CPU for each index tuple in * the bucket , if we knew how many there were . But the per - tuple cost is * just a hash value comparison , not a general datatype - dependent * comparison , so any such charge ought to be quite a bit less than * cpu_operator_cost ; which makes it probably not worth worrying about . * * A bigger issue is that chance hash - value collisions will result in * wasted probes into the heap . We don ' t currently attempt to model this * cost on the grounds that it ' s rare , but maybe it ' s not rare enough . * ( Any fix for this ought to consider the generic lossy - operator problem , * though ; it ' s not entirely hash - specific . ) void double loop_count,double *indexCorrelation,double *indexPages)0 };/* * We model index descent costs similarly to those for btree , but to do * that we first need an idea of the tree height . We somewhat arbitrarily * assume that the fanout is 100 , meaning the tree height is at most * log100 ( index - > pages ) . * * Although this computation isn ' t really expensive enough to require * caching , we might as well use index - > tree_height to cache it . if (index->tree_height < 0 ) /* unknown? */ if (index->pages > 1 ) /* avoid computing log(0) */ int ) (log(index->pages) / log(100 .0 ));else 0 ;/* * Add a CPU - cost component to represent the costs of initial descent . We * just use log ( N ) here not log2 ( N ) since the branching factor isn ' t * necessarily two anyway . As for btree , charge once per SA scan . if (index->tuples > 1 ) /* avoid computing log(0) */ /* * Likewise add a per - page charge , calculated the same as for btrees . 1 ) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;void double loop_count,double *indexCorrelation,double *indexPages)0 };/* * We model index descent costs similarly to those for btree , but to do * that we first need an idea of the tree height . We somewhat arbitrarily * assume that the fanout is 100 , meaning the tree height is at most * log100 ( index - > pages ) . * * Although this computation isn ' t really expensive enough to require * caching , we might as well use index - > tree_height to cache it . if (index->tree_height < 0 ) /* unknown? */ if (index->pages > 1 ) /* avoid computing log(0) */ int ) (log(index->pages) / log(100 .0 ));else 0 ;/* * Add a CPU - cost component to represent the costs of initial descent . We * just use log ( N ) here not log2 ( N ) since the branching factor isn ' t * necessarily two anyway . As for btree , charge once per SA scan . if (index->tuples > 1 ) /* avoid computing log(0) */ /* * Likewise add a per - page charge , calculated the same as for btrees . 1 ) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;/* * Support routines for gincostestimate typedef struct bool attHasFullScan[INDEX_MAX_KEYS];bool attHasNormalScan[INDEX_MAX_KEYS];double partialEntries;double exactEntries;double searchEntries;double arrayScans;/* * Estimate the number of index terms that need to be searched for while * testing the given GIN query , and increment the counts in * counts * appropriately . If the query is unsatisfiable , return false . static bool int indexcol,int strategy_op;0 ;bool *partial_matches = NULL;bool *nullFlags = NULL;/* * Get the operator ' s strategy number and declared input data types within * the index opfamily . ( We don ' t need the latter , but we use * get_op_opfamily_properties because it will throw error if it fails to * find a matching pg_amop entry . ) false ,/* * GIN always uses the " default " support functions , which are those with * lefttype = = righttype = = the opclass ' opcintype ( see * IndexSupportInitialize in relcache . c ) . if (!OidIsValid(extractProcOid))/* should not happen; throw same error as index_getprocinfo */ "missing support function %d for attribute %d of index \" %s\"" ,1 ,/* * Choose collation to pass to extractProc ( should match initGinState ) . if (OidIsValid(index->indexcollations[indexcol]))else if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT)/* No match is possible */ return false ;for (i = 0 ; i < nentries; i++)/* * For partial match we haven ' t any information to estimate number of * matched entries in index , so , we just estimate it as 100 if (partial_matches && partial_matches[i])100 ;else if (searchMode == GIN_SEARCH_MODE_DEFAULT)true ;else if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)/* Treat "include empty" like an exact-match item */ true ;else /* It's GIN_SEARCH_MODE_ALL */ true ;return true ;/* * Estimate the number of index terms that need to be searched for while * testing the given GIN index clause , and increment the counts in * counts * appropriately . If the query is unsatisfiable , return false . static bool int indexcol,/* aggressively reduce to a constant, and look through relabeling */ if (IsA(operand, RelabelType))/* * It ' s impossible to call extractQuery method for unknown operand . So * unless operand is a Const we can ' t do much ; just assume there will be * one ordinary search entry from the operand at runtime . if (!IsA(operand, Const ))return true ;/* If Const is null, there can be no matches */ if (((Const *) operand)->constisnull)return false ;/* Otherwise, apply extractQuery and get the actual term counts */ return gincost_pattern(index, indexcol, clause_op,Const *) operand)->constvalue,/* * Estimate the number of index terms that need to be searched for while * testing the given GIN index clause , and increment the counts in * counts * appropriately . If the query is unsatisfiable , return false . * * A ScalarArrayOpExpr will give rise to N separate indexscans at runtime , * each of which involves one value from the RHS array , plus all the * non - array quals ( if any ) . To model this , we average the counts across * the RHS elements , and add the averages to the counts in * counts ( which * correspond to per - indexscan costs ) . We also multiply counts - > arrayScans * by N , causing gincostestimate to scale up its estimates accordingly . static bool int indexcol,double numIndexEntries,bool elmbyval;char elmalign;int numElems;bool *elemNulls;int numPossible = 0 ;int i;/* aggressively reduce to a constant, and look through relabeling */ if (IsA(rightop, RelabelType))/* * It ' s impossible to call extractQuery method for unknown operand . So * unless operand is a Const we can ' t do much ; just assume there will be * one ordinary search entry from each array entry at runtime , and fall * back on a probably - bad estimate of the number of array entries . if (!IsA(rightop, Const ))return true ;/* If Const is null, there can be no matches */ if (((Const *) rightop)->constisnull)return false ;/* Otherwise, extract the array elements and iterate over them */ Const *) rightop)->constvalue);0 , sizeof (arraycounts));for (i = 0 ; i < numElems; i++)/* NULL can't match anything, so ignore, as the executor will */ if (elemNulls[i])continue ;/* Otherwise, apply extractQuery and get the actual term counts */ 0 , sizeof (elemcounts));if (gincost_pattern(index, indexcol, clause_op, elemValues[i],/* We ignore array elements that are unsatisfiable patterns */ if (elemcounts.attHasFullScan[indexcol] &&/* * Full index scan will be required . We treat this as if * every key in the index had been listed in the query ; is * that reasonable ? 0 ;if (numPossible == 0 )/* No satisfiable patterns in the array */ return false ;/* * Now add the averages to the global counts . This will give us an * estimate of the average number of terms searched for in each indexscan , * including contributions from both array and non - array quals . return true ;/* * GIN has search behavior completely different from other index types void double loop_count,double *indexCorrelation,double *indexPages)double numPages = index->pages,double numEntryPages,bool matchPossible;bool fullIndexScan;double partialScale;double entryPagesFetched,double qual_op_cost,int i;/* * Obtain statistical information from the meta page , if possible . Else * set ginStats to zeroes , and we ' ll cope below . if (!index->hypothetical)/* Lock should have already been obtained in plancat.c */ else 0 , sizeof (ginStats));/* * Assuming we got valid ( nonzero ) stats at all , nPendingPages can be * trusted , but the other fields are data as of the last VACUUM . We can * scale them up to account for growth since then , but that method only * goes so far ; in the worst case , the stats might be for a completely * empty index , and scaling them will produce pretty bogus numbers . * Somewhat arbitrarily , set the cutoff for doing scaling at 4 X growth ; if * it ' s grown more than that , fall back to estimating things only from the * assumed - accurate index size . But we ' ll trust nPendingPages in any case * so long as it ' s not clearly insane , ie , more than the index size . if (ginStats.nPendingPages < numPages)else 0 ;if (numPages > 0 && ginStats.nTotalPages <= numPages &&4 &&0 && ginStats.nEntries > 0 )/* * OK , the stats seem close enough to sane to be trusted . But we * still need to scale them by the ratio numPages / nTotalPages to * account for growth since the last VACUUM . double scale = numPages / ginStats.nTotalPages;/* ensure we didn't round up too much */ else /* * We might get here because it ' s a hypothetical index , or an index * created pre - 9 . 1 and never vacuumed since upgrading ( in which case * its stats would read as zeroes ) , or just because it ' s grown too * much since the last VACUUM for us to put our faith in scaling . * * Invent some plausible internal statistics based on the index page * count ( and clamp that to at least 10 pages , just in case ) . We * estimate that 90 % of the index is entry pages , and the rest is data * pages . Estimate 100 entries per entry page ; this is rather bogus * since it ' ll depend on the size of the keys , but it ' s more robust * than trying to predict the number of entries per heap tuple . 10 );0 .90 );100 );/* In an empty index, numEntries could be zero. Avoid divide-by-zero */ if (numEntries < 1 )1 ;/* * If the index is partial , AND the index predicate with the index - bound * quals to produce a more accurate idea of the number of rows covered by * the bound conditions . /* Estimate the fraction of main-table tuples that will be visited */ /* fetch estimated page cost for tablespace containing index */ /* * Generic assumption about index correlation : there isn ' t any . 0 .0 ;/* * Examine quals to estimate number of search entries & partial matches 0 , sizeof (counts));1 ;true ;if (IsA(clause, OpExpr))if (!matchPossible)break ;else if (IsA(clause, ScalarArrayOpExpr))if (!matchPossible)break ;else /* shouldn't be anything else for a GIN index */ "unsupported GIN indexqual type: %d" ,int ) nodeTag(clause));/* Fall out if there were any provably-unsatisfiable quals */ if (!matchPossible)0 ;0 ;0 ;return ;/* * If attribute has a full scan and at the same time doesn ' t have normal * scan , then we ' ll have to scan all non - null entries of that attribute . * Currently , we don ' t have per - attribute statistics for GIN . Thus , we * must assume the whole GIN index has to be scanned in this case . false ;for (i = 0 ; i < index->nkeycolumns; i++)if (counts.attHasFullScan[i] && !counts.attHasNormalScan[i])true ;break ;if (fullIndexScan || indexQuals == NIL)/* * Full index scan will be required . We treat this as if every key in * the index had been listed in the query ; is that reasonable ? 0 ;/* Will we have more than one iteration of a nestloop scan? */ /* * Compute cost to begin scan , first of all , pay attention to pending * list . /* * Estimate number of entry pages read . We need to do * counts . searchEntries searches . Use a power function as it should be , * but tuples on leaf pages usually is much greater . Here we include all * searches in entry tree , including search of first entry in partial * match algorithm 0 .15 )));/* * Add an estimate of entry pages read by partial match algorithm . It ' s a * scan over leaf pages in entry tree . We haven ' t any useful stats here , * so estimate it as proportion . Because counts . partialEntries is really * pretty bogus ( see code above ) , it ' s possible that it is more than * numEntries ; clamp the proportion to ensure sanity . 1 .0 );/* * Partial match algorithm reads all data pages before doing actual scan , * so it ' s a startup cost . Again , we haven ' t any useful stats here , so * estimate it as proportion . 0 ;0 ;/* * Add a CPU - cost component to represent the costs of initial entry btree * descent . We don ' t charge any I / O cost for touching upper btree levels , * since they tend to stay in cache , but we still have to do about log2 ( N ) * comparisons to descend a btree of N leaf tuples . We charge one * cpu_operator_cost per comparison . * * If there are ScalarArrayOpExprs , charge this once per SA scan . The * ones after the first one are not startup cost so far as the overall * plan is concerned , so add them only to " total " cost . if (numEntries > 1 ) /* avoid computing log(0) */ 2 .0 )) * cpu_operator_cost;/* * Add a cpu cost per entry - page fetched . This is not amortized over a * loop . st;* cpu_operator_cost;/* * Add a cpu cost per data - page fetched . This is also not amortized over a * loop . Since those are the data pages from the partial match algorithm , * charge them as startup cost . d;/* * Since we add the startup cost to the total cost later on , remove the * initial arrayscan from the total . 1 ) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;/* * Calculate cache effects if more than one scan due to nestloops or array * quals . The result is pro - rated per nestloop scan , but the array qual * factor shouldn ' t be pro - rated ( compare genericcostestimate ) . if (outer_scans > 1 || counts.arrayScans > 1 )/* * Here we use random page cost because logically - close pages could be far * apart on disk . /* * Now compute the number of data pages fetched during the scan . * * We assume every entry to have the same number of items , and that there * is no overlap between them . ( XXX : tsvector and array opclasses collect * statistics on the frequency of individual keys ; it would be nice to use * those here . ) /* * If there is a lot of overlap among the entries , in particular if one of * the entries is very frequent , the above calculation can grossly * under - estimate . As a simple cross - check , calculate a lower bound based * on the overall selectivity of the quals . At a minimum , we must read * one item pointer for each matching entry . * * The width of each item pointer varies , based on the level of * compression . We don ' t have statistics on that , but an average of * around 3 bytes per item is fairly typical . 3 )));if (dataPagesFetchedBySel > dataPagesFetched)/* Add one page cpu-cost to the startup cost */ tries;/* * Add once again a CPU - cost for those data pages , before amortizing for * cache . cpu_operator_cost;/* Account for cache effects, the same as above */ if (outer_scans > 1 || counts.arrayScans > 1 )/* And apply random_page_cost as the cost per page */ /* * Add on index qual eval costs , much as in genericcostestimate . We charge * cpu but we can disregard indexorderbys , since GIN doesn ' t support * those . /* * Add a cpu cost per search entry , corresponding to the actual visited * entries . /* Now add a cpu cost per tuple in the posting lists / trees */ /* * BRIN has search behavior completely different from other index types void double loop_count,double *indexCorrelation,double *indexPages)double numPages = index->pages;double qual_arg_cost;double qualSelectivity;double indexRanges;double minimalRanges;double estimatedRanges;double selec;/* fetch estimated page cost for the tablespace containing the index */ /* * Obtain some data from the index itself , if possible . Otherwise invent * some plausible internal statistics based on the relation page count . if (!index->hypothetical)/* * A lock should have already been obtained on the index in plancat . c . /* work out the actual number of ranges in the index */ double ) baserel->pages /1 .0 );else /* * Assume default number of pages per range , and estimate the number * of ranges based on that . double ) baserel->pages /1 .0 );1 ;/* * Compute index correlation * * Because we can use all index quals equally when scanning , we can use * the largest correlation ( in absolute value ) among columns used by the * query . Start at zero , the worst possible case . If we cannot find any * correlation statistics , we will keep it as 0 . 0 ;/* attempt to lookup stats in relation for this index column */ if (attnum != 0 )/* Simple variable -- look to stats for the underlying table */ if (get_relation_stats_hook &&/* * The hook took control of acquiring a stats tuple . If it * did supply a tuple , it ' d better have supplied a freefunc . if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)"no function provided to release variable stats with" );else false ));else /* * Looks like we ' ve found an expression column in the index . Let ' s * see if there ' s any stats for it . /* get the attnum from the 0-based index. */ 1 ;if (get_index_stats_hook &&/* * The hook took control of acquiring a stats tuple . If it * did supply a tuple , it ' d better have supplied a freefunc . if (HeapTupleIsValid(vardata.statsTuple) &&"no function provided to release variable stats with" );else false ));if (HeapTupleIsValid(vardata.statsTuple))if (get_attstatsslot(&sslot, vardata.statsTuple,double varCorrelation = 0 .0 ;if (sslot.nnumbers > 0 )0 ]);if (varCorrelation > *indexCorrelation)/* * Now calculate the minimum possible ranges we could match with if all of * the rows were in the perfect order in the table ' s heap . /* * Now estimate the number of ranges that we ' ll touch by using the * indexCorrelation from the stats . Careful not to divide by zero ( note * we ' re using the absolute value of the correlation ) . if (*indexCorrelation < 1 .0 e-10 )else /* we expect to visit this portion of the table */ /* * Compute the index qual costs , much as in genericcostestimate , to add to * the index costs . We can disregard indexorderbys , since BRIN doesn ' t * support those . /* * Compute the startup cost as the cost to read the whole revmap * sequentially , including the cost to execute the index quals . /* * To read a BRIN index there might be a bit of back and forth over * regular pages , as revmap might point to them out of sequential order ; * calculate the total cost as reading the whole index in random order . /* * Charge a small amount per range tuple which we expect to match to . This * is meant to reflect the costs of manipulating the bitmap . The BRIN scan * will set a bit for each page in the range when we find a matching * range , so we must multiply the charge by the number of pages in the * range . 0 .1 * cpu_operator_cost * estimatedRanges *
Messung V0.5 in Prozent C=88 H=95 G=91
¤ Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.1.497Bemerkung:
(vorverarbeitet am 2026-09-28)
¤ *Bot Zugriff
