Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * clausesel.c
4 : : * Routines to compute clause selectivities
5 : : *
6 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/optimizer/path/clausesel.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : : #include "postgres.h"
16 : :
17 : : #include "nodes/nodeFuncs.h"
18 : : #include "optimizer/clauses.h"
19 : : #include "optimizer/optimizer.h"
20 : : #include "optimizer/pathnode.h"
21 : : #include "optimizer/plancat.h"
22 : : #include "statistics/statistics.h"
23 : : #include "utils/fmgroids.h"
24 : : #include "utils/lsyscache.h"
25 : : #include "utils/selfuncs.h"
26 : :
27 : : /*
28 : : * Data structure for accumulating info about possible range-query
29 : : * clause pairs in clauselist_selectivity.
30 : : */
31 : : typedef struct RangeQueryClause
32 : : {
33 : : struct RangeQueryClause *next; /* next in linked list */
34 : : Node *var; /* The common variable of the clauses */
35 : : bool have_lobound; /* found a low-bound clause yet? */
36 : : bool have_hibound; /* found a high-bound clause yet? */
37 : : Selectivity lobound; /* Selectivity of a var > something clause */
38 : : Selectivity hibound; /* Selectivity of a var < something clause */
39 : : } RangeQueryClause;
40 : :
41 : : static void addRangeClause(RangeQueryClause **rqlist, Node *clause,
42 : : bool varonleft, bool isLTsel, Selectivity s2);
43 : : static RelOptInfo *find_single_rel_for_clauses(PlannerInfo *root,
44 : : List *clauses);
45 : : static Selectivity clauselist_selectivity_or(PlannerInfo *root,
46 : : List *clauses,
47 : : int varRelid,
48 : : JoinType jointype,
49 : : SpecialJoinInfo *sjinfo,
50 : : bool use_extended_stats);
51 : :
52 : : /****************************************************************************
53 : : * ROUTINES TO COMPUTE SELECTIVITIES
54 : : ****************************************************************************/
55 : :
56 : : /*
57 : : * clauselist_selectivity -
58 : : * Compute the selectivity of an implicitly-ANDed list of boolean
59 : : * expression clauses. The list can be empty, in which case 1.0
60 : : * must be returned. List elements may be either RestrictInfos
61 : : * or bare expression clauses --- the former is preferred since
62 : : * it allows caching of results.
63 : : *
64 : : * See clause_selectivity() for the meaning of the additional parameters.
65 : : *
66 : : * The basic approach is to apply extended statistics first, on as many
67 : : * clauses as possible, in order to capture cross-column dependencies etc.
68 : : * The remaining clauses are then estimated by taking the product of their
69 : : * selectivities, but that's only right if they have independent
70 : : * probabilities, and in reality they are often NOT independent even if they
71 : : * only refer to a single column. So, we want to be smarter where we can.
72 : : *
73 : : * We also recognize "range queries", such as "x > 34 AND x < 42". Clauses
74 : : * are recognized as possible range query components if they are restriction
75 : : * opclauses whose operators have scalarltsel or a related function as their
76 : : * restriction selectivity estimator. We pair up clauses of this form that
77 : : * refer to the same variable. An unpairable clause of this kind is simply
78 : : * multiplied into the selectivity product in the normal way. But when we
79 : : * find a pair, we know that the selectivities represent the relative
80 : : * positions of the low and high bounds within the column's range, so instead
81 : : * of figuring the selectivity as hisel * losel, we can figure it as hisel +
82 : : * losel - 1. (To visualize this, see that hisel is the fraction of the range
83 : : * below the high bound, while losel is the fraction above the low bound; so
84 : : * hisel can be interpreted directly as a 0..1 value but we need to convert
85 : : * losel to 1-losel before interpreting it as a value. Then the available
86 : : * range is 1-losel to hisel. However, this calculation double-excludes
87 : : * nulls, so really we need hisel + losel + null_frac - 1.)
88 : : *
89 : : * If either selectivity is exactly DEFAULT_INEQ_SEL, we forget this equation
90 : : * and instead use DEFAULT_RANGE_INEQ_SEL. The same applies if the equation
91 : : * yields an impossible (negative) result.
92 : : *
93 : : * A free side-effect is that we can recognize redundant inequalities such
94 : : * as "x < 4 AND x < 5"; only the tighter constraint will be counted.
95 : : *
96 : : * Of course this is all very dependent on the behavior of the inequality
97 : : * selectivity functions; perhaps some day we can generalize the approach.
98 : : */
99 : : Selectivity
100 : 273642 : clauselist_selectivity(PlannerInfo *root,
101 : : List *clauses,
102 : : int varRelid,
103 : : JoinType jointype,
104 : : SpecialJoinInfo *sjinfo)
105 : : {
106 : 547284 : return clauselist_selectivity_ext(root, clauses, varRelid,
107 : 273642 : jointype, sjinfo, true);
108 : : }
109 : :
110 : : /*
111 : : * clauselist_selectivity_ext -
112 : : * Extended version of clauselist_selectivity(). If "use_extended_stats"
113 : : * is false, all extended statistics will be ignored, and only per-column
114 : : * statistics will be used.
115 : : */
116 : : Selectivity
117 : 274652 : clauselist_selectivity_ext(PlannerInfo *root,
118 : : List *clauses,
119 : : int varRelid,
120 : : JoinType jointype,
121 : : SpecialJoinInfo *sjinfo,
122 : : bool use_extended_stats)
123 : : {
124 : 274652 : Selectivity s1 = 1.0;
125 : 274652 : RelOptInfo *rel;
126 : 274652 : Bitmapset *estimatedclauses = NULL;
127 : 274652 : RangeQueryClause *rqlist = NULL;
128 : 274652 : ListCell *l;
129 : 274652 : int listidx;
130 : :
131 : : /*
132 : : * If there's exactly one clause, just go directly to
133 : : * clause_selectivity_ext(). None of what we might do below is relevant.
134 : : */
135 [ + + ]: 274652 : if (list_length(clauses) == 1)
136 : 274814 : return clause_selectivity_ext(root, (Node *) linitial(clauses),
137 : 137407 : varRelid, jointype, sjinfo,
138 : 137407 : use_extended_stats);
139 : :
140 : : /*
141 : : * Determine if these clauses reference a single relation. If so, and if
142 : : * it has extended statistics, try to apply those.
143 : : */
144 : 137245 : rel = find_single_rel_for_clauses(root, clauses);
145 [ + + + + : 137245 : if (use_extended_stats && rel && rel->rtekind == RTE_RELATION && rel->statlist != NIL)
+ + + + ]
146 : : {
147 : : /*
148 : : * Estimate as many clauses as possible using extended statistics.
149 : : *
150 : : * 'estimatedclauses' is populated with the 0-based list position
151 : : * index of clauses estimated here, and that should be ignored below.
152 : : */
153 : 812 : s1 = statext_clauselist_selectivity(root, clauses, varRelid,
154 : 406 : jointype, sjinfo, rel,
155 : : &estimatedclauses, false);
156 : 406 : }
157 : :
158 : : /*
159 : : * Apply normal selectivity estimates for remaining clauses. We'll be
160 : : * careful to skip any clauses which were already estimated above.
161 : : *
162 : : * Anything that doesn't look like a potential rangequery clause gets
163 : : * multiplied into s1 and forgotten. Anything that does gets inserted into
164 : : * an rqlist entry.
165 : : */
166 : 137245 : listidx = -1;
167 [ + + + + : 212492 : foreach(l, clauses)
+ + ]
168 : : {
169 : 75247 : Node *clause = (Node *) lfirst(l);
170 : 75247 : RestrictInfo *rinfo;
171 : 75247 : Selectivity s2;
172 : :
173 : 75247 : listidx++;
174 : :
175 : : /*
176 : : * Skip this clause if it's already been estimated by some other
177 : : * statistics above.
178 : : */
179 [ + + ]: 75247 : if (bms_is_member(listidx, estimatedclauses))
180 : 777 : continue;
181 : :
182 : : /* Compute the selectivity of this clause in isolation */
183 : 148940 : s2 = clause_selectivity_ext(root, clause, varRelid, jointype, sjinfo,
184 : 74470 : use_extended_stats);
185 : :
186 : : /*
187 : : * Check for being passed a RestrictInfo.
188 : : *
189 : : * If it's a pseudoconstant RestrictInfo, then s2 is either 1.0 or
190 : : * 0.0; just use that rather than looking for range pairs.
191 : : */
192 [ + + ]: 74470 : if (IsA(clause, RestrictInfo))
193 : : {
194 : 74296 : rinfo = (RestrictInfo *) clause;
195 [ + + ]: 74296 : if (rinfo->pseudoconstant)
196 : : {
197 : 4666 : s1 = s1 * s2;
198 : 4666 : continue;
199 : : }
200 : 69630 : clause = (Node *) rinfo->clause;
201 : 69630 : }
202 : : else
203 : 174 : rinfo = NULL;
204 : :
205 : : /*
206 : : * See if it looks like a restriction clause with a pseudoconstant on
207 : : * one side. (Anything more complicated than that might not behave in
208 : : * the simple way we are expecting.) Most of the tests here can be
209 : : * done more efficiently with rinfo than without.
210 : : */
211 [ + + - + ]: 69804 : if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
212 : : {
213 : 61065 : OpExpr *expr = (OpExpr *) clause;
214 : 61065 : bool varonleft = true;
215 : 61065 : bool ok;
216 : :
217 [ + + ]: 61065 : if (rinfo)
218 : : {
219 [ + + ]: 97720 : ok = (rinfo->num_base_rels == 1) &&
220 : 73658 : (is_pseudo_constant_clause_relids(lsecond(expr->args),
221 [ + + + + ]: 73658 : rinfo->right_relids) ||
222 : 1055 : (varonleft = false,
223 : 2110 : is_pseudo_constant_clause_relids(linitial(expr->args),
224 : 1055 : rinfo->left_relids)));
225 : 60891 : }
226 : : else
227 : : {
228 [ + + ]: 336 : ok = (NumRelids(root, clause) == 1) &&
229 [ + - ]: 162 : (is_pseudo_constant_clause(lsecond(expr->args)) ||
230 : 0 : (varonleft = false,
231 : 0 : is_pseudo_constant_clause(linitial(expr->args))));
232 : : }
233 : :
234 [ + + ]: 61065 : if (ok)
235 : : {
236 : : /*
237 : : * If it's not a "<"/"<="/">"/">=" operator, just merge the
238 : : * selectivity in generically. But if it's the right oprrest,
239 : : * add the clause to rqlist for later processing.
240 : : */
241 [ + + + ]: 36898 : switch (get_oprrest(expr->opno))
242 : : {
243 : : case F_SCALARLTSEL:
244 : : case F_SCALARLESEL:
245 : 4288 : addRangeClause(&rqlist, clause,
246 : 2144 : varonleft, true, s2);
247 : 2144 : break;
248 : : case F_SCALARGTSEL:
249 : : case F_SCALARGESEL:
250 : 10744 : addRangeClause(&rqlist, clause,
251 : 5372 : varonleft, false, s2);
252 : 5372 : break;
253 : : default:
254 : : /* Just merge the selectivity in generically */
255 : 29382 : s1 = s1 * s2;
256 : 29382 : break;
257 : : }
258 : 36898 : continue; /* drop to loop bottom */
259 : : }
260 [ + + ]: 61065 : }
261 : :
262 : : /* Not the right form, so treat it generically. */
263 : 32906 : s1 = s1 * s2;
264 [ - + + ]: 75247 : }
265 : :
266 : : /*
267 : : * Now scan the rangequery pair list.
268 : : */
269 [ + + ]: 143246 : while (rqlist != NULL)
270 : : {
271 : 6001 : RangeQueryClause *rqnext;
272 : :
273 [ + + + + ]: 6001 : if (rqlist->have_lobound && rqlist->have_hibound)
274 : : {
275 : : /* Successfully matched a pair of range clauses */
276 : 1377 : Selectivity s2;
277 : :
278 : : /*
279 : : * Exact equality to the default value probably means the
280 : : * selectivity function punted. This is not airtight but should
281 : : * be good enough.
282 : : */
283 [ + + - + ]: 1377 : if (rqlist->hibound == DEFAULT_INEQ_SEL ||
284 : 1017 : rqlist->lobound == DEFAULT_INEQ_SEL)
285 : : {
286 : 360 : s2 = DEFAULT_RANGE_INEQ_SEL;
287 : 360 : }
288 : : else
289 : : {
290 : 1017 : s2 = rqlist->hibound + rqlist->lobound - 1.0;
291 : :
292 : : /* Adjust for double-exclusion of NULLs */
293 : 2034 : s2 += nulltestsel(root, IS_NULL, rqlist->var,
294 : 1017 : varRelid, jointype, sjinfo);
295 : :
296 : : /*
297 : : * A zero or slightly negative s2 should be converted into a
298 : : * small positive value; we probably are dealing with a very
299 : : * tight range and got a bogus result due to roundoff errors.
300 : : * However, if s2 is very negative, then we probably have
301 : : * default selectivity estimates on one or both sides of the
302 : : * range that we failed to recognize above for some reason.
303 : : */
304 [ + + ]: 1017 : if (s2 <= 0.0)
305 : : {
306 [ + + ]: 155 : if (s2 < -0.01)
307 : : {
308 : : /*
309 : : * No data available --- use a default estimate that
310 : : * is small, but not real small.
311 : : */
312 : 2 : s2 = DEFAULT_RANGE_INEQ_SEL;
313 : 2 : }
314 : : else
315 : : {
316 : : /*
317 : : * It's just roundoff error; use a small positive
318 : : * value
319 : : */
320 : 153 : s2 = 1.0e-10;
321 : : }
322 : 155 : }
323 : : }
324 : : /* Merge in the selectivity of the pair of clauses */
325 : 1377 : s1 *= s2;
326 : 1377 : }
327 : : else
328 : : {
329 : : /* Only found one of a pair, merge it in generically */
330 [ + + ]: 4624 : if (rqlist->have_lobound)
331 : 3908 : s1 *= rqlist->lobound;
332 : : else
333 : 716 : s1 *= rqlist->hibound;
334 : : }
335 : : /* release storage and advance */
336 : 6001 : rqnext = rqlist->next;
337 : 6001 : pfree(rqlist);
338 : 6001 : rqlist = rqnext;
339 : 6001 : }
340 : :
341 : 137245 : return s1;
342 : 274652 : }
343 : :
344 : : /*
345 : : * clauselist_selectivity_or -
346 : : * Compute the selectivity of an implicitly-ORed list of boolean
347 : : * expression clauses. The list can be empty, in which case 0.0
348 : : * must be returned. List elements may be either RestrictInfos
349 : : * or bare expression clauses --- the former is preferred since
350 : : * it allows caching of results.
351 : : *
352 : : * See clause_selectivity() for the meaning of the additional parameters.
353 : : *
354 : : * The basic approach is to apply extended statistics first, on as many
355 : : * clauses as possible, in order to capture cross-column dependencies etc.
356 : : * The remaining clauses are then estimated as if they were independent.
357 : : */
358 : : static Selectivity
359 : 1059 : clauselist_selectivity_or(PlannerInfo *root,
360 : : List *clauses,
361 : : int varRelid,
362 : : JoinType jointype,
363 : : SpecialJoinInfo *sjinfo,
364 : : bool use_extended_stats)
365 : : {
366 : 1059 : Selectivity s1 = 0.0;
367 : 1059 : RelOptInfo *rel;
368 : 1059 : Bitmapset *estimatedclauses = NULL;
369 : 1059 : ListCell *lc;
370 : 1059 : int listidx;
371 : :
372 : : /*
373 : : * Determine if these clauses reference a single relation. If so, and if
374 : : * it has extended statistics, try to apply those.
375 : : */
376 : 1059 : rel = find_single_rel_for_clauses(root, clauses);
377 [ + + + + : 1059 : if (use_extended_stats && rel && rel->rtekind == RTE_RELATION && rel->statlist != NIL)
+ + + + ]
378 : : {
379 : : /*
380 : : * Estimate as many clauses as possible using extended statistics.
381 : : *
382 : : * 'estimatedclauses' is populated with the 0-based list position
383 : : * index of clauses estimated here, and that should be ignored below.
384 : : */
385 : 52 : s1 = statext_clauselist_selectivity(root, clauses, varRelid,
386 : 26 : jointype, sjinfo, rel,
387 : : &estimatedclauses, true);
388 : 26 : }
389 : :
390 : : /*
391 : : * Estimate the remaining clauses as if they were independent.
392 : : *
393 : : * Selectivities for an OR clause are computed as s1+s2 - s1*s2 to account
394 : : * for the probable overlap of selected tuple sets.
395 : : *
396 : : * XXX is this too conservative?
397 : : */
398 : 1059 : listidx = -1;
399 [ + - + + : 3719 : foreach(lc, clauses)
+ + ]
400 : : {
401 : 2660 : Selectivity s2;
402 : :
403 : 2660 : listidx++;
404 : :
405 : : /*
406 : : * Skip this clause if it's already been estimated by some other
407 : : * statistics above.
408 : : */
409 [ + + ]: 2660 : if (bms_is_member(listidx, estimatedclauses))
410 : 40 : continue;
411 : :
412 : 5240 : s2 = clause_selectivity_ext(root, (Node *) lfirst(lc), varRelid,
413 : 2620 : jointype, sjinfo, use_extended_stats);
414 : :
415 : 2620 : s1 = s1 + s2 - s1 * s2;
416 [ - + + ]: 2660 : }
417 : :
418 : 2118 : return s1;
419 : 1059 : }
420 : :
421 : : /*
422 : : * addRangeClause --- add a new range clause for clauselist_selectivity
423 : : *
424 : : * Here is where we try to match up pairs of range-query clauses
425 : : */
426 : : static void
427 : 7516 : addRangeClause(RangeQueryClause **rqlist, Node *clause,
428 : : bool varonleft, bool isLTsel, Selectivity s2)
429 : : {
430 : 7516 : RangeQueryClause *rqelem;
431 : 7516 : Node *var;
432 : 7516 : bool is_lobound;
433 : :
434 [ + + ]: 7516 : if (varonleft)
435 : : {
436 : 7480 : var = get_leftop((Expr *) clause);
437 : 7480 : is_lobound = !isLTsel; /* x < something is high bound */
438 : 7480 : }
439 : : else
440 : : {
441 : 36 : var = get_rightop((Expr *) clause);
442 : 36 : is_lobound = isLTsel; /* something < x is low bound */
443 : : }
444 : :
445 [ + + ]: 7735 : for (rqelem = *rqlist; rqelem; rqelem = rqelem->next)
446 : : {
447 : : /*
448 : : * We use full equal() here because the "var" might be a function of
449 : : * one or more attributes of the same relation...
450 : : */
451 [ + + ]: 1734 : if (!equal(var, rqelem->var))
452 : 219 : continue;
453 : : /* Found the right group to put this clause in */
454 [ + + ]: 1515 : if (is_lobound)
455 : : {
456 [ + + ]: 87 : if (!rqelem->have_lobound)
457 : : {
458 : 28 : rqelem->have_lobound = true;
459 : 28 : rqelem->lobound = s2;
460 : 28 : }
461 : : else
462 : : {
463 : :
464 : : /*------
465 : : * We have found two similar clauses, such as
466 : : * x < y AND x <= z.
467 : : * Keep only the more restrictive one.
468 : : *------
469 : : */
470 [ + + ]: 59 : if (rqelem->lobound > s2)
471 : 10 : rqelem->lobound = s2;
472 : : }
473 : 87 : }
474 : : else
475 : : {
476 [ + + ]: 1428 : if (!rqelem->have_hibound)
477 : : {
478 : 1349 : rqelem->have_hibound = true;
479 : 1349 : rqelem->hibound = s2;
480 : 1349 : }
481 : : else
482 : : {
483 : :
484 : : /*------
485 : : * We have found two similar clauses, such as
486 : : * x > y AND x >= z.
487 : : * Keep only the more restrictive one.
488 : : *------
489 : : */
490 [ + + ]: 79 : if (rqelem->hibound > s2)
491 : 26 : rqelem->hibound = s2;
492 : : }
493 : : }
494 : 1515 : return;
495 : : }
496 : :
497 : : /* No matching var found, so make a new clause-pair data structure */
498 : 6001 : rqelem = palloc_object(RangeQueryClause);
499 : 6001 : rqelem->var = var;
500 [ + + ]: 6001 : if (is_lobound)
501 : : {
502 : 5257 : rqelem->have_lobound = true;
503 : 5257 : rqelem->have_hibound = false;
504 : 5257 : rqelem->lobound = s2;
505 : 5257 : }
506 : : else
507 : : {
508 : 744 : rqelem->have_lobound = false;
509 : 744 : rqelem->have_hibound = true;
510 : 744 : rqelem->hibound = s2;
511 : : }
512 : 6001 : rqelem->next = *rqlist;
513 : 6001 : *rqlist = rqelem;
514 [ - + ]: 7516 : }
515 : :
516 : : /*
517 : : * find_single_rel_for_clauses
518 : : * Examine each clause in 'clauses' and determine if all clauses
519 : : * reference only a single relation. If so return that relation,
520 : : * otherwise return NULL.
521 : : */
522 : : static RelOptInfo *
523 : 138587 : find_single_rel_for_clauses(PlannerInfo *root, List *clauses)
524 : : {
525 : 138587 : int lastrelid = 0;
526 : 138587 : ListCell *l;
527 : :
528 [ + + + + : 200981 : foreach(l, clauses)
+ + + + ]
529 : : {
530 : 62394 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
531 : 62394 : int relid;
532 : :
533 : : /*
534 : : * If we have a list of bare clauses rather than RestrictInfos, we
535 : : * could pull out their relids the hard way with pull_varnos().
536 : : * However, currently the extended-stats machinery won't do anything
537 : : * with non-RestrictInfo clauses anyway, so there's no point in
538 : : * spending extra cycles; just fail if that's what we have.
539 : : *
540 : : * An exception to that rule is if we have a bare BoolExpr AND clause.
541 : : * We treat this as a special case because the restrictinfo machinery
542 : : * doesn't build RestrictInfos on top of AND clauses.
543 : : */
544 [ + + ]: 62394 : if (is_andclause(rinfo))
545 : : {
546 : 283 : RelOptInfo *rel;
547 : :
548 : 566 : rel = find_single_rel_for_clauses(root,
549 : 283 : ((BoolExpr *) rinfo)->args);
550 : :
551 [ + + ]: 283 : if (rel == NULL)
552 : 22 : return NULL;
553 [ + + ]: 261 : if (lastrelid == 0)
554 : 95 : lastrelid = rel->relid;
555 [ - + ]: 166 : else if (rel->relid != lastrelid)
556 : 0 : return NULL;
557 : :
558 : 261 : continue;
559 : 283 : }
560 : :
561 [ + + ]: 62111 : if (!IsA(rinfo, RestrictInfo))
562 : 149 : return NULL;
563 : :
564 [ + + ]: 61962 : if (bms_is_empty(rinfo->clause_relids))
565 : 5650 : continue; /* we can ignore variable-free clauses */
566 [ + + ]: 56312 : if (!bms_get_singleton_member(rinfo->clause_relids, &relid))
567 : 18445 : return NULL; /* multiple relations in this clause */
568 [ + + ]: 37867 : if (lastrelid == 0)
569 : 18525 : lastrelid = relid; /* first clause referencing a relation */
570 [ + + ]: 19342 : else if (relid != lastrelid)
571 : 146 : return NULL; /* relation not same as last one */
572 [ + + + ]: 62394 : }
573 : :
574 [ + + ]: 119825 : if (lastrelid != 0)
575 : 16455 : return find_base_rel(root, lastrelid);
576 : :
577 : 103370 : return NULL; /* no clauses */
578 : 138587 : }
579 : :
580 : : /*
581 : : * treat_as_join_clause -
582 : : * Decide whether an operator clause is to be handled by the
583 : : * restriction or join estimator. Subroutine for clause_selectivity().
584 : : */
585 : : static inline bool
586 : 97991 : treat_as_join_clause(PlannerInfo *root, Node *clause, RestrictInfo *rinfo,
587 : : int varRelid, SpecialJoinInfo *sjinfo)
588 : : {
589 [ + + ]: 97991 : if (varRelid != 0)
590 : : {
591 : : /*
592 : : * Caller is forcing restriction mode (eg, because we are examining an
593 : : * inner indexscan qual).
594 : : */
595 : 36578 : return false;
596 : : }
597 [ + + ]: 61413 : else if (sjinfo == NULL)
598 : : {
599 : : /*
600 : : * It must be a restriction clause, since it's being evaluated at a
601 : : * scan node.
602 : : */
603 : 35307 : return false;
604 : : }
605 : : else
606 : : {
607 : : /*
608 : : * Otherwise, it's a join if there's more than one base relation used.
609 : : * We can optimize this calculation if an rinfo was passed.
610 : : *
611 : : * XXX Since we know the clause is being evaluated at a join, the
612 : : * only way it could be single-relation is if it was delayed by outer
613 : : * joins. We intentionally count only baserels here, not OJs that
614 : : * might be present in rinfo->clause_relids, so that we direct such
615 : : * cases to the restriction qual estimators not join estimators.
616 : : * Eventually some notice should be taken of the possibility of
617 : : * injected nulls, but we'll likely want to do that in the restriction
618 : : * estimators rather than starting to treat such cases as join quals.
619 : : */
620 [ + + ]: 26106 : if (rinfo)
621 : 26029 : return (rinfo->num_base_rels > 1);
622 : : else
623 : 77 : return (NumRelids(root, clause) > 1);
624 : : }
625 : 97991 : }
626 : :
627 : :
628 : : /*
629 : : * clause_selectivity -
630 : : * Compute the selectivity of a general boolean expression clause.
631 : : *
632 : : * The clause can be either a RestrictInfo or a plain expression. If it's
633 : : * a RestrictInfo, we try to cache the selectivity for possible re-use,
634 : : * so passing RestrictInfos is preferred.
635 : : *
636 : : * varRelid is either 0 or a rangetable index.
637 : : *
638 : : * When varRelid is not 0, only variables belonging to that relation are
639 : : * considered in computing selectivity; other vars are treated as constants
640 : : * of unknown values. This is appropriate for estimating the selectivity of
641 : : * a join clause that is being used as a restriction clause in a scan of a
642 : : * nestloop join's inner relation --- varRelid should then be the ID of the
643 : : * inner relation.
644 : : *
645 : : * When varRelid is 0, all variables are treated as variables. This
646 : : * is appropriate for ordinary join clauses and restriction clauses.
647 : : *
648 : : * jointype is the join type, if the clause is a join clause. Pass JOIN_INNER
649 : : * if the clause isn't a join clause.
650 : : *
651 : : * sjinfo is NULL for a non-join clause, otherwise it provides additional
652 : : * context information about the join being performed. There are some
653 : : * special cases:
654 : : * 1. For a special (not INNER) join, sjinfo is always a member of
655 : : * root->join_info_list.
656 : : * 2. For an INNER join, sjinfo is just a transient struct, and only the
657 : : * relids and jointype fields in it can be trusted.
658 : : * It is possible for jointype to be different from sjinfo->jointype.
659 : : * This indicates we are considering a variant join: either with
660 : : * the LHS and RHS switched, or with one input unique-ified.
661 : : *
662 : : * Note: when passing nonzero varRelid, it's normally appropriate to set
663 : : * jointype == JOIN_INNER, sjinfo == NULL, even if the clause is really a
664 : : * join clause; because we aren't treating it as a join clause.
665 : : */
666 : : Selectivity
667 : 97789 : clause_selectivity(PlannerInfo *root,
668 : : Node *clause,
669 : : int varRelid,
670 : : JoinType jointype,
671 : : SpecialJoinInfo *sjinfo)
672 : : {
673 : 195578 : return clause_selectivity_ext(root, clause, varRelid,
674 : 97789 : jointype, sjinfo, true);
675 : : }
676 : :
677 : : /*
678 : : * clause_selectivity_ext -
679 : : * Extended version of clause_selectivity(). If "use_extended_stats" is
680 : : * false, all extended statistics will be ignored, and only per-column
681 : : * statistics will be used.
682 : : */
683 : : Selectivity
684 : 313544 : clause_selectivity_ext(PlannerInfo *root,
685 : : Node *clause,
686 : : int varRelid,
687 : : JoinType jointype,
688 : : SpecialJoinInfo *sjinfo,
689 : : bool use_extended_stats)
690 : : {
691 : 313544 : Selectivity s1 = 0.5; /* default for any unhandled clause type */
692 : 313544 : RestrictInfo *rinfo = NULL;
693 : 313544 : bool cacheable = false;
694 : :
695 [ + - ]: 313544 : if (clause == NULL) /* can this still happen? */
696 : 0 : return s1;
697 : :
698 [ + + ]: 313544 : if (IsA(clause, RestrictInfo))
699 : : {
700 : 310896 : rinfo = (RestrictInfo *) clause;
701 : :
702 : : /*
703 : : * If the clause is marked pseudoconstant, then it will be used as a
704 : : * gating qual and should not affect selectivity estimates; hence
705 : : * return 1.0. The only exception is that a constant FALSE may be
706 : : * taken as having selectivity 0.0, since it will surely mean no rows
707 : : * out of the plan. This case is simple enough that we need not
708 : : * bother caching the result.
709 : : */
710 [ + + ]: 310896 : if (rinfo->pseudoconstant)
711 : : {
712 [ + + ]: 4725 : if (!IsA(rinfo->clause, Const))
713 : 4687 : return (Selectivity) 1.0;
714 : 38 : }
715 : :
716 : : /*
717 : : * If possible, cache the result of the selectivity calculation for
718 : : * the clause. We can cache if varRelid is zero or the clause
719 : : * contains only vars of that relid --- otherwise varRelid will affect
720 : : * the result, so mustn't cache. Outer join quals might be examined
721 : : * with either their join's actual jointype or JOIN_INNER, so we need
722 : : * two cache variables to remember both cases. Note: we assume the
723 : : * result won't change if we are switching the input relations or
724 : : * considering a unique-ified case, so we only need one cache variable
725 : : * for all non-JOIN_INNER cases.
726 : : */
727 [ + + ]: 306209 : if (varRelid == 0 ||
728 [ + - + + ]: 174816 : rinfo->num_base_rels == 0 ||
729 [ + + ]: 105230 : (rinfo->num_base_rels == 1 &&
730 : 69586 : bms_is_member(varRelid, rinfo->clause_relids)))
731 : : {
732 : : /* Cacheable --- do we already have the result? */
733 [ + + ]: 270473 : if (jointype == JOIN_INNER)
734 : : {
735 [ + + ]: 242388 : if (rinfo->norm_selec >= 0)
736 : 187918 : return rinfo->norm_selec;
737 : 54470 : }
738 : : else
739 : : {
740 [ + + ]: 28085 : if (rinfo->outer_selec >= 0)
741 : 16331 : return rinfo->outer_selec;
742 : : }
743 : 66224 : cacheable = true;
744 : 66224 : }
745 : :
746 : : /*
747 : : * Proceed with examination of contained clause. If the clause is an
748 : : * OR-clause, we want to look at the variant with sub-RestrictInfos,
749 : : * so that per-subclause selectivities can be cached.
750 : : */
751 [ + + ]: 101960 : if (rinfo->orclause)
752 : 1055 : clause = (Node *) rinfo->orclause;
753 : : else
754 : 100905 : clause = (Node *) rinfo->clause;
755 : 101960 : }
756 : :
757 [ + + ]: 104608 : if (IsA(clause, Var))
758 : : {
759 : 1965 : Var *var = (Var *) clause;
760 : :
761 : : /*
762 : : * We probably shouldn't ever see an uplevel Var here, but if we do,
763 : : * return the default selectivity...
764 : : */
765 [ + - + + ]: 1975 : if (var->varlevelsup == 0 &&
766 [ + + ]: 1965 : (varRelid == 0 || varRelid == (int) var->varno))
767 : : {
768 : : /* Use the restriction selectivity function for a bool Var */
769 : 1964 : s1 = boolvarsel(root, (Node *) var, varRelid);
770 : 1964 : }
771 : 1965 : }
772 [ + + ]: 102643 : else if (IsA(clause, Const))
773 : : {
774 : : /* bool constant is pretty easy... */
775 : 447 : Const *con = (Const *) clause;
776 : :
777 [ + + ]: 447 : s1 = con->constisnull ? 0.0 :
778 : 436 : DatumGetBool(con->constvalue) ? 1.0 : 0.0;
779 : 447 : }
780 [ + + ]: 102196 : else if (IsA(clause, Param))
781 : : {
782 : : /* see if we can replace the Param */
783 : 5 : Node *subst = estimate_expression_value(root, clause);
784 : :
785 [ - + ]: 5 : if (IsA(subst, Const))
786 : : {
787 : : /* bool constant is pretty easy... */
788 : 0 : Const *con = (Const *) subst;
789 : :
790 [ # # ]: 0 : s1 = con->constisnull ? 0.0 :
791 : 0 : DatumGetBool(con->constvalue) ? 1.0 : 0.0;
792 : 0 : }
793 : : else
794 : : {
795 : : /* XXX any way to do better than default? */
796 : : }
797 : 5 : }
798 [ + + ]: 102191 : else if (is_notclause(clause))
799 : : {
800 : : /* inverse of the selectivity of the underlying clause */
801 : 2436 : s1 = 1.0 - clause_selectivity_ext(root,
802 : 1218 : (Node *) get_notclausearg((Expr *) clause),
803 : 1218 : varRelid,
804 : 1218 : jointype,
805 : 1218 : sjinfo,
806 : 1218 : use_extended_stats);
807 : 1218 : }
808 [ + + ]: 100973 : else if (is_andclause(clause))
809 : : {
810 : : /* share code with clauselist_selectivity() */
811 : 684 : s1 = clauselist_selectivity_ext(root,
812 : 342 : ((BoolExpr *) clause)->args,
813 : 342 : varRelid,
814 : 342 : jointype,
815 : 342 : sjinfo,
816 : 342 : use_extended_stats);
817 : 342 : }
818 [ + + ]: 100631 : else if (is_orclause(clause))
819 : : {
820 : : /*
821 : : * Almost the same thing as clauselist_selectivity, but with the
822 : : * clauses connected by OR.
823 : : */
824 : 2118 : s1 = clauselist_selectivity_or(root,
825 : 1059 : ((BoolExpr *) clause)->args,
826 : 1059 : varRelid,
827 : 1059 : jointype,
828 : 1059 : sjinfo,
829 : 1059 : use_extended_stats);
830 : 1059 : }
831 [ + + + + ]: 99572 : else if (is_opclause(clause) || IsA(clause, DistinctExpr))
832 : : {
833 : 94036 : OpExpr *opclause = (OpExpr *) clause;
834 : 94036 : Oid opno = opclause->opno;
835 : :
836 [ + + ]: 94036 : if (treat_as_join_clause(root, clause, rinfo, varRelid, sjinfo))
837 : : {
838 : : /* Estimate selectivity for a join clause. */
839 : 50700 : s1 = join_selectivity(root, opno,
840 : 25350 : opclause->args,
841 : 25350 : opclause->inputcollid,
842 : 25350 : jointype,
843 : 25350 : sjinfo);
844 : 25350 : }
845 : : else
846 : : {
847 : : /* Estimate selectivity for a restriction clause. */
848 : 137372 : s1 = restriction_selectivity(root, opno,
849 : 68686 : opclause->args,
850 : 68686 : opclause->inputcollid,
851 : 68686 : varRelid);
852 : : }
853 : :
854 : : /*
855 : : * DistinctExpr has the same representation as OpExpr, but the
856 : : * contained operator is "=" not "<>", so we must negate the result.
857 : : * This estimation method doesn't give the right behavior for nulls,
858 : : * but it's better than doing nothing.
859 : : */
860 [ + + ]: 94036 : if (IsA(clause, DistinctExpr))
861 : 29 : s1 = 1.0 - s1;
862 : 94036 : }
863 [ + + ]: 5536 : else if (is_funcclause(clause))
864 : : {
865 : 1853 : FuncExpr *funcclause = (FuncExpr *) clause;
866 : :
867 : : /* Try to get an estimate from the support function, if any */
868 : 3706 : s1 = function_selectivity(root,
869 : 1853 : funcclause->funcid,
870 : 1853 : funcclause->args,
871 : 1853 : funcclause->inputcollid,
872 : 3706 : treat_as_join_clause(root, clause, rinfo,
873 : 1853 : varRelid, sjinfo),
874 : 1853 : varRelid,
875 : 1853 : jointype,
876 : 1853 : sjinfo);
877 : :
878 : : /* If no support, fall back on boolvarsel */
879 [ + + ]: 1853 : if (s1 < 0)
880 : 1848 : s1 = boolvarsel(root, clause, varRelid);
881 : 1853 : }
882 [ + + ]: 3683 : else if (IsA(clause, ScalarArrayOpExpr))
883 : : {
884 : : /* Use node specific selectivity calculation function */
885 : 4204 : s1 = scalararraysel(root,
886 : 2102 : (ScalarArrayOpExpr *) clause,
887 : 4204 : treat_as_join_clause(root, clause, rinfo,
888 : 2102 : varRelid, sjinfo),
889 : 2102 : varRelid,
890 : 2102 : jointype,
891 : 2102 : sjinfo);
892 : 2102 : }
893 [ + + ]: 1581 : else if (IsA(clause, RowCompareExpr))
894 : : {
895 : : /* Use node specific selectivity calculation function */
896 : 84 : s1 = rowcomparesel(root,
897 : 42 : (RowCompareExpr *) clause,
898 : 42 : varRelid,
899 : 42 : jointype,
900 : 42 : sjinfo);
901 : 42 : }
902 [ + + ]: 1539 : else if (IsA(clause, NullTest))
903 : : {
904 : : /* Use node specific selectivity calculation function */
905 : 2068 : s1 = nulltestsel(root,
906 : 1034 : ((NullTest *) clause)->nulltesttype,
907 : 1034 : (Node *) ((NullTest *) clause)->arg,
908 : 1034 : varRelid,
909 : 1034 : jointype,
910 : 1034 : sjinfo);
911 : 1034 : }
912 [ + + ]: 505 : else if (IsA(clause, BooleanTest))
913 : : {
914 : : /* Use node specific selectivity calculation function */
915 : 266 : s1 = booltestsel(root,
916 : 133 : ((BooleanTest *) clause)->booltesttype,
917 : 133 : (Node *) ((BooleanTest *) clause)->arg,
918 : 133 : varRelid,
919 : 133 : jointype,
920 : 133 : sjinfo);
921 : 133 : }
922 [ + + ]: 372 : else if (IsA(clause, CurrentOfExpr))
923 : : {
924 : : /* CURRENT OF selects at most one row of its table */
925 : 66 : CurrentOfExpr *cexpr = (CurrentOfExpr *) clause;
926 : 66 : RelOptInfo *crel = find_base_rel(root, cexpr->cvarno);
927 : :
928 [ + + ]: 66 : if (crel->tuples > 0)
929 : 64 : s1 = 1.0 / crel->tuples;
930 : 66 : }
931 [ - + ]: 306 : else if (IsA(clause, RelabelType))
932 : : {
933 : : /* Not sure this case is needed, but it can't hurt */
934 : 0 : s1 = clause_selectivity_ext(root,
935 : 0 : (Node *) ((RelabelType *) clause)->arg,
936 : 0 : varRelid,
937 : 0 : jointype,
938 : 0 : sjinfo,
939 : 0 : use_extended_stats);
940 : 0 : }
941 [ - + ]: 306 : else if (IsA(clause, CoerceToDomain))
942 : : {
943 : : /* Not sure this case is needed, but it can't hurt */
944 : 0 : s1 = clause_selectivity_ext(root,
945 : 0 : (Node *) ((CoerceToDomain *) clause)->arg,
946 : 0 : varRelid,
947 : 0 : jointype,
948 : 0 : sjinfo,
949 : 0 : use_extended_stats);
950 : 0 : }
951 : : else
952 : : {
953 : : /*
954 : : * For anything else, see if we can consider it as a boolean variable.
955 : : * This only works if it's an immutable expression in Vars of a single
956 : : * relation; but there's no point in us checking that here because
957 : : * boolvarsel() will do it internally, and return a suitable default
958 : : * selectivity if not.
959 : : */
960 : 306 : s1 = boolvarsel(root, clause, varRelid);
961 : : }
962 : :
963 : : /* Cache the result if possible */
964 [ + + ]: 104608 : if (cacheable)
965 : : {
966 [ + + ]: 66219 : if (jointype == JOIN_INNER)
967 : 54465 : rinfo->norm_selec = s1;
968 : : else
969 : 11754 : rinfo->outer_selec = s1;
970 : 66219 : }
971 : :
972 : : #ifdef SELECTIVITY_DEBUG
973 : : elog(DEBUG4, "clause_selectivity: s1 %f", s1);
974 : : #endif /* SELECTIVITY_DEBUG */
975 : :
976 : 104608 : return s1;
977 : 313544 : }
|
