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-2023, 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/appendinfo.h"
26 : #include "optimizer/clauses.h"
27 : #include "optimizer/optimizer.h"
28 : #include "optimizer/pathnode.h"
29 : #include "optimizer/paths.h"
30 : #include "optimizer/planmain.h"
31 : #include "optimizer/restrictinfo.h"
32 : #include "rewrite/rewriteManip.h"
33 : #include "utils/lsyscache.h"
34 :
35 :
36 : static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
37 : Expr *expr, Relids relids,
38 : JoinDomain *jdomain,
39 : EquivalenceMember *parent,
40 : Oid datatype);
41 : static bool is_exprlist_member(Expr *node, List *exprs);
42 : static void generate_base_implied_equalities_const(PlannerInfo *root,
43 : EquivalenceClass *ec);
44 : static void generate_base_implied_equalities_no_const(PlannerInfo *root,
45 : EquivalenceClass *ec);
46 : static void generate_base_implied_equalities_broken(PlannerInfo *root,
47 : EquivalenceClass *ec);
48 : static List *generate_join_implied_equalities_normal(PlannerInfo *root,
49 : EquivalenceClass *ec,
50 : Relids join_relids,
51 : Relids outer_relids,
52 : Relids inner_relids);
53 : static List *generate_join_implied_equalities_broken(PlannerInfo *root,
54 : EquivalenceClass *ec,
55 : Relids nominal_join_relids,
56 : Relids outer_relids,
57 : Relids nominal_inner_relids,
58 : RelOptInfo *inner_rel);
59 : static Oid select_equality_operator(EquivalenceClass *ec,
60 : Oid lefttype, Oid righttype);
61 : static RestrictInfo *create_join_clause(PlannerInfo *root,
62 : EquivalenceClass *ec, Oid opno,
63 : EquivalenceMember *leftem,
64 : EquivalenceMember *rightem,
65 : EquivalenceClass *parent_ec);
66 : static bool reconsider_outer_join_clause(PlannerInfo *root,
67 : OuterJoinClauseInfo *ojcinfo,
68 : bool outer_on_left);
69 : static bool reconsider_full_join_clause(PlannerInfo *root,
70 : OuterJoinClauseInfo *ojcinfo);
71 : static JoinDomain *find_join_domain(PlannerInfo *root, Relids relids);
72 : static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root,
73 : Relids relids);
74 : static Bitmapset *get_common_eclass_indexes(PlannerInfo *root, Relids relids1,
75 : Relids relids2);
76 :
77 :
78 : /*
79 : * process_equivalence
80 : * The given clause has a mergejoinable operator and is not an outer-join
81 : * qualification, so its two sides can be considered equal
82 : * anywhere they are both computable; moreover that equality can be
83 : * extended transitively. Record this knowledge in the EquivalenceClass
84 : * data structure, if applicable. Returns true if successful, false if not
85 : * (in which case caller should treat the clause as ordinary, not an
86 : * equivalence).
87 : *
88 : * In some cases, although we cannot convert a clause into EquivalenceClass
89 : * knowledge, we can still modify it to a more useful form than the original.
90 : * Then, *p_restrictinfo will be replaced by a new RestrictInfo, which is what
91 : * the caller should use for further processing.
92 : *
93 : * jdomain is the join domain within which the given clause was found.
94 : * This limits the applicability of deductions from the EquivalenceClass,
95 : * as described in optimizer/README.
96 : *
97 : * We reject proposed equivalence clauses if they contain leaky functions
98 : * and have security_level above zero. The EC evaluation rules require us to
99 : * apply certain tests at certain joining levels, and we can't tolerate
100 : * delaying any test on security_level grounds. By rejecting candidate clauses
101 : * that might require security delays, we ensure it's safe to apply an EC
102 : * clause as soon as it's supposed to be applied.
103 : *
104 : * On success return, we have also initialized the clause's left_ec/right_ec
105 : * fields to point to the EquivalenceClass representing it. This saves lookup
106 : * effort later.
107 : *
108 : * Note: constructing merged EquivalenceClasses is a standard UNION-FIND
109 : * problem, for which there exist better data structures than simple lists.
110 : * If this code ever proves to be a bottleneck then it could be sped up ---
111 : * but for now, simple is beautiful.
112 : *
113 : * Note: this is only called during planner startup, not during GEQO
114 : * exploration, so we need not worry about whether we're in the right
115 : * memory context.
116 : */
117 : bool
118 228782 : process_equivalence(PlannerInfo *root,
119 : RestrictInfo **p_restrictinfo,
120 : JoinDomain *jdomain)
121 : {
122 228782 : RestrictInfo *restrictinfo = *p_restrictinfo;
123 228782 : Expr *clause = restrictinfo->clause;
124 : Oid opno,
125 : collation,
126 : item1_type,
127 : item2_type;
128 : Expr *item1;
129 : Expr *item2;
130 : Relids item1_relids,
131 : item2_relids;
132 : List *opfamilies;
133 : EquivalenceClass *ec1,
134 : *ec2;
135 : EquivalenceMember *em1,
136 : *em2;
137 : ListCell *lc1;
138 : int ec2_idx;
139 :
140 : /* Should not already be marked as having generated an eclass */
141 : Assert(restrictinfo->left_ec == NULL);
142 : Assert(restrictinfo->right_ec == NULL);
143 :
144 : /* Reject if it is potentially postponable by security considerations */
145 228782 : if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
146 202 : return false;
147 :
148 : /* Extract info from given clause */
149 : Assert(is_opclause(clause));
150 228580 : opno = ((OpExpr *) clause)->opno;
151 228580 : collation = ((OpExpr *) clause)->inputcollid;
152 228580 : item1 = (Expr *) get_leftop(clause);
153 228580 : item2 = (Expr *) get_rightop(clause);
154 228580 : item1_relids = restrictinfo->left_relids;
155 228580 : item2_relids = restrictinfo->right_relids;
156 :
157 : /*
158 : * Ensure both input expressions expose the desired collation (their types
159 : * should be OK already); see comments for canonicalize_ec_expression.
160 : */
161 228580 : item1 = canonicalize_ec_expression(item1,
162 : exprType((Node *) item1),
163 : collation);
164 228580 : item2 = canonicalize_ec_expression(item2,
165 : exprType((Node *) item2),
166 : collation);
167 :
168 : /*
169 : * Clauses of the form X=X cannot be translated into EquivalenceClasses.
170 : * We'd either end up with a single-entry EC, losing the knowledge that
171 : * the clause was present at all, or else make an EC with duplicate
172 : * entries, causing other issues.
173 : */
174 228580 : if (equal(item1, item2))
175 : {
176 : /*
177 : * If the operator is strict, then the clause can be treated as just
178 : * "X IS NOT NULL". (Since we know we are considering a top-level
179 : * qual, we can ignore the difference between FALSE and NULL results.)
180 : * It's worth making the conversion because we'll typically get a much
181 : * better selectivity estimate than we would for X=X.
182 : *
183 : * If the operator is not strict, we can't be sure what it will do
184 : * with NULLs, so don't attempt to optimize it.
185 : */
186 42 : set_opfuncid((OpExpr *) clause);
187 42 : if (func_strict(((OpExpr *) clause)->opfuncid))
188 : {
189 42 : NullTest *ntest = makeNode(NullTest);
190 :
191 42 : ntest->arg = item1;
192 42 : ntest->nulltesttype = IS_NOT_NULL;
193 42 : ntest->argisrow = false; /* correct even if composite arg */
194 42 : ntest->location = -1;
195 :
196 42 : *p_restrictinfo =
197 42 : make_restrictinfo(root,
198 : (Expr *) ntest,
199 42 : restrictinfo->is_pushed_down,
200 42 : restrictinfo->has_clone,
201 42 : restrictinfo->is_clone,
202 42 : restrictinfo->pseudoconstant,
203 : restrictinfo->security_level,
204 : NULL,
205 : restrictinfo->incompatible_relids,
206 : restrictinfo->outer_relids);
207 : }
208 42 : return false;
209 : }
210 :
211 : /*
212 : * We use the declared input types of the operator, not exprType() of the
213 : * inputs, as the nominal datatypes for opfamily lookup. This presumes
214 : * that btree operators are always registered with amoplefttype and
215 : * amoprighttype equal to their declared input types. We will need this
216 : * info anyway to build EquivalenceMember nodes, and by extracting it now
217 : * we can use type comparisons to short-circuit some equal() tests.
218 : */
219 228538 : op_input_types(opno, &item1_type, &item2_type);
220 :
221 228538 : opfamilies = restrictinfo->mergeopfamilies;
222 :
223 : /*
224 : * Sweep through the existing EquivalenceClasses looking for matches to
225 : * item1 and item2. These are the possible outcomes:
226 : *
227 : * 1. We find both in the same EC. The equivalence is already known, so
228 : * there's nothing to do.
229 : *
230 : * 2. We find both in different ECs. Merge the two ECs together.
231 : *
232 : * 3. We find just one. Add the other to its EC.
233 : *
234 : * 4. We find neither. Make a new, two-entry EC.
235 : *
236 : * Note: since all ECs are built through this process or the similar
237 : * search in get_eclass_for_sort_expr(), it's impossible that we'd match
238 : * an item in more than one existing nonvolatile EC. So it's okay to stop
239 : * at the first match.
240 : */
241 228538 : ec1 = ec2 = NULL;
242 228538 : em1 = em2 = NULL;
243 228538 : ec2_idx = -1;
244 361882 : foreach(lc1, root->eq_classes)
245 : {
246 133380 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
247 : ListCell *lc2;
248 :
249 : /* Never match to a volatile EC */
250 133380 : if (cur_ec->ec_has_volatile)
251 0 : continue;
252 :
253 : /*
254 : * The collation has to match; check this first since it's cheaper
255 : * than the opfamily comparison.
256 : */
257 133380 : if (collation != cur_ec->ec_collation)
258 10460 : continue;
259 :
260 : /*
261 : * A "match" requires matching sets of btree opfamilies. Use of
262 : * equal() for this test has implications discussed in the comments
263 : * for get_mergejoin_opfamilies().
264 : */
265 122920 : if (!equal(opfamilies, cur_ec->ec_opfamilies))
266 29690 : continue;
267 :
268 281382 : foreach(lc2, cur_ec->ec_members)
269 : {
270 188188 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
271 :
272 : Assert(!cur_em->em_is_child); /* no children yet */
273 :
274 : /*
275 : * Match constants only within the same JoinDomain (see
276 : * optimizer/README).
277 : */
278 188188 : if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
279 3468 : continue;
280 :
281 184720 : if (!ec1 &&
282 346392 : item1_type == cur_em->em_datatype &&
283 173070 : equal(item1, cur_em->em_expr))
284 : {
285 14970 : ec1 = cur_ec;
286 14970 : em1 = cur_em;
287 14970 : if (ec2)
288 18 : break;
289 : }
290 :
291 184702 : if (!ec2 &&
292 364696 : item2_type == cur_em->em_datatype &&
293 182156 : equal(item2, cur_em->em_expr))
294 : {
295 4292 : ec2 = cur_ec;
296 4292 : ec2_idx = foreach_current_index(lc1);
297 4292 : em2 = cur_em;
298 4292 : if (ec1)
299 18 : break;
300 : }
301 : }
302 :
303 93230 : if (ec1 && ec2)
304 36 : break;
305 : }
306 :
307 : /* Sweep finished, what did we find? */
308 :
309 228538 : if (ec1 && ec2)
310 : {
311 : /* If case 1, nothing to do, except add to sources */
312 36 : if (ec1 == ec2)
313 : {
314 12 : ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
315 12 : ec1->ec_min_security = Min(ec1->ec_min_security,
316 : restrictinfo->security_level);
317 12 : ec1->ec_max_security = Max(ec1->ec_max_security,
318 : restrictinfo->security_level);
319 : /* mark the RI as associated with this eclass */
320 12 : restrictinfo->left_ec = ec1;
321 12 : restrictinfo->right_ec = ec1;
322 : /* mark the RI as usable with this pair of EMs */
323 12 : restrictinfo->left_em = em1;
324 12 : restrictinfo->right_em = em2;
325 12 : return true;
326 : }
327 :
328 : /*
329 : * Case 2: need to merge ec1 and ec2. This should never happen after
330 : * the ECs have reached canonical state; otherwise, pathkeys could be
331 : * rendered non-canonical by the merge, and relation eclass indexes
332 : * would get broken by removal of an eq_classes list entry.
333 : */
334 24 : if (root->ec_merging_done)
335 0 : elog(ERROR, "too late to merge equivalence classes");
336 :
337 : /*
338 : * We add ec2's items to ec1, then set ec2's ec_merged link to point
339 : * to ec1 and remove ec2 from the eq_classes list. We cannot simply
340 : * delete ec2 because that could leave dangling pointers in existing
341 : * PathKeys. We leave it behind with a link so that the merged EC can
342 : * be found.
343 : */
344 24 : ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
345 24 : ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
346 24 : ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
347 24 : ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
348 24 : ec1->ec_has_const |= ec2->ec_has_const;
349 : /* can't need to set has_volatile */
350 24 : ec1->ec_min_security = Min(ec1->ec_min_security,
351 : ec2->ec_min_security);
352 24 : ec1->ec_max_security = Max(ec1->ec_max_security,
353 : ec2->ec_max_security);
354 24 : ec2->ec_merged = ec1;
355 24 : root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
356 : /* just to avoid debugging confusion w/ dangling pointers: */
357 24 : ec2->ec_members = NIL;
358 24 : ec2->ec_sources = NIL;
359 24 : ec2->ec_derives = NIL;
360 24 : ec2->ec_relids = NULL;
361 24 : ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
362 24 : ec1->ec_min_security = Min(ec1->ec_min_security,
363 : restrictinfo->security_level);
364 24 : ec1->ec_max_security = Max(ec1->ec_max_security,
365 : restrictinfo->security_level);
366 : /* mark the RI as associated with this eclass */
367 24 : restrictinfo->left_ec = ec1;
368 24 : restrictinfo->right_ec = ec1;
369 : /* mark the RI as usable with this pair of EMs */
370 24 : restrictinfo->left_em = em1;
371 24 : restrictinfo->right_em = em2;
372 : }
373 228502 : else if (ec1)
374 : {
375 : /* Case 3: add item2 to ec1 */
376 14934 : em2 = add_eq_member(ec1, item2, item2_relids,
377 : jdomain, NULL, item2_type);
378 14934 : ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
379 14934 : ec1->ec_min_security = Min(ec1->ec_min_security,
380 : restrictinfo->security_level);
381 14934 : ec1->ec_max_security = Max(ec1->ec_max_security,
382 : restrictinfo->security_level);
383 : /* mark the RI as associated with this eclass */
384 14934 : restrictinfo->left_ec = ec1;
385 14934 : restrictinfo->right_ec = ec1;
386 : /* mark the RI as usable with this pair of EMs */
387 14934 : restrictinfo->left_em = em1;
388 14934 : restrictinfo->right_em = em2;
389 : }
390 213568 : else if (ec2)
391 : {
392 : /* Case 3: add item1 to ec2 */
393 4256 : em1 = add_eq_member(ec2, item1, item1_relids,
394 : jdomain, NULL, item1_type);
395 4256 : ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
396 4256 : ec2->ec_min_security = Min(ec2->ec_min_security,
397 : restrictinfo->security_level);
398 4256 : ec2->ec_max_security = Max(ec2->ec_max_security,
399 : restrictinfo->security_level);
400 : /* mark the RI as associated with this eclass */
401 4256 : restrictinfo->left_ec = ec2;
402 4256 : restrictinfo->right_ec = ec2;
403 : /* mark the RI as usable with this pair of EMs */
404 4256 : restrictinfo->left_em = em1;
405 4256 : restrictinfo->right_em = em2;
406 : }
407 : else
408 : {
409 : /* Case 4: make a new, two-entry EC */
410 209312 : EquivalenceClass *ec = makeNode(EquivalenceClass);
411 :
412 209312 : ec->ec_opfamilies = opfamilies;
413 209312 : ec->ec_collation = collation;
414 209312 : ec->ec_members = NIL;
415 209312 : ec->ec_sources = list_make1(restrictinfo);
416 209312 : ec->ec_derives = NIL;
417 209312 : ec->ec_relids = NULL;
418 209312 : ec->ec_has_const = false;
419 209312 : ec->ec_has_volatile = false;
420 209312 : ec->ec_broken = false;
421 209312 : ec->ec_sortref = 0;
422 209312 : ec->ec_min_security = restrictinfo->security_level;
423 209312 : ec->ec_max_security = restrictinfo->security_level;
424 209312 : ec->ec_merged = NULL;
425 209312 : em1 = add_eq_member(ec, item1, item1_relids,
426 : jdomain, NULL, item1_type);
427 209312 : em2 = add_eq_member(ec, item2, item2_relids,
428 : jdomain, NULL, item2_type);
429 :
430 209312 : root->eq_classes = lappend(root->eq_classes, ec);
431 :
432 : /* mark the RI as associated with this eclass */
433 209312 : restrictinfo->left_ec = ec;
434 209312 : restrictinfo->right_ec = ec;
435 : /* mark the RI as usable with this pair of EMs */
436 209312 : restrictinfo->left_em = em1;
437 209312 : restrictinfo->right_em = em2;
438 : }
439 :
440 228526 : return true;
441 : }
442 :
443 : /*
444 : * canonicalize_ec_expression
445 : *
446 : * This function ensures that the expression exposes the expected type and
447 : * collation, so that it will be equal() to other equivalence-class expressions
448 : * that it ought to be equal() to.
449 : *
450 : * The rule for datatypes is that the exposed type should match what it would
451 : * be for an input to an operator of the EC's opfamilies; which is usually
452 : * the declared input type of the operator, but in the case of polymorphic
453 : * operators no relabeling is wanted (compare the behavior of parse_coerce.c).
454 : * Expressions coming in from quals will generally have the right type
455 : * already, but expressions coming from indexkeys may not (because they are
456 : * represented without any explicit relabel in pg_index), and the same problem
457 : * occurs for sort expressions (because the parser is likewise cavalier about
458 : * putting relabels on them). Such cases will be binary-compatible with the
459 : * real operators, so adding a RelabelType is sufficient.
460 : *
461 : * Also, the expression's exposed collation must match the EC's collation.
462 : * This is important because in comparisons like "foo < bar COLLATE baz",
463 : * only one of the expressions has the correct exposed collation as we receive
464 : * it from the parser. Forcing both of them to have it ensures that all
465 : * variant spellings of such a construct behave the same. Again, we can
466 : * stick on a RelabelType to force the right exposed collation. (It might
467 : * work to not label the collation at all in EC members, but this is risky
468 : * since some parts of the system expect exprCollation() to deliver the
469 : * right answer for a sort key.)
470 : */
471 : Expr *
472 1891834 : canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
473 : {
474 1891834 : Oid expr_type = exprType((Node *) expr);
475 :
476 : /*
477 : * For a polymorphic-input-type opclass, just keep the same exposed type.
478 : * RECORD opclasses work like polymorphic-type ones for this purpose.
479 : */
480 1891834 : if (IsPolymorphicType(req_type) || req_type == RECORDOID)
481 2410 : req_type = expr_type;
482 :
483 : /*
484 : * No work if the expression exposes the right type/collation already.
485 : */
486 3776550 : if (expr_type != req_type ||
487 1884716 : exprCollation((Node *) expr) != req_collation)
488 : {
489 : /*
490 : * If we have to change the type of the expression, set typmod to -1,
491 : * since the new type may not have the same typmod interpretation.
492 : * When we only have to change collation, preserve the exposed typmod.
493 : */
494 : int32 req_typmod;
495 :
496 7748 : if (expr_type != req_type)
497 7118 : req_typmod = -1;
498 : else
499 630 : req_typmod = exprTypmod((Node *) expr);
500 :
501 : /*
502 : * Use applyRelabelType so that we preserve const-flatness. This is
503 : * important since eval_const_expressions has already been applied.
504 : */
505 7748 : expr = (Expr *) applyRelabelType((Node *) expr,
506 : req_type, req_typmod, req_collation,
507 : COERCE_IMPLICIT_CAST, -1, false);
508 : }
509 :
510 1891834 : return expr;
511 : }
512 :
513 : /*
514 : * add_eq_member - build a new EquivalenceMember and add it to an EC
515 : */
516 : static EquivalenceMember *
517 642300 : add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
518 : JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
519 : {
520 642300 : EquivalenceMember *em = makeNode(EquivalenceMember);
521 :
522 642300 : em->em_expr = expr;
523 642300 : em->em_relids = relids;
524 642300 : em->em_is_const = false;
525 642300 : em->em_is_child = (parent != NULL);
526 642300 : em->em_datatype = datatype;
527 642300 : em->em_jdomain = jdomain;
528 642300 : em->em_parent = parent;
529 :
530 642300 : if (bms_is_empty(relids))
531 : {
532 : /*
533 : * No Vars, assume it's a pseudoconstant. This is correct for entries
534 : * generated from process_equivalence(), because a WHERE clause can't
535 : * contain aggregates or SRFs, and non-volatility was checked before
536 : * process_equivalence() ever got called. But
537 : * get_eclass_for_sort_expr() has to work harder. We put the tests
538 : * there not here to save cycles in the equivalence case.
539 : */
540 : Assert(!parent);
541 167216 : em->em_is_const = true;
542 167216 : ec->ec_has_const = true;
543 : /* it can't affect ec_relids */
544 : }
545 475084 : else if (!parent) /* child members don't add to ec_relids */
546 : {
547 434706 : ec->ec_relids = bms_add_members(ec->ec_relids, relids);
548 : }
549 642300 : ec->ec_members = lappend(ec->ec_members, em);
550 :
551 642300 : return em;
552 : }
553 :
554 :
555 : /*
556 : * get_eclass_for_sort_expr
557 : * Given an expression and opfamily/collation info, find an existing
558 : * equivalence class it is a member of; if none, optionally build a new
559 : * single-member EquivalenceClass for it.
560 : *
561 : * sortref is the SortGroupRef of the originating SortGroupClause, if any,
562 : * or zero if not. (It should never be zero if the expression is volatile!)
563 : *
564 : * If rel is not NULL, it identifies a specific relation we're considering
565 : * a path for, and indicates that child EC members for that relation can be
566 : * considered. Otherwise child members are ignored. (Note: since child EC
567 : * members aren't guaranteed unique, a non-NULL value means that there could
568 : * be more than one EC that matches the expression; if so it's order-dependent
569 : * which one you get. This is annoying but it only happens in corner cases,
570 : * so for now we live with just reporting the first match. See also
571 : * generate_implied_equalities_for_column and match_pathkeys_to_index.)
572 : *
573 : * If create_it is true, we'll build a new EquivalenceClass when there is no
574 : * match. If create_it is false, we just return NULL when no match.
575 : *
576 : * This can be used safely both before and after EquivalenceClass merging;
577 : * since it never causes merging it does not invalidate any existing ECs
578 : * or PathKeys. However, ECs added after path generation has begun are
579 : * of limited usefulness, so usually it's best to create them beforehand.
580 : *
581 : * Note: opfamilies must be chosen consistently with the way
582 : * process_equivalence() would do; that is, generated from a mergejoinable
583 : * equality operator. Else we might fail to detect valid equivalences,
584 : * generating poor (but not incorrect) plans.
585 : */
586 : EquivalenceClass *
587 1429280 : get_eclass_for_sort_expr(PlannerInfo *root,
588 : Expr *expr,
589 : List *opfamilies,
590 : Oid opcintype,
591 : Oid collation,
592 : Index sortref,
593 : Relids rel,
594 : bool create_it)
595 : {
596 : JoinDomain *jdomain;
597 : Relids expr_relids;
598 : EquivalenceClass *newec;
599 : EquivalenceMember *newem;
600 : ListCell *lc1;
601 : MemoryContext oldcontext;
602 :
603 : /*
604 : * Ensure the expression exposes the correct type and collation.
605 : */
606 1429280 : expr = canonicalize_ec_expression(expr, opcintype, collation);
607 :
608 : /*
609 : * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
610 : * BY, etc), they can be presumed to belong to the top JoinDomain.
611 : */
612 1429280 : jdomain = linitial_node(JoinDomain, root->join_domains);
613 :
614 : /*
615 : * Scan through the existing EquivalenceClasses for a match
616 : */
617 4639838 : foreach(lc1, root->eq_classes)
618 : {
619 3992670 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
620 : ListCell *lc2;
621 :
622 : /*
623 : * Never match to a volatile EC, except when we are looking at another
624 : * reference to the same volatile SortGroupClause.
625 : */
626 3992670 : if (cur_ec->ec_has_volatile &&
627 36 : (sortref == 0 || sortref != cur_ec->ec_sortref))
628 404 : continue;
629 :
630 3992266 : if (collation != cur_ec->ec_collation)
631 1031914 : continue;
632 2960352 : if (!equal(opfamilies, cur_ec->ec_opfamilies))
633 551126 : continue;
634 :
635 5490602 : foreach(lc2, cur_ec->ec_members)
636 : {
637 3863488 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
638 :
639 : /*
640 : * Ignore child members unless they match the request.
641 : */
642 3863488 : if (cur_em->em_is_child &&
643 210012 : !bms_equal(cur_em->em_relids, rel))
644 172700 : continue;
645 :
646 : /*
647 : * Match constants only within the same JoinDomain (see
648 : * optimizer/README).
649 : */
650 3690788 : if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
651 65460 : continue;
652 :
653 7221560 : if (opcintype == cur_em->em_datatype &&
654 3596232 : equal(expr, cur_em->em_expr))
655 782112 : return cur_ec; /* Match! */
656 : }
657 : }
658 :
659 : /* No match; does caller want a NULL result? */
660 647168 : if (!create_it)
661 483060 : return NULL;
662 :
663 : /*
664 : * OK, build a new single-member EC
665 : *
666 : * Here, we must be sure that we construct the EC in the right context.
667 : */
668 164108 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
669 :
670 164108 : newec = makeNode(EquivalenceClass);
671 164108 : newec->ec_opfamilies = list_copy(opfamilies);
672 164108 : newec->ec_collation = collation;
673 164108 : newec->ec_members = NIL;
674 164108 : newec->ec_sources = NIL;
675 164108 : newec->ec_derives = NIL;
676 164108 : newec->ec_relids = NULL;
677 164108 : newec->ec_has_const = false;
678 164108 : newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
679 164108 : newec->ec_broken = false;
680 164108 : newec->ec_sortref = sortref;
681 164108 : newec->ec_min_security = UINT_MAX;
682 164108 : newec->ec_max_security = 0;
683 164108 : newec->ec_merged = NULL;
684 :
685 164108 : if (newec->ec_has_volatile && sortref == 0) /* should not happen */
686 0 : elog(ERROR, "volatile EquivalenceClass has no sortref");
687 :
688 : /*
689 : * Get the precise set of relids appearing in the expression.
690 : */
691 164108 : expr_relids = pull_varnos(root, (Node *) expr);
692 :
693 164108 : newem = add_eq_member(newec, copyObject(expr), expr_relids,
694 : jdomain, NULL, opcintype);
695 :
696 : /*
697 : * add_eq_member doesn't check for volatile functions, set-returning
698 : * functions, aggregates, or window functions, but such could appear in
699 : * sort expressions; so we have to check whether its const-marking was
700 : * correct.
701 : */
702 164108 : if (newec->ec_has_const)
703 : {
704 2776 : if (newec->ec_has_volatile ||
705 2570 : expression_returns_set((Node *) expr) ||
706 2256 : contain_agg_clause((Node *) expr) ||
707 1040 : contain_window_function((Node *) expr))
708 : {
709 388 : newec->ec_has_const = false;
710 388 : newem->em_is_const = false;
711 : }
712 : }
713 :
714 164108 : root->eq_classes = lappend(root->eq_classes, newec);
715 :
716 : /*
717 : * If EC merging is already complete, we have to mop up by adding the new
718 : * EC to the eclass_indexes of the relation(s) mentioned in it.
719 : */
720 164108 : if (root->ec_merging_done)
721 : {
722 79074 : int ec_index = list_length(root->eq_classes) - 1;
723 79074 : int i = -1;
724 :
725 159756 : while ((i = bms_next_member(newec->ec_relids, i)) > 0)
726 : {
727 80682 : RelOptInfo *rel = root->simple_rel_array[i];
728 :
729 80682 : if (rel == NULL) /* must be an outer join */
730 : {
731 : Assert(bms_is_member(i, root->outer_join_rels));
732 5332 : continue;
733 : }
734 :
735 : Assert(rel->reloptkind == RELOPT_BASEREL);
736 :
737 75350 : rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
738 : ec_index);
739 : }
740 : }
741 :
742 164108 : MemoryContextSwitchTo(oldcontext);
743 :
744 164108 : return newec;
745 : }
746 :
747 : /*
748 : * find_ec_member_matching_expr
749 : * Locate an EquivalenceClass member matching the given expr, if any;
750 : * return NULL if no match.
751 : *
752 : * "Matching" is defined as "equal after stripping RelabelTypes".
753 : * This is used for identifying sort expressions, and we need to allow
754 : * binary-compatible relabeling for some cases involving binary-compatible
755 : * sort operators.
756 : *
757 : * Child EC members are ignored unless they belong to given 'relids'.
758 : */
759 : EquivalenceMember *
760 206908 : find_ec_member_matching_expr(EquivalenceClass *ec,
761 : Expr *expr,
762 : Relids relids)
763 : {
764 : ListCell *lc;
765 :
766 : /* We ignore binary-compatible relabeling on both ends */
767 224786 : while (expr && IsA(expr, RelabelType))
768 17878 : expr = ((RelabelType *) expr)->arg;
769 :
770 420752 : foreach(lc, ec->ec_members)
771 : {
772 305134 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
773 : Expr *emexpr;
774 :
775 : /*
776 : * We shouldn't be trying to sort by an equivalence class that
777 : * contains a constant, so no need to consider such cases any further.
778 : */
779 305134 : if (em->em_is_const)
780 0 : continue;
781 :
782 : /*
783 : * Ignore child members unless they belong to the requested rel.
784 : */
785 305134 : if (em->em_is_child &&
786 83066 : !bms_is_subset(em->em_relids, relids))
787 77584 : continue;
788 :
789 : /*
790 : * Match if same expression (after stripping relabel).
791 : */
792 227550 : emexpr = em->em_expr;
793 231908 : while (emexpr && IsA(emexpr, RelabelType))
794 4358 : emexpr = ((RelabelType *) emexpr)->arg;
795 :
796 227550 : if (equal(emexpr, expr))
797 91290 : return em;
798 : }
799 :
800 115618 : return NULL;
801 : }
802 :
803 : /*
804 : * find_computable_ec_member
805 : * Locate an EquivalenceClass member that can be computed from the
806 : * expressions appearing in "exprs"; return NULL if no match.
807 : *
808 : * "exprs" can be either a list of bare expression trees, or a list of
809 : * TargetEntry nodes. Either way, it should contain Vars and possibly
810 : * Aggrefs and WindowFuncs, which are matched to the corresponding elements
811 : * of the EquivalenceClass's expressions.
812 : *
813 : * Unlike find_ec_member_matching_expr, there's no special provision here
814 : * for binary-compatible relabeling. This is intentional: if we have to
815 : * compute an expression in this way, setrefs.c is going to insist on exact
816 : * matches of Vars to the source tlist.
817 : *
818 : * Child EC members are ignored unless they belong to given 'relids'.
819 : * Also, non-parallel-safe expressions are ignored if 'require_parallel_safe'.
820 : *
821 : * Note: some callers pass root == NULL for notational reasons. This is OK
822 : * when require_parallel_safe is false.
823 : */
824 : EquivalenceMember *
825 2270 : find_computable_ec_member(PlannerInfo *root,
826 : EquivalenceClass *ec,
827 : List *exprs,
828 : Relids relids,
829 : bool require_parallel_safe)
830 : {
831 : ListCell *lc;
832 :
833 7274 : foreach(lc, ec->ec_members)
834 : {
835 5420 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
836 : List *exprvars;
837 : ListCell *lc2;
838 :
839 : /*
840 : * We shouldn't be trying to sort by an equivalence class that
841 : * contains a constant, so no need to consider such cases any further.
842 : */
843 5420 : if (em->em_is_const)
844 0 : continue;
845 :
846 : /*
847 : * Ignore child members unless they belong to the requested rel.
848 : */
849 5420 : if (em->em_is_child &&
850 2934 : !bms_is_subset(em->em_relids, relids))
851 2766 : continue;
852 :
853 : /*
854 : * Match if all Vars and quasi-Vars are available in "exprs".
855 : */
856 2654 : exprvars = pull_var_clause((Node *) em->em_expr,
857 : PVC_INCLUDE_AGGREGATES |
858 : PVC_INCLUDE_WINDOWFUNCS |
859 : PVC_INCLUDE_PLACEHOLDERS);
860 3222 : foreach(lc2, exprvars)
861 : {
862 2782 : if (!is_exprlist_member(lfirst(lc2), exprs))
863 2214 : break;
864 : }
865 2654 : list_free(exprvars);
866 2654 : if (lc2)
867 2214 : continue; /* we hit a non-available Var */
868 :
869 : /*
870 : * If requested, reject expressions that are not parallel-safe. We
871 : * check this last because it's a rather expensive test.
872 : */
873 440 : if (require_parallel_safe &&
874 122 : !is_parallel_safe(root, (Node *) em->em_expr))
875 24 : continue;
876 :
877 416 : return em; /* found usable expression */
878 : }
879 :
880 1854 : return NULL;
881 : }
882 :
883 : /*
884 : * is_exprlist_member
885 : * Subroutine for find_computable_ec_member: is "node" in "exprs"?
886 : *
887 : * Per the requirements of that function, "exprs" might or might not have
888 : * TargetEntry superstructure.
889 : */
890 : static bool
891 2782 : is_exprlist_member(Expr *node, List *exprs)
892 : {
893 : ListCell *lc;
894 :
895 7836 : foreach(lc, exprs)
896 : {
897 5622 : Expr *expr = (Expr *) lfirst(lc);
898 :
899 5622 : if (expr && IsA(expr, TargetEntry))
900 1128 : expr = ((TargetEntry *) expr)->expr;
901 :
902 5622 : if (equal(node, expr))
903 568 : return true;
904 : }
905 2214 : return false;
906 : }
907 :
908 : /*
909 : * relation_can_be_sorted_early
910 : * Can this relation be sorted on this EC before the final output step?
911 : *
912 : * To succeed, we must find an EC member that prepare_sort_from_pathkeys knows
913 : * how to sort on, given the rel's reltarget as input. There are also a few
914 : * additional constraints based on the fact that the desired sort will be done
915 : * "early", within the scan/join part of the plan. Also, non-parallel-safe
916 : * expressions are ignored if 'require_parallel_safe'.
917 : *
918 : * At some point we might want to return the identified EquivalenceMember,
919 : * but for now, callers only want to know if there is one.
920 : */
921 : bool
922 9366 : relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel,
923 : EquivalenceClass *ec, bool require_parallel_safe)
924 : {
925 9366 : PathTarget *target = rel->reltarget;
926 : EquivalenceMember *em;
927 : ListCell *lc;
928 :
929 : /*
930 : * Reject volatile ECs immediately; such sorts must always be postponed.
931 : */
932 9366 : if (ec->ec_has_volatile)
933 42 : return false;
934 :
935 : /*
936 : * Try to find an EM directly matching some reltarget member.
937 : */
938 19078 : foreach(lc, target->exprs)
939 : {
940 17126 : Expr *targetexpr = (Expr *) lfirst(lc);
941 :
942 17126 : em = find_ec_member_matching_expr(ec, targetexpr, rel->relids);
943 17126 : if (!em)
944 9754 : continue;
945 :
946 : /*
947 : * Reject expressions involving set-returning functions, as those
948 : * can't be computed early either. (Note: this test and the following
949 : * one are effectively checking properties of targetexpr, so there's
950 : * no point in asking whether some other EC member would be better.)
951 : */
952 7372 : if (expression_returns_set((Node *) em->em_expr))
953 0 : continue;
954 :
955 : /*
956 : * If requested, reject expressions that are not parallel-safe. We
957 : * check this last because it's a rather expensive test.
958 : */
959 7372 : if (require_parallel_safe &&
960 7372 : !is_parallel_safe(root, (Node *) em->em_expr))
961 0 : continue;
962 :
963 7372 : return true;
964 : }
965 :
966 : /*
967 : * Try to find an expression computable from the reltarget.
968 : */
969 1952 : em = find_computable_ec_member(root, ec, target->exprs, rel->relids,
970 : require_parallel_safe);
971 1952 : if (!em)
972 1854 : return false;
973 :
974 : /*
975 : * Reject expressions involving set-returning functions, as those can't be
976 : * computed early either. (There's no point in looking for another EC
977 : * member in this case; since SRFs can't appear in WHERE, they cannot
978 : * belong to multi-member ECs.)
979 : */
980 98 : if (expression_returns_set((Node *) em->em_expr))
981 12 : return false;
982 :
983 86 : return true;
984 : }
985 :
986 : /*
987 : * generate_base_implied_equalities
988 : * Generate any restriction clauses that we can deduce from equivalence
989 : * classes.
990 : *
991 : * When an EC contains pseudoconstants, our strategy is to generate
992 : * "member = const1" clauses where const1 is the first constant member, for
993 : * every other member (including other constants). If we are able to do this
994 : * then we don't need any "var = var" comparisons because we've successfully
995 : * constrained all the vars at their points of creation. If we fail to
996 : * generate any of these clauses due to lack of cross-type operators, we fall
997 : * back to the "ec_broken" strategy described below. (XXX if there are
998 : * multiple constants of different types, it's possible that we might succeed
999 : * in forming all the required clauses if we started from a different const
1000 : * member; but this seems a sufficiently hokey corner case to not be worth
1001 : * spending lots of cycles on.)
1002 : *
1003 : * For ECs that contain no pseudoconstants, we generate derived clauses
1004 : * "member1 = member2" for each pair of members belonging to the same base
1005 : * relation (actually, if there are more than two for the same base relation,
1006 : * we only need enough clauses to link each to each other). This provides
1007 : * the base case for the recursion: each row emitted by a base relation scan
1008 : * will constrain all computable members of the EC to be equal. As each
1009 : * join path is formed, we'll add additional derived clauses on-the-fly
1010 : * to maintain this invariant (see generate_join_implied_equalities).
1011 : *
1012 : * If the opfamilies used by the EC do not provide complete sets of cross-type
1013 : * equality operators, it is possible that we will fail to generate a clause
1014 : * that must be generated to maintain the invariant. (An example: given
1015 : * "WHERE a.x = b.y AND b.y = a.z", the scheme breaks down if we cannot
1016 : * generate "a.x = a.z" as a restriction clause for A.) In this case we mark
1017 : * the EC "ec_broken" and fall back to regurgitating its original source
1018 : * RestrictInfos at appropriate times. We do not try to retract any derived
1019 : * clauses already generated from the broken EC, so the resulting plan could
1020 : * be poor due to bad selectivity estimates caused by redundant clauses. But
1021 : * the correct solution to that is to fix the opfamilies ...
1022 : *
1023 : * Equality clauses derived by this function are passed off to
1024 : * process_implied_equality (in plan/initsplan.c) to be inserted into the
1025 : * restrictinfo datastructures. Note that this must be called after initial
1026 : * scanning of the quals and before Path construction begins.
1027 : *
1028 : * We make no attempt to avoid generating duplicate RestrictInfos here: we
1029 : * don't search ec_sources or ec_derives for matches. It doesn't really
1030 : * seem worth the trouble to do so.
1031 : */
1032 : void
1033 257456 : generate_base_implied_equalities(PlannerInfo *root)
1034 : {
1035 : int ec_index;
1036 : ListCell *lc;
1037 :
1038 : /*
1039 : * At this point, we're done absorbing knowledge of equivalences in the
1040 : * query, so no further EC merging should happen, and ECs remaining in the
1041 : * eq_classes list can be considered canonical. (But note that it's still
1042 : * possible for new single-member ECs to be added through
1043 : * get_eclass_for_sort_expr().)
1044 : */
1045 257456 : root->ec_merging_done = true;
1046 :
1047 257456 : ec_index = 0;
1048 551778 : foreach(lc, root->eq_classes)
1049 : {
1050 294322 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
1051 294322 : bool can_generate_joinclause = false;
1052 : int i;
1053 :
1054 : Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
1055 : Assert(!ec->ec_broken); /* not yet anyway... */
1056 :
1057 : /*
1058 : * Generate implied equalities that are restriction clauses.
1059 : * Single-member ECs won't generate any deductions, either here or at
1060 : * the join level.
1061 : */
1062 294322 : if (list_length(ec->ec_members) > 1)
1063 : {
1064 210734 : if (ec->ec_has_const)
1065 165656 : generate_base_implied_equalities_const(root, ec);
1066 : else
1067 45078 : generate_base_implied_equalities_no_const(root, ec);
1068 :
1069 : /* Recover if we failed to generate required derived clauses */
1070 210734 : if (ec->ec_broken)
1071 30 : generate_base_implied_equalities_broken(root, ec);
1072 :
1073 : /* Detect whether this EC might generate join clauses */
1074 210734 : can_generate_joinclause =
1075 210734 : (bms_membership(ec->ec_relids) == BMS_MULTIPLE);
1076 : }
1077 :
1078 : /*
1079 : * Mark the base rels cited in each eclass (which should all exist by
1080 : * now) with the eq_classes indexes of all eclasses mentioning them.
1081 : * This will let us avoid searching in subsequent lookups. While
1082 : * we're at it, we can mark base rels that have pending eclass joins;
1083 : * this is a cheap version of has_relevant_eclass_joinclause().
1084 : */
1085 294322 : i = -1;
1086 654258 : while ((i = bms_next_member(ec->ec_relids, i)) > 0)
1087 : {
1088 359936 : RelOptInfo *rel = root->simple_rel_array[i];
1089 :
1090 359936 : if (rel == NULL) /* must be an outer join */
1091 : {
1092 : Assert(bms_is_member(i, root->outer_join_rels));
1093 4900 : continue;
1094 : }
1095 :
1096 : Assert(rel->reloptkind == RELOPT_BASEREL);
1097 :
1098 355036 : rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
1099 : ec_index);
1100 :
1101 355036 : if (can_generate_joinclause)
1102 121364 : rel->has_eclass_joins = true;
1103 : }
1104 :
1105 294322 : ec_index++;
1106 : }
1107 257456 : }
1108 :
1109 : /*
1110 : * generate_base_implied_equalities when EC contains pseudoconstant(s)
1111 : */
1112 : static void
1113 165656 : generate_base_implied_equalities_const(PlannerInfo *root,
1114 : EquivalenceClass *ec)
1115 : {
1116 165656 : EquivalenceMember *const_em = NULL;
1117 : ListCell *lc;
1118 :
1119 : /*
1120 : * In the trivial case where we just had one "var = const" clause, push
1121 : * the original clause back into the main planner machinery. There is
1122 : * nothing to be gained by doing it differently, and we save the effort to
1123 : * re-build and re-analyze an equality clause that will be exactly
1124 : * equivalent to the old one.
1125 : */
1126 314842 : if (list_length(ec->ec_members) == 2 &&
1127 149186 : list_length(ec->ec_sources) == 1)
1128 : {
1129 149186 : RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
1130 :
1131 149186 : distribute_restrictinfo_to_rels(root, restrictinfo);
1132 149186 : return;
1133 : }
1134 :
1135 : /*
1136 : * Find the constant member to use. We prefer an actual constant to
1137 : * pseudo-constants (such as Params), because the constraint exclusion
1138 : * machinery might be able to exclude relations on the basis of generated
1139 : * "var = const" equalities, but "var = param" won't work for that.
1140 : */
1141 36656 : foreach(lc, ec->ec_members)
1142 : {
1143 36606 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
1144 :
1145 36606 : if (cur_em->em_is_const)
1146 : {
1147 16476 : const_em = cur_em;
1148 16476 : if (IsA(cur_em->em_expr, Const))
1149 16420 : break;
1150 : }
1151 : }
1152 : Assert(const_em != NULL);
1153 :
1154 : /* Generate a derived equality against each other member */
1155 66000 : foreach(lc, ec->ec_members)
1156 : {
1157 49560 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
1158 : Oid eq_op;
1159 : RestrictInfo *rinfo;
1160 :
1161 : Assert(!cur_em->em_is_child); /* no children yet */
1162 49560 : if (cur_em == const_em)
1163 16446 : continue;
1164 33114 : eq_op = select_equality_operator(ec,
1165 : cur_em->em_datatype,
1166 : const_em->em_datatype);
1167 33114 : if (!OidIsValid(eq_op))
1168 : {
1169 : /* failed... */
1170 30 : ec->ec_broken = true;
1171 30 : break;
1172 : }
1173 :
1174 : /*
1175 : * We use the constant's em_jdomain as qualscope, so that if the
1176 : * generated clause is variable-free (i.e, both EMs are consts) it
1177 : * will be enforced at the join domain level.
1178 : */
1179 33084 : rinfo = process_implied_equality(root, eq_op, ec->ec_collation,
1180 : cur_em->em_expr, const_em->em_expr,
1181 33084 : const_em->em_jdomain->jd_relids,
1182 : ec->ec_min_security,
1183 33084 : cur_em->em_is_const);
1184 :
1185 : /*
1186 : * If the clause didn't degenerate to a constant, fill in the correct
1187 : * markings for a mergejoinable clause, and save it in ec_derives. (We
1188 : * will not re-use such clauses directly, but selectivity estimation
1189 : * may consult the list later. Note that this use of ec_derives does
1190 : * not overlap with its use for join clauses, since we never generate
1191 : * join clauses from an ec_has_const eclass.)
1192 : */
1193 33084 : if (rinfo && rinfo->mergeopfamilies)
1194 : {
1195 : /* it's not redundant, so don't set parent_ec */
1196 32952 : rinfo->left_ec = rinfo->right_ec = ec;
1197 32952 : rinfo->left_em = cur_em;
1198 32952 : rinfo->right_em = const_em;
1199 32952 : ec->ec_derives = lappend(ec->ec_derives, rinfo);
1200 : }
1201 : }
1202 : }
1203 :
1204 : /*
1205 : * generate_base_implied_equalities when EC contains no pseudoconstants
1206 : */
1207 : static void
1208 45078 : generate_base_implied_equalities_no_const(PlannerInfo *root,
1209 : EquivalenceClass *ec)
1210 : {
1211 : EquivalenceMember **prev_ems;
1212 : ListCell *lc;
1213 :
1214 : /*
1215 : * We scan the EC members once and track the last-seen member for each
1216 : * base relation. When we see another member of the same base relation,
1217 : * we generate "prev_em = cur_em". This results in the minimum number of
1218 : * derived clauses, but it's possible that it will fail when a different
1219 : * ordering would succeed. XXX FIXME: use a UNION-FIND algorithm similar
1220 : * to the way we build merged ECs. (Use a list-of-lists for each rel.)
1221 : */
1222 : prev_ems = (EquivalenceMember **)
1223 45078 : palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *));
1224 :
1225 136364 : foreach(lc, ec->ec_members)
1226 : {
1227 91286 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
1228 : int relid;
1229 :
1230 : Assert(!cur_em->em_is_child); /* no children yet */
1231 91286 : if (!bms_get_singleton_member(cur_em->em_relids, &relid))
1232 180 : continue;
1233 : Assert(relid < root->simple_rel_array_size);
1234 :
1235 91106 : if (prev_ems[relid] != NULL)
1236 : {
1237 268 : EquivalenceMember *prev_em = prev_ems[relid];
1238 : Oid eq_op;
1239 : RestrictInfo *rinfo;
1240 :
1241 268 : eq_op = select_equality_operator(ec,
1242 : prev_em->em_datatype,
1243 : cur_em->em_datatype);
1244 268 : if (!OidIsValid(eq_op))
1245 : {
1246 : /* failed... */
1247 0 : ec->ec_broken = true;
1248 0 : break;
1249 : }
1250 :
1251 : /*
1252 : * The expressions aren't constants, so the passed qualscope will
1253 : * never be used to place the generated clause. We just need to
1254 : * be sure it covers both expressions, which em_relids should do.
1255 : */
1256 268 : rinfo = process_implied_equality(root, eq_op, ec->ec_collation,
1257 : prev_em->em_expr, cur_em->em_expr,
1258 : cur_em->em_relids,
1259 : ec->ec_min_security,
1260 : false);
1261 :
1262 : /*
1263 : * If the clause didn't degenerate to a constant, fill in the
1264 : * correct markings for a mergejoinable clause. We don't put it
1265 : * in ec_derives however; we don't currently need to re-find such
1266 : * clauses, and we don't want to clutter that list with non-join
1267 : * clauses.
1268 : */
1269 268 : if (rinfo && rinfo->mergeopfamilies)
1270 : {
1271 : /* it's not redundant, so don't set parent_ec */
1272 268 : rinfo->left_ec = rinfo->right_ec = ec;
1273 268 : rinfo->left_em = prev_em;
1274 268 : rinfo->right_em = cur_em;
1275 : }
1276 : }
1277 91106 : prev_ems[relid] = cur_em;
1278 : }
1279 :
1280 45078 : pfree(prev_ems);
1281 :
1282 : /*
1283 : * We also have to make sure that all the Vars used in the member clauses
1284 : * will be available at any join node we might try to reference them at.
1285 : * For the moment we force all the Vars to be available at all join nodes
1286 : * for this eclass. Perhaps this could be improved by doing some
1287 : * pre-analysis of which members we prefer to join, but it's no worse than
1288 : * what happened in the pre-8.3 code.
1289 : */
1290 136364 : foreach(lc, ec->ec_members)
1291 : {
1292 91286 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
1293 91286 : List *vars = pull_var_clause((Node *) cur_em->em_expr,
1294 : PVC_RECURSE_AGGREGATES |
1295 : PVC_RECURSE_WINDOWFUNCS |
1296 : PVC_INCLUDE_PLACEHOLDERS);
1297 :
1298 91286 : add_vars_to_targetlist(root, vars, ec->ec_relids);
1299 91286 : list_free(vars);
1300 : }
1301 45078 : }
1302 :
1303 : /*
1304 : * generate_base_implied_equalities cleanup after failure
1305 : *
1306 : * What we must do here is push any zero- or one-relation source RestrictInfos
1307 : * of the EC back into the main restrictinfo datastructures. Multi-relation
1308 : * clauses will be regurgitated later by generate_join_implied_equalities().
1309 : * (We do it this way to maintain continuity with the case that ec_broken
1310 : * becomes set only after we've gone up a join level or two.) However, for
1311 : * an EC that contains constants, we can adopt a simpler strategy and just
1312 : * throw back all the source RestrictInfos immediately; that works because
1313 : * we know that such an EC can't become broken later. (This rule justifies
1314 : * ignoring ec_has_const ECs in generate_join_implied_equalities, even when
1315 : * they are broken.)
1316 : */
1317 : static void
1318 30 : generate_base_implied_equalities_broken(PlannerInfo *root,
1319 : EquivalenceClass *ec)
1320 : {
1321 : ListCell *lc;
1322 :
1323 96 : foreach(lc, ec->ec_sources)
1324 : {
1325 66 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1326 :
1327 66 : if (ec->ec_has_const ||
1328 0 : bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
1329 66 : distribute_restrictinfo_to_rels(root, restrictinfo);
1330 : }
1331 30 : }
1332 :
1333 :
1334 : /*
1335 : * generate_join_implied_equalities
1336 : * Generate any join clauses that we can deduce from equivalence classes.
1337 : *
1338 : * At a join node, we must enforce restriction clauses sufficient to ensure
1339 : * that all equivalence-class members computable at that node are equal.
1340 : * Since the set of clauses to enforce can vary depending on which subset
1341 : * relations are the inputs, we have to compute this afresh for each join
1342 : * relation pair. Hence a fresh List of RestrictInfo nodes is built and
1343 : * passed back on each call.
1344 : *
1345 : * In addition to its use at join nodes, this can be applied to generate
1346 : * eclass-based join clauses for use in a parameterized scan of a base rel.
1347 : * The reason for the asymmetry of specifying the inner rel as a RelOptInfo
1348 : * and the outer rel by Relids is that this usage occurs before we have
1349 : * built any join RelOptInfos.
1350 : *
1351 : * An annoying special case for parameterized scans is that the inner rel can
1352 : * be an appendrel child (an "other rel"). In this case we must generate
1353 : * appropriate clauses using child EC members. add_child_rel_equivalences
1354 : * must already have been done for the child rel.
1355 : *
1356 : * The results are sufficient for use in merge, hash, and plain nestloop join
1357 : * methods. We do not worry here about selecting clauses that are optimal
1358 : * for use in a parameterized indexscan. indxpath.c makes its own selections
1359 : * of clauses to use, and if the ones we pick here are redundant with those,
1360 : * the extras will be eliminated at createplan time, using the parent_ec
1361 : * markers that we provide (see is_redundant_derived_clause()).
1362 : *
1363 : * Because the same join clauses are likely to be needed multiple times as
1364 : * we consider different join paths, we avoid generating multiple copies:
1365 : * whenever we select a particular pair of EquivalenceMembers to join,
1366 : * we check to see if the pair matches any original clause (in ec_sources)
1367 : * or previously-built clause (in ec_derives). This saves memory and allows
1368 : * re-use of information cached in RestrictInfos. We also avoid generating
1369 : * commutative duplicates, i.e. if the algorithm selects "a.x = b.y" but
1370 : * we already have "b.y = a.x", we return the existing clause.
1371 : *
1372 : * If we are considering an outer join, sjinfo is the associated OJ info,
1373 : * otherwise it can be NULL.
1374 : *
1375 : * join_relids should always equal bms_union(outer_relids, inner_rel->relids)
1376 : * plus whatever add_outer_joins_to_relids() would add. We could simplify
1377 : * this function's API by computing it internally, but most callers have the
1378 : * value at hand anyway.
1379 : */
1380 : List *
1381 388088 : generate_join_implied_equalities(PlannerInfo *root,
1382 : Relids join_relids,
1383 : Relids outer_relids,
1384 : RelOptInfo *inner_rel,
1385 : SpecialJoinInfo *sjinfo)
1386 : {
1387 388088 : List *result = NIL;
1388 388088 : Relids inner_relids = inner_rel->relids;
1389 : Relids nominal_inner_relids;
1390 : Relids nominal_join_relids;
1391 : Bitmapset *matching_ecs;
1392 : int i;
1393 :
1394 : /* If inner rel is a child, extra setup work is needed */
1395 388088 : if (IS_OTHER_REL(inner_rel))
1396 : {
1397 : Assert(!bms_is_empty(inner_rel->top_parent_relids));
1398 :
1399 : /* Fetch relid set for the topmost parent rel */
1400 6652 : nominal_inner_relids = inner_rel->top_parent_relids;
1401 : /* ECs will be marked with the parent's relid, not the child's */
1402 6652 : nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1403 6652 : nominal_join_relids = add_outer_joins_to_relids(root,
1404 : nominal_join_relids,
1405 : sjinfo,
1406 : NULL);
1407 : }
1408 : else
1409 : {
1410 381436 : nominal_inner_relids = inner_relids;
1411 381436 : nominal_join_relids = join_relids;
1412 : }
1413 :
1414 : /*
1415 : * Examine all potentially-relevant eclasses.
1416 : *
1417 : * If we are considering an outer join, we must include "join" clauses
1418 : * that mention either input rel plus the outer join's relid; these
1419 : * represent post-join filter clauses that have to be applied at this
1420 : * join. We don't have infrastructure that would let us identify such
1421 : * eclasses cheaply, so just fall back to considering all eclasses
1422 : * mentioning anything in nominal_join_relids.
1423 : *
1424 : * At inner joins, we can be smarter: only consider eclasses mentioning
1425 : * both input rels.
1426 : */
1427 388088 : if (sjinfo && sjinfo->ojrelid != 0)
1428 82920 : matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids);
1429 : else
1430 305168 : matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
1431 : outer_relids);
1432 :
1433 388088 : i = -1;
1434 1124188 : while ((i = bms_next_member(matching_ecs, i)) >= 0)
1435 : {
1436 736100 : EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
1437 736100 : List *sublist = NIL;
1438 :
1439 : /* ECs containing consts do not need any further enforcement */
1440 736100 : if (ec->ec_has_const)
1441 106772 : continue;
1442 :
1443 : /* Single-member ECs won't generate any deductions */
1444 629328 : if (list_length(ec->ec_members) <= 1)
1445 377526 : continue;
1446 :
1447 : /* Sanity check that this eclass overlaps the join */
1448 : Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1449 :
1450 251802 : if (!ec->ec_broken)
1451 251478 : sublist = generate_join_implied_equalities_normal(root,
1452 : ec,
1453 : join_relids,
1454 : outer_relids,
1455 : inner_relids);
1456 :
1457 : /* Recover if we failed to generate required derived clauses */
1458 251802 : if (ec->ec_broken)
1459 360 : sublist = generate_join_implied_equalities_broken(root,
1460 : ec,
1461 : nominal_join_relids,
1462 : outer_relids,
1463 : nominal_inner_relids,
1464 : inner_rel);
1465 :
1466 251802 : result = list_concat(result, sublist);
1467 : }
1468 :
1469 388088 : return result;
1470 : }
1471 :
1472 : /*
1473 : * generate_join_implied_equalities_for_ecs
1474 : * As above, but consider only the listed ECs.
1475 : *
1476 : * For the sole current caller, we can assume sjinfo == NULL, that is we are
1477 : * not interested in outer-join filter clauses. This might need to change
1478 : * in future.
1479 : */
1480 : List *
1481 704 : generate_join_implied_equalities_for_ecs(PlannerInfo *root,
1482 : List *eclasses,
1483 : Relids join_relids,
1484 : Relids outer_relids,
1485 : RelOptInfo *inner_rel)
1486 : {
1487 704 : List *result = NIL;
1488 704 : Relids inner_relids = inner_rel->relids;
1489 : Relids nominal_inner_relids;
1490 : Relids nominal_join_relids;
1491 : ListCell *lc;
1492 :
1493 : /* If inner rel is a child, extra setup work is needed */
1494 704 : if (IS_OTHER_REL(inner_rel))
1495 : {
1496 : Assert(!bms_is_empty(inner_rel->top_parent_relids));
1497 :
1498 : /* Fetch relid set for the topmost parent rel */
1499 0 : nominal_inner_relids = inner_rel->top_parent_relids;
1500 : /* ECs will be marked with the parent's relid, not the child's */
1501 0 : nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1502 : }
1503 : else
1504 : {
1505 704 : nominal_inner_relids = inner_relids;
1506 704 : nominal_join_relids = join_relids;
1507 : }
1508 :
1509 1438 : foreach(lc, eclasses)
1510 : {
1511 734 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
1512 734 : List *sublist = NIL;
1513 :
1514 : /* ECs containing consts do not need any further enforcement */
1515 734 : if (ec->ec_has_const)
1516 0 : continue;
1517 :
1518 : /* Single-member ECs won't generate any deductions */
1519 734 : if (list_length(ec->ec_members) <= 1)
1520 0 : continue;
1521 :
1522 : /* We can quickly ignore any that don't overlap the join, too */
1523 734 : if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1524 0 : continue;
1525 :
1526 734 : if (!ec->ec_broken)
1527 734 : sublist = generate_join_implied_equalities_normal(root,
1528 : ec,
1529 : join_relids,
1530 : outer_relids,
1531 : inner_relids);
1532 :
1533 : /* Recover if we failed to generate required derived clauses */
1534 734 : if (ec->ec_broken)
1535 0 : sublist = generate_join_implied_equalities_broken(root,
1536 : ec,
1537 : nominal_join_relids,
1538 : outer_relids,
1539 : nominal_inner_relids,
1540 : inner_rel);
1541 :
1542 734 : result = list_concat(result, sublist);
1543 : }
1544 :
1545 704 : return result;
1546 : }
1547 :
1548 : /*
1549 : * generate_join_implied_equalities for a still-valid EC
1550 : */
1551 : static List *
1552 252212 : generate_join_implied_equalities_normal(PlannerInfo *root,
1553 : EquivalenceClass *ec,
1554 : Relids join_relids,
1555 : Relids outer_relids,
1556 : Relids inner_relids)
1557 : {
1558 252212 : List *result = NIL;
1559 252212 : List *new_members = NIL;
1560 252212 : List *outer_members = NIL;
1561 252212 : List *inner_members = NIL;
1562 : ListCell *lc1;
1563 :
1564 : /*
1565 : * First, scan the EC to identify member values that are computable at the
1566 : * outer rel, at the inner rel, or at this relation but not in either
1567 : * input rel. The outer-rel members should already be enforced equal,
1568 : * likewise for the inner-rel members. We'll need to create clauses to
1569 : * enforce that any newly computable members are all equal to each other
1570 : * as well as to at least one input member, plus enforce at least one
1571 : * outer-rel member equal to at least one inner-rel member.
1572 : */
1573 862186 : foreach(lc1, ec->ec_members)
1574 : {
1575 609974 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
1576 :
1577 : /*
1578 : * We don't need to check explicitly for child EC members. This test
1579 : * against join_relids will cause them to be ignored except when
1580 : * considering a child inner rel, which is what we want.
1581 : */
1582 609974 : if (!bms_is_subset(cur_em->em_relids, join_relids))
1583 108068 : continue; /* not computable yet, or wrong child */
1584 :
1585 501906 : if (bms_is_subset(cur_em->em_relids, outer_relids))
1586 288518 : outer_members = lappend(outer_members, cur_em);
1587 213388 : else if (bms_is_subset(cur_em->em_relids, inner_relids))
1588 211810 : inner_members = lappend(inner_members, cur_em);
1589 : else
1590 1578 : new_members = lappend(new_members, cur_em);
1591 : }
1592 :
1593 : /*
1594 : * First, select the joinclause if needed. We can equate any one outer
1595 : * member to any one inner member, but we have to find a datatype
1596 : * combination for which an opfamily member operator exists. If we have
1597 : * choices, we prefer simple Var members (possibly with RelabelType) since
1598 : * these are (a) cheapest to compute at runtime and (b) most likely to
1599 : * have useful statistics. Also, prefer operators that are also
1600 : * hashjoinable.
1601 : */
1602 252212 : if (outer_members && inner_members)
1603 : {
1604 200800 : EquivalenceMember *best_outer_em = NULL;
1605 200800 : EquivalenceMember *best_inner_em = NULL;
1606 200800 : Oid best_eq_op = InvalidOid;
1607 200800 : int best_score = -1;
1608 : RestrictInfo *rinfo;
1609 :
1610 213506 : foreach(lc1, outer_members)
1611 : {
1612 200872 : EquivalenceMember *outer_em = (EquivalenceMember *) lfirst(lc1);
1613 : ListCell *lc2;
1614 :
1615 213590 : foreach(lc2, inner_members)
1616 : {
1617 200884 : EquivalenceMember *inner_em = (EquivalenceMember *) lfirst(lc2);
1618 : Oid eq_op;
1619 : int score;
1620 :
1621 200884 : eq_op = select_equality_operator(ec,
1622 : outer_em->em_datatype,
1623 : inner_em->em_datatype);
1624 200884 : if (!OidIsValid(eq_op))
1625 36 : continue;
1626 200848 : score = 0;
1627 200848 : if (IsA(outer_em->em_expr, Var) ||
1628 13132 : (IsA(outer_em->em_expr, RelabelType) &&
1629 2582 : IsA(((RelabelType *) outer_em->em_expr)->arg, Var)))
1630 190250 : score++;
1631 200848 : if (IsA(inner_em->em_expr, Var) ||
1632 4976 : (IsA(inner_em->em_expr, RelabelType) &&
1633 2508 : IsA(((RelabelType *) inner_em->em_expr)->arg, Var)))
1634 198362 : score++;
1635 200848 : if (op_hashjoinable(eq_op,
1636 200848 : exprType((Node *) outer_em->em_expr)))
1637 200776 : score++;
1638 200848 : if (score > best_score)
1639 : {
1640 200764 : best_outer_em = outer_em;
1641 200764 : best_inner_em = inner_em;
1642 200764 : best_eq_op = eq_op;
1643 200764 : best_score = score;
1644 200764 : if (best_score == 3)
1645 188166 : break; /* no need to look further */
1646 : }
1647 : }
1648 200872 : if (best_score == 3)
1649 188166 : break; /* no need to look further */
1650 : }
1651 200800 : if (best_score < 0)
1652 : {
1653 : /* failed... */
1654 36 : ec->ec_broken = true;
1655 36 : return NIL;
1656 : }
1657 :
1658 : /*
1659 : * Create clause, setting parent_ec to mark it as redundant with other
1660 : * joinclauses
1661 : */
1662 200764 : rinfo = create_join_clause(root, ec, best_eq_op,
1663 : best_outer_em, best_inner_em,
1664 : ec);
1665 :
1666 200764 : result = lappend(result, rinfo);
1667 : }
1668 :
1669 : /*
1670 : * Now deal with building restrictions for any expressions that involve
1671 : * Vars from both sides of the join. We have to equate all of these to
1672 : * each other as well as to at least one old member (if any).
1673 : *
1674 : * XXX as in generate_base_implied_equalities_no_const, we could be a lot
1675 : * smarter here to avoid unnecessary failures in cross-type situations.
1676 : * For now, use the same left-to-right method used there.
1677 : */
1678 252176 : if (new_members)
1679 : {
1680 1542 : List *old_members = list_concat(outer_members, inner_members);
1681 1542 : EquivalenceMember *prev_em = NULL;
1682 : RestrictInfo *rinfo;
1683 :
1684 : /* For now, arbitrarily take the first old_member as the one to use */
1685 1542 : if (old_members)
1686 1092 : new_members = lappend(new_members, linitial(old_members));
1687 :
1688 4212 : foreach(lc1, new_members)
1689 : {
1690 2670 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
1691 :
1692 2670 : if (prev_em != NULL)
1693 : {
1694 : Oid eq_op;
1695 :
1696 1128 : eq_op = select_equality_operator(ec,
1697 : prev_em->em_datatype,
1698 : cur_em->em_datatype);
1699 1128 : if (!OidIsValid(eq_op))
1700 : {
1701 : /* failed... */
1702 0 : ec->ec_broken = true;
1703 0 : return NIL;
1704 : }
1705 : /* do NOT set parent_ec, this qual is not redundant! */
1706 1128 : rinfo = create_join_clause(root, ec, eq_op,
1707 : prev_em, cur_em,
1708 : NULL);
1709 :
1710 1128 : result = lappend(result, rinfo);
1711 : }
1712 2670 : prev_em = cur_em;
1713 : }
1714 : }
1715 :
1716 252176 : return result;
1717 : }
1718 :
1719 : /*
1720 : * generate_join_implied_equalities cleanup after failure
1721 : *
1722 : * Return any original RestrictInfos that are enforceable at this join.
1723 : *
1724 : * In the case of a child inner relation, we have to translate the
1725 : * original RestrictInfos from parent to child Vars.
1726 : */
1727 : static List *
1728 360 : generate_join_implied_equalities_broken(PlannerInfo *root,
1729 : EquivalenceClass *ec,
1730 : Relids nominal_join_relids,
1731 : Relids outer_relids,
1732 : Relids nominal_inner_relids,
1733 : RelOptInfo *inner_rel)
1734 : {
1735 360 : List *result = NIL;
1736 : ListCell *lc;
1737 :
1738 984 : foreach(lc, ec->ec_sources)
1739 : {
1740 624 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1741 624 : Relids clause_relids = restrictinfo->required_relids;
1742 :
1743 624 : if (bms_is_subset(clause_relids, nominal_join_relids) &&
1744 336 : !bms_is_subset(clause_relids, outer_relids) &&
1745 312 : !bms_is_subset(clause_relids, nominal_inner_relids))
1746 312 : result = lappend(result, restrictinfo);
1747 : }
1748 :
1749 : /*
1750 : * If we have to translate, just brute-force apply adjust_appendrel_attrs
1751 : * to all the RestrictInfos at once. This will result in returning
1752 : * RestrictInfos that are not listed in ec_derives, but there shouldn't be
1753 : * any duplication, and it's a sufficiently narrow corner case that we
1754 : * shouldn't sweat too much over it anyway.
1755 : *
1756 : * Since inner_rel might be an indirect descendant of the baserel
1757 : * mentioned in the ec_sources clauses, we have to be prepared to apply
1758 : * multiple levels of Var translation.
1759 : */
1760 360 : if (IS_OTHER_REL(inner_rel) && result != NIL)
1761 162 : result = (List *) adjust_appendrel_attrs_multilevel(root,
1762 : (Node *) result,
1763 : inner_rel,
1764 162 : inner_rel->top_parent);
1765 :
1766 360 : return result;
1767 : }
1768 :
1769 :
1770 : /*
1771 : * select_equality_operator
1772 : * Select a suitable equality operator for comparing two EC members
1773 : *
1774 : * Returns InvalidOid if no operator can be found for this datatype combination
1775 : */
1776 : static Oid
1777 311198 : select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
1778 : {
1779 : ListCell *lc;
1780 :
1781 311264 : foreach(lc, ec->ec_opfamilies)
1782 : {
1783 311198 : Oid opfamily = lfirst_oid(lc);
1784 : Oid opno;
1785 :
1786 311198 : opno = get_opfamily_member(opfamily, lefttype, righttype,
1787 : BTEqualStrategyNumber);
1788 311198 : if (!OidIsValid(opno))
1789 66 : continue;
1790 : /* If no barrier quals in query, don't worry about leaky operators */
1791 311132 : if (ec->ec_max_security == 0)
1792 311132 : return opno;
1793 : /* Otherwise, insist that selected operators be leakproof */
1794 428 : if (get_func_leakproof(get_opcode(opno)))
1795 428 : return opno;
1796 : }
1797 66 : return InvalidOid;
1798 : }
1799 :
1800 :
1801 : /*
1802 : * create_join_clause
1803 : * Find or make a RestrictInfo comparing the two given EC members
1804 : * with the given operator (or, possibly, its commutator, because
1805 : * the ordering of the operands in the result is not guaranteed).
1806 : *
1807 : * parent_ec is either equal to ec (if the clause is a potentially-redundant
1808 : * join clause) or NULL (if not). We have to treat this as part of the
1809 : * match requirements --- it's possible that a clause comparing the same two
1810 : * EMs is a join clause in one join path and a restriction clause in another.
1811 : */
1812 : static RestrictInfo *
1813 279548 : create_join_clause(PlannerInfo *root,
1814 : EquivalenceClass *ec, Oid opno,
1815 : EquivalenceMember *leftem,
1816 : EquivalenceMember *rightem,
1817 : EquivalenceClass *parent_ec)
1818 : {
1819 : RestrictInfo *rinfo;
1820 279548 : RestrictInfo *parent_rinfo = NULL;
1821 : ListCell *lc;
1822 : MemoryContext oldcontext;
1823 :
1824 : /*
1825 : * Search to see if we already built a RestrictInfo for this pair of
1826 : * EquivalenceMembers. We can use either original source clauses or
1827 : * previously-derived clauses, and a commutator clause is acceptable.
1828 : *
1829 : * We used to verify that opno matches, but that seems redundant: even if
1830 : * it's not identical, it'd better have the same effects, or the operator
1831 : * families we're using are broken.
1832 : */
1833 601730 : foreach(lc, ec->ec_sources)
1834 : {
1835 323148 : rinfo = (RestrictInfo *) lfirst(lc);
1836 323148 : if (rinfo->left_em == leftem &&
1837 146882 : rinfo->right_em == rightem &&
1838 132786 : rinfo->parent_ec == parent_ec)
1839 966 : return rinfo;
1840 323046 : if (rinfo->left_em == rightem &&
1841 142696 : rinfo->right_em == leftem &&
1842 130092 : rinfo->parent_ec == parent_ec)
1843 864 : return rinfo;
1844 : }
1845 :
1846 358948 : foreach(lc, ec->ec_derives)
1847 : {
1848 308578 : rinfo = (RestrictInfo *) lfirst(lc);
1849 308578 : if (rinfo->left_em == leftem &&
1850 117918 : rinfo->right_em == rightem &&
1851 107180 : rinfo->parent_ec == parent_ec)
1852 228212 : return rinfo;
1853 201404 : if (rinfo->left_em == rightem &&
1854 127696 : rinfo->right_em == leftem &&
1855 121038 : rinfo->parent_ec == parent_ec)
1856 121038 : return rinfo;
1857 : }
1858 :
1859 : /*
1860 : * Not there, so build it, in planner context so we can re-use it. (Not
1861 : * important in normal planning, but definitely so in GEQO.)
1862 : */
1863 50370 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
1864 :
1865 : /*
1866 : * If either EM is a child, recursively create the corresponding
1867 : * parent-to-parent clause, so that we can duplicate its rinfo_serial.
1868 : */
1869 50370 : if (leftem->em_is_child || rightem->em_is_child)
1870 : {
1871 3334 : EquivalenceMember *leftp = leftem->em_parent ? leftem->em_parent : leftem;
1872 3334 : EquivalenceMember *rightp = rightem->em_parent ? rightem->em_parent : rightem;
1873 :
1874 3334 : parent_rinfo = create_join_clause(root, ec, opno,
1875 : leftp, rightp,
1876 : parent_ec);
1877 : }
1878 :
1879 50370 : rinfo = build_implied_join_equality(root,
1880 : opno,
1881 : ec->ec_collation,
1882 : leftem->em_expr,
1883 : rightem->em_expr,
1884 50370 : bms_union(leftem->em_relids,
1885 50370 : rightem->em_relids),
1886 : ec->ec_min_security);
1887 :
1888 : /* If it's a child clause, copy the parent's rinfo_serial */
1889 50370 : if (parent_rinfo)
1890 3334 : rinfo->rinfo_serial = parent_rinfo->rinfo_serial;
1891 :
1892 : /* Mark the clause as redundant, or not */
1893 50370 : rinfo->parent_ec = parent_ec;
1894 :
1895 : /*
1896 : * We know the correct values for left_ec/right_ec, ie this particular EC,
1897 : * so we can just set them directly instead of forcing another lookup.
1898 : */
1899 50370 : rinfo->left_ec = ec;
1900 50370 : rinfo->right_ec = ec;
1901 :
1902 : /* Mark it as usable with these EMs */
1903 50370 : rinfo->left_em = leftem;
1904 50370 : rinfo->right_em = rightem;
1905 : /* and save it for possible re-use */
1906 50370 : ec->ec_derives = lappend(ec->ec_derives, rinfo);
1907 :
1908 50370 : MemoryContextSwitchTo(oldcontext);
1909 :
1910 50370 : return rinfo;
1911 : }
1912 :
1913 :
1914 : /*
1915 : * reconsider_outer_join_clauses
1916 : * Re-examine any outer-join clauses that were set aside by
1917 : * distribute_qual_to_rels(), and see if we can derive any
1918 : * EquivalenceClasses from them. Then, if they were not made
1919 : * redundant, push them out into the regular join-clause lists.
1920 : *
1921 : * When we have mergejoinable clauses A = B that are outer-join clauses,
1922 : * we can't blindly combine them with other clauses A = C to deduce B = C,
1923 : * since in fact the "equality" A = B won't necessarily hold above the
1924 : * outer join (one of the variables might be NULL instead). Nonetheless
1925 : * there are cases where we can add qual clauses using transitivity.
1926 : *
1927 : * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
1928 : * for which there is also an equivalence clause OUTERVAR = CONSTANT.
1929 : * It is safe and useful to push a clause INNERVAR = CONSTANT into the
1930 : * evaluation of the inner (nullable) relation, because any inner rows not
1931 : * meeting this condition will not contribute to the outer-join result anyway.
1932 : * (Any outer rows they could join to will be eliminated by the pushed-down
1933 : * equivalence clause.)
1934 : *
1935 : * Note that the above rule does not work for full outer joins; nor is it
1936 : * very interesting to consider cases where the generated equivalence clause
1937 : * would involve relations outside the outer join, since such clauses couldn't
1938 : * be pushed into the inner side's scan anyway. So the restriction to
1939 : * outervar = pseudoconstant is not really giving up anything.
1940 : *
1941 : * For full-join cases, we can only do something useful if it's a FULL JOIN
1942 : * USING and a merged column has an equivalence MERGEDVAR = CONSTANT.
1943 : * By the time it gets here, the merged column will look like
1944 : * COALESCE(LEFTVAR, RIGHTVAR)
1945 : * and we will have a full-join clause LEFTVAR = RIGHTVAR that we can match
1946 : * the COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT
1947 : * and RIGHTVAR = CONSTANT into the input relations, since any rows not
1948 : * meeting these conditions cannot contribute to the join result.
1949 : *
1950 : * Again, there isn't any traction to be gained by trying to deal with
1951 : * clauses comparing a mergedvar to a non-pseudoconstant. So we can make
1952 : * use of the EquivalenceClasses to search for matching variables that were
1953 : * equivalenced to constants. The interesting outer-join clauses were
1954 : * accumulated for us by distribute_qual_to_rels.
1955 : *
1956 : * When we find one of these cases, we implement the changes we want by
1957 : * generating a new equivalence clause INNERVAR = CONSTANT (or LEFTVAR, etc)
1958 : * and pushing it into the EquivalenceClass structures. This is because we
1959 : * may already know that INNERVAR is equivalenced to some other var(s), and
1960 : * we'd like the constant to propagate to them too. Note that it would be
1961 : * unsafe to merge any existing EC for INNERVAR with the OUTERVAR's EC ---
1962 : * that could result in propagating constant restrictions from
1963 : * INNERVAR to OUTERVAR, which would be very wrong.
1964 : *
1965 : * It's possible that the INNERVAR is also an OUTERVAR for some other
1966 : * outer-join clause, in which case the process can be repeated. So we repeat
1967 : * looping over the lists of clauses until no further deductions can be made.
1968 : * Whenever we do make a deduction, we remove the generating clause from the
1969 : * lists, since we don't want to make the same deduction twice.
1970 : *
1971 : * If we don't find any match for a set-aside outer join clause, we must
1972 : * throw it back into the regular joinclause processing by passing it to
1973 : * distribute_restrictinfo_to_rels(). If we do generate a derived clause,
1974 : * however, the outer-join clause is redundant. We must still put some
1975 : * clause into the regular processing, because otherwise the join will be
1976 : * seen as a clauseless join and avoided during join order searching.
1977 : * We handle this by generating a constant-TRUE clause that is marked with
1978 : * the same required_relids etc as the removed outer-join clause, thus
1979 : * making it a join clause between the correct relations.
1980 : */
1981 : void
1982 258878 : reconsider_outer_join_clauses(PlannerInfo *root)
1983 : {
1984 : bool found;
1985 : ListCell *cell;
1986 :
1987 : /* Outer loop repeats until we find no more deductions */
1988 : do
1989 : {
1990 258878 : found = false;
1991 :
1992 : /* Process the LEFT JOIN clauses */
1993 287806 : foreach(cell, root->left_join_clauses)
1994 : {
1995 28928 : OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
1996 :
1997 28928 : if (reconsider_outer_join_clause(root, ojcinfo, true))
1998 : {
1999 652 : RestrictInfo *rinfo = ojcinfo->rinfo;
2000 :
2001 652 : found = true;
2002 : /* remove it from the list */
2003 652 : root->left_join_clauses =
2004 652 : foreach_delete_current(root->left_join_clauses, cell);
2005 : /* throw back a dummy replacement clause (see notes above) */
2006 652 : rinfo = make_restrictinfo(root,
2007 652 : (Expr *) makeBoolConst(true, false),
2008 652 : rinfo->is_pushed_down,
2009 652 : rinfo->has_clone,
2010 652 : rinfo->is_clone,
2011 : false, /* pseudoconstant */
2012 : 0, /* security_level */
2013 : rinfo->required_relids,
2014 : rinfo->incompatible_relids,
2015 : rinfo->outer_relids);
2016 652 : distribute_restrictinfo_to_rels(root, rinfo);
2017 : }
2018 : }
2019 :
2020 : /* Process the RIGHT JOIN clauses */
2021 277548 : foreach(cell, root->right_join_clauses)
2022 : {
2023 18670 : OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2024 :
2025 18670 : if (reconsider_outer_join_clause(root, ojcinfo, false))
2026 : {
2027 776 : RestrictInfo *rinfo = ojcinfo->rinfo;
2028 :
2029 776 : found = true;
2030 : /* remove it from the list */
2031 776 : root->right_join_clauses =
2032 776 : foreach_delete_current(root->right_join_clauses, cell);
2033 : /* throw back a dummy replacement clause (see notes above) */
2034 776 : rinfo = make_restrictinfo(root,
2035 776 : (Expr *) makeBoolConst(true, false),
2036 776 : rinfo->is_pushed_down,
2037 776 : rinfo->has_clone,
2038 776 : rinfo->is_clone,
2039 : false, /* pseudoconstant */
2040 : 0, /* security_level */
2041 : rinfo->required_relids,
2042 : rinfo->incompatible_relids,
2043 : rinfo->outer_relids);
2044 776 : distribute_restrictinfo_to_rels(root, rinfo);
2045 : }
2046 : }
2047 :
2048 : /* Process the FULL JOIN clauses */
2049 260004 : foreach(cell, root->full_join_clauses)
2050 : {
2051 1126 : OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2052 :
2053 1126 : if (reconsider_full_join_clause(root, ojcinfo))
2054 : {
2055 6 : RestrictInfo *rinfo = ojcinfo->rinfo;
2056 :
2057 6 : found = true;
2058 : /* remove it from the list */
2059 6 : root->full_join_clauses =
2060 6 : foreach_delete_current(root->full_join_clauses, cell);
2061 : /* throw back a dummy replacement clause (see notes above) */
2062 6 : rinfo = make_restrictinfo(root,
2063 6 : (Expr *) makeBoolConst(true, false),
2064 6 : rinfo->is_pushed_down,
2065 6 : rinfo->has_clone,
2066 6 : rinfo->is_clone,
2067 : false, /* pseudoconstant */
2068 : 0, /* security_level */
2069 : rinfo->required_relids,
2070 : rinfo->incompatible_relids,
2071 : rinfo->outer_relids);
2072 6 : distribute_restrictinfo_to_rels(root, rinfo);
2073 : }
2074 : }
2075 258878 : } while (found);
2076 :
2077 : /* Now, any remaining clauses have to be thrown back */
2078 285254 : foreach(cell, root->left_join_clauses)
2079 : {
2080 27798 : OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2081 :
2082 27798 : distribute_restrictinfo_to_rels(root, ojcinfo->rinfo);
2083 : }
2084 274526 : foreach(cell, root->right_join_clauses)
2085 : {
2086 17070 : OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2087 :
2088 17070 : distribute_restrictinfo_to_rels(root, ojcinfo->rinfo);
2089 : }
2090 258576 : foreach(cell, root->full_join_clauses)
2091 : {
2092 1120 : OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2093 :
2094 1120 : distribute_restrictinfo_to_rels(root, ojcinfo->rinfo);
2095 : }
2096 257456 : }
2097 :
2098 : /*
2099 : * reconsider_outer_join_clauses for a single LEFT/RIGHT JOIN clause
2100 : *
2101 : * Returns true if we were able to propagate a constant through the clause.
2102 : */
2103 : static bool
2104 47598 : reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo,
2105 : bool outer_on_left)
2106 : {
2107 47598 : RestrictInfo *rinfo = ojcinfo->rinfo;
2108 47598 : SpecialJoinInfo *sjinfo = ojcinfo->sjinfo;
2109 : Expr *outervar,
2110 : *innervar;
2111 : Oid opno,
2112 : collation,
2113 : left_type,
2114 : right_type,
2115 : inner_datatype;
2116 : Relids inner_relids;
2117 : ListCell *lc1;
2118 :
2119 : Assert(is_opclause(rinfo->clause));
2120 47598 : opno = ((OpExpr *) rinfo->clause)->opno;
2121 47598 : collation = ((OpExpr *) rinfo->clause)->inputcollid;
2122 :
2123 : /* Extract needed info from the clause */
2124 47598 : op_input_types(opno, &left_type, &right_type);
2125 47598 : if (outer_on_left)
2126 : {
2127 28928 : outervar = (Expr *) get_leftop(rinfo->clause);
2128 28928 : innervar = (Expr *) get_rightop(rinfo->clause);
2129 28928 : inner_datatype = right_type;
2130 28928 : inner_relids = rinfo->right_relids;
2131 : }
2132 : else
2133 : {
2134 18670 : outervar = (Expr *) get_rightop(rinfo->clause);
2135 18670 : innervar = (Expr *) get_leftop(rinfo->clause);
2136 18670 : inner_datatype = left_type;
2137 18670 : inner_relids = rinfo->left_relids;
2138 : }
2139 :
2140 : /* Scan EquivalenceClasses for a match to outervar */
2141 305342 : foreach(lc1, root->eq_classes)
2142 : {
2143 259172 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2144 : bool match;
2145 : ListCell *lc2;
2146 :
2147 : /* Ignore EC unless it contains pseudoconstants */
2148 259172 : if (!cur_ec->ec_has_const)
2149 204292 : continue;
2150 : /* Never match to a volatile EC */
2151 54880 : if (cur_ec->ec_has_volatile)
2152 0 : continue;
2153 : /* It has to match the outer-join clause as to semantics, too */
2154 54880 : if (collation != cur_ec->ec_collation)
2155 1896 : continue;
2156 52984 : if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
2157 11498 : continue;
2158 : /* Does it contain a match to outervar? */
2159 41486 : match = false;
2160 127644 : foreach(lc2, cur_ec->ec_members)
2161 : {
2162 87586 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2163 :
2164 : Assert(!cur_em->em_is_child); /* no children yet */
2165 87586 : if (equal(outervar, cur_em->em_expr))
2166 : {
2167 1428 : match = true;
2168 1428 : break;
2169 : }
2170 : }
2171 41486 : if (!match)
2172 40058 : continue; /* no match, so ignore this EC */
2173 :
2174 : /*
2175 : * Yes it does! Try to generate a clause INNERVAR = CONSTANT for each
2176 : * CONSTANT in the EC. Note that we must succeed with at least one
2177 : * constant before we can decide to throw away the outer-join clause.
2178 : */
2179 1428 : match = false;
2180 5108 : foreach(lc2, cur_ec->ec_members)
2181 : {
2182 3680 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2183 : Oid eq_op;
2184 : RestrictInfo *newrinfo;
2185 : JoinDomain *jdomain;
2186 :
2187 3680 : if (!cur_em->em_is_const)
2188 2210 : continue; /* ignore non-const members */
2189 1470 : eq_op = select_equality_operator(cur_ec,
2190 : inner_datatype,
2191 : cur_em->em_datatype);
2192 1470 : if (!OidIsValid(eq_op))
2193 0 : continue; /* can't generate equality */
2194 1470 : newrinfo = build_implied_join_equality(root,
2195 : eq_op,
2196 : cur_ec->ec_collation,
2197 : innervar,
2198 : cur_em->em_expr,
2199 : bms_copy(inner_relids),
2200 : cur_ec->ec_min_security);
2201 : /* This equality holds within the OJ's child JoinDomain */
2202 1470 : jdomain = find_join_domain(root, sjinfo->syn_righthand);
2203 1470 : if (process_equivalence(root, &newrinfo, jdomain))
2204 1470 : match = true;
2205 : }
2206 :
2207 : /*
2208 : * If we were able to equate INNERVAR to any constant, report success.
2209 : * Otherwise, fall out of the search loop, since we know the OUTERVAR
2210 : * appears in at most one EC.
2211 : */
2212 1428 : if (match)
2213 1428 : return true;
2214 : else
2215 0 : break;
2216 : }
2217 :
2218 46170 : return false; /* failed to make any deduction */
2219 : }
2220 :
2221 : /*
2222 : * reconsider_outer_join_clauses for a single FULL JOIN clause
2223 : *
2224 : * Returns true if we were able to propagate a constant through the clause.
2225 : */
2226 : static bool
2227 1126 : reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
2228 : {
2229 1126 : RestrictInfo *rinfo = ojcinfo->rinfo;
2230 1126 : SpecialJoinInfo *sjinfo = ojcinfo->sjinfo;
2231 1126 : Relids fjrelids = bms_make_singleton(sjinfo->ojrelid);
2232 : Expr *leftvar;
2233 : Expr *rightvar;
2234 : Oid opno,
2235 : collation,
2236 : left_type,
2237 : right_type;
2238 : Relids left_relids,
2239 : right_relids;
2240 : ListCell *lc1;
2241 :
2242 : /* Extract needed info from the clause */
2243 : Assert(is_opclause(rinfo->clause));
2244 1126 : opno = ((OpExpr *) rinfo->clause)->opno;
2245 1126 : collation = ((OpExpr *) rinfo->clause)->inputcollid;
2246 1126 : op_input_types(opno, &left_type, &right_type);
2247 1126 : leftvar = (Expr *) get_leftop(rinfo->clause);
2248 1126 : rightvar = (Expr *) get_rightop(rinfo->clause);
2249 1126 : left_relids = rinfo->left_relids;
2250 1126 : right_relids = rinfo->right_relids;
2251 :
2252 5952 : foreach(lc1, root->eq_classes)
2253 : {
2254 4832 : EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2255 4832 : EquivalenceMember *coal_em = NULL;
2256 : bool match;
2257 : bool matchleft;
2258 : bool matchright;
2259 : ListCell *lc2;
2260 4832 : int coal_idx = -1;
2261 :
2262 : /* Ignore EC unless it contains pseudoconstants */
2263 4832 : if (!cur_ec->ec_has_const)
2264 4542 : continue;
2265 : /* Never match to a volatile EC */
2266 290 : if (cur_ec->ec_has_volatile)
2267 0 : continue;
2268 : /* It has to match the outer-join clause as to semantics, too */
2269 290 : if (collation != cur_ec->ec_collation)
2270 36 : continue;
2271 254 : if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
2272 0 : continue;
2273 :
2274 : /*
2275 : * Does it contain a COALESCE(leftvar, rightvar) construct?
2276 : *
2277 : * We can assume the COALESCE() inputs are in the same order as the
2278 : * join clause, since both were automatically generated in the cases
2279 : * we care about.
2280 : *
2281 : * XXX currently this may fail to match in cross-type cases because
2282 : * the COALESCE will contain typecast operations while the join clause
2283 : * may not (if there is a cross-type mergejoin operator available for
2284 : * the two column types). Is it OK to strip implicit coercions from
2285 : * the COALESCE arguments?
2286 : */
2287 254 : match = false;
2288 750 : foreach(lc2, cur_ec->ec_members)
2289 : {
2290 502 : coal_em = (EquivalenceMember *) lfirst(lc2);
2291 : Assert(!coal_em->em_is_child); /* no children yet */
2292 502 : if (IsA(coal_em->em_expr, CoalesceExpr))
2293 : {
2294 18 : CoalesceExpr *cexpr = (CoalesceExpr *) coal_em->em_expr;
2295 : Node *cfirst;
2296 : Node *csecond;
2297 :
2298 18 : if (list_length(cexpr->args) != 2)
2299 12 : continue;
2300 6 : cfirst = (Node *) linitial(cexpr->args);
2301 6 : csecond = (Node *) lsecond(cexpr->args);
2302 :
2303 : /*
2304 : * The COALESCE arguments will be marked as possibly nulled by
2305 : * the full join, while we wish to generate clauses that apply
2306 : * to the join's inputs. So we must strip the join from the
2307 : * nullingrels fields of cfirst/csecond before comparing them
2308 : * to leftvar/rightvar. (Perhaps with a less hokey
2309 : * representation for FULL JOIN USING output columns, this
2310 : * wouldn't be needed?)
2311 : */
2312 6 : cfirst = remove_nulling_relids(cfirst, fjrelids, NULL);
2313 6 : csecond = remove_nulling_relids(csecond, fjrelids, NULL);
2314 :
2315 6 : if (equal(leftvar, cfirst) && equal(rightvar, csecond))
2316 : {
2317 6 : coal_idx = foreach_current_index(lc2);
2318 6 : match = true;
2319 6 : break;
2320 : }
2321 : }
2322 : }
2323 254 : if (!match)
2324 248 : continue; /* no match, so ignore this EC */
2325 :
2326 : /*
2327 : * Yes it does! Try to generate clauses LEFTVAR = CONSTANT and
2328 : * RIGHTVAR = CONSTANT for each CONSTANT in the EC. Note that we must
2329 : * succeed with at least one constant for each var before we can
2330 : * decide to throw away the outer-join clause.
2331 : */
2332 6 : matchleft = matchright = false;
2333 18 : foreach(lc2, cur_ec->ec_members)
2334 : {
2335 12 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2336 : Oid eq_op;
2337 : RestrictInfo *newrinfo;
2338 : JoinDomain *jdomain;
2339 :
2340 12 : if (!cur_em->em_is_const)
2341 6 : continue; /* ignore non-const members */
2342 6 : eq_op = select_equality_operator(cur_ec,
2343 : left_type,
2344 : cur_em->em_datatype);
2345 6 : if (OidIsValid(eq_op))
2346 : {
2347 6 : newrinfo = build_implied_join_equality(root,
2348 : eq_op,
2349 : cur_ec->ec_collation,
2350 : leftvar,
2351 : cur_em->em_expr,
2352 : bms_copy(left_relids),
2353 : cur_ec->ec_min_security);
2354 : /* This equality holds within the lefthand child JoinDomain */
2355 6 : jdomain = find_join_domain(root, sjinfo->syn_lefthand);
2356 6 : if (process_equivalence(root, &newrinfo, jdomain))
2357 6 : matchleft = true;
2358 : }
2359 6 : eq_op = select_equality_operator(cur_ec,
2360 : right_type,
2361 : cur_em->em_datatype);
2362 6 : if (OidIsValid(eq_op))
2363 : {
2364 6 : newrinfo = build_implied_join_equality(root,
2365 : eq_op,
2366 : cur_ec->ec_collation,
2367 : rightvar,
2368 : cur_em->em_expr,
2369 : bms_copy(right_relids),
2370 : cur_ec->ec_min_security);
2371 : /* This equality holds within the righthand child JoinDomain */
2372 6 : jdomain = find_join_domain(root, sjinfo->syn_righthand);
2373 6 : if (process_equivalence(root, &newrinfo, jdomain))
2374 6 : matchright = true;
2375 : }
2376 : }
2377 :
2378 : /*
2379 : * If we were able to equate both vars to constants, we're done, and
2380 : * we can throw away the full-join clause as redundant. Moreover, we
2381 : * can remove the COALESCE entry from the EC, since the added
2382 : * restrictions ensure it will always have the expected value. (We
2383 : * don't bother trying to update ec_relids or ec_sources.)
2384 : */
2385 6 : if (matchleft && matchright)
2386 : {
2387 6 : cur_ec->ec_members = list_delete_nth_cell(cur_ec->ec_members, coal_idx);
2388 6 : return true;
2389 : }
2390 :
2391 : /*
2392 : * Otherwise, fall out of the search loop, since we know the COALESCE
2393 : * appears in at most one EC (XXX might stop being true if we allow
2394 : * stripping of coercions above?)
2395 : */
2396 0 : break;
2397 : }
2398 :
2399 1120 : return false; /* failed to make any deduction */
2400 : }
2401 :
2402 : /*
2403 : * find_join_domain
2404 : * Find the highest JoinDomain enclosed within the given relid set.
2405 : *
2406 : * (We could avoid this search at the cost of complicating APIs elsewhere,
2407 : * which doesn't seem worth it.)
2408 : */
2409 : static JoinDomain *
2410 1482 : find_join_domain(PlannerInfo *root, Relids relids)
2411 : {
2412 : ListCell *lc;
2413 :
2414 3054 : foreach(lc, root->join_domains)
2415 : {
2416 3054 : JoinDomain *jdomain = (JoinDomain *) lfirst(lc);
2417 :
2418 3054 : if (bms_is_subset(jdomain->jd_relids, relids))
2419 1482 : return jdomain;
2420 : }
2421 0 : elog(ERROR, "failed to find appropriate JoinDomain");
2422 : return NULL; /* keep compiler quiet */
2423 : }
2424 :
2425 :
2426 : /*
2427 : * exprs_known_equal
2428 : * Detect whether two expressions are known equal due to equivalence
2429 : * relationships.
2430 : *
2431 : * Actually, this only shows that the expressions are equal according
2432 : * to some opfamily's notion of equality --- but we only use it for
2433 : * selectivity estimation, so a fuzzy idea of equality is OK.
2434 : *
2435 : * Note: does not bother to check for "equal(item1, item2)"; caller must
2436 : * check that case if it's possible to pass identical items.
2437 : */
2438 : bool
2439 3104 : exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
2440 : {
2441 : ListCell *lc1;
2442 :
2443 19118 : foreach(lc1, root->eq_classes)
2444 : {
2445 16134 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2446 16134 : bool item1member = false;
2447 16134 : bool item2member = false;
2448 : ListCell *lc2;
2449 :
2450 : /* Never match to a volatile EC */
2451 16134 : if (ec->ec_has_volatile)
2452 0 : continue;
2453 :
2454 51910 : foreach(lc2, ec->ec_members)
2455 : {
2456 35896 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
2457 :
2458 35896 : if (em->em_is_child)
2459 12732 : continue; /* ignore children here */
2460 23164 : if (equal(item1, em->em_expr))
2461 1526 : item1member = true;
2462 21638 : else if (equal(item2, em->em_expr))
2463 1670 : item2member = true;
2464 : /* Exit as soon as equality is proven */
2465 23164 : if (item1member && item2member)
2466 120 : return true;
2467 : }
2468 : }
2469 2984 : return false;
2470 : }
2471 :
2472 :
2473 : /*
2474 : * match_eclasses_to_foreign_key_col
2475 : * See whether a foreign key column match is proven by any eclass.
2476 : *
2477 : * If the referenced and referencing Vars of the fkey's colno'th column are
2478 : * known equal due to any eclass, return that eclass; otherwise return NULL.
2479 : * (In principle there might be more than one matching eclass if multiple
2480 : * collations are involved, but since collation doesn't matter for equality,
2481 : * we ignore that fine point here.) This is much like exprs_known_equal,
2482 : * except that we insist on the comparison operator matching the eclass, so
2483 : * that the result is definite not approximate.
2484 : *
2485 : * On success, we also set fkinfo->eclass[colno] to the matching eclass,
2486 : * and set fkinfo->fk_eclass_member[colno] to the eclass member for the
2487 : * referencing Var.
2488 : */
2489 : EquivalenceClass *
2490 2150 : match_eclasses_to_foreign_key_col(PlannerInfo *root,
2491 : ForeignKeyOptInfo *fkinfo,
2492 : int colno)
2493 : {
2494 2150 : Index var1varno = fkinfo->con_relid;
2495 2150 : AttrNumber var1attno = fkinfo->conkey[colno];
2496 2150 : Index var2varno = fkinfo->ref_relid;
2497 2150 : AttrNumber var2attno = fkinfo->confkey[colno];
2498 2150 : Oid eqop = fkinfo->conpfeqop[colno];
2499 2150 : RelOptInfo *rel1 = root->simple_rel_array[var1varno];
2500 2150 : RelOptInfo *rel2 = root->simple_rel_array[var2varno];
2501 2150 : List *opfamilies = NIL; /* compute only if needed */
2502 : Bitmapset *matching_ecs;
2503 : int i;
2504 :
2505 : /* Consider only eclasses mentioning both relations */
2506 : Assert(root->ec_merging_done);
2507 : Assert(IS_SIMPLE_REL(rel1));
2508 : Assert(IS_SIMPLE_REL(rel2));
2509 2150 : matching_ecs = bms_intersect(rel1->eclass_indexes,
2510 2150 : rel2->eclass_indexes);
2511 :
2512 2150 : i = -1;
2513 2246 : while ((i = bms_next_member(matching_ecs, i)) >= 0)
2514 : {
2515 438 : EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
2516 : i);
2517 438 : EquivalenceMember *item1_em = NULL;
2518 438 : EquivalenceMember *item2_em = NULL;
2519 : ListCell *lc2;
2520 :
2521 : /* Never match to a volatile EC */
2522 438 : if (ec->ec_has_volatile)
2523 0 : continue;
2524 : /* Note: it seems okay to match to "broken" eclasses here */
2525 :
2526 1074 : foreach(lc2, ec->ec_members)
2527 : {
2528 978 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
2529 : Var *var;
2530 :
2531 978 : if (em->em_is_child)
2532 0 : continue; /* ignore children here */
2533 :
2534 : /* EM must be a Var, possibly with RelabelType */
2535 978 : var = (Var *) em->em_expr;
2536 978 : while (var && IsA(var, RelabelType))
2537 0 : var = (Var *) ((RelabelType *) var)->arg;
2538 978 : if (!(var && IsA(var, Var)))
2539 6 : continue;
2540 :
2541 : /* Match? */
2542 972 : if (var->varno == var1varno && var->varattno == var1attno)
2543 342 : item1_em = em;
2544 630 : else if (var->varno == var2varno && var->varattno == var2attno)
2545 342 : item2_em = em;
2546 :
2547 : /* Have we found both PK and FK column in this EC? */
2548 972 : if (item1_em && item2_em)
2549 : {
2550 : /*
2551 : * Succeed if eqop matches EC's opfamilies. We could test
2552 : * this before scanning the members, but it's probably cheaper
2553 : * to test for member matches first.
2554 : */
2555 342 : if (opfamilies == NIL) /* compute if we didn't already */
2556 342 : opfamilies = get_mergejoin_opfamilies(eqop);
2557 342 : if (equal(opfamilies, ec->ec_opfamilies))
2558 : {
2559 342 : fkinfo->eclass[colno] = ec;
2560 342 : fkinfo->fk_eclass_member[colno] = item2_em;
2561 342 : return ec;
2562 : }
2563 : /* Otherwise, done with this EC, move on to the next */
2564 0 : break;
2565 : }
2566 : }
2567 : }
2568 1808 : return NULL;
2569 : }
2570 :
2571 : /*
2572 : * find_derived_clause_for_ec_member
2573 : * Search for a previously-derived clause mentioning the given EM.
2574 : *
2575 : * The eclass should be an ec_has_const EC, of which the EM is a non-const
2576 : * member. This should ensure there is just one derived clause mentioning
2577 : * the EM (and equating it to a constant).
2578 : * Returns NULL if no such clause can be found.
2579 : */
2580 : RestrictInfo *
2581 6 : find_derived_clause_for_ec_member(EquivalenceClass *ec,
2582 : EquivalenceMember *em)
2583 : {
2584 : ListCell *lc;
2585 :
2586 : Assert(ec->ec_has_const);
2587 : Assert(!em->em_is_const);
2588 6 : foreach(lc, ec->ec_derives)
2589 : {
2590 6 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2591 :
2592 : /*
2593 : * generate_base_implied_equalities_const will have put non-const
2594 : * members on the left side of derived clauses.
2595 : */
2596 6 : if (rinfo->left_em == em)
2597 6 : return rinfo;
2598 : }
2599 0 : return NULL;
2600 : }
2601 :
2602 :
2603 : /*
2604 : * add_child_rel_equivalences
2605 : * Search for EC members that reference the root parent of child_rel, and
2606 : * add transformed members referencing the child_rel.
2607 : *
2608 : * Note that this function won't be called at all unless we have at least some
2609 : * reason to believe that the EC members it generates will be useful.
2610 : *
2611 : * parent_rel and child_rel could be derived from appinfo, but since the
2612 : * caller has already computed them, we might as well just pass them in.
2613 : *
2614 : * The passed-in AppendRelInfo is not used when the parent_rel is not a
2615 : * top-level baserel, since it shows the mapping from the parent_rel but
2616 : * we need to translate EC expressions that refer to the top-level parent.
2617 : * Using it is faster than using adjust_appendrel_attrs_multilevel(), though,
2618 : * so we prefer it when we can.
2619 : */
2620 : void
2621 20472 : add_child_rel_equivalences(PlannerInfo *root,
2622 : AppendRelInfo *appinfo,
2623 : RelOptInfo *parent_rel,
2624 : RelOptInfo *child_rel)
2625 : {
2626 20472 : Relids top_parent_relids = child_rel->top_parent_relids;
2627 20472 : Relids child_relids = child_rel->relids;
2628 : int i;
2629 :
2630 : /*
2631 : * EC merging should be complete already, so we can use the parent rel's
2632 : * eclass_indexes to avoid searching all of root->eq_classes.
2633 : */
2634 : Assert(root->ec_merging_done);
2635 : Assert(IS_SIMPLE_REL(parent_rel));
2636 :
2637 20472 : i = -1;
2638 60820 : while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2639 : {
2640 40348 : EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2641 : int num_members;
2642 :
2643 : /*
2644 : * If this EC contains a volatile expression, then generating child
2645 : * EMs would be downright dangerous, so skip it. We rely on a
2646 : * volatile EC having only one EM.
2647 : */
2648 40348 : if (cur_ec->ec_has_volatile)
2649 0 : continue;
2650 :
2651 : /* Sanity check eclass_indexes only contain ECs for parent_rel */
2652 : Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
2653 :
2654 : /*
2655 : * We don't use foreach() here because there's no point in scanning
2656 : * newly-added child members, so we can stop after the last
2657 : * pre-existing EC member.
2658 : */
2659 40348 : num_members = list_length(cur_ec->ec_members);
2660 186328 : for (int pos = 0; pos < num_members; pos++)
2661 : {
2662 145980 : EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2663 :
2664 145980 : if (cur_em->em_is_const)
2665 3168 : continue; /* ignore consts here */
2666 :
2667 : /*
2668 : * We consider only original EC members here, not
2669 : * already-transformed child members. Otherwise, if some original
2670 : * member expression references more than one appendrel, we'd get
2671 : * an O(N^2) explosion of useless derived expressions for
2672 : * combinations of children. (But add_child_join_rel_equivalences
2673 : * may add targeted combinations for partitionwise-join purposes.)
2674 : */
2675 142812 : if (cur_em->em_is_child)
2676 90462 : continue; /* ignore children here */
2677 :
2678 : /*
2679 : * Consider only members that reference and can be computed at
2680 : * child's topmost parent rel. In particular we want to exclude
2681 : * parent-rel Vars that have nonempty varnullingrels. Translating
2682 : * those might fail, if the transformed expression wouldn't be a
2683 : * simple Var; and in any case it wouldn't produce a member that
2684 : * has any use in creating plans for the child rel.
2685 : */
2686 52350 : if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
2687 37756 : !bms_is_empty(cur_em->em_relids))
2688 : {
2689 : /* OK, generate transformed child version */
2690 : Expr *child_expr;
2691 : Relids new_relids;
2692 :
2693 37756 : if (parent_rel->reloptkind == RELOPT_BASEREL)
2694 : {
2695 : /* Simple single-level transformation */
2696 : child_expr = (Expr *)
2697 30748 : adjust_appendrel_attrs(root,
2698 30748 : (Node *) cur_em->em_expr,
2699 : 1, &appinfo);
2700 : }
2701 : else
2702 : {
2703 : /* Must do multi-level transformation */
2704 : child_expr = (Expr *)
2705 7008 : adjust_appendrel_attrs_multilevel(root,
2706 7008 : (Node *) cur_em->em_expr,
2707 : child_rel,
2708 7008 : child_rel->top_parent);
2709 : }
2710 :
2711 : /*
2712 : * Transform em_relids to match. Note we do *not* do
2713 : * pull_varnos(child_expr) here, as for example the
2714 : * transformation might have substituted a constant, but we
2715 : * don't want the child member to be marked as constant.
2716 : */
2717 37756 : new_relids = bms_difference(cur_em->em_relids,
2718 : top_parent_relids);
2719 37756 : new_relids = bms_add_members(new_relids, child_relids);
2720 :
2721 37756 : (void) add_eq_member(cur_ec, child_expr, new_relids,
2722 : cur_em->em_jdomain,
2723 : cur_em, cur_em->em_datatype);
2724 :
2725 : /* Record this EC index for the child rel */
2726 37756 : child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
2727 : }
2728 : }
2729 : }
2730 20472 : }
2731 :
2732 : /*
2733 : * add_child_join_rel_equivalences
2734 : * Like add_child_rel_equivalences(), but for joinrels
2735 : *
2736 : * Here we find the ECs relevant to the top parent joinrel and add transformed
2737 : * member expressions that refer to this child joinrel.
2738 : *
2739 : * Note that this function won't be called at all unless we have at least some
2740 : * reason to believe that the EC members it generates will be useful.
2741 : */
2742 : void
2743 4180 : add_child_join_rel_equivalences(PlannerInfo *root,
2744 : int nappinfos, AppendRelInfo **appinfos,
2745 : RelOptInfo *parent_joinrel,
2746 : RelOptInfo *child_joinrel)
2747 : {
2748 4180 : Relids top_parent_relids = child_joinrel->top_parent_relids;
2749 4180 : Relids child_relids = child_joinrel->relids;
2750 : Bitmapset *matching_ecs;
2751 : MemoryContext oldcontext;
2752 : int i;
2753 :
2754 : Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2755 :
2756 : /* We need consider only ECs that mention the parent joinrel */
2757 4180 : matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2758 :
2759 : /*
2760 : * If we're being called during GEQO join planning, we still have to
2761 : * create any new EC members in the main planner context, to avoid having
2762 : * a corrupt EC data structure after the GEQO context is reset. This is
2763 : * problematic since we'll leak memory across repeated GEQO cycles. For
2764 : * now, though, bloat is better than crash. If it becomes a real issue
2765 : * we'll have to do something to avoid generating duplicate EC members.
2766 : */
2767 4180 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
2768 :
2769 4180 : i = -1;
2770 19686 : while ((i = bms_next_member(matching_ecs, i)) >= 0)
2771 : {
2772 15506 : EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2773 : int num_members;
2774 :
2775 : /*
2776 : * If this EC contains a volatile expression, then generating child
2777 : * EMs would be downright dangerous, so skip it. We rely on a
2778 : * volatile EC having only one EM.
2779 : */
2780 15506 : if (cur_ec->ec_has_volatile)
2781 0 : continue;
2782 :
2783 : /* Sanity check on get_eclass_indexes_for_relids result */
2784 : Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2785 :
2786 : /*
2787 : * We don't use foreach() here because there's no point in scanning
2788 : * newly-added child members, so we can stop after the last
2789 : * pre-existing EC member.
2790 : */
2791 15506 : num_members = list_length(cur_ec->ec_members);
2792 103442 : for (int pos = 0; pos < num_members; pos++)
2793 : {
2794 87936 : EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2795 :
2796 87936 : if (cur_em->em_is_const)
2797 2232 : continue; /* ignore consts here */
2798 :
2799 : /*
2800 : * We consider only original EC members here, not
2801 : * already-transformed child members.
2802 : */
2803 85704 : if (cur_em->em_is_child)
2804 66074 : continue; /* ignore children here */
2805 :
2806 : /*
2807 : * We may ignore expressions that reference a single baserel,
2808 : * because add_child_rel_equivalences should have handled them.
2809 : */
2810 19630 : if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2811 17008 : continue;
2812 :
2813 : /* Does this member reference child's topmost parent rel? */
2814 2622 : if (bms_overlap(cur_em->em_relids, top_parent_relids))
2815 : {
2816 : /* Yes, generate transformed child version */
2817 : Expr *child_expr;
2818 : Relids new_relids;
2819 :
2820 2622 : if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2821 : {
2822 : /* Simple single-level transformation */
2823 : child_expr = (Expr *)
2824 2526 : adjust_appendrel_attrs(root,
2825 2526 : (Node *) cur_em->em_expr,
2826 : nappinfos, appinfos);
2827 : }
2828 : else
2829 : {
2830 : /* Must do multi-level transformation */
2831 : Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2832 : child_expr = (Expr *)
2833 96 : adjust_appendrel_attrs_multilevel(root,
2834 96 : (Node *) cur_em->em_expr,
2835 : child_joinrel,
2836 96 : child_joinrel->top_parent);
2837 : }
2838 :
2839 : /*
2840 : * Transform em_relids to match. Note we do *not* do
2841 : * pull_varnos(child_expr) here, as for example the
2842 : * transformation might have substituted a constant, but we
2843 : * don't want the child member to be marked as constant.
2844 : */
2845 2622 : new_relids = bms_difference(cur_em->em_relids,
2846 : top_parent_relids);
2847 2622 : new_relids = bms_add_members(new_relids, child_relids);
2848 :
2849 2622 : (void) add_eq_member(cur_ec, child_expr, new_relids,
2850 : cur_em->em_jdomain,
2851 : cur_em, cur_em->em_datatype);
2852 : }
2853 : }
2854 : }
2855 :
2856 4180 : MemoryContextSwitchTo(oldcontext);
2857 4180 : }
2858 :
2859 :
2860 : /*
2861 : * generate_implied_equalities_for_column
2862 : * Create EC-derived joinclauses usable with a specific column.
2863 : *
2864 : * This is used by indxpath.c to extract potentially indexable joinclauses
2865 : * from ECs, and can be used by foreign data wrappers for similar purposes.
2866 : * We assume that only expressions in Vars of a single table are of interest,
2867 : * but the caller provides a callback function to identify exactly which
2868 : * such expressions it would like to know about.
2869 : *
2870 : * We assume that any given table/index column could appear in only one EC.
2871 : * (This should be true in all but the most pathological cases, and if it
2872 : * isn't, we stop on the first match anyway.) Therefore, what we return
2873 : * is a redundant list of clauses equating the table/index column to each of
2874 : * the other-relation values it is known to be equal to. Any one of
2875 : * these clauses can be used to create a parameterized path, and there
2876 : * is no value in using more than one. (But it *is* worthwhile to create
2877 : * a separate parameterized path for each one, since that leads to different
2878 : * join orders.)
2879 : *
2880 : * The caller can pass a Relids set of rels we aren't interested in joining
2881 : * to, so as to save the work of creating useless clauses.
2882 : */
2883 : List *
2884 432776 : generate_implied_equalities_for_column(PlannerInfo *root,
2885 : RelOptInfo *rel,
2886 : ec_matches_callback_type callback,
2887 : void *callback_arg,
2888 : Relids prohibited_rels)
2889 : {
2890 432776 : List *result = NIL;
2891 432776 : bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2892 : Relids parent_relids;
2893 : int i;
2894 :
2895 : /* Should be OK to rely on eclass_indexes */
2896 : Assert(root->ec_merging_done);
2897 :
2898 : /* Indexes are available only on base or "other" member relations. */
2899 : Assert(IS_SIMPLE_REL(rel));
2900 :
2901 : /* If it's a child rel, we'll need to know what its parent(s) are */
2902 432776 : if (is_child_rel)
2903 10010 : parent_relids = find_childrel_parents(root, rel);
2904 : else
2905 422766 : parent_relids = NULL; /* not used, but keep compiler quiet */
2906 :
2907 432776 : i = -1;
2908 1134366 : while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
2909 : {
2910 772856 : EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2911 : EquivalenceMember *cur_em;
2912 : ListCell *lc2;
2913 :
2914 : /* Sanity check eclass_indexes only contain ECs for rel */
2915 : Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
2916 :
2917 : /*
2918 : * Won't generate joinclauses if const or single-member (the latter
2919 : * test covers the volatile case too)
2920 : */
2921 772856 : if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2922 414010 : continue;
2923 :
2924 : /*
2925 : * Scan members, looking for a match to the target column. Note that
2926 : * child EC members are considered, but only when they belong to the
2927 : * target relation. (Unlike regular members, the same expression
2928 : * could be a child member of more than one EC. Therefore, it's
2929 : * potentially order-dependent which EC a child relation's target
2930 : * column gets matched to. This is annoying but it only happens in
2931 : * corner cases, so for now we live with just reporting the first
2932 : * match. See also get_eclass_for_sort_expr.)
2933 : */
2934 358846 : cur_em = NULL;
2935 1069934 : foreach(lc2, cur_ec->ec_members)
2936 : {
2937 782658 : cur_em = (EquivalenceMember *) lfirst(lc2);
2938 1142148 : if (bms_equal(cur_em->em_relids, rel->relids) &&
2939 359490 : callback(root, rel, cur_ec, cur_em, callback_arg))
2940 71570 : break;
2941 711088 : cur_em = NULL;
2942 : }
2943 :
2944 358846 : if (!cur_em)
2945 287276 : continue;
2946 :
2947 : /*
2948 : * Found our match. Scan the other EC members and attempt to generate
2949 : * joinclauses.
2950 : */
2951 236888 : foreach(lc2, cur_ec->ec_members)
2952 : {
2953 165318 : EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2954 : Oid eq_op;
2955 : RestrictInfo *rinfo;
2956 :
2957 165318 : if (other_em->em_is_child)
2958 19124 : continue; /* ignore children here */
2959 :
2960 : /* Make sure it'll be a join to a different rel */
2961 223520 : if (other_em == cur_em ||
2962 77326 : bms_overlap(other_em->em_relids, rel->relids))
2963 69152 : continue;
2964 :
2965 : /* Forget it if caller doesn't want joins to this rel */
2966 77042 : if (bms_overlap(other_em->em_relids, prohibited_rels))
2967 6 : continue;
2968 :
2969 : /*
2970 : * Also, if this is a child rel, avoid generating a useless join
2971 : * to its parent rel(s).
2972 : */
2973 82952 : if (is_child_rel &&
2974 5916 : bms_overlap(parent_relids, other_em->em_relids))
2975 2714 : continue;
2976 :
2977 74322 : eq_op = select_equality_operator(cur_ec,
2978 : cur_em->em_datatype,
2979 : other_em->em_datatype);
2980 74322 : if (!OidIsValid(eq_op))
2981 0 : continue;
2982 :
2983 : /* set parent_ec to mark as redundant with other joinclauses */
2984 74322 : rinfo = create_join_clause(root, cur_ec, eq_op,
2985 : cur_em, other_em,
2986 : cur_ec);
2987 :
2988 74322 : result = lappend(result, rinfo);
2989 : }
2990 :
2991 : /*
2992 : * If somehow we failed to create any join clauses, we might as well
2993 : * keep scanning the ECs for another match. But if we did make any,
2994 : * we're done, because we don't want to return non-redundant clauses.
2995 : */
2996 71570 : if (result)
2997 71266 : break;
2998 : }
2999 :
3000 432776 : return result;
3001 : }
3002 :
3003 : /*
3004 : * have_relevant_eclass_joinclause
3005 : * Detect whether there is an EquivalenceClass that could produce
3006 : * a joinclause involving the two given relations.
3007 : *
3008 : * This is essentially a very cut-down version of
3009 : * generate_join_implied_equalities(). Note it's OK to occasionally say "yes"
3010 : * incorrectly. Hence we don't bother with details like whether the lack of a
3011 : * cross-type operator might prevent the clause from actually being generated.
3012 : * False negatives are not always fatal either: they will discourage, but not
3013 : * completely prevent, investigation of particular join pathways.
3014 : */
3015 : bool
3016 126050 : have_relevant_eclass_joinclause(PlannerInfo *root,
3017 : RelOptInfo *rel1, RelOptInfo *rel2)
3018 : {
3019 : Bitmapset *matching_ecs;
3020 : int i;
3021 :
3022 : /*
3023 : * Examine only eclasses mentioning both rel1 and rel2.
3024 : *
3025 : * Note that we do not consider the possibility of an eclass generating
3026 : * "join" clauses that mention just one of the rels plus an outer join
3027 : * that could be formed from them. Although such clauses must be
3028 : * correctly enforced when we form the outer join, they don't seem like
3029 : * sufficient reason to prioritize this join over other ones. The join
3030 : * ordering rules will force the join to be made when necessary.
3031 : */
3032 126050 : matching_ecs = get_common_eclass_indexes(root, rel1->relids,
3033 : rel2->relids);
3034 :
3035 126050 : i = -1;
3036 126050 : while ((i = bms_next_member(matching_ecs, i)) >= 0)
3037 : {
3038 104852 : EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3039 : i);
3040 :
3041 : /*
3042 : * Sanity check that get_common_eclass_indexes gave only ECs
3043 : * containing both rels.
3044 : */
3045 : Assert(bms_overlap(rel1->relids, ec->ec_relids));
3046 : Assert(bms_overlap(rel2->relids, ec->ec_relids));
3047 :
3048 : /*
3049 : * Won't generate joinclauses if single-member (this test covers the
3050 : * volatile case too)
3051 : */
3052 104852 : if (list_length(ec->ec_members) <= 1)
3053 0 : continue;
3054 :
3055 : /*
3056 : * We do not need to examine the individual members of the EC, because
3057 : * all that we care about is whether each rel overlaps the relids of
3058 : * at least one member, and get_common_eclass_indexes() and the single
3059 : * member check above are sufficient to prove that. (As with
3060 : * have_relevant_joinclause(), it is not necessary that the EC be able
3061 : * to form a joinclause relating exactly the two given rels, only that
3062 : * it be able to form a joinclause mentioning both, and this will
3063 : * surely be true if both of them overlap ec_relids.)
3064 : *
3065 : * Note we don't test ec_broken; if we did, we'd need a separate code
3066 : * path to look through ec_sources. Checking the membership anyway is
3067 : * OK as a possibly-overoptimistic heuristic.
3068 : *
3069 : * We don't test ec_has_const either, even though a const eclass won't
3070 : * generate real join clauses. This is because if we had "WHERE a.x =
3071 : * b.y and a.x = 42", it is worth considering a join between a and b,
3072 : * since the join result is likely to be small even though it'll end
3073 : * up being an unqualified nestloop.
3074 : */
3075 :
3076 104852 : return true;
3077 : }
3078 :
3079 21198 : return false;
3080 : }
3081 :
3082 :
3083 : /*
3084 : * has_relevant_eclass_joinclause
3085 : * Detect whether there is an EquivalenceClass that could produce
3086 : * a joinclause involving the given relation and anything else.
3087 : *
3088 : * This is the same as have_relevant_eclass_joinclause with the other rel
3089 : * implicitly defined as "everything else in the query".
3090 : */
3091 : bool
3092 160544 : has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
3093 : {
3094 : Bitmapset *matched_ecs;
3095 : int i;
3096 :
3097 : /* Examine only eclasses mentioning rel1 */
3098 160544 : matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
3099 :
3100 160544 : i = -1;
3101 572498 : while ((i = bms_next_member(matched_ecs, i)) >= 0)
3102 : {
3103 462676 : EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3104 : i);
3105 :
3106 : /*
3107 : * Won't generate joinclauses if single-member (this test covers the
3108 : * volatile case too)
3109 : */
3110 462676 : if (list_length(ec->ec_members) <= 1)
3111 226546 : continue;
3112 :
3113 : /*
3114 : * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3115 : * to find an EC that mentions both this rel and some other rel.
3116 : */
3117 236130 : if (!bms_is_subset(ec->ec_relids, rel1->relids))
3118 50722 : return true;
3119 : }
3120 :
3121 109822 : return false;
3122 : }
3123 :
3124 :
3125 : /*
3126 : * eclass_useful_for_merging
3127 : * Detect whether the EC could produce any mergejoinable join clauses
3128 : * against the specified relation.
3129 : *
3130 : * This is just a heuristic test and doesn't have to be exact; it's better
3131 : * to say "yes" incorrectly than "no". Hence we don't bother with details
3132 : * like whether the lack of a cross-type operator might prevent the clause
3133 : * from actually being generated.
3134 : */
3135 : bool
3136 512874 : eclass_useful_for_merging(PlannerInfo *root,
3137 : EquivalenceClass *eclass,
3138 : RelOptInfo *rel)
3139 : {
3140 : Relids relids;
3141 : ListCell *lc;
3142 :
3143 : Assert(!eclass->ec_merged);
3144 :
3145 : /*
3146 : * Won't generate joinclauses if const or single-member (the latter test
3147 : * covers the volatile case too)
3148 : */
3149 512874 : if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
3150 39824 : return false;
3151 :
3152 : /*
3153 : * Note we don't test ec_broken; if we did, we'd need a separate code path
3154 : * to look through ec_sources. Checking the members anyway is OK as a
3155 : * possibly-overoptimistic heuristic.
3156 : */
3157 :
3158 : /* If specified rel is a child, we must consider the topmost parent rel */
3159 473050 : if (IS_OTHER_REL(rel))
3160 : {
3161 : Assert(!bms_is_empty(rel->top_parent_relids));
3162 10200 : relids = rel->top_parent_relids;
3163 : }
3164 : else
3165 462850 : relids = rel->relids;
3166 :
3167 : /* If rel already includes all members of eclass, no point in searching */
3168 473050 : if (bms_is_subset(eclass->ec_relids, relids))
3169 182446 : return false;
3170 :
3171 : /* To join, we need a member not in the given rel */
3172 449712 : foreach(lc, eclass->ec_members)
3173 : {
3174 449190 : EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
3175 :
3176 449190 : if (cur_em->em_is_child)
3177 0 : continue; /* ignore children here */
3178 :
3179 449190 : if (!bms_overlap(cur_em->em_relids, relids))
3180 290082 : return true;
3181 : }
3182 :
3183 522 : return false;
3184 : }
3185 :
3186 :
3187 : /*
3188 : * is_redundant_derived_clause
3189 : * Test whether rinfo is derived from same EC as any clause in clauselist;
3190 : * if so, it can be presumed to represent a condition that's redundant
3191 : * with that member of the list.
3192 : */
3193 : bool
3194 72 : is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist)
3195 : {
3196 72 : EquivalenceClass *parent_ec = rinfo->parent_ec;
3197 : ListCell *lc;
3198 :
3199 : /* Fail if it's not a potentially-redundant clause from some EC */
3200 72 : if (parent_ec == NULL)
3201 72 : return false;
3202 :
3203 0 : foreach(lc, clauselist)
3204 : {
3205 0 : RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
3206 :
3207 0 : if (otherrinfo->parent_ec == parent_ec)
3208 0 : return true;
3209 : }
3210 :
3211 0 : return false;
3212 : }
3213 :
3214 : /*
3215 : * is_redundant_with_indexclauses
3216 : * Test whether rinfo is redundant with any clause in the IndexClause
3217 : * list. Here, for convenience, we test both simple identity and
3218 : * whether it is derived from the same EC as any member of the list.
3219 : */
3220 : bool
3221 1070430 : is_redundant_with_indexclauses(RestrictInfo *rinfo, List *indexclauses)
3222 : {
3223 1070430 : EquivalenceClass *parent_ec = rinfo->parent_ec;
3224 : ListCell *lc;
3225 :
3226 1483850 : foreach(lc, indexclauses)
3227 : {
3228 1110240 : IndexClause *iclause = lfirst_node(IndexClause, lc);
3229 1110240 : RestrictInfo *otherrinfo = iclause->rinfo;
3230 :
3231 : /* If indexclause is lossy, it won't enforce the condition exactly */
3232 1110240 : if (iclause->lossy)
3233 33958 : continue;
3234 :
3235 : /* Match if it's same clause (pointer equality should be enough) */
3236 1076282 : if (rinfo == otherrinfo)
3237 696820 : return true;
3238 : /* Match if derived from same EC */
3239 379980 : if (parent_ec && otherrinfo->parent_ec == parent_ec)
3240 518 : return true;
3241 :
3242 : /*
3243 : * No need to look at the derived clauses in iclause->indexquals; they
3244 : * couldn't match if the parent clause didn't.
3245 : */
3246 : }
3247 :
3248 373610 : return false;
3249 : }
3250 :
3251 : /*
3252 : * get_eclass_indexes_for_relids
3253 : * Build and return a Bitmapset containing the indexes into root's
3254 : * eq_classes list for all eclasses that mention any of these relids
3255 : */
3256 : static Bitmapset *
3257 766200 : get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
3258 : {
3259 766200 : Bitmapset *ec_indexes = NULL;
3260 766200 : int i = -1;
3261 :
3262 : /* Should be OK to rely on eclass_indexes */
3263 : Assert(root->ec_merging_done);
3264 :
3265 2483246 : while ((i = bms_next_member(relids, i)) > 0)
3266 : {
3267 1717046 : RelOptInfo *rel = root->simple_rel_array[i];
3268 :
3269 1717046 : if (rel == NULL) /* must be an outer join */
3270 : {
3271 : Assert(bms_is_member(i, root->outer_join_rels));
3272 268956 : continue;
3273 : }
3274 :
3275 1448090 : ec_indexes = bms_add_members(ec_indexes, rel->eclass_indexes);
3276 : }
3277 766200 : return ec_indexes;
3278 : }
3279 :
3280 : /*
3281 : * get_common_eclass_indexes
3282 : * Build and return a Bitmapset containing the indexes into root's
3283 : * eq_classes list for all eclasses that mention rels in both
3284 : * relids1 and relids2.
3285 : */
3286 : static Bitmapset *
3287 431218 : get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
3288 : {
3289 : Bitmapset *rel1ecs;
3290 : Bitmapset *rel2ecs;
3291 : int relid;
3292 :
3293 431218 : rel1ecs = get_eclass_indexes_for_relids(root, relids1);
3294 :
3295 : /*
3296 : * We can get away with just using the relation's eclass_indexes directly
3297 : * when relids2 is a singleton set.
3298 : */
3299 431218 : if (bms_get_singleton_member(relids2, &relid))
3300 343880 : rel2ecs = root->simple_rel_array[relid]->eclass_indexes;
3301 : else
3302 87338 : rel2ecs = get_eclass_indexes_for_relids(root, relids2);
3303 :
3304 : /* Calculate and return the common EC indexes, recycling the left input. */
3305 431218 : return bms_int_members(rel1ecs, rel2ecs);
3306 : }
|
