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-2021, 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/clauses.h"
46 #include "optimizer/optimizer.h"
47 #include "optimizer/pathnode.h"
48 #include "optimizer/paths.h"
49 #include "optimizer/restrictinfo.h"
50
51
52 /*
53 * Does this Var represent the CTID column of the specified baserel?
54 */
55 static inline bool
IsCTIDVar(Var * var,RelOptInfo * rel)56 IsCTIDVar(Var *var, RelOptInfo *rel)
57 {
58 /* The vartype check is strictly paranoia */
59 if (var->varattno == SelfItemPointerAttributeNumber &&
60 var->vartype == TIDOID &&
61 var->varno == rel->relid &&
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
IsBinaryTidClause(RestrictInfo * rinfo,RelOptInfo * rel)76 IsBinaryTidClause(RestrictInfo *rinfo, RelOptInfo *rel)
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) ||
115 contain_volatile_functions(other))
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
IsTidEqualClause(RestrictInfo * rinfo,RelOptInfo * rel)130 IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
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
IsTidRangeClause(RestrictInfo * rinfo,RelOptInfo * rel)150 IsTidRangeClause(RestrictInfo *rinfo, RelOptInfo *rel)
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
IsTidEqualAnyClause(PlannerInfo * root,RestrictInfo * rinfo,RelOptInfo * rel)172 IsTidEqualAnyClause(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
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)) ||
198 contain_volatile_functions(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
IsCurrentOfClause(RestrictInfo * rinfo,RelOptInfo * rel)211 IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
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 * Extract a set of CTID conditions from the given RestrictInfo
229 *
230 * Returns a List of CTID qual RestrictInfos for the specified rel (with
231 * implicit OR semantics across the list), or NIL if there are no usable
232 * conditions.
233 *
234 * This function considers only base cases; AND/OR combination is handled
235 * below. Therefore the returned List never has more than one element.
236 * (Using a List may seem a bit weird, but it simplifies the caller.)
237 */
238 static List *
TidQualFromRestrictInfo(PlannerInfo * root,RestrictInfo * rinfo,RelOptInfo * rel)239 TidQualFromRestrictInfo(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
240 {
241 /*
242 * We may ignore pseudoconstant clauses (they can't contain Vars, so could
243 * not match anyway).
244 */
245 if (rinfo->pseudoconstant)
246 return NIL;
247
248 /*
249 * If clause must wait till after some lower-security-level restriction
250 * clause, reject it.
251 */
252 if (!restriction_is_securely_promotable(rinfo, rel))
253 return NIL;
254
255 /*
256 * Check all base cases. If we get a match, return the clause.
257 */
258 if (IsTidEqualClause(rinfo, rel) ||
259 IsTidEqualAnyClause(root, rinfo, rel) ||
260 IsCurrentOfClause(rinfo, rel))
261 return list_make1(rinfo);
262
263 return NIL;
264 }
265
266 /*
267 * Extract a set of CTID conditions from implicit-AND List of RestrictInfos
268 *
269 * Returns a List of CTID qual RestrictInfos for the specified rel (with
270 * implicit OR semantics across the list), or NIL if there are no usable
271 * equality conditions.
272 *
273 * This function is just concerned with handling AND/OR recursion.
274 */
275 static List *
TidQualFromRestrictInfoList(PlannerInfo * root,List * rlist,RelOptInfo * rel)276 TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel)
277 {
278 List *rlst = NIL;
279 ListCell *l;
280
281 foreach(l, rlist)
282 {
283 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
284
285 if (restriction_is_or_clause(rinfo))
286 {
287 ListCell *j;
288
289 /*
290 * We must be able to extract a CTID condition from every
291 * sub-clause of an OR, or we can't use it.
292 */
293 foreach(j, ((BoolExpr *) rinfo->orclause)->args)
294 {
295 Node *orarg = (Node *) lfirst(j);
296 List *sublist;
297
298 /* OR arguments should be ANDs or sub-RestrictInfos */
299 if (is_andclause(orarg))
300 {
301 List *andargs = ((BoolExpr *) orarg)->args;
302
303 /* Recurse in case there are sub-ORs */
304 sublist = TidQualFromRestrictInfoList(root, andargs, rel);
305 }
306 else
307 {
308 RestrictInfo *rinfo = castNode(RestrictInfo, orarg);
309
310 Assert(!restriction_is_or_clause(rinfo));
311 sublist = TidQualFromRestrictInfo(root, rinfo, rel);
312 }
313
314 /*
315 * If nothing found in this arm, we can't do anything with
316 * this OR clause.
317 */
318 if (sublist == NIL)
319 {
320 rlst = NIL; /* forget anything we had */
321 break; /* out of loop over OR args */
322 }
323
324 /*
325 * OK, continue constructing implicitly-OR'ed result list.
326 */
327 rlst = list_concat(rlst, sublist);
328 }
329 }
330 else
331 {
332 /* Not an OR clause, so handle base cases */
333 rlst = TidQualFromRestrictInfo(root, rinfo, rel);
334 }
335
336 /*
337 * Stop as soon as we find any usable CTID condition. In theory we
338 * could get CTID equality conditions from different AND'ed clauses,
339 * in which case we could try to pick the most efficient one. In
340 * practice, such usage seems very unlikely, so we don't bother; we
341 * just exit as soon as we find the first candidate.
342 */
343 if (rlst)
344 break;
345 }
346
347 return rlst;
348 }
349
350 /*
351 * Extract a set of CTID range conditions from implicit-AND List of RestrictInfos
352 *
353 * Returns a List of CTID range qual RestrictInfos for the specified rel
354 * (with implicit AND semantics across the list), or NIL if there are no
355 * usable range conditions or if the rel's table AM does not support TID range
356 * scans.
357 */
358 static List *
TidRangeQualFromRestrictInfoList(List * rlist,RelOptInfo * rel)359 TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
360 {
361 List *rlst = NIL;
362 ListCell *l;
363
364 if ((rel->amflags & AMFLAG_HAS_TID_RANGE) == 0)
365 return NIL;
366
367 foreach(l, rlist)
368 {
369 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
370
371 if (IsTidRangeClause(rinfo, rel))
372 rlst = lappend(rlst, rinfo);
373 }
374
375 return rlst;
376 }
377
378 /*
379 * Given a list of join clauses involving our rel, create a parameterized
380 * TidPath for each one that is a suitable TidEqual clause.
381 *
382 * In principle we could combine clauses that reference the same outer rels,
383 * but it doesn't seem like such cases would arise often enough to be worth
384 * troubling over.
385 */
386 static void
BuildParameterizedTidPaths(PlannerInfo * root,RelOptInfo * rel,List * clauses)387 BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
388 {
389 ListCell *l;
390
391 foreach(l, clauses)
392 {
393 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
394 List *tidquals;
395 Relids required_outer;
396
397 /*
398 * Validate whether each clause is actually usable; we must check this
399 * even when examining clauses generated from an EquivalenceClass,
400 * since they might not satisfy the restriction on not having Vars of
401 * our rel on the other side, or somebody might've built an operator
402 * class that accepts type "tid" but has other operators in it.
403 *
404 * We currently consider only TidEqual join clauses. In principle we
405 * might find a suitable ScalarArrayOpExpr in the rel's joininfo list,
406 * but it seems unlikely to be worth expending the cycles to check.
407 * And we definitely won't find a CurrentOfExpr here. Hence, we don't
408 * use TidQualFromRestrictInfo; but this must match that function
409 * otherwise.
410 */
411 if (rinfo->pseudoconstant ||
412 !restriction_is_securely_promotable(rinfo, rel) ||
413 !IsTidEqualClause(rinfo, rel))
414 continue;
415
416 /*
417 * Check if clause can be moved to this rel; this is probably
418 * redundant when considering EC-derived clauses, but we must check it
419 * for "loose" join clauses.
420 */
421 if (!join_clause_is_movable_to(rinfo, rel))
422 continue;
423
424 /* OK, make list of clauses for this path */
425 tidquals = list_make1(rinfo);
426
427 /* Compute required outer rels for this path */
428 required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
429 required_outer = bms_del_member(required_outer, rel->relid);
430
431 add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
432 required_outer));
433 }
434 }
435
436 /*
437 * Test whether an EquivalenceClass member matches our rel's CTID Var.
438 *
439 * This is a callback for use by generate_implied_equalities_for_column.
440 */
441 static bool
ec_member_matches_ctid(PlannerInfo * root,RelOptInfo * rel,EquivalenceClass * ec,EquivalenceMember * em,void * arg)442 ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel,
443 EquivalenceClass *ec, EquivalenceMember *em,
444 void *arg)
445 {
446 if (em->em_expr && IsA(em->em_expr, Var) &&
447 IsCTIDVar((Var *) em->em_expr, rel))
448 return true;
449 return false;
450 }
451
452 /*
453 * create_tidscan_paths
454 * Create paths corresponding to direct TID scans of the given rel.
455 *
456 * Candidate paths are added to the rel's pathlist (using add_path).
457 */
458 void
create_tidscan_paths(PlannerInfo * root,RelOptInfo * rel)459 create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
460 {
461 List *tidquals;
462 List *tidrangequals;
463
464 /*
465 * If any suitable quals exist in the rel's baserestrict list, generate a
466 * plain (unparameterized) TidPath with them.
467 */
468 tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
469
470 if (tidquals != NIL)
471 {
472 /*
473 * This path uses no join clauses, but it could still have required
474 * parameterization due to LATERAL refs in its tlist.
475 */
476 Relids required_outer = rel->lateral_relids;
477
478 add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
479 required_outer));
480 }
481
482 /*
483 * If there are range quals in the baserestrict list, generate a
484 * TidRangePath.
485 */
486 tidrangequals = TidRangeQualFromRestrictInfoList(rel->baserestrictinfo,
487 rel);
488
489 if (tidrangequals != NIL)
490 {
491 /*
492 * This path uses no join clauses, but it could still have required
493 * parameterization due to LATERAL refs in its tlist.
494 */
495 Relids required_outer = rel->lateral_relids;
496
497 add_path(rel, (Path *) create_tidrangescan_path(root, rel,
498 tidrangequals,
499 required_outer));
500 }
501
502 /*
503 * Try to generate parameterized TidPaths using equality clauses extracted
504 * from EquivalenceClasses. (This is important since simple "t1.ctid =
505 * t2.ctid" clauses will turn into ECs.)
506 */
507 if (rel->has_eclass_joins)
508 {
509 List *clauses;
510
511 /* Generate clauses, skipping any that join to lateral_referencers */
512 clauses = generate_implied_equalities_for_column(root,
513 rel,
514 ec_member_matches_ctid,
515 NULL,
516 rel->lateral_referencers);
517
518 /* Generate a path for each usable join clause */
519 BuildParameterizedTidPaths(root, rel, clauses);
520 }
521
522 /*
523 * Also consider parameterized TidPaths using "loose" join quals. Quals
524 * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
525 * join quals, for example.
526 */
527 BuildParameterizedTidPaths(root, rel, rel->joininfo);
528 }
529