PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
orclauses.c File Reference
#include "postgres.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/orclauses.h"
#include "optimizer/restrictinfo.h"
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

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

Definition at line 257 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, RestrictInfo::norm_selec, 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().

259 {
260  RestrictInfo *or_rinfo;
261  Selectivity or_selec,
262  orig_selec;
263 
264  /*
265  * Build a RestrictInfo from the new OR clause. We can assume it's valid
266  * as a base restriction clause.
267  */
268  or_rinfo = make_restrictinfo(orclause,
269  true,
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  /* we don't bother trying to make the remaining fields valid */
338  sjinfo.lhs_strict = false;
339  sjinfo.delay_upper_joins = false;
340  sjinfo.semi_can_btree = false;
341  sjinfo.semi_can_hash = false;
342  sjinfo.semi_operators = NIL;
343  sjinfo.semi_rhs_exprs = NIL;
344 
345  /* Compute inner-join size */
346  orig_selec = clause_selectivity(root, (Node *) join_or_rinfo,
347  0, JOIN_INNER, &sjinfo);
348 
349  /* And hack cached selectivity so join size remains the same */
350  join_or_rinfo->norm_selec = orig_selec / or_selec;
351  /* ensure result stays in sane range, in particular not "redundant" */
352  if (join_or_rinfo->norm_selec > 1)
353  join_or_rinfo->norm_selec = 1;
354  /* as explained above, we don't touch outer_selec */
355  }
356 }
#define NIL
Definition: pg_list.h:69
bool semi_can_btree
Definition: relation.h:2015
Index security_level
Definition: relation.h:1847
RestrictInfo * make_restrictinfo(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:57
Relids min_righthand
Definition: relation.h:2008
List * baserestrictinfo
Definition: relation.h:645
NodeTag type
Definition: relation.h:2006
Relids clause_relids
Definition: relation.h:1850
#define Min(x, y)
Definition: c.h:812
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
Definition: nodes.h:510
Index baserestrict_min_security
Definition: relation.h:647
double Selectivity
Definition: nodes.h:640
Relids syn_lefthand
Definition: relation.h:2009
Selectivity norm_selec
Definition: relation.h:1873
Relids syn_righthand
Definition: relation.h:2010
List * semi_rhs_exprs
Definition: relation.h:2018
bool semi_can_hash
Definition: relation.h:2016
Selectivity clause_selectivity(PlannerInfo *root, Node *clause, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:574
Relids relids
Definition: relation.h:585
List * lappend(List *list, void *datum)
Definition: list.c:128
bool delay_upper_joins
Definition: relation.h:2013
JoinType jointype
Definition: relation.h:2011
List * semi_operators
Definition: relation.h:2017
Relids min_lefthand
Definition: relation.h:2007
static Expr * extract_or_clause ( RestrictInfo or_rinfo,
RelOptInfo rel 
)
static

Definition at line 159 of file orclauses.c.

References and_clause(), generate_unaccent_rules::args, Assert, castNode, RestrictInfo::clause, is_safe_restriction_clause_for(), lappend(), lfirst, lfirst_node, list_concat(), list_copy(), make_ands_explicit(), make_orclause(), NIL, or_clause(), RestrictInfo::orclause, and restriction_is_or_clause().

Referenced by extract_restriction_or_clauses().

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

Definition at line 73 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().

74 {
75  Index rti;
76 
77  /* Examine each baserel for potential join OR clauses */
78  for (rti = 1; rti < root->simple_rel_array_size; rti++)
79  {
80  RelOptInfo *rel = root->simple_rel_array[rti];
81  ListCell *lc;
82 
83  /* there may be empty slots corresponding to non-baserel RTEs */
84  if (rel == NULL)
85  continue;
86 
87  Assert(rel->relid == rti); /* sanity check on array */
88 
89  /* ignore RTEs that are "other rels" */
90  if (rel->reloptkind != RELOPT_BASEREL)
91  continue;
92 
93  /*
94  * Find potentially interesting OR joinclauses. We can use any
95  * joinclause that is considered safe to move to this rel by the
96  * parameterized-path machinery, even though what we are going to do
97  * with it is not exactly a parameterized path.
98  *
99  * However, it seems best to ignore clauses that have been marked
100  * redundant (by setting norm_selec > 1). That likely can't happen
101  * for OR clauses, but let's be safe.
102  */
103  foreach(lc, rel->joininfo)
104  {
105  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
106 
107  if (restriction_is_or_clause(rinfo) &&
108  join_clause_is_movable_to(rinfo, rel) &&
109  rinfo->norm_selec <= 1)
110  {
111  /* Try to extract a qual for this rel only */
112  Expr *orclause = extract_or_clause(rinfo, rel);
113 
114  /*
115  * If successful, decide whether we want to use the clause,
116  * and insert it into the rel's restrictinfo list if so.
117  */
118  if (orclause)
119  consider_new_or_clause(root, rel, orclause, rinfo);
120  }
121  }
122  }
123 }
RelOptKind reloptkind
Definition: relation.h:582
static Expr * extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel)
Definition: orclauses.c:159
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:295
Selectivity norm_selec
Definition: relation.h:1873
struct RelOptInfo ** simple_rel_array
Definition: relation.h:179
List * joininfo
Definition: relation.h:649
int simple_rel_array_size
Definition: relation.h:180
Index relid
Definition: relation.h:613
unsigned int Index
Definition: c.h:359
#define Assert(condition)
Definition: c.h:681
#define lfirst(lc)
Definition: pg_list.h:106
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:437
static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel, Expr *orclause, RestrictInfo *join_or_rinfo)
Definition: orclauses.c:257
static bool is_safe_restriction_clause_for ( RestrictInfo rinfo,
RelOptInfo rel 
)
static

Definition at line 129 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().

130 {
131  /*
132  * We want clauses that mention the rel, and only the rel. So in
133  * particular pseudoconstant clauses can be rejected quickly. Then check
134  * the clause's Var membership.
135  */
136  if (rinfo->pseudoconstant)
137  return false;
138  if (!bms_equal(rinfo->clause_relids, rel->relids))
139  return false;
140 
141  /* We don't want extra evaluations of any volatile functions */
142  if (contain_volatile_functions((Node *) rinfo->clause))
143  return false;
144 
145  return true;
146 }
Relids clause_relids
Definition: relation.h:1850
bool pseudoconstant
Definition: relation.h:1843
Definition: nodes.h:510
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:957
Relids relids
Definition: relation.h:585
Expr * clause
Definition: relation.h:1835
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:131