PostgreSQL Source Code  git master
orclauses.c File Reference
Include dependency graph for orclauses.c:

Go to the source code of this file.

Functions

static bool is_safe_restriction_clause_for (RestrictInfo *rinfo, RelOptInfo *rel)
 
static Exprextract_or_clause (RestrictInfo *or_rinfo, RelOptInfo *rel)
 
static void consider_new_or_clause (PlannerInfo *root, RelOptInfo *rel, Expr *orclause, RestrictInfo *join_or_rinfo)
 
void extract_restriction_or_clauses (PlannerInfo *root)
 

Function Documentation

◆ consider_new_or_clause()

static void consider_new_or_clause ( PlannerInfo root,
RelOptInfo rel,
Expr orclause,
RestrictInfo join_or_rinfo 
)
static

Definition at line 253 of file orclauses.c.

255 {
256  RestrictInfo *or_rinfo;
257  Selectivity or_selec,
258  orig_selec;
259 
260  /*
261  * Build a RestrictInfo from the new OR clause. We can assume it's valid
262  * as a base restriction clause.
263  */
264  or_rinfo = make_restrictinfo(root,
265  orclause,
266  true,
267  false,
268  false,
269  false,
270  join_or_rinfo->security_level,
271  NULL,
272  NULL,
273  NULL);
274 
275  /*
276  * Estimate its selectivity. (We could have done this earlier, but doing
277  * it on the RestrictInfo representation allows the result to get cached,
278  * saving work later.)
279  */
280  or_selec = clause_selectivity(root, (Node *) or_rinfo,
281  0, JOIN_INNER, NULL);
282 
283  /*
284  * The clause is only worth adding to the query if it rejects a useful
285  * fraction of the base relation's rows; otherwise, it's just going to
286  * cause duplicate computation (since we will still have to check the
287  * original OR clause when the join is formed). Somewhat arbitrarily, we
288  * set the selectivity threshold at 0.9.
289  */
290  if (or_selec > 0.9)
291  return; /* forget it */
292 
293  /*
294  * OK, add it to the rel's restriction-clause list.
295  */
296  rel->baserestrictinfo = lappend(rel->baserestrictinfo, or_rinfo);
298  or_rinfo->security_level);
299 
300  /*
301  * Adjust the original join OR clause's cached selectivity to compensate
302  * for the selectivity of the added (but redundant) lower-level qual. This
303  * should result in the join rel getting approximately the same rows
304  * estimate as it would have gotten without all these shenanigans.
305  *
306  * XXX major hack alert: this depends on the assumption that the
307  * selectivity will stay cached.
308  *
309  * XXX another major hack: we adjust only norm_selec, the cached
310  * selectivity for JOIN_INNER semantics, even though the join clause
311  * might've been an outer-join clause. This is partly because we can't
312  * easily identify the relevant SpecialJoinInfo here, and partly because
313  * the linearity assumption we're making would fail anyway. (If it is an
314  * outer-join clause, "rel" must be on the nullable side, else we'd not
315  * have gotten here. So the computation of the join size is going to be
316  * quite nonlinear with respect to the size of "rel", so it's not clear
317  * how we ought to adjust outer_selec even if we could compute its
318  * original value correctly.)
319  */
320  if (or_selec > 0)
321  {
322  SpecialJoinInfo sjinfo;
323 
324  /*
325  * Make up a SpecialJoinInfo for JOIN_INNER semantics. (Compare
326  * approx_tuple_count() in costsize.c.)
327  */
328  sjinfo.type = T_SpecialJoinInfo;
329  sjinfo.min_lefthand = bms_difference(join_or_rinfo->clause_relids,
330  rel->relids);
331  sjinfo.min_righthand = rel->relids;
332  sjinfo.syn_lefthand = sjinfo.min_lefthand;
333  sjinfo.syn_righthand = sjinfo.min_righthand;
334  sjinfo.jointype = JOIN_INNER;
335  sjinfo.ojrelid = 0;
336  sjinfo.commute_above_l = NULL;
337  sjinfo.commute_above_r = NULL;
338  sjinfo.commute_below_l = NULL;
339  sjinfo.commute_below_r = NULL;
340  /* we don't bother trying to make the remaining fields valid */
341  sjinfo.lhs_strict = false;
342  sjinfo.semi_can_btree = false;
343  sjinfo.semi_can_hash = false;
344  sjinfo.semi_operators = NIL;
345  sjinfo.semi_rhs_exprs = NIL;
346 
347  /* Compute inner-join size */
348  orig_selec = clause_selectivity(root, (Node *) join_or_rinfo,
349  0, JOIN_INNER, &sjinfo);
350 
351  /* And hack cached selectivity so join size remains the same */
352  join_or_rinfo->norm_selec = orig_selec / or_selec;
353  /* ensure result stays in sane range */
354  if (join_or_rinfo->norm_selec > 1)
355  join_or_rinfo->norm_selec = 1;
356  /* as explained above, we don't touch outer_selec */
357  }
358 }
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:346
#define Min(x, y)
Definition: c.h:991
Selectivity clause_selectivity(PlannerInfo *root, Node *clause, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:667
List * lappend(List *list, void *datum)
Definition: list.c:339
double Selectivity
Definition: nodes.h:240
@ JOIN_INNER
Definition: nodes.h:283
#define NIL
Definition: pg_list.h:68
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
Definition: nodes.h:129
List * baserestrictinfo
Definition: pathnodes.h:966
Relids relids
Definition: pathnodes.h:856
Index baserestrict_min_security
Definition: pathnodes.h:970
Index security_level
Definition: pathnodes.h:2563
Relids commute_above_r
Definition: pathnodes.h:2875
Relids syn_lefthand
Definition: pathnodes.h:2870
Relids min_righthand
Definition: pathnodes.h:2869
List * semi_rhs_exprs
Definition: pathnodes.h:2883
Relids commute_above_l
Definition: pathnodes.h:2874
JoinType jointype
Definition: pathnodes.h:2872
Relids commute_below_l
Definition: pathnodes.h:2876
Relids min_lefthand
Definition: pathnodes.h:2868
Relids syn_righthand
Definition: pathnodes.h:2871
Relids commute_below_r
Definition: pathnodes.h:2877
List * semi_operators
Definition: pathnodes.h:2882

References RelOptInfo::baserestrict_min_security, RelOptInfo::baserestrictinfo, bms_difference(), clause_selectivity(), SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, SpecialJoinInfo::commute_below_r, JOIN_INNER, SpecialJoinInfo::jointype, lappend(), SpecialJoinInfo::lhs_strict, make_restrictinfo(), Min, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SpecialJoinInfo::ojrelid, RelOptInfo::relids, RestrictInfo::security_level, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by extract_restriction_or_clauses().

◆ extract_or_clause()

static Expr * extract_or_clause ( RestrictInfo or_rinfo,
RelOptInfo rel 
)
static

Definition at line 155 of file orclauses.c.

156 {
157  List *clauselist = NIL;
158  ListCell *lc;
159 
160  /*
161  * Scan each arm of the input OR clause. Notice we descend into
162  * or_rinfo->orclause, which has RestrictInfo nodes embedded below the
163  * toplevel OR/AND structure. This is useful because we can use the info
164  * in those nodes to make is_safe_restriction_clause_for()'s checks
165  * cheaper. We'll strip those nodes from the returned tree, though,
166  * meaning that fresh ones will be built if the clause is accepted as a
167  * restriction clause. This might seem wasteful --- couldn't we re-use
168  * the existing RestrictInfos? But that'd require assuming that
169  * selectivity and other cached data is computed exactly the same way for
170  * a restriction clause as for a join clause, which seems undesirable.
171  */
172  Assert(is_orclause(or_rinfo->orclause));
173  foreach(lc, ((BoolExpr *) or_rinfo->orclause)->args)
174  {
175  Node *orarg = (Node *) lfirst(lc);
176  List *subclauses = NIL;
177  Node *subclause;
178 
179  /* OR arguments should be ANDs or sub-RestrictInfos */
180  if (is_andclause(orarg))
181  {
182  List *andargs = ((BoolExpr *) orarg)->args;
183  ListCell *lc2;
184 
185  foreach(lc2, andargs)
186  {
187  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
188 
189  if (restriction_is_or_clause(rinfo))
190  {
191  /*
192  * Recurse to deal with nested OR. Note we *must* recurse
193  * here, this isn't just overly-tense optimization: we
194  * have to descend far enough to find and strip all
195  * RestrictInfos in the expression.
196  */
197  Expr *suborclause;
198 
199  suborclause = extract_or_clause(rinfo, rel);
200  if (suborclause)
201  subclauses = lappend(subclauses, suborclause);
202  }
203  else if (is_safe_restriction_clause_for(rinfo, rel))
204  subclauses = lappend(subclauses, rinfo->clause);
205  }
206  }
207  else
208  {
209  RestrictInfo *rinfo = castNode(RestrictInfo, orarg);
210 
212  if (is_safe_restriction_clause_for(rinfo, rel))
213  subclauses = lappend(subclauses, rinfo->clause);
214  }
215 
216  /*
217  * If nothing could be extracted from this arm, we can't do anything
218  * with this OR clause.
219  */
220  if (subclauses == NIL)
221  return NULL;
222 
223  /*
224  * OK, add subclause(s) to the result OR. If we found more than one,
225  * we need an AND node. But if we found only one, and it is itself an
226  * OR node, add its subclauses to the result instead; this is needed
227  * to preserve AND/OR flatness (ie, no OR directly underneath OR).
228  */
229  subclause = (Node *) make_ands_explicit(subclauses);
230  if (is_orclause(subclause))
231  clauselist = list_concat(clauselist,
232  ((BoolExpr *) subclause)->args);
233  else
234  clauselist = lappend(clauselist, subclause);
235  }
236 
237  /*
238  * If we got a restriction clause from every arm, wrap them up in an OR
239  * node. (In theory the OR node might be unnecessary, if there was only
240  * one arm --- but then the input OR node was also redundant.)
241  */
242  if (clauselist != NIL)
243  return make_orclause(clauselist);
244  return NULL;
245 }
Assert(fmt[strlen(fmt) - 1] !='\n')
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
Expr * make_ands_explicit(List *andclauses)
Definition: makefuncs.c:710
Expr * make_orclause(List *orclauses)
Definition: makefuncs.c:654
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:105
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:114
#define castNode(_type_, nodeptr)
Definition: nodes.h:176
static Expr * extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel)
Definition: orclauses.c:155
static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: orclauses.c:125
#define lfirst(lc)
Definition: pg_list.h:172
#define lfirst_node(type, lc)
Definition: pg_list.h:176
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:416
Definition: pg_list.h:54
Expr * clause
Definition: pathnodes.h:2541

References Assert(), castNode, RestrictInfo::clause, is_andclause(), is_orclause(), is_safe_restriction_clause_for(), lappend(), lfirst, lfirst_node, list_concat(), make_ands_explicit(), make_orclause(), NIL, and restriction_is_or_clause().

Referenced by extract_restriction_or_clauses().

◆ extract_restriction_or_clauses()

void extract_restriction_or_clauses ( PlannerInfo root)

Definition at line 74 of file orclauses.c.

75 {
76  Index rti;
77 
78  /* Examine each baserel for potential join OR clauses */
79  for (rti = 1; rti < root->simple_rel_array_size; rti++)
80  {
81  RelOptInfo *rel = root->simple_rel_array[rti];
82  ListCell *lc;
83 
84  /* there may be empty slots corresponding to non-baserel RTEs */
85  if (rel == NULL)
86  continue;
87 
88  Assert(rel->relid == rti); /* sanity check on array */
89 
90  /* ignore RTEs that are "other rels" */
91  if (rel->reloptkind != RELOPT_BASEREL)
92  continue;
93 
94  /*
95  * Find potentially interesting OR joinclauses. We can use any
96  * joinclause that is considered safe to move to this rel by the
97  * parameterized-path machinery, even though what we are going to do
98  * with it is not exactly a parameterized path.
99  */
100  foreach(lc, rel->joininfo)
101  {
102  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
103 
104  if (restriction_is_or_clause(rinfo) &&
105  join_clause_is_movable_to(rinfo, rel))
106  {
107  /* Try to extract a qual for this rel only */
108  Expr *orclause = extract_or_clause(rinfo, rel);
109 
110  /*
111  * If successful, decide whether we want to use the clause,
112  * and insert it into the rel's restrictinfo list if so.
113  */
114  if (orclause)
115  consider_new_or_clause(root, rel, orclause, rinfo);
116  }
117  }
118  }
119 }
unsigned int Index
Definition: c.h:601
static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel, Expr *orclause, RestrictInfo *join_or_rinfo)
Definition: orclauses.c:253
@ RELOPT_BASEREL
Definition: pathnodes.h:812
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:584
int simple_rel_array_size
Definition: pathnodes.h:229
List * joininfo
Definition: pathnodes.h:972
Index relid
Definition: pathnodes.h:903
RelOptKind reloptkind
Definition: pathnodes.h:850

References Assert(), consider_new_or_clause(), extract_or_clause(), join_clause_is_movable_to(), RelOptInfo::joininfo, lfirst, RelOptInfo::relid, RELOPT_BASEREL, RelOptInfo::reloptkind, restriction_is_or_clause(), and PlannerInfo::simple_rel_array_size.

Referenced by query_planner().

◆ is_safe_restriction_clause_for()

static bool is_safe_restriction_clause_for ( RestrictInfo rinfo,
RelOptInfo rel 
)
static

Definition at line 125 of file orclauses.c.

126 {
127  /*
128  * We want clauses that mention the rel, and only the rel. So in
129  * particular pseudoconstant clauses can be rejected quickly. Then check
130  * the clause's Var membership.
131  */
132  if (rinfo->pseudoconstant)
133  return false;
134  if (!bms_equal(rinfo->clause_relids, rel->relids))
135  return false;
136 
137  /* We don't want extra evaluations of any volatile functions */
138  if (contain_volatile_functions((Node *) rinfo->clause))
139  return false;
140 
141  return true;
142 }
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:142
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:518

References bms_equal(), RestrictInfo::clause, contain_volatile_functions(), and RelOptInfo::relids.

Referenced by extract_or_clause().