Debian Codegraph @

src/backend/optimizer/path/tidpath.c

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