Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pgpa_walker.c
4 : : * Plan tree iteration
5 : : *
6 : : * Copyright (c) 2016-2025, PostgreSQL Global Development Group
7 : : *
8 : : * contrib/pg_plan_advice/pgpa_walker.c
9 : : *
10 : : *-------------------------------------------------------------------------
11 : : */
12 : : #include "postgres.h"
13 : :
14 : : #include "pgpa_join.h"
15 : : #include "pgpa_scan.h"
16 : : #include "pgpa_walker.h"
17 : :
18 : : #include "nodes/plannodes.h"
19 : : #include "parser/parsetree.h"
20 : : #include "utils/lsyscache.h"
21 : :
22 : : static void pgpa_walk_recursively(pgpa_plan_walker_context *walker, Plan *plan,
23 : : bool within_join_problem,
24 : : pgpa_join_unroller *join_unroller,
25 : : List *active_query_features,
26 : : bool beneath_any_gather);
27 : : static Bitmapset *pgpa_process_unrolled_join(pgpa_plan_walker_context *walker,
28 : : pgpa_unrolled_join *ujoin);
29 : :
30 : : static pgpa_query_feature *pgpa_add_feature(pgpa_plan_walker_context *walker,
31 : : pgpa_qf_type type,
32 : : Plan *plan);
33 : :
34 : : static void pgpa_qf_add_rti(List *active_query_features, Index rti);
35 : : static void pgpa_qf_add_rtis(List *active_query_features, Bitmapset *relids);
36 : : static void pgpa_qf_add_plan_rtis(List *active_query_features, Plan *plan,
37 : : List *rtable);
38 : :
39 : : static bool pgpa_walker_join_order_matches(pgpa_unrolled_join *ujoin,
40 : : Index rtable_length,
41 : : pgpa_identifier *rt_identifiers,
42 : : pgpa_advice_target *target,
43 : : bool toplevel);
44 : : static bool pgpa_walker_join_order_matches_member(pgpa_join_member *member,
45 : : Index rtable_length,
46 : : pgpa_identifier *rt_identifiers,
47 : : pgpa_advice_target *target);
48 : : static pgpa_scan *pgpa_walker_find_scan(pgpa_plan_walker_context *walker,
49 : : pgpa_scan_strategy strategy,
50 : : Bitmapset *relids);
51 : : static bool pgpa_walker_index_target_matches_plan(pgpa_index_target *itarget,
52 : : Plan *plan);
53 : : static bool pgpa_walker_contains_feature(pgpa_plan_walker_context *walker,
54 : : pgpa_qf_type type,
55 : : Bitmapset *relids);
56 : : static bool pgpa_walker_contains_join(pgpa_plan_walker_context *walker,
57 : : pgpa_join_strategy strategy,
58 : : Bitmapset *relids);
59 : : static bool pgpa_walker_contains_no_gather(pgpa_plan_walker_context *walker,
60 : : Bitmapset *relids);
61 : :
62 : : /*
63 : : * Top-level entrypoint for the plan tree walk.
64 : : *
65 : : * Populates walker based on a traversal of the Plan trees in pstmt.
66 : : *
67 : : * sj_unique_rels is a list of pgpa_sj_unique_rel objects, one for each
68 : : * relation we considered making unique as part of semijoin planning.
69 : : */
70 : : void
71 : 43527 : pgpa_plan_walker(pgpa_plan_walker_context *walker, PlannedStmt *pstmt,
72 : : List *sj_unique_rels)
73 : : {
74 : 43527 : ListCell *lc;
75 : 43527 : List *sj_unique_rtis = NULL;
76 : 43527 : List *sj_nonunique_qfs = NULL;
77 : :
78 : : /* Initialization. */
79 : 43527 : memset(walker, 0, sizeof(pgpa_plan_walker_context));
80 : 43527 : walker->pstmt = pstmt;
81 : :
82 : : /* Walk the main plan tree. */
83 : 43527 : pgpa_walk_recursively(walker, pstmt->planTree, 0, NULL, NIL, false);
84 : :
85 : : /* Main plan tree walk won't reach subplans, so walk those. */
86 [ + + + + : 47897 : foreach(lc, pstmt->subplans)
+ + ]
87 : : {
88 : 4370 : Plan *plan = lfirst(lc);
89 : :
90 [ + + ]: 4370 : if (plan != NULL)
91 : 4177 : pgpa_walk_recursively(walker, plan, 0, NULL, NIL, false);
92 : 4370 : }
93 : :
94 : : /* Adjust RTIs from sj_unique_rels for the flattened range table. */
95 [ + + + + : 87776 : foreach_ptr(pgpa_sj_unique_rel, ur, sj_unique_rels)
+ + + + ]
96 : : {
97 : 722 : int rtindex = -1;
98 : 722 : int rtoffset = 0;
99 : 722 : bool dummy = false;
100 : 722 : Bitmapset *relids = NULL;
101 : :
102 : : /* If this is a subplan, find the range table offset. */
103 [ + + ]: 722 : if (ur->plan_name != NULL)
104 : : {
105 [ + + + - : 18 : foreach_node(SubPlanRTInfo, rtinfo, pstmt->subrtinfos)
- + + - ]
106 : : {
107 [ + - ]: 6 : if (strcmp(ur->plan_name, rtinfo->plan_name) == 0)
108 : : {
109 : 6 : rtoffset = rtinfo->rtoffset;
110 : 6 : dummy = rtinfo->dummy;
111 : 6 : break;
112 : : }
113 : 6 : }
114 : :
115 [ + - ]: 6 : if (rtoffset == 0)
116 [ # # # # ]: 0 : elog(ERROR, "no rtoffset for plan %s", ur->plan_name);
117 : 6 : }
118 : :
119 : : /* If this entry pertains to a dummy subquery, ignore it. */
120 [ - + ]: 722 : if (dummy)
121 : 0 : continue;
122 : :
123 : : /* Offset each entry from the original set. */
124 [ + + ]: 1486 : while ((rtindex = bms_next_member(ur->relids, rtindex)) >= 0)
125 : 764 : relids = bms_add_member(relids, rtindex + rtoffset);
126 : :
127 : : /* Store the resulting set. */
128 : 722 : sj_unique_rtis = lappend(sj_unique_rtis, relids);
129 [ - - + ]: 44249 : }
130 : :
131 : : /*
132 : : * Remove any non-unique semjoin query features for which making the rel
133 : : * unique wasn't considered.
134 : : */
135 [ + + + + : 87698 : foreach_ptr(pgpa_query_feature, qf,
+ + + + ]
136 : : walker->query_features[PGPAQF_SEMIJOIN_NON_UNIQUE])
137 : : {
138 [ + + ]: 644 : if (list_member(sj_unique_rtis, qf->relids))
139 : 617 : sj_nonunique_qfs = lappend(sj_nonunique_qfs, qf);
140 : 44171 : }
141 : 43527 : walker->query_features[PGPAQF_SEMIJOIN_NON_UNIQUE] = sj_nonunique_qfs;
142 : :
143 : : /*
144 : : * If we find any cases where analysis of the Plan tree shows that the
145 : : * semijoin was made unique but this possibility was never observed to be
146 : : * considered during planning, then we have a bug somewhere.
147 : : */
148 [ + + + + : 87135 : foreach_ptr(pgpa_query_feature, qf,
+ + + + ]
149 : : walker->query_features[PGPAQF_SEMIJOIN_UNIQUE])
150 : : {
151 [ + - ]: 81 : if (!list_member(sj_unique_rtis, qf->relids))
152 : : {
153 : 0 : StringInfoData buf;
154 : :
155 : 0 : initStringInfo(&buf);
156 : 0 : outBitmapset(&buf, qf->relids);
157 [ # # # # ]: 0 : elog(ERROR,
158 : : "unique semijoin found for relids %s but not observed during planning",
159 : : buf.data);
160 : 0 : }
161 : 43608 : }
162 : 43527 : }
163 : :
164 : : /*
165 : : * Main workhorse for the plan tree walk.
166 : : *
167 : : * If within_join_problem is true, we encountered a join at some higher level
168 : : * of the tree walk and haven't yet descended out of the portion of the plan
169 : : * tree that is part of that same join problem. We're no longer in the same
170 : : * join problem if (1) we cross into a different subquery or (2) we descend
171 : : * through an Append or MergeAppend node, below which any further joins would
172 : : * be partitionwise joins planned separately from the outer join problem.
173 : : *
174 : : * If join_unroller != NULL, the join unroller code expects us to find a join
175 : : * that should be unrolled into that object. This implies that we're within a
176 : : * join problem, but the reverse is not true: when we've traversed all the
177 : : * joins but are still looking for the scan that is the leaf of the join tree,
178 : : * join_unroller will be NULL but within_join_problem will be true.
179 : : *
180 : : * Each element of active_query_features corresponds to some item of advice
181 : : * that needs to enumerate all the relations it affects. We add RTIs we find
182 : : * during tree traversal to each of these query features.
183 : : *
184 : : * If beneath_any_gather == true, some higher level of the tree traversal found
185 : : * a Gather or Gather Merge node.
186 : : */
187 : : static void
188 : 118039 : pgpa_walk_recursively(pgpa_plan_walker_context *walker, Plan *plan,
189 : : bool within_join_problem,
190 : : pgpa_join_unroller *join_unroller,
191 : : List *active_query_features,
192 : : bool beneath_any_gather)
193 : : {
194 : 118039 : pgpa_join_unroller *outer_join_unroller = NULL;
195 : 118039 : pgpa_join_unroller *inner_join_unroller = NULL;
196 : 118039 : bool join_unroller_toplevel = false;
197 : 118039 : List *pushdown_query_features = NIL;
198 : 118039 : ListCell *lc;
199 : 118039 : List *extraplans = NIL;
200 : 118039 : List *elided_nodes = NIL;
201 : :
202 [ + + + - ]: 118039 : Assert(within_join_problem || join_unroller == NULL);
203 : :
204 : : /*
205 : : * If this is a Gather or Gather Merge node, directly add it to the list
206 : : * of currently-active query features.
207 : : *
208 : : * Otherwise, check the future_query_features list to see whether this was
209 : : * previously identified as a plan node that needs to be treated as a
210 : : * query feature.
211 : : *
212 : : * Note that the caller also has a copy to active_query_features, so we
213 : : * can't destructively modify it without making a copy.
214 : : */
215 [ + + ]: 118039 : if (IsA(plan, Gather))
216 : : {
217 : 193 : active_query_features =
218 : 386 : lappend(list_copy(active_query_features),
219 : 193 : pgpa_add_feature(walker, PGPAQF_GATHER, plan));
220 : 193 : beneath_any_gather = true;
221 : 193 : }
222 [ + + ]: 117846 : else if (IsA(plan, GatherMerge))
223 : : {
224 : 67 : active_query_features =
225 : 134 : lappend(list_copy(active_query_features),
226 : 67 : pgpa_add_feature(walker, PGPAQF_GATHER_MERGE, plan));
227 : 67 : beneath_any_gather = true;
228 : 67 : }
229 : : else
230 : : {
231 [ + + + + : 239555 : foreach_ptr(pgpa_query_feature, qf, walker->future_query_features)
+ + + + ]
232 : : {
233 [ + + ]: 3997 : if (qf->plan == plan)
234 : : {
235 : 725 : active_query_features = list_copy(active_query_features);
236 : 725 : active_query_features = lappend(active_query_features, qf);
237 : 725 : walker->future_query_features =
238 : 725 : list_delete_ptr(walker->future_query_features, plan);
239 : 725 : break;
240 : : }
241 : 121051 : }
242 : : }
243 : :
244 : : /*
245 : : * Find all elided nodes for this Plan node.
246 : : */
247 [ + + + + : 260124 : foreach_node(ElidedNode, n, walker->pstmt->elidedNodes)
+ + + + ]
248 : : {
249 [ + + ]: 24046 : if (n->plan_node_id == plan->plan_node_id)
250 : 2645 : elided_nodes = lappend(elided_nodes, n);
251 : 142085 : }
252 : :
253 : : /* If we found any elided_nodes, handle them. */
254 [ + + ]: 118039 : if (elided_nodes != NIL)
255 : : {
256 : 2628 : int num_elided_nodes = list_length(elided_nodes);
257 : 2628 : ElidedNode *last_elided_node;
258 : :
259 : : /*
260 : : * RTIs for the final -- and thus logically uppermost -- elided node
261 : : * should be collected for query features passed down by the caller.
262 : : * However, elided nodes act as barriers to query features, which
263 : : * means that (1) the remaining elided nodes, if any, should be
264 : : * ignored for purposes of query features and (2) the list of active
265 : : * query features should be reset to empty so that we do not add RTIs
266 : : * from the plan node that is logically beneath the elided node to the
267 : : * query features passed down from the caller.
268 : : */
269 : 2628 : last_elided_node = list_nth(elided_nodes, num_elided_nodes - 1);
270 : 5256 : pgpa_qf_add_rtis(active_query_features,
271 : 5256 : pgpa_filter_out_join_relids(last_elided_node->relids,
272 : 2628 : walker->pstmt->rtable));
273 : 2628 : active_query_features = NIL;
274 : :
275 : : /*
276 : : * If we're within a join problem, the join_unroller is responsible
277 : : * for building the scan for the final elided node, so throw it out.
278 : : */
279 [ + + ]: 2628 : if (within_join_problem)
280 : 235 : elided_nodes = list_truncate(elided_nodes, num_elided_nodes - 1);
281 : :
282 : : /* Build scans for all (or the remaining) elided nodes. */
283 [ + + + + : 7666 : foreach_node(ElidedNode, elided_node, elided_nodes)
+ + + + ]
284 : : {
285 : 4820 : (void) pgpa_build_scan(walker, plan, elided_node,
286 : 2410 : beneath_any_gather, within_join_problem);
287 : 5038 : }
288 : :
289 : : /*
290 : : * If there were any elided nodes, then everything beneath those nodes
291 : : * is not part of the same join problem.
292 : : *
293 : : * In more detail, if an Append or MergeAppend was elided, then a
294 : : * partitionwise join was chosen and only a single child survived; if
295 : : * a SubqueryScan was elided, the subquery was planned without
296 : : * flattening it into the parent.
297 : : */
298 : 2628 : within_join_problem = false;
299 : 2628 : join_unroller = NULL;
300 : 2628 : }
301 : :
302 : : /*
303 : : * If we're within a join problem, the join unroller is responsible for
304 : : * building any required scan for this node. If not, we do it here.
305 : : */
306 [ + + ]: 118039 : if (!within_join_problem)
307 : 86795 : (void) pgpa_build_scan(walker, plan, NULL, beneath_any_gather, false);
308 : :
309 : : /*
310 : : * If this join needs to unrolled but there's no join unroller already
311 : : * available, create one.
312 : : */
313 [ + + + + ]: 118039 : if (join_unroller == NULL && pgpa_is_join(plan))
314 : : {
315 : 9756 : join_unroller = pgpa_create_join_unroller();
316 : 9756 : join_unroller_toplevel = true;
317 : 9756 : within_join_problem = true;
318 : 9756 : }
319 : :
320 : : /*
321 : : * If this join is to be unrolled, pgpa_unroll_join() will return the join
322 : : * unroller object that should be passed down when we recurse into the
323 : : * outer and inner sides of the plan.
324 : : */
325 [ + + ]: 118039 : if (join_unroller != NULL)
326 : 13297 : pgpa_unroll_join(walker, plan, beneath_any_gather, join_unroller,
327 : : &outer_join_unroller, &inner_join_unroller);
328 : :
329 : : /* Add RTIs from the plan node to all active query features. */
330 : 118039 : pgpa_qf_add_plan_rtis(active_query_features, plan, walker->pstmt->rtable);
331 : :
332 : : /*
333 : : * Recurse into the outer and inner subtrees.
334 : : *
335 : : * As an exception, if this is a ForeignScan, don't recurse. postgres_fdw
336 : : * sometimes stores an EPQ recheck plan in plan->leftree, but that's going
337 : : * to mention the same set of relations as the ForeignScan itself, and we
338 : : * have no way to emit advice targeting the EPQ case vs. the non-EPQ case.
339 : : * Moreover, it's not entirely clear what other FDWs might do with the
340 : : * left and right subtrees. Maybe some better handling is needed here, but
341 : : * for now, we just punt.
342 : : */
343 [ - + ]: 118039 : if (!IsA(plan, ForeignScan))
344 : : {
345 [ + + ]: 118039 : if (plan->lefttree != NULL)
346 : 96340 : pgpa_walk_recursively(walker, plan->lefttree, within_join_problem,
347 : 48170 : outer_join_unroller, active_query_features,
348 : 48170 : beneath_any_gather);
349 [ + + ]: 118039 : if (plan->righttree != NULL)
350 : 26326 : pgpa_walk_recursively(walker, plan->righttree, within_join_problem,
351 : 13163 : inner_join_unroller, active_query_features,
352 : 13163 : beneath_any_gather);
353 : 118039 : }
354 : :
355 : : /*
356 : : * If we created a join unroller up above, then it's also our join to use
357 : : * it to build the final pgpa_unrolled_join, and to destroy the object.
358 : : */
359 [ + + ]: 118039 : if (join_unroller_toplevel)
360 : : {
361 : 9756 : pgpa_unrolled_join *ujoin;
362 : :
363 : 9756 : ujoin = pgpa_build_unrolled_join(walker, join_unroller);
364 : 9756 : walker->toplevel_unrolled_joins =
365 : 9756 : lappend(walker->toplevel_unrolled_joins, ujoin);
366 : 9756 : pgpa_destroy_join_unroller(join_unroller);
367 : 9756 : (void) pgpa_process_unrolled_join(walker, ujoin);
368 : 9756 : }
369 : :
370 : : /*
371 : : * Some plan types can have additional children. Nodes like Append that
372 : : * can have any number of children store them in a List; a SubqueryScan
373 : : * just has a field for a single additional Plan.
374 : : */
375 [ + + + + : 118039 : switch (nodeTag(plan))
+ - + ]
376 : : {
377 : : case T_Append:
378 : : {
379 : 2512 : Append *aplan = (Append *) plan;
380 : :
381 : 2512 : extraplans = aplan->appendplans;
382 [ + + ]: 2512 : if (bms_is_empty(aplan->apprelids))
383 : 78 : pushdown_query_features = active_query_features;
384 : 2512 : }
385 : 2512 : break;
386 : : case T_MergeAppend:
387 : : {
388 : 91 : MergeAppend *maplan = (MergeAppend *) plan;
389 : :
390 : 91 : extraplans = maplan->mergeplans;
391 [ + + ]: 91 : if (bms_is_empty(maplan->apprelids))
392 : 12 : pushdown_query_features = active_query_features;
393 : 91 : }
394 : 91 : break;
395 : : case T_BitmapAnd:
396 : 17 : extraplans = ((BitmapAnd *) plan)->bitmapplans;
397 : 17 : break;
398 : : case T_BitmapOr:
399 : 33 : extraplans = ((BitmapOr *) plan)->bitmapplans;
400 : 33 : break;
401 : : case T_SubqueryScan:
402 : :
403 : : /*
404 : : * We don't pass down active_query_features across here, because
405 : : * those are specific to a subquery level.
406 : : */
407 : 2986 : pgpa_walk_recursively(walker, ((SubqueryScan *) plan)->subplan,
408 : 1493 : 0, NULL, NIL, beneath_any_gather);
409 : 1493 : break;
410 : : case T_CustomScan:
411 : 0 : extraplans = ((CustomScan *) plan)->custom_plans;
412 : 0 : break;
413 : : default:
414 : 113893 : break;
415 : : }
416 : :
417 : : /* If we found a list of extra children, iterate over it. */
418 [ + + + + : 125548 : foreach(lc, extraplans)
+ + ]
419 : : {
420 : 7509 : Plan *subplan = lfirst(lc);
421 : :
422 : 15018 : pgpa_walk_recursively(walker, subplan, 0, NULL, pushdown_query_features,
423 : 7509 : beneath_any_gather);
424 : 7509 : }
425 : 118039 : }
426 : :
427 : : /*
428 : : * Perform final processing of a newly-constructed pgpa_unrolled_join. This
429 : : * only needs to be called for toplevel pgpa_unrolled_join objects, since it
430 : : * recurses to sub-joins as needed.
431 : : *
432 : : * Our goal is to add the set of inner relids to the relevant join_strategies
433 : : * list, and to do the same for any sub-joins. To that end, the return value
434 : : * is the set of relids found beneath the the join, but it is expected that
435 : : * the toplevel caller will ignore this.
436 : : */
437 : : static Bitmapset *
438 : 10166 : pgpa_process_unrolled_join(pgpa_plan_walker_context *walker,
439 : : pgpa_unrolled_join *ujoin)
440 : : {
441 : 10166 : Bitmapset *all_relids = bms_copy(ujoin->outer.scan->relids);
442 : :
443 : : /* If this fails, we didn't unroll properly. */
444 [ + - ]: 10166 : Assert(ujoin->outer.unrolled_join == NULL);
445 : :
446 [ + + ]: 23146 : for (int k = 0; k < ujoin->ninner; ++k)
447 : : {
448 : 12980 : pgpa_join_member *member = &ujoin->inner[k];
449 : 12980 : Bitmapset *relids;
450 : :
451 [ + + ]: 12980 : if (member->unrolled_join != NULL)
452 : 820 : relids = pgpa_process_unrolled_join(walker,
453 : 410 : member->unrolled_join);
454 : : else
455 : : {
456 [ - + ]: 12570 : Assert(member->scan != NULL);
457 : 12570 : relids = member->scan->relids;
458 : : }
459 : 12980 : walker->join_strategies[ujoin->strategy[k]] =
460 : 12980 : lappend(walker->join_strategies[ujoin->strategy[k]], relids);
461 : 12980 : all_relids = bms_add_members(all_relids, relids);
462 : 12980 : }
463 : :
464 : 20332 : return all_relids;
465 : 10166 : }
466 : :
467 : : /*
468 : : * Arrange for the given plan node to be treated as a query feature when the
469 : : * tree walk reaches it.
470 : : *
471 : : * Make sure to only use this for nodes that the tree walk can't have reached
472 : : * yet!
473 : : */
474 : : void
475 : 725 : pgpa_add_future_feature(pgpa_plan_walker_context *walker,
476 : : pgpa_qf_type type, Plan *plan)
477 : : {
478 : 725 : pgpa_query_feature *qf = pgpa_add_feature(walker, type, plan);
479 : :
480 : 725 : walker->future_query_features =
481 : 725 : lappend(walker->future_query_features, qf);
482 : 725 : }
483 : :
484 : : /*
485 : : * Return the last of any elided nodes associated with this plan node ID.
486 : : *
487 : : * The last elided node is the one that would have been uppermost in the plan
488 : : * tree had it not been removed during setrefs processig.
489 : : */
490 : : ElidedNode *
491 : 31080 : pgpa_last_elided_node(PlannedStmt *pstmt, Plan *plan)
492 : : {
493 : 31080 : ElidedNode *elided_node = NULL;
494 : :
495 [ + + + + : 71317 : foreach_node(ElidedNode, n, pstmt->elidedNodes)
+ + + + ]
496 : : {
497 [ + + ]: 9157 : if (n->plan_node_id == plan->plan_node_id)
498 : 236 : elided_node = n;
499 : 40237 : }
500 : :
501 : 62160 : return elided_node;
502 : 31080 : }
503 : :
504 : : /*
505 : : * Certain plan nodes can refer to a set of RTIs. Extract and return the set.
506 : : */
507 : : Bitmapset *
508 : 178053 : pgpa_relids(Plan *plan)
509 : : {
510 [ + + ]: 178053 : if (IsA(plan, Result))
511 : 39392 : return ((Result *) plan)->relids;
512 [ - + ]: 138661 : else if (IsA(plan, ForeignScan))
513 : 0 : return ((ForeignScan *) plan)->fs_relids;
514 [ + + ]: 138661 : else if (IsA(plan, Append))
515 : 5024 : return ((Append *) plan)->apprelids;
516 [ + + ]: 133637 : else if (IsA(plan, MergeAppend))
517 : 182 : return ((MergeAppend *) plan)->apprelids;
518 : :
519 : 133455 : return NULL;
520 : 178053 : }
521 : :
522 : : /*
523 : : * Extract the scanned RTI from a plan node.
524 : : *
525 : : * Returns 0 if there isn't one.
526 : : */
527 : : Index
528 : 207002 : pgpa_scanrelid(Plan *plan)
529 : : {
530 [ + + ]: 207002 : switch (nodeTag(plan))
531 : : {
532 : : case T_SeqScan:
533 : : case T_SampleScan:
534 : : case T_BitmapHeapScan:
535 : : case T_TidScan:
536 : : case T_TidRangeScan:
537 : : case T_SubqueryScan:
538 : : case T_FunctionScan:
539 : : case T_TableFuncScan:
540 : : case T_ValuesScan:
541 : : case T_CteScan:
542 : : case T_NamedTuplestoreScan:
543 : : case T_WorkTableScan:
544 : : case T_ForeignScan:
545 : : case T_CustomScan:
546 : : case T_IndexScan:
547 : : case T_IndexOnlyScan:
548 : 98564 : return ((Scan *) plan)->scanrelid;
549 : : default:
550 : 108438 : return 0;
551 : : }
552 : 207002 : }
553 : :
554 : : /*
555 : : * Construct a new Bitmapset containing non-RTE_JOIN members of 'relids'.
556 : : */
557 : : Bitmapset *
558 : 46305 : pgpa_filter_out_join_relids(Bitmapset *relids, List *rtable)
559 : : {
560 : 46305 : int rti = -1;
561 : 46305 : Bitmapset *result = NULL;
562 : :
563 [ + + ]: 95798 : while ((rti = bms_next_member(relids, rti)) >= 0)
564 : : {
565 : 49493 : RangeTblEntry *rte = rt_fetch(rti, rtable);
566 : :
567 [ + + ]: 49493 : if (rte->rtekind != RTE_JOIN)
568 : 49257 : result = bms_add_member(result, rti);
569 : 49493 : }
570 : :
571 : 92610 : return result;
572 : 46305 : }
573 : :
574 : : /*
575 : : * Create a pgpa_query_feature and add it to the list of all query features
576 : : * for this plan.
577 : : */
578 : : static pgpa_query_feature *
579 : 985 : pgpa_add_feature(pgpa_plan_walker_context *walker,
580 : : pgpa_qf_type type, Plan *plan)
581 : : {
582 : 985 : pgpa_query_feature *qf = palloc0_object(pgpa_query_feature);
583 : :
584 : 985 : qf->type = type;
585 : 985 : qf->plan = plan;
586 : :
587 : 985 : walker->query_features[qf->type] =
588 : 985 : lappend(walker->query_features[qf->type], qf);
589 : :
590 : 1970 : return qf;
591 : 985 : }
592 : :
593 : : /*
594 : : * Add a single RTI to each active query feature.
595 : : */
596 : : static void
597 : 49282 : pgpa_qf_add_rti(List *active_query_features, Index rti)
598 : : {
599 [ + + + + : 99095 : foreach_ptr(pgpa_query_feature, qf, active_query_features)
+ + + + ]
600 : : {
601 : 531 : qf->relids = bms_add_member(qf->relids, rti);
602 : 49813 : }
603 : 49282 : }
604 : :
605 : : /*
606 : : * Add a set of RTIs to each active query feature.
607 : : */
608 : : static void
609 : 22961 : pgpa_qf_add_rtis(List *active_query_features, Bitmapset *relids)
610 : : {
611 [ + + + + : 46518 : foreach_ptr(pgpa_query_feature, qf, active_query_features)
+ + + + ]
612 : : {
613 : 596 : qf->relids = bms_add_members(qf->relids, relids);
614 : 23557 : }
615 : 22961 : }
616 : :
617 : : /*
618 : : * Add RTIs directly contained in a plan node to each active query feature,
619 : : * but filter out any join RTIs, since advice doesn't mention those.
620 : : */
621 : : static void
622 : 118039 : pgpa_qf_add_plan_rtis(List *active_query_features, Plan *plan, List *rtable)
623 : : {
624 : 118039 : Bitmapset *relids;
625 : 118039 : Index rti;
626 : :
627 [ + + ]: 118039 : if ((relids = pgpa_relids(plan)) != NULL)
628 : : {
629 : 20333 : relids = pgpa_filter_out_join_relids(relids, rtable);
630 : 20333 : pgpa_qf_add_rtis(active_query_features, relids);
631 : 20333 : }
632 [ + + ]: 97706 : else if ((rti = pgpa_scanrelid(plan)) != 0)
633 : 49282 : pgpa_qf_add_rti(active_query_features, rti);
634 : 118039 : }
635 : :
636 : : /*
637 : : * If we generated plan advice using the provided walker object and array
638 : : * of identifiers, would we generate the specified tag/target combination?
639 : : *
640 : : * If yes, the plan conforms to the advice; if no, it does not. Note that
641 : : * we have know way of knowing whether the planner was forced to emit a plan
642 : : * that conformed to the advice or just happened to do so.
643 : : */
644 : : bool
645 : 113 : pgpa_walker_would_advise(pgpa_plan_walker_context *walker,
646 : : pgpa_identifier *rt_identifiers,
647 : : pgpa_advice_tag_type tag,
648 : : pgpa_advice_target *target)
649 : : {
650 : 113 : Index rtable_length = list_length(walker->pstmt->rtable);
651 : 113 : Bitmapset *relids = NULL;
652 : :
653 [ + + ]: 113 : if (tag == PGPA_TAG_JOIN_ORDER)
654 : : {
655 [ + + + - : 34 : foreach_ptr(pgpa_unrolled_join, ujoin, walker->toplevel_unrolled_joins)
+ + + + +
+ + + ]
656 : : {
657 [ + + + + ]: 32 : if (pgpa_walker_join_order_matches(ujoin, rtable_length,
658 : 16 : rt_identifiers, target, true))
659 : 14 : return true;
660 : 4 : }
661 : :
662 : 2 : return false;
663 : : }
664 : :
665 [ + + ]: 97 : if (target->ttype == PGPA_TARGET_IDENTIFIER)
666 : : {
667 : 87 : Index rti;
668 : :
669 : 174 : rti = pgpa_compute_rti_from_identifier(rtable_length, rt_identifiers,
670 : 87 : &target->rid);
671 [ + - ]: 87 : if (rti == 0)
672 : 0 : return false;
673 : 87 : relids = bms_make_singleton(rti);
674 [ - + ]: 87 : }
675 : : else
676 : : {
677 [ + - ]: 10 : Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
678 [ + + + - : 40 : foreach_ptr(pgpa_advice_target, child_target, target->children)
+ + + + -
+ - + ]
679 : : {
680 : 20 : Index rti;
681 : :
682 [ + - ]: 20 : Assert(child_target->ttype == PGPA_TARGET_IDENTIFIER);
683 : 40 : rti = pgpa_compute_rti_from_identifier(rtable_length,
684 : 20 : rt_identifiers,
685 : 20 : &child_target->rid);
686 [ + - ]: 20 : if (rti == 0)
687 : 0 : return false;
688 : 20 : relids = bms_add_member(relids, rti);
689 [ - + ]: 30 : }
690 : : }
691 : :
692 [ - + + + : 97 : switch (tag)
+ + + + +
+ + + + +
+ + - + +
+ ]
693 : : {
694 : : case PGPA_TAG_JOIN_ORDER:
695 : : /* should have been handled above */
696 : 0 : pg_unreachable();
697 : : break;
698 : : case PGPA_TAG_BITMAP_HEAP_SCAN:
699 : : /* XXX currenly doesn't try to match the index specification */
700 : 9 : return pgpa_walker_find_scan(walker,
701 : : PGPA_SCAN_BITMAP_HEAP,
702 : 6 : relids) != NULL;
703 : : case PGPA_TAG_FOREIGN_JOIN:
704 : 3 : return pgpa_walker_find_scan(walker,
705 : : PGPA_SCAN_FOREIGN,
706 : 2 : relids) != NULL;
707 : : case PGPA_TAG_INDEX_ONLY_SCAN:
708 : : {
709 : 5 : pgpa_scan *scan;
710 : :
711 : 10 : scan = pgpa_walker_find_scan(walker, PGPA_SCAN_INDEX_ONLY,
712 : 5 : relids);
713 [ + + ]: 5 : if (scan == NULL)
714 : 3 : return false;
715 : :
716 : 2 : return pgpa_walker_index_target_matches_plan(target->itarget, scan->plan);
717 : 5 : }
718 : : case PGPA_TAG_INDEX_SCAN:
719 : : {
720 : 14 : pgpa_scan *scan;
721 : :
722 : 28 : scan = pgpa_walker_find_scan(walker, PGPA_SCAN_INDEX,
723 : 14 : relids);
724 [ + + ]: 14 : if (scan == NULL)
725 : 4 : return false;
726 : :
727 : 10 : return pgpa_walker_index_target_matches_plan(target->itarget, scan->plan);
728 : 14 : }
729 : : case PGPA_TAG_PARTITIONWISE:
730 : 24 : return pgpa_walker_find_scan(walker,
731 : : PGPA_SCAN_PARTITIONWISE,
732 : 16 : relids) != NULL;
733 : : case PGPA_TAG_SEQ_SCAN:
734 : 36 : return pgpa_walker_find_scan(walker,
735 : : PGPA_SCAN_SEQ,
736 : 24 : relids) != NULL;
737 : : case PGPA_TAG_TID_SCAN:
738 : 12 : return pgpa_walker_find_scan(walker,
739 : : PGPA_SCAN_TID,
740 : 8 : relids) != NULL;
741 : : case PGPA_TAG_GATHER:
742 : 14 : return pgpa_walker_contains_feature(walker,
743 : : PGPAQF_GATHER,
744 : 7 : relids);
745 : : case PGPA_TAG_GATHER_MERGE:
746 : 12 : return pgpa_walker_contains_feature(walker,
747 : : PGPAQF_GATHER_MERGE,
748 : 6 : relids);
749 : : case PGPA_TAG_SEMIJOIN_NON_UNIQUE:
750 : 12 : return pgpa_walker_contains_feature(walker,
751 : : PGPAQF_SEMIJOIN_NON_UNIQUE,
752 : 6 : relids);
753 : : case PGPA_TAG_SEMIJOIN_UNIQUE:
754 : 14 : return pgpa_walker_contains_feature(walker,
755 : : PGPAQF_SEMIJOIN_UNIQUE,
756 : 7 : relids);
757 : : case PGPA_TAG_HASH_JOIN:
758 : 6 : return pgpa_walker_contains_join(walker,
759 : : JSTRAT_HASH_JOIN,
760 : 3 : relids);
761 : : case PGPA_TAG_MERGE_JOIN_MATERIALIZE:
762 : 4 : return pgpa_walker_contains_join(walker,
763 : : JSTRAT_MERGE_JOIN_MATERIALIZE,
764 : 2 : relids);
765 : : case PGPA_TAG_MERGE_JOIN_PLAIN:
766 : 4 : return pgpa_walker_contains_join(walker,
767 : : JSTRAT_MERGE_JOIN_PLAIN,
768 : 2 : relids);
769 : : case PGPA_TAG_NESTED_LOOP_MATERIALIZE:
770 : 6 : return pgpa_walker_contains_join(walker,
771 : : JSTRAT_NESTED_LOOP_MATERIALIZE,
772 : 3 : relids);
773 : : case PGPA_TAG_NESTED_LOOP_MEMOIZE:
774 : 4 : return pgpa_walker_contains_join(walker,
775 : : JSTRAT_NESTED_LOOP_MEMOIZE,
776 : 2 : relids);
777 : : case PGPA_TAG_NESTED_LOOP_PLAIN:
778 : 10 : return pgpa_walker_contains_join(walker,
779 : : JSTRAT_NESTED_LOOP_PLAIN,
780 : 5 : relids);
781 : : case PGPA_TAG_NO_GATHER:
782 : 7 : return pgpa_walker_contains_no_gather(walker, relids);
783 : : }
784 : :
785 : : /* should not get here */
786 : 0 : return false;
787 : 113 : }
788 : :
789 : : /*
790 : : * Does the index target match the Plan?
791 : : *
792 : : * Should only be called when we know that itarget mandates an Index Scan or
793 : : * Index Only Scan and this corresponds to the type of Plan. Here, our job is
794 : : * just to check whether it's the same index.
795 : : */
796 : : static bool
797 : 12 : pgpa_walker_index_target_matches_plan(pgpa_index_target *itarget, Plan *plan)
798 : : {
799 : 12 : Oid indexoid = InvalidOid;
800 : :
801 : : /* Retrieve the index OID from the plan. */
802 [ + + ]: 12 : if (IsA(plan, IndexScan))
803 : 10 : indexoid = ((IndexScan *) plan)->indexid;
804 [ + - ]: 2 : else if (IsA(plan, IndexOnlyScan))
805 : 2 : indexoid = ((IndexOnlyScan *) plan)->indexid;
806 : : else
807 [ # # # # ]: 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(plan));
808 : :
809 : : /* Shouldn't be called in any other case. */
810 [ + - ]: 12 : Assert(itarget->itype == PGPA_INDEX_NAME);
811 : :
812 : : /* Check whether schema name matches, if specified in index target. */
813 [ + + ]: 12 : if (itarget->indnamespace != NULL)
814 : : {
815 : 4 : Oid nspoid = get_rel_namespace(indexoid);
816 : 4 : char *relnamespace = get_namespace_name_or_temp(nspoid);
817 : :
818 [ + + ]: 4 : if (strcmp(itarget->indnamespace, relnamespace) != 0)
819 : 1 : return false;
820 [ + + ]: 4 : }
821 : :
822 : : /* Check whether relation name matches. */
823 : 11 : return (strcmp(itarget->indname, get_rel_name(indexoid)) == 0);
824 : 12 : }
825 : :
826 : : /*
827 : : * Does an unrolled join match the join order specified by an advice target?
828 : : */
829 : : static bool
830 : 17 : pgpa_walker_join_order_matches(pgpa_unrolled_join *ujoin,
831 : : Index rtable_length,
832 : : pgpa_identifier *rt_identifiers,
833 : : pgpa_advice_target *target,
834 : : bool toplevel)
835 : : {
836 : 17 : int nchildren = list_length(target->children);
837 : :
838 [ + - ]: 17 : Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
839 : :
840 : : /* At toplevel, we allow a prefix match. */
841 [ + + ]: 17 : if (toplevel)
842 : : {
843 [ - + ]: 16 : if (nchildren > ujoin->ninner + 1)
844 : 0 : return false;
845 : 16 : }
846 : : else
847 : : {
848 [ - + ]: 1 : if (nchildren != ujoin->ninner + 1)
849 : 0 : return false;
850 : : }
851 : :
852 : : /* Outermost rel must match. */
853 [ + + + + ]: 34 : if (!pgpa_walker_join_order_matches_member(&ujoin->outer,
854 : 17 : rtable_length,
855 : 17 : rt_identifiers,
856 : 17 : linitial(target->children)))
857 : 1 : return false;
858 : :
859 : : /* Each inner rel must match. */
860 [ + + + + ]: 34 : for (int n = 0; n < nchildren - 1; ++n)
861 : : {
862 : 18 : pgpa_advice_target *child_target = list_nth(target->children, n + 1);
863 : :
864 [ + + + + ]: 36 : if (!pgpa_walker_join_order_matches_member(&ujoin->inner[n],
865 : 18 : rtable_length,
866 : 18 : rt_identifiers,
867 : 18 : child_target))
868 : 1 : return false;
869 [ + + ]: 18 : }
870 : :
871 : 15 : return true;
872 : 17 : }
873 : :
874 : : /*
875 : : * Does one member of an unrolled join match an advice target?
876 : : */
877 : : static bool
878 : 35 : pgpa_walker_join_order_matches_member(pgpa_join_member *member,
879 : : Index rtable_length,
880 : : pgpa_identifier *rt_identifiers,
881 : : pgpa_advice_target *target)
882 : : {
883 : 35 : Bitmapset *relids = NULL;
884 : :
885 [ + + ]: 35 : if (member->unrolled_join != NULL)
886 : : {
887 [ + + ]: 2 : if (target->ttype != PGPA_TARGET_ORDERED_LIST)
888 : 1 : return false;
889 : 2 : return pgpa_walker_join_order_matches(member->unrolled_join,
890 : 1 : rtable_length,
891 : 1 : rt_identifiers,
892 : 1 : target,
893 : : false);
894 : : }
895 : :
896 [ + - ]: 33 : Assert(member->scan != NULL);
897 [ - - - + ]: 33 : switch (target->ttype)
898 : : {
899 : : case PGPA_TARGET_ORDERED_LIST:
900 : : /* Could only match an unrolled join */
901 : 0 : return false;
902 : :
903 : : case PGPA_TARGET_UNORDERED_LIST:
904 : : {
905 [ # # # # : 0 : foreach_ptr(pgpa_advice_target, child_target, target->children)
# # # # #
# # # ]
906 : : {
907 : 0 : Index rti;
908 : :
909 : 0 : rti = pgpa_compute_rti_from_identifier(rtable_length,
910 : 0 : rt_identifiers,
911 : 0 : &child_target->rid);
912 [ # # ]: 0 : if (rti == 0)
913 : 0 : return false;
914 : 0 : relids = bms_add_member(relids, rti);
915 [ # # ]: 0 : }
916 : 0 : break;
917 : : }
918 : :
919 : : case PGPA_TARGET_IDENTIFIER:
920 : : {
921 : 33 : Index rti;
922 : :
923 : 66 : rti = pgpa_compute_rti_from_identifier(rtable_length,
924 : 33 : rt_identifiers,
925 : 33 : &target->rid);
926 [ + - ]: 33 : if (rti == 0)
927 : 0 : return false;
928 : 33 : relids = bms_make_singleton(rti);
929 : 33 : break;
930 [ - + ]: 33 : }
931 : : }
932 : :
933 : 33 : return bms_equal(member->scan->relids, relids);
934 : 35 : }
935 : :
936 : : /*
937 : : * Find the scan where the walker says that the given scan strategy should be
938 : : * used for the given relid set, if one exists.
939 : : *
940 : : * Returns the pgpa_scan object, or NULL if none was found.
941 : : */
942 : : static pgpa_scan *
943 : 47 : pgpa_walker_find_scan(pgpa_plan_walker_context *walker,
944 : : pgpa_scan_strategy strategy,
945 : : Bitmapset *relids)
946 : : {
947 : 47 : List *scans = walker->scans[strategy];
948 : :
949 [ + + + + : 103 : foreach_ptr(pgpa_scan, scan, scans)
+ + + + +
+ + + ]
950 : : {
951 [ + + ]: 42 : if (bms_equal(scan->relids, relids))
952 : 33 : return scan;
953 : 23 : }
954 : :
955 : 14 : return NULL;
956 : 47 : }
957 : :
958 : : /*
959 : : * Does this walker say that the given query feature applies to the given
960 : : * relid set?
961 : : */
962 : : static bool
963 : 26 : pgpa_walker_contains_feature(pgpa_plan_walker_context *walker,
964 : : pgpa_qf_type type,
965 : : Bitmapset *relids)
966 : : {
967 : 26 : List *query_features = walker->query_features[type];
968 : :
969 [ + + + + : 55 : foreach_ptr(pgpa_query_feature, qf, query_features)
+ + + + +
+ + + ]
970 : : {
971 [ + + ]: 23 : if (bms_equal(qf->relids, relids))
972 : 20 : return true;
973 : 9 : }
974 : :
975 : 6 : return false;
976 : 26 : }
977 : :
978 : : /*
979 : : * Does the walker say that the given join strategy should be used for the
980 : : * given relid set?
981 : : */
982 : : static bool
983 : 17 : pgpa_walker_contains_join(pgpa_plan_walker_context *walker,
984 : : pgpa_join_strategy strategy,
985 : : Bitmapset *relids)
986 : : {
987 : 17 : List *join_strategies = walker->join_strategies[strategy];
988 : :
989 [ + + + + : 35 : foreach_ptr(Bitmapset, jsrelids, join_strategies)
+ + + + +
+ + + ]
990 : : {
991 [ + + ]: 13 : if (bms_equal(jsrelids, relids))
992 : 12 : return true;
993 : 6 : }
994 : :
995 : 5 : return false;
996 : 17 : }
997 : :
998 : : /*
999 : : * Does the walker say that the given relids should be marked as NO_GATHER?
1000 : : */
1001 : : static bool
1002 : 7 : pgpa_walker_contains_no_gather(pgpa_plan_walker_context *walker,
1003 : : Bitmapset *relids)
1004 : : {
1005 : 7 : return bms_is_subset(relids, walker->no_gather_scans);
1006 : : }
|
