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