Age Owner Branch data 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-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
1932 tgl@sss.pgh.pa.us 55 :CBC 393837 : IsCTIDVar(Var *var, RelOptInfo *rel)
56 : : {
57 : : /* The vartype check is strictly paranoia */
58 [ + + ]: 393837 : if (var->varattno == SelfItemPointerAttributeNumber &&
59 [ + - ]: 719 : var->vartype == TIDOID &&
60 [ + + ]: 719 : var->varno == rel->relid &&
440 61 [ + - ]: 659 : var->varnullingrels == NULL &&
1932 62 [ + - ]: 659 : var->varlevelsup == 0)
63 : 659 : return true;
64 : 393178 : 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
1142 drowley@postgresql.o 76 : 388172 : 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 */
1932 tgl@sss.pgh.pa.us 85 [ + + ]: 388172 : if (!is_opclause(rinfo->clause))
86 : 76773 : return false;
87 : 311399 : node = (OpExpr *) rinfo->clause;
88 : :
89 : : /* OpExpr must have two arguments */
1142 drowley@postgresql.o 90 [ + + ]: 311399 : if (list_length(node->args) != 2)
6714 tgl@sss.pgh.pa.us 91 : 24 : return false;
7263 neilc@samurai.com 92 : 311375 : arg1 = linitial(node->args);
8909 bruce@momjian.us 93 : 311375 : arg2 = lsecond(node->args);
94 : :
95 : : /* Look for CTID as either argument */
6809 tgl@sss.pgh.pa.us 96 : 311375 : other = NULL;
1932 97 : 311375 : other_relids = NULL;
98 [ + - + + : 607834 : if (arg1 && IsA(arg1, Var) &&
+ + ]
99 : 296459 : IsCTIDVar((Var *) arg1, rel))
100 : : {
101 : 464 : other = arg2;
102 : 464 : other_relids = rinfo->right_relids;
103 : : }
104 [ + + + - : 363295 : if (!other && arg2 && IsA(arg2, Var) &&
+ + + + ]
105 : 51920 : IsCTIDVar((Var *) arg2, rel))
106 : : {
107 : 114 : other = arg1;
108 : 114 : other_relids = rinfo->left_relids;
109 : : }
6809 110 [ + + ]: 311375 : if (!other)
6714 111 : 310797 : return false;
112 : :
113 : : /* The other argument must be a pseudoconstant */
1932 114 [ + - - + ]: 1156 : if (bms_is_member(rel->relid, other_relids) ||
115 : 578 : contain_volatile_functions(other))
6714 tgl@sss.pgh.pa.us 116 :UBC 0 : return false;
117 : :
6714 tgl@sss.pgh.pa.us 118 :CBC 578 : 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
1142 drowley@postgresql.o 130 : 219212 : IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
131 : : {
132 [ + + ]: 219212 : if (!IsBinaryTidClause(rinfo, rel))
133 : 218839 : return false;
134 : :
135 [ + + ]: 373 : if (((OpExpr *) rinfo->clause)->opno == TIDEqualOperator)
136 : 185 : return true;
137 : :
138 : 188 : 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 : 168960 : IsTidRangeClause(RestrictInfo *rinfo, RelOptInfo *rel)
151 : : {
152 : : Oid opno;
153 : :
154 [ + + ]: 168960 : if (!IsBinaryTidClause(rinfo, rel))
155 : 168755 : return false;
156 : 205 : opno = ((OpExpr *) rinfo->clause)->opno;
157 : :
158 [ + + + + : 205 : if (opno == TIDLessOperator || opno == TIDLessEqOperator ||
+ + ]
159 [ + + ]: 116 : opno == TIDGreaterOperator || opno == TIDGreaterEqOperator)
160 : 116 : return true;
161 : :
162 : 89 : 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
1179 tgl@sss.pgh.pa.us 172 : 165609 : IsTidEqualAnyClause(PlannerInfo *root, RestrictInfo *rinfo, RelOptInfo *rel)
173 : : {
174 : : ScalarArrayOpExpr *node;
175 : : Node *arg1,
176 : : *arg2;
177 : :
178 : : /* Must be a ScalarArrayOpExpr */
1932 179 [ + - + + ]: 165609 : if (!(rinfo->clause && IsA(rinfo->clause, ScalarArrayOpExpr)))
180 : 158300 : return false;
181 : 7309 : node = (ScalarArrayOpExpr *) rinfo->clause;
182 : :
183 : : /* Operator must be tideq */
6714 184 [ + + ]: 7309 : if (node->opno != TIDEqualOperator)
185 : 7294 : return false;
186 [ - + ]: 15 : if (!node->useOr)
6714 tgl@sss.pgh.pa.us 187 :UBC 0 : return false;
6714 tgl@sss.pgh.pa.us 188 [ - + ]:CBC 15 : Assert(list_length(node->args) == 2);
189 : 15 : arg1 = linitial(node->args);
190 : 15 : arg2 = lsecond(node->args);
191 : :
192 : : /* CTID must be first argument */
1932 193 [ + - + - : 30 : if (arg1 && IsA(arg1, Var) &&
+ - ]
194 : 15 : IsCTIDVar((Var *) arg1, rel))
195 : : {
196 : : /* The other argument must be a pseudoconstant */
1179 197 [ + - - + ]: 30 : if (bms_is_member(rel->relid, pull_varnos(root, arg2)) ||
1932 198 : 15 : contain_volatile_functions(arg2))
1932 tgl@sss.pgh.pa.us 199 :UBC 0 : return false;
200 : :
1932 tgl@sss.pgh.pa.us 201 :CBC 15 : return true; /* success */
202 : : }
203 : :
6714 tgl@sss.pgh.pa.us 204 :UBC 0 : return false;
205 : : }
206 : :
207 : : /*
208 : : * Check to see if a RestrictInfo is a CurrentOfExpr referencing "rel".
209 : : */
210 : : static bool
1932 tgl@sss.pgh.pa.us 211 :CBC 165594 : IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
212 : : {
213 : : CurrentOfExpr *node;
214 : :
215 : : /* Must be a CurrentOfExpr */
216 [ + - + + ]: 165594 : if (!(rinfo->clause && IsA(rinfo->clause, CurrentOfExpr)))
217 : 165398 : return false;
218 : 196 : node = (CurrentOfExpr *) rinfo->clause;
219 : :
220 : : /* If it references this rel, we're good */
221 [ + - ]: 196 : if (node->cvarno == rel->relid)
222 : 196 : return true;
223 : :
1932 tgl@sss.pgh.pa.us 224 :UBC 0 : 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 *
1179 tgl@sss.pgh.pa.us 239 :CBC 169397 : 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 : : */
1932 245 [ + + ]: 169397 : if (rinfo->pseudoconstant)
246 : 2888 : return NIL;
247 : :
248 : : /*
249 : : * If clause must wait till after some lower-security-level restriction
250 : : * clause, reject it.
251 : : */
252 [ + + ]: 166509 : if (!restriction_is_securely_promotable(rinfo, rel))
253 : 793 : return NIL;
254 : :
255 : : /*
256 : : * Check all base cases. If we get a match, return the clause.
257 : : */
258 [ + + + + ]: 331325 : if (IsTidEqualClause(rinfo, rel) ||
1179 259 [ + + ]: 331203 : IsTidEqualAnyClause(root, rinfo, rel) ||
1932 260 : 165594 : IsCurrentOfClause(rinfo, rel))
261 : 318 : return list_make1(rinfo);
262 : :
263 : 165398 : 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 *
1179 276 : 173593 : TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel)
277 : : {
6714 278 : 173593 : List *rlst = NIL;
279 : : ListCell *l;
280 : :
1932 281 [ + + + + : 343012 : foreach(l, rlist)
+ + ]
282 : : {
283 : 169737 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
284 : :
285 [ + + ]: 169737 : 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 [ + - + + : 1834 : foreach(j, ((BoolExpr *) rinfo->orclause)->args)
+ + ]
294 : : {
295 : 1822 : Node *orarg = (Node *) lfirst(j);
296 : : List *sublist;
297 : :
298 : : /* OR arguments should be ANDs or sub-RestrictInfos */
1902 299 [ + + ]: 1822 : if (is_andclause(orarg))
300 : : {
1932 301 : 352 : List *andargs = ((BoolExpr *) orarg)->args;
302 : :
303 : : /* Recurse in case there are sub-ORs */
1179 304 : 352 : sublist = TidQualFromRestrictInfoList(root, andargs, rel);
305 : : }
306 : : else
307 : : {
557 drowley@postgresql.o 308 : 1470 : RestrictInfo *ri = castNode(RestrictInfo, orarg);
309 : :
310 [ - + ]: 1470 : Assert(!restriction_is_or_clause(ri));
311 : 1470 : sublist = TidQualFromRestrictInfo(root, ri, rel);
312 : : }
313 : :
314 : : /*
315 : : * If nothing found in this arm, we can't do anything with
316 : : * this OR clause.
317 : : */
1932 tgl@sss.pgh.pa.us 318 [ + + ]: 1822 : if (sublist == NIL)
319 : : {
320 : 1798 : rlst = NIL; /* forget anything we had */
321 : 1798 : break; /* out of loop over OR args */
322 : : }
323 : :
324 : : /*
325 : : * OK, continue constructing implicitly-OR'ed result list.
326 : : */
327 : 24 : rlst = list_concat(rlst, sublist);
328 : : }
329 : : }
330 : : else
331 : : {
332 : : /* Not an OR clause, so handle base cases */
1179 333 : 167927 : 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 : : */
1932 343 [ + + ]: 169737 : if (rlst)
344 : 318 : break;
345 : : }
346 : :
8909 bruce@momjian.us 347 : 173593 : 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 *
1142 drowley@postgresql.o 359 : 173241 : TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
360 : : {
361 : 173241 : List *rlst = NIL;
362 : : ListCell *l;
363 : :
364 [ - + ]: 173241 : if ((rel->amflags & AMFLAG_HAS_TID_RANGE) == 0)
1142 drowley@postgresql.o 365 :UBC 0 : return NIL;
366 : :
1142 drowley@postgresql.o 367 [ + + + + :CBC 342201 : foreach(l, rlist)
+ + ]
368 : : {
369 : 168960 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
370 : :
371 [ + + ]: 168960 : if (IsTidRangeClause(rinfo, rel))
372 : 116 : rlst = lappend(rlst, rinfo);
373 : : }
374 : :
375 : 173241 : 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
1932 tgl@sss.pgh.pa.us 387 : 225473 : BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
388 : : {
389 : : ListCell *l;
390 : :
391 [ + + + + : 283193 : foreach(l, clauses)
+ + ]
392 : : {
393 : 57720 : 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 : : */
1931 411 [ + + ]: 57720 : if (rinfo->pseudoconstant ||
412 [ + - ]: 53496 : !restriction_is_securely_promotable(rinfo, rel) ||
413 [ + + ]: 53496 : !IsTidEqualClause(rinfo, rel))
2643 414 : 57648 : 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 : : */
1932 421 [ + + ]: 78 : if (!join_clause_is_movable_to(rinfo, rel))
422 : 6 : continue;
423 : :
424 : : /* OK, make list of clauses for this path */
425 : 72 : tidquals = list_make1(rinfo);
426 : :
427 : : /* Compute required outer rels for this path */
428 : 72 : required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
429 : 72 : required_outer = bms_del_member(required_outer, rel->relid);
430 : :
431 : 72 : add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
432 : : required_outer));
433 : : }
434 : 225473 : }
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
442 : 47118 : ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel,
443 : : EquivalenceClass *ec, EquivalenceMember *em,
444 : : void *arg)
445 : : {
446 [ + - + + : 92561 : if (em->em_expr && IsA(em->em_expr, Var) &&
+ + ]
447 : 45443 : IsCTIDVar((Var *) em->em_expr, rel))
448 : 66 : return true;
449 : 47052 : 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
6888 459 : 173241 : 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 : : */
1179 468 : 173241 : tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
469 : :
1142 drowley@postgresql.o 470 [ + + ]: 173241 : 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 : : */
1932 tgl@sss.pgh.pa.us 476 : 306 : Relids required_outer = rel->lateral_relids;
477 : :
4249 478 : 306 : 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 : : */
1142 drowley@postgresql.o 486 : 173241 : tidrangequals = TidRangeQualFromRestrictInfoList(rel->baserestrictinfo,
487 : : rel);
488 : :
489 [ + + ]: 173241 : 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 : 101 : Relids required_outer = rel->lateral_relids;
496 : :
497 : 101 : 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 : : */
1932 tgl@sss.pgh.pa.us 507 [ + + ]: 173241 : if (rel->has_eclass_joins)
508 : : {
509 : : List *clauses;
510 : :
511 : : /* Generate clauses, skipping any that join to lateral_referencers */
512 : 52232 : 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 : 52232 : 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 : 173241 : BuildParameterizedTidPaths(root, rel, rel->joininfo);
8909 bruce@momjian.us 528 : 173241 : }
|
