PostgreSQL Source Code  git master
orclauses.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * orclauses.c
4  * Routines to extract restriction OR clauses from join OR clauses
5  *
6  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/optimizer/util/orclauses.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 
16 #include "postgres.h"
17 
18 #include "nodes/makefuncs.h"
19 #include "nodes/nodeFuncs.h"
20 #include "optimizer/clauses.h"
21 #include "optimizer/cost.h"
22 #include "optimizer/optimizer.h"
23 #include "optimizer/orclauses.h"
24 #include "optimizer/restrictinfo.h"
25 
26 
28 static Expr *extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel);
29 static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
30  Expr *orclause, RestrictInfo *join_or_rinfo);
31 
32 
33 /*
34  * extract_restriction_or_clauses
35  * Examine join OR-of-AND clauses to see if any useful restriction OR
36  * clauses can be extracted. If so, add them to the query.
37  *
38  * Although a join clause must reference multiple relations overall,
39  * an OR of ANDs clause might contain sub-clauses that reference just one
40  * relation and can be used to build a restriction clause for that rel.
41  * For example consider
42  * WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
43  * We can transform this into
44  * WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
45  * AND (a.x = 42 OR a.x = 44)
46  * AND (b.y = 43 OR b.z = 45);
47  * which allows the latter clauses to be applied during the scans of a and b,
48  * perhaps as index qualifications, and in any case reducing the number of
49  * rows arriving at the join. In essence this is a partial transformation to
50  * CNF (AND of ORs format). It is not complete, however, because we do not
51  * unravel the original OR --- doing so would usually bloat the qualification
52  * expression to little gain.
53  *
54  * The added quals are partially redundant with the original OR, and therefore
55  * would cause the size of the joinrel to be underestimated when it is finally
56  * formed. (This would be true of a full transformation to CNF as well; the
57  * fault is not really in the transformation, but in clauselist_selectivity's
58  * inability to recognize redundant conditions.) We can compensate for this
59  * redundancy by changing the cached selectivity of the original OR clause,
60  * canceling out the (valid) reduction in the estimated sizes of the base
61  * relations so that the estimated joinrel size remains the same. This is
62  * a MAJOR HACK: it depends on the fact that clause selectivities are cached
63  * and on the fact that the same RestrictInfo node will appear in every
64  * joininfo list that might be used when the joinrel is formed.
65  * And it doesn't work in cases where the size estimation is nonlinear
66  * (i.e., outer and IN joins). But it beats not doing anything.
67  *
68  * We examine each base relation to see if join clauses associated with it
69  * contain extractable restriction conditions. If so, add those conditions
70  * to the rel's baserestrictinfo and update the cached selectivities of the
71  * join clauses. Note that the same join clause will be examined afresh
72  * from the point of view of each baserel that participates in it, so its
73  * cached selectivity may get updated multiple times.
74  */
75 void
77 {
78  Index rti;
79 
80  /* Examine each baserel for potential join OR clauses */
81  for (rti = 1; rti < root->simple_rel_array_size; rti++)
82  {
83  RelOptInfo *rel = root->simple_rel_array[rti];
84  ListCell *lc;
85 
86  /* there may be empty slots corresponding to non-baserel RTEs */
87  if (rel == NULL)
88  continue;
89 
90  Assert(rel->relid == rti); /* sanity check on array */
91 
92  /* ignore RTEs that are "other rels" */
93  if (rel->reloptkind != RELOPT_BASEREL)
94  continue;
95 
96  /*
97  * Find potentially interesting OR joinclauses. We can use any
98  * joinclause that is considered safe to move to this rel by the
99  * parameterized-path machinery, even though what we are going to do
100  * with it is not exactly a parameterized path.
101  */
102  foreach(lc, rel->joininfo)
103  {
104  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
105 
106  if (restriction_is_or_clause(rinfo) &&
107  join_clause_is_movable_to(rinfo, rel))
108  {
109  /* Try to extract a qual for this rel only */
110  Expr *orclause = extract_or_clause(rinfo, rel);
111 
112  /*
113  * If successful, decide whether we want to use the clause,
114  * and insert it into the rel's restrictinfo list if so.
115  */
116  if (orclause)
117  consider_new_or_clause(root, rel, orclause, rinfo);
118  }
119  }
120  }
121 }
122 
123 /*
124  * Is the given primitive (non-OR) RestrictInfo safe to move to the rel?
125  */
126 static bool
128 {
129  /*
130  * We want clauses that mention the rel, and only the rel. So in
131  * particular pseudoconstant clauses can be rejected quickly. Then check
132  * the clause's Var membership.
133  */
134  if (rinfo->pseudoconstant)
135  return false;
136  if (!bms_equal(rinfo->clause_relids, rel->relids))
137  return false;
138 
139  /* We don't want extra evaluations of any volatile functions */
140  if (contain_volatile_functions((Node *) rinfo->clause))
141  return false;
142 
143  return true;
144 }
145 
146 /*
147  * Try to extract a restriction clause mentioning only "rel" from the given
148  * join OR-clause.
149  *
150  * We must be able to extract at least one qual for this rel from each of
151  * the arms of the OR, else we can't use it.
152  *
153  * Returns an OR clause (not a RestrictInfo!) pertaining to rel, or NULL
154  * if no OR clause could be extracted.
155  */
156 static Expr *
158 {
159  List *clauselist = NIL;
160  ListCell *lc;
161 
162  /*
163  * Scan each arm of the input OR clause. Notice we descend into
164  * or_rinfo->orclause, which has RestrictInfo nodes embedded below the
165  * toplevel OR/AND structure. This is useful because we can use the info
166  * in those nodes to make is_safe_restriction_clause_for()'s checks
167  * cheaper. We'll strip those nodes from the returned tree, though,
168  * meaning that fresh ones will be built if the clause is accepted as a
169  * restriction clause. This might seem wasteful --- couldn't we re-use
170  * the existing RestrictInfos? But that'd require assuming that
171  * selectivity and other cached data is computed exactly the same way for
172  * a restriction clause as for a join clause, which seems undesirable.
173  */
174  Assert(is_orclause(or_rinfo->orclause));
175  foreach(lc, ((BoolExpr *) or_rinfo->orclause)->args)
176  {
177  Node *orarg = (Node *) lfirst(lc);
178  List *subclauses = NIL;
179  Node *subclause;
180 
181  /* OR arguments should be ANDs or sub-RestrictInfos */
182  if (is_andclause(orarg))
183  {
184  List *andargs = ((BoolExpr *) orarg)->args;
185  ListCell *lc2;
186 
187  foreach(lc2, andargs)
188  {
189  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
190 
191  if (restriction_is_or_clause(rinfo))
192  {
193  /*
194  * Recurse to deal with nested OR. Note we *must* recurse
195  * here, this isn't just overly-tense optimization: we
196  * have to descend far enough to find and strip all
197  * RestrictInfos in the expression.
198  */
199  Expr *suborclause;
200 
201  suborclause = extract_or_clause(rinfo, rel);
202  if (suborclause)
203  subclauses = lappend(subclauses, suborclause);
204  }
205  else if (is_safe_restriction_clause_for(rinfo, rel))
206  subclauses = lappend(subclauses, rinfo->clause);
207  }
208  }
209  else
210  {
211  RestrictInfo *rinfo = castNode(RestrictInfo, orarg);
212 
214  if (is_safe_restriction_clause_for(rinfo, rel))
215  subclauses = lappend(subclauses, rinfo->clause);
216  }
217 
218  /*
219  * If nothing could be extracted from this arm, we can't do anything
220  * with this OR clause.
221  */
222  if (subclauses == NIL)
223  return NULL;
224 
225  /*
226  * OK, add subclause(s) to the result OR. If we found more than one,
227  * we need an AND node. But if we found only one, and it is itself an
228  * OR node, add its subclauses to the result instead; this is needed
229  * to preserve AND/OR flatness (ie, no OR directly underneath OR).
230  */
231  subclause = (Node *) make_ands_explicit(subclauses);
232  if (is_orclause(subclause))
233  clauselist = list_concat(clauselist,
234  ((BoolExpr *) subclause)->args);
235  else
236  clauselist = lappend(clauselist, subclause);
237  }
238 
239  /*
240  * If we got a restriction clause from every arm, wrap them up in an OR
241  * node. (In theory the OR node might be unnecessary, if there was only
242  * one arm --- but then the input OR node was also redundant.)
243  */
244  if (clauselist != NIL)
245  return make_orclause(clauselist);
246  return NULL;
247 }
248 
249 /*
250  * Consider whether a successfully-extracted restriction OR clause is
251  * actually worth using. If so, add it to the planner's data structures,
252  * and adjust the original join clause (join_or_rinfo) to compensate.
253  */
254 static void
256  Expr *orclause, RestrictInfo *join_or_rinfo)
257 {
258  RestrictInfo *or_rinfo;
259  Selectivity or_selec,
260  orig_selec;
261 
262  /*
263  * Build a RestrictInfo from the new OR clause. We can assume it's valid
264  * as a base restriction clause.
265  */
266  or_rinfo = make_restrictinfo(root,
267  orclause,
268  true,
269  false,
270  false,
271  false,
272  join_or_rinfo->security_level,
273  NULL,
274  NULL,
275  NULL);
276 
277  /*
278  * Estimate its selectivity. (We could have done this earlier, but doing
279  * it on the RestrictInfo representation allows the result to get cached,
280  * saving work later.)
281  */
282  or_selec = clause_selectivity(root, (Node *) or_rinfo,
283  0, JOIN_INNER, NULL);
284 
285  /*
286  * The clause is only worth adding to the query if it rejects a useful
287  * fraction of the base relation's rows; otherwise, it's just going to
288  * cause duplicate computation (since we will still have to check the
289  * original OR clause when the join is formed). Somewhat arbitrarily, we
290  * set the selectivity threshold at 0.9.
291  */
292  if (or_selec > 0.9)
293  return; /* forget it */
294 
295  /*
296  * OK, add it to the rel's restriction-clause list.
297  */
298  rel->baserestrictinfo = lappend(rel->baserestrictinfo, or_rinfo);
300  or_rinfo->security_level);
301 
302  /*
303  * Adjust the original join OR clause's cached selectivity to compensate
304  * for the selectivity of the added (but redundant) lower-level qual. This
305  * should result in the join rel getting approximately the same rows
306  * estimate as it would have gotten without all these shenanigans.
307  *
308  * XXX major hack alert: this depends on the assumption that the
309  * selectivity will stay cached.
310  *
311  * XXX another major hack: we adjust only norm_selec, the cached
312  * selectivity for JOIN_INNER semantics, even though the join clause
313  * might've been an outer-join clause. This is partly because we can't
314  * easily identify the relevant SpecialJoinInfo here, and partly because
315  * the linearity assumption we're making would fail anyway. (If it is an
316  * outer-join clause, "rel" must be on the nullable side, else we'd not
317  * have gotten here. So the computation of the join size is going to be
318  * quite nonlinear with respect to the size of "rel", so it's not clear
319  * how we ought to adjust outer_selec even if we could compute its
320  * original value correctly.)
321  */
322  if (or_selec > 0)
323  {
324  SpecialJoinInfo sjinfo;
325 
326  /*
327  * Make up a SpecialJoinInfo for JOIN_INNER semantics. (Compare
328  * approx_tuple_count() in costsize.c.)
329  */
330  sjinfo.type = T_SpecialJoinInfo;
331  sjinfo.min_lefthand = bms_difference(join_or_rinfo->clause_relids,
332  rel->relids);
333  sjinfo.min_righthand = rel->relids;
334  sjinfo.syn_lefthand = sjinfo.min_lefthand;
335  sjinfo.syn_righthand = sjinfo.min_righthand;
336  sjinfo.jointype = JOIN_INNER;
337  sjinfo.ojrelid = 0;
338  sjinfo.commute_above_l = NULL;
339  sjinfo.commute_above_r = NULL;
340  sjinfo.commute_below_l = NULL;
341  sjinfo.commute_below_r = NULL;
342  /* we don't bother trying to make the remaining fields valid */
343  sjinfo.lhs_strict = false;
344  sjinfo.semi_can_btree = false;
345  sjinfo.semi_can_hash = false;
346  sjinfo.semi_operators = NIL;
347  sjinfo.semi_rhs_exprs = NIL;
348 
349  /* Compute inner-join size */
350  orig_selec = clause_selectivity(root, (Node *) join_or_rinfo,
351  0, JOIN_INNER, &sjinfo);
352 
353  /* And hack cached selectivity so join size remains the same */
354  join_or_rinfo->norm_selec = orig_selec / or_selec;
355  /* ensure result stays in sane range */
356  if (join_or_rinfo->norm_selec > 1)
357  join_or_rinfo->norm_selec = 1;
358  /* as explained above, we don't touch outer_selec */
359  }
360 }
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:97
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:297
#define Min(x, y)
Definition: c.h:993
unsigned int Index
Definition: c.h:603
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:483
Selectivity clause_selectivity(PlannerInfo *root, Node *clause, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:669
Assert(fmt[strlen(fmt) - 1] !='\n')
List * lappend(List *list, void *datum)
Definition: list.c:338
List * list_concat(List *list1, const List *list2)
Definition: list.c:560
Expr * make_ands_explicit(List *andclauses)
Definition: makefuncs.c:711
Expr * make_orclause(List *orclauses)
Definition: makefuncs.c:655
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:105
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:114
double Selectivity
Definition: nodes.h:261
#define castNode(_type_, nodeptr)
Definition: nodes.h:197
@ JOIN_INNER
Definition: nodes.h:304
void extract_restriction_or_clauses(PlannerInfo *root)
Definition: orclauses.c:76
static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel, Expr *orclause, RestrictInfo *join_or_rinfo)
Definition: orclauses.c:255
static Expr * extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel)
Definition: orclauses.c:157
static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: orclauses.c:127
@ RELOPT_BASEREL
Definition: pathnodes.h:812
#define lfirst(lc)
Definition: pg_list.h:172
#define lfirst_node(type, lc)
Definition: pg_list.h:176
#define NIL
Definition: pg_list.h:68
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:416
RestrictInfo * make_restrictinfo(PlannerInfo *root, Expr *clause, bool is_pushed_down, bool has_clone, bool is_clone, bool pseudoconstant, Index security_level, Relids required_relids, Relids incompatible_relids, Relids outer_relids)
Definition: restrictinfo.c:63
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:584
Definition: pg_list.h:54
Definition: nodes.h:129
int simple_rel_array_size
Definition: pathnodes.h:229
List * baserestrictinfo
Definition: pathnodes.h:964
List * joininfo
Definition: pathnodes.h:970
Relids relids
Definition: pathnodes.h:856
Index relid
Definition: pathnodes.h:903
RelOptKind reloptkind
Definition: pathnodes.h:850
Index baserestrict_min_security
Definition: pathnodes.h:968
Index security_level
Definition: pathnodes.h:2551
Expr * clause
Definition: pathnodes.h:2529
Relids commute_above_r
Definition: pathnodes.h:2860
Relids syn_lefthand
Definition: pathnodes.h:2855
Relids min_righthand
Definition: pathnodes.h:2854
List * semi_rhs_exprs
Definition: pathnodes.h:2868
Relids commute_above_l
Definition: pathnodes.h:2859
JoinType jointype
Definition: pathnodes.h:2857
Relids commute_below_l
Definition: pathnodes.h:2861
Relids min_lefthand
Definition: pathnodes.h:2853
Relids syn_righthand
Definition: pathnodes.h:2856
Relids commute_below_r
Definition: pathnodes.h:2862
List * semi_operators
Definition: pathnodes.h:2867