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 260 of file orclauses.c.

References RelOptInfo::baserestrict_min_security, RelOptInfo::baserestrictinfo, bms_difference(), RestrictInfo::clause_relids, clause_selectivity(), SpecialJoinInfo::delay_upper_joins, JOIN_INNER, SpecialJoinInfo::jointype, lappend(), SpecialJoinInfo::lhs_strict, make_restrictinfo(), Min, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, RelOptInfo::relids, RestrictInfo::security_level, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, T_SpecialJoinInfo, and SpecialJoinInfo::type.

Referenced by extract_restriction_or_clauses().

262 {
263  RestrictInfo *or_rinfo;
264  Selectivity or_selec,
265  orig_selec;
266 
267  /*
268  * Build a RestrictInfo from the new OR clause. We can assume it's valid
269  * as a base restriction clause.
270  */
271  or_rinfo = make_restrictinfo(root,
272  orclause,
273  true,
274  false,
275  false,
276  join_or_rinfo->security_level,
277  NULL,
278  NULL,
279  NULL);
280 
281  /*
282  * Estimate its selectivity. (We could have done this earlier, but doing
283  * it on the RestrictInfo representation allows the result to get cached,
284  * saving work later.)
285  */
286  or_selec = clause_selectivity(root, (Node *) or_rinfo,
287  0, JOIN_INNER, NULL);
288 
289  /*
290  * The clause is only worth adding to the query if it rejects a useful
291  * fraction of the base relation's rows; otherwise, it's just going to
292  * cause duplicate computation (since we will still have to check the
293  * original OR clause when the join is formed). Somewhat arbitrarily, we
294  * set the selectivity threshold at 0.9.
295  */
296  if (or_selec > 0.9)
297  return; /* forget it */
298 
299  /*
300  * OK, add it to the rel's restriction-clause list.
301  */
302  rel->baserestrictinfo = lappend(rel->baserestrictinfo, or_rinfo);
304  or_rinfo->security_level);
305 
306  /*
307  * Adjust the original join OR clause's cached selectivity to compensate
308  * for the selectivity of the added (but redundant) lower-level qual. This
309  * should result in the join rel getting approximately the same rows
310  * estimate as it would have gotten without all these shenanigans.
311  *
312  * XXX major hack alert: this depends on the assumption that the
313  * selectivity will stay cached.
314  *
315  * XXX another major hack: we adjust only norm_selec, the cached
316  * selectivity for JOIN_INNER semantics, even though the join clause
317  * might've been an outer-join clause. This is partly because we can't
318  * easily identify the relevant SpecialJoinInfo here, and partly because
319  * the linearity assumption we're making would fail anyway. (If it is an
320  * outer-join clause, "rel" must be on the nullable side, else we'd not
321  * have gotten here. So the computation of the join size is going to be
322  * quite nonlinear with respect to the size of "rel", so it's not clear
323  * how we ought to adjust outer_selec even if we could compute its
324  * original value correctly.)
325  */
326  if (or_selec > 0)
327  {
328  SpecialJoinInfo sjinfo;
329 
330  /*
331  * Make up a SpecialJoinInfo for JOIN_INNER semantics. (Compare
332  * approx_tuple_count() in costsize.c.)
333  */
334  sjinfo.type = T_SpecialJoinInfo;
335  sjinfo.min_lefthand = bms_difference(join_or_rinfo->clause_relids,
336  rel->relids);
337  sjinfo.min_righthand = rel->relids;
338  sjinfo.syn_lefthand = sjinfo.min_lefthand;
339  sjinfo.syn_righthand = sjinfo.min_righthand;
340  sjinfo.jointype = JOIN_INNER;
341  /* we don't bother trying to make the remaining fields valid */
342  sjinfo.lhs_strict = false;
343  sjinfo.delay_upper_joins = 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, in particular not "redundant" */
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 }
#define NIL
Definition: pg_list.h:65
Index security_level
Definition: pathnodes.h:2060
Relids min_righthand
Definition: pathnodes.h:2242
List * baserestrictinfo
Definition: pathnodes.h:740
Relids clause_relids
Definition: pathnodes.h:2063
#define Min(x, y)
Definition: c.h:986
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:291
Definition: nodes.h:539
Index baserestrict_min_security
Definition: pathnodes.h:742
double Selectivity
Definition: nodes.h:672
Relids syn_lefthand
Definition: pathnodes.h:2243
Selectivity norm_selec
Definition: pathnodes.h:2086
Relids syn_righthand
Definition: pathnodes.h:2244
List * semi_rhs_exprs
Definition: pathnodes.h:2252
Selectivity clause_selectivity(PlannerInfo *root, Node *clause, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:690
Relids relids
Definition: pathnodes.h:676
RestrictInfo * make_restrictinfo(PlannerInfo *root, Expr *clause, bool is_pushed_down, bool outerjoin_delayed, bool pseudoconstant, Index security_level, Relids required_relids, Relids outer_relids, Relids nullable_relids)
Definition: restrictinfo.c:61
List * lappend(List *list, void *datum)
Definition: list.c:336
bool delay_upper_joins
Definition: pathnodes.h:2247
JoinType jointype
Definition: pathnodes.h:2245
List * semi_operators
Definition: pathnodes.h:2251
Relids min_lefthand
Definition: pathnodes.h:2241

◆ extract_or_clause()

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

Definition at line 162 of file orclauses.c.

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, RestrictInfo::orclause, and restriction_is_or_clause().

Referenced by extract_restriction_or_clauses().

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

◆ extract_restriction_or_clauses()

void extract_restriction_or_clauses ( PlannerInfo root)

Definition at line 76 of file orclauses.c.

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

Referenced by query_planner().

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  * However, it seems best to ignore clauses that have been marked
103  * redundant (by setting norm_selec > 1). That likely can't happen
104  * for OR clauses, but let's be safe.
105  */
106  foreach(lc, rel->joininfo)
107  {
108  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
109 
110  if (restriction_is_or_clause(rinfo) &&
111  join_clause_is_movable_to(rinfo, rel) &&
112  rinfo->norm_selec <= 1)
113  {
114  /* Try to extract a qual for this rel only */
115  Expr *orclause = extract_or_clause(rinfo, rel);
116 
117  /*
118  * If successful, decide whether we want to use the clause,
119  * and insert it into the rel's restrictinfo list if so.
120  */
121  if (orclause)
122  consider_new_or_clause(root, rel, orclause, rinfo);
123  }
124  }
125  }
126 }
RelOptKind reloptkind
Definition: pathnodes.h:673
static Expr * extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel)
Definition: orclauses.c:162
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:382
Selectivity norm_selec
Definition: pathnodes.h:2086
struct RelOptInfo ** simple_rel_array
Definition: pathnodes.h:185
List * joininfo
Definition: pathnodes.h:744
int simple_rel_array_size
Definition: pathnodes.h:186
Index relid
Definition: pathnodes.h:704
unsigned int Index
Definition: c.h:549
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:525
static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel, Expr *orclause, RestrictInfo *join_or_rinfo)
Definition: orclauses.c:260

◆ is_safe_restriction_clause_for()

static bool is_safe_restriction_clause_for ( RestrictInfo rinfo,
RelOptInfo rel 
)
static

Definition at line 132 of file orclauses.c.

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

Referenced by extract_or_clause().

133 {
134  /*
135  * We want clauses that mention the rel, and only the rel. So in
136  * particular pseudoconstant clauses can be rejected quickly. Then check
137  * the clause's Var membership.
138  */
139  if (rinfo->pseudoconstant)
140  return false;
141  if (!bms_equal(rinfo->clause_relids, rel->relids))
142  return false;
143 
144  /* We don't want extra evaluations of any volatile functions */
145  if (contain_volatile_functions((Node *) rinfo->clause))
146  return false;
147 
148  return true;
149 }
Relids clause_relids
Definition: pathnodes.h:2063
bool pseudoconstant
Definition: pathnodes.h:2053
Definition: nodes.h:539
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:448
Relids relids
Definition: pathnodes.h:676
Expr * clause
Definition: pathnodes.h:2045
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94