Line data Source code
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 936344 : IsCTIDVar(Var *var, RelOptInfo *rel)
57 : {
58 : /* The vartype check is strictly paranoia */
59 936344 : if (var->varattno == SelfItemPointerAttributeNumber &&
60 5074 : var->vartype == TIDOID &&
61 5074 : var->varno == rel->relid &&
62 4954 : var->varnullingrels == NULL &&
63 4954 : var->varlevelsup == 0)
64 4954 : return true;
65 931390 : 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 918408 : 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 918408 : if (!is_opclause(rinfo->clause))
87 180350 : return false;
88 738058 : node = (OpExpr *) rinfo->clause;
89 :
90 : /* OpExpr must have two arguments */
91 738058 : if (list_length(node->args) != 2)
92 48 : return false;
93 738010 : arg1 = linitial(node->args);
94 738010 : arg2 = lsecond(node->args);
95 :
96 : /* Look for CTID as either argument */
97 738010 : other = NULL;
98 738010 : other_relids = NULL;
99 1443616 : if (arg1 && IsA(arg1, Var) &&
100 705606 : IsCTIDVar((Var *) arg1, rel))
101 : {
102 4532 : other = arg2;
103 4532 : other_relids = rinfo->right_relids;
104 : }
105 850948 : if (!other && arg2 && IsA(arg2, Var) &&
106 112938 : IsCTIDVar((Var *) arg2, rel))
107 : {
108 228 : other = arg1;
109 228 : other_relids = rinfo->left_relids;
110 : }
111 738010 : if (!other)
112 733250 : return false;
113 :
114 : /* The other argument must be a pseudoconstant */
115 9520 : if (bms_is_member(rel->relid, other_relids) ||
116 4760 : contain_volatile_functions(other))
117 0 : return false;
118 :
119 4760 : 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 515248 : IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
132 : {
133 515248 : if (!IsBinaryTidClause(rinfo, rel))
134 512700 : return false;
135 :
136 2548 : if (((OpExpr *) rinfo->clause)->opno == TIDEqualOperator)
137 434 : return true;
138 :
139 2114 : 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 403160 : IsTidRangeClause(RestrictInfo *rinfo, RelOptInfo *rel)
152 : {
153 : Oid opno;
154 :
155 403160 : if (!IsBinaryTidClause(rinfo, rel))
156 400948 : return false;
157 2212 : opno = ((OpExpr *) rinfo->clause)->opno;
158 :
159 2212 : if (opno == TIDLessOperator || opno == TIDLessEqOperator ||
160 2030 : opno == TIDGreaterOperator || opno == TIDGreaterEqOperator)
161 1970 : return true;
162 :
163 242 : 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 396168 : IsTidEqualAnyClause(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
174 : {
175 : ScalarArrayOpExpr *node;
176 : Node *arg1,
177 : *arg2;
178 :
179 : /* Must be a ScalarArrayOpExpr */
180 396168 : if (!(rinfo->clause && IsA(rinfo->clause, ScalarArrayOpExpr)))
181 375154 : return false;
182 21014 : node = (ScalarArrayOpExpr *) rinfo->clause;
183 :
184 : /* Operator must be tideq */
185 21014 : if (node->opno != TIDEqualOperator)
186 20952 : return false;
187 62 : if (!node->useOr)
188 0 : return false;
189 : Assert(list_length(node->args) == 2);
190 62 : arg1 = linitial(node->args);
191 62 : arg2 = lsecond(node->args);
192 :
193 : /* CTID must be first argument */
194 124 : if (arg1 && IsA(arg1, Var) &&
195 62 : IsCTIDVar((Var *) arg1, rel))
196 : {
197 : /* The other argument must be a pseudoconstant */
198 124 : if (bms_is_member(rel->relid, pull_varnos(root, arg2)) ||
199 62 : contain_volatile_functions(arg2))
200 0 : return false;
201 :
202 62 : return true; /* success */
203 : }
204 :
205 0 : return false;
206 : }
207 :
208 : /*
209 : * Check to see if a RestrictInfo is a CurrentOfExpr referencing "rel".
210 : */
211 : static bool
212 396826 : IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
213 : {
214 : CurrentOfExpr *node;
215 :
216 : /* Must be a CurrentOfExpr */
217 396826 : if (!(rinfo->clause && IsA(rinfo->clause, CurrentOfExpr)))
218 396018 : return false;
219 808 : node = (CurrentOfExpr *) rinfo->clause;
220 :
221 : /* If it references this rel, we're good */
222 808 : if (node->cvarno == rel->relid)
223 808 : return true;
224 :
225 0 : 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 404700 : 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 404700 : if (rinfo->pseudoconstant)
242 6656 : return false;
243 :
244 : /*
245 : * If clause must wait till after some lower-security-level restriction
246 : * clause, reject it.
247 : */
248 398044 : if (!restriction_is_securely_promotable(rinfo, rel))
249 1598 : return false;
250 :
251 : /*
252 : * Check all base cases.
253 : */
254 792614 : if (IsTidEqualClause(rinfo, rel) ||
255 792274 : IsTidEqualAnyClause(root, rinfo, rel) ||
256 396106 : IsCurrentOfClause(rinfo, rel))
257 744 : return true;
258 :
259 395702 : 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 405430 : TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel,
282 : bool *isCurrentOf)
283 : {
284 405430 : RestrictInfo *tidclause = NULL; /* best simple CTID qual so far */
285 405430 : List *orlist = NIL; /* best OR'ed CTID qual so far */
286 : ListCell *l;
287 :
288 405430 : *isCurrentOf = false;
289 :
290 810502 : foreach(l, rlist)
291 : {
292 405476 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
293 :
294 405476 : if (restriction_is_or_clause(rinfo))
295 : {
296 4838 : 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 4886 : foreach(j, ((BoolExpr *) rinfo->orclause)->args)
304 : {
305 4862 : Node *orarg = (Node *) lfirst(j);
306 : List *sublist;
307 :
308 : /* OR arguments should be ANDs or sub-RestrictInfos */
309 4862 : if (is_andclause(orarg))
310 : {
311 800 : List *andargs = ((BoolExpr *) orarg)->args;
312 : bool sublistIsCurrentOf;
313 :
314 : /* Recurse in case there are sub-ORs */
315 800 : sublist = TidQualFromRestrictInfoList(root, andargs, rel,
316 : &sublistIsCurrentOf);
317 800 : if (sublistIsCurrentOf)
318 0 : elog(ERROR, "IS CURRENT OF within OR clause");
319 : }
320 : else
321 : {
322 4062 : RestrictInfo *ri = castNode(RestrictInfo, orarg);
323 :
324 : Assert(!restriction_is_or_clause(ri));
325 4062 : if (RestrictInfoIsTidQual(root, ri, rel))
326 24 : sublist = list_make1(ri);
327 : else
328 4038 : sublist = NIL;
329 : }
330 :
331 : /*
332 : * If nothing found in this arm, we can't do anything with
333 : * this OR clause.
334 : */
335 4862 : if (sublist == NIL)
336 : {
337 4814 : rlst = NIL; /* forget anything we had */
338 4814 : break; /* out of loop over OR args */
339 : }
340 :
341 : /*
342 : * OK, continue constructing implicitly-OR'ed result list.
343 : */
344 48 : rlst = list_concat(rlst, sublist);
345 : }
346 :
347 4838 : 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 24 : if (orlist == NIL || list_length(rlst) < list_length(orlist))
354 24 : orlist = rlst;
355 : }
356 : }
357 : else
358 : {
359 : /* Not an OR clause, so handle base cases */
360 400638 : if (RestrictInfoIsTidQual(root, rinfo, rel))
361 : {
362 : /* We can stop immediately if it's a CurrentOfExpr */
363 720 : if (IsCurrentOfClause(rinfo, rel))
364 : {
365 404 : *isCurrentOf = true;
366 404 : 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 316 : if (tidclause == NULL)
375 316 : 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 405026 : if (tidclause)
385 304 : return list_make1(tidclause);
386 404722 : 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 404226 : TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
399 : {
400 404226 : List *rlst = NIL;
401 : ListCell *l;
402 :
403 404226 : if ((rel->amflags & AMFLAG_HAS_TID_RANGE) == 0)
404 0 : return NIL;
405 :
406 807386 : foreach(l, rlist)
407 : {
408 403160 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
409 :
410 403160 : if (IsTidRangeClause(rinfo, rel))
411 1970 : rlst = lappend(rlst, rinfo);
412 : }
413 :
414 404226 : 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 534834 : BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
427 : {
428 : ListCell *l;
429 :
430 663608 : foreach(l, clauses)
431 : {
432 128774 : 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 128774 : if (rinfo->pseudoconstant ||
451 118802 : !restriction_is_securely_promotable(rinfo, rel) ||
452 118802 : !IsTidEqualClause(rinfo, rel))
453 128630 : 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 156 : if (!join_clause_is_movable_to(rinfo, rel))
461 12 : continue;
462 :
463 : /* OK, make list of clauses for this path */
464 144 : tidquals = list_make1(rinfo);
465 :
466 : /* Compute required outer rels for this path */
467 144 : required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
468 144 : required_outer = bms_del_member(required_outer, rel->relid);
469 :
470 144 : add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
471 : required_outer));
472 : }
473 534834 : }
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 121398 : ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel,
482 : EquivalenceClass *ec, EquivalenceMember *em,
483 : void *arg)
484 : {
485 239136 : if (em->em_expr && IsA(em->em_expr, Var) &&
486 117738 : IsCTIDVar((Var *) em->em_expr, rel))
487 132 : return true;
488 121266 : 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 404630 : 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 404630 : tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel,
512 : &isCurrentOf);
513 :
514 404630 : 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 708 : Relids required_outer = rel->lateral_relids;
521 :
522 708 : 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 708 : if (isCurrentOf)
532 404 : return true;
533 : }
534 :
535 : /* Skip the rest if TID scans are disabled. */
536 404226 : if (!enable_tidscan)
537 0 : return false;
538 :
539 : /*
540 : * If there are range quals in the baserestrict list, generate a
541 : * TidRangePath.
542 : */
543 404226 : tidrangequals = TidRangeQualFromRestrictInfoList(rel->baserestrictinfo,
544 : rel);
545 :
546 404226 : 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 1940 : Relids required_outer = rel->lateral_relids;
553 :
554 1940 : 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 404226 : if (rel->has_eclass_joins)
565 : {
566 : List *clauses;
567 :
568 : /* Generate clauses, skipping any that join to lateral_referencers */
569 130608 : 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 130608 : 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 404226 : BuildParameterizedTidPaths(root, rel, rel->joininfo);
585 :
586 404226 : return false;
587 : }
|
