PostgreSQL Source Code  git master
tidpath.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * tidpath.c
4  * Routines to determine which TID conditions are usable for scanning
5  * a given relation, and create TidPaths accordingly.
6  *
7  * What we are looking for here is WHERE conditions of the form
8  * "CTID = pseudoconstant", which can be implemented by just fetching
9  * the tuple directly via heap_fetch(). We can also handle OR'd conditions
10  * such as (CTID = const1) OR (CTID = const2), as well as ScalarArrayOpExpr
11  * conditions of the form CTID = ANY(pseudoconstant_array). In particular
12  * this allows
13  * WHERE ctid IN (tid1, tid2, ...)
14  *
15  * As with indexscans, our definition of "pseudoconstant" is pretty liberal:
16  * we allow anything that doesn't involve a volatile function or a Var of
17  * the relation under consideration. Vars belonging to other relations of
18  * the query are allowed, giving rise to parameterized TID scans.
19  *
20  * We also support "WHERE CURRENT OF cursor" conditions (CurrentOfExpr),
21  * which amount to "CTID = run-time-determined-TID". These could in
22  * theory be translated to a simple comparison of CTID to the result of
23  * a function, but in practice it works better to keep the special node
24  * representation all the way through to execution.
25  *
26  *
27  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
28  * Portions Copyright (c) 1994, Regents of the University of California
29  *
30  *
31  * IDENTIFICATION
32  * src/backend/optimizer/path/tidpath.c
33  *
34  *-------------------------------------------------------------------------
35  */
36 #include "postgres.h"
37 
38 #include "access/sysattr.h"
39 #include "catalog/pg_operator.h"
40 #include "catalog/pg_type.h"
41 #include "nodes/nodeFuncs.h"
42 #include "optimizer/clauses.h"
43 #include "optimizer/optimizer.h"
44 #include "optimizer/pathnode.h"
45 #include "optimizer/paths.h"
46 #include "optimizer/restrictinfo.h"
47 
48 
49 /*
50  * Does this Var represent the CTID column of the specified baserel?
51  */
52 static inline bool
54 {
55  /* The vartype check is strictly paranoia */
57  var->vartype == TIDOID &&
58  var->varno == rel->relid &&
59  var->varlevelsup == 0)
60  return true;
61  return false;
62 }
63 
64 /*
65  * Check to see if a RestrictInfo is of the form
66  * CTID = pseudoconstant
67  * or
68  * pseudoconstant = CTID
69  * where the CTID Var belongs to relation "rel", and nothing on the
70  * other side of the clause does.
71  */
72 static bool
74 {
75  OpExpr *node;
76  Node *arg1,
77  *arg2,
78  *other;
79  Relids other_relids;
80 
81  /* Must be an OpExpr */
82  if (!is_opclause(rinfo->clause))
83  return false;
84  node = (OpExpr *) rinfo->clause;
85 
86  /* Operator must be tideq */
87  if (node->opno != TIDEqualOperator)
88  return false;
89  Assert(list_length(node->args) == 2);
90  arg1 = linitial(node->args);
91  arg2 = lsecond(node->args);
92 
93  /* Look for CTID as either argument */
94  other = NULL;
95  other_relids = NULL;
96  if (arg1 && IsA(arg1, Var) &&
97  IsCTIDVar((Var *) arg1, rel))
98  {
99  other = arg2;
100  other_relids = rinfo->right_relids;
101  }
102  if (!other && arg2 && IsA(arg2, Var) &&
103  IsCTIDVar((Var *) arg2, rel))
104  {
105  other = arg1;
106  other_relids = rinfo->left_relids;
107  }
108  if (!other)
109  return false;
110 
111  /* The other argument must be a pseudoconstant */
112  if (bms_is_member(rel->relid, other_relids) ||
114  return false;
115 
116  return true; /* success */
117 }
118 
119 /*
120  * Check to see if a RestrictInfo is of the form
121  * CTID = ANY (pseudoconstant_array)
122  * where the CTID Var belongs to relation "rel", and nothing on the
123  * other side of the clause does.
124  */
125 static bool
127 {
128  ScalarArrayOpExpr *node;
129  Node *arg1,
130  *arg2;
131 
132  /* Must be a ScalarArrayOpExpr */
133  if (!(rinfo->clause && IsA(rinfo->clause, ScalarArrayOpExpr)))
134  return false;
135  node = (ScalarArrayOpExpr *) rinfo->clause;
136 
137  /* Operator must be tideq */
138  if (node->opno != TIDEqualOperator)
139  return false;
140  if (!node->useOr)
141  return false;
142  Assert(list_length(node->args) == 2);
143  arg1 = linitial(node->args);
144  arg2 = lsecond(node->args);
145 
146  /* CTID must be first argument */
147  if (arg1 && IsA(arg1, Var) &&
148  IsCTIDVar((Var *) arg1, rel))
149  {
150  /* The other argument must be a pseudoconstant */
151  if (bms_is_member(rel->relid, pull_varnos(arg2)) ||
153  return false;
154 
155  return true; /* success */
156  }
157 
158  return false;
159 }
160 
161 /*
162  * Check to see if a RestrictInfo is a CurrentOfExpr referencing "rel".
163  */
164 static bool
166 {
167  CurrentOfExpr *node;
168 
169  /* Must be a CurrentOfExpr */
170  if (!(rinfo->clause && IsA(rinfo->clause, CurrentOfExpr)))
171  return false;
172  node = (CurrentOfExpr *) rinfo->clause;
173 
174  /* If it references this rel, we're good */
175  if (node->cvarno == rel->relid)
176  return true;
177 
178  return false;
179 }
180 
181 /*
182  * Extract a set of CTID conditions from the given RestrictInfo
183  *
184  * Returns a List of CTID qual RestrictInfos for the specified rel (with
185  * implicit OR semantics across the list), or NIL if there are no usable
186  * conditions.
187  *
188  * This function considers only base cases; AND/OR combination is handled
189  * below. Therefore the returned List never has more than one element.
190  * (Using a List may seem a bit weird, but it simplifies the caller.)
191  */
192 static List *
194 {
195  /*
196  * We may ignore pseudoconstant clauses (they can't contain Vars, so could
197  * not match anyway).
198  */
199  if (rinfo->pseudoconstant)
200  return NIL;
201 
202  /*
203  * If clause must wait till after some lower-security-level restriction
204  * clause, reject it.
205  */
206  if (!restriction_is_securely_promotable(rinfo, rel))
207  return NIL;
208 
209  /*
210  * Check all base cases. If we get a match, return the clause.
211  */
212  if (IsTidEqualClause(rinfo, rel) ||
213  IsTidEqualAnyClause(rinfo, rel) ||
214  IsCurrentOfClause(rinfo, rel))
215  return list_make1(rinfo);
216 
217  return NIL;
218 }
219 
220 /*
221  * Extract a set of CTID conditions from implicit-AND List of RestrictInfos
222  *
223  * Returns a List of CTID qual RestrictInfos for the specified rel (with
224  * implicit OR semantics across the list), or NIL if there are no usable
225  * conditions.
226  *
227  * This function is just concerned with handling AND/OR recursion.
228  */
229 static List *
231 {
232  List *rlst = NIL;
233  ListCell *l;
234 
235  foreach(l, rlist)
236  {
238 
239  if (restriction_is_or_clause(rinfo))
240  {
241  ListCell *j;
242 
243  /*
244  * We must be able to extract a CTID condition from every
245  * sub-clause of an OR, or we can't use it.
246  */
247  foreach(j, ((BoolExpr *) rinfo->orclause)->args)
248  {
249  Node *orarg = (Node *) lfirst(j);
250  List *sublist;
251 
252  /* OR arguments should be ANDs or sub-RestrictInfos */
253  if (is_andclause(orarg))
254  {
255  List *andargs = ((BoolExpr *) orarg)->args;
256 
257  /* Recurse in case there are sub-ORs */
258  sublist = TidQualFromRestrictInfoList(andargs, rel);
259  }
260  else
261  {
262  RestrictInfo *rinfo = castNode(RestrictInfo, orarg);
263 
265  sublist = TidQualFromRestrictInfo(rinfo, rel);
266  }
267 
268  /*
269  * If nothing found in this arm, we can't do anything with
270  * this OR clause.
271  */
272  if (sublist == NIL)
273  {
274  rlst = NIL; /* forget anything we had */
275  break; /* out of loop over OR args */
276  }
277 
278  /*
279  * OK, continue constructing implicitly-OR'ed result list.
280  */
281  rlst = list_concat(rlst, sublist);
282  }
283  }
284  else
285  {
286  /* Not an OR clause, so handle base cases */
287  rlst = TidQualFromRestrictInfo(rinfo, rel);
288  }
289 
290  /*
291  * Stop as soon as we find any usable CTID condition. In theory we
292  * could get CTID equality conditions from different AND'ed clauses,
293  * in which case we could try to pick the most efficient one. In
294  * practice, such usage seems very unlikely, so we don't bother; we
295  * just exit as soon as we find the first candidate.
296  */
297  if (rlst)
298  break;
299  }
300 
301  return rlst;
302 }
303 
304 /*
305  * Given a list of join clauses involving our rel, create a parameterized
306  * TidPath for each one that is a suitable TidEqual clause.
307  *
308  * In principle we could combine clauses that reference the same outer rels,
309  * but it doesn't seem like such cases would arise often enough to be worth
310  * troubling over.
311  */
312 static void
314 {
315  ListCell *l;
316 
317  foreach(l, clauses)
318  {
320  List *tidquals;
321  Relids required_outer;
322 
323  /*
324  * Validate whether each clause is actually usable; we must check this
325  * even when examining clauses generated from an EquivalenceClass,
326  * since they might not satisfy the restriction on not having Vars of
327  * our rel on the other side, or somebody might've built an operator
328  * class that accepts type "tid" but has other operators in it.
329  *
330  * We currently consider only TidEqual join clauses. In principle we
331  * might find a suitable ScalarArrayOpExpr in the rel's joininfo list,
332  * but it seems unlikely to be worth expending the cycles to check.
333  * And we definitely won't find a CurrentOfExpr here. Hence, we don't
334  * use TidQualFromRestrictInfo; but this must match that function
335  * otherwise.
336  */
337  if (rinfo->pseudoconstant ||
338  !restriction_is_securely_promotable(rinfo, rel) ||
339  !IsTidEqualClause(rinfo, rel))
340  continue;
341 
342  /*
343  * Check if clause can be moved to this rel; this is probably
344  * redundant when considering EC-derived clauses, but we must check it
345  * for "loose" join clauses.
346  */
347  if (!join_clause_is_movable_to(rinfo, rel))
348  continue;
349 
350  /* OK, make list of clauses for this path */
351  tidquals = list_make1(rinfo);
352 
353  /* Compute required outer rels for this path */
354  required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
355  required_outer = bms_del_member(required_outer, rel->relid);
356 
357  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
358  required_outer));
359  }
360 }
361 
362 /*
363  * Test whether an EquivalenceClass member matches our rel's CTID Var.
364  *
365  * This is a callback for use by generate_implied_equalities_for_column.
366  */
367 static bool
370  void *arg)
371 {
372  if (em->em_expr && IsA(em->em_expr, Var) &&
373  IsCTIDVar((Var *) em->em_expr, rel))
374  return true;
375  return false;
376 }
377 
378 /*
379  * create_tidscan_paths
380  * Create paths corresponding to direct TID scans of the given rel.
381  *
382  * Candidate paths are added to the rel's pathlist (using add_path).
383  */
384 void
386 {
387  List *tidquals;
388 
389  /*
390  * If any suitable quals exist in the rel's baserestrict list, generate a
391  * plain (unparameterized) TidPath with them.
392  */
393  tidquals = TidQualFromRestrictInfoList(rel->baserestrictinfo, rel);
394 
395  if (tidquals)
396  {
397  /*
398  * This path uses no join clauses, but it could still have required
399  * parameterization due to LATERAL refs in its tlist.
400  */
401  Relids required_outer = rel->lateral_relids;
402 
403  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
404  required_outer));
405  }
406 
407  /*
408  * Try to generate parameterized TidPaths using equality clauses extracted
409  * from EquivalenceClasses. (This is important since simple "t1.ctid =
410  * t2.ctid" clauses will turn into ECs.)
411  */
412  if (rel->has_eclass_joins)
413  {
414  List *clauses;
415 
416  /* Generate clauses, skipping any that join to lateral_referencers */
418  rel,
420  NULL,
421  rel->lateral_referencers);
422 
423  /* Generate a path for each usable join clause */
424  BuildParameterizedTidPaths(root, rel, clauses);
425  }
426 
427  /*
428  * Also consider parameterized TidPaths using "loose" join quals. Quals
429  * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
430  * join quals, for example.
431  */
432  BuildParameterizedTidPaths(root, rel, rel->joininfo);
433 }
bool has_eclass_joins
Definition: pathnodes.h:709
#define NIL
Definition: pg_list.h:65
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
Index varlevelsup
Definition: primnodes.h:177
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:423
Relids required_relids
Definition: pathnodes.h:1961
#define castNode(_type_, nodeptr)
Definition: nodes.h:594
Expr * orclause
Definition: pathnodes.h:1974
static bool IsTidEqualAnyClause(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:126
List * baserestrictinfo
Definition: pathnodes.h:703
bool pseudoconstant
Definition: pathnodes.h:1951
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:94
Definition: nodes.h:525
List * list_concat(List *list1, const List *list2)
Definition: list.c:516
Relids left_relids
Definition: pathnodes.h:1970
AttrNumber varattno
Definition: primnodes.h:172
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:724
Definition: primnodes.h:167
static bool IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:165
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:361
#define lsecond(l)
Definition: pg_list.h:200
#define list_make1(x1)
Definition: pg_list.h:227
static bool ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition: tidpath.c:368
Relids lateral_relids
Definition: pathnodes.h:666
void create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: tidpath.c:385
#define linitial(l)
Definition: pg_list.h:195
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:313
Oid vartype
Definition: primnodes.h:174
#define lfirst_node(type, lc)
Definition: pg_list.h:193
List * joininfo
Definition: pathnodes.h:707
static List * TidQualFromRestrictInfo(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:193
Relids pull_varnos(Node *node)
Definition: var.c:95
Index relid
Definition: pathnodes.h:669
Relids lateral_referencers
Definition: pathnodes.h:677
Expr * clause
Definition: pathnodes.h:1943
Index varno
Definition: primnodes.h:170
static List * TidQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:230
static bool IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:73
static bool IsCTIDVar(Var *var, RelOptInfo *rel)
Definition: tidpath.c:53
Relids right_relids
Definition: pathnodes.h:1971
#define Assert(condition)
Definition: c.h:732
#define lfirst(lc)
Definition: pg_list.h:190
bool restriction_is_securely_promotable(RestrictInfo *restrictinfo, RelOptInfo *rel)
Definition: restrictinfo.c:376
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
static int list_length(const List *l)
Definition: pg_list.h:169
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:504
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1152
void * arg
Oid opno
Definition: primnodes.h:502
#define SelfItemPointerAttributeNumber
Definition: sysattr.h:21
static bool is_opclause(const void *clause)
Definition: nodeFuncs.h:63
List * args
Definition: primnodes.h:508
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:773
Definition: pg_list.h:50
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:427
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:2362