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 and TidRangePaths accordingly.
6  *
7  * For TidPaths, we look for 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  * Additionally, TidRangePaths may be created for conditions of the form
27  * "CTID relop pseudoconstant", where relop is one of >,>=,<,<=, and
28  * AND-clauses composed of such conditions.
29  *
30  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
31  * Portions Copyright (c) 1994, Regents of the University of California
32  *
33  *
34  * IDENTIFICATION
35  * src/backend/optimizer/path/tidpath.c
36  *
37  *-------------------------------------------------------------------------
38  */
39 #include "postgres.h"
40 
41 #include "access/sysattr.h"
42 #include "catalog/pg_operator.h"
43 #include "catalog/pg_type.h"
44 #include "nodes/nodeFuncs.h"
45 #include "optimizer/optimizer.h"
46 #include "optimizer/pathnode.h"
47 #include "optimizer/paths.h"
48 #include "optimizer/restrictinfo.h"
49 
50 
51 /*
52  * Does this Var represent the CTID column of the specified baserel?
53  */
54 static inline bool
56 {
57  /* The vartype check is strictly paranoia */
59  var->vartype == TIDOID &&
60  var->varno == rel->relid &&
61  var->varnullingrels == NULL &&
62  var->varlevelsup == 0)
63  return true;
64  return false;
65 }
66 
67 /*
68  * Check to see if a RestrictInfo is of the form
69  * CTID OP pseudoconstant
70  * or
71  * pseudoconstant OP CTID
72  * where OP is a binary operation, the CTID Var belongs to relation "rel",
73  * and nothing on the other side of the clause does.
74  */
75 static bool
77 {
78  OpExpr *node;
79  Node *arg1,
80  *arg2,
81  *other;
82  Relids other_relids;
83 
84  /* Must be an OpExpr */
85  if (!is_opclause(rinfo->clause))
86  return false;
87  node = (OpExpr *) rinfo->clause;
88 
89  /* OpExpr must have two arguments */
90  if (list_length(node->args) != 2)
91  return false;
92  arg1 = linitial(node->args);
93  arg2 = lsecond(node->args);
94 
95  /* Look for CTID as either argument */
96  other = NULL;
97  other_relids = NULL;
98  if (arg1 && IsA(arg1, Var) &&
99  IsCTIDVar((Var *) arg1, rel))
100  {
101  other = arg2;
102  other_relids = rinfo->right_relids;
103  }
104  if (!other && arg2 && IsA(arg2, Var) &&
105  IsCTIDVar((Var *) arg2, rel))
106  {
107  other = arg1;
108  other_relids = rinfo->left_relids;
109  }
110  if (!other)
111  return false;
112 
113  /* The other argument must be a pseudoconstant */
114  if (bms_is_member(rel->relid, other_relids) ||
116  return false;
117 
118  return true; /* success */
119 }
120 
121 /*
122  * Check to see if a RestrictInfo is of the form
123  * CTID = pseudoconstant
124  * or
125  * pseudoconstant = CTID
126  * where the CTID Var belongs to relation "rel", and nothing on the
127  * other side of the clause does.
128  */
129 static bool
131 {
132  if (!IsBinaryTidClause(rinfo, rel))
133  return false;
134 
135  if (((OpExpr *) rinfo->clause)->opno == TIDEqualOperator)
136  return true;
137 
138  return false;
139 }
140 
141 /*
142  * Check to see if a RestrictInfo is of the form
143  * CTID OP pseudoconstant
144  * or
145  * pseudoconstant OP CTID
146  * where OP is a range operator such as <, <=, >, or >=, the CTID Var belongs
147  * to relation "rel", and nothing on the other side of the clause does.
148  */
149 static bool
151 {
152  Oid opno;
153 
154  if (!IsBinaryTidClause(rinfo, rel))
155  return false;
156  opno = ((OpExpr *) rinfo->clause)->opno;
157 
158  if (opno == TIDLessOperator || opno == TIDLessEqOperator ||
159  opno == TIDGreaterOperator || opno == TIDGreaterEqOperator)
160  return true;
161 
162  return false;
163 }
164 
165 /*
166  * Check to see if a RestrictInfo is of the form
167  * CTID = ANY (pseudoconstant_array)
168  * where the CTID Var belongs to relation "rel", and nothing on the
169  * other side of the clause does.
170  */
171 static bool
173 {
174  ScalarArrayOpExpr *node;
175  Node *arg1,
176  *arg2;
177 
178  /* Must be a ScalarArrayOpExpr */
179  if (!(rinfo->clause && IsA(rinfo->clause, ScalarArrayOpExpr)))
180  return false;
181  node = (ScalarArrayOpExpr *) rinfo->clause;
182 
183  /* Operator must be tideq */
184  if (node->opno != TIDEqualOperator)
185  return false;
186  if (!node->useOr)
187  return false;
188  Assert(list_length(node->args) == 2);
189  arg1 = linitial(node->args);
190  arg2 = lsecond(node->args);
191 
192  /* CTID must be first argument */
193  if (arg1 && IsA(arg1, Var) &&
194  IsCTIDVar((Var *) arg1, rel))
195  {
196  /* The other argument must be a pseudoconstant */
197  if (bms_is_member(rel->relid, pull_varnos(root, arg2)) ||
199  return false;
200 
201  return true; /* success */
202  }
203 
204  return false;
205 }
206 
207 /*
208  * Check to see if a RestrictInfo is a CurrentOfExpr referencing "rel".
209  */
210 static bool
212 {
213  CurrentOfExpr *node;
214 
215  /* Must be a CurrentOfExpr */
216  if (!(rinfo->clause && IsA(rinfo->clause, CurrentOfExpr)))
217  return false;
218  node = (CurrentOfExpr *) rinfo->clause;
219 
220  /* If it references this rel, we're good */
221  if (node->cvarno == rel->relid)
222  return true;
223 
224  return false;
225 }
226 
227 /*
228  * Is the RestrictInfo usable as a CTID qual for the specified rel?
229  *
230  * This function considers only base cases; AND/OR combination is handled
231  * below.
232  */
233 static bool
235 {
236  /*
237  * We may ignore pseudoconstant clauses (they can't contain Vars, so could
238  * not match anyway).
239  */
240  if (rinfo->pseudoconstant)
241  return false;
242 
243  /*
244  * If clause must wait till after some lower-security-level restriction
245  * clause, reject it.
246  */
247  if (!restriction_is_securely_promotable(rinfo, rel))
248  return false;
249 
250  /*
251  * Check all base cases.
252  */
253  if (IsTidEqualClause(rinfo, rel) ||
254  IsTidEqualAnyClause(root, rinfo, rel) ||
255  IsCurrentOfClause(rinfo, rel))
256  return true;
257 
258  return false;
259 }
260 
261 /*
262  * Extract a set of CTID conditions from implicit-AND List of RestrictInfos
263  *
264  * Returns a List of CTID qual RestrictInfos for the specified rel (with
265  * implicit OR semantics across the list), or NIL if there are no usable
266  * equality conditions.
267  *
268  * This function is mainly concerned with handling AND/OR recursion.
269  * However, we do have a special rule to enforce: if there is a CurrentOfExpr
270  * qual, we *must* return that and only that, else the executor may fail.
271  * Ordinarily a CurrentOfExpr would be all alone anyway because of grammar
272  * restrictions, but it is possible for RLS quals to appear AND'ed with it.
273  * It's even possible (if fairly useless) for the RLS quals to be CTID quals.
274  * So we must scan the whole rlist to see if there's a CurrentOfExpr. Since
275  * we have to do that, we also apply some very-trivial preference rules about
276  * which of the other possibilities should be chosen, in the unlikely event
277  * that there's more than one choice.
278  */
279 static List *
281 {
282  RestrictInfo *tidclause = NULL; /* best simple CTID qual so far */
283  List *orlist = NIL; /* best OR'ed CTID qual so far */
284  ListCell *l;
285 
286  foreach(l, rlist)
287  {
289 
290  if (restriction_is_or_clause(rinfo))
291  {
292  List *rlst = NIL;
293  ListCell *j;
294 
295  /*
296  * We must be able to extract a CTID condition from every
297  * sub-clause of an OR, or we can't use it.
298  */
299  foreach(j, ((BoolExpr *) rinfo->orclause)->args)
300  {
301  Node *orarg = (Node *) lfirst(j);
302  List *sublist;
303 
304  /* OR arguments should be ANDs or sub-RestrictInfos */
305  if (is_andclause(orarg))
306  {
307  List *andargs = ((BoolExpr *) orarg)->args;
308 
309  /* Recurse in case there are sub-ORs */
310  sublist = TidQualFromRestrictInfoList(root, andargs, rel);
311  }
312  else
313  {
314  RestrictInfo *ri = castNode(RestrictInfo, orarg);
315 
317  if (RestrictInfoIsTidQual(root, ri, rel))
318  sublist = list_make1(ri);
319  else
320  sublist = NIL;
321  }
322 
323  /*
324  * If nothing found in this arm, we can't do anything with
325  * this OR clause.
326  */
327  if (sublist == NIL)
328  {
329  rlst = NIL; /* forget anything we had */
330  break; /* out of loop over OR args */
331  }
332 
333  /*
334  * OK, continue constructing implicitly-OR'ed result list.
335  */
336  rlst = list_concat(rlst, sublist);
337  }
338 
339  if (rlst)
340  {
341  /*
342  * Accept the OR'ed list if it's the first one, or if it's
343  * shorter than the previous one.
344  */
345  if (orlist == NIL || list_length(rlst) < list_length(orlist))
346  orlist = rlst;
347  }
348  }
349  else
350  {
351  /* Not an OR clause, so handle base cases */
352  if (RestrictInfoIsTidQual(root, rinfo, rel))
353  {
354  /* We can stop immediately if it's a CurrentOfExpr */
355  if (IsCurrentOfClause(rinfo, rel))
356  return list_make1(rinfo);
357 
358  /*
359  * Otherwise, remember the first non-OR CTID qual. We could
360  * try to apply some preference order if there's more than
361  * one, but such usage seems very unlikely, so don't bother.
362  */
363  if (tidclause == NULL)
364  tidclause = rinfo;
365  }
366  }
367  }
368 
369  /*
370  * Prefer any singleton CTID qual to an OR'ed list. Again, it seems
371  * unlikely to be worth thinking harder than that.
372  */
373  if (tidclause)
374  return list_make1(tidclause);
375  return orlist;
376 }
377 
378 /*
379  * Extract a set of CTID range conditions from implicit-AND List of RestrictInfos
380  *
381  * Returns a List of CTID range qual RestrictInfos for the specified rel
382  * (with implicit AND semantics across the list), or NIL if there are no
383  * usable range conditions or if the rel's table AM does not support TID range
384  * scans.
385  */
386 static List *
388 {
389  List *rlst = NIL;
390  ListCell *l;
391 
392  if ((rel->amflags & AMFLAG_HAS_TID_RANGE) == 0)
393  return NIL;
394 
395  foreach(l, rlist)
396  {
398 
399  if (IsTidRangeClause(rinfo, rel))
400  rlst = lappend(rlst, rinfo);
401  }
402 
403  return rlst;
404 }
405 
406 /*
407  * Given a list of join clauses involving our rel, create a parameterized
408  * TidPath for each one that is a suitable TidEqual clause.
409  *
410  * In principle we could combine clauses that reference the same outer rels,
411  * but it doesn't seem like such cases would arise often enough to be worth
412  * troubling over.
413  */
414 static void
416 {
417  ListCell *l;
418 
419  foreach(l, clauses)
420  {
422  List *tidquals;
423  Relids required_outer;
424 
425  /*
426  * Validate whether each clause is actually usable; we must check this
427  * even when examining clauses generated from an EquivalenceClass,
428  * since they might not satisfy the restriction on not having Vars of
429  * our rel on the other side, or somebody might've built an operator
430  * class that accepts type "tid" but has other operators in it.
431  *
432  * We currently consider only TidEqual join clauses. In principle we
433  * might find a suitable ScalarArrayOpExpr in the rel's joininfo list,
434  * but it seems unlikely to be worth expending the cycles to check.
435  * And we definitely won't find a CurrentOfExpr here. Hence, we don't
436  * use RestrictInfoIsTidQual; but this must match that function
437  * otherwise.
438  */
439  if (rinfo->pseudoconstant ||
440  !restriction_is_securely_promotable(rinfo, rel) ||
441  !IsTidEqualClause(rinfo, rel))
442  continue;
443 
444  /*
445  * Check if clause can be moved to this rel; this is probably
446  * redundant when considering EC-derived clauses, but we must check it
447  * for "loose" join clauses.
448  */
449  if (!join_clause_is_movable_to(rinfo, rel))
450  continue;
451 
452  /* OK, make list of clauses for this path */
453  tidquals = list_make1(rinfo);
454 
455  /* Compute required outer rels for this path */
456  required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
457  required_outer = bms_del_member(required_outer, rel->relid);
458 
459  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
460  required_outer));
461  }
462 }
463 
464 /*
465  * Test whether an EquivalenceClass member matches our rel's CTID Var.
466  *
467  * This is a callback for use by generate_implied_equalities_for_column.
468  */
469 static bool
472  void *arg)
473 {
474  if (em->em_expr && IsA(em->em_expr, Var) &&
475  IsCTIDVar((Var *) em->em_expr, rel))
476  return true;
477  return false;
478 }
479 
480 /*
481  * create_tidscan_paths
482  * Create paths corresponding to direct TID scans of the given rel.
483  *
484  * Candidate paths are added to the rel's pathlist (using add_path).
485  */
486 void
488 {
489  List *tidquals;
490  List *tidrangequals;
491 
492  /*
493  * If any suitable quals exist in the rel's baserestrict list, generate a
494  * plain (unparameterized) TidPath with them.
495  */
496  tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
497 
498  if (tidquals != NIL)
499  {
500  /*
501  * This path uses no join clauses, but it could still have required
502  * parameterization due to LATERAL refs in its tlist.
503  */
504  Relids required_outer = rel->lateral_relids;
505 
506  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
507  required_outer));
508  }
509 
510  /*
511  * If there are range quals in the baserestrict list, generate a
512  * TidRangePath.
513  */
515  rel);
516 
517  if (tidrangequals != NIL)
518  {
519  /*
520  * This path uses no join clauses, but it could still have required
521  * parameterization due to LATERAL refs in its tlist.
522  */
523  Relids required_outer = rel->lateral_relids;
524 
526  tidrangequals,
527  required_outer));
528  }
529 
530  /*
531  * Try to generate parameterized TidPaths using equality clauses extracted
532  * from EquivalenceClasses. (This is important since simple "t1.ctid =
533  * t2.ctid" clauses will turn into ECs.)
534  */
535  if (rel->has_eclass_joins)
536  {
537  List *clauses;
538 
539  /* Generate clauses, skipping any that join to lateral_referencers */
541  rel,
543  NULL,
544  rel->lateral_referencers);
545 
546  /* Generate a path for each usable join clause */
547  BuildParameterizedTidPaths(root, rel, clauses);
548  }
549 
550  /*
551  * Also consider parameterized TidPaths using "loose" join quals. Quals
552  * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
553  * join quals, for example.
554  */
556 }
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:868
#define Assert(condition)
Definition: c.h:858
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:538
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:2960
int j
Definition: isn.c:74
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
List * lappend(List *list, void *datum)
Definition: list.c:339
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:105
static bool is_opclause(const void *clause)
Definition: nodeFuncs.h:74
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define castNode(_type_, nodeptr)
Definition: nodes.h:176
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1179
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:420
TidRangePath * create_tidrangescan_path(PlannerInfo *root, RelOptInfo *rel, List *tidrangequals, Relids required_outer)
Definition: pathnode.c:1208
#define AMFLAG_HAS_TID_RANGE
Definition: pathnodes.h:817
void * arg
#define lfirst(lc)
Definition: pg_list.h:172
#define lfirst_node(type, lc)
Definition: pg_list.h:176
static int list_length(const List *l)
Definition: pg_list.h:152
#define NIL
Definition: pg_list.h:68
#define list_make1(x1)
Definition: pg_list.h:212
#define linitial(l)
Definition: pg_list.h:178
#define lsecond(l)
Definition: pg_list.h:183
unsigned int Oid
Definition: postgres_ext.h:31
tree ctl root
Definition: radixtree.h:1886
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:416
bool restriction_is_securely_promotable(RestrictInfo *restrictinfo, RelOptInfo *rel)
Definition: restrictinfo.c:431
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:584
Definition: pg_list.h:54
Definition: nodes.h:129
List * args
Definition: primnodes.h:836
List * baserestrictinfo
Definition: pathnodes.h:979
uint32 amflags
Definition: pathnodes.h:952
List * joininfo
Definition: pathnodes.h:985
Index relid
Definition: pathnodes.h:912
Relids lateral_relids
Definition: pathnodes.h:907
Relids lateral_referencers
Definition: pathnodes.h:936
bool has_eclass_joins
Definition: pathnodes.h:987
Relids required_relids
Definition: pathnodes.h:2595
Expr * clause
Definition: pathnodes.h:2564
Definition: primnodes.h:248
AttrNumber varattno
Definition: primnodes.h:260
int varno
Definition: primnodes.h:255
Index varlevelsup
Definition: primnodes.h:280
#define SelfItemPointerAttributeNumber
Definition: sysattr.h:21
static bool IsBinaryTidClause(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:76
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:415
static bool IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:130
static List * TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel)
Definition: tidpath.c:280
static List * TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:387
static bool IsCTIDVar(Var *var, RelOptInfo *rel)
Definition: tidpath.c:55
static bool IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:211
static bool RestrictInfoIsTidQual(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:234
static bool ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition: tidpath.c:470
static bool IsTidRangeClause(RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:150
void create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: tidpath.c:487
static bool IsTidEqualAnyClause(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
Definition: tidpath.c:172
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:108