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