equivclass.c source code [PostgreSQL/src/backend/optimizer/path/equivclass.c]

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

Browse the source code of PostgreSQL/src/backend/optimizer/path/equivclass.c