Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * selfuncs.c
4 : * Selectivity functions and index cost estimation functions for
5 : * standard operators and index access methods.
6 : *
7 : * Selectivity routines are registered in the pg_operator catalog
8 : * in the "oprrest" and "oprjoin" attributes.
9 : *
10 : * Index cost functions are located via the index AM's API struct,
11 : * which is obtained from the handler function registered in pg_am.
12 : *
13 : * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
14 : * Portions Copyright (c) 1994, Regents of the University of California
15 : *
16 : *
17 : * IDENTIFICATION
18 : * src/backend/utils/adt/selfuncs.c
19 : *
20 : *-------------------------------------------------------------------------
21 : */
22 :
23 : /*----------
24 : * Operator selectivity estimation functions are called to estimate the
25 : * selectivity of WHERE clauses whose top-level operator is their operator.
26 : * We divide the problem into two cases:
27 : * Restriction clause estimation: the clause involves vars of just
28 : * one relation.
29 : * Join clause estimation: the clause involves vars of multiple rels.
30 : * Join selectivity estimation is far more difficult and usually less accurate
31 : * than restriction estimation.
32 : *
33 : * When dealing with the inner scan of a nestloop join, we consider the
34 : * join's joinclauses as restriction clauses for the inner relation, and
35 : * treat vars of the outer relation as parameters (a/k/a constants of unknown
36 : * values). So, restriction estimators need to be able to accept an argument
37 : * telling which relation is to be treated as the variable.
38 : *
39 : * The call convention for a restriction estimator (oprrest function) is
40 : *
41 : * Selectivity oprrest (PlannerInfo *root,
42 : * Oid operator,
43 : * List *args,
44 : * int varRelid);
45 : *
46 : * root: general information about the query (rtable and RelOptInfo lists
47 : * are particularly important for the estimator).
48 : * operator: OID of the specific operator in question.
49 : * args: argument list from the operator clause.
50 : * varRelid: if not zero, the relid (rtable index) of the relation to
51 : * be treated as the variable relation. May be zero if the args list
52 : * is known to contain vars of only one relation.
53 : *
54 : * This is represented at the SQL level (in pg_proc) as
55 : *
56 : * float8 oprrest (internal, oid, internal, int4);
57 : *
58 : * The result is a selectivity, that is, a fraction (0 to 1) of the rows
59 : * of the relation that are expected to produce a TRUE result for the
60 : * given operator.
61 : *
62 : * The call convention for a join estimator (oprjoin function) is similar
63 : * except that varRelid is not needed, and instead join information is
64 : * supplied:
65 : *
66 : * Selectivity oprjoin (PlannerInfo *root,
67 : * Oid operator,
68 : * List *args,
69 : * JoinType jointype,
70 : * SpecialJoinInfo *sjinfo);
71 : *
72 : * float8 oprjoin (internal, oid, internal, int2, internal);
73 : *
74 : * (Before Postgres 8.4, join estimators had only the first four of these
75 : * parameters. That signature is still allowed, but deprecated.) The
76 : * relationship between jointype and sjinfo is explained in the comments for
77 : * clause_selectivity() --- the short version is that jointype is usually
78 : * best ignored in favor of examining sjinfo.
79 : *
80 : * Join selectivity for regular inner and outer joins is defined as the
81 : * fraction (0 to 1) of the cross product of the relations that is expected
82 : * to produce a TRUE result for the given operator. For both semi and anti
83 : * joins, however, the selectivity is defined as the fraction of the left-hand
84 : * side relation's rows that are expected to have a match (ie, at least one
85 : * row with a TRUE result) in the right-hand side.
86 : *
87 : * For both oprrest and oprjoin functions, the operator's input collation OID
88 : * (if any) is passed using the standard fmgr mechanism, so that the estimator
89 : * function can fetch it with PG_GET_COLLATION(). Note, however, that all
90 : * statistics in pg_statistic are currently built using the relevant column's
91 : * collation. Thus, in most cases where we are looking at statistics, we
92 : * should ignore the operator collation and use the stats entry's collation.
93 : * We expect that the error induced by doing this is usually not large enough
94 : * to justify complicating matters. In any case, doing otherwise would yield
95 : * entirely garbage results for ordered stats data such as histograms.
96 : *----------
97 : */
98 :
99 : #include "postgres.h"
100 :
101 : #include <ctype.h>
102 : #include <math.h>
103 :
104 : #include "access/brin.h"
105 : #include "access/gin.h"
106 : #include "access/htup_details.h"
107 : #include "access/sysattr.h"
108 : #include "access/table.h"
109 : #include "access/tableam.h"
110 : #include "catalog/index.h"
111 : #include "catalog/pg_am.h"
112 : #include "catalog/pg_collation.h"
113 : #include "catalog/pg_operator.h"
114 : #include "catalog/pg_statistic.h"
115 : #include "catalog/pg_statistic_ext.h"
116 : #include "executor/executor.h"
117 : #include "executor/nodeAgg.h"
118 : #include "miscadmin.h"
119 : #include "nodes/makefuncs.h"
120 : #include "nodes/nodeFuncs.h"
121 : #include "optimizer/clauses.h"
122 : #include "optimizer/cost.h"
123 : #include "optimizer/optimizer.h"
124 : #include "optimizer/pathnode.h"
125 : #include "optimizer/paths.h"
126 : #include "optimizer/plancat.h"
127 : #include "parser/parse_clause.h"
128 : #include "parser/parsetree.h"
129 : #include "statistics/statistics.h"
130 : #include "utils/builtins.h"
131 : #include "utils/date.h"
132 : #include "utils/datum.h"
133 : #include "utils/fmgroids.h"
134 : #include "utils/index_selfuncs.h"
135 : #include "utils/lsyscache.h"
136 : #include "utils/pg_locale.h"
137 : #include "utils/rel.h"
138 : #include "utils/selfuncs.h"
139 : #include "utils/snapmgr.h"
140 : #include "utils/spccache.h"
141 : #include "utils/syscache.h"
142 : #include "utils/timestamp.h"
143 : #include "utils/typcache.h"
144 :
145 :
146 : /* Hooks for plugins to get control when we ask for stats */
147 : get_relation_stats_hook_type get_relation_stats_hook = NULL;
148 : get_index_stats_hook_type get_index_stats_hook = NULL;
149 :
150 : static double eqsel_internal(PG_FUNCTION_ARGS, bool negate);
151 : static double eqjoinsel_inner(Oid opfuncoid,
152 : VariableStatData *vardata1, VariableStatData *vardata2,
153 : double nd1, double nd2,
154 : bool isdefault1, bool isdefault2,
155 : AttStatsSlot *sslot1, AttStatsSlot *sslot2,
156 : Form_pg_statistic stats1, Form_pg_statistic stats2,
157 : bool have_mcvs1, bool have_mcvs2);
158 : static double eqjoinsel_semi(Oid opfuncoid,
159 : VariableStatData *vardata1, VariableStatData *vardata2,
160 : double nd1, double nd2,
161 : bool isdefault1, bool isdefault2,
162 : AttStatsSlot *sslot1, AttStatsSlot *sslot2,
163 : Form_pg_statistic stats1, Form_pg_statistic stats2,
164 : bool have_mcvs1, bool have_mcvs2,
165 : RelOptInfo *inner_rel);
166 : static bool estimate_multivariate_ndistinct(PlannerInfo *root,
167 : RelOptInfo *rel, List **varinfos, double *ndistinct);
168 : static bool convert_to_scalar(Datum value, Oid valuetypid, Oid collid,
169 : double *scaledvalue,
170 : Datum lobound, Datum hibound, Oid boundstypid,
171 : double *scaledlobound, double *scaledhibound);
172 : static double convert_numeric_to_scalar(Datum value, Oid typid, bool *failure);
173 : static void convert_string_to_scalar(char *value,
174 : double *scaledvalue,
175 : char *lobound,
176 : double *scaledlobound,
177 : char *hibound,
178 : double *scaledhibound);
179 : static void convert_bytea_to_scalar(Datum value,
180 : double *scaledvalue,
181 : Datum lobound,
182 : double *scaledlobound,
183 : Datum hibound,
184 : double *scaledhibound);
185 : static double convert_one_string_to_scalar(char *value,
186 : int rangelo, int rangehi);
187 : static double convert_one_bytea_to_scalar(unsigned char *value, int valuelen,
188 : int rangelo, int rangehi);
189 : static char *convert_string_datum(Datum value, Oid typid, Oid collid,
190 : bool *failure);
191 : static double convert_timevalue_to_scalar(Datum value, Oid typid,
192 : bool *failure);
193 : static void examine_simple_variable(PlannerInfo *root, Var *var,
194 : VariableStatData *vardata);
195 : static bool get_variable_range(PlannerInfo *root, VariableStatData *vardata,
196 : Oid sortop, Datum *min, Datum *max);
197 : static bool get_actual_variable_range(PlannerInfo *root,
198 : VariableStatData *vardata,
199 : Oid sortop,
200 : Datum *min, Datum *max);
201 : static RelOptInfo *find_join_input_rel(PlannerInfo *root, Relids relids);
202 :
203 :
204 : /*
205 : * eqsel - Selectivity of "=" for any data types.
206 : *
207 : * Note: this routine is also used to estimate selectivity for some
208 : * operators that are not "=" but have comparable selectivity behavior,
209 : * such as "~=" (geometric approximate-match). Even for "=", we must
210 : * keep in mind that the left and right datatypes may differ.
211 : */
212 : Datum
213 291844 : eqsel(PG_FUNCTION_ARGS)
214 : {
215 291844 : PG_RETURN_FLOAT8((float8) eqsel_internal(fcinfo, false));
216 : }
217 :
218 : /*
219 : * Common code for eqsel() and neqsel()
220 : */
221 : static double
222 302954 : eqsel_internal(PG_FUNCTION_ARGS, bool negate)
223 : {
224 302954 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
225 302954 : Oid operator = PG_GETARG_OID(1);
226 302954 : List *args = (List *) PG_GETARG_POINTER(2);
227 302954 : int varRelid = PG_GETARG_INT32(3);
228 : VariableStatData vardata;
229 : Node *other;
230 : bool varonleft;
231 : double selec;
232 :
233 : /*
234 : * When asked about <>, we do the estimation using the corresponding =
235 : * operator, then convert to <> via "1.0 - eq_selectivity - nullfrac".
236 : */
237 302954 : if (negate)
238 : {
239 11110 : operator = get_negator(operator);
240 11110 : if (!OidIsValid(operator))
241 : {
242 : /* Use default selectivity (should we raise an error instead?) */
243 0 : return 1.0 - DEFAULT_EQ_SEL;
244 : }
245 : }
246 :
247 : /*
248 : * If expression is not variable = something or something = variable, then
249 : * punt and return a default estimate.
250 : */
251 302954 : if (!get_restriction_variable(root, args, varRelid,
252 : &vardata, &other, &varonleft))
253 1220 : return negate ? (1.0 - DEFAULT_EQ_SEL) : DEFAULT_EQ_SEL;
254 :
255 : /*
256 : * We can do a lot better if the something is a constant. (Note: the
257 : * Const might result from estimation rather than being a simple constant
258 : * in the query.)
259 : */
260 301734 : if (IsA(other, Const))
261 412536 : selec = var_eq_const(&vardata, operator,
262 137512 : ((Const *) other)->constvalue,
263 137512 : ((Const *) other)->constisnull,
264 : varonleft, negate);
265 : else
266 164222 : selec = var_eq_non_const(&vardata, operator, other,
267 : varonleft, negate);
268 :
269 301734 : ReleaseVariableStats(vardata);
270 :
271 301734 : return selec;
272 : }
273 :
274 : /*
275 : * var_eq_const --- eqsel for var = const case
276 : *
277 : * This is exported so that some other estimation functions can use it.
278 : */
279 : double
280 152780 : var_eq_const(VariableStatData *vardata, Oid operator,
281 : Datum constval, bool constisnull,
282 : bool varonleft, bool negate)
283 : {
284 : double selec;
285 152780 : double nullfrac = 0.0;
286 : bool isdefault;
287 : Oid opfuncoid;
288 :
289 : /*
290 : * If the constant is NULL, assume operator is strict and return zero, ie,
291 : * operator will never return TRUE. (It's zero even for a negator op.)
292 : */
293 152780 : if (constisnull)
294 20 : return 0.0;
295 :
296 : /*
297 : * Grab the nullfrac for use below. Note we allow use of nullfrac
298 : * regardless of security check.
299 : */
300 152760 : if (HeapTupleIsValid(vardata->statsTuple))
301 : {
302 : Form_pg_statistic stats;
303 :
304 104156 : stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
305 104156 : nullfrac = stats->stanullfrac;
306 : }
307 :
308 : /*
309 : * If we matched the var to a unique index or DISTINCT clause, assume
310 : * there is exactly one match regardless of anything else. (This is
311 : * slightly bogus, since the index or clause's equality operator might be
312 : * different from ours, but it's much more likely to be right than
313 : * ignoring the information.)
314 : */
315 152760 : if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1.0)
316 : {
317 30898 : selec = 1.0 / vardata->rel->tuples;
318 : }
319 205128 : else if (HeapTupleIsValid(vardata->statsTuple) &&
320 83266 : statistic_proc_security_check(vardata,
321 : (opfuncoid = get_opcode(operator))))
322 83266 : {
323 : AttStatsSlot sslot;
324 83266 : bool match = false;
325 : int i;
326 :
327 : /*
328 : * Is the constant "=" to any of the column's most common values?
329 : * (Although the given operator may not really be "=", we will assume
330 : * that seeing whether it returns TRUE is an appropriate test. If you
331 : * don't like this, maybe you shouldn't be using eqsel for your
332 : * operator...)
333 : */
334 83266 : if (get_attstatsslot(&sslot, vardata->statsTuple,
335 : STATISTIC_KIND_MCV, InvalidOid,
336 : ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
337 : {
338 : FmgrInfo eqproc;
339 :
340 74462 : fmgr_info(opfuncoid, &eqproc);
341 :
342 1415080 : for (i = 0; i < sslot.nvalues; i++)
343 : {
344 : /* be careful to apply operator right way 'round */
345 1375716 : if (varonleft)
346 1375716 : match = DatumGetBool(FunctionCall2Coll(&eqproc,
347 : sslot.stacoll,
348 : sslot.values[i],
349 : constval));
350 : else
351 0 : match = DatumGetBool(FunctionCall2Coll(&eqproc,
352 : sslot.stacoll,
353 : constval,
354 : sslot.values[i]));
355 1375716 : if (match)
356 35098 : break;
357 : }
358 : }
359 : else
360 : {
361 : /* no most-common-value info available */
362 8804 : i = 0; /* keep compiler quiet */
363 : }
364 :
365 83266 : if (match)
366 : {
367 : /*
368 : * Constant is "=" to this common value. We know selectivity
369 : * exactly (or as exactly as ANALYZE could calculate it, anyway).
370 : */
371 35098 : selec = sslot.numbers[i];
372 : }
373 : else
374 : {
375 : /*
376 : * Comparison is against a constant that is neither NULL nor any
377 : * of the common values. Its selectivity cannot be more than
378 : * this:
379 : */
380 48168 : double sumcommon = 0.0;
381 : double otherdistinct;
382 :
383 1298332 : for (i = 0; i < sslot.nnumbers; i++)
384 1250164 : sumcommon += sslot.numbers[i];
385 48168 : selec = 1.0 - sumcommon - nullfrac;
386 48168 : CLAMP_PROBABILITY(selec);
387 :
388 : /*
389 : * and in fact it's probably a good deal less. We approximate that
390 : * all the not-common values share this remaining fraction
391 : * equally, so we divide by the number of other distinct values.
392 : */
393 96336 : otherdistinct = get_variable_numdistinct(vardata, &isdefault) -
394 48168 : sslot.nnumbers;
395 48168 : if (otherdistinct > 1)
396 29208 : selec /= otherdistinct;
397 :
398 : /*
399 : * Another cross-check: selectivity shouldn't be estimated as more
400 : * than the least common "most common value".
401 : */
402 48168 : if (sslot.nnumbers > 0 && selec > sslot.numbers[sslot.nnumbers - 1])
403 0 : selec = sslot.numbers[sslot.nnumbers - 1];
404 : }
405 :
406 83266 : free_attstatsslot(&sslot);
407 : }
408 : else
409 : {
410 : /*
411 : * No ANALYZE stats available, so make a guess using estimated number
412 : * of distinct values and assuming they are equally common. (The guess
413 : * is unlikely to be very good, but we do know a few special cases.)
414 : */
415 38596 : selec = 1.0 / get_variable_numdistinct(vardata, &isdefault);
416 : }
417 :
418 : /* now adjust if we wanted <> rather than = */
419 152760 : if (negate)
420 8490 : selec = 1.0 - selec - nullfrac;
421 :
422 : /* result should be in range, but make sure... */
423 152760 : CLAMP_PROBABILITY(selec);
424 :
425 152760 : return selec;
426 : }
427 :
428 : /*
429 : * var_eq_non_const --- eqsel for var = something-other-than-const case
430 : *
431 : * This is exported so that some other estimation functions can use it.
432 : */
433 : double
434 164222 : var_eq_non_const(VariableStatData *vardata, Oid operator,
435 : Node *other,
436 : bool varonleft, bool negate)
437 : {
438 : double selec;
439 164222 : double nullfrac = 0.0;
440 : bool isdefault;
441 :
442 : /*
443 : * Grab the nullfrac for use below.
444 : */
445 164222 : if (HeapTupleIsValid(vardata->statsTuple))
446 : {
447 : Form_pg_statistic stats;
448 :
449 123614 : stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
450 123614 : nullfrac = stats->stanullfrac;
451 : }
452 :
453 : /*
454 : * If we matched the var to a unique index or DISTINCT clause, assume
455 : * there is exactly one match regardless of anything else. (This is
456 : * slightly bogus, since the index or clause's equality operator might be
457 : * different from ours, but it's much more likely to be right than
458 : * ignoring the information.)
459 : */
460 164222 : if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1.0)
461 : {
462 80870 : selec = 1.0 / vardata->rel->tuples;
463 : }
464 83352 : else if (HeapTupleIsValid(vardata->statsTuple))
465 : {
466 : double ndistinct;
467 : AttStatsSlot sslot;
468 :
469 : /*
470 : * Search is for a value that we do not know a priori, but we will
471 : * assume it is not NULL. Estimate the selectivity as non-null
472 : * fraction divided by number of distinct values, so that we get a
473 : * result averaged over all possible values whether common or
474 : * uncommon. (Essentially, we are assuming that the not-yet-known
475 : * comparison value is equally likely to be any of the possible
476 : * values, regardless of their frequency in the table. Is that a good
477 : * idea?)
478 : */
479 57390 : selec = 1.0 - nullfrac;
480 57390 : ndistinct = get_variable_numdistinct(vardata, &isdefault);
481 57390 : if (ndistinct > 1)
482 54908 : selec /= ndistinct;
483 :
484 : /*
485 : * Cross-check: selectivity should never be estimated as more than the
486 : * most common value's.
487 : */
488 57390 : if (get_attstatsslot(&sslot, vardata->statsTuple,
489 : STATISTIC_KIND_MCV, InvalidOid,
490 : ATTSTATSSLOT_NUMBERS))
491 : {
492 49602 : if (sslot.nnumbers > 0 && selec > sslot.numbers[0])
493 140 : selec = sslot.numbers[0];
494 49602 : free_attstatsslot(&sslot);
495 : }
496 : }
497 : else
498 : {
499 : /*
500 : * No ANALYZE stats available, so make a guess using estimated number
501 : * of distinct values and assuming they are equally common. (The guess
502 : * is unlikely to be very good, but we do know a few special cases.)
503 : */
504 25962 : selec = 1.0 / get_variable_numdistinct(vardata, &isdefault);
505 : }
506 :
507 : /* now adjust if we wanted <> rather than = */
508 164222 : if (negate)
509 1996 : selec = 1.0 - selec - nullfrac;
510 :
511 : /* result should be in range, but make sure... */
512 164222 : CLAMP_PROBABILITY(selec);
513 :
514 164222 : return selec;
515 : }
516 :
517 : /*
518 : * neqsel - Selectivity of "!=" for any data types.
519 : *
520 : * This routine is also used for some operators that are not "!="
521 : * but have comparable selectivity behavior. See above comments
522 : * for eqsel().
523 : */
524 : Datum
525 11110 : neqsel(PG_FUNCTION_ARGS)
526 : {
527 11110 : PG_RETURN_FLOAT8((float8) eqsel_internal(fcinfo, true));
528 : }
529 :
530 : /*
531 : * scalarineqsel - Selectivity of "<", "<=", ">", ">=" for scalars.
532 : *
533 : * This is the guts of scalarltsel/scalarlesel/scalargtsel/scalargesel.
534 : * The isgt and iseq flags distinguish which of the four cases apply.
535 : *
536 : * The caller has commuted the clause, if necessary, so that we can treat
537 : * the variable as being on the left. The caller must also make sure that
538 : * the other side of the clause is a non-null Const, and dissect that into
539 : * a value and datatype. (This definition simplifies some callers that
540 : * want to estimate against a computed value instead of a Const node.)
541 : *
542 : * This routine works for any datatype (or pair of datatypes) known to
543 : * convert_to_scalar(). If it is applied to some other datatype,
544 : * it will return an approximate estimate based on assuming that the constant
545 : * value falls in the middle of the bin identified by binary search.
546 : */
547 : static double
548 157612 : scalarineqsel(PlannerInfo *root, Oid operator, bool isgt, bool iseq,
549 : VariableStatData *vardata, Datum constval, Oid consttype)
550 : {
551 : Form_pg_statistic stats;
552 : FmgrInfo opproc;
553 : double mcv_selec,
554 : hist_selec,
555 : sumcommon;
556 : double selec;
557 :
558 157612 : if (!HeapTupleIsValid(vardata->statsTuple))
559 : {
560 : /*
561 : * No stats are available. Typically this means we have to fall back
562 : * on the default estimate; but if the variable is CTID then we can
563 : * make an estimate based on comparing the constant to the table size.
564 : */
565 24192 : if (vardata->var && IsA(vardata->var, Var) &&
566 10744 : ((Var *) vardata->var)->varattno == SelfItemPointerAttributeNumber)
567 : {
568 : ItemPointer itemptr;
569 : double block;
570 : double density;
571 :
572 : /*
573 : * If the relation's empty, we're going to include all of it.
574 : * (This is mostly to avoid divide-by-zero below.)
575 : */
576 4 : if (vardata->rel->pages == 0)
577 0 : return 1.0;
578 :
579 4 : itemptr = (ItemPointer) DatumGetPointer(constval);
580 4 : block = ItemPointerGetBlockNumberNoCheck(itemptr);
581 :
582 : /*
583 : * Determine the average number of tuples per page (density).
584 : *
585 : * Since the last page will, on average, be only half full, we can
586 : * estimate it to have half as many tuples as earlier pages. So
587 : * give it half the weight of a regular page.
588 : */
589 4 : density = vardata->rel->tuples / (vardata->rel->pages - 0.5);
590 :
591 : /* If target is the last page, use half the density. */
592 4 : if (block >= vardata->rel->pages - 1)
593 0 : density *= 0.5;
594 :
595 : /*
596 : * Using the average tuples per page, calculate how far into the
597 : * page the itemptr is likely to be and adjust block accordingly,
598 : * by adding that fraction of a whole block (but never more than a
599 : * whole block, no matter how high the itemptr's offset is). Here
600 : * we are ignoring the possibility of dead-tuple line pointers,
601 : * which is fairly bogus, but we lack the info to do better.
602 : */
603 4 : if (density > 0.0)
604 : {
605 4 : OffsetNumber offset = ItemPointerGetOffsetNumberNoCheck(itemptr);
606 :
607 4 : block += Min(offset / density, 1.0);
608 : }
609 :
610 : /*
611 : * Convert relative block number to selectivity. Again, the last
612 : * page has only half weight.
613 : */
614 4 : selec = block / (vardata->rel->pages - 0.5);
615 :
616 : /*
617 : * The calculation so far gave us a selectivity for the "<=" case.
618 : * We'll have one less tuple for "<" and one additional tuple for
619 : * ">=", the latter of which we'll reverse the selectivity for
620 : * below, so we can simply subtract one tuple for both cases. The
621 : * cases that need this adjustment can be identified by iseq being
622 : * equal to isgt.
623 : */
624 4 : if (iseq == isgt && vardata->rel->tuples >= 1.0)
625 0 : selec -= (1.0 / vardata->rel->tuples);
626 :
627 : /* Finally, reverse the selectivity for the ">", ">=" cases. */
628 4 : if (isgt)
629 4 : selec = 1.0 - selec;
630 :
631 4 : CLAMP_PROBABILITY(selec);
632 4 : return selec;
633 : }
634 :
635 : /* no stats available, so default result */
636 13444 : return DEFAULT_INEQ_SEL;
637 : }
638 144164 : stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
639 :
640 144164 : fmgr_info(get_opcode(operator), &opproc);
641 :
642 : /*
643 : * If we have most-common-values info, add up the fractions of the MCV
644 : * entries that satisfy MCV OP CONST. These fractions contribute directly
645 : * to the result selectivity. Also add up the total fraction represented
646 : * by MCV entries.
647 : */
648 144164 : mcv_selec = mcv_selectivity(vardata, &opproc, constval, true,
649 : &sumcommon);
650 :
651 : /*
652 : * If there is a histogram, determine which bin the constant falls in, and
653 : * compute the resulting contribution to selectivity.
654 : */
655 144164 : hist_selec = ineq_histogram_selectivity(root, vardata,
656 : &opproc, isgt, iseq,
657 : constval, consttype);
658 :
659 : /*
660 : * Now merge the results from the MCV and histogram calculations,
661 : * realizing that the histogram covers only the non-null values that are
662 : * not listed in MCV.
663 : */
664 144164 : selec = 1.0 - stats->stanullfrac - sumcommon;
665 :
666 144164 : if (hist_selec >= 0.0)
667 123860 : selec *= hist_selec;
668 : else
669 : {
670 : /*
671 : * If no histogram but there are values not accounted for by MCV,
672 : * arbitrarily assume half of them will match.
673 : */
674 20304 : selec *= 0.5;
675 : }
676 :
677 144164 : selec += mcv_selec;
678 :
679 : /* result should be in range, but make sure... */
680 144164 : CLAMP_PROBABILITY(selec);
681 :
682 144164 : return selec;
683 : }
684 :
685 : /*
686 : * mcv_selectivity - Examine the MCV list for selectivity estimates
687 : *
688 : * Determine the fraction of the variable's MCV population that satisfies
689 : * the predicate (VAR OP CONST), or (CONST OP VAR) if !varonleft. Also
690 : * compute the fraction of the total column population represented by the MCV
691 : * list. This code will work for any boolean-returning predicate operator.
692 : *
693 : * The function result is the MCV selectivity, and the fraction of the
694 : * total population is returned into *sumcommonp. Zeroes are returned
695 : * if there is no MCV list.
696 : */
697 : double
698 146538 : mcv_selectivity(VariableStatData *vardata, FmgrInfo *opproc,
699 : Datum constval, bool varonleft,
700 : double *sumcommonp)
701 : {
702 : double mcv_selec,
703 : sumcommon;
704 : AttStatsSlot sslot;
705 : int i;
706 :
707 146538 : mcv_selec = 0.0;
708 146538 : sumcommon = 0.0;
709 :
710 291836 : if (HeapTupleIsValid(vardata->statsTuple) &&
711 290584 : statistic_proc_security_check(vardata, opproc->fn_oid) &&
712 145286 : get_attstatsslot(&sslot, vardata->statsTuple,
713 : STATISTIC_KIND_MCV, InvalidOid,
714 : ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
715 : {
716 2524014 : for (i = 0; i < sslot.nvalues; i++)
717 : {
718 4898720 : if (varonleft ?
719 2449360 : DatumGetBool(FunctionCall2Coll(opproc,
720 : sslot.stacoll,
721 : sslot.values[i],
722 : constval)) :
723 0 : DatumGetBool(FunctionCall2Coll(opproc,
724 : sslot.stacoll,
725 : constval,
726 : sslot.values[i])))
727 1340144 : mcv_selec += sslot.numbers[i];
728 2449360 : sumcommon += sslot.numbers[i];
729 : }
730 74654 : free_attstatsslot(&sslot);
731 : }
732 :
733 146538 : *sumcommonp = sumcommon;
734 146538 : return mcv_selec;
735 : }
736 :
737 : /*
738 : * histogram_selectivity - Examine the histogram for selectivity estimates
739 : *
740 : * Determine the fraction of the variable's histogram entries that satisfy
741 : * the predicate (VAR OP CONST), or (CONST OP VAR) if !varonleft.
742 : *
743 : * This code will work for any boolean-returning predicate operator, whether
744 : * or not it has anything to do with the histogram sort operator. We are
745 : * essentially using the histogram just as a representative sample. However,
746 : * small histograms are unlikely to be all that representative, so the caller
747 : * should be prepared to fall back on some other estimation approach when the
748 : * histogram is missing or very small. It may also be prudent to combine this
749 : * approach with another one when the histogram is small.
750 : *
751 : * If the actual histogram size is not at least min_hist_size, we won't bother
752 : * to do the calculation at all. Also, if the n_skip parameter is > 0, we
753 : * ignore the first and last n_skip histogram elements, on the grounds that
754 : * they are outliers and hence not very representative. Typical values for
755 : * these parameters are 10 and 1.
756 : *
757 : * The function result is the selectivity, or -1 if there is no histogram
758 : * or it's smaller than min_hist_size.
759 : *
760 : * The output parameter *hist_size receives the actual histogram size,
761 : * or zero if no histogram. Callers may use this number to decide how
762 : * much faith to put in the function result.
763 : *
764 : * Note that the result disregards both the most-common-values (if any) and
765 : * null entries. The caller is expected to combine this result with
766 : * statistics for those portions of the column population. It may also be
767 : * prudent to clamp the result range, ie, disbelieve exact 0 or 1 outputs.
768 : */
769 : double
770 2374 : histogram_selectivity(VariableStatData *vardata, FmgrInfo *opproc,
771 : Datum constval, bool varonleft,
772 : int min_hist_size, int n_skip,
773 : int *hist_size)
774 : {
775 : double result;
776 : AttStatsSlot sslot;
777 :
778 : /* check sanity of parameters */
779 : Assert(n_skip >= 0);
780 : Assert(min_hist_size > 2 * n_skip);
781 :
782 3508 : if (HeapTupleIsValid(vardata->statsTuple) &&
783 2268 : statistic_proc_security_check(vardata, opproc->fn_oid) &&
784 1134 : get_attstatsslot(&sslot, vardata->statsTuple,
785 : STATISTIC_KIND_HISTOGRAM, InvalidOid,
786 : ATTSTATSSLOT_VALUES))
787 : {
788 1130 : *hist_size = sslot.nvalues;
789 1130 : if (sslot.nvalues >= min_hist_size)
790 : {
791 770 : int nmatch = 0;
792 : int i;
793 :
794 67892 : for (i = n_skip; i < sslot.nvalues - n_skip; i++)
795 : {
796 134244 : if (varonleft ?
797 67122 : DatumGetBool(FunctionCall2Coll(opproc,
798 : sslot.stacoll,
799 : sslot.values[i],
800 : constval)) :
801 0 : DatumGetBool(FunctionCall2Coll(opproc,
802 : sslot.stacoll,
803 : constval,
804 : sslot.values[i])))
805 2676 : nmatch++;
806 : }
807 770 : result = ((double) nmatch) / ((double) (sslot.nvalues - 2 * n_skip));
808 : }
809 : else
810 360 : result = -1;
811 1130 : free_attstatsslot(&sslot);
812 : }
813 : else
814 : {
815 1244 : *hist_size = 0;
816 1244 : result = -1;
817 : }
818 :
819 2374 : return result;
820 : }
821 :
822 : /*
823 : * ineq_histogram_selectivity - Examine the histogram for scalarineqsel
824 : *
825 : * Determine the fraction of the variable's histogram population that
826 : * satisfies the inequality condition, ie, VAR < (or <=, >, >=) CONST.
827 : * The isgt and iseq flags distinguish which of the four cases apply.
828 : *
829 : * Returns -1 if there is no histogram (valid results will always be >= 0).
830 : *
831 : * Note that the result disregards both the most-common-values (if any) and
832 : * null entries. The caller is expected to combine this result with
833 : * statistics for those portions of the column population.
834 : *
835 : * This is exported so that some other estimation functions can use it.
836 : */
837 : double
838 145934 : ineq_histogram_selectivity(PlannerInfo *root,
839 : VariableStatData *vardata,
840 : FmgrInfo *opproc, bool isgt, bool iseq,
841 : Datum constval, Oid consttype)
842 : {
843 : double hist_selec;
844 : AttStatsSlot sslot;
845 :
846 145934 : hist_selec = -1.0;
847 :
848 : /*
849 : * Someday, ANALYZE might store more than one histogram per rel/att,
850 : * corresponding to more than one possible sort ordering defined for the
851 : * column type. However, to make that work we will need to figure out
852 : * which staop to search for --- it's not necessarily the one we have at
853 : * hand! (For example, we might have a '<=' operator rather than the '<'
854 : * operator that will appear in staop.) For now, assume that whatever
855 : * appears in pg_statistic is sorted the same way our operator sorts, or
856 : * the reverse way if isgt is true.
857 : */
858 291060 : if (HeapTupleIsValid(vardata->statsTuple) &&
859 290240 : statistic_proc_security_check(vardata, opproc->fn_oid) &&
860 145114 : get_attstatsslot(&sslot, vardata->statsTuple,
861 : STATISTIC_KIND_HISTOGRAM, InvalidOid,
862 : ATTSTATSSLOT_VALUES))
863 : {
864 124820 : if (sslot.nvalues > 1)
865 : {
866 : /*
867 : * Use binary search to find the desired location, namely the
868 : * right end of the histogram bin containing the comparison value,
869 : * which is the leftmost entry for which the comparison operator
870 : * succeeds (if isgt) or fails (if !isgt). (If the given operator
871 : * isn't actually sort-compatible with the histogram, you'll get
872 : * garbage results ... but probably not any more garbage-y than
873 : * you would have from the old linear search.)
874 : *
875 : * In this loop, we pay no attention to whether the operator iseq
876 : * or not; that detail will be mopped up below. (We cannot tell,
877 : * anyway, whether the operator thinks the values are equal.)
878 : *
879 : * If the binary search accesses the first or last histogram
880 : * entry, we try to replace that endpoint with the true column min
881 : * or max as found by get_actual_variable_range(). This
882 : * ameliorates misestimates when the min or max is moving as a
883 : * result of changes since the last ANALYZE. Note that this could
884 : * result in effectively including MCVs into the histogram that
885 : * weren't there before, but we don't try to correct for that.
886 : */
887 : double histfrac;
888 124820 : int lobound = 0; /* first possible slot to search */
889 124820 : int hibound = sslot.nvalues; /* last+1 slot to search */
890 124820 : bool have_end = false;
891 :
892 : /*
893 : * If there are only two histogram entries, we'll want up-to-date
894 : * values for both. (If there are more than two, we need at most
895 : * one of them to be updated, so we deal with that within the
896 : * loop.)
897 : */
898 124820 : if (sslot.nvalues == 2)
899 540 : have_end = get_actual_variable_range(root,
900 : vardata,
901 : sslot.staop,
902 : &sslot.values[0],
903 540 : &sslot.values[1]);
904 :
905 983318 : while (lobound < hibound)
906 : {
907 733678 : int probe = (lobound + hibound) / 2;
908 : bool ltcmp;
909 :
910 : /*
911 : * If we find ourselves about to compare to the first or last
912 : * histogram entry, first try to replace it with the actual
913 : * current min or max (unless we already did so above).
914 : */
915 733678 : if (probe == 0 && sslot.nvalues > 2)
916 63018 : have_end = get_actual_variable_range(root,
917 : vardata,
918 : sslot.staop,
919 : &sslot.values[0],
920 : NULL);
921 670660 : else if (probe == sslot.nvalues - 1 && sslot.nvalues > 2)
922 43674 : have_end = get_actual_variable_range(root,
923 : vardata,
924 : sslot.staop,
925 : NULL,
926 43674 : &sslot.values[probe]);
927 :
928 733678 : ltcmp = DatumGetBool(FunctionCall2Coll(opproc,
929 : sslot.stacoll,
930 : sslot.values[probe],
931 : constval));
932 733678 : if (isgt)
933 55980 : ltcmp = !ltcmp;
934 733678 : if (ltcmp)
935 275978 : lobound = probe + 1;
936 : else
937 457700 : hibound = probe;
938 : }
939 :
940 124820 : if (lobound <= 0)
941 : {
942 : /*
943 : * Constant is below lower histogram boundary. More
944 : * precisely, we have found that no entry in the histogram
945 : * satisfies the inequality clause (if !isgt) or they all do
946 : * (if isgt). We estimate that that's true of the entire
947 : * table, so set histfrac to 0.0 (which we'll flip to 1.0
948 : * below, if isgt).
949 : */
950 59040 : histfrac = 0.0;
951 : }
952 65780 : else if (lobound >= sslot.nvalues)
953 : {
954 : /*
955 : * Inverse case: constant is above upper histogram boundary.
956 : */
957 21694 : histfrac = 1.0;
958 : }
959 : else
960 : {
961 : /* We have values[i-1] <= constant <= values[i]. */
962 44086 : int i = lobound;
963 44086 : double eq_selec = 0;
964 : double val,
965 : high,
966 : low;
967 : double binfrac;
968 :
969 : /*
970 : * In the cases where we'll need it below, obtain an estimate
971 : * of the selectivity of "x = constval". We use a calculation
972 : * similar to what var_eq_const() does for a non-MCV constant,
973 : * ie, estimate that all distinct non-MCV values occur equally
974 : * often. But multiplication by "1.0 - sumcommon - nullfrac"
975 : * will be done by our caller, so we shouldn't do that here.
976 : * Therefore we can't try to clamp the estimate by reference
977 : * to the least common MCV; the result would be too small.
978 : *
979 : * Note: since this is effectively assuming that constval
980 : * isn't an MCV, it's logically dubious if constval in fact is
981 : * one. But we have to apply *some* correction for equality,
982 : * and anyway we cannot tell if constval is an MCV, since we
983 : * don't have a suitable equality operator at hand.
984 : */
985 44086 : if (i == 1 || isgt == iseq)
986 : {
987 : double otherdistinct;
988 : bool isdefault;
989 : AttStatsSlot mcvslot;
990 :
991 : /* Get estimated number of distinct values */
992 10640 : otherdistinct = get_variable_numdistinct(vardata,
993 : &isdefault);
994 :
995 : /* Subtract off the number of known MCVs */
996 10640 : if (get_attstatsslot(&mcvslot, vardata->statsTuple,
997 : STATISTIC_KIND_MCV, InvalidOid,
998 : ATTSTATSSLOT_NUMBERS))
999 : {
1000 2412 : otherdistinct -= mcvslot.nnumbers;
1001 2412 : free_attstatsslot(&mcvslot);
1002 : }
1003 :
1004 : /* If result doesn't seem sane, leave eq_selec at 0 */
1005 10640 : if (otherdistinct > 1)
1006 10640 : eq_selec = 1.0 / otherdistinct;
1007 : }
1008 :
1009 : /*
1010 : * Convert the constant and the two nearest bin boundary
1011 : * values to a uniform comparison scale, and do a linear
1012 : * interpolation within this bin.
1013 : */
1014 132258 : if (convert_to_scalar(constval, consttype, sslot.stacoll,
1015 : &val,
1016 88172 : sslot.values[i - 1], sslot.values[i],
1017 : vardata->vartype,
1018 : &low, &high))
1019 : {
1020 44082 : if (high <= low)
1021 : {
1022 : /* cope if bin boundaries appear identical */
1023 0 : binfrac = 0.5;
1024 : }
1025 44082 : else if (val <= low)
1026 7800 : binfrac = 0.0;
1027 36282 : else if (val >= high)
1028 902 : binfrac = 1.0;
1029 : else
1030 : {
1031 35380 : binfrac = (val - low) / (high - low);
1032 :
1033 : /*
1034 : * Watch out for the possibility that we got a NaN or
1035 : * Infinity from the division. This can happen
1036 : * despite the previous checks, if for example "low"
1037 : * is -Infinity.
1038 : */
1039 35380 : if (isnan(binfrac) ||
1040 35380 : binfrac < 0.0 || binfrac > 1.0)
1041 0 : binfrac = 0.5;
1042 : }
1043 : }
1044 : else
1045 : {
1046 : /*
1047 : * Ideally we'd produce an error here, on the grounds that
1048 : * the given operator shouldn't have scalarXXsel
1049 : * registered as its selectivity func unless we can deal
1050 : * with its operand types. But currently, all manner of
1051 : * stuff is invoking scalarXXsel, so give a default
1052 : * estimate until that can be fixed.
1053 : */
1054 4 : binfrac = 0.5;
1055 : }
1056 :
1057 : /*
1058 : * Now, compute the overall selectivity across the values
1059 : * represented by the histogram. We have i-1 full bins and
1060 : * binfrac partial bin below the constant.
1061 : */
1062 44086 : histfrac = (double) (i - 1) + binfrac;
1063 44086 : histfrac /= (double) (sslot.nvalues - 1);
1064 :
1065 : /*
1066 : * At this point, histfrac is an estimate of the fraction of
1067 : * the population represented by the histogram that satisfies
1068 : * "x <= constval". Somewhat remarkably, this statement is
1069 : * true regardless of which operator we were doing the probes
1070 : * with, so long as convert_to_scalar() delivers reasonable
1071 : * results. If the probe constant is equal to some histogram
1072 : * entry, we would have considered the bin to the left of that
1073 : * entry if probing with "<" or ">=", or the bin to the right
1074 : * if probing with "<=" or ">"; but binfrac would have come
1075 : * out as 1.0 in the first case and 0.0 in the second, leading
1076 : * to the same histfrac in either case. For probe constants
1077 : * between histogram entries, we find the same bin and get the
1078 : * same estimate with any operator.
1079 : *
1080 : * The fact that the estimate corresponds to "x <= constval"
1081 : * and not "x < constval" is because of the way that ANALYZE
1082 : * constructs the histogram: each entry is, effectively, the
1083 : * rightmost value in its sample bucket. So selectivity
1084 : * values that are exact multiples of 1/(histogram_size-1)
1085 : * should be understood as estimates including a histogram
1086 : * entry plus everything to its left.
1087 : *
1088 : * However, that breaks down for the first histogram entry,
1089 : * which necessarily is the leftmost value in its sample
1090 : * bucket. That means the first histogram bin is slightly
1091 : * narrower than the rest, by an amount equal to eq_selec.
1092 : * Another way to say that is that we want "x <= leftmost" to
1093 : * be estimated as eq_selec not zero. So, if we're dealing
1094 : * with the first bin (i==1), rescale to make that true while
1095 : * adjusting the rest of that bin linearly.
1096 : */
1097 44086 : if (i == 1)
1098 4316 : histfrac += eq_selec * (1.0 - binfrac);
1099 :
1100 : /*
1101 : * "x <= constval" is good if we want an estimate for "<=" or
1102 : * ">", but if we are estimating for "<" or ">=", we now need
1103 : * to decrease the estimate by eq_selec.
1104 : */
1105 44086 : if (isgt == iseq)
1106 9874 : histfrac -= eq_selec;
1107 : }
1108 :
1109 : /*
1110 : * Now the estimate is finished for "<" and "<=" cases. If we are
1111 : * estimating for ">" or ">=", flip it.
1112 : */
1113 124820 : hist_selec = isgt ? (1.0 - histfrac) : histfrac;
1114 :
1115 : /*
1116 : * The histogram boundaries are only approximate to begin with,
1117 : * and may well be out of date anyway. Therefore, don't believe
1118 : * extremely small or large selectivity estimates --- unless we
1119 : * got actual current endpoint values from the table, in which
1120 : * case just do the usual sanity clamp. Somewhat arbitrarily, we
1121 : * set the cutoff for other cases at a hundredth of the histogram
1122 : * resolution.
1123 : */
1124 124820 : if (have_end)
1125 64522 : CLAMP_PROBABILITY(hist_selec);
1126 : else
1127 : {
1128 60298 : double cutoff = 0.01 / (double) (sslot.nvalues - 1);
1129 :
1130 60298 : if (hist_selec < cutoff)
1131 18860 : hist_selec = cutoff;
1132 41438 : else if (hist_selec > 1.0 - cutoff)
1133 21232 : hist_selec = 1.0 - cutoff;
1134 : }
1135 : }
1136 :
1137 124820 : free_attstatsslot(&sslot);
1138 : }
1139 :
1140 145934 : return hist_selec;
1141 : }
1142 :
1143 : /*
1144 : * Common wrapper function for the selectivity estimators that simply
1145 : * invoke scalarineqsel().
1146 : */
1147 : static Datum
1148 29436 : scalarineqsel_wrapper(PG_FUNCTION_ARGS, bool isgt, bool iseq)
1149 : {
1150 29436 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
1151 29436 : Oid operator = PG_GETARG_OID(1);
1152 29436 : List *args = (List *) PG_GETARG_POINTER(2);
1153 29436 : int varRelid = PG_GETARG_INT32(3);
1154 : VariableStatData vardata;
1155 : Node *other;
1156 : bool varonleft;
1157 : Datum constval;
1158 : Oid consttype;
1159 : double selec;
1160 :
1161 : /*
1162 : * If expression is not variable op something or something op variable,
1163 : * then punt and return a default estimate.
1164 : */
1165 29436 : if (!get_restriction_variable(root, args, varRelid,
1166 : &vardata, &other, &varonleft))
1167 176 : PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
1168 :
1169 : /*
1170 : * Can't do anything useful if the something is not a constant, either.
1171 : */
1172 29260 : if (!IsA(other, Const))
1173 : {
1174 1760 : ReleaseVariableStats(vardata);
1175 1760 : PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
1176 : }
1177 :
1178 : /*
1179 : * If the constant is NULL, assume operator is strict and return zero, ie,
1180 : * operator will never return TRUE.
1181 : */
1182 27500 : if (((Const *) other)->constisnull)
1183 : {
1184 0 : ReleaseVariableStats(vardata);
1185 0 : PG_RETURN_FLOAT8(0.0);
1186 : }
1187 27500 : constval = ((Const *) other)->constvalue;
1188 27500 : consttype = ((Const *) other)->consttype;
1189 :
1190 : /*
1191 : * Force the var to be on the left to simplify logic in scalarineqsel.
1192 : */
1193 27500 : if (!varonleft)
1194 : {
1195 92 : operator = get_commutator(operator);
1196 92 : if (!operator)
1197 : {
1198 : /* Use default selectivity (should we raise an error instead?) */
1199 0 : ReleaseVariableStats(vardata);
1200 0 : PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
1201 : }
1202 92 : isgt = !isgt;
1203 : }
1204 :
1205 : /* The rest of the work is done by scalarineqsel(). */
1206 27500 : selec = scalarineqsel(root, operator, isgt, iseq,
1207 : &vardata, constval, consttype);
1208 :
1209 27500 : ReleaseVariableStats(vardata);
1210 :
1211 27500 : PG_RETURN_FLOAT8((float8) selec);
1212 : }
1213 :
1214 : /*
1215 : * scalarltsel - Selectivity of "<" for scalars.
1216 : */
1217 : Datum
1218 7708 : scalarltsel(PG_FUNCTION_ARGS)
1219 : {
1220 7708 : return scalarineqsel_wrapper(fcinfo, false, false);
1221 : }
1222 :
1223 : /*
1224 : * scalarlesel - Selectivity of "<=" for scalars.
1225 : */
1226 : Datum
1227 3124 : scalarlesel(PG_FUNCTION_ARGS)
1228 : {
1229 3124 : return scalarineqsel_wrapper(fcinfo, false, true);
1230 : }
1231 :
1232 : /*
1233 : * scalargtsel - Selectivity of ">" for scalars.
1234 : */
1235 : Datum
1236 11686 : scalargtsel(PG_FUNCTION_ARGS)
1237 : {
1238 11686 : return scalarineqsel_wrapper(fcinfo, true, false);
1239 : }
1240 :
1241 : /*
1242 : * scalargesel - Selectivity of ">=" for scalars.
1243 : */
1244 : Datum
1245 6918 : scalargesel(PG_FUNCTION_ARGS)
1246 : {
1247 6918 : return scalarineqsel_wrapper(fcinfo, true, true);
1248 : }
1249 :
1250 : /*
1251 : * boolvarsel - Selectivity of Boolean variable.
1252 : *
1253 : * This can actually be called on any boolean-valued expression. If it
1254 : * involves only Vars of the specified relation, and if there are statistics
1255 : * about the Var or expression (the latter is possible if it's indexed) then
1256 : * we'll produce a real estimate; otherwise it's just a default.
1257 : */
1258 : Selectivity
1259 15494 : boolvarsel(PlannerInfo *root, Node *arg, int varRelid)
1260 : {
1261 : VariableStatData vardata;
1262 : double selec;
1263 :
1264 15494 : examine_variable(root, arg, varRelid, &vardata);
1265 15494 : if (HeapTupleIsValid(vardata.statsTuple))
1266 : {
1267 : /*
1268 : * A boolean variable V is equivalent to the clause V = 't', so we
1269 : * compute the selectivity as if that is what we have.
1270 : */
1271 12776 : selec = var_eq_const(&vardata, BooleanEqualOperator,
1272 : BoolGetDatum(true), false, true, false);
1273 : }
1274 : else
1275 : {
1276 : /* Otherwise, the default estimate is 0.5 */
1277 2718 : selec = 0.5;
1278 : }
1279 15494 : ReleaseVariableStats(vardata);
1280 15494 : return selec;
1281 : }
1282 :
1283 : /*
1284 : * booltestsel - Selectivity of BooleanTest Node.
1285 : */
1286 : Selectivity
1287 132 : booltestsel(PlannerInfo *root, BoolTestType booltesttype, Node *arg,
1288 : int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
1289 : {
1290 : VariableStatData vardata;
1291 : double selec;
1292 :
1293 132 : examine_variable(root, arg, varRelid, &vardata);
1294 :
1295 132 : if (HeapTupleIsValid(vardata.statsTuple))
1296 : {
1297 : Form_pg_statistic stats;
1298 : double freq_null;
1299 : AttStatsSlot sslot;
1300 :
1301 0 : stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
1302 0 : freq_null = stats->stanullfrac;
1303 :
1304 0 : if (get_attstatsslot(&sslot, vardata.statsTuple,
1305 : STATISTIC_KIND_MCV, InvalidOid,
1306 : ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS)
1307 0 : && sslot.nnumbers > 0)
1308 0 : {
1309 : double freq_true;
1310 : double freq_false;
1311 :
1312 : /*
1313 : * Get first MCV frequency and derive frequency for true.
1314 : */
1315 0 : if (DatumGetBool(sslot.values[0]))
1316 0 : freq_true = sslot.numbers[0];
1317 : else
1318 0 : freq_true = 1.0 - sslot.numbers[0] - freq_null;
1319 :
1320 : /*
1321 : * Next derive frequency for false. Then use these as appropriate
1322 : * to derive frequency for each case.
1323 : */
1324 0 : freq_false = 1.0 - freq_true - freq_null;
1325 :
1326 0 : switch (booltesttype)
1327 : {
1328 : case IS_UNKNOWN:
1329 : /* select only NULL values */
1330 0 : selec = freq_null;
1331 0 : break;
1332 : case IS_NOT_UNKNOWN:
1333 : /* select non-NULL values */
1334 0 : selec = 1.0 - freq_null;
1335 0 : break;
1336 : case IS_TRUE:
1337 : /* select only TRUE values */
1338 0 : selec = freq_true;
1339 0 : break;
1340 : case IS_NOT_TRUE:
1341 : /* select non-TRUE values */
1342 0 : selec = 1.0 - freq_true;
1343 0 : break;
1344 : case IS_FALSE:
1345 : /* select only FALSE values */
1346 0 : selec = freq_false;
1347 0 : break;
1348 : case IS_NOT_FALSE:
1349 : /* select non-FALSE values */
1350 0 : selec = 1.0 - freq_false;
1351 0 : break;
1352 : default:
1353 0 : elog(ERROR, "unrecognized booltesttype: %d",
1354 : (int) booltesttype);
1355 : selec = 0.0; /* Keep compiler quiet */
1356 : break;
1357 : }
1358 :
1359 0 : free_attstatsslot(&sslot);
1360 : }
1361 : else
1362 : {
1363 : /*
1364 : * No most-common-value info available. Still have null fraction
1365 : * information, so use it for IS [NOT] UNKNOWN. Otherwise adjust
1366 : * for null fraction and assume a 50-50 split of TRUE and FALSE.
1367 : */
1368 0 : switch (booltesttype)
1369 : {
1370 : case IS_UNKNOWN:
1371 : /* select only NULL values */
1372 0 : selec = freq_null;
1373 0 : break;
1374 : case IS_NOT_UNKNOWN:
1375 : /* select non-NULL values */
1376 0 : selec = 1.0 - freq_null;
1377 0 : break;
1378 : case IS_TRUE:
1379 : case IS_FALSE:
1380 : /* Assume we select half of the non-NULL values */
1381 0 : selec = (1.0 - freq_null) / 2.0;
1382 0 : break;
1383 : case IS_NOT_TRUE:
1384 : case IS_NOT_FALSE:
1385 : /* Assume we select NULLs plus half of the non-NULLs */
1386 : /* equiv. to freq_null + (1.0 - freq_null) / 2.0 */
1387 0 : selec = (freq_null + 1.0) / 2.0;
1388 0 : break;
1389 : default:
1390 0 : elog(ERROR, "unrecognized booltesttype: %d",
1391 : (int) booltesttype);
1392 : selec = 0.0; /* Keep compiler quiet */
1393 : break;
1394 : }
1395 : }
1396 : }
1397 : else
1398 : {
1399 : /*
1400 : * If we can't get variable statistics for the argument, perhaps
1401 : * clause_selectivity can do something with it. We ignore the
1402 : * possibility of a NULL value when using clause_selectivity, and just
1403 : * assume the value is either TRUE or FALSE.
1404 : */
1405 132 : switch (booltesttype)
1406 : {
1407 : case IS_UNKNOWN:
1408 12 : selec = DEFAULT_UNK_SEL;
1409 12 : break;
1410 : case IS_NOT_UNKNOWN:
1411 12 : selec = DEFAULT_NOT_UNK_SEL;
1412 12 : break;
1413 : case IS_TRUE:
1414 : case IS_NOT_FALSE:
1415 32 : selec = (double) clause_selectivity(root, arg,
1416 : varRelid,
1417 : jointype, sjinfo);
1418 32 : break;
1419 : case IS_FALSE:
1420 : case IS_NOT_TRUE:
1421 76 : selec = 1.0 - (double) clause_selectivity(root, arg,
1422 : varRelid,
1423 : jointype, sjinfo);
1424 76 : break;
1425 : default:
1426 0 : elog(ERROR, "unrecognized booltesttype: %d",
1427 : (int) booltesttype);
1428 : selec = 0.0; /* Keep compiler quiet */
1429 : break;
1430 : }
1431 : }
1432 :
1433 132 : ReleaseVariableStats(vardata);
1434 :
1435 : /* result should be in range, but make sure... */
1436 132 : CLAMP_PROBABILITY(selec);
1437 :
1438 132 : return (Selectivity) selec;
1439 : }
1440 :
1441 : /*
1442 : * nulltestsel - Selectivity of NullTest Node.
1443 : */
1444 : Selectivity
1445 12286 : nulltestsel(PlannerInfo *root, NullTestType nulltesttype, Node *arg,
1446 : int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
1447 : {
1448 : VariableStatData vardata;
1449 : double selec;
1450 :
1451 12286 : examine_variable(root, arg, varRelid, &vardata);
1452 :
1453 12286 : if (HeapTupleIsValid(vardata.statsTuple))
1454 : {
1455 : Form_pg_statistic stats;
1456 : double freq_null;
1457 :
1458 3806 : stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
1459 3806 : freq_null = stats->stanullfrac;
1460 :
1461 3806 : switch (nulltesttype)
1462 : {
1463 : case IS_NULL:
1464 :
1465 : /*
1466 : * Use freq_null directly.
1467 : */
1468 3322 : selec = freq_null;
1469 3322 : break;
1470 : case IS_NOT_NULL:
1471 :
1472 : /*
1473 : * Select not unknown (not null) values. Calculate from
1474 : * freq_null.
1475 : */
1476 484 : selec = 1.0 - freq_null;
1477 484 : break;
1478 : default:
1479 0 : elog(ERROR, "unrecognized nulltesttype: %d",
1480 : (int) nulltesttype);
1481 : return (Selectivity) 0; /* keep compiler quiet */
1482 : }
1483 : }
1484 14340 : else if (vardata.var && IsA(vardata.var, Var) &&
1485 5860 : ((Var *) vardata.var)->varattno < 0)
1486 : {
1487 : /*
1488 : * There are no stats for system columns, but we know they are never
1489 : * NULL.
1490 : */
1491 0 : selec = (nulltesttype == IS_NULL) ? 0.0 : 1.0;
1492 : }
1493 : else
1494 : {
1495 : /*
1496 : * No ANALYZE stats available, so make a guess
1497 : */
1498 8480 : switch (nulltesttype)
1499 : {
1500 : case IS_NULL:
1501 938 : selec = DEFAULT_UNK_SEL;
1502 938 : break;
1503 : case IS_NOT_NULL:
1504 7542 : selec = DEFAULT_NOT_UNK_SEL;
1505 7542 : break;
1506 : default:
1507 0 : elog(ERROR, "unrecognized nulltesttype: %d",
1508 : (int) nulltesttype);
1509 : return (Selectivity) 0; /* keep compiler quiet */
1510 : }
1511 : }
1512 :
1513 12286 : ReleaseVariableStats(vardata);
1514 :
1515 : /* result should be in range, but make sure... */
1516 12286 : CLAMP_PROBABILITY(selec);
1517 :
1518 12286 : return (Selectivity) selec;
1519 : }
1520 :
1521 : /*
1522 : * strip_array_coercion - strip binary-compatible relabeling from an array expr
1523 : *
1524 : * For array values, the parser normally generates ArrayCoerceExpr conversions,
1525 : * but it seems possible that RelabelType might show up. Also, the planner
1526 : * is not currently tense about collapsing stacked ArrayCoerceExpr nodes,
1527 : * so we need to be ready to deal with more than one level.
1528 : */
1529 : static Node *
1530 62078 : strip_array_coercion(Node *node)
1531 : {
1532 : for (;;)
1533 : {
1534 62090 : if (node && IsA(node, ArrayCoerceExpr))
1535 12 : {
1536 224 : ArrayCoerceExpr *acoerce = (ArrayCoerceExpr *) node;
1537 :
1538 : /*
1539 : * If the per-element expression is just a RelabelType on top of
1540 : * CaseTestExpr, then we know it's a binary-compatible relabeling.
1541 : */
1542 236 : if (IsA(acoerce->elemexpr, RelabelType) &&
1543 12 : IsA(((RelabelType *) acoerce->elemexpr)->arg, CaseTestExpr))
1544 12 : node = (Node *) acoerce->arg;
1545 : else
1546 : break;
1547 : }
1548 61854 : else if (node && IsA(node, RelabelType))
1549 : {
1550 : /* We don't really expect this case, but may as well cope */
1551 0 : node = (Node *) ((RelabelType *) node)->arg;
1552 : }
1553 : else
1554 : break;
1555 : }
1556 62066 : return node;
1557 : }
1558 :
1559 : /*
1560 : * scalararraysel - Selectivity of ScalarArrayOpExpr Node.
1561 : */
1562 : Selectivity
1563 12718 : scalararraysel(PlannerInfo *root,
1564 : ScalarArrayOpExpr *clause,
1565 : bool is_join_clause,
1566 : int varRelid,
1567 : JoinType jointype,
1568 : SpecialJoinInfo *sjinfo)
1569 : {
1570 12718 : Oid operator = clause->opno;
1571 12718 : bool useOr = clause->useOr;
1572 12718 : bool isEquality = false;
1573 12718 : bool isInequality = false;
1574 : Node *leftop;
1575 : Node *rightop;
1576 : Oid nominal_element_type;
1577 : Oid nominal_element_collation;
1578 : TypeCacheEntry *typentry;
1579 : RegProcedure oprsel;
1580 : FmgrInfo oprselproc;
1581 : Selectivity s1;
1582 : Selectivity s1disjoint;
1583 :
1584 : /* First, deconstruct the expression */
1585 : Assert(list_length(clause->args) == 2);
1586 12718 : leftop = (Node *) linitial(clause->args);
1587 12718 : rightop = (Node *) lsecond(clause->args);
1588 :
1589 : /* aggressively reduce both sides to constants */
1590 12718 : leftop = estimate_expression_value(root, leftop);
1591 12718 : rightop = estimate_expression_value(root, rightop);
1592 :
1593 : /* get nominal (after relabeling) element type of rightop */
1594 12718 : nominal_element_type = get_base_element_type(exprType(rightop));
1595 12718 : if (!OidIsValid(nominal_element_type))
1596 0 : return (Selectivity) 0.5; /* probably shouldn't happen */
1597 : /* get nominal collation, too, for generating constants */
1598 12718 : nominal_element_collation = exprCollation(rightop);
1599 :
1600 : /* look through any binary-compatible relabeling of rightop */
1601 12718 : rightop = strip_array_coercion(rightop);
1602 :
1603 : /*
1604 : * Detect whether the operator is the default equality or inequality
1605 : * operator of the array element type.
1606 : */
1607 12718 : typentry = lookup_type_cache(nominal_element_type, TYPECACHE_EQ_OPR);
1608 12718 : if (OidIsValid(typentry->eq_opr))
1609 : {
1610 12718 : if (operator == typentry->eq_opr)
1611 12196 : isEquality = true;
1612 522 : else if (get_negator(operator) == typentry->eq_opr)
1613 426 : isInequality = true;
1614 : }
1615 :
1616 : /*
1617 : * If it is equality or inequality, we might be able to estimate this as a
1618 : * form of array containment; for instance "const = ANY(column)" can be
1619 : * treated as "ARRAY[const] <@ column". scalararraysel_containment tries
1620 : * that, and returns the selectivity estimate if successful, or -1 if not.
1621 : */
1622 12718 : if ((isEquality || isInequality) && !is_join_clause)
1623 : {
1624 12622 : s1 = scalararraysel_containment(root, leftop, rightop,
1625 : nominal_element_type,
1626 : isEquality, useOr, varRelid);
1627 12622 : if (s1 >= 0.0)
1628 38 : return s1;
1629 : }
1630 :
1631 : /*
1632 : * Look up the underlying operator's selectivity estimator. Punt if it
1633 : * hasn't got one.
1634 : */
1635 12680 : if (is_join_clause)
1636 0 : oprsel = get_oprjoin(operator);
1637 : else
1638 12680 : oprsel = get_oprrest(operator);
1639 12680 : if (!oprsel)
1640 0 : return (Selectivity) 0.5;
1641 12680 : fmgr_info(oprsel, &oprselproc);
1642 :
1643 : /*
1644 : * In the array-containment check above, we must only believe that an
1645 : * operator is equality or inequality if it is the default btree equality
1646 : * operator (or its negator) for the element type, since those are the
1647 : * operators that array containment will use. But in what follows, we can
1648 : * be a little laxer, and also believe that any operators using eqsel() or
1649 : * neqsel() as selectivity estimator act like equality or inequality.
1650 : */
1651 12680 : if (oprsel == F_EQSEL || oprsel == F_EQJOINSEL)
1652 12206 : isEquality = true;
1653 474 : else if (oprsel == F_NEQSEL || oprsel == F_NEQJOINSEL)
1654 402 : isInequality = true;
1655 :
1656 : /*
1657 : * We consider three cases:
1658 : *
1659 : * 1. rightop is an Array constant: deconstruct the array, apply the
1660 : * operator's selectivity function for each array element, and merge the
1661 : * results in the same way that clausesel.c does for AND/OR combinations.
1662 : *
1663 : * 2. rightop is an ARRAY[] construct: apply the operator's selectivity
1664 : * function for each element of the ARRAY[] construct, and merge.
1665 : *
1666 : * 3. otherwise, make a guess ...
1667 : */
1668 12680 : if (rightop && IsA(rightop, Const))
1669 6280 : {
1670 6280 : Datum arraydatum = ((Const *) rightop)->constvalue;
1671 6280 : bool arrayisnull = ((Const *) rightop)->constisnull;
1672 : ArrayType *arrayval;
1673 : int16 elmlen;
1674 : bool elmbyval;
1675 : char elmalign;
1676 : int num_elems;
1677 : Datum *elem_values;
1678 : bool *elem_nulls;
1679 : int i;
1680 :
1681 6280 : if (arrayisnull) /* qual can't succeed if null array */
1682 0 : return (Selectivity) 0.0;
1683 6280 : arrayval = DatumGetArrayTypeP(arraydatum);
1684 6280 : get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
1685 : &elmlen, &elmbyval, &elmalign);
1686 6280 : deconstruct_array(arrayval,
1687 : ARR_ELEMTYPE(arrayval),
1688 : elmlen, elmbyval, elmalign,
1689 : &elem_values, &elem_nulls, &num_elems);
1690 :
1691 : /*
1692 : * For generic operators, we assume the probability of success is
1693 : * independent for each array element. But for "= ANY" or "<> ALL",
1694 : * if the array elements are distinct (which'd typically be the case)
1695 : * then the probabilities are disjoint, and we should just sum them.
1696 : *
1697 : * If we were being really tense we would try to confirm that the
1698 : * elements are all distinct, but that would be expensive and it
1699 : * doesn't seem to be worth the cycles; it would amount to penalizing
1700 : * well-written queries in favor of poorly-written ones. However, we
1701 : * do protect ourselves a little bit by checking whether the
1702 : * disjointness assumption leads to an impossible (out of range)
1703 : * probability; if so, we fall back to the normal calculation.
1704 : */
1705 6280 : s1 = s1disjoint = (useOr ? 0.0 : 1.0);
1706 :
1707 26316 : for (i = 0; i < num_elems; i++)
1708 : {
1709 : List *args;
1710 : Selectivity s2;
1711 :
1712 20036 : args = list_make2(leftop,
1713 : makeConst(nominal_element_type,
1714 : -1,
1715 : nominal_element_collation,
1716 : elmlen,
1717 : elem_values[i],
1718 : elem_nulls[i],
1719 : elmbyval));
1720 20036 : if (is_join_clause)
1721 0 : s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
1722 : clause->inputcollid,
1723 : PointerGetDatum(root),
1724 : ObjectIdGetDatum(operator),
1725 : PointerGetDatum(args),
1726 : Int16GetDatum(jointype),
1727 : PointerGetDatum(sjinfo)));
1728 : else
1729 20036 : s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
1730 : clause->inputcollid,
1731 : PointerGetDatum(root),
1732 : ObjectIdGetDatum(operator),
1733 : PointerGetDatum(args),
1734 : Int32GetDatum(varRelid)));
1735 :
1736 20036 : if (useOr)
1737 : {
1738 18834 : s1 = s1 + s2 - s1 * s2;
1739 18834 : if (isEquality)
1740 18734 : s1disjoint += s2;
1741 : }
1742 : else
1743 : {
1744 1202 : s1 = s1 * s2;
1745 1202 : if (isInequality)
1746 1166 : s1disjoint += s2 - 1.0;
1747 : }
1748 : }
1749 :
1750 : /* accept disjoint-probability estimate if in range */
1751 6280 : if ((useOr ? isEquality : isInequality) &&
1752 6184 : s1disjoint >= 0.0 && s1disjoint <= 1.0)
1753 6164 : s1 = s1disjoint;
1754 : }
1755 6454 : else if (rightop && IsA(rightop, ArrayExpr) &&
1756 54 : !((ArrayExpr *) rightop)->multidims)
1757 54 : {
1758 54 : ArrayExpr *arrayexpr = (ArrayExpr *) rightop;
1759 : int16 elmlen;
1760 : bool elmbyval;
1761 : ListCell *l;
1762 :
1763 54 : get_typlenbyval(arrayexpr->element_typeid,
1764 : &elmlen, &elmbyval);
1765 :
1766 : /*
1767 : * We use the assumption of disjoint probabilities here too, although
1768 : * the odds of equal array elements are rather higher if the elements
1769 : * are not all constants (which they won't be, else constant folding
1770 : * would have reduced the ArrayExpr to a Const). In this path it's
1771 : * critical to have the sanity check on the s1disjoint estimate.
1772 : */
1773 54 : s1 = s1disjoint = (useOr ? 0.0 : 1.0);
1774 :
1775 200 : foreach(l, arrayexpr->elements)
1776 : {
1777 146 : Node *elem = (Node *) lfirst(l);
1778 : List *args;
1779 : Selectivity s2;
1780 :
1781 : /*
1782 : * Theoretically, if elem isn't of nominal_element_type we should
1783 : * insert a RelabelType, but it seems unlikely that any operator
1784 : * estimation function would really care ...
1785 : */
1786 146 : args = list_make2(leftop, elem);
1787 146 : if (is_join_clause)
1788 0 : s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
1789 : clause->inputcollid,
1790 : PointerGetDatum(root),
1791 : ObjectIdGetDatum(operator),
1792 : PointerGetDatum(args),
1793 : Int16GetDatum(jointype),
1794 : PointerGetDatum(sjinfo)));
1795 : else
1796 146 : s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
1797 : clause->inputcollid,
1798 : PointerGetDatum(root),
1799 : ObjectIdGetDatum(operator),
1800 : PointerGetDatum(args),
1801 : Int32GetDatum(varRelid)));
1802 :
1803 146 : if (useOr)
1804 : {
1805 146 : s1 = s1 + s2 - s1 * s2;
1806 146 : if (isEquality)
1807 146 : s1disjoint += s2;
1808 : }
1809 : else
1810 : {
1811 0 : s1 = s1 * s2;
1812 0 : if (isInequality)
1813 0 : s1disjoint += s2 - 1.0;
1814 : }
1815 : }
1816 :
1817 : /* accept disjoint-probability estimate if in range */
1818 54 : if ((useOr ? isEquality : isInequality) &&
1819 54 : s1disjoint >= 0.0 && s1disjoint <= 1.0)
1820 54 : s1 = s1disjoint;
1821 : }
1822 : else
1823 : {
1824 : CaseTestExpr *dummyexpr;
1825 : List *args;
1826 : Selectivity s2;
1827 : int i;
1828 :
1829 : /*
1830 : * We need a dummy rightop to pass to the operator selectivity
1831 : * routine. It can be pretty much anything that doesn't look like a
1832 : * constant; CaseTestExpr is a convenient choice.
1833 : */
1834 6346 : dummyexpr = makeNode(CaseTestExpr);
1835 6346 : dummyexpr->typeId = nominal_element_type;
1836 6346 : dummyexpr->typeMod = -1;
1837 6346 : dummyexpr->collation = clause->inputcollid;
1838 6346 : args = list_make2(leftop, dummyexpr);
1839 6346 : if (is_join_clause)
1840 0 : s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
1841 : clause->inputcollid,
1842 : PointerGetDatum(root),
1843 : ObjectIdGetDatum(operator),
1844 : PointerGetDatum(args),
1845 : Int16GetDatum(jointype),
1846 : PointerGetDatum(sjinfo)));
1847 : else
1848 6346 : s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
1849 : clause->inputcollid,
1850 : PointerGetDatum(root),
1851 : ObjectIdGetDatum(operator),
1852 : PointerGetDatum(args),
1853 : Int32GetDatum(varRelid)));
1854 6346 : s1 = useOr ? 0.0 : 1.0;
1855 :
1856 : /*
1857 : * Arbitrarily assume 10 elements in the eventual array value (see
1858 : * also estimate_array_length). We don't risk an assumption of
1859 : * disjoint probabilities here.
1860 : */
1861 69806 : for (i = 0; i < 10; i++)
1862 : {
1863 63460 : if (useOr)
1864 63460 : s1 = s1 + s2 - s1 * s2;
1865 : else
1866 0 : s1 = s1 * s2;
1867 : }
1868 : }
1869 :
1870 : /* result should be in range, but make sure... */
1871 12680 : CLAMP_PROBABILITY(s1);
1872 :
1873 12680 : return s1;
1874 : }
1875 :
1876 : /*
1877 : * Estimate number of elements in the array yielded by an expression.
1878 : *
1879 : * It's important that this agree with scalararraysel.
1880 : */
1881 : int
1882 49348 : estimate_array_length(Node *arrayexpr)
1883 : {
1884 : /* look through any binary-compatible relabeling of arrayexpr */
1885 49348 : arrayexpr = strip_array_coercion(arrayexpr);
1886 :
1887 49348 : if (arrayexpr && IsA(arrayexpr, Const))
1888 : {
1889 8718 : Datum arraydatum = ((Const *) arrayexpr)->constvalue;
1890 8718 : bool arrayisnull = ((Const *) arrayexpr)->constisnull;
1891 : ArrayType *arrayval;
1892 :
1893 8718 : if (arrayisnull)
1894 0 : return 0;
1895 8718 : arrayval = DatumGetArrayTypeP(arraydatum);
1896 8718 : return ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
1897 : }
1898 40726 : else if (arrayexpr && IsA(arrayexpr, ArrayExpr) &&
1899 96 : !((ArrayExpr *) arrayexpr)->multidims)
1900 : {
1901 96 : return list_length(((ArrayExpr *) arrayexpr)->elements);
1902 : }
1903 : else
1904 : {
1905 : /* default guess --- see also scalararraysel */
1906 40534 : return 10;
1907 : }
1908 : }
1909 :
1910 : /*
1911 : * rowcomparesel - Selectivity of RowCompareExpr Node.
1912 : *
1913 : * We estimate RowCompare selectivity by considering just the first (high
1914 : * order) columns, which makes it equivalent to an ordinary OpExpr. While
1915 : * this estimate could be refined by considering additional columns, it
1916 : * seems unlikely that we could do a lot better without multi-column
1917 : * statistics.
1918 : */
1919 : Selectivity
1920 104 : rowcomparesel(PlannerInfo *root,
1921 : RowCompareExpr *clause,
1922 : int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
1923 : {
1924 : Selectivity s1;
1925 104 : Oid opno = linitial_oid(clause->opnos);
1926 104 : Oid inputcollid = linitial_oid(clause->inputcollids);
1927 : List *opargs;
1928 : bool is_join_clause;
1929 :
1930 : /* Build equivalent arg list for single operator */
1931 104 : opargs = list_make2(linitial(clause->largs), linitial(clause->rargs));
1932 :
1933 : /*
1934 : * Decide if it's a join clause. This should match clausesel.c's
1935 : * treat_as_join_clause(), except that we intentionally consider only the
1936 : * leading columns and not the rest of the clause.
1937 : */
1938 104 : if (varRelid != 0)
1939 : {
1940 : /*
1941 : * Caller is forcing restriction mode (eg, because we are examining an
1942 : * inner indexscan qual).
1943 : */
1944 36 : is_join_clause = false;
1945 : }
1946 68 : else if (sjinfo == NULL)
1947 : {
1948 : /*
1949 : * It must be a restriction clause, since it's being evaluated at a
1950 : * scan node.
1951 : */
1952 60 : is_join_clause = false;
1953 : }
1954 : else
1955 : {
1956 : /*
1957 : * Otherwise, it's a join if there's more than one relation used.
1958 : */
1959 8 : is_join_clause = (NumRelids((Node *) opargs) > 1);
1960 : }
1961 :
1962 104 : if (is_join_clause)
1963 : {
1964 : /* Estimate selectivity for a join clause. */
1965 8 : s1 = join_selectivity(root, opno,
1966 : opargs,
1967 : inputcollid,
1968 : jointype,
1969 : sjinfo);
1970 : }
1971 : else
1972 : {
1973 : /* Estimate selectivity for a restriction clause. */
1974 96 : s1 = restriction_selectivity(root, opno,
1975 : opargs,
1976 : inputcollid,
1977 : varRelid);
1978 : }
1979 :
1980 104 : return s1;
1981 : }
1982 :
1983 : /*
1984 : * eqjoinsel - Join selectivity of "="
1985 : */
1986 : Datum
1987 110610 : eqjoinsel(PG_FUNCTION_ARGS)
1988 : {
1989 110610 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
1990 110610 : Oid operator = PG_GETARG_OID(1);
1991 110610 : List *args = (List *) PG_GETARG_POINTER(2);
1992 :
1993 : #ifdef NOT_USED
1994 : JoinType jointype = (JoinType) PG_GETARG_INT16(3);
1995 : #endif
1996 110610 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) PG_GETARG_POINTER(4);
1997 : double selec;
1998 : double selec_inner;
1999 : VariableStatData vardata1;
2000 : VariableStatData vardata2;
2001 : double nd1;
2002 : double nd2;
2003 : bool isdefault1;
2004 : bool isdefault2;
2005 : Oid opfuncoid;
2006 : AttStatsSlot sslot1;
2007 : AttStatsSlot sslot2;
2008 110610 : Form_pg_statistic stats1 = NULL;
2009 110610 : Form_pg_statistic stats2 = NULL;
2010 110610 : bool have_mcvs1 = false;
2011 110610 : bool have_mcvs2 = false;
2012 : bool join_is_reversed;
2013 : RelOptInfo *inner_rel;
2014 :
2015 110610 : get_join_variables(root, args, sjinfo,
2016 : &vardata1, &vardata2, &join_is_reversed);
2017 :
2018 110610 : nd1 = get_variable_numdistinct(&vardata1, &isdefault1);
2019 110610 : nd2 = get_variable_numdistinct(&vardata2, &isdefault2);
2020 :
2021 110610 : opfuncoid = get_opcode(operator);
2022 :
2023 110610 : memset(&sslot1, 0, sizeof(sslot1));
2024 110610 : memset(&sslot2, 0, sizeof(sslot2));
2025 :
2026 110610 : if (HeapTupleIsValid(vardata1.statsTuple))
2027 : {
2028 : /* note we allow use of nullfrac regardless of security check */
2029 69964 : stats1 = (Form_pg_statistic) GETSTRUCT(vardata1.statsTuple);
2030 69964 : if (statistic_proc_security_check(&vardata1, opfuncoid))
2031 69964 : have_mcvs1 = get_attstatsslot(&sslot1, vardata1.statsTuple,
2032 : STATISTIC_KIND_MCV, InvalidOid,
2033 : ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS);
2034 : }
2035 :
2036 110610 : if (HeapTupleIsValid(vardata2.statsTuple))
2037 : {
2038 : /* note we allow use of nullfrac regardless of security check */
2039 70880 : stats2 = (Form_pg_statistic) GETSTRUCT(vardata2.statsTuple);
2040 70880 : if (statistic_proc_security_check(&vardata2, opfuncoid))
2041 70880 : have_mcvs2 = get_attstatsslot(&sslot2, vardata2.statsTuple,
2042 : STATISTIC_KIND_MCV, InvalidOid,
2043 : ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS);
2044 : }
2045 :
2046 : /* We need to compute the inner-join selectivity in all cases */
2047 110610 : selec_inner = eqjoinsel_inner(opfuncoid,
2048 : &vardata1, &vardata2,
2049 : nd1, nd2,
2050 : isdefault1, isdefault2,
2051 : &sslot1, &sslot2,
2052 : stats1, stats2,
2053 : have_mcvs1, have_mcvs2);
2054 :
2055 110610 : switch (sjinfo->jointype)
2056 : {
2057 : case JOIN_INNER:
2058 : case JOIN_LEFT:
2059 : case JOIN_FULL:
2060 101344 : selec = selec_inner;
2061 101344 : break;
2062 : case JOIN_SEMI:
2063 : case JOIN_ANTI:
2064 :
2065 : /*
2066 : * Look up the join's inner relation. min_righthand is sufficient
2067 : * information because neither SEMI nor ANTI joins permit any
2068 : * reassociation into or out of their RHS, so the righthand will
2069 : * always be exactly that set of rels.
2070 : */
2071 9266 : inner_rel = find_join_input_rel(root, sjinfo->min_righthand);
2072 :
2073 9266 : if (!join_is_reversed)
2074 6846 : selec = eqjoinsel_semi(opfuncoid,
2075 : &vardata1, &vardata2,
2076 : nd1, nd2,
2077 : isdefault1, isdefault2,
2078 : &sslot1, &sslot2,
2079 : stats1, stats2,
2080 : have_mcvs1, have_mcvs2,
2081 : inner_rel);
2082 : else
2083 : {
2084 2420 : Oid commop = get_commutator(operator);
2085 2420 : Oid commopfuncoid = OidIsValid(commop) ? get_opcode(commop) : InvalidOid;
2086 :
2087 2420 : selec = eqjoinsel_semi(commopfuncoid,
2088 : &vardata2, &vardata1,
2089 : nd2, nd1,
2090 : isdefault2, isdefault1,
2091 : &sslot2, &sslot1,
2092 : stats2, stats1,
2093 : have_mcvs2, have_mcvs1,
2094 : inner_rel);
2095 : }
2096 :
2097 : /*
2098 : * We should never estimate the output of a semijoin to be more
2099 : * rows than we estimate for an inner join with the same input
2100 : * rels and join condition; it's obviously impossible for that to
2101 : * happen. The former estimate is N1 * Ssemi while the latter is
2102 : * N1 * N2 * Sinner, so we may clamp Ssemi <= N2 * Sinner. Doing
2103 : * this is worthwhile because of the shakier estimation rules we
2104 : * use in eqjoinsel_semi, particularly in cases where it has to
2105 : * punt entirely.
2106 : */
2107 9266 : selec = Min(selec, inner_rel->rows * selec_inner);
2108 9266 : break;
2109 : default:
2110 : /* other values not expected here */
2111 0 : elog(ERROR, "unrecognized join type: %d",
2112 : (int) sjinfo->jointype);
2113 : selec = 0; /* keep compiler quiet */
2114 : break;
2115 : }
2116 :
2117 110610 : free_attstatsslot(&sslot1);
2118 110610 : free_attstatsslot(&sslot2);
2119 :
2120 110610 : ReleaseVariableStats(vardata1);
2121 110610 : ReleaseVariableStats(vardata2);
2122 :
2123 110610 : CLAMP_PROBABILITY(selec);
2124 :
2125 110610 : PG_RETURN_FLOAT8((float8) selec);
2126 : }
2127 :
2128 : /*
2129 : * eqjoinsel_inner --- eqjoinsel for normal inner join
2130 : *
2131 : * We also use this for LEFT/FULL outer joins; it's not presently clear
2132 : * that it's worth trying to distinguish them here.
2133 : */
2134 : static double
2135 110610 : eqjoinsel_inner(Oid opfuncoid,
2136 : VariableStatData *vardata1, VariableStatData *vardata2,
2137 : double nd1, double nd2,
2138 : bool isdefault1, bool isdefault2,
2139 : AttStatsSlot *sslot1, AttStatsSlot *sslot2,
2140 : Form_pg_statistic stats1, Form_pg_statistic stats2,
2141 : bool have_mcvs1, bool have_mcvs2)
2142 : {
2143 : double selec;
2144 :
2145 110610 : if (have_mcvs1 && have_mcvs2)
2146 8422 : {
2147 : /*
2148 : * We have most-common-value lists for both relations. Run through
2149 : * the lists to see which MCVs actually join to each other with the
2150 : * given operator. This allows us to determine the exact join
2151 : * selectivity for the portion of the relations represented by the MCV
2152 : * lists. We still have to estimate for the remaining population, but
2153 : * in a skewed distribution this gives us a big leg up in accuracy.
2154 : * For motivation see the analysis in Y. Ioannidis and S.
2155 : * Christodoulakis, "On the propagation of errors in the size of join
2156 : * results", Technical Report 1018, Computer Science Dept., University
2157 : * of Wisconsin, Madison, March 1991 (available from ftp.cs.wisc.edu).
2158 : */
2159 : FmgrInfo eqproc;
2160 : bool *hasmatch1;
2161 : bool *hasmatch2;
2162 8422 : double nullfrac1 = stats1->stanullfrac;
2163 8422 : double nullfrac2 = stats2->stanullfrac;
2164 : double matchprodfreq,
2165 : matchfreq1,
2166 : matchfreq2,
2167 : unmatchfreq1,
2168 : unmatchfreq2,
2169 : otherfreq1,
2170 : otherfreq2,
2171 : totalsel1,
2172 : totalsel2;
2173 : int i,
2174 : nmatches;
2175 :
2176 8422 : fmgr_info(opfuncoid, &eqproc);
2177 8422 : hasmatch1 = (bool *) palloc0(sslot1->nvalues * sizeof(bool));
2178 8422 : hasmatch2 = (bool *) palloc0(sslot2->nvalues * sizeof(bool));
2179 :
2180 : /*
2181 : * Note we assume that each MCV will match at most one member of the
2182 : * other MCV list. If the operator isn't really equality, there could
2183 : * be multiple matches --- but we don't look for them, both for speed
2184 : * and because the math wouldn't add up...
2185 : */
2186 8422 : matchprodfreq = 0.0;
2187 8422 : nmatches = 0;
2188 200426 : for (i = 0; i < sslot1->nvalues; i++)
2189 : {
2190 : int j;
2191 :
2192 4977480 : for (j = 0; j < sslot2->nvalues; j++)
2193 : {
2194 4830378 : if (hasmatch2[j])
2195 1600192 : continue;
2196 3230186 : if (DatumGetBool(FunctionCall2Coll(&eqproc,
2197 : sslot1->stacoll,
2198 : sslot1->values[i],
2199 : sslot2->values[j])))
2200 : {
2201 44902 : hasmatch1[i] = hasmatch2[j] = true;
2202 44902 : matchprodfreq += sslot1->numbers[i] * sslot2->numbers[j];
2203 44902 : nmatches++;
2204 44902 : break;
2205 : }
2206 : }
2207 : }
2208 8422 : CLAMP_PROBABILITY(matchprodfreq);
2209 : /* Sum up frequencies of matched and unmatched MCVs */
2210 8422 : matchfreq1 = unmatchfreq1 = 0.0;
2211 200426 : for (i = 0; i < sslot1->nvalues; i++)
2212 : {
2213 192004 : if (hasmatch1[i])
2214 44902 : matchfreq1 += sslot1->numbers[i];
2215 : else
2216 147102 : unmatchfreq1 += sslot1->numbers[i];
2217 : }
2218 8422 : CLAMP_PROBABILITY(matchfreq1);
2219 8422 : CLAMP_PROBABILITY(unmatchfreq1);
2220 8422 : matchfreq2 = unmatchfreq2 = 0.0;
2221 393814 : for (i = 0; i < sslot2->nvalues; i++)
2222 : {
2223 385392 : if (hasmatch2[i])
2224 44902 : matchfreq2 += sslot2->numbers[i];
2225 : else
2226 340490 : unmatchfreq2 += sslot2->numbers[i];
2227 : }
2228 8422 : CLAMP_PROBABILITY(matchfreq2);
2229 8422 : CLAMP_PROBABILITY(unmatchfreq2);
2230 8422 : pfree(hasmatch1);
2231 8422 : pfree(hasmatch2);
2232 :
2233 : /*
2234 : * Compute total frequency of non-null values that are not in the MCV
2235 : * lists.
2236 : */
2237 8422 : otherfreq1 = 1.0 - nullfrac1 - matchfreq1 - unmatchfreq1;
2238 8422 : otherfreq2 = 1.0 - nullfrac2 - matchfreq2 - unmatchfreq2;
2239 8422 : CLAMP_PROBABILITY(otherfreq1);
2240 8422 : CLAMP_PROBABILITY(otherfreq2);
2241 :
2242 : /*
2243 : * We can estimate the total selectivity from the point of view of
2244 : * relation 1 as: the known selectivity for matched MCVs, plus
2245 : * unmatched MCVs that are assumed to match against random members of
2246 : * relation 2's non-MCV population, plus non-MCV values that are
2247 : * assumed to match against random members of relation 2's unmatched
2248 : * MCVs plus non-MCV values.
2249 : */
2250 8422 : totalsel1 = matchprodfreq;
2251 8422 : if (nd2 > sslot2->nvalues)
2252 7070 : totalsel1 += unmatchfreq1 * otherfreq2 / (nd2 - sslot2->nvalues);
2253 8422 : if (nd2 > nmatches)
2254 16036 : totalsel1 += otherfreq1 * (otherfreq2 + unmatchfreq2) /
2255 8018 : (nd2 - nmatches);
2256 : /* Same estimate from the point of view of relation 2. */
2257 8422 : totalsel2 = matchprodfreq;
2258 8422 : if (nd1 > sslot1->nvalues)
2259 6968 : totalsel2 += unmatchfreq2 * otherfreq1 / (nd1 - sslot1->nvalues);
2260 8422 : if (nd1 > nmatches)
2261 14568 : totalsel2 += otherfreq2 * (otherfreq1 + unmatchfreq1) /
2262 7284 : (nd1 - nmatches);
2263 :
2264 : /*
2265 : * Use the smaller of the two estimates. This can be justified in
2266 : * essentially the same terms as given below for the no-stats case: to
2267 : * a first approximation, we are estimating from the point of view of
2268 : * the relation with smaller nd.
2269 : */
2270 8422 : selec = (totalsel1 < totalsel2) ? totalsel1 : totalsel2;
2271 : }
2272 : else
2273 : {
2274 : /*
2275 : * We do not have MCV lists for both sides. Estimate the join
2276 : * selectivity as MIN(1/nd1,1/nd2)*(1-nullfrac1)*(1-nullfrac2). This
2277 : * is plausible if we assume that the join operator is strict and the
2278 : * non-null values are about equally distributed: a given non-null
2279 : * tuple of rel1 will join to either zero or N2*(1-nullfrac2)/nd2 rows
2280 : * of rel2, so total join rows are at most
2281 : * N1*(1-nullfrac1)*N2*(1-nullfrac2)/nd2 giving a join selectivity of
2282 : * not more than (1-nullfrac1)*(1-nullfrac2)/nd2. By the same logic it
2283 : * is not more than (1-nullfrac1)*(1-nullfrac2)/nd1, so the expression
2284 : * with MIN() is an upper bound. Using the MIN() means we estimate
2285 : * from the point of view of the relation with smaller nd (since the
2286 : * larger nd is determining the MIN). It is reasonable to assume that
2287 : * most tuples in this rel will have join partners, so the bound is
2288 : * probably reasonably tight and should be taken as-is.
2289 : *
2290 : * XXX Can we be smarter if we have an MCV list for just one side? It
2291 : * seems that if we assume equal distribution for the other side, we
2292 : * end up with the same answer anyway.
2293 : */
2294 102188 : double nullfrac1 = stats1 ? stats1->stanullfrac : 0.0;
2295 102188 : double nullfrac2 = stats2 ? stats2->stanullfrac : 0.0;
2296 :
2297 102188 : selec = (1.0 - nullfrac1) * (1.0 - nullfrac2);
2298 102188 : if (nd1 > nd2)
2299 33576 : selec /= nd1;
2300 : else
2301 68612 : selec /= nd2;
2302 : }
2303 :
2304 110610 : return selec;
2305 : }
2306 :
2307 : /*
2308 : * eqjoinsel_semi --- eqjoinsel for semi join
2309 : *
2310 : * (Also used for anti join, which we are supposed to estimate the same way.)
2311 : * Caller has ensured that vardata1 is the LHS variable.
2312 : * Unlike eqjoinsel_inner, we have to cope with opfuncoid being InvalidOid.
2313 : */
2314 : static double
2315 9266 : eqjoinsel_semi(Oid opfuncoid,
2316 : VariableStatData *vardata1, VariableStatData *vardata2,
2317 : double nd1, double nd2,
2318 : bool isdefault1, bool isdefault2,
2319 : AttStatsSlot *sslot1, AttStatsSlot *sslot2,
2320 : Form_pg_statistic stats1, Form_pg_statistic stats2,
2321 : bool have_mcvs1, bool have_mcvs2,
2322 : RelOptInfo *inner_rel)
2323 : {
2324 : double selec;
2325 :
2326 : /*
2327 : * We clamp nd2 to be not more than what we estimate the inner relation's
2328 : * size to be. This is intuitively somewhat reasonable since obviously
2329 : * there can't be more than that many distinct values coming from the
2330 : * inner rel. The reason for the asymmetry (ie, that we don't clamp nd1
2331 : * likewise) is that this is the only pathway by which restriction clauses
2332 : * applied to the inner rel will affect the join result size estimate,
2333 : * since set_joinrel_size_estimates will multiply SEMI/ANTI selectivity by
2334 : * only the outer rel's size. If we clamped nd1 we'd be double-counting
2335 : * the selectivity of outer-rel restrictions.
2336 : *
2337 : * We can apply this clamping both with respect to the base relation from
2338 : * which the join variable comes (if there is just one), and to the
2339 : * immediate inner input relation of the current join.
2340 : *
2341 : * If we clamp, we can treat nd2 as being a non-default estimate; it's not
2342 : * great, maybe, but it didn't come out of nowhere either. This is most
2343 : * helpful when the inner relation is empty and consequently has no stats.
2344 : */
2345 9266 : if (vardata2->rel)
2346 : {
2347 9266 : if (nd2 >= vardata2->rel->rows)
2348 : {
2349 8674 : nd2 = vardata2->rel->rows;
2350 8674 : isdefault2 = false;
2351 : }
2352 : }
2353 9266 : if (nd2 >= inner_rel->rows)
2354 : {
2355 8642 : nd2 = inner_rel->rows;
2356 8642 : isdefault2 = false;
2357 : }
2358 :
2359 9266 : if (have_mcvs1 && have_mcvs2 && OidIsValid(opfuncoid))
2360 44 : {
2361 : /*
2362 : * We have most-common-value lists for both relations. Run through
2363 : * the lists to see which MCVs actually join to each other with the
2364 : * given operator. This allows us to determine the exact join
2365 : * selectivity for the portion of the relations represented by the MCV
2366 : * lists. We still have to estimate for the remaining population, but
2367 : * in a skewed distribution this gives us a big leg up in accuracy.
2368 : */
2369 : FmgrInfo eqproc;
2370 : bool *hasmatch1;
2371 : bool *hasmatch2;
2372 44 : double nullfrac1 = stats1->stanullfrac;
2373 : double matchfreq1,
2374 : uncertainfrac,
2375 : uncertain;
2376 : int i,
2377 : nmatches,
2378 : clamped_nvalues2;
2379 :
2380 : /*
2381 : * The clamping above could have resulted in nd2 being less than
2382 : * sslot2->nvalues; in which case, we assume that precisely the nd2
2383 : * most common values in the relation will appear in the join input,
2384 : * and so compare to only the first nd2 members of the MCV list. Of
2385 : * course this is frequently wrong, but it's the best bet we can make.
2386 : */
2387 44 : clamped_nvalues2 = Min(sslot2->nvalues, nd2);
2388 :
2389 44 : fmgr_info(opfuncoid, &eqproc);
2390 44 : hasmatch1 = (bool *) palloc0(sslot1->nvalues * sizeof(bool));
2391 44 : hasmatch2 = (bool *) palloc0(clamped_nvalues2 * sizeof(bool));
2392 :
2393 : /*
2394 : * Note we assume that each MCV will match at most one member of the
2395 : * other MCV list. If the operator isn't really equality, there could
2396 : * be multiple matches --- but we don't look for them, both for speed
2397 : * and because the math wouldn't add up...
2398 : */
2399 44 : nmatches = 0;
2400 2724 : for (i = 0; i < sslot1->nvalues; i++)
2401 : {
2402 : int j;
2403 :
2404 103172 : for (j = 0; j < clamped_nvalues2; j++)
2405 : {
2406 102808 : if (hasmatch2[j])
2407 93232 : continue;
2408 9576 : if (DatumGetBool(FunctionCall2Coll(&eqproc,
2409 : sslot1->stacoll,
2410 : sslot1->values[i],
2411 : sslot2->values[j])))
2412 : {
2413 2316 : hasmatch1[i] = hasmatch2[j] = true;
2414 2316 : nmatches++;
2415 2316 : break;
2416 : }
2417 : }
2418 : }
2419 : /* Sum up frequencies of matched MCVs */
2420 44 : matchfreq1 = 0.0;
2421 2724 : for (i = 0; i < sslot1->nvalues; i++)
2422 : {
2423 2680 : if (hasmatch1[i])
2424 2316 : matchfreq1 += sslot1->numbers[i];
2425 : }
2426 44 : CLAMP_PROBABILITY(matchfreq1);
2427 44 : pfree(hasmatch1);
2428 44 : pfree(hasmatch2);
2429 :
2430 : /*
2431 : * Now we need to estimate the fraction of relation 1 that has at
2432 : * least one join partner. We know for certain that the matched MCVs
2433 : * do, so that gives us a lower bound, but we're really in the dark
2434 : * about everything else. Our crude approach is: if nd1 <= nd2 then
2435 : * assume all non-null rel1 rows have join partners, else assume for
2436 : * the uncertain rows that a fraction nd2/nd1 have join partners. We
2437 : * can discount the known-matched MCVs from the distinct-values counts
2438 : * before doing the division.
2439 : *
2440 : * Crude as the above is, it's completely useless if we don't have
2441 : * reliable ndistinct values for both sides. Hence, if either nd1 or
2442 : * nd2 is default, punt and assume half of the uncertain rows have
2443 : * join partners.
2444 : */
2445 44 : if (!isdefault1 && !isdefault2)
2446 : {
2447 44 : nd1 -= nmatches;
2448 44 : nd2 -= nmatches;
2449 88 : if (nd1 <= nd2 || nd2 < 0)
2450 32 : uncertainfrac = 1.0;
2451 : else
2452 12 : uncertainfrac = nd2 / nd1;
2453 : }
2454 : else
2455 0 : uncertainfrac = 0.5;
2456 44 : uncertain = 1.0 - matchfreq1 - nullfrac1;
2457 44 : CLAMP_PROBABILITY(uncertain);
2458 44 : selec = matchfreq1 + uncertainfrac * uncertain;
2459 : }
2460 : else
2461 : {
2462 : /*
2463 : * Without MCV lists for both sides, we can only use the heuristic
2464 : * about nd1 vs nd2.
2465 : */
2466 9222 : double nullfrac1 = stats1 ? stats1->stanullfrac : 0.0;
2467 :
2468 9222 : if (!isdefault1 && !isdefault2)
2469 : {
2470 16320 : if (nd1 <= nd2 || nd2 < 0)
2471 6926 : selec = 1.0 - nullfrac1;
2472 : else
2473 1234 : selec = (nd2 / nd1) * (1.0 - nullfrac1);
2474 : }
2475 : else
2476 1062 : selec = 0.5 * (1.0 - nullfrac1);
2477 : }
2478 :
2479 9266 : return selec;
2480 : }
2481 :
2482 : /*
2483 : * neqjoinsel - Join selectivity of "!="
2484 : */
2485 : Datum
2486 978 : neqjoinsel(PG_FUNCTION_ARGS)
2487 : {
2488 978 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
2489 978 : Oid operator = PG_GETARG_OID(1);
2490 978 : List *args = (List *) PG_GETARG_POINTER(2);
2491 978 : JoinType jointype = (JoinType) PG_GETARG_INT16(3);
2492 978 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) PG_GETARG_POINTER(4);
2493 : float8 result;
2494 :
2495 978 : if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
2496 274 : {
2497 : /*
2498 : * For semi-joins, if there is more than one distinct value in the RHS
2499 : * relation then every non-null LHS row must find a row to join since
2500 : * it can only be equal to one of them. We'll assume that there is
2501 : * always more than one distinct RHS value for the sake of stability,
2502 : * though in theory we could have special cases for empty RHS
2503 : * (selectivity = 0) and single-distinct-value RHS (selectivity =
2504 : * fraction of LHS that has the same value as the single RHS value).
2505 : *
2506 : * For anti-joins, if we use the same assumption that there is more
2507 : * than one distinct key in the RHS relation, then every non-null LHS
2508 : * row must be suppressed by the anti-join.
2509 : *
2510 : * So either way, the selectivity estimate should be 1 - nullfrac.
2511 : */
2512 : VariableStatData leftvar;
2513 : VariableStatData rightvar;
2514 : bool reversed;
2515 : HeapTuple statsTuple;
2516 : double nullfrac;
2517 :
2518 274 : get_join_variables(root, args, sjinfo, &leftvar, &rightvar, &reversed);
2519 274 : statsTuple = reversed ? rightvar.statsTuple : leftvar.statsTuple;
2520 274 : if (HeapTupleIsValid(statsTuple))
2521 180 : nullfrac = ((Form_pg_statistic) GETSTRUCT(statsTuple))->stanullfrac;
2522 : else
2523 94 : nullfrac = 0.0;
2524 274 : ReleaseVariableStats(leftvar);
2525 274 : ReleaseVariableStats(rightvar);
2526 :
2527 274 : result = 1.0 - nullfrac;
2528 : }
2529 : else
2530 : {
2531 : /*
2532 : * We want 1 - eqjoinsel() where the equality operator is the one
2533 : * associated with this != operator, that is, its negator.
2534 : */
2535 704 : Oid eqop = get_negator(operator);
2536 :
2537 704 : if (eqop)
2538 : {
2539 704 : result = DatumGetFloat8(DirectFunctionCall5(eqjoinsel,
2540 : PointerGetDatum(root),
2541 : ObjectIdGetDatum(eqop),
2542 : PointerGetDatum(args),
2543 : Int16GetDatum(jointype),
2544 : PointerGetDatum(sjinfo)));
2545 : }
2546 : else
2547 : {
2548 : /* Use default selectivity (should we raise an error instead?) */
2549 0 : result = DEFAULT_EQ_SEL;
2550 : }
2551 704 : result = 1.0 - result;
2552 : }
2553 :
2554 978 : PG_RETURN_FLOAT8(result);
2555 : }
2556 :
2557 : /*
2558 : * scalarltjoinsel - Join selectivity of "<" for scalars
2559 : */
2560 : Datum
2561 192 : scalarltjoinsel(PG_FUNCTION_ARGS)
2562 : {
2563 192 : PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
2564 : }
2565 :
2566 : /*
2567 : * scalarlejoinsel - Join selectivity of "<=" for scalars
2568 : */
2569 : Datum
2570 34 : scalarlejoinsel(PG_FUNCTION_ARGS)
2571 : {
2572 34 : PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
2573 : }
2574 :
2575 : /*
2576 : * scalargtjoinsel - Join selectivity of ">" for scalars
2577 : */
2578 : Datum
2579 140 : scalargtjoinsel(PG_FUNCTION_ARGS)
2580 : {
2581 140 : PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
2582 : }
2583 :
2584 : /*
2585 : * scalargejoinsel - Join selectivity of ">=" for scalars
2586 : */
2587 : Datum
2588 12 : scalargejoinsel(PG_FUNCTION_ARGS)
2589 : {
2590 12 : PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
2591 : }
2592 :
2593 :
2594 : /*
2595 : * mergejoinscansel - Scan selectivity of merge join.
2596 : *
2597 : * A merge join will stop as soon as it exhausts either input stream.
2598 : * Therefore, if we can estimate the ranges of both input variables,
2599 : * we can estimate how much of the input will actually be read. This
2600 : * can have a considerable impact on the cost when using indexscans.
2601 : *
2602 : * Also, we can estimate how much of each input has to be read before the
2603 : * first join pair is found, which will affect the join's startup time.
2604 : *
2605 : * clause should be a clause already known to be mergejoinable. opfamily,
2606 : * strategy, and nulls_first specify the sort ordering being used.
2607 : *
2608 : * The outputs are:
2609 : * *leftstart is set to the fraction of the left-hand variable expected
2610 : * to be scanned before the first join pair is found (0 to 1).
2611 : * *leftend is set to the fraction of the left-hand variable expected
2612 : * to be scanned before the join terminates (0 to 1).
2613 : * *rightstart, *rightend similarly for the right-hand variable.
2614 : */
2615 : void
2616 51024 : mergejoinscansel(PlannerInfo *root, Node *clause,
2617 : Oid opfamily, int strategy, bool nulls_first,
2618 : Selectivity *leftstart, Selectivity *leftend,
2619 : Selectivity *rightstart, Selectivity *rightend)
2620 : {
2621 : Node *left,
2622 : *right;
2623 : VariableStatData leftvar,
2624 : rightvar;
2625 : int op_strategy;
2626 : Oid op_lefttype;
2627 : Oid op_righttype;
2628 : Oid opno,
2629 : lsortop,
2630 : rsortop,
2631 : lstatop,
2632 : rstatop,
2633 : ltop,
2634 : leop,
2635 : revltop,
2636 : revleop;
2637 : bool isgt;
2638 : Datum leftmin,
2639 : leftmax,
2640 : rightmin,
2641 : rightmax;
2642 : double selec;
2643 :
2644 : /* Set default results if we can't figure anything out. */
2645 : /* XXX should default "start" fraction be a bit more than 0? */
2646 51024 : *leftstart = *rightstart = 0.0;
2647 51024 : *leftend = *rightend = 1.0;
2648 :
2649 : /* Deconstruct the merge clause */
2650 51024 : if (!is_opclause(clause))
2651 0 : return; /* shouldn't happen */
2652 51024 : opno = ((OpExpr *) clause)->opno;
2653 51024 : left = get_leftop((Expr *) clause);
2654 51024 : right = get_rightop((Expr *) clause);
2655 51024 : if (!right)
2656 0 : return; /* shouldn't happen */
2657 :
2658 : /* Look for stats for the inputs */
2659 51024 : examine_variable(root, left, 0, &leftvar);
2660 51024 : examine_variable(root, right, 0, &rightvar);
2661 :
2662 : /* Extract the operator's declared left/right datatypes */
2663 51024 : get_op_opfamily_properties(opno, opfamily, false,
2664 : &op_strategy,
2665 : &op_lefttype,
2666 : &op_righttype);
2667 : Assert(op_strategy == BTEqualStrategyNumber);
2668 :
2669 : /*
2670 : * Look up the various operators we need. If we don't find them all, it
2671 : * probably means the opfamily is broken, but we just fail silently.
2672 : *
2673 : * Note: we expect that pg_statistic histograms will be sorted by the '<'
2674 : * operator, regardless of which sort direction we are considering.
2675 : */
2676 51024 : switch (strategy)
2677 : {
2678 : case BTLessStrategyNumber:
2679 51020 : isgt = false;
2680 51020 : if (op_lefttype == op_righttype)
2681 : {
2682 : /* easy case */
2683 49896 : ltop = get_opfamily_member(opfamily,
2684 : op_lefttype, op_righttype,
2685 : BTLessStrategyNumber);
2686 49896 : leop = get_opfamily_member(opfamily,
2687 : op_lefttype, op_righttype,
2688 : BTLessEqualStrategyNumber);
2689 49896 : lsortop = ltop;
2690 49896 : rsortop = ltop;
2691 49896 : lstatop = lsortop;
2692 49896 : rstatop = rsortop;
2693 49896 : revltop = ltop;
2694 49896 : revleop = leop;
2695 : }
2696 : else
2697 : {
2698 1124 : ltop = get_opfamily_member(opfamily,
2699 : op_lefttype, op_righttype,
2700 : BTLessStrategyNumber);
2701 1124 : leop = get_opfamily_member(opfamily,
2702 : op_lefttype, op_righttype,
2703 : BTLessEqualStrategyNumber);
2704 1124 : lsortop = get_opfamily_member(opfamily,
2705 : op_lefttype, op_lefttype,
2706 : BTLessStrategyNumber);
2707 1124 : rsortop = get_opfamily_member(opfamily,
2708 : op_righttype, op_righttype,
2709 : BTLessStrategyNumber);
2710 1124 : lstatop = lsortop;
2711 1124 : rstatop = rsortop;
2712 1124 : revltop = get_opfamily_member(opfamily,
2713 : op_righttype, op_lefttype,
2714 : BTLessStrategyNumber);
2715 1124 : revleop = get_opfamily_member(opfamily,
2716 : op_righttype, op_lefttype,
2717 : BTLessEqualStrategyNumber);
2718 : }
2719 51020 : break;
2720 : case BTGreaterStrategyNumber:
2721 : /* descending-order case */
2722 4 : isgt = true;
2723 4 : if (op_lefttype == op_righttype)
2724 : {
2725 : /* easy case */
2726 4 : ltop = get_opfamily_member(opfamily,
2727 : op_lefttype, op_righttype,
2728 : BTGreaterStrategyNumber);
2729 4 : leop = get_opfamily_member(opfamily,
2730 : op_lefttype, op_righttype,
2731 : BTGreaterEqualStrategyNumber);
2732 4 : lsortop = ltop;
2733 4 : rsortop = ltop;
2734 4 : lstatop = get_opfamily_member(opfamily,
2735 : op_lefttype, op_lefttype,
2736 : BTLessStrategyNumber);
2737 4 : rstatop = lstatop;
2738 4 : revltop = ltop;
2739 4 : revleop = leop;
2740 : }
2741 : else
2742 : {
2743 0 : ltop = get_opfamily_member(opfamily,
2744 : op_lefttype, op_righttype,
2745 : BTGreaterStrategyNumber);
2746 0 : leop = get_opfamily_member(opfamily,
2747 : op_lefttype, op_righttype,
2748 : BTGreaterEqualStrategyNumber);
2749 0 : lsortop = get_opfamily_member(opfamily,
2750 : op_lefttype, op_lefttype,
2751 : BTGreaterStrategyNumber);
2752 0 : rsortop = get_opfamily_member(opfamily,
2753 : op_righttype, op_righttype,
2754 : BTGreaterStrategyNumber);
2755 0 : lstatop = get_opfamily_member(opfamily,
2756 : op_lefttype, op_lefttype,
2757 : BTLessStrategyNumber);
2758 0 : rstatop = get_opfamily_member(opfamily,
2759 : op_righttype, op_righttype,
2760 : BTLessStrategyNumber);
2761 0 : revltop = get_opfamily_member(opfamily,
2762 : op_righttype, op_lefttype,
2763 : BTGreaterStrategyNumber);
2764 0 : revleop = get_opfamily_member(opfamily,
2765 : op_righttype, op_lefttype,
2766 : BTGreaterEqualStrategyNumber);
2767 : }
2768 4 : break;
2769 : default:
2770 0 : goto fail; /* shouldn't get here */
2771 : }
2772 :
2773 51024 : if (!OidIsValid(lsortop) ||
2774 51024 : !OidIsValid(rsortop) ||
2775 51024 : !OidIsValid(lstatop) ||
2776 51024 : !OidIsValid(rstatop) ||
2777 51016 : !OidIsValid(ltop) ||
2778 51016 : !OidIsValid(leop) ||
2779 51016 : !OidIsValid(revltop) ||
2780 : !OidIsValid(revleop))
2781 : goto fail; /* insufficient info in catalogs */
2782 :
2783 : /* Try to get ranges of both inputs */
2784 51016 : if (!isgt)
2785 : {
2786 51012 : if (!get_variable_range(root, &leftvar, lstatop,
2787 : &leftmin, &leftmax))
2788 15276 : goto fail; /* no range available from stats */
2789 35736 : if (!get_variable_range(root, &rightvar, rstatop,
2790 : &rightmin, &rightmax))
2791 3208 : goto fail; /* no range available from stats */
2792 : }
2793 : else
2794 : {
2795 : /* need to swap the max and min */
2796 4 : if (!get_variable_range(root, &leftvar, lstatop,
2797 : &leftmax, &leftmin))
2798 4 : goto fail; /* no range available from stats */
2799 0 : if (!get_variable_range(root, &rightvar, rstatop,
2800 : &rightmax, &rightmin))
2801 0 : goto fail; /* no range available from stats */
2802 : }
2803 :
2804 : /*
2805 : * Now, the fraction of the left variable that will be scanned is the
2806 : * fraction that's <= the right-side maximum value. But only believe
2807 : * non-default estimates, else stick with our 1.0.
2808 : */
2809 32528 : selec = scalarineqsel(root, leop, isgt, true, &leftvar,
2810 : rightmax, op_righttype);
2811 32528 : if (selec != DEFAULT_INEQ_SEL)
2812 32524 : *leftend = selec;
2813 :
2814 : /* And similarly for the right variable. */
2815 32528 : selec = scalarineqsel(root, revleop, isgt, true, &rightvar,
2816 : leftmax, op_lefttype);
2817 32528 : if (selec != DEFAULT_INEQ_SEL)
2818 32528 : *rightend = selec;
2819 :
2820 : /*
2821 : * Only one of the two "end" fractions can really be less than 1.0;
2822 : * believe the smaller estimate and reset the other one to exactly 1.0. If
2823 : * we get exactly equal estimates (as can easily happen with self-joins),
2824 : * believe neither.
2825 : */
2826 32528 : if (*leftend > *rightend)
2827 19492 : *leftend = 1.0;
2828 13036 : else if (*leftend < *rightend)
2829 11252 : *rightend = 1.0;
2830 : else
2831 1784 : *leftend = *rightend = 1.0;
2832 :
2833 : /*
2834 : * Also, the fraction of the left variable that will be scanned before the
2835 : * first join pair is found is the fraction that's < the right-side
2836 : * minimum value. But only believe non-default estimates, else stick with
2837 : * our own default.
2838 : */
2839 32528 : selec = scalarineqsel(root, ltop, isgt, false, &leftvar,
2840 : rightmin, op_righttype);
2841 32528 : if (selec != DEFAULT_INEQ_SEL)
2842 32528 : *leftstart = selec;
2843 :
2844 : /* And similarly for the right variable. */
2845 32528 : selec = scalarineqsel(root, revltop, isgt, false, &rightvar,
2846 : leftmin, op_lefttype);
2847 32528 : if (selec != DEFAULT_INEQ_SEL)
2848 32528 : *rightstart = selec;
2849 :
2850 : /*
2851 : * Only one of the two "start" fractions can really be more than zero;
2852 : * believe the larger estimate and reset the other one to exactly 0.0. If
2853 : * we get exactly equal estimates (as can easily happen with self-joins),
2854 : * believe neither.
2855 : */
2856 32528 : if (*leftstart < *rightstart)
2857 8676 : *leftstart = 0.0;
2858 23852 : else if (*leftstart > *rightstart)
2859 18168 : *rightstart = 0.0;
2860 : else
2861 5684 : *leftstart = *rightstart = 0.0;
2862 :
2863 : /*
2864 : * If the sort order is nulls-first, we're going to have to skip over any
2865 : * nulls too. These would not have been counted by scalarineqsel, and we
2866 : * can safely add in this fraction regardless of whether we believe
2867 : * scalarineqsel's results or not. But be sure to clamp the sum to 1.0!
2868 : */
2869 32528 : if (nulls_first)
2870 : {
2871 : Form_pg_statistic stats;
2872 :
2873 0 : if (HeapTupleIsValid(leftvar.statsTuple))
2874 : {
2875 0 : stats = (Form_pg_statistic) GETSTRUCT(leftvar.statsTuple);
2876 0 : *leftstart += stats->stanullfrac;
2877 0 : CLAMP_PROBABILITY(*leftstart);
2878 0 : *leftend += stats->stanullfrac;
2879 0 : CLAMP_PROBABILITY(*leftend);
2880 : }
2881 0 : if (HeapTupleIsValid(rightvar.statsTuple))
2882 : {
2883 0 : stats = (Form_pg_statistic) GETSTRUCT(rightvar.statsTuple);
2884 0 : *rightstart += stats->stanullfrac;
2885 0 : CLAMP_PROBABILITY(*rightstart);
2886 0 : *rightend += stats->stanullfrac;
2887 0 : CLAMP_PROBABILITY(*rightend);
2888 : }
2889 : }
2890 :
2891 : /* Disbelieve start >= end, just in case that can happen */
2892 32528 : if (*leftstart >= *leftend)
2893 : {
2894 660 : *leftstart = 0.0;
2895 660 : *leftend = 1.0;
2896 : }
2897 32528 : if (*rightstart >= *rightend)
2898 : {
2899 972 : *rightstart = 0.0;
2900 972 : *rightend = 1.0;
2901 : }
2902 :
2903 : fail:
2904 51024 : ReleaseVariableStats(leftvar);
2905 51024 : ReleaseVariableStats(rightvar);
2906 : }
2907 :
2908 :
2909 : /*
2910 : * Helper routine for estimate_num_groups: add an item to a list of
2911 : * GroupVarInfos, but only if it's not known equal to any of the existing
2912 : * entries.
2913 : */
2914 : typedef struct
2915 : {
2916 : Node *var; /* might be an expression, not just a Var */
2917 : RelOptInfo *rel; /* relation it belongs to */
2918 : double ndistinct; /* # distinct values */
2919 : } GroupVarInfo;
2920 :
2921 : static List *
2922 8754 : add_unique_group_var(PlannerInfo *root, List *varinfos,
2923 : Node *var, VariableStatData *vardata)
2924 : {
2925 : GroupVarInfo *varinfo;
2926 : double ndistinct;
2927 : bool isdefault;
2928 : ListCell *lc;
2929 :
2930 8754 : ndistinct = get_variable_numdistinct(vardata, &isdefault);
2931 :
2932 : /* cannot use foreach here because of possible list_delete */
2933 8754 : lc = list_head(varinfos);
2934 20100 : while (lc)
2935 : {
2936 2784 : varinfo = (GroupVarInfo *) lfirst(lc);
2937 :
2938 : /* must advance lc before list_delete possibly pfree's it */
2939 2784 : lc = lnext(lc);
2940 :
2941 : /* Drop exact duplicates */
2942 2784 : if (equal(var, varinfo->var))
2943 140 : return varinfos;
2944 :
2945 : /*
2946 : * Drop known-equal vars, but only if they belong to different
2947 : * relations (see comments for estimate_num_groups)
2948 : */
2949 3024 : if (vardata->rel != varinfo->rel &&
2950 380 : exprs_known_equal(root, var, varinfo->var))
2951 : {
2952 56 : if (varinfo->ndistinct <= ndistinct)
2953 : {
2954 : /* Keep older item, forget new one */
2955 52 : return varinfos;
2956 : }
2957 : else
2958 : {
2959 : /* Delete the older item */
2960 4 : varinfos = list_delete_ptr(varinfos, varinfo);
2961 : }
2962 : }
2963 : }
2964 :
2965 8562 : varinfo = (GroupVarInfo *) palloc(sizeof(GroupVarInfo));
2966 :
2967 8562 : varinfo->var = var;
2968 8562 : varinfo->rel = vardata->rel;
2969 8562 : varinfo->ndistinct = ndistinct;
2970 8562 : varinfos = lappend(varinfos, varinfo);
2971 8562 : return varinfos;
2972 : }
2973 :
2974 : /*
2975 : * estimate_num_groups - Estimate number of groups in a grouped query
2976 : *
2977 : * Given a query having a GROUP BY clause, estimate how many groups there
2978 : * will be --- ie, the number of distinct combinations of the GROUP BY
2979 : * expressions.
2980 : *
2981 : * This routine is also used to estimate the number of rows emitted by
2982 : * a DISTINCT filtering step; that is an isomorphic problem. (Note:
2983 : * actually, we only use it for DISTINCT when there's no grouping or
2984 : * aggregation ahead of the DISTINCT.)
2985 : *
2986 : * Inputs:
2987 : * root - the query
2988 : * groupExprs - list of expressions being grouped by
2989 : * input_rows - number of rows estimated to arrive at the group/unique
2990 : * filter step
2991 : * pgset - NULL, or a List** pointing to a grouping set to filter the
2992 : * groupExprs against
2993 : *
2994 : * Given the lack of any cross-correlation statistics in the system, it's
2995 : * impossible to do anything really trustworthy with GROUP BY conditions
2996 : * involving multiple Vars. We should however avoid assuming the worst
2997 : * case (all possible cross-product terms actually appear as groups) since
2998 : * very often the grouped-by Vars are highly correlated. Our current approach
2999 : * is as follows:
3000 : * 1. Expressions yielding boolean are assumed to contribute two groups,
3001 : * independently of their content, and are ignored in the subsequent
3002 : * steps. This is mainly because tests like "col IS NULL" break the
3003 : * heuristic used in step 2 especially badly.
3004 : * 2. Reduce the given expressions to a list of unique Vars used. For
3005 : * example, GROUP BY a, a + b is treated the same as GROUP BY a, b.
3006 : * It is clearly correct not to count the same Var more than once.
3007 : * It is also reasonable to treat f(x) the same as x: f() cannot
3008 : * increase the number of distinct values (unless it is volatile,
3009 : * which we consider unlikely for grouping), but it probably won't
3010 : * reduce the number of distinct values much either.
3011 : * As a special case, if a GROUP BY expression can be matched to an
3012 : * expressional index for which we have statistics, then we treat the
3013 : * whole expression as though it were just a Var.
3014 : * 3. If the list contains Vars of different relations that are known equal
3015 : * due to equivalence classes, then drop all but one of the Vars from each
3016 : * known-equal set, keeping the one with smallest estimated # of values
3017 : * (since the extra values of the others can't appear in joined rows).
3018 : * Note the reason we only consider Vars of different relations is that
3019 : * if we considered ones of the same rel, we'd be double-counting the
3020 : * restriction selectivity of the equality in the next step.
3021 : * 4. For Vars within a single source rel, we multiply together the numbers
3022 : * of values, clamp to the number of rows in the rel (divided by 10 if
3023 : * more than one Var), and then multiply by a factor based on the
3024 : * selectivity of the restriction clauses for that rel. When there's
3025 : * more than one Var, the initial product is probably too high (it's the
3026 : * worst case) but clamping to a fraction of the rel's rows seems to be a
3027 : * helpful heuristic for not letting the estimate get out of hand. (The
3028 : * factor of 10 is derived from pre-Postgres-7.4 practice.) The factor
3029 : * we multiply by to adjust for the restriction selectivity assumes that
3030 : * the restriction clauses are independent of the grouping, which may not
3031 : * be a valid assumption, but it's hard to do better.
3032 : * 5. If there are Vars from multiple rels, we repeat step 4 for each such
3033 : * rel, and multiply the results together.
3034 : * Note that rels not containing grouped Vars are ignored completely, as are
3035 : * join clauses. Such rels cannot increase the number of groups, and we
3036 : * assume such clauses do not reduce the number either (somewhat bogus,
3037 : * but we don't have the info to do better).
3038 : */
3039 : double
3040 7220 : estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
3041 : List **pgset)
3042 : {
3043 7220 : List *varinfos = NIL;
3044 7220 : double srf_multiplier = 1.0;
3045 : double numdistinct;
3046 : ListCell *l;
3047 : int i;
3048 :
3049 : /*
3050 : * We don't ever want to return an estimate of zero groups, as that tends
3051 : * to lead to division-by-zero and other unpleasantness. The input_rows
3052 : * estimate is usually already at least 1, but clamp it just in case it
3053 : * isn't.
3054 : */
3055 7220 : input_rows = clamp_row_est(input_rows);
3056 :
3057 : /*
3058 : * If no grouping columns, there's exactly one group. (This can't happen
3059 : * for normal cases with GROUP BY or DISTINCT, but it is possible for
3060 : * corner cases with set operations.)
3061 : */
3062 7220 : if (groupExprs == NIL || (pgset && list_length(*pgset) < 1))
3063 416 : return 1.0;
3064 :
3065 : /*
3066 : * Count groups derived from boolean grouping expressions. For other
3067 : * expressions, find the unique Vars used, treating an expression as a Var
3068 : * if we can find stats for it. For each one, record the statistical
3069 : * estimate of number of distinct values (total in its table, without
3070 : * regard for filtering).
3071 : */
3072 6804 : numdistinct = 1.0;
3073 :
3074 6804 : i = 0;
3075 16040 : foreach(l, groupExprs)
3076 : {
3077 9240 : Node *groupexpr = (Node *) lfirst(l);
3078 : double this_srf_multiplier;
3079 : VariableStatData vardata;
3080 : List *varshere;
3081 : ListCell *l2;
3082 :
3083 : /* is expression in this grouping set? */
3084 9240 : if (pgset && !list_member_int(*pgset, i++))
3085 5394 : continue;
3086 :
3087 : /*
3088 : * Set-returning functions in grouping columns are a bit problematic.
3089 : * The code below will effectively ignore their SRF nature and come up
3090 : * with a numdistinct estimate as though they were scalar functions.
3091 : * We compensate by scaling up the end result by the largest SRF
3092 : * rowcount estimate. (This will be an overestimate if the SRF
3093 : * produces multiple copies of any output value, but it seems best to
3094 : * assume the SRF's outputs are distinct. In any case, it's probably
3095 : * pointless to worry too much about this without much better
3096 : * estimates for SRF output rowcounts than we have today.)
3097 : */
3098 8972 : this_srf_multiplier = expression_returns_set_rows(root, groupexpr);
3099 8972 : if (srf_multiplier < this_srf_multiplier)
3100 72 : srf_multiplier = this_srf_multiplier;
3101 :
3102 : /* Short-circuit for expressions returning boolean */
3103 8972 : if (exprType(groupexpr) == BOOLOID)
3104 : {
3105 24 : numdistinct *= 2.0;
3106 24 : continue;
3107 : }
3108 :
3109 : /*
3110 : * If examine_variable is able to deduce anything about the GROUP BY
3111 : * expression, treat it as a single variable even if it's really more
3112 : * complicated.
3113 : */
3114 8948 : examine_variable(root, groupexpr, 0, &vardata);
3115 8948 : if (HeapTupleIsValid(vardata.statsTuple) || vardata.isunique)
3116 : {
3117 4548 : varinfos = add_unique_group_var(root, varinfos,
3118 : groupexpr, &vardata);
3119 4548 : ReleaseVariableStats(vardata);
3120 4548 : continue;
3121 : }
3122 4400 : ReleaseVariableStats(vardata);
3123 :
3124 : /*
3125 : * Else pull out the component Vars. Handle PlaceHolderVars by
3126 : * recursing into their arguments (effectively assuming that the
3127 : * PlaceHolderVar doesn't change the number of groups, which boils
3128 : * down to ignoring the possible addition of nulls to the result set).
3129 : */
3130 4400 : varshere = pull_var_clause(groupexpr,
3131 : PVC_RECURSE_AGGREGATES |
3132 : PVC_RECURSE_WINDOWFUNCS |
3133 : PVC_RECURSE_PLACEHOLDERS);
3134 :
3135 : /*
3136 : * If we find any variable-free GROUP BY item, then either it is a
3137 : * constant (and we can ignore it) or it contains a volatile function;
3138 : * in the latter case we punt and assume that each input row will
3139 : * yield a distinct group.
3140 : */
3141 4400 : if (varshere == NIL)
3142 : {
3143 290 : if (contain_volatile_functions(groupexpr))
3144 4 : return input_rows;
3145 286 : continue;
3146 : }
3147 :
3148 : /*
3149 : * Else add variables to varinfos list
3150 : */
3151 8316 : foreach(l2, varshere)
3152 : {
3153 4206 : Node *var = (Node *) lfirst(l2);
3154 :
3155 4206 : examine_variable(root, var, 0, &vardata);
3156 4206 : varinfos = add_unique_group_var(root, varinfos, var, &vardata);
3157 4206 : ReleaseVariableStats(vardata);
3158 : }
3159 : }
3160 :
3161 : /*
3162 : * If now no Vars, we must have an all-constant or all-boolean GROUP BY
3163 : * list.
3164 : */
3165 6800 : if (varinfos == NIL)
3166 : {
3167 : /* Apply SRF multiplier as we would do in the long path */
3168 148 : numdistinct *= srf_multiplier;
3169 : /* Round off */
3170 148 : numdistinct = ceil(numdistinct);
3171 : /* Guard against out-of-range answers */
3172 148 : if (numdistinct > input_rows)
3173 0 : numdistinct = input_rows;
3174 148 : if (numdistinct < 1.0)
3175 0 : numdistinct = 1.0;
3176 148 : return numdistinct;
3177 : }
3178 :
3179 : /*
3180 : * Group Vars by relation and estimate total numdistinct.
3181 : *
3182 : * For each iteration of the outer loop, we process the frontmost Var in
3183 : * varinfos, plus all other Vars in the same relation. We remove these
3184 : * Vars from the newvarinfos list for the next iteration. This is the
3185 : * easiest way to group Vars of same rel together.
3186 : */
3187 : do
3188 : {
3189 6880 : GroupVarInfo *varinfo1 = (GroupVarInfo *) linitial(varinfos);
3190 6880 : RelOptInfo *rel = varinfo1->rel;
3191 6880 : double reldistinct = 1;
3192 6880 : double relmaxndistinct = reldistinct;
3193 6880 : int relvarcount = 0;
3194 6880 : List *newvarinfos = NIL;
3195 6880 : List *relvarinfos = NIL;
3196 :
3197 : /*
3198 : * Split the list of varinfos in two - one for the current rel, one
3199 : * for remaining Vars on other rels.
3200 : */
3201 6880 : relvarinfos = lcons(varinfo1, relvarinfos);
3202 8814 : for_each_cell(l, lnext(list_head(varinfos)))
3203 : {
3204 1934 : GroupVarInfo *varinfo2 = (GroupVarInfo *) lfirst(l);
3205 :
3206 1934 : if (varinfo2->rel == varinfo1->rel)
3207 : {
3208 : /* varinfos on current rel */
3209 1678 : relvarinfos = lcons(varinfo2, relvarinfos);
3210 : }
3211 : else
3212 : {
3213 : /* not time to process varinfo2 yet */
3214 256 : newvarinfos = lcons(varinfo2, newvarinfos);
3215 : }
3216 : }
3217 :
3218 : /*
3219 : * Get the numdistinct estimate for the Vars of this rel. We
3220 : * iteratively search for multivariate n-distinct with maximum number
3221 : * of vars; assuming that each var group is independent of the others,
3222 : * we multiply them together. Any remaining relvarinfos after no more
3223 : * multivariate matches are found are assumed independent too, so
3224 : * their individual ndistinct estimates are multiplied also.
3225 : *
3226 : * While iterating, count how many separate numdistinct values we
3227 : * apply. We apply a fudge factor below, but only if we multiplied
3228 : * more than one such values.
3229 : */
3230 20656 : while (relvarinfos)
3231 : {
3232 : double mvndistinct;
3233 :
3234 6896 : if (estimate_multivariate_ndistinct(root, rel, &relvarinfos,
3235 : &mvndistinct))
3236 : {
3237 36 : reldistinct *= mvndistinct;
3238 36 : if (relmaxndistinct < mvndistinct)
3239 36 : relmaxndistinct = mvndistinct;
3240 36 : relvarcount++;
3241 : }
3242 : else
3243 : {
3244 15330 : foreach(l, relvarinfos)
3245 : {
3246 8470 : GroupVarInfo *varinfo2 = (GroupVarInfo *) lfirst(l);
3247 :
3248 8470 : reldistinct *= varinfo2->ndistinct;
3249 8470 : if (relmaxndistinct < varinfo2->ndistinct)
3250 7224 : relmaxndistinct = varinfo2->ndistinct;
3251 8470 : relvarcount++;
3252 : }
3253 :
3254 : /* we're done with this relation */
3255 6860 : relvarinfos = NIL;
3256 : }
3257 : }
3258 :
3259 : /*
3260 : * Sanity check --- don't divide by zero if empty relation.
3261 : */
3262 : Assert(IS_SIMPLE_REL(rel));
3263 6880 : if (rel->tuples > 0)
3264 : {
3265 : /*
3266 : * Clamp to size of rel, or size of rel / 10 if multiple Vars. The
3267 : * fudge factor is because the Vars are probably correlated but we
3268 : * don't know by how much. We should never clamp to less than the
3269 : * largest ndistinct value for any of the Vars, though, since
3270 : * there will surely be at least that many groups.
3271 : */
3272 6842 : double clamp = rel->tuples;
3273 :
3274 6842 : if (relvarcount > 1)
3275 : {
3276 1184 : clamp *= 0.1;
3277 1184 : if (clamp < relmaxndistinct)
3278 : {
3279 626 : clamp = relmaxndistinct;
3280 : /* for sanity in case some ndistinct is too large: */
3281 626 : if (clamp > rel->tuples)
3282 8 : clamp = rel->tuples;
3283 : }
3284 : }
3285 6842 : if (reldistinct > clamp)
3286 796 : reldistinct = clamp;
3287 :
3288 : /*
3289 : * Update the estimate based on the restriction selectivity,
3290 : * guarding against division by zero when reldistinct is zero.
3291 : * Also skip this if we know that we are returning all rows.
3292 : */
3293 6842 : if (reldistinct > 0 && rel->rows < rel->tuples)
3294 : {
3295 : /*
3296 : * Given a table containing N rows with n distinct values in a
3297 : * uniform distribution, if we select p rows at random then
3298 : * the expected number of distinct values selected is
3299 : *
3300 : * n * (1 - product((N-N/n-i)/(N-i), i=0..p-1))
3301 : *
3302 : * = n * (1 - (N-N/n)! / (N-N/n-p)! * (N-p)! / N!)
3303 : *
3304 : * See "Approximating block accesses in database
3305 : * organizations", S. B. Yao, Communications of the ACM,
3306 : * Volume 20 Issue 4, April 1977 Pages 260-261.
3307 : *
3308 : * Alternatively, re-arranging the terms from the factorials,
3309 : * this may be written as
3310 : *
3311 : * n * (1 - product((N-p-i)/(N-i), i=0..N/n-1))
3312 : *
3313 : * This form of the formula is more efficient to compute in
3314 : * the common case where p is larger than N/n. Additionally,
3315 : * as pointed out by Dell'Era, if i << N for all terms in the
3316 : * product, it can be approximated by
3317 : *
3318 : * n * (1 - ((N-p)/N)^(N/n))
3319 : *
3320 : * See "Expected distinct values when selecting from a bag
3321 : * without replacement", Alberto Dell'Era,
3322 : * http://www.adellera.it/investigations/distinct_balls/.
3323 : *
3324 : * The condition i << N is equivalent to n >> 1, so this is a
3325 : * good approximation when the number of distinct values in
3326 : * the table is large. It turns out that this formula also
3327 : * works well even when n is small.
3328 : */
3329 1752 : reldistinct *=
3330 1752 : (1 - pow((rel->tuples - rel->rows) / rel->tuples,
3331 1752 : rel->tuples / reldistinct));
3332 : }
3333 6842 : reldistinct = clamp_row_est(reldistinct);
3334 :
3335 : /*
3336 : * Update estimate of total distinct groups.
3337 : */
3338 6842 : numdistinct *= reldistinct;
3339 : }
3340 :
3341 6880 : varinfos = newvarinfos;
3342 6880 : } while (varinfos != NIL);
3343 :
3344 : /* Now we can account for the effects of any SRFs */
3345 6652 : numdistinct *= srf_multiplier;
3346 :
3347 : /* Round off */
3348 6652 : numdistinct = ceil(numdistinct);
3349 :
3350 : /* Guard against out-of-range answers */
3351 6652 : if (numdistinct > input_rows)
3352 382 : numdistinct = input_rows;
3353 6652 : if (numdistinct < 1.0)
3354 0 : numdistinct = 1.0;
3355 :
3356 6652 : return numdistinct;
3357 : }
3358 :
3359 : /*
3360 : * Estimate hash bucket statistics when the specified expression is used
3361 : * as a hash key for the given number of buckets.
3362 : *
3363 : * This attempts to determine two values:
3364 : *
3365 : * 1. The frequency of the most common value of the expression (returns
3366 : * zero into *mcv_freq if we can't get that).
3367 : *
3368 : * 2. The "bucketsize fraction", ie, average number of entries in a bucket
3369 : * divided by total tuples in relation.
3370 : *
3371 : * XXX This is really pretty bogus since we're effectively assuming that the
3372 : * distribution of hash keys will be the same after applying restriction
3373 : * clauses as it was in the underlying relation. However, we are not nearly
3374 : * smart enough to figure out how the restrict clauses might change the
3375 : * distribution, so this will have to do for now.
3376 : *
3377 : * We are passed the number of buckets the executor will use for the given
3378 : * input relation. If the data were perfectly distributed, with the same
3379 : * number of tuples going into each available bucket, then the bucketsize
3380 : * fraction would be 1/nbuckets. But this happy state of affairs will occur
3381 : * only if (a) there are at least nbuckets distinct data values, and (b)
3382 : * we have a not-too-skewed data distribution. Otherwise the buckets will
3383 : * be nonuniformly occupied. If the other relation in the join has a key
3384 : * distribution similar to this one's, then the most-loaded buckets are
3385 : * exactly those that will be probed most often. Therefore, the "average"
3386 : * bucket size for costing purposes should really be taken as something close
3387 : * to the "worst case" bucket size. We try to estimate this by adjusting the
3388 : * fraction if there are too few distinct data values, and then scaling up
3389 : * by the ratio of the most common value's frequency to the average frequency.
3390 : *
3391 : * If no statistics are available, use a default estimate of 0.1. This will
3392 : * discourage use of a hash rather strongly if the inner relation is large,
3393 : * which is what we want. We do not want to hash unless we know that the
3394 : * inner rel is well-dispersed (or the alternatives seem much worse).
3395 : *
3396 : * The caller should also check that the mcv_freq is not so large that the
3397 : * most common value would by itself require an impractically large bucket.
3398 : * In a hash join, the executor can split buckets if they get too big, but
3399 : * obviously that doesn't help for a bucket that contains many duplicates of
3400 : * the same value.
3401 : */
3402 : void
3403 74528 : estimate_hash_bucket_stats(PlannerInfo *root, Node *hashkey, double nbuckets,
3404 : Selectivity *mcv_freq,
3405 : Selectivity *bucketsize_frac)
3406 : {
3407 : VariableStatData vardata;
3408 : double estfract,
3409 : ndistinct,
3410 : stanullfrac,
3411 : avgfreq;
3412 : bool isdefault;
3413 : AttStatsSlot sslot;
3414 :
3415 74528 : examine_variable(root, hashkey, 0, &vardata);
3416 :
3417 : /* Look up the frequency of the most common value, if available */
3418 74528 : *mcv_freq = 0.0;
3419 :
3420 74528 : if (HeapTupleIsValid(vardata.statsTuple))
3421 : {
3422 44476 : if (get_attstatsslot(&sslot, vardata.statsTuple,
3423 : STATISTIC_KIND_MCV, InvalidOid,
3424 : ATTSTATSSLOT_NUMBERS))
3425 : {
3426 : /*
3427 : * The first MCV stat is for the most common value.
3428 : */
3429 23808 : if (sslot.nnumbers > 0)
3430 23808 : *mcv_freq = sslot.numbers[0];
3431 23808 : free_attstatsslot(&sslot);
3432 : }
3433 : }
3434 :
3435 : /* Get number of distinct values */
3436 74528 : ndistinct = get_variable_numdistinct(&vardata, &isdefault);
3437 :
3438 : /*
3439 : * If ndistinct isn't real, punt. We normally return 0.1, but if the
3440 : * mcv_freq is known to be even higher than that, use it instead.
3441 : */
3442 74528 : if (isdefault)
3443 : {
3444 11644 : *bucketsize_frac = (Selectivity) Max(0.1, *mcv_freq);
3445 11644 : ReleaseVariableStats(vardata);
3446 11644 : return;
3447 : }
3448 :
3449 : /* Get fraction that are null */
3450 62884 : if (HeapTupleIsValid(vardata.statsTuple))
3451 : {
3452 : Form_pg_statistic stats;
3453 :
3454 44464 : stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
3455 44464 : stanullfrac = stats->stanullfrac;
3456 : }
3457 : else
3458 18420 : stanullfrac = 0.0;
3459 :
3460 : /* Compute avg freq of all distinct data values in raw relation */
3461 62884 : avgfreq = (1.0 - stanullfrac) / ndistinct;
3462 :
3463 : /*
3464 : * Adjust ndistinct to account for restriction clauses. Observe we are
3465 : * assuming that the data distribution is affected uniformly by the
3466 : * restriction clauses!
3467 : *
3468 : * XXX Possibly better way, but much more expensive: multiply by
3469 : * selectivity of rel's restriction clauses that mention the target Var.
3470 : */
3471 62884 : if (vardata.rel && vardata.rel->tuples > 0)
3472 : {
3473 62876 : ndistinct *= vardata.rel->rows / vardata.rel->tuples;
3474 62876 : ndistinct = clamp_row_est(ndistinct);
3475 : }
3476 :
3477 : /*
3478 : * Initial estimate of bucketsize fraction is 1/nbuckets as long as the
3479 : * number of buckets is less than the expected number of distinct values;
3480 : * otherwise it is 1/ndistinct.
3481 : */
3482 62884 : if (ndistinct > nbuckets)
3483 40 : estfract = 1.0 / nbuckets;
3484 : else
3485 62844 : estfract = 1.0 / ndistinct;
3486 :
3487 : /*
3488 : * Adjust estimated bucketsize upward to account for skewed distribution.
3489 : */
3490 62884 : if (avgfreq > 0.0 && *mcv_freq > avgfreq)
3491 22980 : estfract *= *mcv_freq / avgfreq;
3492 :
3493 : /*
3494 : * Clamp bucketsize to sane range (the above adjustment could easily
3495 : * produce an out-of-range result). We set the lower bound a little above
3496 : * zero, since zero isn't a very sane result.
3497 : */
3498 62884 : if (estfract < 1.0e-6)
3499 0 : estfract = 1.0e-6;
3500 62884 : else if (estfract > 1.0)
3501 18896 : estfract = 1.0;
3502 :
3503 62884 : *bucketsize_frac = (Selectivity) estfract;
3504 :
3505 62884 : ReleaseVariableStats(vardata);
3506 : }
3507 :
3508 : /*
3509 : * estimate_hashagg_tablesize
3510 : * estimate the number of bytes that a hash aggregate hashtable will
3511 : * require based on the agg_costs, path width and number of groups.
3512 : *
3513 : * We return the result as "double" to forestall any possible overflow
3514 : * problem in the multiplication by dNumGroups.
3515 : *
3516 : * XXX this may be over-estimating the size now that hashagg knows to omit
3517 : * unneeded columns from the hashtable. Also for mixed-mode grouping sets,
3518 : * grouping columns not in the hashed set are counted here even though hashagg
3519 : * won't store them. Is this a problem?
3520 : */
3521 : double
3522 4532 : estimate_hashagg_tablesize(Path *path, const AggClauseCosts *agg_costs,
3523 : double dNumGroups)
3524 : {
3525 : Size hashentrysize;
3526 :
3527 : /* Estimate per-hash-entry space at tuple width... */
3528 4532 : hashentrysize = MAXALIGN(path->pathtarget->width) +
3529 : MAXALIGN(SizeofMinimalTupleHeader);
3530 :
3531 : /* plus space for pass-by-ref transition values... */
3532 4532 : hashentrysize += agg_costs->transitionSpace;
3533 : /* plus the per-hash-entry overhead */
3534 4532 : hashentrysize += hash_agg_entry_size(agg_costs->numAggs);
3535 :
3536 : /*
3537 : * Note that this disregards the effect of fill-factor and growth policy
3538 : * of the hash table. That's probably ok, given that the default
3539 : * fill-factor is relatively high. It'd be hard to meaningfully factor in
3540 : * "double-in-size" growth policies here.
3541 : */
3542 4532 : return hashentrysize * dNumGroups;
3543 : }
3544 :
3545 :
3546 : /*-------------------------------------------------------------------------
3547 : *
3548 : * Support routines
3549 : *
3550 : *-------------------------------------------------------------------------
3551 : */
3552 :
3553 : /*
3554 : * Find applicable ndistinct statistics for the given list of VarInfos (which
3555 : * must all belong to the given rel), and update *ndistinct to the estimate of
3556 : * the MVNDistinctItem that best matches. If a match it found, *varinfos is
3557 : * updated to remove the list of matched varinfos.
3558 : *
3559 : * Varinfos that aren't for simple Vars are ignored.
3560 : *
3561 : * Return true if we're able to find a match, false otherwise.
3562 : */
3563 : static bool
3564 6896 : estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
3565 : List **varinfos, double *ndistinct)
3566 : {
3567 : ListCell *lc;
3568 6896 : Bitmapset *attnums = NULL;
3569 : int nmatches;
3570 6896 : Oid statOid = InvalidOid;
3571 : MVNDistinct *stats;
3572 6896 : Bitmapset *matched = NULL;
3573 :
3574 : /* bail out immediately if the table has no extended statistics */
3575 6896 : if (!rel->statlist)
3576 6840 : return false;
3577 :
3578 : /* Determine the attnums we're looking for */
3579 184 : foreach(lc, *varinfos)
3580 : {
3581 128 : GroupVarInfo *varinfo = (GroupVarInfo *) lfirst(lc);
3582 :
3583 : Assert(varinfo->rel == rel);
3584 :
3585 128 : if (IsA(varinfo->var, Var))
3586 : {
3587 128 : attnums = bms_add_member(attnums,
3588 128 : ((Var *) varinfo->var)->varattno);
3589 : }
3590 : }
3591 :
3592 : /* look for the ndistinct statistics matching the most vars */
3593 56 : nmatches = 1; /* we require at least two matches */
3594 224 : foreach(lc, rel->statlist)
3595 : {
3596 168 : StatisticExtInfo *info = (StatisticExtInfo *) lfirst(lc);
3597 : Bitmapset *shared;
3598 : int nshared;
3599 :
3600 : /* skip statistics of other kinds */
3601 168 : if (info->kind != STATS_EXT_NDISTINCT)
3602 112 : continue;
3603 :
3604 : /* compute attnums shared by the vars and the statistics object */
3605 56 : shared = bms_intersect(info->keys, attnums);
3606 56 : nshared = bms_num_members(shared);
3607 :
3608 : /*
3609 : * Does this statistics object match more columns than the currently
3610 : * best object? If so, use this one instead.
3611 : *
3612 : * XXX This should break ties using name of the object, or something
3613 : * like that, to make the outcome stable.
3614 : */
3615 56 : if (nshared > nmatches)
3616 : {
3617 36 : statOid = info->statOid;
3618 36 : nmatches = nshared;
3619 36 : matched = shared;
3620 : }
3621 : }
3622 :
3623 : /* No match? */
3624 56 : if (statOid == InvalidOid)
3625 20 : return false;
3626 : Assert(nmatches > 1 && matched != NULL);
3627 :
3628 36 : stats = statext_ndistinct_load(statOid);
3629 :
3630 : /*
3631 : * If we have a match, search it for the specific item that matches (there
3632 : * must be one), and construct the output values.
3633 : */
3634 36 : if (stats)
3635 : {
3636 : int i;
3637 36 : List *newlist = NIL;
3638 36 : MVNDistinctItem *item = NULL;
3639 :
3640 : /* Find the specific item that exactly matches the combination */
3641 108 : for (i = 0; i < stats->nitems; i++)
3642 : {
3643 108 : MVNDistinctItem *tmpitem = &stats->items[i];
3644 :
3645 108 : if (bms_subset_compare(tmpitem->attrs, matched) == BMS_EQUAL)
3646 : {
3647 36 : item = tmpitem;
3648 36 : break;
3649 : }
3650 : }
3651 :
3652 : /* make sure we found an item */
3653 36 : if (!item)
3654 0 : elog(ERROR, "corrupt MVNDistinct entry");
3655 :
3656 : /* Form the output varinfo list, keeping only unmatched ones */
3657 140 : foreach(lc, *varinfos)
3658 : {
3659 104 : GroupVarInfo *varinfo = (GroupVarInfo *) lfirst(lc);
3660 : AttrNumber attnum;
3661 :
3662 104 : if (!IsA(varinfo->var, Var))
3663 : {
3664 0 : newlist = lappend(newlist, varinfo);
3665 0 : continue;
3666 : }
3667 :
3668 104 : attnum = ((Var *) varinfo->var)->varattno;
3669 104 : if (!bms_is_member(attnum, matched))
3670 16 : newlist = lappend(newlist, varinfo);
3671 : }
3672 :
3673 36 : *varinfos = newlist;
3674 36 : *ndistinct = item->ndistinct;
3675 36 : return true;
3676 : }
3677 :
3678 0 : return false;
3679 : }
3680 :
3681 : /*
3682 : * convert_to_scalar
3683 : * Convert non-NULL values of the indicated types to the comparison
3684 : * scale needed by scalarineqsel().
3685 : * Returns "true" if successful.
3686 : *
3687 : * XXX this routine is a hack: ideally we should look up the conversion
3688 : * subroutines in pg_type.
3689 : *
3690 : * All numeric datatypes are simply converted to their equivalent
3691 : * "double" values. (NUMERIC values that are outside the range of "double"
3692 : * are clamped to +/- HUGE_VAL.)
3693 : *
3694 : * String datatypes are converted by convert_string_to_scalar(),
3695 : * which is explained below. The reason why this routine deals with
3696 : * three values at a time, not just one, is that we need it for strings.
3697 : *
3698 : * The bytea datatype is just enough different from strings that it has
3699 : * to be treated separately.
3700 : *
3701 : * The several datatypes representing absolute times are all converted
3702 : * to Timestamp, which is actually a double, and then we just use that
3703 : * double value. Note this will give correct results even for the "special"
3704 : * values of Timestamp, since those are chosen to compare correctly;
3705 : * see timestamp_cmp.
3706 : *
3707 : * The several datatypes representing relative times (intervals) are all
3708 : * converted to measurements expressed in seconds.
3709 : */
3710 : static bool
3711 44086 : convert_to_scalar(Datum value, Oid valuetypid, Oid collid, double *scaledvalue,
3712 : Datum lobound, Datum hibound, Oid boundstypid,
3713 : double *scaledlobound, double *scaledhibound)
3714 : {
3715 44086 : bool failure = false;
3716 :
3717 : /*
3718 : * Both the valuetypid and the boundstypid should exactly match the
3719 : * declared input type(s) of the operator we are invoked for. However,
3720 : * extensions might try to use scalarineqsel as estimator for operators
3721 : * with input type(s) we don't handle here; in such cases, we want to
3722 : * return false, not fail. In any case, we mustn't assume that valuetypid
3723 : * and boundstypid are identical.
3724 : *
3725 : * XXX The histogram we are interpolating between points of could belong
3726 : * to a column that's only binary-compatible with the declared type. In
3727 : * essence we are assuming that the semantics of binary-compatible types
3728 : * are enough alike that we can use a histogram generated with one type's
3729 : * operators to estimate selectivity for the other's. This is outright
3730 : * wrong in some cases --- in particular signed versus unsigned
3731 : * interpretation could trip us up. But it's useful enough in the
3732 : * majority of cases that we do it anyway. Should think about more
3733 : * rigorous ways to do it.
3734 : */
3735 44086 : switch (valuetypid)
3736 : {
3737 : /*
3738 : * Built-in numeric types
3739 : */
3740 : case BOOLOID:
3741 : case INT2OID:
3742 : case INT4OID:
3743 : case INT8OID:
3744 : case FLOAT4OID:
3745 : case FLOAT8OID:
3746 : case NUMERICOID:
3747 : case OIDOID:
3748 : case REGPROCOID:
3749 : case REGPROCEDUREOID:
3750 : case REGOPEROID:
3751 : case REGOPERATOROID:
3752 : case REGCLASSOID:
3753 : case REGTYPEOID:
3754 : case REGCONFIGOID:
3755 : case REGDICTIONARYOID:
3756 : case REGROLEOID:
3757 : case REGNAMESPACEOID:
3758 41806 : *scaledvalue = convert_numeric_to_scalar(value, valuetypid,
3759 : &failure);
3760 41806 : *scaledlobound = convert_numeric_to_scalar(lobound, boundstypid,
3761 : &failure);
3762 41806 : *scaledhibound = convert_numeric_to_scalar(hibound, boundstypid,
3763 : &failure);
3764 41806 : return !failure;
3765 :
3766 : /*
3767 : * Built-in string types
3768 : */
3769 : case CHAROID:
3770 : case BPCHAROID:
3771 : case VARCHAROID:
3772 : case TEXTOID:
3773 : case NAMEOID:
3774 : {
3775 2276 : char *valstr = convert_string_datum(value, valuetypid,
3776 : collid, &failure);
3777 2276 : char *lostr = convert_string_datum(lobound, boundstypid,
3778 : collid, &failure);
3779 2276 : char *histr = convert_string_datum(hibound, boundstypid,
3780 : collid, &failure);
3781 :
3782 : /*
3783 : * Bail out if any of the values is not of string type. We
3784 : * might leak converted strings for the other value(s), but
3785 : * that's not worth troubling over.
3786 : */
3787 2276 : if (failure)
3788 0 : return false;
3789 :
3790 2276 : convert_string_to_scalar(valstr, scaledvalue,
3791 : lostr, scaledlobound,
3792 : histr, scaledhibound);
3793 2276 : pfree(valstr);
3794 2276 : pfree(lostr);
3795 2276 : pfree(histr);
3796 2276 : return true;
3797 : }
3798 :
3799 : /*
3800 : * Built-in bytea type
3801 : */
3802 : case BYTEAOID:
3803 : {
3804 : /* We only support bytea vs bytea comparison */
3805 0 : if (boundstypid != BYTEAOID)
3806 0 : return false;
3807 0 : convert_bytea_to_scalar(value, scaledvalue,
3808 : lobound, scaledlobound,
3809 : hibound, scaledhibound);
3810 0 : return true;
3811 : }
3812 :
3813 : /*
3814 : * Built-in time types
3815 : */
3816 : case TIMESTAMPOID:
3817 : case TIMESTAMPTZOID:
3818 : case DATEOID:
3819 : case INTERVALOID:
3820 : case TIMEOID:
3821 : case TIMETZOID:
3822 0 : *scaledvalue = convert_timevalue_to_scalar(value, valuetypid,
3823 : &failure);
3824 0 : *scaledlobound = convert_timevalue_to_scalar(lobound, boundstypid,
3825 : &failure);
3826 0 : *scaledhibound = convert_timevalue_to_scalar(hibound, boundstypid,
3827 : &failure);
3828 0 : return !failure;
3829 :
3830 : /*
3831 : * Built-in network types
3832 : */
3833 : case INETOID:
3834 : case CIDROID:
3835 : case MACADDROID:
3836 : case MACADDR8OID:
3837 0 : *scaledvalue = convert_network_to_scalar(value, valuetypid,
3838 : &failure);
3839 0 : *scaledlobound = convert_network_to_scalar(lobound, boundstypid,
3840 : &failure);
3841 0 : *scaledhibound = convert_network_to_scalar(hibound, boundstypid,
3842 : &failure);
3843 0 : return !failure;
3844 : }
3845 : /* Don't know how to convert */
3846 4 : *scaledvalue = *scaledlobound = *scaledhibound = 0;
3847 4 : return false;
3848 : }
3849 :
3850 : /*
3851 : * Do convert_to_scalar()'s work for any numeric data type.
3852 : *
3853 : * On failure (e.g., unsupported typid), set *failure to true;
3854 : * otherwise, that variable is not changed.
3855 : */
3856 : static double
3857 125418 : convert_numeric_to_scalar(Datum value, Oid typid, bool *failure)
3858 : {
3859 125418 : switch (typid)
3860 : {
3861 : case BOOLOID:
3862 0 : return (double) DatumGetBool(value);
3863 : case INT2OID:
3864 8 : return (double) DatumGetInt16(value);
3865 : case INT4OID:
3866 12154 : return (double) DatumGetInt32(value);
3867 : case INT8OID:
3868 0 : return (double) DatumGetInt64(value);
3869 : case FLOAT4OID:
3870 0 : return (double) DatumGetFloat4(value);
3871 : case FLOAT8OID:
3872 24 : return (double) DatumGetFloat8(value);
3873 : case NUMERICOID:
3874 : /* Note: out-of-range values will be clamped to +-HUGE_VAL */
3875 0 : return (double)
3876 0 : DatumGetFloat8(DirectFunctionCall1(numeric_float8_no_overflow,
3877 : value));
3878 : case OIDOID:
3879 : case REGPROCOID:
3880 : case REGPROCEDUREOID:
3881 : case REGOPEROID:
3882 : case REGOPERATOROID:
3883 : case REGCLASSOID:
3884 : case REGTYPEOID:
3885 : case REGCONFIGOID:
3886 : case REGDICTIONARYOID:
3887 : case REGROLEOID:
3888 : case REGNAMESPACEOID:
3889 : /* we can treat OIDs as integers... */
3890 113232 : return (double) DatumGetObjectId(value);
3891 : }
3892 :
3893 0 : *failure = true;
3894 0 : return 0;
3895 : }
3896 :
3897 : /*
3898 : * Do convert_to_scalar()'s work for any character-string data type.
3899 : *
3900 : * String datatypes are converted to a scale that ranges from 0 to 1,
3901 : * where we visualize the bytes of the string as fractional digits.
3902 : *
3903 : * We do not want the base to be 256, however, since that tends to
3904 : * generate inflated selectivity estimates; few databases will have
3905 : * occurrences of all 256 possible byte values at each position.
3906 : * Instead, use the smallest and largest byte values seen in the bounds
3907 : * as the estimated range for each byte, after some fudging to deal with
3908 : * the fact that we probably aren't going to see the full range that way.
3909 : *
3910 : * An additional refinement is that we discard any common prefix of the
3911 : * three strings before computing the scaled values. This allows us to
3912 : * "zoom in" when we encounter a narrow data range. An example is a phone
3913 : * number database where all the values begin with the same area code.
3914 : * (Actually, the bounds will be adjacent histogram-bin-boundary values,
3915 : * so this is more likely to happen than you might think.)
3916 : */
3917 : static void
3918 2276 : convert_string_to_scalar(char *value,
3919 : double *scaledvalue,
3920 : char *lobound,
3921 : double *scaledlobound,
3922 : char *hibound,
3923 : double *scaledhibound)
3924 : {
3925 : int rangelo,
3926 : rangehi;
3927 : char *sptr;
3928 :
3929 2276 : rangelo = rangehi = (unsigned char) hibound[0];
3930 32610 : for (sptr = lobound; *sptr; sptr++)
3931 : {
3932 30334 : if (rangelo > (unsigned char) *sptr)
3933 6172 : rangelo = (unsigned char) *sptr;
3934 30334 : if (rangehi < (unsigned char) *sptr)
3935 2602 : rangehi = (unsigned char) *sptr;
3936 : }
3937 32248 : for (sptr = hibound; *sptr; sptr++)
3938 : {
3939 29972 : if (rangelo > (unsigned char) *sptr)
3940 622 : rangelo = (unsigned char) *sptr;
3941 29972 : if (rangehi < (unsigned char) *sptr)
3942 3256 : rangehi = (unsigned char) *sptr;
3943 : }
3944 : /* If range includes any upper-case ASCII chars, make it include all */
3945 2276 : if (rangelo <= 'Z' && rangehi >= 'A')
3946 : {
3947 1304 : if (rangelo > 'A')
3948 56 : rangelo = 'A';
3949 1304 : if (rangehi < 'Z')
3950 328 : rangehi = 'Z';
3951 : }
3952 : /* Ditto lower-case */
3953 2276 : if (rangelo <= 'z' && rangehi >= 'a')
3954 : {
3955 1916 : if (rangelo > 'a')
3956 0 : rangelo = 'a';
3957 1916 : if (rangehi < 'z')
3958 1750 : rangehi = 'z';
3959 : }
3960 : /* Ditto digits */
3961 2276 : if (rangelo <= '9' && rangehi >= '0')
3962 : {
3963 928 : if (rangelo > '0')
3964 872 : rangelo = '0';
3965 928 : if (rangehi < '9')
3966 4 : rangehi = '9';
3967 : }
3968 :
3969 : /*
3970 : * If range includes less than 10 chars, assume we have not got enough
3971 : * data, and make it include regular ASCII set.
3972 : */
3973 2276 : if (rangehi - rangelo < 9)
3974 : {
3975 0 : rangelo = ' ';
3976 0 : rangehi = 127;
3977 : }
3978 :
3979 : /*
3980 : * Now strip any common prefix of the three strings.
3981 : */
3982 6570 : while (*lobound)
3983 : {
3984 4210 : if (*lobound != *hibound || *lobound != *value)
3985 : break;
3986 2018 : lobound++, hibound++, value++;
3987 : }
3988 :
3989 : /*
3990 : * Now we can do the conversions.
3991 : */
3992 2276 : *scaledvalue = convert_one_string_to_scalar(value, rangelo, rangehi);
3993 2276 : *scaledlobound = convert_one_string_to_scalar(lobound, rangelo, rangehi);
3994 2276 : *scaledhibound = convert_one_string_to_scalar(hibound, rangelo, rangehi);
3995 2276 : }
3996 :
3997 : static double
3998 6828 : convert_one_string_to_scalar(char *value, int rangelo, int rangehi)
3999 : {
4000 6828 : int slen = strlen(value);
4001 : double num,
4002 : denom,
4003 : base;
4004 :
4005 6828 : if (slen <= 0)
4006 84 : return 0.0; /* empty string has scalar value 0 */
4007 :
4008 : /*
4009 : * There seems little point in considering more than a dozen bytes from
4010 : * the string. Since base is at least 10, that will give us nominal
4011 : * resolution of at least 12 decimal digits, which is surely far more
4012 : * precision than this estimation technique has got anyway (especially in
4013 : * non-C locales). Also, even with the maximum possible base of 256, this
4014 : * ensures denom cannot grow larger than 256^13 = 2.03e31, which will not
4015 : * overflow on any known machine.
4016 : */
4017 6744 : if (slen > 12)
4018 1822 : slen = 12;
4019 :
4020 : /* Convert initial characters to fraction */
4021 6744 : base = rangehi - rangelo + 1;
4022 6744 : num = 0.0;
4023 6744 : denom = base;
4024 64392 : while (slen-- > 0)
4025 : {
4026 50904 : int ch = (unsigned char) *value++;
4027 :
4028 50904 : if (ch < rangelo)
4029 48 : ch = rangelo - 1;
4030 50856 : else if (ch > rangehi)
4031 0 : ch = rangehi + 1;
4032 50904 : num += ((double) (ch - rangelo)) / denom;
4033 50904 : denom *= base;
4034 : }
4035 :
4036 6744 : return num;
4037 : }
4038 :
4039 : /*
4040 : * Convert a string-type Datum into a palloc'd, null-terminated string.
4041 : *
4042 : * On failure (e.g., unsupported typid), set *failure to true;
4043 : * otherwise, that variable is not changed. (We'll return NULL on failure.)
4044 : *
4045 : * When using a non-C locale, we must pass the string through strxfrm()
4046 : * before continuing, so as to generate correct locale-specific results.
4047 : */
4048 : static char *
4049 6828 : convert_string_datum(Datum value, Oid typid, Oid collid, bool *failure)
4050 : {
4051 : char *val;
4052 :
4053 6828 : switch (typid)
4054 : {
4055 : case CHAROID:
4056 0 : val = (char *) palloc(2);
4057 0 : val[0] = DatumGetChar(value);
4058 0 : val[1] = '\0';
4059 0 : break;
4060 : case BPCHAROID:
4061 : case VARCHAROID:
4062 : case TEXTOID:
4063 1180 : val = TextDatumGetCString(value);
4064 1180 : break;
4065 : case NAMEOID:
4066 : {
4067 5648 : NameData *nm = (NameData *) DatumGetPointer(value);
4068 :
4069 5648 : val = pstrdup(NameStr(*nm));
4070 5648 : break;
4071 : }
4072 : default:
4073 0 : *failure = true;
4074 0 : return NULL;
4075 : }
4076 :
4077 6828 : if (!lc_collate_is_c(collid))
4078 : {
4079 : char *xfrmstr;
4080 : size_t xfrmlen;
4081 : size_t xfrmlen2 PG_USED_FOR_ASSERTS_ONLY;
4082 :
4083 : /*
4084 : * XXX: We could guess at a suitable output buffer size and only call
4085 : * strxfrm twice if our guess is too small.
4086 : *
4087 : * XXX: strxfrm doesn't support UTF-8 encoding on Win32, it can return
4088 : * bogus data or set an error. This is not really a problem unless it
4089 : * crashes since it will only give an estimation error and nothing
4090 : * fatal.
4091 : */
4092 : #if _MSC_VER == 1400 /* VS.Net 2005 */
4093 :
4094 : /*
4095 : *
4096 : * http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=99694
4097 : */
4098 : {
4099 : char x[1];
4100 :
4101 : xfrmlen = strxfrm(x, val, 0);
4102 : }
4103 : #else
4104 72 : xfrmlen = strxfrm(NULL, val, 0);
4105 : #endif
4106 : #ifdef WIN32
4107 :
4108 : /*
4109 : * On Windows, strxfrm returns INT_MAX when an error occurs. Instead
4110 : * of trying to allocate this much memory (and fail), just return the
4111 : * original string unmodified as if we were in the C locale.
4112 : */
4113 : if (xfrmlen == INT_MAX)
4114 : return val;
4115 : #endif
4116 72 : xfrmstr = (char *) palloc(xfrmlen + 1);
4117 72 : xfrmlen2 = strxfrm(xfrmstr, val, xfrmlen + 1);
4118 :
4119 : /*
4120 : * Some systems (e.g., glibc) can return a smaller value from the
4121 : * second call than the first; thus the Assert must be <= not ==.
4122 : */
4123 : Assert(xfrmlen2 <= xfrmlen);
4124 72 : pfree(val);
4125 72 : val = xfrmstr;
4126 : }
4127 :
4128 6828 : return val;
4129 : }
4130 :
4131 : /*
4132 : * Do convert_to_scalar()'s work for any bytea data type.
4133 : *
4134 : * Very similar to convert_string_to_scalar except we can't assume
4135 : * null-termination and therefore pass explicit lengths around.
4136 : *
4137 : * Also, assumptions about likely "normal" ranges of characters have been
4138 : * removed - a data range of 0..255 is always used, for now. (Perhaps
4139 : * someday we will add information about actual byte data range to
4140 : * pg_statistic.)
4141 : */
4142 : static void
4143 0 : convert_bytea_to_scalar(Datum value,
4144 : double *scaledvalue,
4145 : Datum lobound,
4146 : double *scaledlobound,
4147 : Datum hibound,
4148 : double *scaledhibound)
4149 : {
4150 0 : bytea *valuep = DatumGetByteaPP(value);
4151 0 : bytea *loboundp = DatumGetByteaPP(lobound);
4152 0 : bytea *hiboundp = DatumGetByteaPP(hibound);
4153 : int rangelo,
4154 : rangehi,
4155 0 : valuelen = VARSIZE_ANY_EXHDR(valuep),
4156 0 : loboundlen = VARSIZE_ANY_EXHDR(loboundp),
4157 0 : hiboundlen = VARSIZE_ANY_EXHDR(hiboundp),
4158 : i,
4159 : minlen;
4160 0 : unsigned char *valstr = (unsigned char *) VARDATA_ANY(valuep);
4161 0 : unsigned char *lostr = (unsigned char *) VARDATA_ANY(loboundp);
4162 0 : unsigned char *histr = (unsigned char *) VARDATA_ANY(hiboundp);
4163 :
4164 : /*
4165 : * Assume bytea data is uniformly distributed across all byte values.
4166 : */
4167 0 : rangelo = 0;
4168 0 : rangehi = 255;
4169 :
4170 : /*
4171 : * Now strip any common prefix of the three strings.
4172 : */
4173 0 : minlen = Min(Min(valuelen, loboundlen), hiboundlen);
4174 0 : for (i = 0; i < minlen; i++)
4175 : {
4176 0 : if (*lostr != *histr || *lostr != *valstr)
4177 : break;
4178 0 : lostr++, histr++, valstr++;
4179 0 : loboundlen--, hiboundlen--, valuelen--;
4180 : }
4181 :
4182 : /*
4183 : * Now we can do the conversions.
4184 : */
4185 0 : *scaledvalue = convert_one_bytea_to_scalar(valstr, valuelen, rangelo, rangehi);
4186 0 : *scaledlobound = convert_one_bytea_to_scalar(lostr, loboundlen, rangelo, rangehi);
4187 0 : *scaledhibound = convert_one_bytea_to_scalar(histr, hiboundlen, rangelo, rangehi);
4188 0 : }
4189 :
4190 : static double
4191 0 : convert_one_bytea_to_scalar(unsigned char *value, int valuelen,
4192 : int rangelo, int rangehi)
4193 : {
4194 : double num,
4195 : denom,
4196 : base;
4197 :
4198 0 : if (valuelen <= 0)
4199 0 : return 0.0; /* empty string has scalar value 0 */
4200 :
4201 : /*
4202 : * Since base is 256, need not consider more than about 10 chars (even
4203 : * this many seems like overkill)
4204 : */
4205 0 : if (valuelen > 10)
4206 0 : valuelen = 10;
4207 :
4208 : /* Convert initial characters to fraction */
4209 0 : base = rangehi - rangelo + 1;
4210 0 : num = 0.0;
4211 0 : denom = base;
4212 0 : while (valuelen-- > 0)
4213 : {
4214 0 : int ch = *value++;
4215 :
4216 0 : if (ch < rangelo)
4217 0 : ch = rangelo - 1;
4218 0 : else if (ch > rangehi)
4219 0 : ch = rangehi + 1;
4220 0 : num += ((double) (ch - rangelo)) / denom;
4221 0 : denom *= base;
4222 : }
4223 :
4224 0 : return num;
4225 : }
4226 :
4227 : /*
4228 : * Do convert_to_scalar()'s work for any timevalue data type.
4229 : *
4230 : * On failure (e.g., unsupported typid), set *failure to true;
4231 : * otherwise, that variable is not changed.
4232 : */
4233 : static double
4234 0 : convert_timevalue_to_scalar(Datum value, Oid typid, bool *failure)
4235 : {
4236 0 : switch (typid)
4237 : {
4238 : case TIMESTAMPOID:
4239 0 : return DatumGetTimestamp(value);
4240 : case TIMESTAMPTZOID:
4241 0 : return DatumGetTimestampTz(value);
4242 : case DATEOID:
4243 0 : return date2timestamp_no_overflow(DatumGetDateADT(value));
4244 : case INTERVALOID:
4245 : {
4246 0 : Interval *interval = DatumGetIntervalP(value);
4247 :
4248 : /*
4249 : * Convert the month part of Interval to days using assumed
4250 : * average month length of 365.25/12.0 days. Not too
4251 : * accurate, but plenty good enough for our purposes.
4252 : */
4253 0 : return interval->time + interval->day * (double) USECS_PER_DAY +
4254 0 : interval->month * ((DAYS_PER_YEAR / (double) MONTHS_PER_YEAR) * USECS_PER_DAY);
4255 : }
4256 : case TIMEOID:
4257 0 : return DatumGetTimeADT(value);
4258 : case TIMETZOID:
4259 : {
4260 0 : TimeTzADT *timetz = DatumGetTimeTzADTP(value);
4261 :
4262 : /* use GMT-equivalent time */
4263 0 : return (double) (timetz->time + (timetz->zone * 1000000.0));
4264 : }
4265 : }
4266 :
4267 0 : *failure = true;
4268 0 : return 0;
4269 : }
4270 :
4271 :
4272 : /*
4273 : * get_restriction_variable
4274 : * Examine the args of a restriction clause to see if it's of the
4275 : * form (variable op pseudoconstant) or (pseudoconstant op variable),
4276 : * where "variable" could be either a Var or an expression in vars of a
4277 : * single relation. If so, extract information about the variable,
4278 : * and also indicate which side it was on and the other argument.
4279 : *
4280 : * Inputs:
4281 : * root: the planner info
4282 : * args: clause argument list
4283 : * varRelid: see specs for restriction selectivity functions
4284 : *
4285 : * Outputs: (these are valid only if true is returned)
4286 : * *vardata: gets information about variable (see examine_variable)
4287 : * *other: gets other clause argument, aggressively reduced to a constant
4288 : * *varonleft: set true if variable is on the left, false if on the right
4289 : *
4290 : * Returns true if a variable is identified, otherwise false.
4291 : *
4292 : * Note: if there are Vars on both sides of the clause, we must fail, because
4293 : * callers are expecting that the other side will act like a pseudoconstant.
4294 : */
4295 : bool
4296 338626 : get_restriction_variable(PlannerInfo *root, List *args, int varRelid,
4297 : VariableStatData *vardata, Node **other,
4298 : bool *varonleft)
4299 : {
4300 : Node *left,
4301 : *right;
4302 : VariableStatData rdata;
4303 :
4304 : /* Fail if not a binary opclause (probably shouldn't happen) */
4305 338626 : if (list_length(args) != 2)
4306 0 : return false;
4307 :
4308 338626 : left = (Node *) linitial(args);
4309 338626 : right = (Node *) lsecond(args);
4310 :
4311 : /*
4312 : * Examine both sides. Note that when varRelid is nonzero, Vars of other
4313 : * relations will be treated as pseudoconstants.
4314 : */
4315 338626 : examine_variable(root, left, varRelid, vardata);
4316 338626 : examine_variable(root, right, varRelid, &rdata);
4317 :
4318 : /*
4319 : * If one side is a variable and the other not, we win.
4320 : */
4321 338626 : if (vardata->rel && rdata.rel == NULL)
4322 : {
4323 280392 : *varonleft = true;
4324 280392 : *other = estimate_expression_value(root, rdata.var);
4325 : /* Assume we need no ReleaseVariableStats(rdata) here */
4326 280392 : return true;
4327 : }
4328 :
4329 58234 : if (vardata->rel == NULL && rdata.rel)
4330 : {
4331 56774 : *varonleft = false;
4332 56774 : *other = estimate_expression_value(root, vardata->var);
4333 : /* Assume we need no ReleaseVariableStats(*vardata) here */
4334 56774 : *vardata = rdata;
4335 56774 : return true;
4336 : }
4337 :
4338 : /* Oops, clause has wrong structure (probably var op var) */
4339 1460 : ReleaseVariableStats(*vardata);
4340 1460 : ReleaseVariableStats(rdata);
4341 :
4342 1460 : return false;
4343 : }
4344 :
4345 : /*
4346 : * get_join_variables
4347 : * Apply examine_variable() to each side of a join clause.
4348 : * Also, attempt to identify whether the join clause has the same
4349 : * or reversed sense compared to the SpecialJoinInfo.
4350 : *
4351 : * We consider the join clause "normal" if it is "lhs_var OP rhs_var",
4352 : * or "reversed" if it is "rhs_var OP lhs_var". In complicated cases
4353 : * where we can't tell for sure, we default to assuming it's normal.
4354 : */
4355 : void
4356 110884 : get_join_variables(PlannerInfo *root, List *args, SpecialJoinInfo *sjinfo,
4357 : VariableStatData *vardata1, VariableStatData *vardata2,
4358 : bool *join_is_reversed)
4359 : {
4360 : Node *left,
4361 : *right;
4362 :
4363 110884 : if (list_length(args) != 2)
4364 0 : elog(ERROR, "join operator should take two arguments");
4365 :
4366 110884 : left = (Node *) linitial(args);
4367 110884 : right = (Node *) lsecond(args);
4368 :
4369 110884 : examine_variable(root, left, 0, vardata1);
4370 110884 : examine_variable(root, right, 0, vardata2);
4371 :
4372 221696 : if (vardata1->rel &&
4373 110812 : bms_is_subset(vardata1->rel->relids, sjinfo->syn_righthand))
4374 17652 : *join_is_reversed = true; /* var1 is on RHS */
4375 186412 : else if (vardata2->rel &&
4376 93180 : bms_is_subset(vardata2->rel->relids, sjinfo->syn_lefthand))
4377 80 : *join_is_reversed = true; /* var2 is on LHS */
4378 : else
4379 93152 : *join_is_reversed = false;
4380 110884 : }
4381 :
4382 : /*
4383 : * examine_variable
4384 : * Try to look up statistical data about an expression.
4385 : * Fill in a VariableStatData struct to describe the expression.
4386 : *
4387 : * Inputs:
4388 : * root: the planner info
4389 : * node: the expression tree to examine
4390 : * varRelid: see specs for restriction selectivity functions
4391 : *
4392 : * Outputs: *vardata is filled as follows:
4393 : * var: the input expression (with any binary relabeling stripped, if
4394 : * it is or contains a variable; but otherwise the type is preserved)
4395 : * rel: RelOptInfo for relation containing variable; NULL if expression
4396 : * contains no Vars (NOTE this could point to a RelOptInfo of a
4397 : * subquery, not one in the current query).
4398 : * statsTuple: the pg_statistic entry for the variable, if one exists;
4399 : * otherwise NULL.
4400 : * freefunc: pointer to a function to release statsTuple with.
4401 : * vartype: exposed type of the expression; this should always match
4402 : * the declared input type of the operator we are estimating for.
4403 : * atttype, atttypmod: actual type/typmod of the "var" expression. This is
4404 : * commonly the same as the exposed type of the variable argument,
4405 : * but can be different in binary-compatible-type cases.
4406 : * isunique: true if we were able to match the var to a unique index or a
4407 : * single-column DISTINCT clause, implying its values are unique for
4408 : * this query. (Caution: this should be trusted for statistical
4409 : * purposes only, since we do not check indimmediate nor verify that
4410 : * the exact same definition of equality applies.)
4411 : * acl_ok: true if current user has permission to read the column(s)
4412 : * underlying the pg_statistic entry. This is consulted by
4413 : * statistic_proc_security_check().
4414 : *
4415 : * Caller is responsible for doing ReleaseVariableStats() before exiting.
4416 : */
4417 : void
4418 1129284 : examine_variable(PlannerInfo *root, Node *node, int varRelid,
4419 : VariableStatData *vardata)
4420 : {
4421 : Node *basenode;
4422 : Relids varnos;
4423 : RelOptInfo *onerel;
4424 :
4425 : /* Make sure we don't return dangling pointers in vardata */
4426 1129284 : MemSet(vardata, 0, sizeof(VariableStatData));
4427 :
4428 : /* Save the exposed type of the expression */
4429 1129284 : vardata->vartype = exprType(node);
4430 :
4431 : /* Look inside any binary-compatible relabeling */
4432 :
4433 1129284 : if (IsA(node, RelabelType))
4434 15130 : basenode = (Node *) ((RelabelType *) node)->arg;
4435 : else
4436 1114154 : basenode = node;
4437 :
4438 : /* Fast path for a simple Var */
4439 :
4440 1129284 : if (IsA(basenode, Var) &&
4441 273710 : (varRelid == 0 || varRelid == ((Var *) basenode)->varno))
4442 : {
4443 761946 : Var *var = (Var *) basenode;
4444 :
4445 : /* Set up result fields other than the stats tuple */
4446 761946 : vardata->var = basenode; /* return Var without relabeling */
4447 761946 : vardata->rel = find_base_rel(root, var->varno);
4448 761946 : vardata->atttype = var->vartype;
4449 761946 : vardata->atttypmod = var->vartypmod;
4450 761946 : vardata->isunique = has_unique_index(vardata->rel, var->varattno);
4451 :
4452 : /* Try to locate some stats */
4453 761946 : examine_simple_variable(root, var, vardata);
4454 :
4455 761946 : return;
4456 : }
4457 :
4458 : /*
4459 : * Okay, it's a more complicated expression. Determine variable
4460 : * membership. Note that when varRelid isn't zero, only vars of that
4461 : * relation are considered "real" vars.
4462 : */
4463 367338 : varnos = pull_varnos(basenode);
4464 :
4465 367338 : onerel = NULL;
4466 :
4467 367338 : switch (bms_membership(varnos))
4468 : {
4469 : case BMS_EMPTY_SET:
4470 : /* No Vars at all ... must be pseudo-constant clause */
4471 217084 : break;
4472 : case BMS_SINGLETON:
4473 147442 : if (varRelid == 0 || bms_is_member(varRelid, varnos))
4474 : {
4475 13376 : onerel = find_base_rel(root,
4476 : (varRelid ? varRelid : bms_singleton_member(varnos)));
4477 13376 : vardata->rel = onerel;
4478 13376 : node = basenode; /* strip any relabeling */
4479 : }
4480 : /* else treat it as a constant */
4481 147442 : break;
4482 : case BMS_MULTIPLE:
4483 2812 : if (varRelid == 0)
4484 : {
4485 : /* treat it as a variable of a join relation */
4486 2700 : vardata->rel = find_join_rel(root, varnos);
4487 2700 : node = basenode; /* strip any relabeling */
4488 : }
4489 112 : else if (bms_is_member(varRelid, varnos))
4490 : {
4491 : /* ignore the vars belonging to other relations */
4492 20 : vardata->rel = find_base_rel(root, varRelid);
4493 20 : node = basenode; /* strip any relabeling */
4494 : /* note: no point in expressional-index search here */
4495 : }
4496 : /* else treat it as a constant */
4497 2812 : break;
4498 : }
4499 :
4500 367338 : bms_free(varnos);
4501 :
4502 367338 : vardata->var = node;
4503 367338 : vardata->atttype = exprType(node);
4504 367338 : vardata->atttypmod = exprTypmod(node);
4505 :
4506 367338 : if (onerel)
4507 : {
4508 : /*
4509 : * We have an expression in vars of a single relation. Try to match
4510 : * it to expressional index columns, in hopes of finding some
4511 : * statistics.
4512 : *
4513 : * Note that we consider all index columns including INCLUDE columns,
4514 : * since there could be stats for such columns. But the test for
4515 : * uniqueness needs to be warier.
4516 : *
4517 : * XXX it's conceivable that there are multiple matches with different
4518 : * index opfamilies; if so, we need to pick one that matches the
4519 : * operator we are estimating for. FIXME later.
4520 : */
4521 : ListCell *ilist;
4522 :
4523 21782 : foreach(ilist, onerel->indexlist)
4524 : {
4525 10266 : IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
4526 : ListCell *indexpr_item;
4527 : int pos;
4528 :
4529 10266 : indexpr_item = list_head(index->indexprs);
4530 10266 : if (indexpr_item == NULL)
4531 7286 : continue; /* no expressions here... */
4532 :
4533 4100 : for (pos = 0; pos < index->ncolumns; pos++)
4534 : {
4535 2980 : if (index->indexkeys[pos] == 0)
4536 : {
4537 : Node *indexkey;
4538 :
4539 2980 : if (indexpr_item == NULL)
4540 0 : elog(ERROR, "too few entries in indexprs list");
4541 2980 : indexkey = (Node *) lfirst(indexpr_item);
4542 2980 : if (indexkey && IsA(indexkey, RelabelType))
4543 0 : indexkey = (Node *) ((RelabelType *) indexkey)->arg;
4544 2980 : if (equal(node, indexkey))
4545 : {
4546 : /*
4547 : * Found a match ... is it a unique index? Tests here
4548 : * should match has_unique_index().
4549 : */
4550 2444 : if (index->unique &&
4551 520 : index->nkeycolumns == 1 &&
4552 260 : pos == 0 &&
4553 260 : (index->indpred == NIL || index->predOK))
4554 260 : vardata->isunique = true;
4555 :
4556 : /*
4557 : * Has it got stats? We only consider stats for
4558 : * non-partial indexes, since partial indexes probably
4559 : * don't reflect whole-relation statistics; the above
4560 : * check for uniqueness is the only info we take from
4561 : * a partial index.
4562 : *
4563 : * An index stats hook, however, must make its own
4564 : * decisions about what to do with partial indexes.
4565 : */
4566 2184 : if (get_index_stats_hook &&
4567 0 : (*get_index_stats_hook) (root, index->indexoid,
4568 0 : pos + 1, vardata))
4569 : {
4570 : /*
4571 : * The hook took control of acquiring a stats
4572 : * tuple. If it did supply a tuple, it'd better
4573 : * have supplied a freefunc.
4574 : */
4575 0 : if (HeapTupleIsValid(vardata->statsTuple) &&
4576 0 : !vardata->freefunc)
4577 0 : elog(ERROR, "no function provided to release variable stats with");
4578 : }
4579 2184 : else if (index->indpred == NIL)
4580 : {
4581 2184 : vardata->statsTuple =
4582 4368 : SearchSysCache3(STATRELATTINH,
4583 2184 : ObjectIdGetDatum(index->indexoid),
4584 2184 : Int16GetDatum(pos + 1),
4585 : BoolGetDatum(false));
4586 2184 : vardata->freefunc = ReleaseSysCache;
4587 :
4588 2184 : if (HeapTupleIsValid(vardata->statsTuple))
4589 : {
4590 : /* Get index's table for permission check */
4591 : RangeTblEntry *rte;
4592 : Oid userid;
4593 :
4594 1860 : rte = planner_rt_fetch(index->rel->relid, root);
4595 : Assert(rte->rtekind == RTE_RELATION);
4596 :
4597 : /*
4598 : * Use checkAsUser if it's set, in case we're
4599 : * accessing the table via a view.
4600 : */
4601 1860 : userid = rte->checkAsUser ? rte->checkAsUser : GetUserId();
4602 :
4603 : /*
4604 : * For simplicity, we insist on the whole
4605 : * table being selectable, rather than trying
4606 : * to identify which column(s) the index
4607 : * depends on. Also require all rows to be
4608 : * selectable --- there must be no
4609 : * securityQuals from security barrier views
4610 : * or RLS policies.
4611 : */
4612 1860 : vardata->acl_ok =
4613 3720 : rte->securityQuals == NIL &&
4614 1860 : (pg_class_aclcheck(rte->relid, userid,
4615 : ACL_SELECT) == ACLCHECK_OK);
4616 : }
4617 : else
4618 : {
4619 : /* suppress leakproofness checks later */
4620 324 : vardata->acl_ok = true;
4621 : }
4622 : }
4623 2184 : if (vardata->statsTuple)
4624 1860 : break;
4625 : }
4626 1120 : indexpr_item = lnext(indexpr_item);
4627 : }
4628 : }
4629 2980 : if (vardata->statsTuple)
4630 1860 : break;
4631 : }
4632 : }
4633 : }
4634 :
4635 : /*
4636 : * examine_simple_variable
4637 : * Handle a simple Var for examine_variable
4638 : *
4639 : * This is split out as a subroutine so that we can recurse to deal with
4640 : * Vars referencing subqueries.
4641 : *
4642 : * We already filled in all the fields of *vardata except for the stats tuple.
4643 : */
4644 : static void
4645 762494 : examine_simple_variable(PlannerInfo *root, Var *var,
4646 : VariableStatData *vardata)
4647 : {
4648 762494 : RangeTblEntry *rte = root->simple_rte_array[var->varno];
4649 :
4650 : Assert(IsA(rte, RangeTblEntry));
4651 :
4652 762494 : if (get_relation_stats_hook &&
4653 0 : (*get_relation_stats_hook) (root, rte, var->varattno, vardata))
4654 : {
4655 : /*
4656 : * The hook took control of acquiring a stats tuple. If it did supply
4657 : * a tuple, it'd better have supplied a freefunc.
4658 : */
4659 0 : if (HeapTupleIsValid(vardata->statsTuple) &&
4660 0 : !vardata->freefunc)
4661 0 : elog(ERROR, "no function provided to release variable stats with");
4662 : }
4663 762494 : else if (rte->rtekind == RTE_RELATION)
4664 : {
4665 : /*
4666 : * Plain table or parent of an inheritance appendrel, so look up the
4667 : * column in pg_statistic
4668 : */
4669 2148600 : vardata->statsTuple = SearchSysCache3(STATRELATTINH,
4670 716200 : ObjectIdGetDatum(rte->relid),
4671 716200 : Int16GetDatum(var->varattno),
4672 716200 : BoolGetDatum(rte->inh));
4673 716200 : vardata->freefunc = ReleaseSysCache;
4674 :
4675 716200 : if (HeapTupleIsValid(vardata->statsTuple))
4676 : {
4677 : Oid userid;
4678 :
4679 : /*
4680 : * Check if user has permission to read this column. We require
4681 : * all rows to be accessible, so there must be no securityQuals
4682 : * from security barrier views or RLS policies. Use checkAsUser
4683 : * if it's set, in case we're accessing the table via a view.
4684 : */
4685 508402 : userid = rte->checkAsUser ? rte->checkAsUser : GetUserId();
4686 :
4687 508402 : vardata->acl_ok =
4688 1524650 : rte->securityQuals == NIL &&
4689 508126 : ((pg_class_aclcheck(rte->relid, userid,
4690 104 : ACL_SELECT) == ACLCHECK_OK) ||
4691 104 : (pg_attribute_aclcheck(rte->relid, var->varattno, userid,
4692 : ACL_SELECT) == ACLCHECK_OK));
4693 : }
4694 : else
4695 : {
4696 : /* suppress any possible leakproofness checks later */
4697 207798 : vardata->acl_ok = true;
4698 : }
4699 : }
4700 46294 : else if (rte->rtekind == RTE_SUBQUERY && !rte->inh)
4701 : {
4702 : /*
4703 : * Plain subquery (not one that was converted to an appendrel).
4704 : */
4705 2204 : Query *subquery = rte->subquery;
4706 : RelOptInfo *rel;
4707 : TargetEntry *ste;
4708 :
4709 : /*
4710 : * Punt if it's a whole-row var rather than a plain column reference.
4711 : */
4712 2204 : if (var->varattno == InvalidAttrNumber)
4713 0 : return;
4714 :
4715 : /*
4716 : * Punt if subquery uses set operations or GROUP BY, as these will
4717 : * mash underlying columns' stats beyond recognition. (Set ops are
4718 : * particularly nasty; if we forged ahead, we would return stats
4719 : * relevant to only the leftmost subselect...) DISTINCT is also
4720 : * problematic, but we check that later because there is a possibility
4721 : * of learning something even with it.
4722 : */
4723 4292 : if (subquery->setOperations ||
4724 2088 : subquery->groupClause)
4725 364 : return;
4726 :
4727 : /*
4728 : * OK, fetch RelOptInfo for subquery. Note that we don't change the
4729 : * rel returned in vardata, since caller expects it to be a rel of the
4730 : * caller's query level. Because we might already be recursing, we
4731 : * can't use that rel pointer either, but have to look up the Var's
4732 : * rel afresh.
4733 : */
4734 1840 : rel = find_base_rel(root, var->varno);
4735 :
4736 : /* If the subquery hasn't been planned yet, we have to punt */
4737 1840 : if (rel->subroot == NULL)
4738 0 : return;
4739 : Assert(IsA(rel->subroot, PlannerInfo));
4740 :
4741 : /*
4742 : * Switch our attention to the subquery as mangled by the planner. It
4743 : * was okay to look at the pre-planning version for the tests above,
4744 : * but now we need a Var that will refer to the subroot's live
4745 : * RelOptInfos. For instance, if any subquery pullup happened during
4746 : * planning, Vars in the targetlist might have gotten replaced, and we
4747 : * need to see the replacement expressions.
4748 : */
4749 1840 : subquery = rel->subroot->parse;
4750 : Assert(IsA(subquery, Query));
4751 :
4752 : /* Get the subquery output expression referenced by the upper Var */
4753 1840 : ste = get_tle_by_resno(subquery->targetList, var->varattno);
4754 1840 : if (ste == NULL || ste->resjunk)
4755 0 : elog(ERROR, "subquery %s does not have attribute %d",
4756 : rte->eref->aliasname, var->varattno);
4757 1840 : var = (Var *) ste->expr;
4758 :
4759 : /*
4760 : * If subquery uses DISTINCT, we can't make use of any stats for the
4761 : * variable ... but, if it's the only DISTINCT column, we are entitled
4762 : * to consider it unique. We do the test this way so that it works
4763 : * for cases involving DISTINCT ON.
4764 : */
4765 1840 : if (subquery->distinctClause)
4766 : {
4767 200 : if (list_length(subquery->distinctClause) == 1 &&
4768 68 : targetIsInSortList(ste, InvalidOid, subquery->distinctClause))
4769 68 : vardata->isunique = true;
4770 : /* cannot go further */
4771 132 : return;
4772 : }
4773 :
4774 : /*
4775 : * If the sub-query originated from a view with the security_barrier
4776 : * attribute, we must not look at the variable's statistics, though it
4777 : * seems all right to notice the existence of a DISTINCT clause. So
4778 : * stop here.
4779 : *
4780 : * This is probably a harsher restriction than necessary; it's
4781 : * certainly OK for the selectivity estimator (which is a C function,
4782 : * and therefore omnipotent anyway) to look at the statistics. But
4783 : * many selectivity estimators will happily *invoke the operator
4784 : * function* to try to work out a good estimate - and that's not OK.
4785 : * So for now, don't dig down for stats.
4786 : */
4787 1708 : if (rte->security_barrier)
4788 140 : return;
4789 :
4790 : /* Can only handle a simple Var of subquery's query level */
4791 2116 : if (var && IsA(var, Var) &&
4792 548 : var->varlevelsup == 0)
4793 : {
4794 : /*
4795 : * OK, recurse into the subquery. Note that the original setting
4796 : * of vardata->isunique (which will surely be false) is left
4797 : * unchanged in this situation. That's what we want, since even
4798 : * if the underlying column is unique, the subquery may have
4799 : * joined to other tables in a way that creates duplicates.
4800 : */
4801 548 : examine_simple_variable(rel->subroot, var, vardata);
4802 : }
4803 : }
4804 : else
4805 : {
4806 : /*
4807 : * Otherwise, the Var comes from a FUNCTION, VALUES, or CTE RTE. (We
4808 : * won't see RTE_JOIN here because join alias Vars have already been
4809 : * flattened.) There's not much we can do with function outputs, but
4810 : * maybe someday try to be smarter about VALUES and/or CTEs.
4811 : */
4812 : }
4813 : }
4814 :
4815 : /*
4816 : * Check whether it is permitted to call func_oid passing some of the
4817 : * pg_statistic data in vardata. We allow this either if the user has SELECT
4818 : * privileges on the table or column underlying the pg_statistic data or if
4819 : * the function is marked leak-proof.
4820 : */
4821 : bool
4822 585400 : statistic_proc_security_check(VariableStatData *vardata, Oid func_oid)
4823 : {
4824 585400 : if (vardata->acl_ok)
4825 585088 : return true;
4826 :
4827 312 : if (!OidIsValid(func_oid))
4828 0 : return false;
4829 :
4830 312 : if (get_func_leakproof(func_oid))
4831 288 : return true;
4832 :
4833 24 : ereport(DEBUG2,
4834 : (errmsg_internal("not using statistics because function \"%s\" is not leak-proof",
4835 : get_func_name(func_oid))));
4836 24 : return false;
4837 : }
4838 :
4839 : /*
4840 : * get_variable_numdistinct
4841 : * Estimate the number of distinct values of a variable.
4842 : *
4843 : * vardata: results of examine_variable
4844 : * *isdefault: set to true if the result is a default rather than based on
4845 : * anything meaningful.
4846 : *
4847 : * NB: be careful to produce a positive integral result, since callers may
4848 : * compare the result to exact integer counts, or might divide by it.
4849 : */
4850 : double
4851 485258 : get_variable_numdistinct(VariableStatData *vardata, bool *isdefault)
4852 : {
4853 : double stadistinct;
4854 485258 : double stanullfrac = 0.0;
4855 : double ntuples;
4856 :
4857 485258 : *isdefault = false;
4858 :
4859 : /*
4860 : * Determine the stadistinct value to use. There are cases where we can
4861 : * get an estimate even without a pg_statistic entry, or can get a better
4862 : * value than is in pg_statistic. Grab stanullfrac too if we can find it
4863 : * (otherwise, assume no nulls, for lack of any better idea).
4864 : */
4865 485258 : if (HeapTupleIsValid(vardata->statsTuple))
4866 : {
4867 : /* Use the pg_statistic entry */
4868 : Form_pg_statistic stats;
4869 :
4870 306418 : stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
4871 306418 : stadistinct = stats->stadistinct;
4872 306418 : stanullfrac = stats->stanullfrac;
4873 : }
4874 178840 : else if (vardata->vartype == BOOLOID)
4875 : {
4876 : /*
4877 : * Special-case boolean columns: presumably, two distinct values.
4878 : *
4879 : * Are there any other datatypes we should wire in special estimates
4880 : * for?
4881 : */
4882 140 : stadistinct = 2.0;
4883 : }
4884 178700 : else if (vardata->rel && vardata->rel->rtekind == RTE_VALUES)
4885 : {
4886 : /*
4887 : * If the Var represents a column of a VALUES RTE, assume it's unique.
4888 : * This could of course be very wrong, but it should tend to be true
4889 : * in well-written queries. We could consider examining the VALUES'
4890 : * contents to get some real statistics; but that only works if the
4891 : * entries are all constants, and it would be pretty expensive anyway.
4892 : */
4893 816 : stadistinct = -1.0; /* unique (and all non null) */
4894 : }
4895 : else
4896 : {
4897 : /*
4898 : * We don't keep statistics for system columns, but in some cases we
4899 : * can infer distinctness anyway.
4900 : */
4901 177884 : if (vardata->var && IsA(vardata->var, Var))
4902 : {
4903 172682 : switch (((Var *) vardata->var)->varattno)
4904 : {
4905 : case SelfItemPointerAttributeNumber:
4906 474 : stadistinct = -1.0; /* unique (and all non null) */
4907 474 : break;
4908 : case TableOidAttributeNumber:
4909 1978 : stadistinct = 1.0; /* only 1 value */
4910 1978 : break;
4911 : default:
4912 170230 : stadistinct = 0.0; /* means "unknown" */
4913 170230 : break;
4914 : }
4915 172682 : }
4916 : else
4917 5202 : stadistinct = 0.0; /* means "unknown" */
4918 :
4919 : /*
4920 : * XXX consider using estimate_num_groups on expressions?
4921 : */
4922 : }
4923 :
4924 : /*
4925 : * If there is a unique index or DISTINCT clause for the variable, assume
4926 : * it is unique no matter what pg_statistic says; the statistics could be
4927 : * out of date, or we might have found a partial unique index that proves
4928 : * the var is unique for this query. However, we'd better still believe
4929 : * the null-fraction statistic.
4930 : */
4931 485258 : if (vardata->isunique)
4932 110104 : stadistinct = -1.0 * (1.0 - stanullfrac);
4933 :
4934 : /*
4935 : * If we had an absolute estimate, use that.
4936 : */
4937 485258 : if (stadistinct > 0.0)
4938 77752 : return clamp_row_est(stadistinct);
4939 :
4940 : /*
4941 : * Otherwise we need to get the relation size; punt if not available.
4942 : */
4943 407506 : if (vardata->rel == NULL)
4944 : {
4945 124 : *isdefault = true;
4946 124 : return DEFAULT_NUM_DISTINCT;
4947 : }
4948 407382 : ntuples = vardata->rel->tuples;
4949 407382 : if (ntuples <= 0.0)
4950 : {
4951 1276 : *isdefault = true;
4952 1276 : return DEFAULT_NUM_DISTINCT;
4953 : }
4954 :
4955 : /*
4956 : * If we had a relative estimate, use that.
4957 : */
4958 406106 : if (stadistinct < 0.0)
4959 255484 : return clamp_row_est(-stadistinct * ntuples);
4960 :
4961 : /*
4962 : * With no data, estimate ndistinct = ntuples if the table is small, else
4963 : * use default. We use DEFAULT_NUM_DISTINCT as the cutoff for "small" so
4964 : * that the behavior isn't discontinuous.
4965 : */
4966 150622 : if (ntuples < DEFAULT_NUM_DISTINCT)
4967 53478 : return clamp_row_est(ntuples);
4968 :
4969 97144 : *isdefault = true;
4970 97144 : return DEFAULT_NUM_DISTINCT;
4971 : }
4972 :
4973 : /*
4974 : * get_variable_range
4975 : * Estimate the minimum and maximum value of the specified variable.
4976 : * If successful, store values in *min and *max, and return true.
4977 : * If no data available, return false.
4978 : *
4979 : * sortop is the "<" comparison operator to use. This should generally
4980 : * be "<" not ">", as only the former is likely to be found in pg_statistic.
4981 : */
4982 : static bool
4983 86752 : get_variable_range(PlannerInfo *root, VariableStatData *vardata, Oid sortop,
4984 : Datum *min, Datum *max)
4985 : {
4986 86752 : Datum tmin = 0;
4987 86752 : Datum tmax = 0;
4988 86752 : bool have_data = false;
4989 : int16 typLen;
4990 : bool typByVal;
4991 : Oid opfuncoid;
4992 : AttStatsSlot sslot;
4993 : int i;
4994 :
4995 : /*
4996 : * XXX It's very tempting to try to use the actual column min and max, if
4997 : * we can get them relatively-cheaply with an index probe. However, since
4998 : * this function is called many times during join planning, that could
4999 : * have unpleasant effects on planning speed. Need more investigation
5000 : * before enabling this.
5001 : */
5002 : #ifdef NOT_USED
5003 : if (get_actual_variable_range(root, vardata, sortop, min, max))
5004 : return true;
5005 : #endif
5006 :
5007 86752 : if (!HeapTupleIsValid(vardata->statsTuple))
5008 : {
5009 : /* no stats available, so default result */
5010 18128 : return false;
5011 : }
5012 :
5013 : /*
5014 : * If we can't apply the sortop to the stats data, just fail. In
5015 : * principle, if there's a histogram and no MCVs, we could return the
5016 : * histogram endpoints without ever applying the sortop ... but it's
5017 : * probably not worth trying, because whatever the caller wants to do with
5018 : * the endpoints would likely fail the security check too.
5019 : */
5020 68624 : if (!statistic_proc_security_check(vardata,
5021 : (opfuncoid = get_opcode(sortop))))
5022 0 : return false;
5023 :
5024 68624 : get_typlenbyval(vardata->atttype, &typLen, &typByVal);
5025 :
5026 : /*
5027 : * If there is a histogram, grab the first and last values.
5028 : *
5029 : * If there is a histogram that is sorted with some other operator than
5030 : * the one we want, fail --- this suggests that there is data we can't
5031 : * use.
5032 : */
5033 68624 : if (get_attstatsslot(&sslot, vardata->statsTuple,
5034 : STATISTIC_KIND_HISTOGRAM, sortop,
5035 : ATTSTATSSLOT_VALUES))
5036 : {
5037 59292 : if (sslot.nvalues > 0)
5038 : {
5039 59292 : tmin = datumCopy(sslot.values[0], typByVal, typLen);
5040 59292 : tmax = datumCopy(sslot.values[sslot.nvalues - 1], typByVal, typLen);
5041 59292 : have_data = true;
5042 : }
5043 59292 : free_attstatsslot(&sslot);
5044 : }
5045 9332 : else if (get_attstatsslot(&sslot, vardata->statsTuple,
5046 : STATISTIC_KIND_HISTOGRAM, InvalidOid,
5047 : 0))
5048 : {
5049 0 : free_attstatsslot(&sslot);
5050 0 : return false;
5051 : }
5052 :
5053 : /*
5054 : * If we have most-common-values info, look for extreme MCVs. This is
5055 : * needed even if we also have a histogram, since the histogram excludes
5056 : * the MCVs. However, usually the MCVs will not be the extreme values, so
5057 : * avoid unnecessary data copying.
5058 : */
5059 68624 : if (get_attstatsslot(&sslot, vardata->statsTuple,
5060 : STATISTIC_KIND_MCV, InvalidOid,
5061 : ATTSTATSSLOT_VALUES))
5062 : {
5063 32986 : bool tmin_is_mcv = false;
5064 32986 : bool tmax_is_mcv = false;
5065 : FmgrInfo opproc;
5066 :
5067 32986 : fmgr_info(opfuncoid, &opproc);
5068 :
5069 991906 : for (i = 0; i < sslot.nvalues; i++)
5070 : {
5071 958920 : if (!have_data)
5072 : {
5073 8972 : tmin = tmax = sslot.values[i];
5074 8972 : tmin_is_mcv = tmax_is_mcv = have_data = true;
5075 8972 : continue;
5076 : }
5077 949948 : if (DatumGetBool(FunctionCall2Coll(&opproc,
5078 : sslot.stacoll,
5079 : sslot.values[i], tmin)))
5080 : {
5081 35084 : tmin = sslot.values[i];
5082 35084 : tmin_is_mcv = true;
5083 : }
5084 949948 : if (DatumGetBool(FunctionCall2Coll(&opproc,
5085 : sslot.stacoll,
5086 : tmax, sslot.values[i])))
5087 : {
5088 30494 : tmax = sslot.values[i];
5089 30494 : tmax_is_mcv = true;
5090 : }
5091 : }
5092 32986 : if (tmin_is_mcv)
5093 27498 : tmin = datumCopy(tmin, typByVal, typLen);
5094 32986 : if (tmax_is_mcv)
5095 11180 : tmax = datumCopy(tmax, typByVal, typLen);
5096 32986 : free_attstatsslot(&sslot);
5097 : }
5098 :
5099 68624 : *min = tmin;
5100 68624 : *max = tmax;
5101 68624 : return have_data;
5102 : }
5103 :
5104 :
5105 : /*
5106 : * get_actual_variable_range
5107 : * Attempt to identify the current *actual* minimum and/or maximum
5108 : * of the specified variable, by looking for a suitable btree index
5109 : * and fetching its low and/or high values.
5110 : * If successful, store values in *min and *max, and return true.
5111 : * (Either pointer can be NULL if that endpoint isn't needed.)
5112 : * If no data available, return false.
5113 : *
5114 : * sortop is the "<" comparison operator to use.
5115 : */
5116 : static bool
5117 107232 : get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
5118 : Oid sortop,
5119 : Datum *min, Datum *max)
5120 : {
5121 107232 : bool have_data = false;
5122 107232 : RelOptInfo *rel = vardata->rel;
5123 : RangeTblEntry *rte;
5124 : ListCell *lc;
5125 :
5126 : /* No hope if no relation or it doesn't have indexes */
5127 107232 : if (rel == NULL || rel->indexlist == NIL)
5128 4518 : return false;
5129 : /* If it has indexes it must be a plain relation */
5130 102714 : rte = root->simple_rte_array[rel->relid];
5131 : Assert(rte->rtekind == RTE_RELATION);
5132 :
5133 : /* Search through the indexes to see if any match our problem */
5134 234632 : foreach(lc, rel->indexlist)
5135 : {
5136 196440 : IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
5137 : ScanDirection indexscandir;
5138 :
5139 : /* Ignore non-btree indexes */
5140 196440 : if (index->relam != BTREE_AM_OID)
5141 0 : continue;
5142 :
5143 : /*
5144 : * Ignore partial indexes --- we only want stats that cover the entire
5145 : * relation.
5146 : */
5147 196440 : if (index->indpred != NIL)
5148 68 : continue;
5149 :
5150 : /*
5151 : * The index list might include hypothetical indexes inserted by a
5152 : * get_relation_info hook --- don't try to access them.
5153 : */
5154 196372 : if (index->hypothetical)
5155 0 : continue;
5156 :
5157 : /*
5158 : * The first index column must match the desired variable and sort
5159 : * operator --- but we can use a descending-order index.
5160 : */
5161 196372 : if (!match_index_to_operand(vardata->var, 0, index))
5162 131850 : continue;
5163 64522 : switch (get_op_opfamily_strategy(sortop, index->sortopfamily[0]))
5164 : {
5165 : case BTLessStrategyNumber:
5166 64522 : if (index->reverse_sort[0])
5167 0 : indexscandir = BackwardScanDirection;
5168 : else
5169 64522 : indexscandir = ForwardScanDirection;
5170 64522 : break;
5171 : case BTGreaterStrategyNumber:
5172 0 : if (index->reverse_sort[0])
5173 0 : indexscandir = ForwardScanDirection;
5174 : else
5175 0 : indexscandir = BackwardScanDirection;
5176 0 : break;
5177 : default:
5178 : /* index doesn't match the sortop */
5179 0 : continue;
5180 : }
5181 :
5182 : /*
5183 : * Found a suitable index to extract data from. We'll need an EState
5184 : * and a bunch of other infrastructure.
5185 : */
5186 : {
5187 : EState *estate;
5188 : ExprContext *econtext;
5189 : MemoryContext tmpcontext;
5190 : MemoryContext oldcontext;
5191 : Relation heapRel;
5192 : Relation indexRel;
5193 : IndexInfo *indexInfo;
5194 : TupleTableSlot *slot;
5195 : int16 typLen;
5196 : bool typByVal;
5197 : ScanKeyData scankeys[1];
5198 : IndexScanDesc index_scan;
5199 : Datum values[INDEX_MAX_KEYS];
5200 : bool isnull[INDEX_MAX_KEYS];
5201 : SnapshotData SnapshotNonVacuumable;
5202 :
5203 64522 : estate = CreateExecutorState();
5204 64522 : econtext = GetPerTupleExprContext(estate);
5205 : /* Make sure any cruft is generated in the econtext's memory */
5206 64522 : tmpcontext = econtext->ecxt_per_tuple_memory;
5207 64522 : oldcontext = MemoryContextSwitchTo(tmpcontext);
5208 :
5209 : /*
5210 : * Open the table and index so we can read from them. We should
5211 : * already have some type of lock on each.
5212 : */
5213 64522 : heapRel = table_open(rte->relid, NoLock);
5214 64522 : indexRel = index_open(index->indexoid, NoLock);
5215 :
5216 : /* extract index key information from the index's pg_index info */
5217 64522 : indexInfo = BuildIndexInfo(indexRel);
5218 :
5219 : /* some other stuff */
5220 64522 : slot = table_slot_create(heapRel, NULL);
5221 64522 : econtext->ecxt_scantuple = slot;
5222 64522 : get_typlenbyval(vardata->atttype, &typLen, &typByVal);
5223 64522 : InitNonVacuumableSnapshot(SnapshotNonVacuumable, RecentGlobalXmin);
5224 :
5225 : /* set up an IS NOT NULL scan key so that we ignore nulls */
5226 64522 : ScanKeyEntryInitialize(&scankeys[0],
5227 : SK_ISNULL | SK_SEARCHNOTNULL,
5228 : 1, /* index col to scan */
5229 : InvalidStrategy, /* no strategy */
5230 : InvalidOid, /* no strategy subtype */
5231 : InvalidOid, /* no collation */
5232 : InvalidOid, /* no reg proc for this */
5233 : (Datum) 0); /* constant */
5234 :
5235 64522 : have_data = true;
5236 :
5237 : /* If min is requested ... */
5238 64522 : if (min)
5239 : {
5240 : /*
5241 : * In principle, we should scan the index with our current
5242 : * active snapshot, which is the best approximation we've got
5243 : * to what the query will see when executed. But that won't
5244 : * be exact if a new snap is taken before running the query,
5245 : * and it can be very expensive if a lot of recently-dead or
5246 : * uncommitted rows exist at the beginning or end of the index
5247 : * (because we'll laboriously fetch each one and reject it).
5248 : * Instead, we use SnapshotNonVacuumable. That will accept
5249 : * recently-dead and uncommitted rows as well as normal
5250 : * visible rows. On the other hand, it will reject known-dead
5251 : * rows, and thus not give a bogus answer when the extreme
5252 : * value has been deleted (unless the deletion was quite
5253 : * recent); that case motivates not using SnapshotAny here.
5254 : *
5255 : * A crucial point here is that SnapshotNonVacuumable, with
5256 : * RecentGlobalXmin as horizon, yields the inverse of the
5257 : * condition that the indexscan will use to decide that index
5258 : * entries are killable (see heap_hot_search_buffer()).
5259 : * Therefore, if the snapshot rejects a tuple and we have to
5260 : * continue scanning past it, we know that the indexscan will
5261 : * mark that index entry killed. That means that the next
5262 : * get_actual_variable_range() call will not have to visit
5263 : * that heap entry. In this way we avoid repetitive work when
5264 : * this function is used a lot during planning.
5265 : */
5266 37216 : index_scan = index_beginscan(heapRel, indexRel,
5267 : &SnapshotNonVacuumable,
5268 : 1, 0);
5269 37216 : index_rescan(index_scan, scankeys, 1, NULL, 0);
5270 :
5271 : /* Fetch first tuple in sortop's direction */
5272 37216 : if (index_getnext_slot(index_scan, indexscandir, slot))
5273 : {
5274 : /* Extract the index column values from the slot */
5275 37216 : FormIndexDatum(indexInfo, slot, estate,
5276 : values, isnull);
5277 :
5278 : /* Shouldn't have got a null, but be careful */
5279 37216 : if (isnull[0])
5280 0 : elog(ERROR, "found unexpected null value in index \"%s\"",
5281 : RelationGetRelationName(indexRel));
5282 :
5283 : /* Copy the index column value out to caller's context */
5284 37216 : MemoryContextSwitchTo(oldcontext);
5285 37216 : *min = datumCopy(values[0], typByVal, typLen);
5286 37216 : MemoryContextSwitchTo(tmpcontext);
5287 : }
5288 : else
5289 0 : have_data = false;
5290 :
5291 37216 : index_endscan(index_scan);
5292 : }
5293 :
5294 : /* If max is requested, and we didn't find the index is empty */
5295 64522 : if (max && have_data)
5296 : {
5297 27594 : index_scan = index_beginscan(heapRel, indexRel,
5298 : &SnapshotNonVacuumable,
5299 : 1, 0);
5300 27594 : index_rescan(index_scan, scankeys, 1, NULL, 0);
5301 :
5302 : /* Fetch first tuple in reverse direction */
5303 27594 : if (index_getnext_slot(index_scan, -indexscandir, slot))
5304 : {
5305 : /* Extract the index column values from the slot */
5306 27594 : FormIndexDatum(indexInfo, slot, estate,
5307 : values, isnull);
5308 :
5309 : /* Shouldn't have got a null, but be careful */
5310 27594 : if (isnull[0])
5311 0 : elog(ERROR, "found unexpected null value in index \"%s\"",
5312 : RelationGetRelationName(indexRel));
5313 :
5314 : /* Copy the index column value out to caller's context */
5315 27594 : MemoryContextSwitchTo(oldcontext);
5316 27594 : *max = datumCopy(values[0], typByVal, typLen);
5317 27594 : MemoryContextSwitchTo(tmpcontext);
5318 : }
5319 : else
5320 0 : have_data = false;
5321 :
5322 27594 : index_endscan(index_scan);
5323 : }
5324 :
5325 : /* Clean everything up */
5326 64522 : ExecDropSingleTupleTableSlot(slot);
5327 :
5328 64522 : index_close(indexRel, NoLock);
5329 64522 : table_close(heapRel, NoLock);
5330 :
5331 64522 : MemoryContextSwitchTo(oldcontext);
5332 64522 : FreeExecutorState(estate);
5333 :
5334 : /* And we're done */
5335 64522 : break;
5336 : }
5337 : }
5338 :
5339 102714 : return have_data;
5340 : }
5341 :
5342 : /*
5343 : * find_join_input_rel
5344 : * Look up the input relation for a join.
5345 : *
5346 : * We assume that the input relation's RelOptInfo must have been constructed
5347 : * already.
5348 : */
5349 : static RelOptInfo *
5350 9266 : find_join_input_rel(PlannerInfo *root, Relids relids)
5351 : {
5352 9266 : RelOptInfo *rel = NULL;
5353 :
5354 9266 : switch (bms_membership(relids))
5355 : {
5356 : case BMS_EMPTY_SET:
5357 : /* should not happen */
5358 0 : break;
5359 : case BMS_SINGLETON:
5360 9114 : rel = find_base_rel(root, bms_singleton_member(relids));
5361 9114 : break;
5362 : case BMS_MULTIPLE:
5363 152 : rel = find_join_rel(root, relids);
5364 152 : break;
5365 : }
5366 :
5367 9266 : if (rel == NULL)
5368 0 : elog(ERROR, "could not find RelOptInfo for given relids");
5369 :
5370 9266 : return rel;
5371 : }
5372 :
5373 :
5374 : /*-------------------------------------------------------------------------
5375 : *
5376 : * Index cost estimation functions
5377 : *
5378 : *-------------------------------------------------------------------------
5379 : */
5380 :
5381 : /*
5382 : * Extract the actual indexquals (as RestrictInfos) from an IndexClause list
5383 : */
5384 : List *
5385 366202 : get_quals_from_indexclauses(List *indexclauses)
5386 : {
5387 366202 : List *result = NIL;
5388 : ListCell *lc;
5389 :
5390 674230 : foreach(lc, indexclauses)
5391 : {
5392 308028 : IndexClause *iclause = lfirst_node(IndexClause, lc);
5393 : ListCell *lc2;
5394 :
5395 617802 : foreach(lc2, iclause->indexquals)
5396 : {
5397 309774 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
5398 :
5399 309774 : result = lappend(result, rinfo);
5400 : }
5401 : }
5402 366202 : return result;
5403 : }
5404 :
5405 : /*
5406 : * Compute the total evaluation cost of the comparison operands in a list
5407 : * of index qual expressions. Since we know these will be evaluated just
5408 : * once per scan, there's no need to distinguish startup from per-row cost.
5409 : *
5410 : * This can be used either on the result of get_quals_from_indexclauses(),
5411 : * or directly on an indexorderbys list. In both cases, we expect that the
5412 : * index key expression is on the left side of binary clauses.
5413 : */
5414 : Cost
5415 727314 : index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
5416 : {
5417 727314 : Cost qual_arg_cost = 0;
5418 : ListCell *lc;
5419 :
5420 1037348 : foreach(lc, indexquals)
5421 : {
5422 310034 : Expr *clause = (Expr *) lfirst(lc);
5423 : Node *other_operand;
5424 : QualCost index_qual_cost;
5425 :
5426 : /*
5427 : * Index quals will have RestrictInfos, indexorderbys won't. Look
5428 : * through RestrictInfo if present.
5429 : */
5430 310034 : if (IsA(clause, RestrictInfo))
5431 309766 : clause = ((RestrictInfo *) clause)->clause;
5432 :
5433 310034 : if (IsA(clause, OpExpr))
5434 : {
5435 301020 : OpExpr *op = (OpExpr *) clause;
5436 :
5437 301020 : other_operand = (Node *) lsecond(op->args);
5438 : }
5439 9014 : else if (IsA(clause, RowCompareExpr))
5440 : {
5441 88 : RowCompareExpr *rc = (RowCompareExpr *) clause;
5442 :
5443 88 : other_operand = (Node *) rc->rargs;
5444 : }
5445 8926 : else if (IsA(clause, ScalarArrayOpExpr))
5446 : {
5447 7028 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
5448 :
5449 7028 : other_operand = (Node *) lsecond(saop->args);
5450 : }
5451 1898 : else if (IsA(clause, NullTest))
5452 : {
5453 1898 : other_operand = NULL;
5454 : }
5455 : else
5456 : {
5457 0 : elog(ERROR, "unsupported indexqual type: %d",
5458 : (int) nodeTag(clause));
5459 : other_operand = NULL; /* keep compiler quiet */
5460 : }
5461 :
5462 310034 : cost_qual_eval_node(&index_qual_cost, other_operand, root);
5463 310034 : qual_arg_cost += index_qual_cost.startup + index_qual_cost.per_tuple;
5464 : }
5465 727314 : return qual_arg_cost;
5466 : }
5467 :
5468 : void
5469 361120 : genericcostestimate(PlannerInfo *root,
5470 : IndexPath *path,
5471 : double loop_count,
5472 : GenericCosts *costs)
5473 : {
5474 361120 : IndexOptInfo *index = path->indexinfo;
5475 361120 : List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
5476 361120 : List *indexOrderBys = path->indexorderbys;
5477 : Cost indexStartupCost;
5478 : Cost indexTotalCost;
5479 : Selectivity indexSelectivity;
5480 : double indexCorrelation;
5481 : double numIndexPages;
5482 : double numIndexTuples;
5483 : double spc_random_page_cost;
5484 : double num_sa_scans;
5485 : double num_outer_scans;
5486 : double num_scans;
5487 : double qual_op_cost;
5488 : double qual_arg_cost;
5489 : List *selectivityQuals;
5490 : ListCell *l;
5491 :
5492 : /*
5493 : * If the index is partial, AND the index predicate with the explicitly
5494 : * given indexquals to produce a more accurate idea of the index
5495 : * selectivity.
5496 : */
5497 361120 : selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
5498 :
5499 : /*
5500 : * Check for ScalarArrayOpExpr index quals, and estimate the number of
5501 : * index scans that will be performed.
5502 : */
5503 361120 : num_sa_scans = 1;
5504 665804 : foreach(l, indexQuals)
5505 : {
5506 304684 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
5507 :
5508 304684 : if (IsA(rinfo->clause, ScalarArrayOpExpr))
5509 : {
5510 7024 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) rinfo->clause;
5511 7024 : int alength = estimate_array_length(lsecond(saop->args));
5512 :
5513 7024 : if (alength > 1)
5514 7024 : num_sa_scans *= alength;
5515 : }
5516 : }
5517 :
5518 : /* Estimate the fraction of main-table tuples that will be visited */
5519 361120 : indexSelectivity = clauselist_selectivity(root, selectivityQuals,
5520 361120 : index->rel->relid,
5521 : JOIN_INNER,
5522 : NULL);
5523 :
5524 : /*
5525 : * If caller didn't give us an estimate, estimate the number of index
5526 : * tuples that will be visited. We do it in this rather peculiar-looking
5527 : * way in order to get the right answer for partial indexes.
5528 : */
5529 361120 : numIndexTuples = costs->numIndexTuples;
5530 361120 : if (numIndexTuples <= 0.0)
5531 : {
5532 18750 : numIndexTuples = indexSelectivity * index->rel->tuples;
5533 :
5534 : /*
5535 : * The above calculation counts all the tuples visited across all
5536 : * scans induced by ScalarArrayOpExpr nodes. We want to consider the
5537 : * average per-indexscan number, so adjust. This is a handy place to
5538 : * round to integer, too. (If caller supplied tuple estimate, it's
5539 : * responsible for handling these considerations.)
5540 : */
5541 18750 : numIndexTuples = rint(numIndexTuples / num_sa_scans);
5542 : }
5543 :
5544 : /*
5545 : * We can bound the number of tuples by the index size in any case. Also,
5546 : * always estimate at least one tuple is touched, even when
5547 : * indexSelectivity estimate is tiny.
5548 : */
5549 361120 : if (numIndexTuples > index->tuples)
5550 202 : numIndexTuples = index->tuples;
5551 361120 : if (numIndexTuples < 1.0)
5552 16176 : numIndexTuples = 1.0;
5553 :
5554 : /*
5555 : * Estimate the number of index pages that will be retrieved.
5556 : *
5557 : * We use the simplistic method of taking a pro-rata fraction of the total
5558 : * number of index pages. In effect, this counts only leaf pages and not
5559 : * any overhead such as index metapage or upper tree levels.
5560 : *
5561 : * In practice access to upper index levels is often nearly free because
5562 : * those tend to stay in cache under load; moreover, the cost involved is
5563 : * highly dependent on index type. We therefore ignore such costs here
5564 : * and leave it to the caller to add a suitable charge if needed.
5565 : */
5566 361120 : if (index->pages > 1 && index->tuples > 1)
5567 342520 : numIndexPages = ceil(numIndexTuples * index->pages / index->tuples);
5568 : else
5569 18600 : numIndexPages = 1.0;
5570 :
5571 : /* fetch estimated page cost for tablespace containing index */
5572 361120 : get_tablespace_page_costs(index->reltablespace,
5573 : &spc_random_page_cost,
5574 : NULL);
5575 :
5576 : /*
5577 : * Now compute the disk access costs.
5578 : *
5579 : * The above calculations are all per-index-scan. However, if we are in a
5580 : * nestloop inner scan, we can expect the scan to be repeated (with
5581 : * different search keys) for each row of the outer relation. Likewise,
5582 : * ScalarArrayOpExpr quals result in multiple index scans. This creates
5583 : * the potential for cache effects to reduce the number of disk page
5584 : * fetches needed. We want to estimate the average per-scan I/O cost in
5585 : * the presence of caching.
5586 : *
5587 : * We use the Mackert-Lohman formula (see costsize.c for details) to
5588 : * estimate the total number of page fetches that occur. While this
5589 : * wasn't what it was designed for, it seems a reasonable model anyway.
5590 : * Note that we are counting pages not tuples anymore, so we take N = T =
5591 : * index size, as if there were one "tuple" per page.
5592 : */
5593 361120 : num_outer_scans = loop_count;
5594 361120 : num_scans = num_sa_scans * num_outer_scans;
5595 :
5596 361120 : if (num_scans > 1)
5597 : {
5598 : double pages_fetched;
5599 :
5600 : /* total page fetches ignoring cache effects */
5601 47348 : pages_fetched = numIndexPages * num_scans;
5602 :
5603 : /* use Mackert and Lohman formula to adjust for cache effects */
5604 47348 : pages_fetched = index_pages_fetched(pages_fetched,
5605 : index->pages,
5606 47348 : (double) index->pages,
5607 : root);
5608 :
5609 : /*
5610 : * Now compute the total disk access cost, and then report a pro-rated
5611 : * share for each outer scan. (Don't pro-rate for ScalarArrayOpExpr,
5612 : * since that's internal to the indexscan.)
5613 : */
5614 47348 : indexTotalCost = (pages_fetched * spc_random_page_cost)
5615 : / num_outer_scans;
5616 : }
5617 : else
5618 : {
5619 : /*
5620 : * For a single index scan, we just charge spc_random_page_cost per
5621 : * page touched.
5622 : */
5623 313772 : indexTotalCost = numIndexPages * spc_random_page_cost;
5624 : }
5625 :
5626 : /*
5627 : * CPU cost: any complex expressions in the indexquals will need to be
5628 : * evaluated once at the start of the scan to reduce them to runtime keys
5629 : * to pass to the index AM (see nodeIndexscan.c). We model the per-tuple
5630 : * CPU costs as cpu_index_tuple_cost plus one cpu_operator_cost per
5631 : * indexqual operator. Because we have numIndexTuples as a per-scan
5632 : * number, we have to multiply by num_sa_scans to get the correct result
5633 : * for ScalarArrayOpExpr cases. Similarly add in costs for any index
5634 : * ORDER BY expressions.
5635 : *
5636 : * Note: this neglects the possible costs of rechecking lossy operators.
5637 : * Detecting that that might be needed seems more expensive than it's
5638 : * worth, though, considering all the other inaccuracies here ...
5639 : */
5640 722240 : qual_arg_cost = index_other_operands_eval_cost(root, indexQuals) +
5641 361120 : index_other_operands_eval_cost(root, indexOrderBys);
5642 361120 : qual_op_cost = cpu_operator_cost *
5643 361120 : (list_length(indexQuals) + list_length(indexOrderBys));
5644 :
5645 361120 : indexStartupCost = qual_arg_cost;
5646 361120 : indexTotalCost += qual_arg_cost;
5647 361120 : indexTotalCost += numIndexTuples * num_sa_scans * (cpu_index_tuple_cost + qual_op_cost);
5648 :
5649 : /*
5650 : * Generic assumption about index correlation: there isn't any.
5651 : */
5652 361120 : indexCorrelation = 0.0;
5653 :
5654 : /*
5655 : * Return everything to caller.
5656 : */
5657 361120 : costs->indexStartupCost = indexStartupCost;
5658 361120 : costs->indexTotalCost = indexTotalCost;
5659 361120 : costs->indexSelectivity = indexSelectivity;
5660 361120 : costs->indexCorrelation = indexCorrelation;
5661 361120 : costs->numIndexPages = numIndexPages;
5662 361120 : costs->numIndexTuples = numIndexTuples;
5663 361120 : costs->spc_random_page_cost = spc_random_page_cost;
5664 361120 : costs->num_sa_scans = num_sa_scans;
5665 361120 : }
5666 :
5667 : /*
5668 : * If the index is partial, add its predicate to the given qual list.
5669 : *
5670 : * ANDing the index predicate with the explicitly given indexquals produces
5671 : * a more accurate idea of the index's selectivity. However, we need to be
5672 : * careful not to insert redundant clauses, because clauselist_selectivity()
5673 : * is easily fooled into computing a too-low selectivity estimate. Our
5674 : * approach is to add only the predicate clause(s) that cannot be proven to
5675 : * be implied by the given indexquals. This successfully handles cases such
5676 : * as a qual "x = 42" used with a partial index "WHERE x >= 40 AND x < 50".
5677 : * There are many other cases where we won't detect redundancy, leading to a
5678 : * too-low selectivity estimate, which will bias the system in favor of using
5679 : * partial indexes where possible. That is not necessarily bad though.
5680 : *
5681 : * Note that indexQuals contains RestrictInfo nodes while the indpred
5682 : * does not, so the output list will be mixed. This is OK for both
5683 : * predicate_implied_by() and clauselist_selectivity(), but might be
5684 : * problematic if the result were passed to other things.
5685 : */
5686 : List *
5687 614586 : add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
5688 : {
5689 614586 : List *predExtraQuals = NIL;
5690 : ListCell *lc;
5691 :
5692 614586 : if (index->indpred == NIL)
5693 613348 : return indexQuals;
5694 :
5695 2484 : foreach(lc, index->indpred)
5696 : {
5697 1246 : Node *predQual = (Node *) lfirst(lc);
5698 1246 : List *oneQual = list_make1(predQual);
5699 :
5700 1246 : if (!predicate_implied_by(oneQual, indexQuals, false))
5701 1096 : predExtraQuals = list_concat(predExtraQuals, oneQual);
5702 : }
5703 : /* list_concat avoids modifying the passed-in indexQuals list */
5704 1238 : return list_concat(predExtraQuals, indexQuals);
5705 : }
5706 :
5707 :
5708 : void
5709 358166 : btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
5710 : Cost *indexStartupCost, Cost *indexTotalCost,
5711 : Selectivity *indexSelectivity, double *indexCorrelation,
5712 : double *indexPages)
5713 : {
5714 358166 : IndexOptInfo *index = path->indexinfo;
5715 : GenericCosts costs;
5716 : Oid relid;
5717 : AttrNumber colnum;
5718 : VariableStatData vardata;
5719 : double numIndexTuples;
5720 : Cost descentCost;
5721 : List *indexBoundQuals;
5722 : int indexcol;
5723 : bool eqQualHere;
5724 : bool found_saop;
5725 : bool found_is_null_op;
5726 : double num_sa_scans;
5727 : ListCell *lc;
5728 :
5729 : /*
5730 : * For a btree scan, only leading '=' quals plus inequality quals for the
5731 : * immediately next attribute contribute to index selectivity (these are
5732 : * the "boundary quals" that determine the starting and stopping points of
5733 : * the index scan). Additional quals can suppress visits to the heap, so
5734 : * it's OK to count them in indexSelectivity, but they should not count
5735 : * for estimating numIndexTuples. So we must examine the given indexquals
5736 : * to find out which ones count as boundary quals. We rely on the
5737 : * knowledge that they are given in index column order.
5738 : *
5739 : * For a RowCompareExpr, we consider only the first column, just as
5740 : * rowcomparesel() does.
5741 : *
5742 : * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
5743 : * index scans not one, but the ScalarArrayOpExpr's operator can be
5744 : * considered to act the same as it normally does.
5745 : */
5746 358166 : indexBoundQuals = NIL;
5747 358166 : indexcol = 0;
5748 358166 : eqQualHere = false;
5749 358166 : found_saop = false;
5750 358166 : found_is_null_op = false;
5751 358166 : num_sa_scans = 1;
5752 645916 : foreach(lc, path->indexclauses)
5753 : {
5754 296846 : IndexClause *iclause = lfirst_node(IndexClause, lc);
5755 : ListCell *lc2;
5756 :
5757 296846 : if (indexcol != iclause->indexcol)
5758 : {
5759 : /* Beginning of a new column's quals */
5760 47660 : if (!eqQualHere)
5761 8544 : break; /* done if no '=' qual for indexcol */
5762 39116 : eqQualHere = false;
5763 39116 : indexcol++;
5764 39116 : if (indexcol != iclause->indexcol)
5765 552 : break; /* no quals at all for indexcol */
5766 : }
5767 :
5768 : /* Examine each indexqual associated with this index clause */
5769 577206 : foreach(lc2, iclause->indexquals)
5770 : {
5771 289456 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
5772 289456 : Expr *clause = rinfo->clause;
5773 289456 : Oid clause_op = InvalidOid;
5774 : int op_strategy;
5775 :
5776 289456 : if (IsA(clause, OpExpr))
5777 : {
5778 280830 : OpExpr *op = (OpExpr *) clause;
5779 :
5780 280830 : clause_op = op->opno;
5781 : }
5782 8626 : else if (IsA(clause, RowCompareExpr))
5783 : {
5784 88 : RowCompareExpr *rc = (RowCompareExpr *) clause;
5785 :
5786 88 : clause_op = linitial_oid(rc->opnos);
5787 : }
5788 8538 : else if (IsA(clause, ScalarArrayOpExpr))
5789 : {
5790 6964 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
5791 6964 : Node *other_operand = (Node *) lsecond(saop->args);
5792 6964 : int alength = estimate_array_length(other_operand);
5793 :
5794 6964 : clause_op = saop->opno;
5795 6964 : found_saop = true;
5796 : /* count number of SA scans induced by indexBoundQuals only */
5797 6964 : if (alength > 1)
5798 6964 : num_sa_scans *= alength;
5799 : }
5800 1574 : else if (IsA(clause, NullTest))
5801 : {
5802 1574 : NullTest *nt = (NullTest *) clause;
5803 :
5804 1574 : if (nt->nulltesttype == IS_NULL)
5805 : {
5806 88 : found_is_null_op = true;
5807 : /* IS NULL is like = for selectivity purposes */
5808 88 : eqQualHere = true;
5809 : }
5810 : }
5811 : else
5812 0 : elog(ERROR, "unsupported indexqual type: %d",
5813 : (int) nodeTag(clause));
5814 :
5815 : /* check for equality operator */
5816 289456 : if (OidIsValid(clause_op))
5817 : {
5818 287882 : op_strategy = get_op_opfamily_strategy(clause_op,
5819 287882 : index->opfamily[indexcol]);
5820 : Assert(op_strategy != 0); /* not a member of opfamily?? */
5821 287882 : if (op_strategy == BTEqualStrategyNumber)
5822 266534 : eqQualHere = true;
5823 : }
5824 :
5825 289456 : indexBoundQuals = lappend(indexBoundQuals, rinfo);
5826 : }
5827 : }
5828 :
5829 : /*
5830 : * If index is unique and we found an '=' clause for each column, we can
5831 : * just assume numIndexTuples = 1 and skip the expensive
5832 : * clauselist_selectivity calculations. However, a ScalarArrayOp or
5833 : * NullTest invalidates that theory, even though it sets eqQualHere.
5834 : */
5835 669802 : if (index->unique &&
5836 513262 : indexcol == index->nkeycolumns - 1 &&
5837 112558 : eqQualHere &&
5838 218400 : !found_saop &&
5839 105842 : !found_is_null_op)
5840 105802 : numIndexTuples = 1.0;
5841 : else
5842 : {
5843 : List *selectivityQuals;
5844 : Selectivity btreeSelectivity;
5845 :
5846 : /*
5847 : * If the index is partial, AND the index predicate with the
5848 : * index-bound quals to produce a more accurate idea of the number of
5849 : * rows covered by the bound conditions.
5850 : */
5851 252364 : selectivityQuals = add_predicate_to_index_quals(index, indexBoundQuals);
5852 :
5853 252364 : btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
5854 252364 : index->rel->relid,
5855 : JOIN_INNER,
5856 : NULL);
5857 252364 : numIndexTuples = btreeSelectivity * index->rel->tuples;
5858 :
5859 : /*
5860 : * As in genericcostestimate(), we have to adjust for any
5861 : * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
5862 : * to integer.
5863 : */
5864 252364 : numIndexTuples = rint(numIndexTuples / num_sa_scans);
5865 : }
5866 :
5867 : /*
5868 : * Now do generic index cost estimation.
5869 : */
5870 358166 : MemSet(&costs, 0, sizeof(costs));
5871 358166 : costs.numIndexTuples = numIndexTuples;
5872 :
5873 358166 : genericcostestimate(root, path, loop_count, &costs);
5874 :
5875 : /*
5876 : * Add a CPU-cost component to represent the costs of initial btree
5877 : * descent. We don't charge any I/O cost for touching upper btree levels,
5878 : * since they tend to stay in cache, but we still have to do about log2(N)
5879 : * comparisons to descend a btree of N leaf tuples. We charge one
5880 : * cpu_operator_cost per comparison.
5881 : *
5882 : * If there are ScalarArrayOpExprs, charge this once per SA scan. The
5883 : * ones after the first one are not startup cost so far as the overall
5884 : * plan is concerned, so add them only to "total" cost.
5885 : */
5886 358166 : if (index->tuples > 1) /* avoid computing log(0) */
5887 : {
5888 356302 : descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
5889 356302 : costs.indexStartupCost += descentCost;
5890 356302 : costs.indexTotalCost += costs.num_sa_scans * descentCost;
5891 : }
5892 :
5893 : /*
5894 : * Even though we're not charging I/O cost for touching upper btree pages,
5895 : * it's still reasonable to charge some CPU cost per page descended
5896 : * through. Moreover, if we had no such charge at all, bloated indexes
5897 : * would appear to have the same search cost as unbloated ones, at least
5898 : * in cases where only a single leaf page is expected to be visited. This
5899 : * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
5900 : * touched. The number of such pages is btree tree height plus one (ie,
5901 : * we charge for the leaf page too). As above, charge once per SA scan.
5902 : */
5903 358166 : descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
5904 358166 : costs.indexStartupCost += descentCost;
5905 358166 : costs.indexTotalCost += costs.num_sa_scans * descentCost;
5906 :
5907 : /*
5908 : * If we can get an estimate of the first column's ordering correlation C
5909 : * from pg_statistic, estimate the index correlation as C for a
5910 : * single-column index, or C * 0.75 for multiple columns. (The idea here
5911 : * is that multiple columns dilute the importance of the first column's
5912 : * ordering, but don't negate it entirely. Before 8.0 we divided the
5913 : * correlation by the number of columns, but that seems too strong.)
5914 : */
5915 358166 : MemSet(&vardata, 0, sizeof(vardata));
5916 :
5917 358166 : if (index->indexkeys[0] != 0)
5918 : {
5919 : /* Simple variable --- look to stats for the underlying table */
5920 356970 : RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
5921 :
5922 : Assert(rte->rtekind == RTE_RELATION);
5923 356970 : relid = rte->relid;
5924 : Assert(relid != InvalidOid);
5925 356970 : colnum = index->indexkeys[0];
5926 :
5927 356970 : if (get_relation_stats_hook &&
5928 0 : (*get_relation_stats_hook) (root, rte, colnum, &vardata))
5929 : {
5930 : /*
5931 : * The hook took control of acquiring a stats tuple. If it did
5932 : * supply a tuple, it'd better have supplied a freefunc.
5933 : */
5934 0 : if (HeapTupleIsValid(vardata.statsTuple) &&
5935 0 : !vardata.freefunc)
5936 0 : elog(ERROR, "no function provided to release variable stats with");
5937 : }
5938 : else
5939 : {
5940 356970 : vardata.statsTuple = SearchSysCache3(STATRELATTINH,
5941 : ObjectIdGetDatum(relid),
5942 : Int16GetDatum(colnum),
5943 356970 : BoolGetDatum(rte->inh));
5944 356970 : vardata.freefunc = ReleaseSysCache;
5945 : }
5946 : }
5947 : else
5948 : {
5949 : /* Expression --- maybe there are stats for the index itself */
5950 1196 : relid = index->indexoid;
5951 1196 : colnum = 1;
5952 :
5953 1196 : if (get_index_stats_hook &&
5954 0 : (*get_index_stats_hook) (root, relid, colnum, &vardata))
5955 : {
5956 : /*
5957 : * The hook took control of acquiring a stats tuple. If it did
5958 : * supply a tuple, it'd better have supplied a freefunc.
5959 : */
5960 0 : if (HeapTupleIsValid(vardata.statsTuple) &&
5961 0 : !vardata.freefunc)
5962 0 : elog(ERROR, "no function provided to release variable stats with");
5963 : }
5964 : else
5965 : {
5966 1196 : vardata.statsTuple = SearchSysCache3(STATRELATTINH,
5967 : ObjectIdGetDatum(relid),
5968 : Int16GetDatum(colnum),
5969 : BoolGetDatum(false));
5970 1196 : vardata.freefunc = ReleaseSysCache;
5971 : }
5972 : }
5973 :
5974 358166 : if (HeapTupleIsValid(vardata.statsTuple))
5975 : {
5976 : Oid sortop;
5977 : AttStatsSlot sslot;
5978 :
5979 544528 : sortop = get_opfamily_member(index->opfamily[0],
5980 272264 : index->opcintype[0],
5981 272264 : index->opcintype[0],
5982 : BTLessStrategyNumber);
5983 544528 : if (OidIsValid(sortop) &&
5984 272264 : get_attstatsslot(&sslot, vardata.statsTuple,
5985 : STATISTIC_KIND_CORRELATION, sortop,
5986 : ATTSTATSSLOT_NUMBERS))
5987 : {
5988 : double varCorrelation;
5989 :
5990 : Assert(sslot.nnumbers == 1);
5991 270518 : varCorrelation = sslot.numbers[0];
5992 :
5993 270518 : if (index->reverse_sort[0])
5994 0 : varCorrelation = -varCorrelation;
5995 :
5996 270518 : if (index->nkeycolumns > 1)
5997 113504 : costs.indexCorrelation = varCorrelation * 0.75;
5998 : else
5999 157014 : costs.indexCorrelation = varCorrelation;
6000 :
6001 270518 : free_attstatsslot(&sslot);
6002 : }
6003 : }
6004 :
6005 358166 : ReleaseVariableStats(vardata);
6006 :
6007 358166 : *indexStartupCost = costs.indexStartupCost;
6008 358166 : *indexTotalCost = costs.indexTotalCost;
6009 358166 : *indexSelectivity = costs.indexSelectivity;
6010 358166 : *indexCorrelation = costs.indexCorrelation;
6011 358166 : *indexPages = costs.numIndexPages;
6012 358166 : }
6013 :
6014 : void
6015 270 : hashcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
6016 : Cost *indexStartupCost, Cost *indexTotalCost,
6017 : Selectivity *indexSelectivity, double *indexCorrelation,
6018 : double *indexPages)
6019 : {
6020 : GenericCosts costs;
6021 :
6022 270 : MemSet(&costs, 0, sizeof(costs));
6023 :
6024 270 : genericcostestimate(root, path, loop_count, &costs);
6025 :
6026 : /*
6027 : * A hash index has no descent costs as such, since the index AM can go
6028 : * directly to the target bucket after computing the hash value. There
6029 : * are a couple of other hash-specific costs that we could conceivably add
6030 : * here, though:
6031 : *
6032 : * Ideally we'd charge spc_random_page_cost for each page in the target
6033 : * bucket, not just the numIndexPages pages that genericcostestimate
6034 : * thought we'd visit. However in most cases we don't know which bucket
6035 : * that will be. There's no point in considering the average bucket size
6036 : * because the hash AM makes sure that's always one page.
6037 : *
6038 : * Likewise, we could consider charging some CPU for each index tuple in
6039 : * the bucket, if we knew how many there were. But the per-tuple cost is
6040 : * just a hash value comparison, not a general datatype-dependent
6041 : * comparison, so any such charge ought to be quite a bit less than
6042 : * cpu_operator_cost; which makes it probably not worth worrying about.
6043 : *
6044 : * A bigger issue is that chance hash-value collisions will result in
6045 : * wasted probes into the heap. We don't currently attempt to model this
6046 : * cost on the grounds that it's rare, but maybe it's not rare enough.
6047 : * (Any fix for this ought to consider the generic lossy-operator problem,
6048 : * though; it's not entirely hash-specific.)
6049 : */
6050 :
6051 270 : *indexStartupCost = costs.indexStartupCost;
6052 270 : *indexTotalCost = costs.indexTotalCost;
6053 270 : *indexSelectivity = costs.indexSelectivity;
6054 270 : *indexCorrelation = costs.indexCorrelation;
6055 270 : *indexPages = costs.numIndexPages;
6056 270 : }
6057 :
6058 : void
6059 1524 : gistcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
6060 : Cost *indexStartupCost, Cost *indexTotalCost,
6061 : Selectivity *indexSelectivity, double *indexCorrelation,
6062 : double *indexPages)
6063 : {
6064 1524 : IndexOptInfo *index = path->indexinfo;
6065 : GenericCosts costs;
6066 : Cost descentCost;
6067 :
6068 1524 : MemSet(&costs, 0, sizeof(costs));
6069 :
6070 1524 : genericcostestimate(root, path, loop_count, &costs);
6071 :
6072 : /*
6073 : * We model index descent costs similarly to those for btree, but to do
6074 : * that we first need an idea of the tree height. We somewhat arbitrarily
6075 : * assume that the fanout is 100, meaning the tree height is at most
6076 : * log100(index->pages).
6077 : *
6078 : * Although this computation isn't really expensive enough to require
6079 : * caching, we might as well use index->tree_height to cache it.
6080 : */
6081 1524 : if (index->tree_height < 0) /* unknown? */
6082 : {
6083 1516 : if (index->pages > 1) /* avoid computing log(0) */
6084 1184 : index->tree_height = (int) (log(index->pages) / log(100.0));
6085 : else
6086 332 : index->tree_height = 0;
6087 : }
6088 :
6089 : /*
6090 : * Add a CPU-cost component to represent the costs of initial descent. We
6091 : * just use log(N) here not log2(N) since the branching factor isn't
6092 : * necessarily two anyway. As for btree, charge once per SA scan.
6093 : */
6094 1524 : if (index->tuples > 1) /* avoid computing log(0) */
6095 : {
6096 1524 : descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6097 1524 : costs.indexStartupCost += descentCost;
6098 1524 : costs.indexTotalCost += costs.num_sa_scans * descentCost;
6099 : }
6100 :
6101 : /*
6102 : * Likewise add a per-page charge, calculated the same as for btrees.
6103 : */
6104 1524 : descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6105 1524 : costs.indexStartupCost += descentCost;
6106 1524 : costs.indexTotalCost += costs.num_sa_scans * descentCost;
6107 :
6108 1524 : *indexStartupCost = costs.indexStartupCost;
6109 1524 : *indexTotalCost = costs.indexTotalCost;
6110 1524 : *indexSelectivity = costs.indexSelectivity;
6111 1524 : *indexCorrelation = costs.indexCorrelation;
6112 1524 : *indexPages = costs.numIndexPages;
6113 1524 : }
6114 :
6115 : void
6116 1112 : spgcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
6117 : Cost *indexStartupCost, Cost *indexTotalCost,
6118 : Selectivity *indexSelectivity, double *indexCorrelation,
6119 : double *indexPages)
6120 : {
6121 1112 : IndexOptInfo *index = path->indexinfo;
6122 : GenericCosts costs;
6123 : Cost descentCost;
6124 :
6125 1112 : MemSet(&costs, 0, sizeof(costs));
6126 :
6127 1112 : genericcostestimate(root, path, loop_count, &costs);
6128 :
6129 : /*
6130 : * We model index descent costs similarly to those for btree, but to do
6131 : * that we first need an idea of the tree height. We somewhat arbitrarily
6132 : * assume that the fanout is 100, meaning the tree height is at most
6133 : * log100(index->pages).
6134 : *
6135 : * Although this computation isn't really expensive enough to require
6136 : * caching, we might as well use index->tree_height to cache it.
6137 : */
6138 1112 : if (index->tree_height < 0) /* unknown? */
6139 : {
6140 1108 : if (index->pages > 1) /* avoid computing log(0) */
6141 1108 : index->tree_height = (int) (log(index->pages) / log(100.0));
6142 : else
6143 0 : index->tree_height = 0;
6144 : }
6145 :
6146 : /*
6147 : * Add a CPU-cost component to represent the costs of initial descent. We
6148 : * just use log(N) here not log2(N) since the branching factor isn't
6149 : * necessarily two anyway. As for btree, charge once per SA scan.
6150 : */
6151 1112 : if (index->tuples > 1) /* avoid computing log(0) */
6152 : {
6153 1112 : descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6154 1112 : costs.indexStartupCost += descentCost;
6155 1112 : costs.indexTotalCost += costs.num_sa_scans * descentCost;
6156 : }
6157 :
6158 : /*
6159 : * Likewise add a per-page charge, calculated the same as for btrees.
6160 : */
6161 1112 : descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6162 1112 : costs.indexStartupCost += descentCost;
6163 1112 : costs.indexTotalCost += costs.num_sa_scans * descentCost;
6164 :
6165 1112 : *indexStartupCost = costs.indexStartupCost;
6166 1112 : *indexTotalCost = costs.indexTotalCost;
6167 1112 : *indexSelectivity = costs.indexSelectivity;
6168 1112 : *indexCorrelation = costs.indexCorrelation;
6169 1112 : *indexPages = costs.numIndexPages;
6170 1112 : }
6171 :
6172 :
6173 : /*
6174 : * Support routines for gincostestimate
6175 : */
6176 :
6177 : typedef struct
6178 : {
6179 : bool haveFullScan;
6180 : double partialEntries;
6181 : double exactEntries;
6182 : double searchEntries;
6183 : double arrayScans;
6184 : } GinQualCounts;
6185 :
6186 : /*
6187 : * Estimate the number of index terms that need to be searched for while
6188 : * testing the given GIN query, and increment the counts in *counts
6189 : * appropriately. If the query is unsatisfiable, return false.
6190 : */
6191 : static bool
6192 1114 : gincost_pattern(IndexOptInfo *index, int indexcol,
6193 : Oid clause_op, Datum query,
6194 : GinQualCounts *counts)
6195 : {
6196 : Oid extractProcOid;
6197 : Oid collation;
6198 : int strategy_op;
6199 : Oid lefttype,
6200 : righttype;
6201 1114 : int32 nentries = 0;
6202 1114 : bool *partial_matches = NULL;
6203 1114 : Pointer *extra_data = NULL;
6204 1114 : bool *nullFlags = NULL;
6205 1114 : int32 searchMode = GIN_SEARCH_MODE_DEFAULT;
6206 : int32 i;
6207 :
6208 : Assert(indexcol < index->nkeycolumns);
6209 :
6210 : /*
6211 : * Get the operator's strategy number and declared input data types within
6212 : * the index opfamily. (We don't need the latter, but we use
6213 : * get_op_opfamily_properties because it will throw error if it fails to
6214 : * find a matching pg_amop entry.)
6215 : */
6216 1114 : get_op_opfamily_properties(clause_op, index->opfamily[indexcol], false,
6217 : &strategy_op, &lefttype, &righttype);
6218 :
6219 : /*
6220 : * GIN always uses the "default" support functions, which are those with
6221 : * lefttype == righttype == the opclass' opcintype (see
6222 : * IndexSupportInitialize in relcache.c).
6223 : */
6224 2228 : extractProcOid = get_opfamily_proc(index->opfamily[indexcol],
6225 1114 : index->opcintype[indexcol],
6226 1114 : index->opcintype[indexcol],
6227 : GIN_EXTRACTQUERY_PROC);
6228 :
6229 1114 : if (!OidIsValid(extractProcOid))
6230 : {
6231 : /* should not happen; throw same error as index_getprocinfo */
6232 0 : elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
6233 : GIN_EXTRACTQUERY_PROC, indexcol + 1,
6234 : get_rel_name(index->indexoid));
6235 : }
6236 :
6237 : /*
6238 : * Choose collation to pass to extractProc (should match initGinState).
6239 : */
6240 1114 : if (OidIsValid(index->indexcollations[indexcol]))
6241 250 : collation = index->indexcollations[indexcol];
6242 : else
6243 864 : collation = DEFAULT_COLLATION_OID;
6244 :
6245 1114 : OidFunctionCall7Coll(extractProcOid,
6246 : collation,
6247 : query,
6248 : PointerGetDatum(&nentries),
6249 : UInt16GetDatum(strategy_op),
6250 : PointerGetDatum(&partial_matches),
6251 : PointerGetDatum(&extra_data),
6252 : PointerGetDatum(&nullFlags),
6253 : PointerGetDatum(&searchMode));
6254 :
6255 1114 : if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT)
6256 : {
6257 : /* No match is possible */
6258 8 : return false;
6259 : }
6260 :
6261 3744 : for (i = 0; i < nentries; i++)
6262 : {
6263 : /*
6264 : * For partial match we haven't any information to estimate number of
6265 : * matched entries in index, so, we just estimate it as 100
6266 : */
6267 2638 : if (partial_matches && partial_matches[i])
6268 302 : counts->partialEntries += 100;
6269 : else
6270 2336 : counts->exactEntries++;
6271 :
6272 2638 : counts->searchEntries++;
6273 : }
6274 :
6275 1106 : if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
6276 : {
6277 : /* Treat "include empty" like an exact-match item */
6278 28 : counts->exactEntries++;
6279 28 : counts->searchEntries++;
6280 : }
6281 1078 : else if (searchMode != GIN_SEARCH_MODE_DEFAULT)
6282 : {
6283 : /* It's GIN_SEARCH_MODE_ALL */
6284 76 : counts->haveFullScan = true;
6285 : }
6286 :
6287 1106 : return true;
6288 : }
6289 :
6290 : /*
6291 : * Estimate the number of index terms that need to be searched for while
6292 : * testing the given GIN index clause, and increment the counts in *counts
6293 : * appropriately. If the query is unsatisfiable, return false.
6294 : */
6295 : static bool
6296 1106 : gincost_opexpr(PlannerInfo *root,
6297 : IndexOptInfo *index,
6298 : int indexcol,
6299 : OpExpr *clause,
6300 : GinQualCounts *counts)
6301 : {
6302 1106 : Oid clause_op = clause->opno;
6303 1106 : Node *operand = (Node *) lsecond(clause->args);
6304 :
6305 : /* aggressively reduce to a constant, and look through relabeling */
6306 1106 : operand = estimate_expression_value(root, operand);
6307 :
6308 1106 : if (IsA(operand, RelabelType))
6309 0 : operand = (Node *) ((RelabelType *) operand)->arg;
6310 :
6311 : /*
6312 : * It's impossible to call extractQuery method for unknown operand. So
6313 : * unless operand is a Const we can't do much; just assume there will be
6314 : * one ordinary search entry from the operand at runtime.
6315 : */
6316 1106 : if (!IsA(operand, Const))
6317 : {
6318 0 : counts->exactEntries++;
6319 0 : counts->searchEntries++;
6320 0 : return true;
6321 : }
6322 :
6323 : /* If Const is null, there can be no matches */
6324 1106 : if (((Const *) operand)->constisnull)
6325 0 : return false;
6326 :
6327 : /* Otherwise, apply extractQuery and get the actual term counts */
6328 1106 : return gincost_pattern(index, indexcol, clause_op,
6329 : ((Const *) operand)->constvalue,
6330 : counts);
6331 : }
6332 :
6333 : /*
6334 : * Estimate the number of index terms that need to be searched for while
6335 : * testing the given GIN index clause, and increment the counts in *counts
6336 : * appropriately. If the query is unsatisfiable, return false.
6337 : *
6338 : * A ScalarArrayOpExpr will give rise to N separate indexscans at runtime,
6339 : * each of which involves one value from the RHS array, plus all the
6340 : * non-array quals (if any). To model this, we average the counts across
6341 : * the RHS elements, and add the averages to the counts in *counts (which
6342 : * correspond to per-indexscan costs). We also multiply counts->arrayScans
6343 : * by N, causing gincostestimate to scale up its estimates accordingly.
6344 : */
6345 : static bool
6346 4 : gincost_scalararrayopexpr(PlannerInfo *root,
6347 : IndexOptInfo *index,
6348 : int indexcol,
6349 : ScalarArrayOpExpr *clause,
6350 : double numIndexEntries,
6351 : GinQualCounts *counts)
6352 : {
6353 4 : Oid clause_op = clause->opno;
6354 4 : Node *rightop = (Node *) lsecond(clause->args);
6355 : ArrayType *arrayval;
6356 : int16 elmlen;
6357 : bool elmbyval;
6358 : char elmalign;
6359 : int numElems;
6360 : Datum *elemValues;
6361 : bool *elemNulls;
6362 : GinQualCounts arraycounts;
6363 4 : int numPossible = 0;
6364 : int i;
6365 :
6366 : Assert(clause->useOr);
6367 :
6368 : /* aggressively reduce to a constant, and look through relabeling */
6369 4 : rightop = estimate_expression_value(root, rightop);
6370 :
6371 4 : if (IsA(rightop, RelabelType))
6372 0 : rightop = (Node *) ((RelabelType *) rightop)->arg;
6373 :
6374 : /*
6375 : * It's impossible to call extractQuery method for unknown operand. So
6376 : * unless operand is a Const we can't do much; just assume there will be
6377 : * one ordinary search entry from each array entry at runtime, and fall
6378 : * back on a probably-bad estimate of the number of array entries.
6379 : */
6380 4 : if (!IsA(rightop, Const))
6381 : {
6382 0 : counts->exactEntries++;
6383 0 : counts->searchEntries++;
6384 0 : counts->arrayScans *= estimate_array_length(rightop);
6385 0 : return true;
6386 : }
6387 :
6388 : /* If Const is null, there can be no matches */
6389 4 : if (((Const *) rightop)->constisnull)
6390 0 : return false;
6391 :
6392 : /* Otherwise, extract the array elements and iterate over them */
6393 4 : arrayval = DatumGetArrayTypeP(((Const *) rightop)->constvalue);
6394 4 : get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
6395 : &elmlen, &elmbyval, &elmalign);
6396 4 : deconstruct_array(arrayval,
6397 : ARR_ELEMTYPE(arrayval),
6398 : elmlen, elmbyval, elmalign,
6399 : &elemValues, &elemNulls, &numElems);
6400 :
6401 4 : memset(&arraycounts, 0, sizeof(arraycounts));
6402 :
6403 12 : for (i = 0; i < numElems; i++)
6404 : {
6405 : GinQualCounts elemcounts;
6406 :
6407 : /* NULL can't match anything, so ignore, as the executor will */
6408 8 : if (elemNulls[i])
6409 0 : continue;
6410 :
6411 : /* Otherwise, apply extractQuery and get the actual term counts */
6412 8 : memset(&elemcounts, 0, sizeof(elemcounts));
6413 :
6414 8 : if (gincost_pattern(index, indexcol, clause_op, elemValues[i],
6415 : &elemcounts))
6416 : {
6417 : /* We ignore array elements that are unsatisfiable patterns */
6418 8 : numPossible++;
6419 :
6420 8 : if (elemcounts.haveFullScan)
6421 : {
6422 : /*
6423 : * Full index scan will be required. We treat this as if
6424 : * every key in the index had been listed in the query; is
6425 : * that reasonable?
6426 : */
6427 0 : elemcounts.partialEntries = 0;
6428 0 : elemcounts.exactEntries = numIndexEntries;
6429 0 : elemcounts.searchEntries = numIndexEntries;
6430 : }
6431 8 : arraycounts.partialEntries += elemcounts.partialEntries;
6432 8 : arraycounts.exactEntries += elemcounts.exactEntries;
6433 8 : arraycounts.searchEntries += elemcounts.searchEntries;
6434 : }
6435 : }
6436 :
6437 4 : if (numPossible == 0)
6438 : {
6439 : /* No satisfiable patterns in the array */
6440 0 : return false;
6441 : }
6442 :
6443 : /*
6444 : * Now add the averages to the global counts. This will give us an
6445 : * estimate of the average number of terms searched for in each indexscan,
6446 : * including contributions from both array and non-array quals.
6447 : */
6448 4 : counts->partialEntries += arraycounts.partialEntries / numPossible;
6449 4 : counts->exactEntries += arraycounts.exactEntries / numPossible;
6450 4 : counts->searchEntries += arraycounts.searchEntries / numPossible;
6451 :
6452 4 : counts->arrayScans *= numPossible;
6453 :
6454 4 : return true;
6455 : }
6456 :
6457 : /*
6458 : * GIN has search behavior completely different from other index types
6459 : */
6460 : void
6461 1102 : gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
6462 : Cost *indexStartupCost, Cost *indexTotalCost,
6463 : Selectivity *indexSelectivity, double *indexCorrelation,
6464 : double *indexPages)
6465 : {
6466 1102 : IndexOptInfo *index = path->indexinfo;
6467 1102 : List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
6468 : List *selectivityQuals;
6469 1102 : double numPages = index->pages,
6470 1102 : numTuples = index->tuples;
6471 : double numEntryPages,
6472 : numDataPages,
6473 : numPendingPages,
6474 : numEntries;
6475 : GinQualCounts counts;
6476 : bool matchPossible;
6477 : double partialScale;
6478 : double entryPagesFetched,
6479 : dataPagesFetched,
6480 : dataPagesFetchedBySel;
6481 : double qual_op_cost,
6482 : qual_arg_cost,
6483 : spc_random_page_cost,
6484 : outer_scans;
6485 : Relation indexRel;
6486 : GinStatsData ginStats;
6487 : ListCell *lc;
6488 :
6489 : /*
6490 : * Obtain statistical information from the meta page, if possible. Else
6491 : * set ginStats to zeroes, and we'll cope below.
6492 : */
6493 1102 : if (!index->hypothetical)
6494 : {
6495 : /* Lock should have already been obtained in plancat.c */
6496 1102 : indexRel = index_open(index->indexoid, NoLock);
6497 1102 : ginGetStats(indexRel, &ginStats);
6498 1102 : index_close(indexRel, NoLock);
6499 : }
6500 : else
6501 : {
6502 0 : memset(&ginStats, 0, sizeof(ginStats));
6503 : }
6504 :
6505 : /*
6506 : * Assuming we got valid (nonzero) stats at all, nPendingPages can be
6507 : * trusted, but the other fields are data as of the last VACUUM. We can
6508 : * scale them up to account for growth since then, but that method only
6509 : * goes so far; in the worst case, the stats might be for a completely
6510 : * empty index, and scaling them will produce pretty bogus numbers.
6511 : * Somewhat arbitrarily, set the cutoff for doing scaling at 4X growth; if
6512 : * it's grown more than that, fall back to estimating things only from the
6513 : * assumed-accurate index size. But we'll trust nPendingPages in any case
6514 : * so long as it's not clearly insane, ie, more than the index size.
6515 : */
6516 1102 : if (ginStats.nPendingPages < numPages)
6517 1102 : numPendingPages = ginStats.nPendingPages;
6518 : else
6519 0 : numPendingPages = 0;
6520 :
6521 2204 : if (numPages > 0 && ginStats.nTotalPages <= numPages &&
6522 2204 : ginStats.nTotalPages > numPages / 4 &&
6523 2204 : ginStats.nEntryPages > 0 && ginStats.nEntries > 0)
6524 1082 : {
6525 : /*
6526 : * OK, the stats seem close enough to sane to be trusted. But we
6527 : * still need to scale them by the ratio numPages / nTotalPages to
6528 : * account for growth since the last VACUUM.
6529 : */
6530 1082 : double scale = numPages / ginStats.nTotalPages;
6531 :
6532 1082 : numEntryPages = ceil(ginStats.nEntryPages * scale);
6533 1082 : numDataPages = ceil(ginStats.nDataPages * scale);
6534 1082 : numEntries = ceil(ginStats.nEntries * scale);
6535 : /* ensure we didn't round up too much */
6536 1082 : numEntryPages = Min(numEntryPages, numPages - numPendingPages);
6537 1082 : numDataPages = Min(numDataPages,
6538 : numPages - numPendingPages - numEntryPages);
6539 : }
6540 : else
6541 : {
6542 : /*
6543 : * We might get here because it's a hypothetical index, or an index
6544 : * created pre-9.1 and never vacuumed since upgrading (in which case
6545 : * its stats would read as zeroes), or just because it's grown too
6546 : * much since the last VACUUM for us to put our faith in scaling.
6547 : *
6548 : * Invent some plausible internal statistics based on the index page
6549 : * count (and clamp that to at least 10 pages, just in case). We
6550 : * estimate that 90% of the index is entry pages, and the rest is data
6551 : * pages. Estimate 100 entries per entry page; this is rather bogus
6552 : * since it'll depend on the size of the keys, but it's more robust
6553 : * than trying to predict the number of entries per heap tuple.
6554 : */
6555 20 : numPages = Max(numPages, 10);
6556 20 : numEntryPages = floor((numPages - numPendingPages) * 0.90);
6557 20 : numDataPages = numPages - numPendingPages - numEntryPages;
6558 20 : numEntries = floor(numEntryPages * 100);
6559 : }
6560 :
6561 : /* In an empty index, numEntries could be zero. Avoid divide-by-zero */
6562 1102 : if (numEntries < 1)
6563 0 : numEntries = 1;
6564 :
6565 : /*
6566 : * If the index is partial, AND the index predicate with the index-bound
6567 : * quals to produce a more accurate idea of the number of rows covered by
6568 : * the bound conditions.
6569 : */
6570 1102 : selectivityQuals = add_predicate_to_index_quals(index, indexQuals);
6571 :
6572 : /* Estimate the fraction of main-table tuples that will be visited */
6573 1102 : *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
6574 1102 : index->rel->relid,
6575 : JOIN_INNER,
6576 : NULL);
6577 :
6578 : /* fetch estimated page cost for tablespace containing index */
6579 1102 : get_tablespace_page_costs(index->reltablespace,
6580 : &spc_random_page_cost,
6581 : NULL);
6582 :
6583 : /*
6584 : * Generic assumption about index correlation: there isn't any.
6585 : */
6586 1102 : *indexCorrelation = 0.0;
6587 :
6588 : /*
6589 : * Examine quals to estimate number of search entries & partial matches
6590 : */
6591 1102 : memset(&counts, 0, sizeof(counts));
6592 1102 : counts.arrayScans = 1;
6593 1102 : matchPossible = true;
6594 :
6595 2212 : foreach(lc, path->indexclauses)
6596 : {
6597 1110 : IndexClause *iclause = lfirst_node(IndexClause, lc);
6598 : ListCell *lc2;
6599 :
6600 2212 : foreach(lc2, iclause->indexquals)
6601 : {
6602 1110 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
6603 1110 : Expr *clause = rinfo->clause;
6604 :
6605 1110 : if (IsA(clause, OpExpr))
6606 : {
6607 1106 : matchPossible = gincost_opexpr(root,
6608 : index,
6609 1106 : iclause->indexcol,
6610 : (OpExpr *) clause,
6611 : &counts);
6612 1106 : if (!matchPossible)
6613 8 : break;
6614 : }
6615 4 : else if (IsA(clause, ScalarArrayOpExpr))
6616 : {
6617 4 : matchPossible = gincost_scalararrayopexpr(root,
6618 : index,
6619 4 : iclause->indexcol,
6620 : (ScalarArrayOpExpr *) clause,
6621 : numEntries,
6622 : &counts);
6623 4 : if (!matchPossible)
6624 0 : break;
6625 : }
6626 : else
6627 : {
6628 : /* shouldn't be anything else for a GIN index */
6629 0 : elog(ERROR, "unsupported GIN indexqual type: %d",
6630 : (int) nodeTag(clause));
6631 : }
6632 : }
6633 : }
6634 :
6635 : /* Fall out if there were any provably-unsatisfiable quals */
6636 1102 : if (!matchPossible)
6637 : {
6638 8 : *indexStartupCost = 0;
6639 8 : *indexTotalCost = 0;
6640 8 : *indexSelectivity = 0;
6641 8 : return;
6642 : }
6643 :
6644 1094 : if (counts.haveFullScan || indexQuals == NIL)
6645 : {
6646 : /*
6647 : * Full index scan will be required. We treat this as if every key in
6648 : * the index had been listed in the query; is that reasonable?
6649 : */
6650 76 : counts.partialEntries = 0;
6651 76 : counts.exactEntries = numEntries;
6652 76 : counts.searchEntries = numEntries;
6653 : }
6654 :
6655 : /* Will we have more than one iteration of a nestloop scan? */
6656 1094 : outer_scans = loop_count;
6657 :
6658 : /*
6659 : * Compute cost to begin scan, first of all, pay attention to pending
6660 : * list.
6661 : */
6662 1094 : entryPagesFetched = numPendingPages;
6663 :
6664 : /*
6665 : * Estimate number of entry pages read. We need to do
6666 : * counts.searchEntries searches. Use a power function as it should be,
6667 : * but tuples on leaf pages usually is much greater. Here we include all
6668 : * searches in entry tree, including search of first entry in partial
6669 : * match algorithm
6670 : */
6671 1094 : entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
6672 :
6673 : /*
6674 : * Add an estimate of entry pages read by partial match algorithm. It's a
6675 : * scan over leaf pages in entry tree. We haven't any useful stats here,
6676 : * so estimate it as proportion. Because counts.partialEntries is really
6677 : * pretty bogus (see code above), it's possible that it is more than
6678 : * numEntries; clamp the proportion to ensure sanity.
6679 : */
6680 1094 : partialScale = counts.partialEntries / numEntries;
6681 1094 : partialScale = Min(partialScale, 1.0);
6682 :
6683 1094 : entryPagesFetched += ceil(numEntryPages * partialScale);
6684 :
6685 : /*
6686 : * Partial match algorithm reads all data pages before doing actual scan,
6687 : * so it's a startup cost. Again, we haven't any useful stats here, so
6688 : * estimate it as proportion.
6689 : */
6690 1094 : dataPagesFetched = ceil(numDataPages * partialScale);
6691 :
6692 : /*
6693 : * Calculate cache effects if more than one scan due to nestloops or array
6694 : * quals. The result is pro-rated per nestloop scan, but the array qual
6695 : * factor shouldn't be pro-rated (compare genericcostestimate).
6696 : */
6697 1094 : if (outer_scans > 1 || counts.arrayScans > 1)
6698 : {
6699 4 : entryPagesFetched *= outer_scans * counts.arrayScans;
6700 4 : entryPagesFetched = index_pages_fetched(entryPagesFetched,
6701 : (BlockNumber) numEntryPages,
6702 : numEntryPages, root);
6703 4 : entryPagesFetched /= outer_scans;
6704 4 : dataPagesFetched *= outer_scans * counts.arrayScans;
6705 4 : dataPagesFetched = index_pages_fetched(dataPagesFetched,
6706 : (BlockNumber) numDataPages,
6707 : numDataPages, root);
6708 4 : dataPagesFetched /= outer_scans;
6709 : }
6710 :
6711 : /*
6712 : * Here we use random page cost because logically-close pages could be far
6713 : * apart on disk.
6714 : */
6715 1094 : *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
6716 :
6717 : /*
6718 : * Now compute the number of data pages fetched during the scan.
6719 : *
6720 : * We assume every entry to have the same number of items, and that there
6721 : * is no overlap between them. (XXX: tsvector and array opclasses collect
6722 : * statistics on the frequency of individual keys; it would be nice to use
6723 : * those here.)
6724 : */
6725 1094 : dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
6726 :
6727 : /*
6728 : * If there is a lot of overlap among the entries, in particular if one of
6729 : * the entries is very frequent, the above calculation can grossly
6730 : * under-estimate. As a simple cross-check, calculate a lower bound based
6731 : * on the overall selectivity of the quals. At a minimum, we must read
6732 : * one item pointer for each matching entry.
6733 : *
6734 : * The width of each item pointer varies, based on the level of
6735 : * compression. We don't have statistics on that, but an average of
6736 : * around 3 bytes per item is fairly typical.
6737 : */
6738 2188 : dataPagesFetchedBySel = ceil(*indexSelectivity *
6739 1094 : (numTuples / (BLCKSZ / 3)));
6740 1094 : if (dataPagesFetchedBySel > dataPagesFetched)
6741 1020 : dataPagesFetched = dataPagesFetchedBySel;
6742 :
6743 : /* Account for cache effects, the same as above */
6744 1094 : if (outer_scans > 1 || counts.arrayScans > 1)
6745 : {
6746 4 : dataPagesFetched *= outer_scans * counts.arrayScans;
6747 4 : dataPagesFetched = index_pages_fetched(dataPagesFetched,
6748 : (BlockNumber) numDataPages,
6749 : numDataPages, root);
6750 4 : dataPagesFetched /= outer_scans;
6751 : }
6752 :
6753 : /* And apply random_page_cost as the cost per page */
6754 2188 : *indexTotalCost = *indexStartupCost +
6755 1094 : dataPagesFetched * spc_random_page_cost;
6756 :
6757 : /*
6758 : * Add on index qual eval costs, much as in genericcostestimate. But we
6759 : * can disregard indexorderbys, since GIN doesn't support those.
6760 : */
6761 1094 : qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
6762 1094 : qual_op_cost = cpu_operator_cost * list_length(indexQuals);
6763 :
6764 1094 : *indexStartupCost += qual_arg_cost;
6765 1094 : *indexTotalCost += qual_arg_cost;
6766 1094 : *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
6767 1094 : *indexPages = dataPagesFetched;
6768 : }
6769 :
6770 : /*
6771 : * BRIN has search behavior completely different from other index types
6772 : */
6773 : void
6774 3980 : brincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
6775 : Cost *indexStartupCost, Cost *indexTotalCost,
6776 : Selectivity *indexSelectivity, double *indexCorrelation,
6777 : double *indexPages)
6778 : {
6779 3980 : IndexOptInfo *index = path->indexinfo;
6780 3980 : List *indexQuals = get_quals_from_indexclauses(path->indexclauses);
6781 3980 : double numPages = index->pages;
6782 3980 : RelOptInfo *baserel = index->rel;
6783 3980 : RangeTblEntry *rte = planner_rt_fetch(baserel->relid, root);
6784 : Cost spc_seq_page_cost;
6785 : Cost spc_random_page_cost;
6786 : double qual_arg_cost;
6787 : double qualSelectivity;
6788 : BrinStatsData statsData;
6789 : double indexRanges;
6790 : double minimalRanges;
6791 : double estimatedRanges;
6792 : double selec;
6793 : Relation indexRel;
6794 : ListCell *l;
6795 : VariableStatData vardata;
6796 :
6797 : Assert(rte->rtekind == RTE_RELATION);
6798 :
6799 : /* fetch estimated page cost for the tablespace containing the index */
6800 3980 : get_tablespace_page_costs(index->reltablespace,
6801 : &spc_random_page_cost,
6802 : &spc_seq_page_cost);
6803 :
6804 : /*
6805 : * Obtain some data from the index itself. A lock should have already
6806 : * been obtained on the index in plancat.c.
6807 : */
6808 3980 : indexRel = index_open(index->indexoid, NoLock);
6809 3980 : brinGetStats(indexRel, &statsData);
6810 3980 : index_close(indexRel, NoLock);
6811 :
6812 : /*
6813 : * Compute index correlation
6814 : *
6815 : * Because we can use all index quals equally when scanning, we can use
6816 : * the largest correlation (in absolute value) among columns used by the
6817 : * query. Start at zero, the worst possible case. If we cannot find any
6818 : * correlation statistics, we will keep it as 0.
6819 : */
6820 3980 : *indexCorrelation = 0;
6821 :
6822 7960 : foreach(l, path->indexclauses)
6823 : {
6824 3980 : IndexClause *iclause = lfirst_node(IndexClause, l);
6825 3980 : AttrNumber attnum = index->indexkeys[iclause->indexcol];
6826 :
6827 : /* attempt to lookup stats in relation for this index column */
6828 3980 : if (attnum != 0)
6829 : {
6830 : /* Simple variable -- look to stats for the underlying table */
6831 3980 : if (get_relation_stats_hook &&
6832 0 : (*get_relation_stats_hook) (root, rte, attnum, &vardata))
6833 : {
6834 : /*
6835 : * The hook took control of acquiring a stats tuple. If it
6836 : * did supply a tuple, it'd better have supplied a freefunc.
6837 : */
6838 0 : if (HeapTupleIsValid(vardata.statsTuple) && !vardata.freefunc)
6839 0 : elog(ERROR,
6840 : "no function provided to release variable stats with");
6841 : }
6842 : else
6843 : {
6844 3980 : vardata.statsTuple =
6845 7960 : SearchSysCache3(STATRELATTINH,
6846 3980 : ObjectIdGetDatum(rte->relid),
6847 : Int16GetDatum(attnum),
6848 : BoolGetDatum(false));
6849 3980 : vardata.freefunc = ReleaseSysCache;
6850 : }
6851 : }
6852 : else
6853 : {
6854 : /*
6855 : * Looks like we've found an expression column in the index. Let's
6856 : * see if there's any stats for it.
6857 : */
6858 :
6859 : /* get the attnum from the 0-based index. */
6860 0 : attnum = iclause->indexcol + 1;
6861 :
6862 0 : if (get_index_stats_hook &&
6863 0 : (*get_index_stats_hook) (root, index->indexoid, attnum, &vardata))
6864 : {
6865 : /*
6866 : * The hook took control of acquiring a stats tuple. If it
6867 : * did supply a tuple, it'd better have supplied a freefunc.
6868 : */
6869 0 : if (HeapTupleIsValid(vardata.statsTuple) &&
6870 0 : !vardata.freefunc)
6871 0 : elog(ERROR, "no function provided to release variable stats with");
6872 : }
6873 : else
6874 : {
6875 0 : vardata.statsTuple = SearchSysCache3(STATRELATTINH,
6876 0 : ObjectIdGetDatum(index->indexoid),
6877 : Int16GetDatum(attnum),
6878 : BoolGetDatum(false));
6879 0 : vardata.freefunc = ReleaseSysCache;
6880 : }
6881 : }
6882 :
6883 3980 : if (HeapTupleIsValid(vardata.statsTuple))
6884 : {
6885 : AttStatsSlot sslot;
6886 :
6887 8 : if (get_attstatsslot(&sslot, vardata.statsTuple,
6888 : STATISTIC_KIND_CORRELATION, InvalidOid,
6889 : ATTSTATSSLOT_NUMBERS))
6890 : {
6891 8 : double varCorrelation = 0.0;
6892 :
6893 8 : if (sslot.nnumbers > 0)
6894 8 : varCorrelation = Abs(sslot.numbers[0]);
6895 :
6896 8 : if (varCorrelation > *indexCorrelation)
6897 8 : *indexCorrelation = varCorrelation;
6898 :
6899 8 : free_attstatsslot(&sslot);
6900 : }
6901 : }
6902 :
6903 3980 : ReleaseVariableStats(vardata);
6904 : }
6905 :
6906 3980 : qualSelectivity = clauselist_selectivity(root, indexQuals,
6907 3980 : baserel->relid,
6908 : JOIN_INNER, NULL);
6909 :
6910 : /* work out the actual number of ranges in the index */
6911 3980 : indexRanges = Max(ceil((double) baserel->pages / statsData.pagesPerRange),
6912 : 1.0);
6913 :
6914 : /*
6915 : * Now calculate the minimum possible ranges we could match with if all of
6916 : * the rows were in the perfect order in the table's heap.
6917 : */
6918 3980 : minimalRanges = ceil(indexRanges * qualSelectivity);
6919 :
6920 : /*
6921 : * Now estimate the number of ranges that we'll touch by using the
6922 : * indexCorrelation from the stats. Careful not to divide by zero (note
6923 : * we're using the absolute value of the correlation).
6924 : */
6925 3980 : if (*indexCorrelation < 1.0e-10)
6926 3972 : estimatedRanges = indexRanges;
6927 : else
6928 8 : estimatedRanges = Min(minimalRanges / *indexCorrelation, indexRanges);
6929 :
6930 : /* we expect to visit this portion of the table */
6931 3980 : selec = estimatedRanges / indexRanges;
6932 :
6933 3980 : CLAMP_PROBABILITY(selec);
6934 :
6935 3980 : *indexSelectivity = selec;
6936 :
6937 : /*
6938 : * Compute the index qual costs, much as in genericcostestimate, to add to
6939 : * the index costs. We can disregard indexorderbys, since BRIN doesn't
6940 : * support those.
6941 : */
6942 3980 : qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
6943 :
6944 : /*
6945 : * Compute the startup cost as the cost to read the whole revmap
6946 : * sequentially, including the cost to execute the index quals.
6947 : */
6948 3980 : *indexStartupCost =
6949 3980 : spc_seq_page_cost * statsData.revmapNumPages * loop_count;
6950 3980 : *indexStartupCost += qual_arg_cost;
6951 :
6952 : /*
6953 : * To read a BRIN index there might be a bit of back and forth over
6954 : * regular pages, as revmap might point to them out of sequential order;
6955 : * calculate the total cost as reading the whole index in random order.
6956 : */
6957 7960 : *indexTotalCost = *indexStartupCost +
6958 3980 : spc_random_page_cost * (numPages - statsData.revmapNumPages) * loop_count;
6959 :
6960 : /*
6961 : * Charge a small amount per range tuple which we expect to match to. This
6962 : * is meant to reflect the costs of manipulating the bitmap. The BRIN scan
6963 : * will set a bit for each page in the range when we find a matching
6964 : * range, so we must multiply the charge by the number of pages in the
6965 : * range.
6966 : */
6967 7960 : *indexTotalCost += 0.1 * cpu_operator_cost * estimatedRanges *
6968 3980 : statsData.pagesPerRange;
6969 :
6970 3980 : *indexPages = index->pages;
6971 3980 : }
|
