1/*-------------------------------------------------------------------------
2 *
3 * tidpath.c
4 * Routines to determine which TID conditions are usable for scanning
5 * a given relation, and create TidPaths accordingly.
6 *
7 * What we are looking for here is 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 *
27 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
28 * Portions Copyright (c) 1994, Regents of the University of California
29 *
30 *
31 * IDENTIFICATION
32 * src/backend/optimizer/path/tidpath.c
33 *
34 *-------------------------------------------------------------------------
35 */
36#include "postgres.h"
37
38#include "access/sysattr.h"
39#include "catalog/pg_operator.h"
40#include "catalog/pg_type.h"
41#include "nodes/nodeFuncs.h"
42#include "optimizer/clauses.h"
43#include "optimizer/optimizer.h"
44#include "optimizer/pathnode.h"
45#include "optimizer/paths.h"
46#include "optimizer/restrictinfo.h"
47
48
49/*
50 * Does this Var represent the CTID column of the specified baserel?
51 */
52static inline bool
53IsCTIDVar(Var *var, RelOptInfo *rel)
54{
55 /* The vartype check is strictly paranoia */
56 if (var->varattno == SelfItemPointerAttributeNumber &&
57 var->vartype == TIDOID &&
58 var->varno == rel->relid &&
59 var->varlevelsup == 0)
60 return true;
61 return false;
62}
63
64/*
65 * Check to see if a RestrictInfo is of the form
66 * CTID = pseudoconstant
67 * or
68 * pseudoconstant = CTID
69 * where the CTID Var belongs to relation "rel", and nothing on the
70 * other side of the clause does.
71 */
72static bool
73IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
74{
75 OpExpr *node;
76 Node *arg1,
77 *arg2,
78 *other;
79 Relids other_relids;
80
81 /* Must be an OpExpr */
82 if (!is_opclause(rinfo->clause))
83 return false;
84 node = (OpExpr *) rinfo->clause;
85
86 /* Operator must be tideq */
87 if (node->opno != TIDEqualOperator)
88 return false;
89 Assert(list_length(node->args) == 2);
90 arg1 = linitial(node->args);
91 arg2 = lsecond(node->args);
92
93 /* Look for CTID as either argument */
94 other = NULL;
95 other_relids = NULL;
96 if (arg1 && IsA(arg1, Var) &&
97 IsCTIDVar((Var *) arg1, rel))
98 {
99 other = arg2;
100 other_relids = rinfo->right_relids;
101 }
102 if (!other && arg2 && IsA(arg2, Var) &&
103 IsCTIDVar((Var *) arg2, rel))
104 {
105 other = arg1;
106 other_relids = rinfo->left_relids;
107 }
108 if (!other)
109 return false;
110
111 /* The other argument must be a pseudoconstant */
112 if (bms_is_member(rel->relid, other_relids) ||
113 contain_volatile_functions(other))
114 return false;
115
116 return true; /* success */
117}
118
119/*
120 * Check to see if a RestrictInfo is of the form
121 * CTID = ANY (pseudoconstant_array)
122 * where the CTID Var belongs to relation "rel", and nothing on the
123 * other side of the clause does.
124 */
125static bool
126IsTidEqualAnyClause(RestrictInfo *rinfo, RelOptInfo *rel)
127{
128 ScalarArrayOpExpr *node;
129 Node *arg1,
130 *arg2;
131
132 /* Must be a ScalarArrayOpExpr */
133 if (!(rinfo->clause && IsA(rinfo->clause, ScalarArrayOpExpr)))
134 return false;
135 node = (ScalarArrayOpExpr *) rinfo->clause;
136
137 /* Operator must be tideq */
138 if (node->opno != TIDEqualOperator)
139 return false;
140 if (!node->useOr)
141 return false;
142 Assert(list_length(node->args) == 2);
143 arg1 = linitial(node->args);
144 arg2 = lsecond(node->args);
145
146 /* CTID must be first argument */
147 if (arg1 && IsA(arg1, Var) &&
148 IsCTIDVar((Var *) arg1, rel))
149 {
150 /* The other argument must be a pseudoconstant */
151 if (bms_is_member(rel->relid, pull_varnos(arg2)) ||
152 contain_volatile_functions(arg2))
153 return false;
154
155 return true; /* success */
156 }
157
158 return false;
159}
160
161/*
162 * Check to see if a RestrictInfo is a CurrentOfExpr referencing "rel".
163 */
164static bool
165IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
166{
167 CurrentOfExpr *node;
168
169 /* Must be a CurrentOfExpr */
170 if (!(rinfo->clause && IsA(rinfo->clause, CurrentOfExpr)))
171 return false;
172 node = (CurrentOfExpr *) rinfo->clause;
173
174 /* If it references this rel, we're good */
175 if (node->cvarno == rel->relid)
176 return true;
177
178 return false;
179}
180
181/*
182 * Extract a set of CTID conditions from the given RestrictInfo
183 *
184 * Returns a List of CTID qual RestrictInfos for the specified rel (with
185 * implicit OR semantics across the list), or NIL if there are no usable
186 * conditions.
187 *
188 * This function considers only base cases; AND/OR combination is handled
189 * below. Therefore the returned List never has more than one element.
190 * (Using a List may seem a bit weird, but it simplifies the caller.)
191 */
192static List *
193TidQualFromRestrictInfo(RestrictInfo *rinfo, RelOptInfo *rel)
194{
195 /*
196 * We may ignore pseudoconstant clauses (they can't contain Vars, so could
197 * not match anyway).
198 */
199 if (rinfo->pseudoconstant)
200 return NIL;
201
202 /*
203 * If clause must wait till after some lower-security-level restriction
204 * clause, reject it.
205 */
206 if (!restriction_is_securely_promotable(rinfo, rel))
207 return NIL;
208
209 /*
210 * Check all base cases. If we get a match, return the clause.
211 */
212 if (IsTidEqualClause(rinfo, rel) ||
213 IsTidEqualAnyClause(rinfo, rel) ||
214 IsCurrentOfClause(rinfo, rel))
215 return list_make1(rinfo);
216
217 return NIL;
218}
219
220/*
221 * Extract a set of CTID conditions from implicit-AND List of RestrictInfos
222 *
223 * Returns a List of CTID qual RestrictInfos for the specified rel (with
224 * implicit OR semantics across the list), or NIL if there are no usable
225 * conditions.
226 *
227 * This function is just concerned with handling AND/OR recursion.
228 */
229static List *
230TidQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
231{
232 List *rlst = NIL;
233 ListCell *l;
234
235 foreach(l, rlist)
236 {
237 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
238
239 if (restriction_is_or_clause(rinfo))
240 {
241 ListCell *j;
242
243 /*
244 * We must be able to extract a CTID condition from every
245 * sub-clause of an OR, or we can't use it.
246 */
247 foreach(j, ((BoolExpr *) rinfo->orclause)->args)
248 {
249 Node *orarg = (Node *) lfirst(j);
250 List *sublist;
251
252 /* OR arguments should be ANDs or sub-RestrictInfos */
253 if (is_andclause(orarg))
254 {
255 List *andargs = ((BoolExpr *) orarg)->args;
256
257 /* Recurse in case there are sub-ORs */
258 sublist = TidQualFromRestrictInfoList(andargs, rel);
259 }
260 else
261 {
262 RestrictInfo *rinfo = castNode(RestrictInfo, orarg);
263
264 Assert(!restriction_is_or_clause(rinfo));
265 sublist = TidQualFromRestrictInfo(rinfo, rel);
266 }
267
268 /*
269 * If nothing found in this arm, we can't do anything with
270 * this OR clause.
271 */
272 if (sublist == NIL)
273 {
274 rlst = NIL; /* forget anything we had */
275 break; /* out of loop over OR args */
276 }
277
278 /*
279 * OK, continue constructing implicitly-OR'ed result list.
280 */
281 rlst = list_concat(rlst, sublist);
282 }
283 }
284 else
285 {
286 /* Not an OR clause, so handle base cases */
287 rlst = TidQualFromRestrictInfo(rinfo, rel);
288 }
289
290 /*
291 * Stop as soon as we find any usable CTID condition. In theory we
292 * could get CTID equality conditions from different AND'ed clauses,
293 * in which case we could try to pick the most efficient one. In
294 * practice, such usage seems very unlikely, so we don't bother; we
295 * just exit as soon as we find the first candidate.
296 */
297 if (rlst)
298 break;
299 }
300
301 return rlst;
302}
303
304/*
305 * Given a list of join clauses involving our rel, create a parameterized
306 * TidPath for each one that is a suitable TidEqual clause.
307 *
308 * In principle we could combine clauses that reference the same outer rels,
309 * but it doesn't seem like such cases would arise often enough to be worth
310 * troubling over.
311 */
312static void
313BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
314{
315 ListCell *l;
316
317 foreach(l, clauses)
318 {
319 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
320 List *tidquals;
321 Relids required_outer;
322
323 /*
324 * Validate whether each clause is actually usable; we must check this
325 * even when examining clauses generated from an EquivalenceClass,
326 * since they might not satisfy the restriction on not having Vars of
327 * our rel on the other side, or somebody might've built an operator
328 * class that accepts type "tid" but has other operators in it.
329 *
330 * We currently consider only TidEqual join clauses. In principle we
331 * might find a suitable ScalarArrayOpExpr in the rel's joininfo list,
332 * but it seems unlikely to be worth expending the cycles to check.
333 * And we definitely won't find a CurrentOfExpr here. Hence, we don't
334 * use TidQualFromRestrictInfo; but this must match that function
335 * otherwise.
336 */
337 if (rinfo->pseudoconstant ||
338 !restriction_is_securely_promotable(rinfo, rel) ||
339 !IsTidEqualClause(rinfo, rel))
340 continue;
341
342 /*
343 * Check if clause can be moved to this rel; this is probably
344 * redundant when considering EC-derived clauses, but we must check it
345 * for "loose" join clauses.
346 */
347 if (!join_clause_is_movable_to(rinfo, rel))
348 continue;
349
350 /* OK, make list of clauses for this path */
351 tidquals = list_make1(rinfo);
352
353 /* Compute required outer rels for this path */
354 required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
355 required_outer = bms_del_member(required_outer, rel->relid);
356
357 add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
358 required_outer));
359 }
360}
361
362/*
363 * Test whether an EquivalenceClass member matches our rel's CTID Var.
364 *
365 * This is a callback for use by generate_implied_equalities_for_column.
366 */
367static bool
368ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel,
369 EquivalenceClass *ec, EquivalenceMember *em,
370 void *arg)
371{
372 if (em->em_expr && IsA(em->em_expr, Var) &&
373 IsCTIDVar((Var *) em->em_expr, rel))
374 return true;
375 return false;
376}
377
378/*
379 * create_tidscan_paths
380 * Create paths corresponding to direct TID scans of the given rel.
381 *
382 * Candidate paths are added to the rel's pathlist (using add_path).
383 */
384void
385create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
386{
387 List *tidquals;
388
389 /*
390 * If any suitable quals exist in the rel's baserestrict list, generate a
391 * plain (unparameterized) TidPath with them.
392 */
393 tidquals = TidQualFromRestrictInfoList(rel->baserestrictinfo, rel);
394
395 if (tidquals)
396 {
397 /*
398 * This path uses no join clauses, but it could still have required
399 * parameterization due to LATERAL refs in its tlist.
400 */
401 Relids required_outer = rel->lateral_relids;
402
403 add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
404 required_outer));
405 }
406
407 /*
408 * Try to generate parameterized TidPaths using equality clauses extracted
409 * from EquivalenceClasses. (This is important since simple "t1.ctid =
410 * t2.ctid" clauses will turn into ECs.)
411 */
412 if (rel->has_eclass_joins)
413 {
414 List *clauses;
415
416 /* Generate clauses, skipping any that join to lateral_referencers */
417 clauses = generate_implied_equalities_for_column(root,
418 rel,
419 ec_member_matches_ctid,
420 NULL,
421 rel->lateral_referencers);
422
423 /* Generate a path for each usable join clause */
424 BuildParameterizedTidPaths(root, rel, clauses);
425 }
426
427 /*
428 * Also consider parameterized TidPaths using "loose" join quals. Quals
429 * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
430 * join quals, for example.
431 */
432 BuildParameterizedTidPaths(root, rel, rel->joininfo);
433}
434