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-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
55 794746 : IsCTIDVar(Var *var, RelOptInfo *rel)
56 : {
57 : /* The vartype check is strictly paranoia */
58 794746 : if (var->varattno == SelfItemPointerAttributeNumber &&
59 1468 : var->vartype == TIDOID &&
60 1468 : var->varno == rel->relid &&
61 1348 : var->varnullingrels == NULL &&
62 1348 : var->varlevelsup == 0)
63 1348 : return true;
64 793398 : 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
76 785850 : 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 785850 : if (!is_opclause(rinfo->clause))
86 156212 : return false;
87 629638 : node = (OpExpr *) rinfo->clause;
88 :
89 : /* OpExpr must have two arguments */
90 629638 : if (list_length(node->args) != 2)
91 48 : return false;
92 629590 : arg1 = linitial(node->args);
93 629590 : arg2 = lsecond(node->args);
94 :
95 : /* Look for CTID as either argument */
96 629590 : other = NULL;
97 629590 : other_relids = NULL;
98 1229346 : if (arg1 && IsA(arg1, Var) &&
99 599756 : IsCTIDVar((Var *) arg1, rel))
100 : {
101 928 : other = arg2;
102 928 : other_relids = rinfo->right_relids;
103 : }
104 733386 : if (!other && arg2 && IsA(arg2, Var) &&
105 103796 : IsCTIDVar((Var *) arg2, rel))
106 : {
107 228 : other = arg1;
108 228 : other_relids = rinfo->left_relids;
109 : }
110 629590 : if (!other)
111 628434 : return false;
112 :
113 : /* The other argument must be a pseudoconstant */
114 2312 : if (bms_is_member(rel->relid, other_relids) ||
115 1156 : contain_volatile_functions(other))
116 0 : return false;
117 :
118 1156 : 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
130 442972 : IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
131 : {
132 442972 : if (!IsBinaryTidClause(rinfo, rel))
133 442226 : return false;
134 :
135 746 : if (((OpExpr *) rinfo->clause)->opno == TIDEqualOperator)
136 370 : return true;
137 :
138 376 : 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
150 342878 : IsTidRangeClause(RestrictInfo *rinfo, RelOptInfo *rel)
151 : {
152 : Oid opno;
153 :
154 342878 : if (!IsBinaryTidClause(rinfo, rel))
155 342468 : return false;
156 410 : opno = ((OpExpr *) rinfo->clause)->opno;
157 :
158 410 : if (opno == TIDLessOperator || opno == TIDLessEqOperator ||
159 232 : opno == TIDGreaterOperator || opno == TIDGreaterEqOperator)
160 232 : return true;
161 :
162 178 : 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
172 336028 : IsTidEqualAnyClause(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
173 : {
174 : ScalarArrayOpExpr *node;
175 : Node *arg1,
176 : *arg2;
177 :
178 : /* Must be a ScalarArrayOpExpr */
179 336028 : if (!(rinfo->clause && IsA(rinfo->clause, ScalarArrayOpExpr)))
180 321286 : return false;
181 14742 : node = (ScalarArrayOpExpr *) rinfo->clause;
182 :
183 : /* Operator must be tideq */
184 14742 : if (node->opno != TIDEqualOperator)
185 14682 : return false;
186 60 : if (!node->useOr)
187 0 : return false;
188 : Assert(list_length(node->args) == 2);
189 60 : arg1 = linitial(node->args);
190 60 : arg2 = lsecond(node->args);
191 :
192 : /* CTID must be first argument */
193 120 : if (arg1 && IsA(arg1, Var) &&
194 60 : IsCTIDVar((Var *) arg1, rel))
195 : {
196 : /* The other argument must be a pseudoconstant */
197 120 : if (bms_is_member(rel->relid, pull_varnos(root, arg2)) ||
198 60 : contain_volatile_functions(arg2))
199 0 : return false;
200 :
201 60 : return true; /* success */
202 : }
203 :
204 0 : return false;
205 : }
206 :
207 : /*
208 : * Check to see if a RestrictInfo is a CurrentOfExpr referencing "rel".
209 : */
210 : static bool
211 336622 : IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
212 : {
213 : CurrentOfExpr *node;
214 :
215 : /* Must be a CurrentOfExpr */
216 336622 : if (!(rinfo->clause && IsA(rinfo->clause, CurrentOfExpr)))
217 335814 : return false;
218 808 : node = (CurrentOfExpr *) rinfo->clause;
219 :
220 : /* If it references this rel, we're good */
221 808 : if (node->cvarno == rel->relid)
222 808 : return true;
223 :
224 0 : 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
234 343754 : RestrictInfoIsTidQual(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
235 : {
236 : /*
237 : * We may ignore pseudoconstant clauses (they can't contain Vars, so could
238 : * not match anyway).
239 : */
240 343754 : if (rinfo->pseudoconstant)
241 5926 : return false;
242 :
243 : /*
244 : * If clause must wait till after some lower-security-level restriction
245 : * clause, reject it.
246 : */
247 337828 : if (!restriction_is_securely_promotable(rinfo, rel))
248 1586 : return false;
249 :
250 : /*
251 : * Check all base cases.
252 : */
253 672270 : if (IsTidEqualClause(rinfo, rel) ||
254 671996 : IsTidEqualAnyClause(root, rinfo, rel) ||
255 335968 : IsCurrentOfClause(rinfo, rel))
256 678 : return true;
257 :
258 335564 : 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 *
280 349834 : TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel)
281 : {
282 349834 : RestrictInfo *tidclause = NULL; /* best simple CTID qual so far */
283 349834 : List *orlist = NIL; /* best OR'ed CTID qual so far */
284 : ListCell *l;
285 :
286 693860 : foreach(l, rlist)
287 : {
288 344430 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
289 :
290 344430 : if (restriction_is_or_clause(rinfo))
291 : {
292 3628 : 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 3676 : foreach(j, ((BoolExpr *) rinfo->orclause)->args)
300 : {
301 3652 : Node *orarg = (Node *) lfirst(j);
302 : List *sublist;
303 :
304 : /* OR arguments should be ANDs or sub-RestrictInfos */
305 3652 : if (is_andclause(orarg))
306 : {
307 700 : List *andargs = ((BoolExpr *) orarg)->args;
308 :
309 : /* Recurse in case there are sub-ORs */
310 700 : sublist = TidQualFromRestrictInfoList(root, andargs, rel);
311 : }
312 : else
313 : {
314 2952 : RestrictInfo *ri = castNode(RestrictInfo, orarg);
315 :
316 : Assert(!restriction_is_or_clause(ri));
317 2952 : if (RestrictInfoIsTidQual(root, ri, rel))
318 24 : sublist = list_make1(ri);
319 : else
320 2928 : sublist = NIL;
321 : }
322 :
323 : /*
324 : * If nothing found in this arm, we can't do anything with
325 : * this OR clause.
326 : */
327 3652 : if (sublist == NIL)
328 : {
329 3604 : rlst = NIL; /* forget anything we had */
330 3604 : break; /* out of loop over OR args */
331 : }
332 :
333 : /*
334 : * OK, continue constructing implicitly-OR'ed result list.
335 : */
336 48 : rlst = list_concat(rlst, sublist);
337 : }
338 :
339 3628 : 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 24 : if (orlist == NIL || list_length(rlst) < list_length(orlist))
346 24 : orlist = rlst;
347 : }
348 : }
349 : else
350 : {
351 : /* Not an OR clause, so handle base cases */
352 340802 : if (RestrictInfoIsTidQual(root, rinfo, rel))
353 : {
354 : /* We can stop immediately if it's a CurrentOfExpr */
355 654 : if (IsCurrentOfClause(rinfo, rel))
356 404 : 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 250 : if (tidclause == NULL)
364 250 : 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 349430 : if (tidclause)
374 238 : return list_make1(tidclause);
375 349192 : 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 *
387 349134 : TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
388 : {
389 349134 : List *rlst = NIL;
390 : ListCell *l;
391 :
392 349134 : if ((rel->amflags & AMFLAG_HAS_TID_RANGE) == 0)
393 0 : return NIL;
394 :
395 692012 : foreach(l, rlist)
396 : {
397 342878 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
398 :
399 342878 : if (IsTidRangeClause(rinfo, rel))
400 232 : rlst = lappend(rlst, rinfo);
401 : }
402 :
403 349134 : 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
415 455036 : BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
416 : {
417 : ListCell *l;
418 :
419 570412 : foreach(l, clauses)
420 : {
421 115376 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
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 115376 : if (rinfo->pseudoconstant ||
440 106730 : !restriction_is_securely_promotable(rinfo, rel) ||
441 106730 : !IsTidEqualClause(rinfo, rel))
442 115232 : 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 156 : if (!join_clause_is_movable_to(rinfo, rel))
450 12 : continue;
451 :
452 : /* OK, make list of clauses for this path */
453 144 : tidquals = list_make1(rinfo);
454 :
455 : /* Compute required outer rels for this path */
456 144 : required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
457 144 : required_outer = bms_del_member(required_outer, rel->relid);
458 :
459 144 : add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
460 : required_outer));
461 : }
462 455036 : }
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
470 94498 : ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel,
471 : EquivalenceClass *ec, EquivalenceMember *em,
472 : void *arg)
473 : {
474 185632 : if (em->em_expr && IsA(em->em_expr, Var) &&
475 91134 : IsCTIDVar((Var *) em->em_expr, rel))
476 132 : return true;
477 94366 : 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
487 349134 : create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
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 349134 : tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
497 :
498 349134 : 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 642 : Relids required_outer = rel->lateral_relids;
505 :
506 642 : 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 : */
514 349134 : tidrangequals = TidRangeQualFromRestrictInfoList(rel->baserestrictinfo,
515 : rel);
516 :
517 349134 : 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 202 : Relids required_outer = rel->lateral_relids;
524 :
525 202 : add_path(rel, (Path *) create_tidrangescan_path(root, rel,
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 349134 : if (rel->has_eclass_joins)
536 : {
537 : List *clauses;
538 :
539 : /* Generate clauses, skipping any that join to lateral_referencers */
540 105902 : clauses = generate_implied_equalities_for_column(root,
541 : rel,
542 : ec_member_matches_ctid,
543 : NULL,
544 : rel->lateral_referencers);
545 :
546 : /* Generate a path for each usable join clause */
547 105902 : 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 : */
555 349134 : BuildParameterizedTidPaths(root, rel, rel->joininfo);
556 349134 : }
|