TLA 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-2023, 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
56 CBC 340363 : IsCTIDVar(Var *var, RelOptInfo *rel)
57 : {
58 : /* The vartype check is strictly paranoia */
59 340363 : if (var->varattno == SelfItemPointerAttributeNumber &&
60 710 : var->vartype == TIDOID &&
61 710 : var->varno == rel->relid &&
62 GNC 653 : var->varnullingrels == NULL &&
63 CBC 653 : var->varlevelsup == 0)
64 653 : return true;
65 339710 : return false;
66 ECB : }
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 GIC 340427 : IsBinaryTidClause(RestrictInfo *rinfo, RelOptInfo *rel)
78 ECB : {
79 : OpExpr *node;
80 : Node *arg1,
81 : *arg2,
82 : *other;
83 : Relids other_relids;
84 :
85 : /* Must be an OpExpr */
86 GIC 340427 : if (!is_opclause(rinfo->clause))
87 CBC 70386 : return false;
88 270041 : node = (OpExpr *) rinfo->clause;
89 ECB :
90 : /* OpExpr must have two arguments */
91 GIC 270041 : if (list_length(node->args) != 2)
92 CBC 24 : return false;
93 270017 : arg1 = linitial(node->args);
94 270017 : arg2 = lsecond(node->args);
95 ECB :
96 : /* Look for CTID as either argument */
97 GIC 270017 : other = NULL;
98 CBC 270017 : other_relids = NULL;
99 525563 : if (arg1 && IsA(arg1, Var) &&
100 255546 : IsCTIDVar((Var *) arg1, rel))
101 ECB : {
102 GIC 461 : other = arg2;
103 CBC 461 : other_relids = rinfo->right_relids;
104 ECB : }
105 GIC 315483 : if (!other && arg2 && IsA(arg2, Var) &&
106 CBC 45466 : IsCTIDVar((Var *) arg2, rel))
107 ECB : {
108 GIC 111 : other = arg1;
109 CBC 111 : other_relids = rinfo->left_relids;
110 ECB : }
111 GIC 270017 : if (!other)
112 CBC 269445 : return false;
113 ECB :
114 : /* The other argument must be a pseudoconstant */
115 GIC 1144 : if (bms_is_member(rel->relid, other_relids) ||
116 CBC 572 : contain_volatile_functions(other))
117 LBC 0 : return false;
118 EUB :
119 GIC 572 : return true; /* success */
120 ECB : }
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 GIC 191925 : IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
132 ECB : {
133 GIC 191925 : if (!IsBinaryTidClause(rinfo, rel))
134 CBC 191558 : return false;
135 ECB :
136 GIC 367 : if (((OpExpr *) rinfo->clause)->opno == TIDEqualOperator)
137 CBC 185 : return true;
138 ECB :
139 GIC 182 : return false;
140 ECB : }
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 GIC 148502 : IsTidRangeClause(RestrictInfo *rinfo, RelOptInfo *rel)
152 ECB : {
153 : Oid opno;
154 :
155 GIC 148502 : if (!IsBinaryTidClause(rinfo, rel))
156 CBC 148297 : return false;
157 205 : opno = ((OpExpr *) rinfo->clause)->opno;
158 ECB :
159 GIC 205 : if (opno == TIDLessOperator || opno == TIDLessEqOperator ||
160 CBC 116 : opno == TIDGreaterOperator || opno == TIDGreaterEqOperator)
161 116 : return true;
162 ECB :
163 GIC 89 : return false;
164 ECB : }
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 GIC 145416 : IsTidEqualAnyClause(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
174 ECB : {
175 : ScalarArrayOpExpr *node;
176 : Node *arg1,
177 : *arg2;
178 :
179 : /* Must be a ScalarArrayOpExpr */
180 GIC 145416 : if (!(rinfo->clause && IsA(rinfo->clause, ScalarArrayOpExpr)))
181 CBC 138250 : return false;
182 7166 : node = (ScalarArrayOpExpr *) rinfo->clause;
183 ECB :
184 : /* Operator must be tideq */
185 GIC 7166 : if (node->opno != TIDEqualOperator)
186 CBC 7151 : return false;
187 15 : if (!node->useOr)
188 LBC 0 : return false;
189 GBC 15 : Assert(list_length(node->args) == 2);
190 CBC 15 : arg1 = linitial(node->args);
191 15 : arg2 = lsecond(node->args);
192 ECB :
193 : /* CTID must be first argument */
194 GIC 30 : if (arg1 && IsA(arg1, Var) &&
195 CBC 15 : IsCTIDVar((Var *) arg1, rel))
196 ECB : {
197 : /* The other argument must be a pseudoconstant */
198 GIC 30 : if (bms_is_member(rel->relid, pull_varnos(root, arg2)) ||
199 CBC 15 : contain_volatile_functions(arg2))
200 LBC 0 : return false;
201 EUB :
202 GIC 15 : return true; /* success */
203 ECB : }
204 :
205 UIC 0 : return false;
206 EUB : }
207 :
208 : /*
209 : * Check to see if a RestrictInfo is a CurrentOfExpr referencing "rel".
210 : */
211 : static bool
212 GIC 145401 : IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
213 ECB : {
214 : CurrentOfExpr *node;
215 :
216 : /* Must be a CurrentOfExpr */
217 GIC 145401 : if (!(rinfo->clause && IsA(rinfo->clause, CurrentOfExpr)))
218 CBC 145205 : return false;
219 196 : node = (CurrentOfExpr *) rinfo->clause;
220 ECB :
221 : /* If it references this rel, we're good */
222 GIC 196 : if (node->cvarno == rel->relid)
223 CBC 196 : return true;
224 ECB :
225 UIC 0 : return false;
226 EUB : }
227 :
228 : /*
229 : * Extract a set of CTID conditions from the given RestrictInfo
230 : *
231 : * Returns a List of CTID qual RestrictInfos for the specified rel (with
232 : * implicit OR semantics across the list), or NIL if there are no usable
233 : * conditions.
234 : *
235 : * This function considers only base cases; AND/OR combination is handled
236 : * below. Therefore the returned List never has more than one element.
237 : * (Using a List may seem a bit weird, but it simplifies the caller.)
238 : */
239 : static List *
240 GIC 148878 : TidQualFromRestrictInfo(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
241 ECB : {
242 : /*
243 : * We may ignore pseudoconstant clauses (they can't contain Vars, so could
244 : * not match anyway).
245 : */
246 GIC 148878 : if (rinfo->pseudoconstant)
247 CBC 2541 : return NIL;
248 ECB :
249 : /*
250 : * If clause must wait till after some lower-security-level restriction
251 : * clause, reject it.
252 : */
253 GIC 146337 : if (!restriction_is_securely_promotable(rinfo, rel))
254 CBC 814 : return NIL;
255 ECB :
256 : /*
257 : * Check all base cases. If we get a match, return the clause.
258 : */
259 GIC 290939 : if (IsTidEqualClause(rinfo, rel) ||
260 CBC 290817 : IsTidEqualAnyClause(root, rinfo, rel) ||
261 145401 : IsCurrentOfClause(rinfo, rel))
262 318 : return list_make1(rinfo);
263 ECB :
264 GIC 145205 : return NIL;
265 ECB : }
266 :
267 : /*
268 : * Extract a set of CTID conditions from implicit-AND List of RestrictInfos
269 : *
270 : * Returns a List of CTID qual RestrictInfos for the specified rel (with
271 : * implicit OR semantics across the list), or NIL if there are no usable
272 : * equality conditions.
273 : *
274 : * This function is just concerned with handling AND/OR recursion.
275 : */
276 : static List *
277 GIC 157672 : TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel)
278 ECB : {
279 GIC 157672 : List *rlst = NIL;
280 ECB : ListCell *l;
281 :
282 GIC 306541 : foreach(l, rlist)
283 ECB : {
284 GIC 149187 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
285 ECB :
286 GIC 149187 : if (restriction_is_or_clause(rinfo))
287 ECB : {
288 : ListCell *j;
289 :
290 : /*
291 : * We must be able to extract a CTID condition from every
292 : * sub-clause of an OR, or we can't use it.
293 : */
294 GIC 1647 : foreach(j, ((BoolExpr *) rinfo->orclause)->args)
295 ECB : {
296 GIC 1635 : Node *orarg = (Node *) lfirst(j);
297 ECB : List *sublist;
298 :
299 : /* OR arguments should be ANDs or sub-RestrictInfos */
300 GIC 1635 : if (is_andclause(orarg))
301 ECB : {
302 GIC 321 : List *andargs = ((BoolExpr *) orarg)->args;
303 ECB :
304 : /* Recurse in case there are sub-ORs */
305 GIC 321 : sublist = TidQualFromRestrictInfoList(root, andargs, rel);
306 ECB : }
307 : else
308 : {
309 GNC 1314 : RestrictInfo *ri = castNode(RestrictInfo, orarg);
310 ECB :
311 GNC 1314 : Assert(!restriction_is_or_clause(ri));
312 1314 : sublist = TidQualFromRestrictInfo(root, ri, rel);
313 ECB : }
314 :
315 : /*
316 : * If nothing found in this arm, we can't do anything with
317 : * this OR clause.
318 : */
319 GIC 1635 : if (sublist == NIL)
320 ECB : {
321 GIC 1611 : rlst = NIL; /* forget anything we had */
322 CBC 1611 : break; /* out of loop over OR args */
323 ECB : }
324 :
325 : /*
326 : * OK, continue constructing implicitly-OR'ed result list.
327 : */
328 GIC 24 : rlst = list_concat(rlst, sublist);
329 ECB : }
330 : }
331 : else
332 : {
333 : /* Not an OR clause, so handle base cases */
334 GIC 147564 : rlst = TidQualFromRestrictInfo(root, rinfo, rel);
335 ECB : }
336 :
337 : /*
338 : * Stop as soon as we find any usable CTID condition. In theory we
339 : * could get CTID equality conditions from different AND'ed clauses,
340 : * in which case we could try to pick the most efficient one. In
341 : * practice, such usage seems very unlikely, so we don't bother; we
342 : * just exit as soon as we find the first candidate.
343 : */
344 GIC 149187 : if (rlst)
345 CBC 318 : break;
346 ECB : }
347 :
348 GIC 157672 : return rlst;
349 ECB : }
350 :
351 : /*
352 : * Extract a set of CTID range conditions from implicit-AND List of RestrictInfos
353 : *
354 : * Returns a List of CTID range qual RestrictInfos for the specified rel
355 : * (with implicit AND semantics across the list), or NIL if there are no
356 : * usable range conditions or if the rel's table AM does not support TID range
357 : * scans.
358 : */
359 : static List *
360 GIC 157351 : TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
361 ECB : {
362 GIC 157351 : List *rlst = NIL;
363 ECB : ListCell *l;
364 :
365 GIC 157351 : if ((rel->amflags & AMFLAG_HAS_TID_RANGE) == 0)
366 LBC 0 : return NIL;
367 EUB :
368 GIC 305853 : foreach(l, rlist)
369 ECB : {
370 GIC 148502 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
371 ECB :
372 GIC 148502 : if (IsTidRangeClause(rinfo, rel))
373 CBC 116 : rlst = lappend(rlst, rinfo);
374 ECB : }
375 :
376 GIC 157351 : return rlst;
377 ECB : }
378 :
379 : /*
380 : * Given a list of join clauses involving our rel, create a parameterized
381 : * TidPath for each one that is a suitable TidEqual clause.
382 : *
383 : * In principle we could combine clauses that reference the same outer rels,
384 : * but it doesn't seem like such cases would arise often enough to be worth
385 : * troubling over.
386 : */
387 : static void
388 GIC 201481 : BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
389 ECB : {
390 : ListCell *l;
391 :
392 GIC 251546 : foreach(l, clauses)
393 ECB : {
394 GIC 50065 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
395 ECB : List *tidquals;
396 : Relids required_outer;
397 :
398 : /*
399 : * Validate whether each clause is actually usable; we must check this
400 : * even when examining clauses generated from an EquivalenceClass,
401 : * since they might not satisfy the restriction on not having Vars of
402 : * our rel on the other side, or somebody might've built an operator
403 : * class that accepts type "tid" but has other operators in it.
404 : *
405 : * We currently consider only TidEqual join clauses. In principle we
406 : * might find a suitable ScalarArrayOpExpr in the rel's joininfo list,
407 : * but it seems unlikely to be worth expending the cycles to check.
408 : * And we definitely won't find a CurrentOfExpr here. Hence, we don't
409 : * use TidQualFromRestrictInfo; but this must match that function
410 : * otherwise.
411 : */
412 GIC 50065 : if (rinfo->pseudoconstant ||
413 CBC 46402 : !restriction_is_securely_promotable(rinfo, rel) ||
414 46402 : !IsTidEqualClause(rinfo, rel))
415 49993 : continue;
416 ECB :
417 : /*
418 : * Check if clause can be moved to this rel; this is probably
419 : * redundant when considering EC-derived clauses, but we must check it
420 : * for "loose" join clauses.
421 : */
422 GIC 78 : if (!join_clause_is_movable_to(rinfo, rel))
423 CBC 6 : continue;
424 ECB :
425 : /* OK, make list of clauses for this path */
426 GIC 72 : tidquals = list_make1(rinfo);
427 ECB :
428 : /* Compute required outer rels for this path */
429 GIC 72 : required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
430 CBC 72 : required_outer = bms_del_member(required_outer, rel->relid);
431 ECB :
432 GIC 72 : add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
433 ECB : required_outer));
434 : }
435 GIC 201481 : }
436 ECB :
437 : /*
438 : * Test whether an EquivalenceClass member matches our rel's CTID Var.
439 : *
440 : * This is a callback for use by generate_implied_equalities_for_column.
441 : */
442 : static bool
443 GIC 40534 : ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel,
444 ECB : EquivalenceClass *ec, EquivalenceMember *em,
445 : void *arg)
446 : {
447 GIC 79870 : if (em->em_expr && IsA(em->em_expr, Var) &&
448 CBC 39336 : IsCTIDVar((Var *) em->em_expr, rel))
449 66 : return true;
450 40468 : return false;
451 ECB : }
452 :
453 : /*
454 : * create_tidscan_paths
455 : * Create paths corresponding to direct TID scans of the given rel.
456 : *
457 : * Candidate paths are added to the rel's pathlist (using add_path).
458 : */
459 : void
460 GIC 157351 : create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
461 ECB : {
462 : List *tidquals;
463 : List *tidrangequals;
464 :
465 : /*
466 : * If any suitable quals exist in the rel's baserestrict list, generate a
467 : * plain (unparameterized) TidPath with them.
468 : */
469 GIC 157351 : tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
470 ECB :
471 GIC 157351 : if (tidquals != NIL)
472 ECB : {
473 : /*
474 : * This path uses no join clauses, but it could still have required
475 : * parameterization due to LATERAL refs in its tlist.
476 : */
477 GIC 306 : Relids required_outer = rel->lateral_relids;
478 ECB :
479 GIC 306 : add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
480 ECB : required_outer));
481 : }
482 :
483 : /*
484 : * If there are range quals in the baserestrict list, generate a
485 : * TidRangePath.
486 : */
487 GIC 157351 : tidrangequals = TidRangeQualFromRestrictInfoList(rel->baserestrictinfo,
488 ECB : rel);
489 :
490 GIC 157351 : if (tidrangequals != NIL)
491 ECB : {
492 : /*
493 : * This path uses no join clauses, but it could still have required
494 : * parameterization due to LATERAL refs in its tlist.
495 : */
496 GIC 101 : Relids required_outer = rel->lateral_relids;
497 ECB :
498 GIC 101 : add_path(rel, (Path *) create_tidrangescan_path(root, rel,
499 ECB : tidrangequals,
500 : required_outer));
501 : }
502 :
503 : /*
504 : * Try to generate parameterized TidPaths using equality clauses extracted
505 : * from EquivalenceClasses. (This is important since simple "t1.ctid =
506 : * t2.ctid" clauses will turn into ECs.)
507 : */
508 GIC 157351 : if (rel->has_eclass_joins)
509 ECB : {
510 : List *clauses;
511 :
512 : /* Generate clauses, skipping any that join to lateral_referencers */
513 GIC 44130 : clauses = generate_implied_equalities_for_column(root,
514 ECB : rel,
515 : ec_member_matches_ctid,
516 : NULL,
517 : rel->lateral_referencers);
518 :
519 : /* Generate a path for each usable join clause */
520 GIC 44130 : BuildParameterizedTidPaths(root, rel, clauses);
521 ECB : }
522 :
523 : /*
524 : * Also consider parameterized TidPaths using "loose" join quals. Quals
525 : * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
526 : * join quals, for example.
527 : */
528 GIC 157351 : BuildParameterizedTidPaths(root, rel, rel->joininfo);
529 CBC 157351 : }
|