Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * equivclass.c
4 : * Routines for managing EquivalenceClasses
5 : *
6 : * See src/backend/optimizer/README for discussion of EquivalenceClasses.
7 : *
8 : *
9 : * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
10 : * Portions Copyright (c) 1994, Regents of the University of California
11 : *
12 : * IDENTIFICATION
13 : * src/backend/optimizer/path/equivclass.c
14 : *
15 : *-------------------------------------------------------------------------
16 : */
17 : #include "postgres.h"
18 :
19 : #include <limits.h>
20 :
21 : #include "access/stratnum.h"
22 : #include "catalog/pg_type.h"
23 : #include "nodes/makefuncs.h"
24 : #include "nodes/nodeFuncs.h"
25 : #include "optimizer/clauses.h"
26 : #include "optimizer/pathnode.h"
27 : #include "optimizer/paths.h"
28 : #include "optimizer/planmain.h"
29 : #include "optimizer/prep.h"
30 : #include "optimizer/var.h"
31 : #include "utils/lsyscache.h"
32 :
33 :
34 : static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
35 : Expr *expr, Relids relids, Relids nullable_relids,
36 : bool is_child, Oid datatype);
37 : static void generate_base_implied_equalities_const(PlannerInfo *root,
38 : EquivalenceClass *ec);
39 : static void generate_base_implied_equalities_no_const(PlannerInfo *root,
40 : EquivalenceClass *ec);
41 : static void generate_base_implied_equalities_broken(PlannerInfo *root,
42 : EquivalenceClass *ec);
43 : static List *generate_join_implied_equalities_normal(PlannerInfo *root,
44 : EquivalenceClass *ec,
45 : Relids join_relids,
46 : Relids outer_relids,
47 : Relids inner_relids);
48 : static List *generate_join_implied_equalities_broken(PlannerInfo *root,
49 : EquivalenceClass *ec,
50 : Relids nominal_join_relids,
51 : Relids outer_relids,
52 : Relids nominal_inner_relids,
53 : RelOptInfo *inner_rel);
54 : static Oid select_equality_operator(EquivalenceClass *ec,
55 : Oid lefttype, Oid righttype);
56 : static RestrictInfo *create_join_clause(PlannerInfo *root,
57 : EquivalenceClass *ec, Oid opno,
58 : EquivalenceMember *leftem,
59 : EquivalenceMember *rightem,
60 : EquivalenceClass *parent_ec);
61 : static bool reconsider_outer_join_clause(PlannerInfo *root,
62 : RestrictInfo *rinfo,
63 : bool outer_on_left);
64 : static bool reconsider_full_join_clause(PlannerInfo *root,
65 : RestrictInfo *rinfo);
66 :
67 :
68 : /*
69 : * process_equivalence
70 : * The given clause has a mergejoinable operator and can be applied without
71 : * any delay by an outer join, so its two sides can be considered equal
72 : * anywhere they are both computable; moreover that equality can be
73 : * extended transitively. Record this knowledge in the EquivalenceClass
74 : * data structure. Returns TRUE if successful, FALSE if not (in which
75 : * case caller should treat the clause as ordinary, not an equivalence).
76 : *
77 : * If below_outer_join is true, then the clause was found below the nullable
78 : * side of an outer join, so its sides might validly be both NULL rather than
79 : * strictly equal. We can still deduce equalities in such cases, but we take
80 : * care to mark an EquivalenceClass if it came from any such clauses. Also,
81 : * we have to check that both sides are either pseudo-constants or strict
82 : * functions of Vars, else they might not both go to NULL above the outer
83 : * join. (This is the main reason why we need a failure return. It's more
84 : * convenient to check this case here than at the call sites...)
85 : *
86 : * We also reject proposed equivalence clauses if they contain leaky functions
87 : * and have security_level above zero. The EC evaluation rules require us to
88 : * apply certain tests at certain joining levels, and we can't tolerate
89 : * delaying any test on security_level grounds. By rejecting candidate clauses
90 : * that might require security delays, we ensure it's safe to apply an EC
91 : * clause as soon as it's supposed to be applied.
92 : *
93 : * On success return, we have also initialized the clause's left_ec/right_ec
94 : * fields to point to the EquivalenceClass representing it. This saves lookup
95 : * effort later.
96 : *
97 : * Note: constructing merged EquivalenceClasses is a standard UNION-FIND
98 : * problem, for which there exist better data structures than simple lists.
99 : * If this code ever proves to be a bottleneck then it could be sped up ---
100 : * but for now, simple is beautiful.
101 : *
102 : * Note: this is only called during planner startup, not during GEQO
103 : * exploration, so we need not worry about whether we're in the right
104 : * memory context.
105 : */
106 : bool
107 9369 : process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
108 : bool below_outer_join)
109 : {
110 9369 : Expr *clause = restrictinfo->clause;
111 : Oid opno,
112 : collation,
113 : item1_type,
114 : item2_type;
115 : Expr *item1;
116 : Expr *item2;
117 : Relids item1_relids,
118 : item2_relids,
119 : item1_nullable_relids,
120 : item2_nullable_relids;
121 : List *opfamilies;
122 : EquivalenceClass *ec1,
123 : *ec2;
124 : EquivalenceMember *em1,
125 : *em2;
126 : ListCell *lc1;
127 :
128 : /* Should not already be marked as having generated an eclass */
129 9369 : Assert(restrictinfo->left_ec == NULL);
130 9369 : Assert(restrictinfo->right_ec == NULL);
131 :
132 : /* Reject if it is potentially postponable by security considerations */
133 9369 : if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
134 8 : return false;
135 :
136 : /* Extract info from given clause */
137 9361 : Assert(is_opclause(clause));
138 9361 : opno = ((OpExpr *) clause)->opno;
139 9361 : collation = ((OpExpr *) clause)->inputcollid;
140 9361 : item1 = (Expr *) get_leftop(clause);
141 9361 : item2 = (Expr *) get_rightop(clause);
142 9361 : item1_relids = restrictinfo->left_relids;
143 9361 : item2_relids = restrictinfo->right_relids;
144 :
145 : /*
146 : * Ensure both input expressions expose the desired collation (their types
147 : * should be OK already); see comments for canonicalize_ec_expression.
148 : */
149 9361 : item1 = canonicalize_ec_expression(item1,
150 : exprType((Node *) item1),
151 : collation);
152 9361 : item2 = canonicalize_ec_expression(item2,
153 : exprType((Node *) item2),
154 : collation);
155 :
156 : /*
157 : * Reject clauses of the form X=X. These are not as redundant as they
158 : * might seem at first glance: assuming the operator is strict, this is
159 : * really an expensive way to write X IS NOT NULL. So we must not risk
160 : * just losing the clause, which would be possible if there is already a
161 : * single-element EquivalenceClass containing X. The case is not common
162 : * enough to be worth contorting the EC machinery for, so just reject the
163 : * clause and let it be processed as a normal restriction clause.
164 : */
165 9361 : if (equal(item1, item2))
166 3 : return false; /* X=X is not a useful equivalence */
167 :
168 : /*
169 : * If below outer join, check for strictness, else reject.
170 : */
171 9358 : if (below_outer_join)
172 : {
173 960 : if (!bms_is_empty(item1_relids) &&
174 479 : contain_nonstrict_functions((Node *) item1))
175 0 : return false; /* LHS is non-strict but not constant */
176 567 : if (!bms_is_empty(item2_relids) &&
177 86 : contain_nonstrict_functions((Node *) item2))
178 0 : return false; /* RHS is non-strict but not constant */
179 : }
180 :
181 : /* Calculate nullable-relid sets for each side of the clause */
182 9358 : item1_nullable_relids = bms_intersect(item1_relids,
183 9358 : restrictinfo->nullable_relids);
184 9358 : item2_nullable_relids = bms_intersect(item2_relids,
185 9358 : restrictinfo->nullable_relids);
186 :
187 : /*
188 : * We use the declared input types of the operator, not exprType() of the
189 : * inputs, as the nominal datatypes for opfamily lookup. This presumes
190 : * that btree operators are always registered with amoplefttype and
191 : * amoprighttype equal to their declared input types. We will need this
192 : * info anyway to build EquivalenceMember nodes, and by extracting it now
193 : * we can use type comparisons to short-circuit some equal() tests.
194 : */
195 9358 : op_input_types(opno, &item1_type, &item2_type);
196 :
197 9358 : opfamilies = restrictinfo->mergeopfamilies;
198 :
199 : /*
200 : * Sweep through the existing EquivalenceClasses looking for matches to
201 : * item1 and item2. These are the possible outcomes:
202 : *
203 : * 1. We find both in the same EC. The equivalence is already known, so
204 : * there's nothing to do.
205 : *
206 : * 2. We find both in different ECs. Merge the two ECs together.
207 : *
208 : * 3. We find just one. Add the other to its EC.
209 : *
210 : * 4. We find neither. Make a new, two-entry EC.
211 : *
212 : * Note: since all ECs are built through this process or the similar
213 : * search in get_eclass_for_sort_expr(), it's impossible that we'd match
214 : * an item in more than one existing nonvolatile EC. So it's okay to stop
215 : * at the first match.
216 : */
217 9358 : ec1 = ec2 = NULL;
218 9358 : em1 = em2 = NULL;
219 17113 : foreach(lc1, root->eq_classes)
220 : {
221 7785 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
222 : ListCell *lc2;
223 :
224 : /* Never match to a volatile EC */
225 7785 : if (cur_ec->ec_has_volatile)
226 0 : continue;
227 :
228 : /*
229 : * The collation has to match; check this first since it's cheaper
230 : * than the opfamily comparison.
231 : */
232 7785 : if (collation != cur_ec->ec_collation)
233 457 : continue;
234 :
235 : /*
236 : * A "match" requires matching sets of btree opfamilies. Use of
237 : * equal() for this test has implications discussed in the comments
238 : * for get_mergejoin_opfamilies().
239 : */
240 7328 : if (!equal(opfamilies, cur_ec->ec_opfamilies))
241 2273 : continue;
242 :
243 13174 : foreach(lc2, cur_ec->ec_members)
244 : {
245 8149 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
246 :
247 8149 : Assert(!cur_em->em_is_child); /* no children yet */
248 :
249 : /*
250 : * If below an outer join, don't match constants: they're not as
251 : * constant as they look.
252 : */
253 10528 : if ((below_outer_join || cur_ec->ec_below_outer_join) &&
254 2379 : cur_em->em_is_const)
255 163 : continue;
256 :
257 15347 : if (!ec1 &&
258 14688 : item1_type == cur_em->em_datatype &&
259 7327 : equal(item1, cur_em->em_expr))
260 : {
261 493 : ec1 = cur_ec;
262 493 : em1 = cur_em;
263 493 : if (ec2)
264 30 : break;
265 : }
266 :
267 15816 : if (!ec2 &&
268 15674 : item2_type == cur_em->em_datatype &&
269 7814 : equal(item2, cur_em->em_expr))
270 : {
271 116 : ec2 = cur_ec;
272 116 : em2 = cur_em;
273 116 : if (ec1)
274 0 : break;
275 : }
276 : }
277 :
278 5055 : if (ec1 && ec2)
279 30 : break;
280 : }
281 :
282 : /* Sweep finished, what did we find? */
283 :
284 9358 : if (ec1 && ec2)
285 : {
286 : /* If case 1, nothing to do, except add to sources */
287 30 : if (ec1 == ec2)
288 : {
289 0 : ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
290 0 : ec1->ec_below_outer_join |= below_outer_join;
291 0 : ec1->ec_min_security = Min(ec1->ec_min_security,
292 : restrictinfo->security_level);
293 0 : ec1->ec_max_security = Max(ec1->ec_max_security,
294 : restrictinfo->security_level);
295 : /* mark the RI as associated with this eclass */
296 0 : restrictinfo->left_ec = ec1;
297 0 : restrictinfo->right_ec = ec1;
298 : /* mark the RI as usable with this pair of EMs */
299 0 : restrictinfo->left_em = em1;
300 0 : restrictinfo->right_em = em2;
301 0 : return true;
302 : }
303 :
304 : /*
305 : * Case 2: need to merge ec1 and ec2. This should never happen after
306 : * we've built any canonical pathkeys; if it did, those pathkeys might
307 : * be rendered non-canonical by the merge.
308 : */
309 30 : if (root->canon_pathkeys != NIL)
310 0 : elog(ERROR, "too late to merge equivalence classes");
311 :
312 : /*
313 : * We add ec2's items to ec1, then set ec2's ec_merged link to point
314 : * to ec1 and remove ec2 from the eq_classes list. We cannot simply
315 : * delete ec2 because that could leave dangling pointers in existing
316 : * PathKeys. We leave it behind with a link so that the merged EC can
317 : * be found.
318 : */
319 30 : ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
320 30 : ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
321 30 : ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
322 30 : ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
323 30 : ec1->ec_has_const |= ec2->ec_has_const;
324 : /* can't need to set has_volatile */
325 30 : ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
326 30 : ec1->ec_min_security = Min(ec1->ec_min_security,
327 : ec2->ec_min_security);
328 30 : ec1->ec_max_security = Max(ec1->ec_max_security,
329 : ec2->ec_max_security);
330 30 : ec2->ec_merged = ec1;
331 30 : root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
332 : /* just to avoid debugging confusion w/ dangling pointers: */
333 30 : ec2->ec_members = NIL;
334 30 : ec2->ec_sources = NIL;
335 30 : ec2->ec_derives = NIL;
336 30 : ec2->ec_relids = NULL;
337 30 : ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
338 30 : ec1->ec_below_outer_join |= below_outer_join;
339 30 : ec1->ec_min_security = Min(ec1->ec_min_security,
340 : restrictinfo->security_level);
341 30 : ec1->ec_max_security = Max(ec1->ec_max_security,
342 : restrictinfo->security_level);
343 : /* mark the RI as associated with this eclass */
344 30 : restrictinfo->left_ec = ec1;
345 30 : restrictinfo->right_ec = ec1;
346 : /* mark the RI as usable with this pair of EMs */
347 30 : restrictinfo->left_em = em1;
348 30 : restrictinfo->right_em = em2;
349 : }
350 9328 : else if (ec1)
351 : {
352 : /* Case 3: add item2 to ec1 */
353 463 : em2 = add_eq_member(ec1, item2, item2_relids, item2_nullable_relids,
354 : false, item2_type);
355 463 : ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
356 463 : ec1->ec_below_outer_join |= below_outer_join;
357 463 : ec1->ec_min_security = Min(ec1->ec_min_security,
358 : restrictinfo->security_level);
359 463 : ec1->ec_max_security = Max(ec1->ec_max_security,
360 : restrictinfo->security_level);
361 : /* mark the RI as associated with this eclass */
362 463 : restrictinfo->left_ec = ec1;
363 463 : restrictinfo->right_ec = ec1;
364 : /* mark the RI as usable with this pair of EMs */
365 463 : restrictinfo->left_em = em1;
366 463 : restrictinfo->right_em = em2;
367 : }
368 8865 : else if (ec2)
369 : {
370 : /* Case 3: add item1 to ec2 */
371 86 : em1 = add_eq_member(ec2, item1, item1_relids, item1_nullable_relids,
372 : false, item1_type);
373 86 : ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
374 86 : ec2->ec_below_outer_join |= below_outer_join;
375 86 : ec2->ec_min_security = Min(ec2->ec_min_security,
376 : restrictinfo->security_level);
377 86 : ec2->ec_max_security = Max(ec2->ec_max_security,
378 : restrictinfo->security_level);
379 : /* mark the RI as associated with this eclass */
380 86 : restrictinfo->left_ec = ec2;
381 86 : restrictinfo->right_ec = ec2;
382 : /* mark the RI as usable with this pair of EMs */
383 86 : restrictinfo->left_em = em1;
384 86 : restrictinfo->right_em = em2;
385 : }
386 : else
387 : {
388 : /* Case 4: make a new, two-entry EC */
389 8779 : EquivalenceClass *ec = makeNode(EquivalenceClass);
390 :
391 8779 : ec->ec_opfamilies = opfamilies;
392 8779 : ec->ec_collation = collation;
393 8779 : ec->ec_members = NIL;
394 8779 : ec->ec_sources = list_make1(restrictinfo);
395 8779 : ec->ec_derives = NIL;
396 8779 : ec->ec_relids = NULL;
397 8779 : ec->ec_has_const = false;
398 8779 : ec->ec_has_volatile = false;
399 8779 : ec->ec_below_outer_join = below_outer_join;
400 8779 : ec->ec_broken = false;
401 8779 : ec->ec_sortref = 0;
402 8779 : ec->ec_min_security = restrictinfo->security_level;
403 8779 : ec->ec_max_security = restrictinfo->security_level;
404 8779 : ec->ec_merged = NULL;
405 8779 : em1 = add_eq_member(ec, item1, item1_relids, item1_nullable_relids,
406 : false, item1_type);
407 8779 : em2 = add_eq_member(ec, item2, item2_relids, item2_nullable_relids,
408 : false, item2_type);
409 :
410 8779 : root->eq_classes = lappend(root->eq_classes, ec);
411 :
412 : /* mark the RI as associated with this eclass */
413 8779 : restrictinfo->left_ec = ec;
414 8779 : restrictinfo->right_ec = ec;
415 : /* mark the RI as usable with this pair of EMs */
416 8779 : restrictinfo->left_em = em1;
417 8779 : restrictinfo->right_em = em2;
418 : }
419 :
420 9358 : return true;
421 : }
422 :
423 : /*
424 : * canonicalize_ec_expression
425 : *
426 : * This function ensures that the expression exposes the expected type and
427 : * collation, so that it will be equal() to other equivalence-class expressions
428 : * that it ought to be equal() to.
429 : *
430 : * The rule for datatypes is that the exposed type should match what it would
431 : * be for an input to an operator of the EC's opfamilies; which is usually
432 : * the declared input type of the operator, but in the case of polymorphic
433 : * operators no relabeling is wanted (compare the behavior of parse_coerce.c).
434 : * Expressions coming in from quals will generally have the right type
435 : * already, but expressions coming from indexkeys may not (because they are
436 : * represented without any explicit relabel in pg_index), and the same problem
437 : * occurs for sort expressions (because the parser is likewise cavalier about
438 : * putting relabels on them). Such cases will be binary-compatible with the
439 : * real operators, so adding a RelabelType is sufficient.
440 : *
441 : * Also, the expression's exposed collation must match the EC's collation.
442 : * This is important because in comparisons like "foo < bar COLLATE baz",
443 : * only one of the expressions has the correct exposed collation as we receive
444 : * it from the parser. Forcing both of them to have it ensures that all
445 : * variant spellings of such a construct behave the same. Again, we can
446 : * stick on a RelabelType to force the right exposed collation. (It might
447 : * work to not label the collation at all in EC members, but this is risky
448 : * since some parts of the system expect exprCollation() to deliver the
449 : * right answer for a sort key.)
450 : *
451 : * Note this code assumes that the expression has already been through
452 : * eval_const_expressions, so there are no CollateExprs and no redundant
453 : * RelabelTypes.
454 : */
455 : Expr *
456 72409 : canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
457 : {
458 72409 : Oid expr_type = exprType((Node *) expr);
459 :
460 : /*
461 : * For a polymorphic-input-type opclass, just keep the same exposed type.
462 : */
463 72409 : if (IsPolymorphicType(req_type))
464 76 : req_type = expr_type;
465 :
466 : /*
467 : * No work if the expression exposes the right type/collation already.
468 : */
469 144172 : if (expr_type != req_type ||
470 71763 : exprCollation((Node *) expr) != req_collation)
471 : {
472 : /*
473 : * Strip any existing RelabelType, then add a new one if needed. This
474 : * is to preserve the invariant of no redundant RelabelTypes.
475 : *
476 : * If we have to change the exposed type of the stripped expression,
477 : * set typmod to -1 (since the new type may not have the same typmod
478 : * interpretation). If we only have to change collation, preserve the
479 : * exposed typmod.
480 : */
481 1319 : while (expr && IsA(expr, RelabelType))
482 15 : expr = (Expr *) ((RelabelType *) expr)->arg;
483 :
484 652 : if (exprType((Node *) expr) != req_type)
485 635 : expr = (Expr *) makeRelabelType(expr,
486 : req_type,
487 : -1,
488 : req_collation,
489 : COERCE_IMPLICIT_CAST);
490 17 : else if (exprCollation((Node *) expr) != req_collation)
491 6 : expr = (Expr *) makeRelabelType(expr,
492 : req_type,
493 : exprTypmod((Node *) expr),
494 : req_collation,
495 : COERCE_IMPLICIT_CAST);
496 : }
497 :
498 72409 : return expr;
499 : }
500 :
501 : /*
502 : * add_eq_member - build a new EquivalenceMember and add it to an EC
503 : */
504 : static EquivalenceMember *
505 26265 : add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
506 : Relids nullable_relids, bool is_child, Oid datatype)
507 : {
508 26265 : EquivalenceMember *em = makeNode(EquivalenceMember);
509 :
510 26265 : em->em_expr = expr;
511 26265 : em->em_relids = relids;
512 26265 : em->em_nullable_relids = nullable_relids;
513 26265 : em->em_is_const = false;
514 26265 : em->em_is_child = is_child;
515 26265 : em->em_datatype = datatype;
516 :
517 26265 : if (bms_is_empty(relids))
518 : {
519 : /*
520 : * No Vars, assume it's a pseudoconstant. This is correct for entries
521 : * generated from process_equivalence(), because a WHERE clause can't
522 : * contain aggregates or SRFs, and non-volatility was checked before
523 : * process_equivalence() ever got called. But
524 : * get_eclass_for_sort_expr() has to work harder. We put the tests
525 : * there not here to save cycles in the equivalence case.
526 : */
527 7154 : Assert(!is_child);
528 7154 : em->em_is_const = true;
529 7154 : ec->ec_has_const = true;
530 : /* it can't affect ec_relids */
531 : }
532 19111 : else if (!is_child) /* child members don't add to ec_relids */
533 : {
534 18075 : ec->ec_relids = bms_add_members(ec->ec_relids, relids);
535 : }
536 26265 : ec->ec_members = lappend(ec->ec_members, em);
537 :
538 26265 : return em;
539 : }
540 :
541 :
542 : /*
543 : * get_eclass_for_sort_expr
544 : * Given an expression and opfamily/collation info, find an existing
545 : * equivalence class it is a member of; if none, optionally build a new
546 : * single-member EquivalenceClass for it.
547 : *
548 : * expr is the expression, and nullable_relids is the set of base relids
549 : * that are potentially nullable below it. We actually only care about
550 : * the set of such relids that are used in the expression; but for caller
551 : * convenience, we perform that intersection step here. The caller need
552 : * only be sure that nullable_relids doesn't omit any nullable rels that
553 : * might appear in the expr.
554 : *
555 : * sortref is the SortGroupRef of the originating SortGroupClause, if any,
556 : * or zero if not. (It should never be zero if the expression is volatile!)
557 : *
558 : * If rel is not NULL, it identifies a specific relation we're considering
559 : * a path for, and indicates that child EC members for that relation can be
560 : * considered. Otherwise child members are ignored. (Note: since child EC
561 : * members aren't guaranteed unique, a non-NULL value means that there could
562 : * be more than one EC that matches the expression; if so it's order-dependent
563 : * which one you get. This is annoying but it only happens in corner cases,
564 : * so for now we live with just reporting the first match. See also
565 : * generate_implied_equalities_for_column and match_pathkeys_to_index.)
566 : *
567 : * If create_it is TRUE, we'll build a new EquivalenceClass when there is no
568 : * match. If create_it is FALSE, we just return NULL when no match.
569 : *
570 : * This can be used safely both before and after EquivalenceClass merging;
571 : * since it never causes merging it does not invalidate any existing ECs
572 : * or PathKeys. However, ECs added after path generation has begun are
573 : * of limited usefulness, so usually it's best to create them beforehand.
574 : *
575 : * Note: opfamilies must be chosen consistently with the way
576 : * process_equivalence() would do; that is, generated from a mergejoinable
577 : * equality operator. Else we might fail to detect valid equivalences,
578 : * generating poor (but not incorrect) plans.
579 : */
580 : EquivalenceClass *
581 53083 : get_eclass_for_sort_expr(PlannerInfo *root,
582 : Expr *expr,
583 : Relids nullable_relids,
584 : List *opfamilies,
585 : Oid opcintype,
586 : Oid collation,
587 : Index sortref,
588 : Relids rel,
589 : bool create_it)
590 : {
591 : Relids expr_relids;
592 : EquivalenceClass *newec;
593 : EquivalenceMember *newem;
594 : ListCell *lc1;
595 : MemoryContext oldcontext;
596 :
597 : /*
598 : * Ensure the expression exposes the correct type and collation.
599 : */
600 53083 : expr = canonicalize_ec_expression(expr, opcintype, collation);
601 :
602 : /*
603 : * Get the precise set of nullable relids appearing in the expression.
604 : */
605 53083 : expr_relids = pull_varnos((Node *) expr);
606 53083 : nullable_relids = bms_intersect(nullable_relids, expr_relids);
607 :
608 : /*
609 : * Scan through the existing EquivalenceClasses for a match
610 : */
611 155704 : foreach(lc1, root->eq_classes)
612 : {
613 131303 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
614 : ListCell *lc2;
615 :
616 : /*
617 : * Never match to a volatile EC, except when we are looking at another
618 : * reference to the same volatile SortGroupClause.
619 : */
620 131303 : if (cur_ec->ec_has_volatile &&
621 3 : (sortref == 0 || sortref != cur_ec->ec_sortref))
622 41 : continue;
623 :
624 131262 : if (collation != cur_ec->ec_collation)
625 5104 : continue;
626 126158 : if (!equal(opfamilies, cur_ec->ec_opfamilies))
627 54443 : continue;
628 :
629 151184 : foreach(lc2, cur_ec->ec_members)
630 : {
631 108151 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
632 :
633 : /*
634 : * Ignore child members unless they match the request.
635 : */
636 111775 : if (cur_em->em_is_child &&
637 3624 : !bms_equal(cur_em->em_relids, rel))
638 2676 : continue;
639 :
640 : /*
641 : * If below an outer join, don't match constants: they're not as
642 : * constant as they look.
643 : */
644 114898 : if (cur_ec->ec_below_outer_join &&
645 9423 : cur_em->em_is_const)
646 1839 : continue;
647 :
648 205912 : if (opcintype == cur_em->em_datatype &&
649 102276 : equal(expr, cur_em->em_expr))
650 28682 : return cur_ec; /* Match! */
651 : }
652 : }
653 :
654 : /* No match; does caller want a NULL result? */
655 24401 : if (!create_it)
656 17279 : return NULL;
657 :
658 : /*
659 : * OK, build a new single-member EC
660 : *
661 : * Here, we must be sure that we construct the EC in the right context.
662 : */
663 7122 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
664 :
665 7122 : newec = makeNode(EquivalenceClass);
666 7122 : newec->ec_opfamilies = list_copy(opfamilies);
667 7122 : newec->ec_collation = collation;
668 7122 : newec->ec_members = NIL;
669 7122 : newec->ec_sources = NIL;
670 7122 : newec->ec_derives = NIL;
671 7122 : newec->ec_relids = NULL;
672 7122 : newec->ec_has_const = false;
673 7122 : newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
674 7122 : newec->ec_below_outer_join = false;
675 7122 : newec->ec_broken = false;
676 7122 : newec->ec_sortref = sortref;
677 7122 : newec->ec_min_security = UINT_MAX;
678 7122 : newec->ec_max_security = 0;
679 7122 : newec->ec_merged = NULL;
680 :
681 7122 : if (newec->ec_has_volatile && sortref == 0) /* should not happen */
682 0 : elog(ERROR, "volatile EquivalenceClass has no sortref");
683 :
684 7122 : newem = add_eq_member(newec, copyObject(expr), expr_relids,
685 : nullable_relids, false, opcintype);
686 :
687 : /*
688 : * add_eq_member doesn't check for volatile functions, set-returning
689 : * functions, aggregates, or window functions, but such could appear in
690 : * sort expressions; so we have to check whether its const-marking was
691 : * correct.
692 : */
693 7122 : if (newec->ec_has_const)
694 : {
695 196 : if (newec->ec_has_volatile ||
696 169 : expression_returns_set((Node *) expr) ||
697 144 : contain_agg_clause((Node *) expr) ||
698 70 : contain_window_function((Node *) expr))
699 : {
700 32 : newec->ec_has_const = false;
701 32 : newem->em_is_const = false;
702 : }
703 : }
704 :
705 7122 : root->eq_classes = lappend(root->eq_classes, newec);
706 :
707 7122 : MemoryContextSwitchTo(oldcontext);
708 :
709 7122 : return newec;
710 : }
711 :
712 :
713 : /*
714 : * generate_base_implied_equalities
715 : * Generate any restriction clauses that we can deduce from equivalence
716 : * classes.
717 : *
718 : * When an EC contains pseudoconstants, our strategy is to generate
719 : * "member = const1" clauses where const1 is the first constant member, for
720 : * every other member (including other constants). If we are able to do this
721 : * then we don't need any "var = var" comparisons because we've successfully
722 : * constrained all the vars at their points of creation. If we fail to
723 : * generate any of these clauses due to lack of cross-type operators, we fall
724 : * back to the "ec_broken" strategy described below. (XXX if there are
725 : * multiple constants of different types, it's possible that we might succeed
726 : * in forming all the required clauses if we started from a different const
727 : * member; but this seems a sufficiently hokey corner case to not be worth
728 : * spending lots of cycles on.)
729 : *
730 : * For ECs that contain no pseudoconstants, we generate derived clauses
731 : * "member1 = member2" for each pair of members belonging to the same base
732 : * relation (actually, if there are more than two for the same base relation,
733 : * we only need enough clauses to link each to each other). This provides
734 : * the base case for the recursion: each row emitted by a base relation scan
735 : * will constrain all computable members of the EC to be equal. As each
736 : * join path is formed, we'll add additional derived clauses on-the-fly
737 : * to maintain this invariant (see generate_join_implied_equalities).
738 : *
739 : * If the opfamilies used by the EC do not provide complete sets of cross-type
740 : * equality operators, it is possible that we will fail to generate a clause
741 : * that must be generated to maintain the invariant. (An example: given
742 : * "WHERE a.x = b.y AND b.y = a.z", the scheme breaks down if we cannot
743 : * generate "a.x = a.z" as a restriction clause for A.) In this case we mark
744 : * the EC "ec_broken" and fall back to regurgitating its original source
745 : * RestrictInfos at appropriate times. We do not try to retract any derived
746 : * clauses already generated from the broken EC, so the resulting plan could
747 : * be poor due to bad selectivity estimates caused by redundant clauses. But
748 : * the correct solution to that is to fix the opfamilies ...
749 : *
750 : * Equality clauses derived by this function are passed off to
751 : * process_implied_equality (in plan/initsplan.c) to be inserted into the
752 : * restrictinfo datastructures. Note that this must be called after initial
753 : * scanning of the quals and before Path construction begins.
754 : *
755 : * We make no attempt to avoid generating duplicate RestrictInfos here: we
756 : * don't search ec_sources for matches, nor put the created RestrictInfos
757 : * into ec_derives. Doing so would require some slightly ugly changes in
758 : * initsplan.c's API, and there's no real advantage, because the clauses
759 : * generated here can't duplicate anything we will generate for joins anyway.
760 : */
761 : void
762 13818 : generate_base_implied_equalities(PlannerInfo *root)
763 : {
764 : ListCell *lc;
765 : Index rti;
766 :
767 25626 : foreach(lc, root->eq_classes)
768 : {
769 11808 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
770 :
771 11808 : Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
772 11808 : Assert(!ec->ec_broken); /* not yet anyway... */
773 :
774 : /* Single-member ECs won't generate any deductions */
775 11808 : if (list_length(ec->ec_members) <= 1)
776 2907 : continue;
777 :
778 8901 : if (ec->ec_has_const)
779 7043 : generate_base_implied_equalities_const(root, ec);
780 : else
781 1858 : generate_base_implied_equalities_no_const(root, ec);
782 :
783 : /* Recover if we failed to generate required derived clauses */
784 8901 : if (ec->ec_broken)
785 5 : generate_base_implied_equalities_broken(root, ec);
786 : }
787 :
788 : /*
789 : * This is also a handy place to mark base rels (which should all exist by
790 : * now) with flags showing whether they have pending eclass joins.
791 : */
792 40855 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
793 : {
794 27037 : RelOptInfo *brel = root->simple_rel_array[rti];
795 :
796 27037 : if (brel == NULL)
797 7514 : continue;
798 :
799 19523 : brel->has_eclass_joins = has_relevant_eclass_joinclause(root, brel);
800 : }
801 13818 : }
802 :
803 : /*
804 : * generate_base_implied_equalities when EC contains pseudoconstant(s)
805 : */
806 : static void
807 7043 : generate_base_implied_equalities_const(PlannerInfo *root,
808 : EquivalenceClass *ec)
809 : {
810 7043 : EquivalenceMember *const_em = NULL;
811 : ListCell *lc;
812 :
813 : /*
814 : * In the trivial case where we just had one "var = const" clause, push
815 : * the original clause back into the main planner machinery. There is
816 : * nothing to be gained by doing it differently, and we save the effort to
817 : * re-build and re-analyze an equality clause that will be exactly
818 : * equivalent to the old one.
819 : */
820 13666 : if (list_length(ec->ec_members) == 2 &&
821 6623 : list_length(ec->ec_sources) == 1)
822 : {
823 6623 : RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
824 :
825 6623 : if (bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
826 : {
827 6615 : distribute_restrictinfo_to_rels(root, restrictinfo);
828 13658 : return;
829 : }
830 : }
831 :
832 : /*
833 : * Find the constant member to use. We prefer an actual constant to
834 : * pseudo-constants (such as Params), because the constraint exclusion
835 : * machinery might be able to exclude relations on the basis of generated
836 : * "var = const" equalities, but "var = param" won't work for that.
837 : */
838 1149 : foreach(lc, ec->ec_members)
839 : {
840 1148 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
841 :
842 1148 : if (cur_em->em_is_const)
843 : {
844 428 : const_em = cur_em;
845 428 : if (IsA(cur_em->em_expr, Const))
846 427 : break;
847 : }
848 : }
849 428 : Assert(const_em != NULL);
850 :
851 : /* Generate a derived equality against each other member */
852 1698 : foreach(lc, ec->ec_members)
853 : {
854 1275 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
855 : Oid eq_op;
856 :
857 1275 : Assert(!cur_em->em_is_child); /* no children yet */
858 1275 : if (cur_em == const_em)
859 424 : continue;
860 851 : eq_op = select_equality_operator(ec,
861 : cur_em->em_datatype,
862 : const_em->em_datatype);
863 851 : if (!OidIsValid(eq_op))
864 : {
865 : /* failed... */
866 5 : ec->ec_broken = true;
867 5 : break;
868 : }
869 3384 : process_implied_equality(root, eq_op, ec->ec_collation,
870 : cur_em->em_expr, const_em->em_expr,
871 846 : bms_copy(ec->ec_relids),
872 846 : bms_union(cur_em->em_nullable_relids,
873 846 : const_em->em_nullable_relids),
874 : ec->ec_min_security,
875 846 : ec->ec_below_outer_join,
876 846 : cur_em->em_is_const);
877 : }
878 : }
879 :
880 : /*
881 : * generate_base_implied_equalities when EC contains no pseudoconstants
882 : */
883 : static void
884 1858 : generate_base_implied_equalities_no_const(PlannerInfo *root,
885 : EquivalenceClass *ec)
886 : {
887 : EquivalenceMember **prev_ems;
888 : ListCell *lc;
889 :
890 : /*
891 : * We scan the EC members once and track the last-seen member for each
892 : * base relation. When we see another member of the same base relation,
893 : * we generate "prev_mem = cur_mem". This results in the minimum number
894 : * of derived clauses, but it's possible that it will fail when a
895 : * different ordering would succeed. XXX FIXME: use a UNION-FIND
896 : * algorithm similar to the way we build merged ECs. (Use a list-of-lists
897 : * for each rel.)
898 : */
899 1858 : prev_ems = (EquivalenceMember **)
900 1858 : palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *));
901 :
902 5605 : foreach(lc, ec->ec_members)
903 : {
904 3747 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
905 : int relid;
906 :
907 3747 : Assert(!cur_em->em_is_child); /* no children yet */
908 3747 : if (!bms_get_singleton_member(cur_em->em_relids, &relid))
909 10 : continue;
910 3737 : Assert(relid < root->simple_rel_array_size);
911 :
912 3737 : if (prev_ems[relid] != NULL)
913 : {
914 11 : EquivalenceMember *prev_em = prev_ems[relid];
915 : Oid eq_op;
916 :
917 11 : eq_op = select_equality_operator(ec,
918 : prev_em->em_datatype,
919 : cur_em->em_datatype);
920 11 : if (!OidIsValid(eq_op))
921 : {
922 : /* failed... */
923 0 : ec->ec_broken = true;
924 0 : break;
925 : }
926 33 : process_implied_equality(root, eq_op, ec->ec_collation,
927 : prev_em->em_expr, cur_em->em_expr,
928 11 : bms_copy(ec->ec_relids),
929 11 : bms_union(prev_em->em_nullable_relids,
930 11 : cur_em->em_nullable_relids),
931 : ec->ec_min_security,
932 11 : ec->ec_below_outer_join,
933 : false);
934 : }
935 3737 : prev_ems[relid] = cur_em;
936 : }
937 :
938 1858 : pfree(prev_ems);
939 :
940 : /*
941 : * We also have to make sure that all the Vars used in the member clauses
942 : * will be available at any join node we might try to reference them at.
943 : * For the moment we force all the Vars to be available at all join nodes
944 : * for this eclass. Perhaps this could be improved by doing some
945 : * pre-analysis of which members we prefer to join, but it's no worse than
946 : * what happened in the pre-8.3 code.
947 : */
948 5605 : foreach(lc, ec->ec_members)
949 : {
950 3747 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
951 3747 : List *vars = pull_var_clause((Node *) cur_em->em_expr,
952 : PVC_RECURSE_AGGREGATES |
953 : PVC_RECURSE_WINDOWFUNCS |
954 : PVC_INCLUDE_PLACEHOLDERS);
955 :
956 3747 : add_vars_to_targetlist(root, vars, ec->ec_relids, false);
957 3747 : list_free(vars);
958 : }
959 1858 : }
960 :
961 : /*
962 : * generate_base_implied_equalities cleanup after failure
963 : *
964 : * What we must do here is push any zero- or one-relation source RestrictInfos
965 : * of the EC back into the main restrictinfo datastructures. Multi-relation
966 : * clauses will be regurgitated later by generate_join_implied_equalities().
967 : * (We do it this way to maintain continuity with the case that ec_broken
968 : * becomes set only after we've gone up a join level or two.) However, for
969 : * an EC that contains constants, we can adopt a simpler strategy and just
970 : * throw back all the source RestrictInfos immediately; that works because
971 : * we know that such an EC can't become broken later. (This rule justifies
972 : * ignoring ec_has_const ECs in generate_join_implied_equalities, even when
973 : * they are broken.)
974 : */
975 : static void
976 5 : generate_base_implied_equalities_broken(PlannerInfo *root,
977 : EquivalenceClass *ec)
978 : {
979 : ListCell *lc;
980 :
981 16 : foreach(lc, ec->ec_sources)
982 : {
983 11 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
984 :
985 11 : if (ec->ec_has_const ||
986 0 : bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
987 11 : distribute_restrictinfo_to_rels(root, restrictinfo);
988 : }
989 5 : }
990 :
991 :
992 : /*
993 : * generate_join_implied_equalities
994 : * Generate any join clauses that we can deduce from equivalence classes.
995 : *
996 : * At a join node, we must enforce restriction clauses sufficient to ensure
997 : * that all equivalence-class members computable at that node are equal.
998 : * Since the set of clauses to enforce can vary depending on which subset
999 : * relations are the inputs, we have to compute this afresh for each join
1000 : * relation pair. Hence a fresh List of RestrictInfo nodes is built and
1001 : * passed back on each call.
1002 : *
1003 : * In addition to its use at join nodes, this can be applied to generate
1004 : * eclass-based join clauses for use in a parameterized scan of a base rel.
1005 : * The reason for the asymmetry of specifying the inner rel as a RelOptInfo
1006 : * and the outer rel by Relids is that this usage occurs before we have
1007 : * built any join RelOptInfos.
1008 : *
1009 : * An annoying special case for parameterized scans is that the inner rel can
1010 : * be an appendrel child (an "other rel"). In this case we must generate
1011 : * appropriate clauses using child EC members. add_child_rel_equivalences
1012 : * must already have been done for the child rel.
1013 : *
1014 : * The results are sufficient for use in merge, hash, and plain nestloop join
1015 : * methods. We do not worry here about selecting clauses that are optimal
1016 : * for use in a parameterized indexscan. indxpath.c makes its own selections
1017 : * of clauses to use, and if the ones we pick here are redundant with those,
1018 : * the extras will be eliminated at createplan time, using the parent_ec
1019 : * markers that we provide (see is_redundant_derived_clause()).
1020 : *
1021 : * Because the same join clauses are likely to be needed multiple times as
1022 : * we consider different join paths, we avoid generating multiple copies:
1023 : * whenever we select a particular pair of EquivalenceMembers to join,
1024 : * we check to see if the pair matches any original clause (in ec_sources)
1025 : * or previously-built clause (in ec_derives). This saves memory and allows
1026 : * re-use of information cached in RestrictInfos.
1027 : *
1028 : * join_relids should always equal bms_union(outer_relids, inner_rel->relids).
1029 : * We could simplify this function's API by computing it internally, but in
1030 : * most current uses, the caller has the value at hand anyway.
1031 : */
1032 : List *
1033 11760 : generate_join_implied_equalities(PlannerInfo *root,
1034 : Relids join_relids,
1035 : Relids outer_relids,
1036 : RelOptInfo *inner_rel)
1037 : {
1038 11760 : return generate_join_implied_equalities_for_ecs(root,
1039 : root->eq_classes,
1040 : join_relids,
1041 : outer_relids,
1042 : inner_rel);
1043 : }
1044 :
1045 : /*
1046 : * generate_join_implied_equalities_for_ecs
1047 : * As above, but consider only the listed ECs.
1048 : */
1049 : List *
1050 11820 : generate_join_implied_equalities_for_ecs(PlannerInfo *root,
1051 : List *eclasses,
1052 : Relids join_relids,
1053 : Relids outer_relids,
1054 : RelOptInfo *inner_rel)
1055 : {
1056 11820 : List *result = NIL;
1057 11820 : Relids inner_relids = inner_rel->relids;
1058 : Relids nominal_inner_relids;
1059 : Relids nominal_join_relids;
1060 : ListCell *lc;
1061 :
1062 : /* If inner rel is a child, extra setup work is needed */
1063 11820 : if (IS_OTHER_REL(inner_rel))
1064 : {
1065 104 : Assert(!bms_is_empty(inner_rel->top_parent_relids));
1066 :
1067 : /* Fetch relid set for the topmost parent rel */
1068 104 : nominal_inner_relids = inner_rel->top_parent_relids;
1069 : /* ECs will be marked with the parent's relid, not the child's */
1070 104 : nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1071 : }
1072 : else
1073 : {
1074 11716 : nominal_inner_relids = inner_relids;
1075 11716 : nominal_join_relids = join_relids;
1076 : }
1077 :
1078 83477 : foreach(lc, eclasses)
1079 : {
1080 71657 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
1081 71657 : List *sublist = NIL;
1082 :
1083 : /* ECs containing consts do not need any further enforcement */
1084 71657 : if (ec->ec_has_const)
1085 15329 : continue;
1086 :
1087 : /* Single-member ECs won't generate any deductions */
1088 56328 : if (list_length(ec->ec_members) <= 1)
1089 32784 : continue;
1090 :
1091 : /* We can quickly ignore any that don't overlap the join, too */
1092 23544 : if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1093 6489 : continue;
1094 :
1095 17055 : if (!ec->ec_broken)
1096 17012 : sublist = generate_join_implied_equalities_normal(root,
1097 : ec,
1098 : join_relids,
1099 : outer_relids,
1100 : inner_relids);
1101 :
1102 : /* Recover if we failed to generate required derived clauses */
1103 17055 : if (ec->ec_broken)
1104 48 : sublist = generate_join_implied_equalities_broken(root,
1105 : ec,
1106 : nominal_join_relids,
1107 : outer_relids,
1108 : nominal_inner_relids,
1109 : inner_rel);
1110 :
1111 17055 : result = list_concat(result, sublist);
1112 : }
1113 :
1114 11820 : return result;
1115 : }
1116 :
1117 : /*
1118 : * generate_join_implied_equalities for a still-valid EC
1119 : */
1120 : static List *
1121 17012 : generate_join_implied_equalities_normal(PlannerInfo *root,
1122 : EquivalenceClass *ec,
1123 : Relids join_relids,
1124 : Relids outer_relids,
1125 : Relids inner_relids)
1126 : {
1127 17012 : List *result = NIL;
1128 17012 : List *new_members = NIL;
1129 17012 : List *outer_members = NIL;
1130 17012 : List *inner_members = NIL;
1131 : ListCell *lc1;
1132 :
1133 : /*
1134 : * First, scan the EC to identify member values that are computable at the
1135 : * outer rel, at the inner rel, or at this relation but not in either
1136 : * input rel. The outer-rel members should already be enforced equal,
1137 : * likewise for the inner-rel members. We'll need to create clauses to
1138 : * enforce that any newly computable members are all equal to each other
1139 : * as well as to at least one input member, plus enforce at least one
1140 : * outer-rel member equal to at least one inner-rel member.
1141 : */
1142 52561 : foreach(lc1, ec->ec_members)
1143 : {
1144 35549 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
1145 :
1146 : /*
1147 : * We don't need to check explicitly for child EC members. This test
1148 : * against join_relids will cause them to be ignored except when
1149 : * considering a child inner rel, which is what we want.
1150 : */
1151 35549 : if (!bms_is_subset(cur_em->em_relids, join_relids))
1152 5834 : continue; /* not computable yet, or wrong child */
1153 :
1154 29715 : if (bms_is_subset(cur_em->em_relids, outer_relids))
1155 17834 : outer_members = lappend(outer_members, cur_em);
1156 11881 : else if (bms_is_subset(cur_em->em_relids, inner_relids))
1157 11723 : inner_members = lappend(inner_members, cur_em);
1158 : else
1159 158 : new_members = lappend(new_members, cur_em);
1160 : }
1161 :
1162 : /*
1163 : * First, select the joinclause if needed. We can equate any one outer
1164 : * member to any one inner member, but we have to find a datatype
1165 : * combination for which an opfamily member operator exists. If we have
1166 : * choices, we prefer simple Var members (possibly with RelabelType) since
1167 : * these are (a) cheapest to compute at runtime and (b) most likely to
1168 : * have useful statistics. Also, prefer operators that are also
1169 : * hashjoinable.
1170 : */
1171 17012 : if (outer_members && inner_members)
1172 : {
1173 7008 : EquivalenceMember *best_outer_em = NULL;
1174 7008 : EquivalenceMember *best_inner_em = NULL;
1175 7008 : Oid best_eq_op = InvalidOid;
1176 7008 : int best_score = -1;
1177 : RestrictInfo *rinfo;
1178 :
1179 7449 : foreach(lc1, outer_members)
1180 : {
1181 7014 : EquivalenceMember *outer_em = (EquivalenceMember *) lfirst(lc1);
1182 : ListCell *lc2;
1183 :
1184 7457 : foreach(lc2, inner_members)
1185 : {
1186 7016 : EquivalenceMember *inner_em = (EquivalenceMember *) lfirst(lc2);
1187 : Oid eq_op;
1188 : int score;
1189 :
1190 7016 : eq_op = select_equality_operator(ec,
1191 : outer_em->em_datatype,
1192 : inner_em->em_datatype);
1193 7016 : if (!OidIsValid(eq_op))
1194 5 : continue;
1195 7011 : score = 0;
1196 7447 : if (IsA(outer_em->em_expr, Var) ||
1197 674 : (IsA(outer_em->em_expr, RelabelType) &&
1198 238 : IsA(((RelabelType *) outer_em->em_expr)->arg, Var)))
1199 6751 : score++;
1200 7280 : if (IsA(inner_em->em_expr, Var) ||
1201 373 : (IsA(inner_em->em_expr, RelabelType) &&
1202 104 : IsA(((RelabelType *) inner_em->em_expr)->arg, Var)))
1203 6789 : score++;
1204 7011 : if (op_hashjoinable(eq_op,
1205 7011 : exprType((Node *) outer_em->em_expr)))
1206 6999 : score++;
1207 7011 : if (score > best_score)
1208 : {
1209 7003 : best_outer_em = outer_em;
1210 7003 : best_inner_em = inner_em;
1211 7003 : best_eq_op = eq_op;
1212 7003 : best_score = score;
1213 7003 : if (best_score == 3)
1214 6573 : break; /* no need to look further */
1215 : }
1216 : }
1217 7014 : if (best_score == 3)
1218 6573 : break; /* no need to look further */
1219 : }
1220 7008 : if (best_score < 0)
1221 : {
1222 : /* failed... */
1223 5 : ec->ec_broken = true;
1224 5 : return NIL;
1225 : }
1226 :
1227 : /*
1228 : * Create clause, setting parent_ec to mark it as redundant with other
1229 : * joinclauses
1230 : */
1231 7003 : rinfo = create_join_clause(root, ec, best_eq_op,
1232 : best_outer_em, best_inner_em,
1233 : ec);
1234 :
1235 7003 : result = lappend(result, rinfo);
1236 : }
1237 :
1238 : /*
1239 : * Now deal with building restrictions for any expressions that involve
1240 : * Vars from both sides of the join. We have to equate all of these to
1241 : * each other as well as to at least one old member (if any).
1242 : *
1243 : * XXX as in generate_base_implied_equalities_no_const, we could be a lot
1244 : * smarter here to avoid unnecessary failures in cross-type situations.
1245 : * For now, use the same left-to-right method used there.
1246 : */
1247 17007 : if (new_members)
1248 : {
1249 158 : List *old_members = list_concat(outer_members, inner_members);
1250 158 : EquivalenceMember *prev_em = NULL;
1251 : RestrictInfo *rinfo;
1252 :
1253 : /* For now, arbitrarily take the first old_member as the one to use */
1254 158 : if (old_members)
1255 133 : new_members = lappend(new_members, linitial(old_members));
1256 :
1257 449 : foreach(lc1, new_members)
1258 : {
1259 291 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
1260 :
1261 291 : if (prev_em != NULL)
1262 : {
1263 : Oid eq_op;
1264 :
1265 133 : eq_op = select_equality_operator(ec,
1266 : prev_em->em_datatype,
1267 : cur_em->em_datatype);
1268 133 : if (!OidIsValid(eq_op))
1269 : {
1270 : /* failed... */
1271 0 : ec->ec_broken = true;
1272 0 : return NIL;
1273 : }
1274 : /* do NOT set parent_ec, this qual is not redundant! */
1275 133 : rinfo = create_join_clause(root, ec, eq_op,
1276 : prev_em, cur_em,
1277 : NULL);
1278 :
1279 133 : result = lappend(result, rinfo);
1280 : }
1281 291 : prev_em = cur_em;
1282 : }
1283 : }
1284 :
1285 17007 : return result;
1286 : }
1287 :
1288 : /*
1289 : * generate_join_implied_equalities cleanup after failure
1290 : *
1291 : * Return any original RestrictInfos that are enforceable at this join.
1292 : *
1293 : * In the case of a child inner relation, we have to translate the
1294 : * original RestrictInfos from parent to child Vars.
1295 : */
1296 : static List *
1297 48 : generate_join_implied_equalities_broken(PlannerInfo *root,
1298 : EquivalenceClass *ec,
1299 : Relids nominal_join_relids,
1300 : Relids outer_relids,
1301 : Relids nominal_inner_relids,
1302 : RelOptInfo *inner_rel)
1303 : {
1304 48 : List *result = NIL;
1305 : ListCell *lc;
1306 :
1307 132 : foreach(lc, ec->ec_sources)
1308 : {
1309 84 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1310 84 : Relids clause_relids = restrictinfo->required_relids;
1311 :
1312 130 : if (bms_is_subset(clause_relids, nominal_join_relids) &&
1313 88 : !bms_is_subset(clause_relids, outer_relids) &&
1314 42 : !bms_is_subset(clause_relids, nominal_inner_relids))
1315 42 : result = lappend(result, restrictinfo);
1316 : }
1317 :
1318 : /*
1319 : * If we have to translate, just brute-force apply adjust_appendrel_attrs
1320 : * to all the RestrictInfos at once. This will result in returning
1321 : * RestrictInfos that are not listed in ec_derives, but there shouldn't be
1322 : * any duplication, and it's a sufficiently narrow corner case that we
1323 : * shouldn't sweat too much over it anyway.
1324 : *
1325 : * Since inner_rel might be an indirect descendant of the baserel
1326 : * mentioned in the ec_sources clauses, we have to be prepared to apply
1327 : * multiple levels of Var translation.
1328 : */
1329 48 : if (IS_OTHER_REL(inner_rel) && result != NIL)
1330 27 : result = (List *) adjust_appendrel_attrs_multilevel(root,
1331 : (Node *) result,
1332 : inner_rel->relids,
1333 : inner_rel->top_parent_relids);
1334 :
1335 48 : return result;
1336 : }
1337 :
1338 :
1339 : /*
1340 : * select_equality_operator
1341 : * Select a suitable equality operator for comparing two EC members
1342 : *
1343 : * Returns InvalidOid if no operator can be found for this datatype combination
1344 : */
1345 : static Oid
1346 10754 : select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
1347 : {
1348 : ListCell *lc;
1349 :
1350 10764 : foreach(lc, ec->ec_opfamilies)
1351 : {
1352 10754 : Oid opfamily = lfirst_oid(lc);
1353 : Oid opno;
1354 :
1355 10754 : opno = get_opfamily_member(opfamily, lefttype, righttype,
1356 : BTEqualStrategyNumber);
1357 10754 : if (!OidIsValid(opno))
1358 10 : continue;
1359 : /* If no barrier quals in query, don't worry about leaky operators */
1360 10744 : if (ec->ec_max_security == 0)
1361 10660 : return opno;
1362 : /* Otherwise, insist that selected operators be leakproof */
1363 84 : if (get_func_leakproof(get_opcode(opno)))
1364 84 : return opno;
1365 : }
1366 10 : return InvalidOid;
1367 : }
1368 :
1369 :
1370 : /*
1371 : * create_join_clause
1372 : * Find or make a RestrictInfo comparing the two given EC members
1373 : * with the given operator.
1374 : *
1375 : * parent_ec is either equal to ec (if the clause is a potentially-redundant
1376 : * join clause) or NULL (if not). We have to treat this as part of the
1377 : * match requirements --- it's possible that a clause comparing the same two
1378 : * EMs is a join clause in one join path and a restriction clause in another.
1379 : */
1380 : static RestrictInfo *
1381 9826 : create_join_clause(PlannerInfo *root,
1382 : EquivalenceClass *ec, Oid opno,
1383 : EquivalenceMember *leftem,
1384 : EquivalenceMember *rightem,
1385 : EquivalenceClass *parent_ec)
1386 : {
1387 : RestrictInfo *rinfo;
1388 : ListCell *lc;
1389 : MemoryContext oldcontext;
1390 :
1391 : /*
1392 : * Search to see if we already built a RestrictInfo for this pair of
1393 : * EquivalenceMembers. We can use either original source clauses or
1394 : * previously-derived clauses. The check on opno is probably redundant,
1395 : * but be safe ...
1396 : */
1397 20245 : foreach(lc, ec->ec_sources)
1398 : {
1399 10431 : rinfo = (RestrictInfo *) lfirst(lc);
1400 16004 : if (rinfo->left_em == leftem &&
1401 10944 : rinfo->right_em == rightem &&
1402 5383 : rinfo->parent_ec == parent_ec &&
1403 12 : opno == ((OpExpr *) rinfo->clause)->opno)
1404 12 : return rinfo;
1405 : }
1406 :
1407 16126 : foreach(lc, ec->ec_derives)
1408 : {
1409 12445 : rinfo = (RestrictInfo *) lfirst(lc);
1410 19158 : if (rinfo->left_em == leftem &&
1411 12944 : rinfo->right_em == rightem &&
1412 12364 : rinfo->parent_ec == parent_ec &&
1413 6133 : opno == ((OpExpr *) rinfo->clause)->opno)
1414 6133 : return rinfo;
1415 : }
1416 :
1417 : /*
1418 : * Not there, so build it, in planner context so we can re-use it. (Not
1419 : * important in normal planning, but definitely so in GEQO.)
1420 : */
1421 3681 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
1422 :
1423 11043 : rinfo = build_implied_join_equality(opno,
1424 : ec->ec_collation,
1425 : leftem->em_expr,
1426 : rightem->em_expr,
1427 3681 : bms_union(leftem->em_relids,
1428 3681 : rightem->em_relids),
1429 3681 : bms_union(leftem->em_nullable_relids,
1430 3681 : rightem->em_nullable_relids),
1431 : ec->ec_min_security);
1432 :
1433 : /* Mark the clause as redundant, or not */
1434 3681 : rinfo->parent_ec = parent_ec;
1435 :
1436 : /*
1437 : * We know the correct values for left_ec/right_ec, ie this particular EC,
1438 : * so we can just set them directly instead of forcing another lookup.
1439 : */
1440 3681 : rinfo->left_ec = ec;
1441 3681 : rinfo->right_ec = ec;
1442 :
1443 : /* Mark it as usable with these EMs */
1444 3681 : rinfo->left_em = leftem;
1445 3681 : rinfo->right_em = rightem;
1446 : /* and save it for possible re-use */
1447 3681 : ec->ec_derives = lappend(ec->ec_derives, rinfo);
1448 :
1449 3681 : MemoryContextSwitchTo(oldcontext);
1450 :
1451 3681 : return rinfo;
1452 : }
1453 :
1454 :
1455 : /*
1456 : * reconsider_outer_join_clauses
1457 : * Re-examine any outer-join clauses that were set aside by
1458 : * distribute_qual_to_rels(), and see if we can derive any
1459 : * EquivalenceClasses from them. Then, if they were not made
1460 : * redundant, push them out into the regular join-clause lists.
1461 : *
1462 : * When we have mergejoinable clauses A = B that are outer-join clauses,
1463 : * we can't blindly combine them with other clauses A = C to deduce B = C,
1464 : * since in fact the "equality" A = B won't necessarily hold above the
1465 : * outer join (one of the variables might be NULL instead). Nonetheless
1466 : * there are cases where we can add qual clauses using transitivity.
1467 : *
1468 : * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
1469 : * for which there is also an equivalence clause OUTERVAR = CONSTANT.
1470 : * It is safe and useful to push a clause INNERVAR = CONSTANT into the
1471 : * evaluation of the inner (nullable) relation, because any inner rows not
1472 : * meeting this condition will not contribute to the outer-join result anyway.
1473 : * (Any outer rows they could join to will be eliminated by the pushed-down
1474 : * equivalence clause.)
1475 : *
1476 : * Note that the above rule does not work for full outer joins; nor is it
1477 : * very interesting to consider cases where the generated equivalence clause
1478 : * would involve relations outside the outer join, since such clauses couldn't
1479 : * be pushed into the inner side's scan anyway. So the restriction to
1480 : * outervar = pseudoconstant is not really giving up anything.
1481 : *
1482 : * For full-join cases, we can only do something useful if it's a FULL JOIN
1483 : * USING and a merged column has an equivalence MERGEDVAR = CONSTANT.
1484 : * By the time it gets here, the merged column will look like
1485 : * COALESCE(LEFTVAR, RIGHTVAR)
1486 : * and we will have a full-join clause LEFTVAR = RIGHTVAR that we can match
1487 : * the COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT
1488 : * and RIGHTVAR = CONSTANT into the input relations, since any rows not
1489 : * meeting these conditions cannot contribute to the join result.
1490 : *
1491 : * Again, there isn't any traction to be gained by trying to deal with
1492 : * clauses comparing a mergedvar to a non-pseudoconstant. So we can make
1493 : * use of the EquivalenceClasses to search for matching variables that were
1494 : * equivalenced to constants. The interesting outer-join clauses were
1495 : * accumulated for us by distribute_qual_to_rels.
1496 : *
1497 : * When we find one of these cases, we implement the changes we want by
1498 : * generating a new equivalence clause INNERVAR = CONSTANT (or LEFTVAR, etc)
1499 : * and pushing it into the EquivalenceClass structures. This is because we
1500 : * may already know that INNERVAR is equivalenced to some other var(s), and
1501 : * we'd like the constant to propagate to them too. Note that it would be
1502 : * unsafe to merge any existing EC for INNERVAR with the OUTERVAR's EC ---
1503 : * that could result in propagating constant restrictions from
1504 : * INNERVAR to OUTERVAR, which would be very wrong.
1505 : *
1506 : * It's possible that the INNERVAR is also an OUTERVAR for some other
1507 : * outer-join clause, in which case the process can be repeated. So we repeat
1508 : * looping over the lists of clauses until no further deductions can be made.
1509 : * Whenever we do make a deduction, we remove the generating clause from the
1510 : * lists, since we don't want to make the same deduction twice.
1511 : *
1512 : * If we don't find any match for a set-aside outer join clause, we must
1513 : * throw it back into the regular joinclause processing by passing it to
1514 : * distribute_restrictinfo_to_rels(). If we do generate a derived clause,
1515 : * however, the outer-join clause is redundant. We still throw it back,
1516 : * because otherwise the join will be seen as a clauseless join and avoided
1517 : * during join order searching; but we mark it as redundant to keep from
1518 : * messing up the joinrel's size estimate. (This behavior means that the
1519 : * API for this routine is uselessly complex: we could have just put all
1520 : * the clauses into the regular processing initially. We keep it because
1521 : * someday we might want to do something else, such as inserting "dummy"
1522 : * joinclauses instead of real ones.)
1523 : *
1524 : * Outer join clauses that are marked outerjoin_delayed are special: this
1525 : * condition means that one or both VARs might go to null due to a lower
1526 : * outer join. We can still push a constant through the clause, but only
1527 : * if its operator is strict; and we *have to* throw the clause back into
1528 : * regular joinclause processing. By keeping the strict join clause,
1529 : * we ensure that any null-extended rows that are mistakenly generated due
1530 : * to suppressing rows not matching the constant will be rejected at the
1531 : * upper outer join. (This doesn't work for full-join clauses.)
1532 : */
1533 : void
1534 13864 : reconsider_outer_join_clauses(PlannerInfo *root)
1535 : {
1536 : bool found;
1537 : ListCell *cell;
1538 : ListCell *prev;
1539 : ListCell *next;
1540 :
1541 : /* Outer loop repeats until we find no more deductions */
1542 : do
1543 : {
1544 13864 : found = false;
1545 :
1546 : /* Process the LEFT JOIN clauses */
1547 13864 : prev = NULL;
1548 14648 : for (cell = list_head(root->left_join_clauses); cell; cell = next)
1549 : {
1550 784 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1551 :
1552 784 : next = lnext(cell);
1553 784 : if (reconsider_outer_join_clause(root, rinfo, true))
1554 : {
1555 18 : found = true;
1556 : /* remove it from the list */
1557 18 : root->left_join_clauses =
1558 18 : list_delete_cell(root->left_join_clauses, cell, prev);
1559 : /* we throw it back anyway (see notes above) */
1560 : /* but the thrown-back clause has no extra selectivity */
1561 18 : rinfo->norm_selec = 2.0;
1562 18 : rinfo->outer_selec = 1.0;
1563 18 : distribute_restrictinfo_to_rels(root, rinfo);
1564 : }
1565 : else
1566 766 : prev = cell;
1567 : }
1568 :
1569 : /* Process the RIGHT JOIN clauses */
1570 13864 : prev = NULL;
1571 14610 : for (cell = list_head(root->right_join_clauses); cell; cell = next)
1572 : {
1573 746 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1574 :
1575 746 : next = lnext(cell);
1576 746 : if (reconsider_outer_join_clause(root, rinfo, false))
1577 : {
1578 29 : found = true;
1579 : /* remove it from the list */
1580 29 : root->right_join_clauses =
1581 29 : list_delete_cell(root->right_join_clauses, cell, prev);
1582 : /* we throw it back anyway (see notes above) */
1583 : /* but the thrown-back clause has no extra selectivity */
1584 29 : rinfo->norm_selec = 2.0;
1585 29 : rinfo->outer_selec = 1.0;
1586 29 : distribute_restrictinfo_to_rels(root, rinfo);
1587 : }
1588 : else
1589 717 : prev = cell;
1590 : }
1591 :
1592 : /* Process the FULL JOIN clauses */
1593 13864 : prev = NULL;
1594 13897 : for (cell = list_head(root->full_join_clauses); cell; cell = next)
1595 : {
1596 33 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1597 :
1598 33 : next = lnext(cell);
1599 33 : if (reconsider_full_join_clause(root, rinfo))
1600 : {
1601 1 : found = true;
1602 : /* remove it from the list */
1603 1 : root->full_join_clauses =
1604 1 : list_delete_cell(root->full_join_clauses, cell, prev);
1605 : /* we throw it back anyway (see notes above) */
1606 : /* but the thrown-back clause has no extra selectivity */
1607 1 : rinfo->norm_selec = 2.0;
1608 1 : rinfo->outer_selec = 1.0;
1609 1 : distribute_restrictinfo_to_rels(root, rinfo);
1610 : }
1611 : else
1612 32 : prev = cell;
1613 : }
1614 13864 : } while (found);
1615 :
1616 : /* Now, any remaining clauses have to be thrown back */
1617 14584 : foreach(cell, root->left_join_clauses)
1618 : {
1619 766 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1620 :
1621 766 : distribute_restrictinfo_to_rels(root, rinfo);
1622 : }
1623 14506 : foreach(cell, root->right_join_clauses)
1624 : {
1625 688 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1626 :
1627 688 : distribute_restrictinfo_to_rels(root, rinfo);
1628 : }
1629 13850 : foreach(cell, root->full_join_clauses)
1630 : {
1631 32 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1632 :
1633 32 : distribute_restrictinfo_to_rels(root, rinfo);
1634 : }
1635 13818 : }
1636 :
1637 : /*
1638 : * reconsider_outer_join_clauses for a single LEFT/RIGHT JOIN clause
1639 : *
1640 : * Returns TRUE if we were able to propagate a constant through the clause.
1641 : */
1642 : static bool
1643 1530 : reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
1644 : bool outer_on_left)
1645 : {
1646 : Expr *outervar,
1647 : *innervar;
1648 : Oid opno,
1649 : collation,
1650 : left_type,
1651 : right_type,
1652 : inner_datatype;
1653 : Relids inner_relids,
1654 : inner_nullable_relids;
1655 : ListCell *lc1;
1656 :
1657 1530 : Assert(is_opclause(rinfo->clause));
1658 1530 : opno = ((OpExpr *) rinfo->clause)->opno;
1659 1530 : collation = ((OpExpr *) rinfo->clause)->inputcollid;
1660 :
1661 : /* If clause is outerjoin_delayed, operator must be strict */
1662 1530 : if (rinfo->outerjoin_delayed && !op_strict(opno))
1663 0 : return false;
1664 :
1665 : /* Extract needed info from the clause */
1666 1530 : op_input_types(opno, &left_type, &right_type);
1667 1530 : if (outer_on_left)
1668 : {
1669 784 : outervar = (Expr *) get_leftop(rinfo->clause);
1670 784 : innervar = (Expr *) get_rightop(rinfo->clause);
1671 784 : inner_datatype = right_type;
1672 784 : inner_relids = rinfo->right_relids;
1673 : }
1674 : else
1675 : {
1676 746 : outervar = (Expr *) get_rightop(rinfo->clause);
1677 746 : innervar = (Expr *) get_leftop(rinfo->clause);
1678 746 : inner_datatype = left_type;
1679 746 : inner_relids = rinfo->left_relids;
1680 : }
1681 1530 : inner_nullable_relids = bms_intersect(inner_relids,
1682 1530 : rinfo->nullable_relids);
1683 :
1684 : /* Scan EquivalenceClasses for a match to outervar */
1685 8418 : foreach(lc1, root->eq_classes)
1686 : {
1687 6935 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1688 : bool match;
1689 : ListCell *lc2;
1690 :
1691 : /* Ignore EC unless it contains pseudoconstants */
1692 6935 : if (!cur_ec->ec_has_const)
1693 5562 : continue;
1694 : /* Never match to a volatile EC */
1695 1373 : if (cur_ec->ec_has_volatile)
1696 0 : continue;
1697 : /* It has to match the outer-join clause as to semantics, too */
1698 1373 : if (collation != cur_ec->ec_collation)
1699 82 : continue;
1700 1291 : if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
1701 450 : continue;
1702 : /* Does it contain a match to outervar? */
1703 841 : match = false;
1704 2533 : foreach(lc2, cur_ec->ec_members)
1705 : {
1706 1739 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1707 :
1708 1739 : Assert(!cur_em->em_is_child); /* no children yet */
1709 1739 : if (equal(outervar, cur_em->em_expr))
1710 : {
1711 47 : match = true;
1712 47 : break;
1713 : }
1714 : }
1715 841 : if (!match)
1716 794 : continue; /* no match, so ignore this EC */
1717 :
1718 : /*
1719 : * Yes it does! Try to generate a clause INNERVAR = CONSTANT for each
1720 : * CONSTANT in the EC. Note that we must succeed with at least one
1721 : * constant before we can decide to throw away the outer-join clause.
1722 : */
1723 47 : match = false;
1724 177 : foreach(lc2, cur_ec->ec_members)
1725 : {
1726 130 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1727 : Oid eq_op;
1728 : RestrictInfo *newrinfo;
1729 :
1730 130 : if (!cur_em->em_is_const)
1731 79 : continue; /* ignore non-const members */
1732 51 : eq_op = select_equality_operator(cur_ec,
1733 : inner_datatype,
1734 : cur_em->em_datatype);
1735 51 : if (!OidIsValid(eq_op))
1736 0 : continue; /* can't generate equality */
1737 51 : newrinfo = build_implied_join_equality(eq_op,
1738 : cur_ec->ec_collation,
1739 : innervar,
1740 : cur_em->em_expr,
1741 : bms_copy(inner_relids),
1742 : bms_copy(inner_nullable_relids),
1743 : cur_ec->ec_min_security);
1744 51 : if (process_equivalence(root, newrinfo, true))
1745 51 : match = true;
1746 : }
1747 :
1748 : /*
1749 : * If we were able to equate INNERVAR to any constant, report success.
1750 : * Otherwise, fall out of the search loop, since we know the OUTERVAR
1751 : * appears in at most one EC.
1752 : */
1753 47 : if (match)
1754 47 : return true;
1755 : else
1756 0 : break;
1757 : }
1758 :
1759 1483 : return false; /* failed to make any deduction */
1760 : }
1761 :
1762 : /*
1763 : * reconsider_outer_join_clauses for a single FULL JOIN clause
1764 : *
1765 : * Returns TRUE if we were able to propagate a constant through the clause.
1766 : */
1767 : static bool
1768 33 : reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
1769 : {
1770 : Expr *leftvar;
1771 : Expr *rightvar;
1772 : Oid opno,
1773 : collation,
1774 : left_type,
1775 : right_type;
1776 : Relids left_relids,
1777 : right_relids,
1778 : left_nullable_relids,
1779 : right_nullable_relids;
1780 : ListCell *lc1;
1781 :
1782 : /* Can't use an outerjoin_delayed clause here */
1783 33 : if (rinfo->outerjoin_delayed)
1784 0 : return false;
1785 :
1786 : /* Extract needed info from the clause */
1787 33 : Assert(is_opclause(rinfo->clause));
1788 33 : opno = ((OpExpr *) rinfo->clause)->opno;
1789 33 : collation = ((OpExpr *) rinfo->clause)->inputcollid;
1790 33 : op_input_types(opno, &left_type, &right_type);
1791 33 : leftvar = (Expr *) get_leftop(rinfo->clause);
1792 33 : rightvar = (Expr *) get_rightop(rinfo->clause);
1793 33 : left_relids = rinfo->left_relids;
1794 33 : right_relids = rinfo->right_relids;
1795 33 : left_nullable_relids = bms_intersect(left_relids,
1796 33 : rinfo->nullable_relids);
1797 33 : right_nullable_relids = bms_intersect(right_relids,
1798 33 : rinfo->nullable_relids);
1799 :
1800 163 : foreach(lc1, root->eq_classes)
1801 : {
1802 131 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1803 131 : EquivalenceMember *coal_em = NULL;
1804 : bool match;
1805 : bool matchleft;
1806 : bool matchright;
1807 : ListCell *lc2;
1808 :
1809 : /* Ignore EC unless it contains pseudoconstants */
1810 131 : if (!cur_ec->ec_has_const)
1811 128 : continue;
1812 : /* Never match to a volatile EC */
1813 3 : if (cur_ec->ec_has_volatile)
1814 0 : continue;
1815 : /* It has to match the outer-join clause as to semantics, too */
1816 3 : if (collation != cur_ec->ec_collation)
1817 0 : continue;
1818 3 : if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
1819 2 : continue;
1820 :
1821 : /*
1822 : * Does it contain a COALESCE(leftvar, rightvar) construct?
1823 : *
1824 : * We can assume the COALESCE() inputs are in the same order as the
1825 : * join clause, since both were automatically generated in the cases
1826 : * we care about.
1827 : *
1828 : * XXX currently this may fail to match in cross-type cases because
1829 : * the COALESCE will contain typecast operations while the join clause
1830 : * may not (if there is a cross-type mergejoin operator available for
1831 : * the two column types). Is it OK to strip implicit coercions from
1832 : * the COALESCE arguments?
1833 : */
1834 1 : match = false;
1835 1 : foreach(lc2, cur_ec->ec_members)
1836 : {
1837 1 : coal_em = (EquivalenceMember *) lfirst(lc2);
1838 1 : Assert(!coal_em->em_is_child); /* no children yet */
1839 1 : if (IsA(coal_em->em_expr, CoalesceExpr))
1840 : {
1841 1 : CoalesceExpr *cexpr = (CoalesceExpr *) coal_em->em_expr;
1842 : Node *cfirst;
1843 : Node *csecond;
1844 :
1845 1 : if (list_length(cexpr->args) != 2)
1846 0 : continue;
1847 1 : cfirst = (Node *) linitial(cexpr->args);
1848 1 : csecond = (Node *) lsecond(cexpr->args);
1849 :
1850 1 : if (equal(leftvar, cfirst) && equal(rightvar, csecond))
1851 : {
1852 1 : match = true;
1853 1 : break;
1854 : }
1855 : }
1856 : }
1857 1 : if (!match)
1858 0 : continue; /* no match, so ignore this EC */
1859 :
1860 : /*
1861 : * Yes it does! Try to generate clauses LEFTVAR = CONSTANT and
1862 : * RIGHTVAR = CONSTANT for each CONSTANT in the EC. Note that we must
1863 : * succeed with at least one constant for each var before we can
1864 : * decide to throw away the outer-join clause.
1865 : */
1866 1 : matchleft = matchright = false;
1867 3 : foreach(lc2, cur_ec->ec_members)
1868 : {
1869 2 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1870 : Oid eq_op;
1871 : RestrictInfo *newrinfo;
1872 :
1873 2 : if (!cur_em->em_is_const)
1874 1 : continue; /* ignore non-const members */
1875 1 : eq_op = select_equality_operator(cur_ec,
1876 : left_type,
1877 : cur_em->em_datatype);
1878 1 : if (OidIsValid(eq_op))
1879 : {
1880 1 : newrinfo = build_implied_join_equality(eq_op,
1881 : cur_ec->ec_collation,
1882 : leftvar,
1883 : cur_em->em_expr,
1884 : bms_copy(left_relids),
1885 : bms_copy(left_nullable_relids),
1886 : cur_ec->ec_min_security);
1887 1 : if (process_equivalence(root, newrinfo, true))
1888 1 : matchleft = true;
1889 : }
1890 1 : eq_op = select_equality_operator(cur_ec,
1891 : right_type,
1892 : cur_em->em_datatype);
1893 1 : if (OidIsValid(eq_op))
1894 : {
1895 1 : newrinfo = build_implied_join_equality(eq_op,
1896 : cur_ec->ec_collation,
1897 : rightvar,
1898 : cur_em->em_expr,
1899 : bms_copy(right_relids),
1900 : bms_copy(right_nullable_relids),
1901 : cur_ec->ec_min_security);
1902 1 : if (process_equivalence(root, newrinfo, true))
1903 1 : matchright = true;
1904 : }
1905 : }
1906 :
1907 : /*
1908 : * If we were able to equate both vars to constants, we're done, and
1909 : * we can throw away the full-join clause as redundant. Moreover, we
1910 : * can remove the COALESCE entry from the EC, since the added
1911 : * restrictions ensure it will always have the expected value. (We
1912 : * don't bother trying to update ec_relids or ec_sources.)
1913 : */
1914 1 : if (matchleft && matchright)
1915 : {
1916 1 : cur_ec->ec_members = list_delete_ptr(cur_ec->ec_members, coal_em);
1917 1 : return true;
1918 : }
1919 :
1920 : /*
1921 : * Otherwise, fall out of the search loop, since we know the COALESCE
1922 : * appears in at most one EC (XXX might stop being true if we allow
1923 : * stripping of coercions above?)
1924 : */
1925 0 : break;
1926 : }
1927 :
1928 32 : return false; /* failed to make any deduction */
1929 : }
1930 :
1931 :
1932 : /*
1933 : * exprs_known_equal
1934 : * Detect whether two expressions are known equal due to equivalence
1935 : * relationships.
1936 : *
1937 : * Actually, this only shows that the expressions are equal according
1938 : * to some opfamily's notion of equality --- but we only use it for
1939 : * selectivity estimation, so a fuzzy idea of equality is OK.
1940 : *
1941 : * Note: does not bother to check for "equal(item1, item2)"; caller must
1942 : * check that case if it's possible to pass identical items.
1943 : */
1944 : bool
1945 58 : exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
1946 : {
1947 : ListCell *lc1;
1948 :
1949 353 : foreach(lc1, root->eq_classes)
1950 : {
1951 298 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
1952 298 : bool item1member = false;
1953 298 : bool item2member = false;
1954 : ListCell *lc2;
1955 :
1956 : /* Never match to a volatile EC */
1957 298 : if (ec->ec_has_volatile)
1958 0 : continue;
1959 :
1960 705 : foreach(lc2, ec->ec_members)
1961 : {
1962 410 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
1963 :
1964 410 : if (em->em_is_child)
1965 0 : continue; /* ignore children here */
1966 410 : if (equal(item1, em->em_expr))
1967 48 : item1member = true;
1968 362 : else if (equal(item2, em->em_expr))
1969 48 : item2member = true;
1970 : /* Exit as soon as equality is proven */
1971 410 : if (item1member && item2member)
1972 3 : return true;
1973 : }
1974 : }
1975 55 : return false;
1976 : }
1977 :
1978 :
1979 : /*
1980 : * match_eclasses_to_foreign_key_col
1981 : * See whether a foreign key column match is proven by any eclass.
1982 : *
1983 : * If the referenced and referencing Vars of the fkey's colno'th column are
1984 : * known equal due to any eclass, return that eclass; otherwise return NULL.
1985 : * (In principle there might be more than one matching eclass if multiple
1986 : * collations are involved, but since collation doesn't matter for equality,
1987 : * we ignore that fine point here.) This is much like exprs_known_equal,
1988 : * except that we insist on the comparison operator matching the eclass, so
1989 : * that the result is definite not approximate.
1990 : */
1991 : EquivalenceClass *
1992 156 : match_eclasses_to_foreign_key_col(PlannerInfo *root,
1993 : ForeignKeyOptInfo *fkinfo,
1994 : int colno)
1995 : {
1996 156 : Index var1varno = fkinfo->con_relid;
1997 156 : AttrNumber var1attno = fkinfo->conkey[colno];
1998 156 : Index var2varno = fkinfo->ref_relid;
1999 156 : AttrNumber var2attno = fkinfo->confkey[colno];
2000 156 : Oid eqop = fkinfo->conpfeqop[colno];
2001 156 : List *opfamilies = NIL; /* compute only if needed */
2002 : ListCell *lc1;
2003 :
2004 699 : foreach(lc1, root->eq_classes)
2005 : {
2006 574 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2007 574 : bool item1member = false;
2008 574 : bool item2member = false;
2009 : ListCell *lc2;
2010 :
2011 : /* Never match to a volatile EC */
2012 574 : if (ec->ec_has_volatile)
2013 0 : continue;
2014 : /* Note: it seems okay to match to "broken" eclasses here */
2015 :
2016 1240 : foreach(lc2, ec->ec_members)
2017 : {
2018 697 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
2019 : Var *var;
2020 :
2021 697 : if (em->em_is_child)
2022 0 : continue; /* ignore children here */
2023 :
2024 : /* EM must be a Var, possibly with RelabelType */
2025 697 : var = (Var *) em->em_expr;
2026 1473 : while (var && IsA(var, RelabelType))
2027 79 : var = (Var *) ((RelabelType *) var)->arg;
2028 697 : if (!(var && IsA(var, Var)))
2029 62 : continue;
2030 :
2031 : /* Match? */
2032 635 : if (var->varno == var1varno && var->varattno == var1attno)
2033 131 : item1member = true;
2034 504 : else if (var->varno == var2varno && var->varattno == var2attno)
2035 145 : item2member = true;
2036 :
2037 : /* Have we found both PK and FK column in this EC? */
2038 635 : if (item1member && item2member)
2039 : {
2040 : /*
2041 : * Succeed if eqop matches EC's opfamilies. We could test
2042 : * this before scanning the members, but it's probably cheaper
2043 : * to test for member matches first.
2044 : */
2045 31 : if (opfamilies == NIL) /* compute if we didn't already */
2046 31 : opfamilies = get_mergejoin_opfamilies(eqop);
2047 31 : if (equal(opfamilies, ec->ec_opfamilies))
2048 31 : return ec;
2049 : /* Otherwise, done with this EC, move on to the next */
2050 0 : break;
2051 : }
2052 : }
2053 : }
2054 125 : return NULL;
2055 : }
2056 :
2057 :
2058 : /*
2059 : * add_child_rel_equivalences
2060 : * Search for EC members that reference the parent_rel, and
2061 : * add transformed members referencing the child_rel.
2062 : *
2063 : * Note that this function won't be called at all unless we have at least some
2064 : * reason to believe that the EC members it generates will be useful.
2065 : *
2066 : * parent_rel and child_rel could be derived from appinfo, but since the
2067 : * caller has already computed them, we might as well just pass them in.
2068 : */
2069 : void
2070 845 : add_child_rel_equivalences(PlannerInfo *root,
2071 : AppendRelInfo *appinfo,
2072 : RelOptInfo *parent_rel,
2073 : RelOptInfo *child_rel)
2074 : {
2075 : ListCell *lc1;
2076 :
2077 2015 : foreach(lc1, root->eq_classes)
2078 : {
2079 1170 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2080 : ListCell *lc2;
2081 :
2082 : /*
2083 : * If this EC contains a volatile expression, then generating child
2084 : * EMs would be downright dangerous, so skip it. We rely on a
2085 : * volatile EC having only one EM.
2086 : */
2087 1170 : if (cur_ec->ec_has_volatile)
2088 0 : continue;
2089 :
2090 : /*
2091 : * No point in searching if parent rel not mentioned in eclass; but we
2092 : * can't tell that for sure if parent rel is itself a child.
2093 : */
2094 2262 : if (parent_rel->reloptkind == RELOPT_BASEREL &&
2095 1092 : !bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
2096 122 : continue;
2097 :
2098 4814 : foreach(lc2, cur_ec->ec_members)
2099 : {
2100 3766 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2101 :
2102 3766 : if (cur_em->em_is_const)
2103 96 : continue; /* ignore consts here */
2104 :
2105 : /* Does it reference parent_rel? */
2106 3670 : if (bms_overlap(cur_em->em_relids, parent_rel->relids))
2107 : {
2108 : /* Yes, generate transformed child version */
2109 : Expr *child_expr;
2110 : Relids new_relids;
2111 : Relids new_nullable_relids;
2112 :
2113 1036 : child_expr = (Expr *)
2114 : adjust_appendrel_attrs(root,
2115 1036 : (Node *) cur_em->em_expr,
2116 : 1, &appinfo);
2117 :
2118 : /*
2119 : * Transform em_relids to match. Note we do *not* do
2120 : * pull_varnos(child_expr) here, as for example the
2121 : * transformation might have substituted a constant, but we
2122 : * don't want the child member to be marked as constant.
2123 : */
2124 1036 : new_relids = bms_difference(cur_em->em_relids,
2125 1036 : parent_rel->relids);
2126 1036 : new_relids = bms_add_members(new_relids, child_rel->relids);
2127 :
2128 : /*
2129 : * And likewise for nullable_relids. Note this code assumes
2130 : * parent and child relids are singletons.
2131 : */
2132 1036 : new_nullable_relids = cur_em->em_nullable_relids;
2133 1036 : if (bms_overlap(new_nullable_relids, parent_rel->relids))
2134 : {
2135 0 : new_nullable_relids = bms_difference(new_nullable_relids,
2136 0 : parent_rel->relids);
2137 0 : new_nullable_relids = bms_add_members(new_nullable_relids,
2138 0 : child_rel->relids);
2139 : }
2140 :
2141 1036 : (void) add_eq_member(cur_ec, child_expr,
2142 : new_relids, new_nullable_relids,
2143 : true, cur_em->em_datatype);
2144 : }
2145 : }
2146 : }
2147 845 : }
2148 :
2149 :
2150 : /*
2151 : * generate_implied_equalities_for_column
2152 : * Create EC-derived joinclauses usable with a specific column.
2153 : *
2154 : * This is used by indxpath.c to extract potentially indexable joinclauses
2155 : * from ECs, and can be used by foreign data wrappers for similar purposes.
2156 : * We assume that only expressions in Vars of a single table are of interest,
2157 : * but the caller provides a callback function to identify exactly which
2158 : * such expressions it would like to know about.
2159 : *
2160 : * We assume that any given table/index column could appear in only one EC.
2161 : * (This should be true in all but the most pathological cases, and if it
2162 : * isn't, we stop on the first match anyway.) Therefore, what we return
2163 : * is a redundant list of clauses equating the table/index column to each of
2164 : * the other-relation values it is known to be equal to. Any one of
2165 : * these clauses can be used to create a parameterized path, and there
2166 : * is no value in using more than one. (But it *is* worthwhile to create
2167 : * a separate parameterized path for each one, since that leads to different
2168 : * join orders.)
2169 : *
2170 : * The caller can pass a Relids set of rels we aren't interested in joining
2171 : * to, so as to save the work of creating useless clauses.
2172 : */
2173 : List *
2174 11195 : generate_implied_equalities_for_column(PlannerInfo *root,
2175 : RelOptInfo *rel,
2176 : ec_matches_callback_type callback,
2177 : void *callback_arg,
2178 : Relids prohibited_rels)
2179 : {
2180 11195 : List *result = NIL;
2181 11195 : bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2182 : Relids parent_relids;
2183 : ListCell *lc1;
2184 :
2185 : /* Indexes are available only on base or "other" member relations. */
2186 11195 : Assert(IS_SIMPLE_REL(rel));
2187 :
2188 : /* If it's a child rel, we'll need to know what its parent(s) are */
2189 11195 : if (is_child_rel)
2190 189 : parent_relids = find_childrel_parents(root, rel);
2191 : else
2192 11006 : parent_relids = NULL; /* not used, but keep compiler quiet */
2193 :
2194 42984 : foreach(lc1, root->eq_classes)
2195 : {
2196 34424 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2197 : EquivalenceMember *cur_em;
2198 : ListCell *lc2;
2199 :
2200 : /*
2201 : * Won't generate joinclauses if const or single-member (the latter
2202 : * test covers the volatile case too)
2203 : */
2204 34424 : if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2205 20889 : continue;
2206 :
2207 : /*
2208 : * No point in searching if rel not mentioned in eclass (but we can't
2209 : * tell that for a child rel).
2210 : */
2211 26867 : if (!is_child_rel &&
2212 13332 : !bms_is_subset(rel->relids, cur_ec->ec_relids))
2213 3982 : continue;
2214 :
2215 : /*
2216 : * Scan members, looking for a match to the target column. Note that
2217 : * child EC members are considered, but only when they belong to the
2218 : * target relation. (Unlike regular members, the same expression
2219 : * could be a child member of more than one EC. Therefore, it's
2220 : * potentially order-dependent which EC a child relation's target
2221 : * column gets matched to. This is annoying but it only happens in
2222 : * corner cases, so for now we live with just reporting the first
2223 : * match. See also get_eclass_for_sort_expr.)
2224 : */
2225 9553 : cur_em = NULL;
2226 25915 : foreach(lc2, cur_ec->ec_members)
2227 : {
2228 19005 : cur_em = (EquivalenceMember *) lfirst(lc2);
2229 28514 : if (bms_equal(cur_em->em_relids, rel->relids) &&
2230 9509 : callback(root, rel, cur_ec, cur_em, callback_arg))
2231 2643 : break;
2232 16362 : cur_em = NULL;
2233 : }
2234 :
2235 9553 : if (!cur_em)
2236 6910 : continue;
2237 :
2238 : /*
2239 : * Found our match. Scan the other EC members and attempt to generate
2240 : * joinclauses.
2241 : */
2242 8278 : foreach(lc2, cur_ec->ec_members)
2243 : {
2244 5635 : EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2245 : Oid eq_op;
2246 : RestrictInfo *rinfo;
2247 :
2248 5635 : if (other_em->em_is_child)
2249 294 : continue; /* ignore children here */
2250 :
2251 : /* Make sure it'll be a join to a different rel */
2252 8100 : if (other_em == cur_em ||
2253 2759 : bms_overlap(other_em->em_relids, rel->relids))
2254 2588 : continue;
2255 :
2256 : /* Forget it if caller doesn't want joins to this rel */
2257 2753 : if (bms_overlap(other_em->em_relids, prohibited_rels))
2258 0 : continue;
2259 :
2260 : /*
2261 : * Also, if this is a child rel, avoid generating a useless join
2262 : * to its parent rel(s).
2263 : */
2264 2887 : if (is_child_rel &&
2265 134 : bms_overlap(parent_relids, other_em->em_relids))
2266 63 : continue;
2267 :
2268 2690 : eq_op = select_equality_operator(cur_ec,
2269 : cur_em->em_datatype,
2270 : other_em->em_datatype);
2271 2690 : if (!OidIsValid(eq_op))
2272 0 : continue;
2273 :
2274 : /* set parent_ec to mark as redundant with other joinclauses */
2275 2690 : rinfo = create_join_clause(root, cur_ec, eq_op,
2276 : cur_em, other_em,
2277 : cur_ec);
2278 :
2279 2690 : result = lappend(result, rinfo);
2280 : }
2281 :
2282 : /*
2283 : * If somehow we failed to create any join clauses, we might as well
2284 : * keep scanning the ECs for another match. But if we did make any,
2285 : * we're done, because we don't want to return non-redundant clauses.
2286 : */
2287 2643 : if (result)
2288 2635 : break;
2289 : }
2290 :
2291 11195 : return result;
2292 : }
2293 :
2294 : /*
2295 : * have_relevant_eclass_joinclause
2296 : * Detect whether there is an EquivalenceClass that could produce
2297 : * a joinclause involving the two given relations.
2298 : *
2299 : * This is essentially a very cut-down version of
2300 : * generate_join_implied_equalities(). Note it's OK to occasionally say "yes"
2301 : * incorrectly. Hence we don't bother with details like whether the lack of a
2302 : * cross-type operator might prevent the clause from actually being generated.
2303 : */
2304 : bool
2305 6059 : have_relevant_eclass_joinclause(PlannerInfo *root,
2306 : RelOptInfo *rel1, RelOptInfo *rel2)
2307 : {
2308 : ListCell *lc1;
2309 :
2310 31829 : foreach(lc1, root->eq_classes)
2311 : {
2312 30304 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2313 :
2314 : /*
2315 : * Won't generate joinclauses if single-member (this test covers the
2316 : * volatile case too)
2317 : */
2318 30304 : if (list_length(ec->ec_members) <= 1)
2319 11775 : continue;
2320 :
2321 : /*
2322 : * We do not need to examine the individual members of the EC, because
2323 : * all that we care about is whether each rel overlaps the relids of
2324 : * at least one member, and a test on ec_relids is sufficient to prove
2325 : * that. (As with have_relevant_joinclause(), it is not necessary
2326 : * that the EC be able to form a joinclause relating exactly the two
2327 : * given rels, only that it be able to form a joinclause mentioning
2328 : * both, and this will surely be true if both of them overlap
2329 : * ec_relids.)
2330 : *
2331 : * Note we don't test ec_broken; if we did, we'd need a separate code
2332 : * path to look through ec_sources. Checking the membership anyway is
2333 : * OK as a possibly-overoptimistic heuristic.
2334 : *
2335 : * We don't test ec_has_const either, even though a const eclass won't
2336 : * generate real join clauses. This is because if we had "WHERE a.x =
2337 : * b.y and a.x = 42", it is worth considering a join between a and b,
2338 : * since the join result is likely to be small even though it'll end
2339 : * up being an unqualified nestloop.
2340 : */
2341 28290 : if (bms_overlap(rel1->relids, ec->ec_relids) &&
2342 9761 : bms_overlap(rel2->relids, ec->ec_relids))
2343 4534 : return true;
2344 : }
2345 :
2346 1525 : return false;
2347 : }
2348 :
2349 :
2350 : /*
2351 : * has_relevant_eclass_joinclause
2352 : * Detect whether there is an EquivalenceClass that could produce
2353 : * a joinclause involving the given relation and anything else.
2354 : *
2355 : * This is the same as have_relevant_eclass_joinclause with the other rel
2356 : * implicitly defined as "everything else in the query".
2357 : */
2358 : bool
2359 24874 : has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
2360 : {
2361 : ListCell *lc1;
2362 :
2363 56583 : foreach(lc1, root->eq_classes)
2364 : {
2365 37511 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2366 :
2367 : /*
2368 : * Won't generate joinclauses if single-member (this test covers the
2369 : * volatile case too)
2370 : */
2371 37511 : if (list_length(ec->ec_members) <= 1)
2372 14716 : continue;
2373 :
2374 : /*
2375 : * Per the comment in have_relevant_eclass_joinclause, it's sufficient
2376 : * to find an EC that mentions both this rel and some other rel.
2377 : */
2378 40644 : if (bms_overlap(rel1->relids, ec->ec_relids) &&
2379 17849 : !bms_is_subset(ec->ec_relids, rel1->relids))
2380 5802 : return true;
2381 : }
2382 :
2383 19072 : return false;
2384 : }
2385 :
2386 :
2387 : /*
2388 : * eclass_useful_for_merging
2389 : * Detect whether the EC could produce any mergejoinable join clauses
2390 : * against the specified relation.
2391 : *
2392 : * This is just a heuristic test and doesn't have to be exact; it's better
2393 : * to say "yes" incorrectly than "no". Hence we don't bother with details
2394 : * like whether the lack of a cross-type operator might prevent the clause
2395 : * from actually being generated.
2396 : */
2397 : bool
2398 14907 : eclass_useful_for_merging(PlannerInfo *root,
2399 : EquivalenceClass *eclass,
2400 : RelOptInfo *rel)
2401 : {
2402 : Relids relids;
2403 : ListCell *lc;
2404 :
2405 14907 : Assert(!eclass->ec_merged);
2406 :
2407 : /*
2408 : * Won't generate joinclauses if const or single-member (the latter test
2409 : * covers the volatile case too)
2410 : */
2411 14907 : if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
2412 2119 : return false;
2413 :
2414 : /*
2415 : * Note we don't test ec_broken; if we did, we'd need a separate code path
2416 : * to look through ec_sources. Checking the members anyway is OK as a
2417 : * possibly-overoptimistic heuristic.
2418 : */
2419 :
2420 : /* If specified rel is a child, we must consider the topmost parent rel */
2421 12788 : if (IS_OTHER_REL(rel))
2422 : {
2423 134 : Assert(!bms_is_empty(rel->top_parent_relids));
2424 134 : relids = rel->top_parent_relids;
2425 : }
2426 : else
2427 12654 : relids = rel->relids;
2428 :
2429 : /* If rel already includes all members of eclass, no point in searching */
2430 12788 : if (bms_is_subset(eclass->ec_relids, relids))
2431 5936 : return false;
2432 :
2433 : /* To join, we need a member not in the given rel */
2434 10801 : foreach(lc, eclass->ec_members)
2435 : {
2436 10745 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
2437 :
2438 10745 : if (cur_em->em_is_child)
2439 0 : continue; /* ignore children here */
2440 :
2441 10745 : if (!bms_overlap(cur_em->em_relids, relids))
2442 6796 : return true;
2443 : }
2444 :
2445 56 : return false;
2446 : }
2447 :
2448 :
2449 : /*
2450 : * is_redundant_derived_clause
2451 : * Test whether rinfo is derived from same EC as any clause in clauselist;
2452 : * if so, it can be presumed to represent a condition that's redundant
2453 : * with that member of the list.
2454 : */
2455 : bool
2456 17907 : is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist)
2457 : {
2458 17907 : EquivalenceClass *parent_ec = rinfo->parent_ec;
2459 : ListCell *lc;
2460 :
2461 : /* Fail if it's not a potentially-redundant clause from some EC */
2462 17907 : if (parent_ec == NULL)
2463 11781 : return false;
2464 :
2465 6654 : foreach(lc, clauselist)
2466 : {
2467 6605 : RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2468 :
2469 6605 : if (otherrinfo->parent_ec == parent_ec)
2470 6077 : return true;
2471 : }
2472 :
2473 49 : return false;
2474 : }
|
